Egison

Egison

Paradigm	functional, lazy/non-strict
Designed by	Satoshi Egi
First appeared	2011 (2011)
Typing discipline	Dynamic
OS	Cross-platform
Filename extensions	.egi
Website	www.egison.org
Influenced by
Scheme, Haskell, Prolog, Curry

Search Egison on Amazon.

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)))))

External links

• egison.org

This article "Egison" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Egison. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• SETL
• L Sharp
• Pascal-p2
• Python (programming language)
• Cayenne (programming language)
• CoSpaces
• Zig Programming Language

---