---

このドキュメントの目的は、Egisonのパターンマッチのコンセプトをできる限り素早く読者に理解していただくことです。
括弧だらけの構文に慣れていない方々のために、Haskellの構文に似た擬似コードも併用して解説します。

---

イントロダクション

パターンマッチはプログラミングにおいて重要な機能です。
パターンマッチにより、データの分解やデータの中身による分岐処理は、簡潔なマッチ式を1つで表現できます。

しかし、従来のパターンマッチには、特定のデータ型のデータしか直接的な記述で操作できないという問題がありました。
例えば、既存の言語のパターンマッチは、リストに対するパターンマッチはある程度得意ですが、要素の順序構造を無視する集合や多重集合に対するパターンマッチは難しいです。
そのため、簡潔に記述することができない冗長なデータ操作がまだあります。

Egisonは、この問題を解決するために作られたプログラミング言語です。
Egisonは、パターンの表現力を強力にしてかつ、プログラマが集合や多重集合を含む一般的なデータ型それぞれに対しパターンマッチの方法を記述できるようにすることにより、アルゴリズムのより直接的な表現を実現しました。

以下の例は、与えられたコレクションの要素のうち、2回以上現れる要素を列挙するプログラムを記述したものです。
パターンマッチを用いなければ、2重ループを記述する必要があるところを、簡潔なパターンマッチ1つにより記述できます。

以下、簡単かつ具体的な例を交えながら、Egisonのパターンマッチの何が新しいのかを説明します。

パターンマッチのための構文

ではまず、match-all 式について説明します。
この式だけを用いれば、Egison のコンセプトを説明することができます。

(match-all {1 2 3} ; ターゲット (list integer) ; マッチャー [<cons $x $xs> [x xs]] ; マッチ節: [パターン ボディ] ) ;=>{[1 {2 3}]} ; 結果

Egisonのマッチ式の一番の特徴は、マッチャーなるものを引数に受け取ることです。
Egison 処理系は引数のターゲットとパターンに対して、マッチャーで指定された方法でパターンマッチを行います。

もし、Haskellに似た擬似コードで同じ意味のコードを書くと以下のようになります。

matchAll [1, 2, 3] as -- ターゲット ('as' はパターンマッチのための予約語) (List Integer) with -- マッチャー ('with' はパターンマッチのための予約語) x:xs -> (x, xs) -- マッチ節: パターン -> ボディ -- =>[(1,[2,3])] -- 結果

様々なデータに対するパターンマッチ

Egison ではそれぞれのデータ型に対してパターンマッチの方法を定義できます。
下記の例では、1つのコレクションに対して、リスト、多重集合、集合としてそれぞれパターンマッチを行っています。
パターンコンストラクタ cons はコレクションを1つの要素と残りのコレクションに分解します。
パターンコンストラクタ cons の意味はそれぞれのマッチャー毎に異なり、Egison ライブラリ内でそれぞれのマッチャー毎に定義されています。

(match-all {1 2 3} (list integer) [<cons $x $xs> [x xs]]) ;=>{[1 {2 3}]} (match-all {1 2 3} (multiset integer) [<cons $x $xs> [x xs]]) ;=>{[1 {2 3}] [2 {1 3}] [3 {1 2}]} ; 要素の並びの順番が無視される (match-all {1 2 3} (set integer) [<cons $x $xs> [x xs]]) ;=>{[1 {1 2 3}] [2 {1 2 3}] [3 {1 2 3}]} ; 要素の並びの順番と重複の両方が無視される matchAll [1, 2, 3] as (List Integer) with x:xs -> (x, xs) -- =>[(1,[2,3])] matchAll [1, 2, 3] as (Multiset Integer) with x:xs -> (x, xs) -- =>[(1,[2,3]),(2,[1,3]),(3,[1,2])] ; 要素の並びの順番が無視される matchAll [1, 2, 3] as (Set Integer) with x:xs -> (x, xs) -- =>[(1,[1,2,3]),(2,[1,2,3]),(3,[1,2,3])] ; 要素の並びの順番と重複の両方が無視される

上記のパターンマッチが複数の結果を持っていることに注意してください。
これは、多重集合や集合のような1つの定まった標準形を持たないデータに対するパターンマッチのためには必須の機能です。
なぜなら、これらのデータは複数の分解の方法があるからです。

パターンコンストラクタ cons をネストして使うことも可能で、下記の例では2つの要素をコレクションから取り出しています。

(match-all {1 2 3} (list integer) [<cons $x <cons $y _>> [x y]]) ;=>{[1 2]} (match-all {1 2 3} (multiset integer) [<cons $x <cons $y _>> [x y]]) ;=>{[1 2] [1 3] [2 1] [2 3] [3 1] [3 2]} (match-all {1 2 3} (set integer) [<cons $x <cons $y _>> [x y]]) ;=>{[1 1] [1 2] [2 1] [1 3] [2 2] [3 1] [2 3] [3 2] [3 3]} matchAll [1, 2, 3] as (List Integer) with x:y:_ -> (x, y) -- =>[(1,[2,3])] matchAll [1, 2, 3] as (Multiset Integer) with x:y:_ -> (x, y) -- =>[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)] matchAll [1, 2, 3] as (Set Integer) with x:y:_ -> (x, y) -- =>[(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(2,3),(3,2),(3,3)]

コレクションを2つのコレクションに分解するパターンコンストラクタ join も用意されています。
パターンコンストラクタ join の意味もそれぞれのマッチャー毎に Egison ライブラリ内で定義されています。

(match-all {1 2 3} (list integer) [<join $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{1} {2 3}] [{1 2} {3}] [{1 2 3} {}]} (match-all {1 2 3} (multiset integer) [<join $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{1} {2 3}] [{2} {1 3}] [{3} {1 2}] [{1 2} {3}] [{1 3} {2}] [{2 3} {1}] [{1 2 3} {}]} matchAll [1, 2, 3] as (List Integer) with xs ++ ys -> (xs, ys) -- =>[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])] matchAll [1, 2, 3] as (Multiset Integer) with xs ++ ys -> (xs, ys) -- =>[([],[1,2,3]),([1],[2,3]),([2],[1,3]),([3],[1,2]),([1,2],[3]),([1,3],[2]),([2,3],[1]),([1,2,3],[])]

上記の list、multiset、set といったマッチャーは全てユーザが自身で定義できます。
Egisonプログラマは、マッチャーを自身で定義することにより、自身が定義した新たなデータ型に対するパターンマッチの方法も定義できます。

非線形パターン

Egison では1つのパターン内で同じ変数が複数現れるパターンを記述することができます。
パターンの先頭に , が付くパターンはバリューパターンと呼ばれるパターンです。
多くの場合、バリューパターンについては同値性がチェックされることが多いです。
バリューパターンの扱いについては、それぞれのデータ型についてマッチャー毎に定義できます。

(match-all {1 2 3 3 2 4} (multiset integer) [<cons $x <cons ,x _>> x]) ;=>{2 3 3 2} matchAll [1, 2, 3, 3, 2, 4] as (Multiset Integer) with x:x:_ -> x -- =>[2,3,3,2]

Egison は純粋関数型プログラミング言語です。 Egison プログラマは無限リストを Haskell のように直接扱うことができます。
バリューパターンには任意の式を記述できることにも注意してください。

(take 10 (match-all primes (list integer) [<join _ <cons $p <cons ,(+ p 2) _>>> ; 双子素数にマッチするパターン [p (+ p 2)]])) ;=>{[3 5] [5 7] [11 13] [17 19] [29 31] [41 43] [59 61] [71 73] [101 103] [107 109]} take 10 (matchAll primes as (List Integer) with (_ ++ (p : p+2 : _))) -> (p, p+2)) -- =>[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61),(71,73),(101,103),(107,109)]

非線形パターンは、パターンの表現力を大きく高めます。
非線形パターンにより、深くネストしたループの中のネストした条件分岐を取り除くことができます。
ポーカーの役判定のデモもぜひ見てみてください。

Egison では、集合のリストや集合の集合などといったネストしたデータ型に対してのパターンマッチも可能です。
下記の例では2重にネストしたコレクションの中の共通要素を取り出しています。

(match-all {{1 2 3 4 5} {4 5 1} {6 1 7 4}} (list (multiset integer)) [<cons <cons $n _> <cons <cons ,n _> <cons <cons ,n _> <nil>>>> n]) ;=>{1 4} matchAll [[1, 2, 3, 4, 5], [4, 5, 1] [6, 1, 7, 4]] as List (Multiset Integer) with (n:_):(n:_):(n:_):[] -> n -- =>[1,4]

パターンの静的スコープ

パターンのみを引数に取りパターンを返す関数、パターン関数を用いて、有用なパターンをモジュール化し使いまわすことが可能です。
パターン関数は静的スコープを持つため、変数の衝突を気にすることなくパターンのモジュール化が可能です。

(define $twin (pattern-function [$pat1 $pat2] <cons (& $pat pat1) <cons ,pat pat2>>)) (take 1 (match-all {1 2 1 3 2} (multiset integer) [(twin $m (twin $n _)) [m n]])) ;=>{[1 2]}

この機能は非常に複雑なパターンでも簡潔に書けるようにします。
麻雀の上がり判定のデモをぜひ見てみてください。.

まとめ

以下の全ての機能を同時に実現することにより、強力で直感的なパターンマッチを実現しています。

パターンマッチの方法のモジュール化

データ型ごとにパターンマッチの方法を定義できます。
例えば、リスト、多重集合、集合それぞれに対してパターンマッチの方法をユーザが定義できます。

複数の結果を持つパターンマッチング

内部的にバックトラックを行うことにより、複数の結果を持つパターンマッチを行うことが可能です。

非線形パターン

1つのパターン内で同じ変数が複数現れるパターンを記述できます。

静的スコープを保ったパターンのモジュール化

パターンのみを引数に取りパターンを返す関数、パターン関数を用いて、有用なパターンをモジュール化できます。
パターン関数は静的スコープを持ち、変数の衝突を気にすることなくパターンのモジュール化が可能です。

関連記事

Egison のパターンマッチについてのドキュメントはたくさん書かれています。 以下の記事も読んでみてください。

• CodeIQ MAGAZINE 連載 : 新しいプログラミング言語を作る理由──パターンマッチ指向プログラミング言語Egison紹介(第1回)
• Egison ユーザマニュアル - Pattern Matching (英語)

また、内部の仕組みに興味をお持ちの方は、 Egison デベロッパーマニュアルの Pattern-Matching Mechanism (英語) の章をご参照ください。

次に見てほしいもの...

Egison パターンマッチ論文 (英語) » オンライン・デモンストレーション » トップに戻る