Egison

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動
Egison
パラダイム 関数型言語パターンマッチ指向
設計者 江木 聡志
型付け 強い動的型付け
影響を受けた言語 SchemeHaskell
テンプレートを表示

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

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

パターンマッチの特徴[編集]

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

非線形パターンに対する効率的なバックトラッキング[編集]

非線形パターン(1つのパターン内で同じ変数が複数現れるパターン)に対するパターンマッチをサポートしている。 また、パターンマッチのよるデータの分解方法が複数ある場合でも、パターンマッチのための探索空間を効率よくバックトラッキングする。 ,(+ x 1)のように,からはじまるパターンは、バリューパターンと呼ばれる、値の同値性をチェックするパターンである。 パターンマッチのターゲットと、バリューパターンの中身(この例の場合,(+ x 1))が同値であった場合にパターンマッチに成功する。

(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では、同じデータをプログラムの違う箇所で別々のデータ型としてパターンマッチすることがある。 例えば、あるリストデータが、ある場所では多重集合として、別の場所ではリストとして、パターンマッチされることが起こりうる。 そのため、パターンの多相性は、パターン記述のために覚えなければならないパターンコンストラクタの名前の数を減らし、パターンの簡潔な記述に役に立つ。

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

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

(match-all {1 2 3} (list integer) [,{2 1 3} "Matched"]) ; {}
(match-all {1 2 3} (multiset integer) [,{2 1 3} "Matched"]) ; {"Matched"}

パターンの拡張性[編集]

パターンごとのデータの分解アルゴリズムを保持するオブジェクトであるマッチャーを、ユーザーが自身で定義できる。 例えば、リスト、多重集合、集合それぞれに対してパターンマッチの方法をユーザが定義できる。

(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 (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の上には、そのパターンマッチを応用して、数式処理システムが実装されている。[5] この数式処理システムは以下のような機能をもっている。

テンソルの添字記法[編集]

Egisonはアインシュタインの縮約記法を含むテンソルの添字記法をサポートしている。[6][7]

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

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


脚注[編集]

外部リンク[編集]