8Sweet Egison - EgisonパターンマッチのHaskellライブラリ
Egisonパターンマッチの実装には，本書でここまで紹介してきたEgisonの言語実装のほかに，既存言語上のDomain Specific Language（DSL）として実装したライブラリ実装もある． 既存言語のライブラリ実装には，deep embedding（インタプリタを埋め込むによりDSLを実現する手法）による実装であるminiEgison系と，shallow embedding（コンパイラを埋め込むことによりDSLを実現する手法）による実装であるSweet Egison系の二種類がある． 本章は，これらの実装のなかでもっとも高速なSweet EgisonのHaskell実装の使い方を紹介する． Egisonと異なりHaskellは静的型システムをもつ． そのため，Sweet Egisonを使ったパターンマッチはコンパイル時に型検査がなされる．
8.1Sweet Egisonの使い方
Sweet EgisonはHackageを通してHaskellライブラリとして公開されている． 本節はSweet Egisonをすでにインストールしているものとして使い方を解説する．
Sweet EgisonにはEgisonと同様にmatchAll式がある． matchAllは引数として探索戦略とターゲットマッチャー，マッチ節のリストをとる． Sweet EgisonではmatchAllはHaskellの関数として実装されており，asやwithのようなキーワードは挟まない．
matchAll dfs [1, 2, 3] (List Something)
[[mc| $x : $xs -> (x, xs) |]]
-- [(1, [2, 3])]上記のmatchAll式は探索戦略として深さ優先探索dfsが指定されている． Sweet Egisonではユーザが新しい評価戦略を定義できる． これはEgisonにはないSweet Egisonの機能である． 探索戦略の定義の方法は8.6節で解説する． 上記のmatchAll式のマッチャーは(List Something)である． 8.5節で改めて解説するように，Sweet EgisonではマッチャーはHaskellのデータとして表現される． マッチ節はmcクアジ・クォーター（quasi-quoter）を使って表現される． クアジ・クォーターはTemplate Haskellが提供する機能のひとつで，[mc|と|]で囲まれた部分を文字列として受け取り，Haskellプログラムを返す関数を定義することで，ユーザはHaskellメタプログラミングすることができる． マッチ節がどのようなHaskellプログラムに展開されるのかは，8.2節で紹介する． コンス・パターンはHaskellと同様にコロンひとつで表現する．
ライブラリに最初から定義されている探索戦略には，深さ優先探索dfsと幅優先探索bfsがある． 深さ優先探索dfsは，無限にあるパターンマッチの結果をすべて列挙できないことがあるが，高速である．
take 10 (matchAll dfs [1..] (Set Something)
[[mc| $x : $y : _ -> (x, y) |]])
-- [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10)]幅優先探索bfsは，無限にあるパターンマッチの結果をすべて列挙できるが，深さ優先探索dfsにくらべて実行効率がよくない．
take 10 (matchAll bfs [1..] (Set Something)
[[mc| $x : $y : _ -> (x, y) |]])
-- [(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1)]matchAll式がマッチ節のリストを引数にとるのは，複数のマッチ節を扱うためである． Egisonと同様に“matchAll \(t\) \(m\) [\(c_1\),\(c_2\),\(...\)]”というプログラムは，“matchAll \(t\) \(m\) [\(c_1\)] ++ matchAll \(t\) \(m\) [\(c_2\)] ++ \(...\)”と同値である．
matchAll [1, 2, 3] (List Something)
[[mc| $x : $xs -> (x, xs) |]
,[mc| _ : $x : $xs -> (x, xs) |]]
-- [(1, [2, 3]), (2, [3])]Sweet Egisonでは，Egisonと同様に#を使って値パターンを表現する． 値パターンを使って非線形パターンを表現できる．
matchAll [1, 5, 2, 4] (Multiset Eql)
[[mc| $x : #(x + 1) : _ -> (x, x + 1) |]]
-- [(1, 2), (4, 5)]最初のパターンマッチの結果だけを返すmatchもSweet Egisonには実装されている． matchAllを使ってmatchは以下のように定義される．
match s tgt m cs = head (matchAll s tgt m cs)matchを使ってポーカーの役判定は図8.1のように記述できる． Sweet Egisonでは，ターゲットのデータ型とマッチャーの両方でデータコンストラクタを使うために，データコンストラクタの名前がかぶりやすい． そのため，マッチャーのほうにCardMのように末尾にマッチャーのMをつけて，名前の衝突を回避することがある．
data Suit = Spade | Heart | Club | Diamond deriving (Eq)
data Card = Card Suit Integer
poker :: [Card] -> String
poker cs =
matchDFS cs (Multiset CardM)
[[mc| [card $s $n, card #s #(n-1), card #s #(n-2), card #s #(n-3), card #s #(n-4)] -> "Straight flush" |],
[mc| [card _ $n, card _ #n, card _ #n, card _ #n, _] -> "Four of a kind" |],
[mc| [card _ $m, card _ #m, card _ #m, card _ $n, card _ #n] -> "Full house" |],
[mc| [card $s _, card #s _, card #s _, card #s _, card #s _] -> "Flush" |],
[mc| [card _ $n, card _ #(n-1), card _ #(n-2), card _ #(n-3), card _ #(n-4)] -> "Straight" |],
[mc| [card _ $n, card _ #n, card _ #n, _, _] -> "Three of a kind" |],
[mc| [card _ $m, card _ #m, card _ $n, card _ #n, _] -> "Two pair" |],
[mc| [card _ $n, card _ #n, _, _, _] -> "One pair" |],
[mc| _ -> "Nothing" |]]
8.2Sweet Egisonの仕組み
Sweet Egisonの実装のアイデアを説明するために，まず以下のmatchAll式がどのようなHaskellプログラムに変換されるのかみる． cons $x _は$x : _と同値のパターンである． Sweet Egisonでは中置演算子は組み込みで:と++のみが実装されている． 説明をわかりやすくするために，本節では前置記法でコンス・パターンを記述する．
matchAll dfs [1, 2, 3] (Multiset Something) [[mc| cons $x _ -> x |]]上記のプログラムは以下のようなリスト・モナドについてのdo式に展開される．
(\ (matcher, target) -> do
(x, _) <- cons matcher target
let (_, _) = consM matcher target
return x)
(Multiset Something, [1, 2, 3]) -- [1, 2, 3]展開後のプログラムにあらわれるconsとconsMはそれぞれネクスト・ターゲット，ネクスト・マッチャーを計算するための関数である． consとconsMはHaskellで定義された関数である． consとconsMは，マッチャーとターゲットを引数に取る． マッチャーを引数にとる理由はパターンの多相性を実現するためである．
cons (Multiset Something) [1, 2, 3] -- [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]
consM (Multiset Something) [1, 2, 3] -- (Something, Multiset Something)matchAll dfs [1, 2, 3] (Multiset Something) [[mc| cons $x (cons $y _) -> (x, y) |]]
-- [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3,2)](\ (matcher, target) -> do
(x, target') <- cons matcher target
let (_, matcher') = consM matcher target
(y, _) <- cons matcher' target'
let (_, _) = consM matcher' target'
return (x, y))
(Multiset Something, [1, 2, 3])値パターンを含むパターンの展開もみる．
matchAll dfs [1, 2, 3] (Multiset Eql)
[[mc| cons $x (cons #(x * 2) _) -> (x, y) |]]
-- [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3,2)]valuePatはHaskellで定義された関数であり，さきほど登場したcons関数と同様にHaskellで定義された関数である．
(\ (matcher, target) -> do
(x, target') <- cons matcher target
let (_, matcher') = consM matcher target
(target'', _) <- cons matcher' target'
let (matcher'', _) = consM matcher' target'
valuePat (x * 2) matcher'' target''
return (x, y))
(Multiset Something, [1, 2, 3])8.3Sweet Egisonの最適化
実際のSweet Egisonは8.2節で解説した展開よりも，最適化のために，もうすこし複雑な展開をする． 特にワイルドカード最適化のために特別な工夫がある． 本節ではこれらの工夫を紹介する．
8.3.1ワイルドカードのパターンマッチの最適化
6.6節で述べたワイルドカード最適化をSweet Egisonでもおこなうことができる． ワイルドカード最適化とは，ワイルドカードを含むパターンについて，ワイルドカードにマッチするターゲットの計算を省くことにより，パターンマッチの処理を高速化することであった． 本節は，6.6節と同様に，多重集合に対するコンス・パターンの第二引数がワイルドカードであった場合の最適化の例を使ってSweet Egisonでこの最適化を使う方法を説明する．
matchAll dfs [1, 2, 3] (Multiset Something) [[mc| $x : _ -> x |]]
-- [1, 2, 3]上記のmatchAll式はワイルドカード最適化のために以下のように展開される．
(\ (matcher, target) -> do
(x, _) <- cons (GP, WC) matcher target
let (_, _) = consM matcher target
return x)
(Multiset Something, [1, 2, 3])\(2\)行目のcons関数が第一引数にパターンに対するパターンを追加で引数にとっている． パターンに対するパターンは，ワイルドカードとそれ以外のパターンを区別する． 以下，PPはパターンに対するパターン（Patterns for Patterns），WCはワイルドカード（Wildcard），GPは一般のパターン（General Patterns）の略である．
data PP a = WC | GPcons関数は第一引数として追加でこのパターンに対するパターンを追加で引数にとる． 以下のようにconsパターンの第二引数がワイルドカードである場合は，その第二引数に対するネクスト・ターゲットとしてundefinedを返す．
cons (GP, WC) (Multiset Something) [1, 2, 3]
-- [(1, undefined), (2, undefined), (3, undefined)]consパターンの第二引数がワイルドカード以外である場合は，ネクスト・ターゲットとしてコレクションを計算して返す．
cons (GP, GP) (Multiset Something) [1, 2, 3]
-- [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]8.3.2パターン・フュージョン
6.5節で解説した最適化であるパターン・フュージョンは，パターンのパターンマッチがでいないSweet Egisonではユーザーが追加することができない． リストに対するパターンマッチで頻出するジョイン・コンス・パターンについてのみ組み込みでパターン・フュージョンが定義されている． Sweet Egisonはジョイン・コンス・パターン\(p_{1}\) ++ \(p_{2}\) : \(p_{3}\)をjoinCons \(p_{1}\) \(p_{2}\) \(p_{3}\)に変換する．
matchAll dfs [1, 2, 3] (List Something) [[mc| _ ++ $x : _ -> x |]]
-- [1, 2, 3]たとえば，上記のmatchAll式は以下のように展開される．
(\ (matcher, target) -> do
(_, x, _) <- joinCons (WC, GP, WC) matcher target
let (_, _, _) = joinConsM matcher target
(List Something, [1, 2, 3])8.4マッチャーとパターンの型
マッチャーの型はクラスメソッドのない型クラスを使って表現される．
class Matcher m tgtこの型クラスを使って，たとえばSomethingマッチャーは下記のように定義される． データSomethingをもつ型Somethingを定義し，型Somethingのデータは型aのマッチャーであるという関係をインスタンス宣言で表現している． 本来は，データSomethingにMatcher aのような型を直接つけることが理想であるが，これはHaskellの型システムの制約のためできない．
data Something = Something
instance Matcher Something aパターンは，8.3節で述べたように，パターンに対するパターンと，マッチャー，ターゲットを引数にとり，ネクスト・ターゲットを返す関数として定義される．
type Pattern ps im it ot = ps -> im -> it -> [ot]パターンの多相性を実現するためには，パターンを型クラスに属する関数として定義する． たとえば，コレクションに対するパターンは以下のような型クラスを使って定義される．
class CollectionPattern m t where
type ElemM m
type ElemT t
nil :: Pattern () m t ()
nilM :: m -> t -> ()
cons :: Pattern (PP (ElemT t), PP t) m t (ElemT t, t)
consM :: m -> t -> (ElemM m, m)
join :: Pattern (PP t, PP t) m t (t, t)
joinM :: m -> t -> (m, m)
joinCons :: Pattern (PP t, PP (ElemT t), PP t) m t (t, ElemT t, t)
joinConsM :: m -> t -> (m, ElemM m, m)8.5Sweet Egisonのマッチャー定義
多重集合のマッチャーは以下のように定義される．
newtype Multiset m = Multiset m
instance Matcher m t => Matcher (Multiset m) [t]
instance Matcher m t => CollectionPattern (Multiset m) [t] where
type ElemM (Multiset m) = m
type ElemT [t] = t
cons (_, WC) (Multiset _) xs = map (\x -> (x, undefined)) xs
cons _ (Multiset _) xs = matchAll dfs xs (List Something)
[[mc| $hs ++ $x : $ts -> (x, hs ++ ts) |]]
consM (Multiset m) _ = (m, Multiset m)8.6ユーザによる探索戦略の追加
バックトラッキングによる探索アルゴリズムを記述することに使えるモナドをバックトラッキング・モナドという． 代表的なバックトラッキング・モナドとしてリスト・モナドが知られている． リスト・モナドは以下のようにバックトラッキングを記述することに使える． リスト・モナドを使って\(1\)から\(3\)の整数のペアを列挙している．
do ns <- [1..3]
x <- ns
y <- ns
return (x, y)
-- [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]リスト・モナドは探索木を深さ優先探索の順番で探索する． そのため，探索木が無限に大きい場合，すべての結果を列挙できないことがある．
do ns <- [1..]
x <- ns
y <- ns
return (x, y)
-- [(1,1),(1,2),(1,3),(1,4),(1,5),...]ここで，深さ優先探索に対するリスト・モナドのように，深さ優先探索以外の探索戦略についても対応するモナドが存在するのかという疑問が生じる． Spiveyによって幅優先探索について，リストのリストをベースのデータ構造にするモナドが対応することが発見されている[4]． このモナドは\(n\)要素目のリストに，探索木の深さ\(n\)の場所にあるノードを保持する．
バックトラッキング・モナドは，fromListとtoListという関数をもつ． これらはモナドのベースとなるデータ構造とリストとの間の変換関数である． 深さ優先探索のモナドの場合は，ベースとなるデータ構造がリストであるため，どちらもid関数として実装できる． 幅優先探索のモナドの場合は，ベースとなるデータ構造がリストのリストであるため，toList関数がconcatになったりする． バックトラッキング・モナドの実装の詳細は，backtrackingという名前のHaskellライブラリとしてHackageで公開されているのでそちらを参照してほしい[5]．
バックトラッキング・モナドを使うと探索戦略を多相的に切り替えることができる． 以下dfsとbfsはそれぞれ深さ優先探索と幅優先探索のモナドのベースとなるデータ構造を初期化するための関数である． dfsとbfsを置き換えるだけで，探索戦略を制御できる．
toList (do
ns <- dfs [1..]
x <- fromList ns
y <- fromList ns
return (x, y))
-- [(1,1),(1,2),(1,3),(1,4),...]toList (do
ns <- bfs [1..]
x <- fromList ns
y <- fromList ns
return (x, y))
-- [(1,1),(1,2),(2,1),(1,3),...]matchAllの第一引数に渡されるのはこの探索戦略ごとのモナドを初期化するための関数である．
matchAll strategy [1..] (Set Something) [[mc| $x : $y : _ -> (x, y) |]]matchAllの変換結果に適切に，この初期化関数とfromListとtoListを挿入すれば，探索戦略を制御することができる．
toList
((\ (matcher, target) -> do
(x, target') <- fromList (cons matcher target)
let (_, matcher') = consM matcher target
(y, _) <- fromList (cons matcher' target')
let (_, _) = consM matcher' target'
return (x, y))
(strategy (Set Something, [1..])))深さ優先探索や幅優先探索のためのモナドはHaskellで定義されている． ユーザーが新しく別の探索戦略のためのモナドを追加することも可能である． この機能はEgison本体にはないSweet Egisonならではの機能である．