# Egison

Paradigm | functional, lazy/non-strict |
---|---|

Designed by | Satoshi Egi |

First appeared | 2011 |

Typing discipline | Dynamic |

OS | Cross-platform |

Filename extensions | `.egi` |

Website | www |

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.^{[1]}
Its interpreter has been implemented in Haskell and open-sourced under MIT licence.^{[2]}

## Features of pattern matching[edit]

This section is written like a manual or guidebook. (October 2018) (Learn how and when to remove this template message) |

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]

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]

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]

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]

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]

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]

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]

- ↑ IPSJ Software Japan Award
- ↑ https://github.com/egison/egison/
- ↑
^{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. - ↑ 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. - ↑ 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]

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.