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

Egison

From EverybodyWiki Bios & Wiki
Jump to navigation Jump to search




Egison
Paradigmfunctional, lazy/non-strict
Designed bySatoshi Egi
First appeared2011; 8 years ago (2011)
Typing disciplineDynamic
OSCross-platform
Filename extensions.egi
Websitewww.egison.org
Influenced by
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.[1] Its interpreter has been implemented in Haskell and open-sourced under MIT licence.[2]

Features of pattern matching[edit | edit source]

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

Efficient backtracking algorithm for non-linear patterns[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

A computer algebra system is implemented on Egison as an application of its pattern-matching facility.[3] This computer algebra system has the following feature.

Tensor index notation[edit | edit source]

Egison supports tensor index notation including Einstein summation notation.[5]

For example, the formula of Riemann curvature tensor is coded in Egison as follows.

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

References[edit | edit source]

  1. IPSJ Software Japan Award
  2. https://github.com/egison/egison/
  3. 3.0 3.1 Satoshi Egi & Yuichi Nishiwaki (2018). "Non-linear Pattern Matching with Backtracking for Non-free Data Types" (postscript or PDF). 16th Asian Symposium on Programming Languages and Systems. Retrieved 2018-09-06.
  4. Satoshi Egi (2018). "Loop Patterns: Extension of Kleene Star Operator for More Expressive Pattern Matching against Arbitrary Data Structures" (postscript or PDF). Scheme and Functional Programming Workshop 2018. Retrieved 2018-09-06.
  5. Satoshi Egi (2017). "Scalar and Tensor Parameters for Importing Tensor Index Notation including Einstein Summation Notation" (postscript or PDF). Scheme and Functional Programming Workshop 2017. Retrieved 2018-09-06.

External links[edit | edit source]


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.



Compte Twitter EverybodyWiki Follow us on https://twitter.com/EverybodyWiki !