Welcome to EverybodyWiki ! Sign in or create an account to improve, watchlist or create an article like a company page or a bio (yours ?)...

# Egison

Paradigm functional, lazy/non-strict Satoshi Egi 2011; 8 years ago Dynamic Cross-platform .egi www.egison.org Scheme, Haskell, Prolog, Curry

Egison is a functional programming language that features customizable pattern-matching facility for non-free data types. The creator of the language was awarded Software Japan Award from Information Processing Society of Japan. Its interpreter has been implemented in Haskell and open-sourced under MIT licence.

## Features of pattern matching

Egison is a programming language that features efficient, expressive, and customizable pattern-matching facility. Pattern matching of Egison fulfills the following features.

### Efficient backtracking algorithm for non-linear patterns

Egison supports non-linear pattern matching. Non-linear patterns are patterns that allow multiple occurrences of same variables in a pattern. Egison can process non-linear pattern matching with multiple results efficiently by using backtracking. In the following samples, patterns that prepend , as ,(+ x 1) are called value patterns. A value pattern is a pattern that matches when the value in the pattern is equal to the target.

(match-all (take n (repeat 0)) (multiset integer)
[<cons $x <cons ,(+ x 1) _>> x]) ; returns {} in O(n^2) time (match-all (take n (repeat 0)) (multiset integer) [<cons$x <cons ,(+ x 1) <cons ,(+ x 2) _>>> x])
; returns {} in O(n^2) time


### Polymorphic patterns

This feature allows users to use the same pattern for different data types. Data of non-free data types can be pattern-matched as different data types in programs. For example, a collection {1 2 3} is pattern-matched sometimes as a list and other times as a multiset or a set as follows. Therefore, polymorphic patterns are useful to decrease the number of pattern constructors and improve the readability of patterns.

(match-all {1 2 3} (list integer) [<cons $x$rs> [x rs]])
; {[1 {2 3}]}
(match-all {1 2 3} (multiset integer) [<cons $x$rs> [x rs]])
; {[1 {2 3}] [2 {1 3}] [3 {1 2}]}
(match-all {1 2 3} (set integer) [<cons $x$rs> [x rs]])
; {[1 {1 2 3}] [2 {1 2 3}] [3 {1 2 3}]}


Polymorphic patterns are also useful when we use value patterns as follows.

(match-all {1 2 3} (list integer) [,{2 1 3} "Matched"]) ; {}
(match-all {1 2 3} (multiset integer) [,{2 1 3} "Matched"]) ; {"Matched"}


### Extensibility of pattern matching

Users can customize a pattern-matching algorithm for each pattern by defining matchers. For example, users can define matchers for lists, multisets, sets, graphs, and mathematical expressions by themselves.

(define $unordered-pair (lambda [$a]
(matcher {[<pair > [a a] {[<Pair $x$y> {[x y] [y x]}]}]
[$[something] {[$tgt {tgt}]}]})))

(match-all <Pair 2 5> (unordered-pair integer) [<pair ,5 $x> x]) ; {2}  (define$multiset
(lambda [$a] (matcher {[<nil> [] {[{} {[]}] [_ {}]}] [<cons$ $> [a (multiset a)] {[$tgt (match-all tgt (list a)
[<join $hs <cons$x $ts>> [x (append hs ts)]])]}] [,$val []
{[$tgt (match [val tgt] [(list a) (multiset a)] {[[<nil> <nil>] {[]}] [[<cons$x $xs> <cons ,x ,xs>] {[]}] [[_ _] {}]})]}] [$ [something] {[$tgt {tgt}]}]})))  ### Pattern matching with infinitely many results The pattern-matching algorithm of Egison is designed to enumerate all pattern-matching results even for the cases that the search space of pattern matching is infinitely large. (take 8 (match-all nats (set integer) [<cons$m <cons $n _>> [m n]])) ; {[1 1] [1 2] [2 1] [1 3] [2 2] [3 1] [1 4] [2 3]}  (define$twin-primes
(match-all primes (list integer)
[<join _ <cons $p <cons ,(+ p 2) _>>> [p (+ p 2)]])) ;; Enumerate first 6 twin primes. (take 6 twin-primes) ; {[3 5] [5 7] [11 13] [17 19] [29 31] [41 43]}  ## Features as computer algebra system A computer algebra system is implemented on Egison as an application of its pattern-matching facility. This computer algebra system has the following feature. ### Tensor index notation Egison supports tensor index notation including Einstein summation notation. For example, the formula of Riemann curvature tensor is coded in Egison as follows. $R^{i}{}_{jkl}={\frac {\partial \Gamma ^{i}{}_{lj}}{\partial x^{k}}}-{\frac {\partial \Gamma ^{i}{}_{kj}}{\partial x^{l}}}+\Gamma ^{i}{}_{km}\Gamma ^{m}{}_{lj}-\Gamma ^{i}{}_{lm}\Gamma ^{m}{}_{kj}$ (define$R~i_j_k_l
(with-symbols {m}
(+ (- (∂/∂ Γ~i_j_l x~k) (∂/∂ Γ~i_j_k x~l))
(- (. Γ~m_j_l Γ~i_m_k) (. Γ~m_j_k Γ~i_m_l)))))