Egison

Egison
パラダイム	関数型言語、パターンマッチ指向
設計者	江木聡志
型付け	強い動的型付け
影響を受けた言語	Scheme、Haskell
	テンプレートを表示

■カテゴリ / ■テンプレート

Egison（エギソン）はパターンマッチ指向のプログラミング言語である。2014年にはInfoWorldで「活気のある10のプログラミング言語」の1つに選出されている。^[1]

Egisonの設計・開発は江木聡志によるもので、2015年には情報処理学会ソフトウェアジャパンアワードと第10回日本OSS奨励賞を受賞している。^[2]^[3]

構文

version 3までは(Lispのような)S式の構文を持っていたが、version 4から中置記法（:=，++，::，+など）をサポートするなど、Haskellのような構文に変わっている。

新旧の併記のないコードは新構文(Ver.4以降)で記した。

パターンマッチの特徴

Egisonは、効率的でかつ強力な表現力をもつパターンマッチが特徴のプログラミング言語である。 Egisonのパターンマッチは、以下のような特徴をもつ。^[4]

値パターン

#(p + 2)のように#からはじまるパターンは、値パターンと呼ばれる、値の同値性をチェックするパターンである。パターンマッチのターゲットと、値パターンの中身（この例の場合，#(p + 2)）が同値であった場合にパターンマッチに成功する。

双子素数のパターンマッチ

-- 素数の無限リストから全ての双子素数をパターンマッチにより抽出
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)

述語パターンの先頭は、?からはじまり、?のあとには 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 パターン|は、p + 2とp + 4の両方にマッチするために使われている。

and パターン&は、p + 2またはp + 4にマッチした場合、その値を$mに束縛するために使われている。

この 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 つ組もターゲットのリストには含まれていないため、これらのmatchAll式は両方とも空リストを返す。2 つ目の matchAll式が評価されるとき、Egison 処理系は 2 つ目の#xのパターンマッチまで行き着かない。1 つ目の#xでパターンマッチが失敗するからである。それゆえ、両方のmatchAll式の時間計算量は同じである。

旧構文

旧構文では値パターンは,(+ x 1)のように,からはじまる。旧記法におけるconsは、新記法では中置の::に、旧記法におけるjoinは、新記法では中置の++に、変わっている。

(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

パターンの多相性

同じパターンを複数のデータ型に対するパターンマッチで使いまわせる。リストだけでなく、多重集合や、集合のパターンマッチもサポート可能な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])]

旧構文

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

パターンコンストラクタだけでなく、値の同値性をチェックする値パターンも多相性を持っている。

新構文

matchAll [1..3] as list integer with #[2,1,3] -> "Matched"
-- []
matchAll [1..3] as multiset integer with #[2,1,3] -> "Matched"
-- ["Matched"]

旧構文

(match-all {1 2 3} (list integer) [,{2 1 3} "Matched"]) ; {}
(match-all {1 2 3} (multiset integer) [,{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}]}]})))

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

無限の結果を持つパターンマッチ

無限の結果をもつパターンマッチをサポートしている。パターンマッチの探索空間が無限に大きい場合でも、すべての解を列挙するように、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)]

既出の双子素数 twinPrimesも参照。

旧構文

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

;; 最初の6個の双子素数を列挙
(take 6 twin-primes) ; {[3 5] [5 7] [11 13] [17 19] [29 31] [41 43]}

中置演算子の定義

Egison はユーザーが新しく中置演算子を定義する機能を提供している．中置演算子を宣言するには，infix，または infixl，infixrを使う．infix，infixl，infixrはそれぞれ結合性のない演算子，左結合の演算子，右結合の演算子を定義するのに使う．infix，infixl，infixrは共通して三つの引数をとる．第一引数には，これから定義する中置演算子が関数であるのか，パターンコンストラクタであるのか指定するために，expressionかpatternというキーワードをとる．第二引数には，これから定義する中置演算子の優先度を整数値でとる．第三引数には，これから定義する中置演算子の名前をとる．

中置演算子として使う関数を定義する例として排他的論理和を|^|として定義する。

-- 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と同様に関数はカリー化されている。標準ライブラリのfilter関数は第一引数に残す要素を判定する関数をとる。

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
#!/usr/bin/env egison

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

数式処理システムは、 $x+x\to 2x$ や $(x+y)^{2}\to x^{2}+2xy+y^{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には微分計算をするための関数d/dがライブラリ関数として実装されている。

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はアインシュタインの縮約記法を含むテンソルの添字表記法をサポートしている。^[5]^[6]

上添字は~、下添字は_を使ってプログラム上で表現される。

例えば、リーマン曲率テンソルの公式を以下のようにプログラムとしてそのまま記述できる。

$R^{i}{}_{jkl}={\frac {\partial \Gamma ^{i}{}_{lj}}{\partial x^{k}}}-{\frac {\partial \Gamma ^{i}{}_{kj}}{\partial x^{l}}}+\Gamma ^{i}{}_{km}\Gamma ^{m}{}_{lj}-\Gamma ^{i}{}_{lm}\Gamma ^{m}{}_{kj}$

新構文

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

脚注

外部リンク

egison.org - 公式サイト

[1] ttps://www.infoworld.com/article/2606823/application-development/146094-Ten-useful-programming-languages-you-might-not-know-about.html

[2] ソフトウェアジャパンアワード

[3] 「第10回日本OSS貢献者賞・日本OSS奨励賞」

[#1-4] ttps://arxiv.org/abs/1808.10603

[5] ttps://arxiv.org/abs/1702.06343

[6] ttp://www.schemeworkshop.org/2017/Scheme17_egi.pdf

[1]

[2]

[3]

[4]

[5]

[6]

表話編歴 LISP系言語
言語（処理系）	AutoLISP（英語版） Clojure Common Lisp Emacs Lisp Interlisp ISLISP（英語版） LFE（英語版） LISP LISPマシン Lush Maclisp Scheme GNU Guile MIT/GNU Scheme Gauche Chicken Kawa Racket SKILL Steel Bank Common Lisp
関連項目	S式 SRFI ラムダ計算