プログラミング言語Egisonとは

まえおき

2019年Egisonアドベントカレンダーの空き日をEgisonの作者の江木が使って，Egisonの解説記事を書いていこうと思っています． これらの記事をまとめて近いうちにEgison入門書を作りたいと考えています． 1日目である本日は，Egisonの概略を紹介します．

Egisonとは？

Egisonはより直感的にアルゴリズムを表現できるプログラミング言語がほしいという動機で作られたプログラミング言語です． Egisonには，直感的なアルゴリズムの表現を達成するための2つの独自の機能が実装されています． 1つ目の機能は，ユーザーにより拡張可能でかつ，非線形パターン（パターン変数に束縛した値を同じパターン内で参照するパターン）をバックトラッキングにより効率的に処理するパターンマッチ機能です． 2つ目の機能は，微分幾何の計算を表現するのに便利なテンソルの添字記法をプログラム中で使うための機能です．

これらのEgisonの独自の機能は，筆者がいろいろなアルゴリズムのプログラムを書いているうちに，既存のプログラミング言語では思い通りに書けない事柄をみつけたときに，その解決案を見つけるためにときに年単位で試行錯誤することによって実装されました． 本日は，Egison独自の1つ目の機能である拡張可能な非線形パターンマッチについてその動機を中心に紹介します．

Egisonのパターンマッチは，2010年3月に筆者が大学の卒業研究で整数論の定理を自動で予想するプログラムを書いていたときに，多重集合や論理式についてのパターンマッチを思い通りにモジュール化する機能の必要性に気づいて，開発が始まりました． 多重集合や論理式に対してどのようなパターンマッチがしたいのか考えた結果，

• 正規表現のように非線形パターンを効率的に処理できる
• ユーザーがいろいろなデータ型に対して自身でパターンマッチエンジンを定義できる

パターンマッチシステムが必要だという結論にたどり着いて，このパターンマッチシステムを基本とした独自のプログラミング言語の開発をはじめることに決めました． その後，1年かけて設計・実装し，2011年5月に言語を完成させ，Egisonと名付けリリースしました． Egisonをリリースしたあとは，Egisonのパターンマッチ機能を使っていろいろなプログラムを書いているうちに，このパターンマッチ機能の使用法や拡張についてどんどんアイデアを思いついていき．実装していきました．

ここから先は，Egisonのパターンマッチの使用法について触れてみます． 関数型プログラミングやオブジェクト指向プログラミングには，それぞれのプログラミングパラダイムの考えを反映した様々なプログラミングテクニックがあります． 同様に，Egisonのパターンマッチを活用したプログラミングテクニックも多数あり，これらのプログラミングテクニックには共通した考え方がみえます． このような考え方をまとめて，パターンマッチ指向プログラミングと呼んでいます．

パターンマッチ指向プログラミングの例を紹介します．

パターンマッチ指向プログラミングによってプログラムの記述が直感的になっていることのわかりやすい例にintersect関数の実装があります． intersectは2つのリストを引数にとり，それらのリストに共通する要素のリストを返す関数です． Egisonを使って引数のリストをそれぞれ多重集合としてパターンマッチすると，2つのリストの共通要素にマッチするパターンを記述することにより，intersectを記述できます．（プログラムの読み方はまた別の記事で紹介します．） intersect xs ys := matchAllDFS (xs, ys) as (multiset eq, multiset eq) with | ($x :: _, #x :: _) -> x 対して，Egisonのパターンマッチを使わずに関数型プログラミングのスタイルでHaskellで記述すると，リストに対する関数を組み合わせて共通要素を抜き出すための方法を記述する必要があります． intersect xs ys = filter (\x -> any (== x) ys) xs このプログラムは，リスト内包表記を使って以下のように書き直すこともできます． intersect xs ys = [x | x <- xs, any (== x) ys]

Egisonのパターンマッチを使ったプログラムは，2つのリストの共通要素にマッチするパターンを記述しているだけであるのに対し，関数型プログラミングでは，どうやってその共通要素を取り出すかその方法をプログラマが考えて記述しています． 前者のように「何を計算したいか（what to do）」を記述するプログラミングスタイルは宣言型プログラミング，後者のように「どうのように計算するか（how to do）」を記述するプログラミングスタイルは手続き型プログラミングと呼ばれています． 「何を計算したいか」から「どのように計算するか」が明らかである場合は，「何を計算したいか」を記述する宣言型プログラミングのほうがプログラムが読みやすく簡潔になります． intersectの例の場合は，Egisonが多重集合のパターンマッチアルゴリズムをモジュール化できるおかげで，宣言的なプログラミングが可能になっています．

少し毛色の違う例として，concat関数をパターンマッチ指向プログラミングで定義します． リストのリストの要素にマッチするパターンを記述することにより，concatを定義できます． concat xss := matchAllDFS xss as list (list something) with | _ ++ (_ ++ $x :: _) :: _ -> x concat [[1,2],[3],[4,5]] -- [1,2,3,4,5]

さらにおもしろいパターンマッチ指向プログラミングの例として，unique関数を定義します． 後方に自身と同じ値が含まれない要素にマッチするパターンを記述することによりuniqueを定義できます． unique xs := matchAllDFS xs as list eq with | _ ++ $x :: !(_ ++ #x :: _) -> x unique [1,2,3,2,4] -- [1,3,2,4]

明日以降の記事では，上記のプログラムで使われているEgisonの構文や，機能，プログラミングテクニックの解説をしていきます．

参考文献

Egisonのパターンマッチについては，論文がAPLAS 2018で発表されています．

• Satoshi Egi and Yuichi Nishiwaki: Non-linear Pattern Matching with Backtracking for Non-free Data Types

テンソルの添字記法のプログラミング言語への導入については，論文がScheme Workshop 2017で発表されています．

• Satoshi Egi: Scalar and Tensor Parameters for Importing the Notation in Differential Geometry into Programming

Egisonの歴史については，BOOTHで頒布しているEgison Journal Vol. 1の筆者の記事が詳しいです．

• Egison BOOTH