---

The aim of this document is to explain the concept of Egison as quickly as possible.
We use pseudocode of Haskell to make it easy to understand for those who don't used to parenthesized syntax.

---

Introduction

Pattern-matching is an important feature of programming languages.
Pattern-matching enables us to express data decomposition and conditional branches in a simple pattern-matching expression.

However, the existing pattern-matching expressions have a problem that they are only capable against the limited range of data types.
For example, they are good at pattern-matching against lists, but not good at pattern-matching against multisets and sets that ignore the order of the elements.
Therefore, there still exist data operations that we cannot express directly.

Egison is a programming language designed to solve this problem.

In the following sample code, we are enumerating the elements that appear multiple times in a collection.
If we write it in the existing languages in a naive way without using library functions, we need to write nested loops and a conditional branch.
If we write it in Egison, we can write it in a single pattern-matching expression.

In the following sections, we will explain what is the novelty of Egison with specific examples.

Syntax of Pattern-Matching

Let us introduce the syntax of the match-all expression.
We can explain the concept of Egison with only this expression.

(match-all {1 2 3} ; Target (list integer) ; Matcher [<cons $x $xs> [x xs]] ; Match-Clause: [Pattern Body] ) ;=>{[1 {2 3}]} ; Result

The characteristic of our match-all expression is it takes a matcher. Our interpreter matches the target with the pattern in the way specified with the matcher.
A matcher specifies the way of pattern-matching.

If we wrote the same meaning code in Haskell, it will be as follow. (The following code does not run because Haskell does not support such kind of syntax for now.)

matchAll [1, 2, 3] as -- Target ('as' is a reserved word for pattern-matching) (List Integer) with -- Matcher ('with' is a reserved word for pattern-matching) x:xs -> (x, xs) -- Match-Clause: Pattern -> Body -- =>[(1,[2,3])] -- Result

Modularization of the Way of Pattern-Matching

We can define the way of pattern-matching for each data type.
In the following example, we do pattern-matching against a collection as a list, multiset and set respectively.
The pattern constructor cons divides a collection into an element and the rest.
The meaning of cons varies for each matcher and is defined in Egison libraries for each matcher.

(match-all {1 2 3} (list integer) [<cons $x $xs> [x xs]]) ;=>{[1 {2 3}]} (match-all {1 2 3} (multiset integer) [<cons $x $xs> [x xs]]) ;=>{[1 {2 3}] [2 {1 3}] [3 {1 2}]} ; The order of elements is ignored (match-all {1 2 3} (set integer) [<cons $x $xs> [x xs]]) ;=>{[1 {1 2 3}] [2 {1 2 3}] [3 {1 2 3}]} ; The order and duplication of elements are ignored matchAll [1, 2, 3] as (List Integer) with x:xs -> (x, xs) -- =>[(1,[2,3])] matchAll [1, 2, 3] as (Multiset Integer) with x:xs -> (x, xs) -- =>[(1,[2,3]),(2,[1,3]),(3,[1,2])] ; The order of elements is ignored matchAll [1, 2, 3] as (Set Integer) with x:xs -> (x, xs) -- =>[(1,[1,2,3]),(2,[1,2,3]),(3,[1,2,3])] ; The order and duplication of elements are ignored

Please note that we are handling pattern-matching with multiple results.
This feature is necessary to pattern-matching against data types whose data have no standard form such as multisets and sets.
This is because they have multiple ways of destruction.

We can extract two elements from a collection with the nested cons pattern.

(match-all {1 2 3} (list integer) [<cons $x <cons $y _>> [x y]]) ;=>{[1 2]} (match-all {1 2 3} (multiset integer) [<cons $x <cons $y _>> [x y]]) ;=>{[1 2] [1 3] [2 1] [2 3] [3 1] [3 2]} (match-all {1 2 3} (set integer) [<cons $x <cons $y _>> [x y]]) ;=>{[1 1] [1 2] [2 1] [1 3] [2 2] [3 1] [2 3] [3 2] [3 3]} matchAll [1, 2, 3] as (List Integer) with x:y:_ -> (x, y) -- =>[(1,[2,3])] matchAll [1, 2, 3] as (Multiset Integer) with x:y:_ -> (x, y) -- =>[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)] matchAll [1, 2, 3] as (Set Integer) with x:y:_ -> (x, y) -- =>[(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(2,3),(3,2),(3,3)]

We have the join pattern constructor, which divides a collection into two collections.
The meaning of join also varies for each matcher and is defined in Egison libraries for each matcher.

(match-all {1 2 3} (list integer) [<join $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{1} {2 3}] [{1 2} {3}] [{1 2 3} {}]} (match-all {1 2 3} (multiset integer) [<join $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{1} {2 3}] [{2} {1 3}] [{3} {1 2}] [{1 2} {3}] [{1 3} {2}] [{2 3} {1}] [{1 2 3} {}]} matchAll [1, 2, 3] as (List Integer) with xs ++ ys -> (xs, ys) -- =>[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])] matchAll [1, 2, 3] as (Multiset Integer) with xs ++ ys -> (xs, ys) -- =>[([],[1,2,3]),([1],[2,3]),([2],[1,3]),([3],[1,2]),([1,2],[3]),([1,3],[2]),([2,3],[1]),([1,2,3],[])]

Let us emphasize that we can define matchers such as list, multiset and set and pattern-constructors such as cons and join by ourselves.

Non-Linear Patterns

We can handle multiple occurrence of same variables in a pattern.
Patterns that have , ahead are called value-patterns.
In many cases, it is natural to check equality by a value-pattern.
We can define how to handle value-patterns for each data type in the matcher.

(match-all {1 2 3 3 2 4} (multiset integer) [<cons $x <cons ,x _>> x]) ;=>{2 3 3 2} matchAll [1, 2, 3, 3, 2, 4] as (Multiset Integer) with x:x:_ -> x -- =>[2,3,3,2]

Egison is purely functional programming language. We can directly handle pattern-matching against infinite collections as Haskell.
Please also note that, we can write an any expression in a value pattern.

(take 10 (match-all primes (list integer) [<join _ <cons $p <cons ,(+ p 2) _>>> ; patterns for twin primes [p (+ p 2)]])) ;=>{[3 5] [5 7] [11 13] [17 19] [29 31] [41 43] [59 61] [71 73] [101 103] [107 109]} take 10 (matchAll primes as (List Integer) with (_ ++ (p : p+2 : _))) -> (p, p+2)) -- =>[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61),(71,73),(101,103),(107,109)]

Non-linear patterns extend the expressive power of pattern-matching so much.
It eliminates deeply nested loops and conditional branches.
Please check our Poker Hands Demonstration.

We can do pattern-matching also against nested data types such as lists of sets and sets and sets. The following code enumerates common elements among collections inside a collection that contains three collections.

(match-all {{1 2 3 4 5} {4 5 1} {6 1 7 4}} (list (multiset integer)) [<cons <cons $n _> <cons <cons ,n _> <cons <cons ,n _> <nil>>>> n]) ;=>{1 4} matchAll [[1, 2, 3, 4, 5], [4, 5, 1] [6, 1, 7, 4]] as List (Multiset Integer) with (n:_):(n:_):(n:_):[] -> n -- =>[1,4]

Lexical Scoping of Patterns

We can modularize useful patterns with pattern-functions, functions that receive patterns and return a pattern.
Since a pattern-function has lexical scoping, useful patterns can be reused in many places in a program without worry of name clash.

(define $twin (pattern-function [$pat1 $pat2] <cons (& $pat pat1) <cons ,pat pat2>>)) (take 1 (match-all {1 2 1 3 2} (multiset integer) [(twin $m (twin $n _)) [m n]])) ;=>{[1 2]}

This feature enables us to write complex patterns very simply.
Please check our Mahjong Demonstration.

Conclusion

The combination of all of the following features realizes intuitive powerful pattern-matching.

Modularization of the way of pattern-matching

We can define the way of pattern-matching for each data types.
For example, we can define how to pattern-match against lists, multiset, and sets respectively.

Multiple pattern-matching results

We can handle pattern-matching that has multiple results with backtracking.
This feature is necessary to pattern-matching against data types whose data have no standard form.

Non-linear patterns

We can handle multiple occurrence of same variables in a pattern.

Lexical scoping of patterns

We can modularize useful patterns with pattern-functions, functions that receive patterns and return a pattern.
Since a pattern-function has lexical scoping, bindings for pattern-variables in the argument patterns and the body of pattern-functions don't conflict.
Useful patterns can be reused in many places in a program without worry of name clash.

See Also ...

We have written a lot of documentations about Egison pattern-matching. Please refer the following articles, too.

• Egison Manual - Pattern Matching
• The 3 Exciting Moments Developing Egison

We also recommend you to read the chapter Pattern-Matching Mechanism, if you are interested in the mechanism pattern-matching inside Egison.

What to do next...

Egison Paper on arXiv.org » View More Demonstrations » Back to Home