プログラミング言語 Egison
この資料は株式会社オプトの社内勉強会で発表するために作られています。
発表の目的
今回の発表の目的はこんな感じです。
- Egison の認知拡大
- Egison に興味を持った人がより深く学ぶ方法を提示
Egison とは？
Egison (エギソン) は強力なパターンマッチを特徴とするプログラミング言語です。
2011年に江木 聡志さんが東京大学大学院修士課程で開発を始めました。
そのあたりの歴史が公式サイトに載っているのですが、人間味溢れていて面白いです。
インストール
公式サイトのドキュメントタブからインストール方法にたどり着けます。
Homebrew を使ったインストール
macOS で Homebrew を使っている方は
$ brew update
$ brew tap egison/egison
$ brew install egison
でインストールできます。
インストールが完了すると、
$ egison
で Egison インタープリターが立ち上がります。
本来であれば egison-tutorial というコマンドも同時にインストールされて、 Egison のチュートリアルをローカル環境で遊べるはずなのですが、私の環境ではうまく動きませんでした。
Haskell 拡張を開発している関係で現在は egison-tutorial が壊れているらしいです。
オンラインチュートリアルも同様に壊れています。
残念。
Haskell Platform を使ったインストール
Homebrew を使ったインストールよりも手間がかかりますが、こちらは egison-tutorial コマンドも動きます。
$ curl https://get-ghcup.haskell.org -sSf | sh
で Haskell Platform をインストールします。
このとき、多少プロンプトが出るので、適当に答えます。
インストールできると cabal コマンドが使えるようになるので、
$ cabal update
$ cabal install egison egison-tutorial
で egison と egison-tutorial が使えるようになります。
Egison の嬉しさ
map 関数の例
Egison Journal Vol. 2 の付録 3 にいい感じの例が載っていたので参考にします。
関数型プログラミングをしたことのない新入エンジニアに 「map 関数って何をする関数ですか？」 と質問されたら何と答えますか？
「関数とリストを引数にとり、(*) する関数です」
という答えの (*) をどのように埋めるか考えてみてください。
...
...
...
考えたでしょうか？
きっと、
「関数とリストを引数にとり、リストの各要素に関数を適用した結果をリストにする関数です」
のような答えになると思います。
この map 関数を Scala で書く場合にはおそらく以下のようなコードになります。
オブジェクト指向ガン無視なのは許して。
def map[A, B](f: A => B, l: List[A]): List[B] = {
l match {
case Nil => Nil
case h::t => f(h)::map(f, t)
}
}
このコードを素直に日本語に直すと、先ほどの map 関数の説明よりもむしろ、
「関数とリストを引数にとり、リストが空だったら空リストを返し、そうでない場合は、リストの先頭要素に関数を適用した結果と、リストの残りの部分に map 関数を再帰的に適用した結果を cons したリストを返す関数」
のようになるでしょう。
つまり、この map 関数の定義は人間が map 関数に持っている気持ちとギャップがあるわけです。
Egison はパターンマッチの力でこのギャップを小さくできます。
例えば、map 関数の Egison による定義は以下のようになります。
(define $map // map という変数を定義
(lambda [$f $l] // map は f と l を引数とする関数
(match-all l (list something) // l をなんらかのリストとしてパターンマッチ
[<join _ <cons $x _>> (f x)]))) // 要素 x に f を適用
List が空かどうかという直感に反した場合分けをすることなく map を定義できています。
Egison のコードは Lisp っぽい構文でカッコが多いので、慣れないと読みづらいかもしれないですね。
変数を導入する際に $ マークがつくのも中々慣れないです。
そんな細かいことは今は気にしないようにしましょう。
どちらかと言うと、3 行目の (list something) が重要です。
Egison ではデータをどのようにパターンマッチするかをマッチャーと言い、任意に指定することができます。
今回はなんらかのリストとしてパターンマッチするという事だったので、 (list something) としています。
文字列のリストとしてパターンマッチするときは (list string) 、なんらかの集合としてパターンマッチするときは (set something) のようにマッチャーを使い分けることができます。
adjacentMap の例
map 関数の例では納得できない人向けの例も Egison Journal に載っていたので紹介します。
リストの隣接する 2 要素を二引数関数に渡していって、結果をリストで返す adjacentMap 関数です。
Scala では以下のような定義になるでしょうか。
def adjacentMap[A, B](f: (A, A) => B, l: List[A]): List[B] = {
l match {
case Nil => Nil
case _::Nil => Nil
case x::y::t => f(x, y)::adjacentMap(f, y::t)
}
}
場合分けが増えてしまいますね。
一方、 Egison では以下のように map 関数とよく似たコードで定義できます。
(define $adjacentMap
(lambda [$f $l]
(match-all l (list something)
[<join _ <cons $x <cons $y _>>> (f x y)])))
これを使ってみると、
> (adjacentMap * {1 2 3 4 5})
{2 6 12 20}
のようになります。
map 関数の亜種も map 関数と同様に気持ちに近い定義ができた気がします。
もうちょっと複雑な例
ポーカーの役判定は丁度いい複雑さだと思います。
コードは三つの部分で構成されています。
一つ目がマッチャーの定義です。
トランプのカードに当たるデータをどのようにしてパターンマッチするのかを定義しています。
二つ目がポーカーの役判定をする関数 poker-hands の定義です。
この関数は一つの大きなマッチ式で定義されています。
ポーカーの役が全て簡潔なパターンで記述される部分が面白いところです。
例えば、フルハウスという 5 枚の手札のうち 3 枚が同じ数字で、残り 2 枚もまた数字が揃っているような役は
[<cons <card _ $m>
<cons <card _ ,m>
<cons <card _ ,m>
<cons <card _ $n>
<cons <card _ ,n>
<nil>>>>>>
<Full-House>]
のように記述されています。
「手札のうち 3 枚の数字が m で残り 2 枚の数字が n ならフルハウス」という素直な書き方になっていると思います。
Egison の応用先
Egison Journal では以下のような応用が紹介されています。
- 置換群の計算
- と、それを利用した数学パズル「100人の囚人問題」の解法
- グラフの5-彩色
- 項書き換え系の完備化
- SMT ソルバーの実装
次の発表がシェル芸についてですが、 Egison がシェル芸と相性がいいという話もあります。
また、Egison のパターンマッチを別の言語で実現しようとする試みもいくつかあるようです。
普及していったら普段あなたの使っている言語でも Egison 由来のパターンマッチが使えるようになるかも......?
もっと Egison について知るには
公式サイトのリファレンスを読めばだいたいの Egison の仕様が分かります。
また、実際に Egison でプログラミングする際にはチートシートが便利です。
Egison の話をもっと知りたいという場合には、 Egison Journal があります。
Vol. 2 であればお貸しできます。
Vol. 1 は実は持っていないので購入してください。
開発者である江木さんの話を聞きたい場合は、 Egison Workshop 2019 が来週 11/24 (日)に本郷で開かれます。
昨年の workshop に参加しましたが、最新の Egison の開発話や初心者向けの親切だけどパズル要素があって飽きないハンズオンがあって楽しかったです。