Egison

Egison（エギソン）はパターンマッチ指向のプログラミング言語である。2014年にはInfoWorldで「活気のある10のプログラミング言語」の1つに選出されている。
Egisonの設計・開発は江木聡志によるもので、2015年には情報処理学会ソフトウェアジャパンアワードと第10回日本OSS奨励賞を受賞している。
構文.
version 3までは(Lispのような)S式の構文を持っていたが、version 4から中置記法（:=，++，::，+など）をサポートするなど、Haskellのような構文に変わっている。
新旧の併記のないコードは新構文(Ver.4以降)で記した。
パターンマッチの特徴.
Egisonは、効率的でかつ強力な表現力をもつパターンマッチが特徴のプログラミング言語である。
Egisonのパターンマッチは、以下のような特徴をもつ。
値パターン.
codice_1のようにcodice_2からはじまるパターンは、値パターンと呼ばれる、値の同値性をチェックするパターンである。
パターンマッチのターゲットと、値パターンの中身（この例の場合，codice_1）が同値であった場合にパターンマッチに成功する。
双子素数のパターンマッチ
-- 素数の無限リストから全ての双子素数をパターンマッチにより抽出
def twinPrimes := matchAll primes as list integer with
 | _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)
take 8 twinPrimes
-- [(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)]
述語パターン.
上記の双子素数のパターンマッチを述語パターンで記述する。
def twinPrimes := matchAll primes as list integer with
 | _ ++ $p :: ?(\q -> q = p + 2) :: _ -> (p, p + 2)
述語パターンの先頭は、codice_4からはじまり、codice_4のあとには 1 引数の述語が続く。
述語を引数に取り述語パターンにする事も出来る。
def filter pred xs := matchAll xs as list something with
 | _ ++ (?pred & $x) :: _ -> x
filter (= 2) [1,2,3,4] -- [2]
and パターン・or パターン.
and パターンと or パターンの使用例として、三つ子素数を抽出するパターンマッチを紹介する。
def primeTriples := matchAll primes as list integer with
 | _ ++ $p :: ((#(p + 2) | #(p + 4)) & $m) :: #(p + 6) :: _
 -> (p, m, p + 6)
take 6 primeTriples -- [(5,7,11),(7,11,13),(11,13,17),(13,17,19),(17,19,23),(37,41,43)]
or パターンcodice_6は、codice_7とcodice_8の両方にマッチするために使われている。
and パターンcodice_9は、codice_7またはcodice_8にマッチした場合、その値をcodice_12に束縛するために使われている。
この and パターンの使い方は、Haskell に提供されている as パターンの使い方に似ている。
非線形パターンに対する効率的なバックトラッキング.
非線形パターン（1つのパターン内で同じ変数が複数現れるパターン）に対するパターンマッチをサポートしている。
また、パターンマッチのよるデータの分解方法が複数ある場合でも、パターンマッチのための探索空間を効率よくバックトラッキングする。
新構文.
matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ -> x
-- O(nˆ2) で [] を返す
matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ ++ #x :: _ -> x
-- O(nˆ2) で [] を返す
上記の 2 つのマッチ式は、1 から n までの整数のリストから同じ要素の 2 つ組、3 つ組をそれぞれ抽出する。同じ要素の 2 つ組も 3 つ組もターゲットのリストには含まれていないため、これらのcodice_13式は両方とも空リストを返す。2 つ目の codice_13式が評価されるとき、Egison 処理系は 2 つ目のcodice_15のパターンマッチまで行き着かない。1 つ目のcodice_15でパターンマッチが失敗するからである。それゆえ、両方のcodice_13式の時間計算量は同じである。
旧構文.
旧構文では値パターンはcodice_18のようにcodice_19からはじまる。
旧記法におけるcodice_20は、新記法では中置のcodice_21に、
旧記法におけるcodice_22は、新記法では中置のcodice_23に、変わっている。
 [<cons $x <cons ,(+ x 1) _» x])
 [<cons $x <cons ,(+ x 1) <cons ,(+ x 2) _»> x])
パターンの多相性.
同じパターンを複数のデータ型に対するパターンマッチで使いまわせる。
リストだけでなく、多重集合や、集合のパターンマッチもサポート可能なEgisonでは、同じデータをプログラムの違う箇所で別々のデータ型としてパターンマッチすることがある。
例えば、あるリストデータが、ある場所では多重集合として、別の場所ではリストとして、パターンマッチされることが起こりうる。
そのため、パターンの多相性は、パターン記述のために覚えなければならないパターンコンストラクタの名前の数を減らし、パターンの簡潔な記述に役に立つ。
新構文.
matchAll [1..3] as list integer with $x :: $rs -> (x, rs)
-- [(1, [2, 3])]
matchAll [1..3] as multiset integer with $x :: $rs -> (x, rs)
-- [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]
matchAll [1..3] as set integer with $x :: $rs -> (x, rs)
-- [(1, [1, 2, 3]), (2, [1, 2, 3]), (3, [1, 2, 3])]
旧構文.
パターンコンストラクタだけでなく、値の同値性をチェックする値パターンも多相性を持っている。
新構文.
matchAll [1..3] as list integer with #[2,1,3] -> "Matched"
matchAll [1..3] as multiset integer with #[2,1,3] -> "Matched"
-- ["Matched"]
パターンの拡張性.
パターンごとのデータの分解アルゴリズムを保持するオブジェクトであるマッチャーを、ユーザーが自身で定義できる。
例えば、リスト、多重集合、集合それぞれに対してパターンマッチの方法をユーザが定義できる。
新構文.
def unorderedPair := matcher
 | pair $ $ as (something, something) with
 | ($x, $y) -> [(x, y), (y, x)]
 | $ as something with
 | $tgt -> [tgt]
matchAll (2, "five") as unorderedPair with pair #"five" $x -> x -- [2]
def multiset a := matcher
 | [] as () with
 | $tgt -> match tgt as (mutiset a) with
 | _ -> []
 | $ :: $ as (a, multiset a) with
 | $tgt -> matchAll tgt as list a with
 | $hs ++ $x :: $ts -> (x, hs ++ ts)
 | #$val as () with
 | $tgt -> match (val, tgt) as (list a, multiset a) with
 | ($x :: $xs, #x :: #xs) -> [()]
 | (_, _) -> []
 | $ as something with
 | $tgt -> [tgt]
旧構文.
(define $unordered-pair
 (lambda [$a]
 (matcher {[<pair $ $> [a a] {[<Pair $x $y> {[x y] [y x]}]}]
 [$ [something] {[$tgt {tgt}]}]})))
(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}]}]})))
無限の結果を持つパターンマッチ.
無限の結果をもつパターンマッチをサポートしている。
パターンマッチの探索空間が無限に大きい場合でも、すべての解を列挙するように、Egisonは設計されている。
新構文.
take 8 $ matchAll nats as set integer with $m :: $n :: _ -> (m, n)
-- [(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3)]
[[Egison#値パターン|既出]] の [[双子素数]] twinPrimesも参照。
旧構文.
(define $twin-primes
 (match-all primes (list integer)
 [<join _ <cons $p <cons ,(+ p 2) _»> [p (+ p 2)]]))
中置演算子の定義.
Egison はユーザーが新しく中置演算子を定義する機能を提供している．中置演算子を宣言するには，infix，または infixl，infixrを使う．infix，infixl，infixrはそれぞれ結合性のない演算子，左結合の演算子，右結合の演算子を定義するのに使う．infix，infixl，infixrは共通して三つの引数をとる．第一引数には，これから定義する中置演算子が関数であるのか，パターンコンストラクタであるのか指定するために，expressionかpatternというキーワードをとる．第二引数には，これから定義する中置演算子の優先度を整数値でとる．第三引数には，これから定義する中置演算子の名前をとる．
中置演算子として使う関数を定義する例として排他的論理和をcodice_24として定義する。
-- Define a right-associative infix '|^|' of priority 3.
infixr expression 3 |^|
-- Definition of '|^|'.
def (|^|) a b := match (a, b) as (eq, eq) with
 | (#True, #False) -> True
 | (#False, #True) -> True
 | _ -> False
中置演算子として使うパターンコンストラクタを定義する例
-- Define a left-associative infix '<>' of priority 7.
infixl pattern 7 <>
def exampleMatcher := matcher
 | $ <> $ as (integer, integer) with
 | $x :: $y :: [] -> [(x, y)]
 | _ -> []
match [1, 2] as exampleMatcher with $x <> $y -> x + y
---> 3
関数のカリー化と部分適用.
Haskellと同様に関数は[[カリー化]]されている。
標準ライブラリのcodice_25関数は第一引数に残す要素を判定する関数をとる。
filter (> 0) [-4, 5, 0, 3, -1, 9] -- [5, 3, 9]
ここで、部分適用を使うと整数のリストから正の値のみを取り出す関数positivesは次のように定義できる。
def positives := filter (> 0)
positives [-4, 5, 0, 3, -1, 9] -- [5, 3, 9]
その他の例.
[[逆ポーランド記法]]評価器の例
def calc ls :=
 let f ls str :=
 match ls as list something with
 | $x :: $y :: $zs ->
 match str as string with
 | #"+" -> y + x :: zs
 | #"-" -> y - x :: zs
 | #"*" -> y * x :: zs
 | #"/" -> y / x :: zs
 | _ -> read str :: ls
 in
 let words := S.split " "
 in
 foldl f [] $ words ls
calc "1 2 / pi *" -- [pi / 2]
空リストを初期状態とし、f を使って一語ずつ文字列を解釈していく。f は、注目している語が演算子ならばその演算を実行し、それ以外ならば計算スタックに積んでいる。
IO 入出力.
Haskell と同じような方法で副作用をもつプログラムを記述出来る。
Hello world!
def main args := write "Hello world!\n"
Egison でつくったスクリプトをコマンドにしたい場合はシェバン（shebang）を使えばよい。
$ cat args.egi
def main args := write (show args)
$ ./args.egi hello world 1
["hello", "world", "1"]
do 式.
do式は Haskell の do記法に対応している。
def main args := repl
def repl := do
 write "» "
 flush ()
 let line := readLine ()
 print line
 flush ()
 repl
Egison は静的型システムを持つ言語ではないため，do式は多相的ではない。
Haskell の do式は、リストモナドや Maybe モナド、State モナド、IO モナドなどさまざまなモナドに対して使うことができるが、Egison のdo式は IO モナドに対してしか使うことができない。
[[数式処理システム]]としてのEgison.
[[数式処理システム]]は、formula_1やformula_2のようなシンボリックな計算ができる。
Egisonもこのような計算をサポートしている。
未定義変数 = シンボル.
Egisonは未束縛の変数をシンボルとして扱う。
そのため、未定義の変数をプログラム中で使ってもエラーにならない。
またシンボル同士の足し算や掛け算、冪演算が組み込みで定義されている。
x + x -- 2x
(x + y)^2 -- x^2 + 2 * x * y + y^2
数式の簡約.
sqrt x * sqrt x -- x
(sin θ)^2 + (cos θ)^2 -- 1
微分.
Egisonには微分計算をするための関数codice_26がライブラリ関数として実装されている。
d/d x x -- 1
d/d (x^2) x -- 2 * x
d/d (exp x) x -- exp x
d/d (log x) x -- 1 / x
d/d (x * log x) x -- log x + 1
d/d (1 / log x) x -- -1 / (x * (log x)ˆ2)
テンソルの添字記法.
Egisonは[[アインシュタインの縮約記法]]を含むテンソルの[[添字表記法]]をサポートしている。
上添字はcodice_27、下添字はcodice_28を使ってプログラム上で表現される。
例えば、[[リーマン曲率テンソル]]の公式を以下のようにプログラムとしてそのまま記述できる。
formula_3
新構文.
def R~i_j_k_l := withSymbols [m]
 ∂/∂ Γ~i_j_l x~k - ∂/∂ Γ~i_j_k x~l + Γ~m_j_l . Γ~i_m_k - Γ~m_j_k . Γ~i_m_l
旧構文.
(define $R~i_j_k_l
 (+ (- (∂/∂ Γ~i_j_l x~k) (∂/∂ Γ~i_j_k x~l))
 (- (. Γ~m_j_l Γ~i_m_k) (. Γ~m_j_k Γ~i_m_l)))))
外部リンク.
[[Category:プログラミング言語]]
[[Category:関数型プログラミング言語]]