The Egison Programming Language

Top Expressions

`define` and `test` expressions

(define $x 2)
(test (+ x 3));=>5
  
(define $f (lambda [$x $y] [(+ x y) (* x y)]))
(test (f 2 4));=>[6 8]

`load` and `load-file` expressions

; Load Egison library
(load "lib/core/number.egi")

; Load your program
(load-file "/home/xxx/code/egison/myfile.egi")

Objects

Builtin data

;; Boolean values
#t ; True
#f ; False

;; Integers  
1
0
-100
  
;; Float numbers
10.2
-100.1

;; Characters
'a'
'1'
'\n'

;; Strings
"Hello world!\n"

Composed data

We have five ways to compose data, inductive data, tuples, collections, arrays, and hashes.

;; Inductive data
<Card <Diamond> 13>
<Node 3 <Node <Leaf 1> <Leaf 2>> <Leaf 4>>

;; Tuples
[]
[1 2]
[#t "abc" 4]
[1];=>1
[[[[[[[[[[["too many"]]]]]]]]]]];=>"too many"

;; Collections
{}
{1 2 3 4 5}
{@{1 2} 3 4};=>{1 2 3 4}
{1 @{2 3} 4};=>{1 2 3 4}
{1 2 @{3 4}};=>{1 2 3 4}
{@{@{1}} @{2 @{3} 4}};=>{1 2 3 4}

;; Arrays
(define $xa (| 1 2 3 4 5 |))
(array-bounds xa);=> [1 5]
(array-ref xa 2);=>2
xa_1;=>1
xa_5;=>5

;; Hashes
(define $xh {| [1 11] [2 12] [3 13] [4 14] [5 15] |})
xh_1;=>11
xh_4;=>14

Note that, a tuple that consists of a single element is equal with the element itself.

[1];=>1
[[[[[[[[[[["too many"]]]]]]]]]]];=>"too many"

Note that we can splice collections using @ inside a collection.

{1 @{2 3} 4};=>{1 2 3 4}
{1 @{2 3 @{4}} 5};=>{1 2 3 4 5}

Functions

lambda expressions make functions as other functional programming languages.

(lambda [$x] x)
(lambda [$x $y] (* (+ x y) (- x y)))

Matchers

We can define our own matcher using a matcher expression is used to define how to pattern-match for each data type. It's too complicated to explain here, so please read the manual for that.
The following matchers are defined in the core libraries. something is an only buitin matcher.

something
integer
(list integer)
(multiset integer)
(set integer)
(list (multiset integer))

Patterns

;; Wildcard
_

;; Pattern-variables
$x
$y_1
$z_1_(+ 1 2)
$w_n

;; Value-patterns
,1
,(+ n 10)
,(id 10)

;; Predicate-patterns
?(eq? $ 10);=>,10
?(lt? $ 10)
?even?
  
;; Inductive patterns
<nil>
<cons $x $xs>
<join $xs $ys>
<join _ <cons $x_1 <join _ <cons $x_2 _>>>>

;; Not-patterns
!_
!,10
<cons $x !<cons ,x _>>

;; And-patterns
(& ,3 $n)

;; Or-patterns
(| ,3 ,4)

;; Loop-patterns
(loop $i [3 {4 5} $n] <cons $x_i ...> _)
;=><cons $x_3 <cons $x_4 (| _ <cons $x_5 _>)>>

; Syntax sugars for loop-patterns
(loop $i [3 {4 5}] <cons $x_i ...> _)
;=>(loop $i [3 {4 5} _] <cons $x_i ...> _)

(loop $i [3 5] <cons $x_i ...> _)
;=>(loop $i [3 {5} _] <cons $x_i ...> _)

(loop $i [3 $n] <cons $x_i ...> _)
;=>(loop $i [3 {3 4 5 ...} $n] <cons $x_i ...> _)

;; Pattern-functions
(pattern-function [$pat] pat)

(pattern-function [$pat1 $pat2]
    <cons (& $pat pat1) <cons ,pat pat2>>)

Syntax

Partial evaluation

We support partial evaluations.

((+ $ $) 3 4);=>7
((+ $1 $2) 3 4);=>7
((* $1 $1) 5);=>25
((map $2 $1) {1 2 3} (+ $ 1));=>{2 3 4}

(2#%1 1 2);=>1
(2#%2 1 2);=>2
(1#(not (prime? %1)) 10);=>#t
(take 10 (1#{%1 @(%0 (* %1 2))} 2))
;=>{2 4 8 16 32 64 128 256 512 1024})

`let`, `let*` and `letrec` expressions

A let and letrec expression are used for local variable bindings. The difference is that a letrec expression can used for recursive definitions. Mutual recursion is also allowed.

(let {[$x 1] [$y 2]} (+ x y));=>3

(let* {[$x 2] [$y (+ x 1)]} y)
;=>(let {[$x 2]} (let {[$y (+ x 1)]} y))
;=>3

(letrec {[$evens {2 @(map (+ $ 2) evens)}]}
  (take 10 evens))
;=>{2 4 6 8 10 12 14 16 18 20}

(letrec {[$odds {1 @(map (+ $ 1) evens)}]
         [$evens (map (+ $ 1) odds)]}
  (take 10 evens))
;=>{2 4 6 8 10 12 14 16 18 20}

`if` expressions

It's ordinary if. But, note the result of an evaluation of the first argument must be a boolean value (i.e. #t or #f).

(if #t "YES" "NO");=>"YES"
(if #f "YES" "NO");=>"NO"

`match-all` expressions

(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}]}

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

`match` expressions

(match {1 2 3 4} (list integer)
  {[<nil> #f]
   [<cons $x $xs> [x xs]]});=>[1 {2 3 4}]

(match {1 2 3 4} (set integer)
  {[<nil> #f]
   [<cons $x $xs> [x xs]]});=>[1 {1 2 3 4}]

Pattern-Matching

`cons`,`join`, and `nil`

The cons pattern is used to divide a collection into a element and the rest of the collection.

(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}]}

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

(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]}

The join pattern is used to divide a collection into two collections.

(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} {}]}

(match-all {1 2 3} (set integer)
  [<join $xs $ys> [xs ys]])
;=>{[{} {1 2 3}] [{1} {1 2 3}] [{2} {1 2 3}] [{3} {1 2 3}] [{1 2} {1 2 3}] [{1 3} {1 2 3}] [{2 1} {1 2 3}] [{2 3} {1 2 3}] [{3 1} {1 2 3}] [{1 2 3} {1 2 3}] [{3 2} {1 2 3}] [{1 3 2} {1 2 3}] [{2 1 3} {1 2 3}] [{2 3 1} {1 2 3}] [{3 1 2} {1 2 3}] [{3 2 1} {1 2 3}]}

The nil pattern matches if a collection is empty.

(match {} (list integer)
  {[<nil> #t]
   [_ #f]});=>#t

Non-linear patterns

We can write non-linear patterns.

(match-all {1 1 2 3 2} (list integer)
  [<cons $x <cons ,x _>> x])
;=>{1}

(match-all {1 1 2 3 2} (multiset integer)
  [<cons $x <cons ,x _>> x])
;=>{1 1 2 2}

(match-all {1 1 2 3 2} (multiset integer)
  [<cons $x !<cons ,x _>> x])
;=>{3}

Loop-patterns

We can write a pattern that include ....

(match-all {1 2 3 4} (list integer)
  [(loop $i [1 3] <join _ <cons $xh_i ...>> _)
   xh])
;=>{{|[1 1] [2 2] [3 3]|} {|[1 1] [2 2] [3 4]|} {|[1 1] [2 3] [3 4]|} {|[1 2] [2 3] [3 4]|}}

(match-all {1 2 3 4} (list integer)
  [(loop $i [1 $n] <join _ <cons $xh_i ...>> _)
   [n xh]])
;=>{[0 {||}] [1 {|[1 1]|}] [1 {|[1 2]|}] [1 {|[1 3]|}] [1 {|[1 4]|}] [2 {|[1 1] [2 2]|}] [2 {|[1 1] [2 3]|}] [2 {|[1 2] [2 3]|}] [2 {|[1 1] [2 4]|}] [2 {|[1 2] [2 4]|}] [2 {|[1 3] [2 4]|}] [3 {|[1 1] [2 2] [3 3]|}] [3 {|[1 1] [2 2] [3 4]|}] [3 {|[1 1] [2 3] [3 4]|}] [3 {|[1 2] [2 3] [3 4]|}] [4 {|[1 1] [2 2] [3 3] [4 4]|}]}

(match-all {1 2 3 4} (list integer)
  [(loop $i [1 {2 4} $n] <join _ <cons $xh_i ...>> _)
   [n xh]])
;=>{[2 {|[1 1] [2 2]|}] [2 {|[1 1] [2 3]|}] [2 {|[1 2] [2 3]|}] [2 {|[1 1] [2 4]|}] [2 {|[1 2] [2 4]|}] [2 {|[1 3] [2 4]|}] [4 {|[1 1] [2 2] [3 3] [4 4]|}]}

Modularization of patterns

We can reuse useful patterns with pattern-functions, functions that take patterns and return a pattern.

(define $twin
  (pattern-function [$pat1 $pat2]
    <cons (& $pat pat1) <cons ,pat pat2>>))

(match-all {1 1 2 3} (list integer)
  [(twin $n _) n]);=>{1}

(match-all {1 2 1 3} (multiset integer)
  [(twin $n _) n]);=>{1 1}

Builtin Functions

Please check here for the complete list of builtin functions.

Calculate numbers

(+ 1 2);=>3
(- 30 15);=>15
(* 10 20);=>200
(/ 20 5);=>4
(modulo 17 4);=>1
(power 2 10);=>1024

(+ 2/3 1/5);=>13/15
(/ 42 84);=>1/2

(+ 10.2 1.3);=>11.5
(* 10.2 1.3);=>13.26

(rtof 1/5);=>0.2
(rtof 1/100);=>1.0e-2

Compare numbers

We can compare numbers using the eq?, gt?, lt?, gte?, and lte? function.

(eq? 1 1);=>#t ; equal
(gt? 1 1);=>#f ; greater than
(lt? 1 1);=>#f ; less than
(gte? 1 1);=>#t ; greater than or equal
(lte? 1 1);->#t ; less than or equal

Strings

A string is a collection of characters in Egison. Therefore, we can use functions for collections to handle strings.

Type predicates

(bool? #t);=>#t
(integer? 12);=>#t
(rational? 2/3);=>#t
(float? 3.2);=>#t
(char? 'a');=>#t
(collection? {});=>#t
(collection? {1 2});=>#t

Libraries

Please check here for the Egison library list.

Collections

Please check here for the Egison collection library.

The nats is a collection that contains all natural numbers.
The primes is a collection that contains all prime numbers.
We can play with them. With the take function, we can extract a head part of the collection.

(take 3 {1 2 3 4 5});=>{1 2 3}
(take 10 nats);=>{1 2 3 4 5 6 7 8 9 10}
(take 10 primes);=>{2 3 5 7 11 13 17 19 23 29}

With the map function, we can operate each element of the collection at once.

(map (+ $ 10) {1 2 3 4 5});=>{11 12 13 14 15}
(map (* $ 2) {1 2 3 4 5});=>{2 4 6 8 10}

With the foldl function, we can gather together all elements of the collection using an operator we like.

(foldl + 0 {1 2 3 4 5});=>15
(foldl * 1 {1 2 3 4 5});=>120

With the filter function, we can extract all elements that satisfy the predicate.

(filter odd? {1 2 3 4 5});=>{1 3 5}
(filter even? {1 2 3 4 5});=>{2 4}
(take 20 (filter (lambda [$p] (eq? (modulo p 4) 1)) primes))
;=>{5 13 17 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193}

With the while function, we can extract all head elements that satisfy the predicate.

(while (lt? $ 100) primes)
;=>{2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97}

Programming Tips

Infinite collections

We can generate infinite collections recursively.

(define $ones {1 @ones})
(take 10 ones);=>{1 1 1 1 1 1 1 1 1 1}

(define $nats {1 @(map (+ $ 1) nats)})
(take 10 nats);=>{1 2 3 4 5 6 7 8 9 10}

(define $evens (map (* $ 2) nats))
(take 10 evens);=>{2 4 6 8 10 12 14 16 18 20}

(define $primes (filter prime? nats))
(take 10 primes);=>{2 3 5 7 11 13 17 19 23 29}

The results of match-all can be infinite.

(define $twin-primes
  (match-all primes (list integer)
    [<join _ <cons $p <cons ,(+ p 2) _>>>
     [p (+ p 2)]]))

(take 10 twin-primes)
;=>{[3 5] [5 7] [11 13] [17 19] [29 31] [41 43] [59 61] [71 73] [101 103] [107 109]}

This website in other langauge: English, 日本語

Egison Quick Reference