Haskell ライブラリ MiniEgison の紹介
今年の11月に miniEgison というプログラミング言語 Egison のパターンマッチを提供する Haskell ライブラリを Hackage からリリースしました． このライブラリのソースコードはGitHubでも公開されています． この記事では，このライブラリの使い方を紹介します．
Egison のパターンマッチとは？
Egison のパターンマッチは，多重集合や論理式，数式にたいしてパターンマッチの方法を思い通りにモジュール化する機能がほしいという動機のもとに2010年3月頃に開発が始まりました． 多重集合や論理式に対してどのようなパターンマッチがしたいのか考えた結果，
- 正規表現のように非線形パターン（パターン変数に束縛した値を同じパターン内で参照するパターン）を効率的に処理できてかつ，
- ユーザーがいろいろなデータ型に対して自身でパターンマッチエンジンを定義できる
時は流れて，2018年末から，Egisonのパターンマッチを既存の関数型プログラミング言語の上に実装するメタプログラミングの手法の研究を開始しました． 研究は順調に進んで，2019年の間にSchemeとHaskellのライブラリを実装しリリースしました． 次節から．Haskellの上に実装したEgisonパターンマッチライブラリを紹介していきます．
MiniEgison クイックツアー
パターンマッチを記述するためのいくつかの構文を miniEgison は提供しています．
そのうちもっとも基本的な構文はmatchAll式です．
matchAll式は，ターゲット（上記の場合， [1,2,3] ），マッチャー（上記の場合， (List Something) ），マッチ節のリスト（上記の場合， [[mc| cons $x $xs => (x,xs) |] ）から構成されます．
マッチ節は，パターン（上記の場合， cons $x $xs ）とボディ（上記の場合， (x,xs) ）からなります．
matchAll式は，既存のプログラミング言語のマッチ式と同様に，ターゲットとパターンのパターンマッチを試みて，もしマッチしたらそのマッチ節のボディを評価します．
EgisonのmatchAll式の特徴は， (1) matchAllという名前と結果としてリストを返すことと， (2) マッチャーという追加の引数をとることにあります．
(1) の特徴は，複数の結果をもつパターンマッチをサポートするための特徴です．
matchAll式は複数のパターンマッチの結果すべてについてボディを評価して，その結果を集めてリストとして返します．
上記の例のパターンに使われている cons はコンスパターンと呼ばれるリストを先頭の要素と残りのリストに分解するパターンコンストラクタです．
そのため，上記の例の場合は，パターンマッチの結果が一つであるので，長さが 1 のリストを返しています．
(2) の特徴は，パターンマッチアルゴリズムの拡張性とパターンの多相性を実現するための特徴です．
マッチャーはEgison以外の言語ではみられない独自のオブジェクトで，パターンマッチアルゴリズムを保持するためのオブジェクトです．
matchAll式に渡すマッチャーを変えると他のmatchAllの引数がすべて同じでも結果が変わります．
例えば，上記のmatchAll式のマッチャーを Multiset Something に変えるとターゲットのリストを多重集合としてパターンマッチし，複数の分解結果を得られます．
マッチャーを変えるとこのmatchAll式の評価結果が変わる理由は， マッチャーを Multiset Something に変えた影響で cons パターンコンストラクタの解釈の方法が変わるからです．
上述したように，リストのマッチャーが使われているとき， cons はリストを先頭の要素と残りのリストに分解します．
対して，多重集合のマッチャーが使われているとき， cons はリストをある要素とその要素をのぞいた残りのリストに分解します．
その結果，要素数が 3 のリストがターゲットの場合， 3 つの分解結果が返ってきます．
Egisonは非線形パターンをサポートしています．
非線形パターンとは，パターン内で変数に束縛した値を同じパターン内で参照するようなパターンのことをいいます．
matchAll式がサポートする複数の結果を持つパターンマッチと，非線形パターンを組み合わせると，パターンマッチで簡潔に記述できるアルゴリズムの範囲が大きく広がります．
非線形パターンは，#からはじまる値パターンを使って表現します．
#のあとには，任意のHaskell式を書くことができます．
#のあとにつづく式を評価した結果と，ターゲットが等しいとき，値パターンはパターンマッチに成功します．
以下のmatchAll式は，ターゲットのリストから，連番の要素のペアを抽出します．
2つの連番となっている要素のペア（(1,2)と(4,5)）が返ってきています．
以下の式で使われているEqlマッチャーは，値の同値性のチェックが定義されているマッチャーです．
miniEgison内部のパターンマッチアルゴリズムではバックトラッキングが使われています．
以下のmatchAll式は，0だけを要素に持つ長さnのリストから連番となっている要素の2つ組と3つ組を取り出します．
バックトラッキングのおかげで，これら2つのmatchAll式の時間計算量は同じです．
このようなバックトラッキングを活かした効率の良い処理の実装のしやすさは，パターンガードにたいする非線形パターンの長所です．
（パターンガードの実装は，たいてい，パターンマッチの結果をすべて列挙したあと，パターンガードで指定された条件でフィルターします．
たいして，非線形パターンは，パターンマッチの途中で順次，条件を適用し，枝刈りしていきます．）
可算無限の結果をすべて列挙するように設計されていることも，miniEgisonのmatchAll式の特徴です．
そのために，matchAll式は，パターンマッチの探索木を幅優先探索します．
以下で使われているSetマッチャーについてcons，ターゲットのリストから要素を1つ取り出すのに使われています．
consパターンの第2引数にはターゲットのリストがそのままマッチします．
集合を，すべての要素を無限個含んだコレクションとして捉えるとこの解釈は自然と思えます．
一方，matchAllDFS式は，パターンマッチの探索木を深さ優先探索します．
matchAll式をmatchAllDFS式に変えると，下記のようにパターンマッチの結果の順序が変わります．
実用上，matchAllDFS式のほうが便利な場面も多いです．
既存の関数型プログラミング言語のパターンマッチのように，パターンマッチの結果の最初の1つについてボディを評価するmatch式もminiEgisonは提供しています．
match式は，matchAll式を使って簡単に定義されています．
パターンマッチ指向プログラミング
関数型プログラミングやオブジェクト指向プログラミングには，それぞれのプログラミングパラダイムの考えを反映した様々なプログラミングテクニックがあります． 同様に，Egisonのパターンマッチを活用したプログラミングテクニックも多数あり，これらのプログラミングテクニックには共通した考え方がみえます． このような考え方をまとめて，パターンマッチ指向プログラミングと呼んで，新しいプログラミング・パラダイムとして提唱しています．
パターンマッチ指向プログラミングの例を紹介します．
パターンマッチ指向プログラミングによってプログラムの記述が直感的になっていることのわかりやすい例にintersect関数の実装があります． intersectは2つのリストを引数にとり，それらのリストに共通する要素のリストを返す関数です． Egisonを使って引数のリストをそれぞれ多重集合としてパターンマッチすると，2つのリストの共通要素にマッチするパターンを記述することにより，intersectを記述できます．（プログラムの読み方はまた別の記事で紹介します．） 対して，Egisonのパターンマッチを使わずに関数型プログラミングのスタイルで記述すると，リストに対する関数を組み合わせて共通要素を抜き出すための方法を記述する必要があります． このプログラムは，リスト内包表記を使って以下のように書き直すこともできます．
Egisonのパターンマッチを使ったプログラムは，2つのリストの共通要素にマッチするパターンを記述しているだけであるのに対し，関数型プログラミングでは，どうやってその共通要素を取り出すかその方法をプログラマが考えて記述しています． 前者のように「何を計算したいか（what to do）」を記述するプログラミングスタイルは宣言型プログラミング，後者のように「どうのように計算するか（how to do）」を記述するプログラミングスタイルは手続き型プログラミングと呼ばれています． 「何を計算したいか」から「どのように計算するか」が明らかである場合は，「何を計算したいか」を記述する宣言型プログラミングのほうがプログラムが読みやすく簡潔になります． intersectの例の場合は，Egisonが多重集合のパターンマッチアルゴリズムをモジュール化できるおかげで，宣言的なプログラミングが可能になっています．
少し毛色の違う例として，concat関数をパターンマッチ指向プログラミングで定義します． リストのリストの要素にマッチするパターンを記述することにより，concatを定義できます．
さらにおもしろいパターンマッチ指向プログラミングの例として，unique関数を定義します． 後方に自身と同じ値が含まれない要素にマッチするパターンを記述することによりuniqueを定義できます．
パターンマッチ指向プログラミングについての論文
ちょうど先週，新しいプログラミング・パラダイムとして，パターンマッチ指向プログラミングを提唱する論文が， <programming> 2020 に採択されました！ この論文では，Egison本体のより進んだ機能の紹介や，それらの機能を使ったよりおもしろいプログラミング・テクニックが紹介されています． ぜひご覧になってみてください！