- Notifications
You must be signed in to change notification settings - Fork31
The Egison Programming Language
License
egison/egison
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Egison is a functional programming language featuring its expressive pattern-matching facility.Egison allows users to define efficient and expressive pattern-matching methods for arbitrary user-defined data types including non-free data types such as lists, multisets, sets, trees, graphs, and mathematical expressions.This is the repository of the interpreter of Egison.
For more information, visitour website.
- Satoshi Egi, Yuichi Nishiwaki:Non-linear Pattern Matching with Backtracking for Non-free Data Types (APLAS 2018)
- Satoshi Egi, Yuichi Nishiwaki:Functional Programming in Pattern-Match-Oriented Programming Style ( 2020)
- Satoshi Egi:Scalar and Tensor Parameters for Importing Tensor Index Notation including Einstein Summation Notation (Scheme Workshop 2017)
We can use non-linear pattern matching for non-free data types in Egison.A non-free data type is a data type whose data have no canonical form, or a standard way to represent that object.For example, multisets are non-free data types because a multiset {a,b,b} has two other syntastically different representations: {b,a,b} and {b,b,a}.Expressive pattern matching for these data types enables us to write elegant programs.
We can use pattern matching for enumeration.The following code enumerates all twin primes from the infinite list of prime numbers with pattern matching!
def twinPrimes:= matchAll primes as list integer with| _++$p::#(p+2)::_-> (p,p+2)take8 twinPrimes-- [(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)]
The following code is a program that determines poker-hands written in Egison.All hands are expressed in a single pattern.
def poker cs:= match cs as multiset card with| card$s$n::card#s#(n-1)::card#s#(n-2)::card#s#(n-3)::card#s#(n-4)::_->"Straight flush"| card _$n::card_#n::card_#n::card_#n::_::[]->"Four of a kind"| card _$m::card_#m::card_#m::card_$n::card_#n::[]->"Full house"| card$s _::card#s_::card#s_::card#s_::card#s_::[]->"Flush"| card _$n::card_#(n-1)::card_#(n-2)::card_#(n-3)::card_#(n-4)::[]->"Straight"| card _$n::card_#n::card_#n::_::_::[]->"Three of a kind"| card _$m::card_#m::card_$n::card_#n::_::[]->"Two pair"| card _$n::card_#n::_::_::_::[]->"One pair"| _::_::_::_::_::[]->"Nothing"
We can pattern-match against graphs.We can write a program to solve the travelling salesman problem in a single pattern-matching expression.
def graph:= multiset (string, multiset (string, integer))def graphData:= [("Berlin", [("New York",14), ("London",2), ("Tokyo",14), ("Vancouver",13)]), ("New York", [("Berlin",14), ("London",12), ("Tokyo",18), ("Vancouver",6)]), ("London", [("Berlin",2), ("New York",12), ("Tokyo",15), ("Vancouver",10)]), ("Tokyo", [("Berlin",14), ("New York",18), ("London",15), ("Vancouver",12)]), ("Vancouver", [("Berlin",13), ("New York",6), ("London",10), ("Tokyo",12)])]def trips:=let n:=length graphDatain matchAll graphData as graph with| (#"Berlin", (($s_1,$p_1): _)):: loop$i (2, n-1) ((#s_(i-1), ($s_i,$p_i)::_)::...) ((#s_(n-1), (#"Berlin"&$s_n,$p_n)::_)::[])->sum (map (\i-> p_i) [1..n]),map (\i-> s_i) [1..n]car (sortBy (\(_, x), (_, y)->compare x y)) trips)-- (["London", "New York", "Vancouver", "Tokyo"," Berlin"], 46)
As an application of Egison pattern matching, we have implemented a computer algebra system on Egison.The most part of this computer algebra system is written in Egison and extensible using Egison.
Egison treats unbound variables as symbols.
> xx> (x + y)^2x^2 + 2 * x * y + y^2> (x + y)^4x^4 + 4 * x^3 * y + 6 * x^2 * y^2 + 4 * x * y^3 + y^4We can handle algebraic numbers, too.
> sqrt xsqrt x> sqrt 2sqrt 2> x + sqrt yx + sqrt yThe symboli is defined to rewritei^2 to-1 in Egison library.
> i * i-1> (1 + i) * (1 + i)2 * i> (x + y * i) * (x + y * i)x^2 + 2 * x * y * i - y^2The rewriting rule forsqrt is also defined in Egison library.
> sqrt 2 * sqrt 22> sqrt 6 * sqrt 102 * sqrt 15> sqrt (x * y) * sqrt (2 * x)x * sqrt 2 * sqrt yThe following is a sample to calculate the 5th roots of unity.
> qF' 1 1 (-1)((-1 + sqrt 5) / 2, (-1 - sqrt 5) / 2)> def t := fst (qF' 1 1 (-1))> qF' 1 (-t) 1((-1 + sqrt 5 + sqrt 2 * sqrt (-5 - sqrt 5)) / 4, (-1 + sqrt 5 - sqrt 2 * sqrt (-5 - sqrt 5)) / 4)> def z := fst (qF' 1 (-t) 1)> z(-1 + sqrt 5 + sqrt 2 * sqrt (-5 - sqrt 5)) / 4> z ^ 51We can implement differentiation easily in Egison.
> d/d (x ^ 3) x3 * x^2> d/d (e ^ (i * x)) xexp (x * i) * i> d/d (d/d (log x) x) x-1 / x^2> d/d (cos x * sin x) x-2 * (sin x)^2 + 1The following sample executes Taylor expansion on Egison.We verifyEuler's formula in the following sample.
> take 8 (taylorExpansion (exp (i * x)) x 0)[1, x * i, - x^2 / 2, - x^3 * i / 6, x^4 / 24, x^5 * i / 120, - x^6 / 720, - x^7 * i / 5040]> take 8 (taylorExpansion (cos x) x 0)[1, 0, - x^2 / 2, 0, x^4 / 24, 0, - x^6 / 720, 0]> take 8 (taylorExpansion (i * sin x) x 0)[0, x * i, 0, - x^3 * i / 6, 0, x^5 * i / 120, 0, - x^7 * i / 5040]> take 8 (map2 (+) (taylorExpansion (cos x) x 0) (taylorExpansion (i * sin x) x 0))[1, x * i, - x^2 / 2, - x^3 * i / 6, x^4 / 24, x^5 * i / 120, - x^6 / 720, - x^7 * i / 5040]Egison supports tesnsor index notation.We can useEinstein notation to express arithmetic operations between tensors.
The method for importing tensor index notation into programming is discussed inEgison tensor paper.
The following sample is fromRiemann Curvature Tensor of S2 - Egison Mathematics Notebook.
-- Parametersdef x:= [| θ, φ|]defX:= [| r* (sin θ)* (cos φ)-- x , r* (sin θ)* (sin φ)-- y , r* (cos θ)-- z|]def e_i_j:= (∂/∂X_j x~i)-- Metric tensorsdef g_i_j:= generateTensor (\x y->V.* e_x_# e_y_#) [2,2]def g~i~j:=M.inverse g_#_#g_#_#-- [| [| r^2, 0 |], [| 0, r^2 * (sin θ)^2 |] |]_#_#g~#~#-- [| [| 1 / r^2, 0 |], [| 0, 1 / (r^2 * (sin θ)^2) |] |]~#~#-- Christoffel symbolsdefΓ_i_j_k:= (1/2)* (∂/∂ g_i_k x~j+∂/∂ g_i_j x~k-∂/∂ g_j_k x~i)Γ_1_#_#-- [| [| 0, 0 |], [| 0, -1 * r^2 * (sin θ) * (cos θ) |] |]_#_#Γ_2_#_#-- [| [| 0, r^2 * (sin θ) * (cos θ) |], [| r^2 * (sin θ) * (cos θ), 0 |] |]_#_#defΓ~i_j_k:= withSymbols [m] g~i~m.Γ_m_j_kΓ~1_#_#-- [| [| 0, 0 |], [| 0, -1 * (sin θ) * (cos θ) |] |]_#_#Γ~2_#_#-- [| [| 0, (cos θ) / (sin θ) |], [| (cos θ) / (sin θ), 0 |] |]_#_#-- Riemann curvaturedefR~i_j_k_l:= withSymbols [m]∂/∂Γ~i_j_l x~k-∂/∂Γ~i_j_k x~l+Γ~m_j_l.Γ~i_m_k-Γ~m_j_k.Γ~i_m_lR~#_#_1_1-- [| [| 0, 0 |], [| 0, 0 |] |]~#_#R~#_#_1_2-- [| [| 0, (sin θ)^2 |], [| -1, 0 |] |]~#_#R~#_#_2_1-- [| [| 0, -1 * (sin θ)^2 |], [| 1, 0 |] |]~#_#R~#_#_2_2-- [| [| 0, 0 |], [| 0, 0 |] |]~#_#
By designing the index completion rules for omitted indices, we can use the above notation to express a calculation handling the differential forms.
The following sample is fromCurvature Form - Egison Mathematics Notebook.
-- Parameters and metric tensordef x:= [| θ, φ|]def g_i_j:= [| [| r^2,0|], [|0, r^2* (sin θ)^2|]|]_i_jdef g~i~j:= [| [|1/ r^2,0|], [|0,1/ (r^2* (sin θ)^2)|]|]~i~j-- Christoffel symbolsdefΓ_j_l_k:= (1/2)* (∂/∂ g_j_l x~k+∂/∂ g_j_k x~l-∂/∂ g_k_l x~j)defΓ~i_k_l:= withSymbols [j] g~i~j.Γ_j_l_k-- Exterior derivativedef d%t:=!(flip∂/∂) x t-- Wedge productinfixl expression7∧def(∧)%x%y:= x!. y-- Connection formdef ω~i_j:=Γ~i_j_#-- Curvature formdefΩ~i_j:= withSymbols [k] antisymmetrize (d ω~i_j+ ω~i_k∧ ω~k_j)Ω~#_#_1_1-- [| [| 0, 0 |], [| 0, 0 |] |]~#_#Ω~#_#_1_2-- [| [| 0, (sin θ)^2 / 2|], [| -1 / 2, 0 |] |]~#_#Ω~#_#_2_1-- [| [| 0, -1 * (sin θ)^2 / 2 |], [| 1 / 2, 0 |] |]~#_#Ω~#_#_2_2-- [| [| 0, 0 |], [| 0, 0 |] |]~#_#
Here are more samples.
There area lot of existing work for pattern matching.
The advantage of Egison is that it fulfills the following two requirements at the same time.
- Efficient backtracking algorithm for non-linear pattern matching.
- Extensibility of patterns.
Additionally, it fulfills the following requirements.
- Polymorphism of patterns.
- Pattern matching with infinitely many results.
Check outour paper for details.
Installation guide is available on our website.
If you are a beginner of Egison, it would be better to installegison-tutorial as well.
We also haveonline interpreter andonline tutorial.Enjoy!
Egison provides syntax highlighting plugins for the following editors:
- Emacs:
emacs/egison-mode.el-- Seeemacs/README.mdfor installation instructions. - Vim / Neovim:
vim/-- Seevim/README.mdfor installation instructions. - VS Code / Cursor:
vscode-extension/-- Seevscode-extension/INSTALL.mdfor installation instructions.
You can build Egison as follows:
$ cabal buildFor testing, seetest/README.md.
We havea mailing list.Please join us!
We are onTwitter.Please follow us.
Egison is released under theMIT license.
We usedhusk-scheme by Justin Ethier as reference to implement the base part of the previous version of the interpreter.
Egison is sponsored byRakuten, Inc. andRakuten Institute of Technology.
About
The Egison Programming Language
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
Uh oh!
There was an error while loading.Please reload this page.