Egisonのmatcherの定義（基本編）
第1回 Egison Dev Meeting(http://egison.pira.jp/workshops/1-dev.html)に行ってきました。
Egison自体まだまだ色々と発展途上の言語なので、「この仕様はどうなのか」「ここはこの書き方でいいのか」「これからの展望は」などEgisonの今後に関する多くの意見があり、有意義なDev Meetingでした。
ただ、これは以前行われたEgisonのワークショップなんかでも思ったことですが、新しい概念を導入するときのコード例が複雑すぎる気がしました。そこで、その中でも特に重要かつ面白い"matcher"の定義方法についてチュートリアル的なものを書いてみます。この記事はその基本編で、matcherという概念自体の説明及び定義文のシンタックスに関する説明に重きを置いています。あとでもっとmatcherのすごさが伝わる応用編を書く予定です。予定です。
（注意：この記事はEgisonのよさを伝える記事というよりは、Egisonを実際に書く為の基本的ノウハウを共有するための記事であり、そのため極めて簡易的な機能の実装を目指しています。なので「それって別にパターンマッチングでやる必要なくね？」と思ったとしても気にせず読んでいただけたらと思います。）
（注意２：Egisonは現在進行形で開発されている言語なので、Syntaxやその他細かい仕様がいつまでもこの記事のままとは限りません。事実、この記事を書いている間にalgebraic-data-matcher構文のSyntaxが変わりました。*1）
なお、多少厳密さに欠けるところもあるため、詳細が知りたい人は公式マニュアル：How to Define Matchers（http://egison.pira.jp/manual3/how-to-define-matchers.html）を参照してください。
定義方法の前にそもそもmatcherとは、それ自体既存のパターンマッチングには登場しない概念なので、これについて整理します。
既存のパターンマッチは
match expr
pattern_1 -> expr_1
pattern_2 -> expr_2
...
pattern_n -> expr_n
のような構文によって、「exprを評価した値がpattern_iにマッチしたならば、そのマッチングによって得られた変数束縛によって拡張された環境のもとでexpr_iを評価する」というものでした。
これに対しEgisonの（matchによる）パターンマッチは
match expr matcher
pattern_1 -> expr_1
pattern_2 -> expr_2
...
pattern_n -> expr_n
のような構文を持ち、「exprを評価した値をmatcherとして見たとき、pattern_iにマッチしたならば、そのマッチングの結果の１つによって得られた変数束縛によって拡張された環境のもとでexpr_iを評価する」という意味を持ちます。
つまり、例えば既存のパターンマッチで「<cons 0 tail>」と書かれたパターンは、「先頭の要素が0のリストで、Tailを変数tailに束縛」のような意味でしかありえませんが、Egisonではmatcherの違いにより「先頭の要素が0のリストで、Tailを変数tailに束縛」「要素のうちの一つが0の多重集合で、0を取った残りの要素を変数tailに束縛」「要素のうちの一つが0の集合で、元の集合＝set∪{0}となるようなsetを変数tailに束縛」のように、「<cons ....>」が様々な意味を持ち得ます。さらには「0」でさえ、単なる「整数値0」という意味だけでなく、「3で割ったら0になる値」のようなマッチングも可能です。*2
つまるところmatcherとは、既存の言語では「値を評価してデータの構造レベルで比べる」というたった１つの方法しかなかった「パターンマッチングの方法」を独自に定義するものです。様々なmatcherを定義して使うことで、柔軟な方法によるパターンマッチングを実現することができます。
さて本題です。Egisonのパターンマッチの柔軟さを示す例として、まず紹介されるのがmultisetというmatcherで、これはコレクションを多重集合と見て（つまりリストと違い順序を無視して）パターンマッチすることができるというものです。matcherの使い方・定義方法の説明には今までこのmultisetが使われてきました。しかし、使用方法はともかく、multisetの定義はとっかかりとしては大きすぎ、実際ここですこし引いてしまうようなところがあります。
そこで、もっと小さく、しかし既存のパターンマッチングでは実現できなかった例として同じ型のペア（対）に対するmatcherを定義することを考えてみます。
別に特別高機能な言語でなくとも、ペアに相当するデータ構造を定義するのは容易です。OCamlやHaskellでは普通に2-タプルを使えばいいですし、例えばHaskellだったら
data Pair a = Pair a a
のようにデータ型としても定義できるわけです。OCamlならバリアントを使えばいいですね。
しかし、そのパターンマッチの仕方としては、Pairを順序対として見るような方法しかありません。つまり、Pair x 4のようなパターンでPair 3 4という値をマッチさせると、{x=3}という束縛が手に入ります。
しかし、ペアの値を考えるにあたって順序が重要でない、あるいは意図的に無視したい場合があります。そこでこれから、Egisonで順序対・非順序対のmatcher、つまり、
> (test (match <Pair 4 3> (unordered-pair integer) {[<pair $x ,4> <Just x>] [_ <Nothing>]}))
<Just 3>
> (test (match <Pair 4 3> (ordered-pair integer) {[<pair $x ,4> <Just x>] [_ <Nothing>]}))
<Nothing>
となる*3ようなmatcher ordered-pairとunordered-pairを定義してみましょう。
順序対のmatcherは簡単です。matcher式を使うまでもありません。
先に述べたように、順序対としてのマッチは既存の言語にもある「データ構造に基づくパターンマッチ」です。このようなmatcherを実現するために、これを簡単に定義する構文糖algebraic-data-matcherがあります。
(define $ordered-pair
(lambda [$a]
(algebraic-data-matcher
{<pair a a>})))
(algebraic-data-matcher {...})で...に指定したコンストラクタ・パターンに対応するmatcherが定義できます。つまりordered-pair integerを指定した<Pair 2 5>のパターンマッチの結果は
- _ → {[]}
- $x → {[x = <Pair 2 5>]}
- <Pair $x $y> → {[x = 2, y = 5]}
のようになります。
本題の非順序対のmatcherです。定義は以下のようになります。
((1)...(10)は単なる参照)
(define $unordered-pair
(lambda [$a]
(matcher(1)
{[,$val(2) [](3)
{[$tgt(4) (match [val tgt] [(ordered-pair a) (ordered-pair a)]
{[(| [<pair $a $b> <pair ,a ,b>]
[<pair $a $b> <pair ,b ,a>]) {[]}(5)]
[_ {}(6)]})]}]
[<pair $ $> [a a](7)
{[<Pair $x $y>(8) {[x y] [y x]}(9)]}]
[$ [something](10)
{[$tgt {tgt}]}]})))
一気に複雑になりましたね。各部分の意味を読解します。
- (matcher {[case 1] [case 2] ... [case n]})
matcher式は「（パターン・再帰的に呼ぶmatcher・マッチング処理）をひとまとめにした節」のコレクションをとり、これ（コレクションの一要素）をプリミティブパターン節(primitive pattern clause)と呼びます。ここでは「,$val」「<pair $ $>」「$」の3つのケースに対するマッチング処理が記述されています。 - ,$val
パターンマッチ・ケースの第1要素にはプリミティブパターンパターン(primitive pattern pattern)と呼ばれる、パターンにマッチさせるパターンが記述されます。「このパターンはどの規則によってパターンマッチさせるべきか」という分岐処理はまさに「パターンに対するパターンマッチ」で記述されるべきだからです。現時点ではパターンに対するパターンはごく基本的なものに限られており、「,$val」はその一つのバリューパターンパターン(value pattern pattern)と呼ばれるものです。これは「,(コンマ)＋値」の形式のパターンすなわちバリューパターン(value pattern)にマッチするものです。つまりこのケースには、値「<Pair 3 4>」をパターン「,<Pair 4 3>」にマッチさせるときの処理が記述されています。 - []
Egisonだけでなく従来のパターンマッチにおいても、あるパターンへのマッチング処理が再帰的に他のパターンマッチを呼ぶことは普通にあることで、例えば「Pair 3 4」の「Pair x y」へのパターンマッチングは厳密には「Pair 3 4がPair x 4にマッチ」→「3がxにマッチ＆4が4にマッチ」→「{x=3}、4が4にマッチ」→「{x=3}」と進んでいくわけです。ここでは変数へのマッチングを呼んでいることになります。
さて、Egisonでmatcherを定義する際にはこのマッチングに使用するmatcherを明示しなくてはなりません。ここではバリューパターンへのマッチングであり、他のマッチングを呼ぶことはないので（上でいう「4が4にマッチ」に対応）空のタプルを書きます。 - $tgt
マッチング処理をするには、とりあえず普通の（プリミティヴな）方法で値を束縛・分解しなければなりませんが、それをするための「最も原始的なパターン」がプリミティブデータパターン(primitive data pattern)です。マッチング処理はプリミティブデータパターンによる原始的なパターンマッチングのマッチ節: [<primitive data pattern> (マッチング結果)]のコレクションによって書かれ、これらのマッチ節をプリミティブデータ節(primitive data clause)と言います。ここには1つのマッチ節しかなく、単なる変数束縛(primitive data variable: $+識別子)を使って、データ自体を変数に束縛しています。 - {[]}
Egisonでは、マッチング結果として複数の値を許します。よってマッチング結果はコレクションを返す仕様になっています。マッチング結果は、再帰的に呼ぶmatcherが[matcher_1 matcher_2 ... matcher_n]ならば[(matcher_1にマッチさせる式) (matcher_2にマッチさせる式)... (matcher_nにマッチさせる式)]となります。ここでは再帰的にマッチさせるmatcherはありませんので、マッチングが成功した場合は[]を1つ返すことでマッチングの成功を表現することになります。ここでやっているのは、「,$valにマッチしたバリューパターンの表す値が<Pair a b>か<Pair b a>で、マッチさせる値（$tgtに束縛されている）が<Pair a b>であればマッチング成功、そうでなければ失敗」という処理を、先程定義したordered-pairによるマッチングを使って書いています。 - {}
パターンマッチの失敗は、空のコレクション{}を返すことで表現します。「パターンマッチに失敗した＝マッチングの結果が0個」ということです。 - <pair $ $> [a a]
このケースは、<pair $x _>のようなパターンに対する処理が記述されています。<pair ...>はプリミティブインダクティブパターン(primitive inductive pattern)、$はプリミティブパターン変数(primitive pattern variable)と呼ばれます。
$は再帰的なパターンマッチングを行う場所を示すもので、3.では１つもなかった「再帰的なマッチングに用いるmatcher」がここでは指定されています。pairの要素に対応するmatcherはラムダでaに束縛しているため、ここでは２つともaを指定しておけばいいというわけです。 - <Pair $x $y>
4.ではマッチさせる値を変数に束縛するだけでしたが、今回は値を分解しています。ここで用いている<Pair ...>はプリミティブインダクティブデータ(primitive inductive data)というプリミティブデータパターンで、コンストラクタの先頭は値と同じ大文字になります。 - {[x y] [y x]}
このケースでは、前とは違いマッチング結果を返すケースです。マッチング結果を返すと、指定したmatcherによるパターンマッチングが結果のすべてについて行われます。
ここでは非順序対のmatcherを書きたいので、値「<Pair x y>」に対するパターン「<pair pattern_1 pattern_2>」をマッチングする際、「xにpattern_1がマッチ＆yにpattern_2がマッチ」と「yにpattern_1がマッチ＆xにpattern_2がマッチ」が行われて欲しいので、[x y]と[y x]の２つを指定します。 - $ [something]
最後のケースは上のどれにもあてはまらないパターン、すなわち変数パターン$xであり、このときは単純にxにマッチングさせる値を束縛すればいいことになります。
さて、実はここまで変数に値をマッチングさせる方法を一切紹介していません。最初のケースは束縛の必要がなく、次のケースも再帰的に呼ぶmatcherに後の処理を任せてしまっています。変数に値を束縛するにはどうすればいいのでしょうか？
ここで登場するのが唯一の組み込みmatcherであるsomethingです。somethingは変数パターンしか取れないmatcherで、変数パターンに対するマッチは必ず成功し、その変数に値を束縛します。ライブラリcollection.egiなどを見てもらえばわかりますが、この書き方はmatcherの最後によく来るので、イディオムとして覚えておくのもよいでしょう。
以上がunordered-pairの定義の読み方で、matcher定義の基本的な部分です。
まとめると、matcherを定義するには「マッチさせるパターンをプリミティブパターンパターンによるパターンマッチングによって分類」し、「マッチする値をプリミティブデータパターンによるパターンマッチングによって分類」し、それら分岐の先で「マッチング結果を返す」式を書けばいいことになります。こう言ってしまえば単純なのですが、やはりSyntaxが込みいっていることもあって初見はとまどってしまいますね。
しかし、上の定義を追えたのならば、もう後はわからないことは紹介していないプリミティブ{パターン or データ}パターンぐらいなもんでしょうから、上で紹介した公式マニュアル片手にライブラリのmatcherのコードも読めると思います。
次に読むとしたら先に挙げた多重集合か、剰余環Z/nZの上の等号を使ってマッチできるmod nなんかが面白いと思います。mod nを使うと「3で割ったあまりが2な数にマッチ」とか面白いことができます。
本記事はEgisonの本格的な紹介記事ではないので紹介しませんでしたが、先に述べたようにEgisonでは複数のマッチング結果を返せるので、従来のパターンマッチではありえなかった（というより、従来のパターンマッチではマッチング結果が一個しかないから意味がなかった）「複数のマッチング結果すべてを取り出して処理を行う」match-all 構文があります。これと組みあわせることでEgisonのパターンマッチはその真価を発揮することとなります。
Egisonはパターンマッチ指向言語ですので、matcherを独自に定義できるようになれば一気にできることの幅が広がります。是非独自matcherで色々遊んでみましょう。
