パターンマッチングの実装（決定木コンパイル）

なぜ「決定木」へコンパイルするのか

match 式をそのまま実装する素朴な方法は、節（arm）を上から順に1つずつ照合するバックトラッキング法です。書いた順に意味が定まるので正しさは保証されますが、ネストした深いパターンでは同じコンストラクタを何度も検査し直すことになります。たとえば最初の節で「タプルの第1要素が Some」を調べ、外れて次の節でも同じ第1要素をまた調べる——この重複が積み重なると、最悪では節数とパターン深さの積に比例する検査回数になります。

決定木（decision tree）へのコンパイルは、この重複を消す手法です。「ある位置の値はどのコンストラクタか」という検査(test)を内部ノード、「実行すべき節の本体」を**葉(leaf)**とする木を作り、各位置のコンストラクタを高々1回しか調べないようにします。これは AST/中間表現 の段階で match を分解し、最終的に分岐命令の列へ落とす——コンパイルとインタプリタ で言うコード生成の一部です。代数的データ型とパターンマッチ で見た直和型のタグ付き構造が、この機械的な変換を可能にしています。

パターン行列という土台

コンパイルの入力をパターン行列として形式化します。各行が1つの節に対応し、各列が現在検査中の値の位置（オカレンス）に対応します。最初は検査対象が1つなので1列です。

match (x, y) with        パターン行列 P （右端は節の本体）
| (None,    _   ) -> A      None    _    -> A
| (_,       None) -> B      _       None -> B
| (Some(a), Some(b)) -> C   Some(a) Some(b) -> C

コンパイラ compile(occurrences, P) は、行列 P と「いま各列が指す値の位置の並び」を受け取り、決定木を返す再帰関数です。基本ケースは2つ。行列が空（行が1つも無い）なら、どの節にも当たらない失敗(Fail)の葉を返します。これが残ると非網羅です。先頭行が全部ワイルドカード（_ だけ）なら、その行は必ずマッチするので、その節の本体をLeafとして返します。

それ以外では、ある1列を検査する列として選び、その列に現れるコンストラクタごとに木を枝分かれさせます。ここで2つの行列操作が中心になります。

特殊化とデフォルト：行列を削る2操作

検査列の値がコンストラクタ C（引数 a 個）だった、という枝を作るために特殊化(specialization) S(C, P) を行います。検査列の各行を次のように変換します。

S(C, P) の行ごとの規則（検査列＝先頭列とする）
  先頭が C(p1..pa) の行 : 先頭を p1..pa の a 列に展開して残す
  先頭が _        の行 : 先頭を _ を a 個並べた列に展開して残す（任意のCに当たるため）
  先頭が C 以外のコンストラクタの行 : 削除（この枝には到達しない）

つまり「検査列が C だった世界」だけを取り出し、C の引数を新たな列として展開します。C を1回調べれば、その引数の照合は別の列の問題に還元される——同じコンストラクタを二度調べないのはこの還元のおかげです。

検査列に現れたコンストラクタの集合が、その型の全コンストラクタを覆っていない場合（シグネチャが不完全な場合）は、それ以外を受けるためのデフォルト(default) D(P) も作ります。

D(P) の行ごとの規則
  先頭がコンストラクタの行 : 削除（既に各 C の枝で処理済み）
  先頭が _ の行          : 先頭列を落として残す

決定木のその検査ノードは、各コンストラクタ C について compile(..., S(C, P)) を子に持ち、シグネチャが不完全なら compile(..., D(P)) をデフォルト子に持ちます。シグネチャが完全（全コンストラクタが枝に現れる）ならデフォルトは不要です。先の (x, y) の例では、まず第1列を検査し、None の枝・Some の枝へ特殊化していくと、Some(a) Some(b) の照合は内側の列の検査へと自然に分解されます。

どの列を検査するか：木の質を決めるヒューリスティック

compile は「どの列を検査するか」を選べます。検査列が先頭列である必要はなく、この列選択(column selection) が決定木の大きさと速度を大きく左右します。最初に当たった列を常に選ぶと、決定木が指数的に膨らむパターンが存在することが知られています。最適な（ノード数最小の）決定木を作る問題は一般に NP 困難なので、実際のコンパイラはヒューリスティックを使います。

複数のヒューリスティックを組み合わせて評価する実装が多く、Maranget のアルゴリズムは「必要性」を軸に良質な木を実用的なコストで得ます。列選択を変えてもマッチの意味は変わりません（同じ値には同じ節が当たる）。変わるのは生成コードの大きさと検査回数だけです。ここが 制御フロー の最適化として効いてきます。

決定木か、バックトラッキング自動機か

決定木は同じ検査を二度しない代わりに、特殊化で行が複製されるためコード量(葉や検査の数)が増えうるという欠点があります。各位置を高々1回検査するので実行は速い一方、最悪ではコードが指数的に膨らみます。

対するバックトラッキング自動機(backtracking automaton) は、節を順に試す素朴法を有限オートマトンとして実装したものです。コードの増加は線形に抑えられますが、照合に失敗して後戻りするとき同じ値を再検査しうるため、実行時の検査回数は増えがちです。

            コードサイズ        実行時の検査回数
決定木        最悪は指数的       各位置 高々1回（速い）
自動機        線形（小さい）     後戻りで再検査あり（遅めになりうる）

OCaml のように決定木を採る処理系もあれば、コードサイズを優先して自動機を採る設計もあります。両者は同じ意味論の異なるトレードオフであり、どちらも正しい結果を返します。

網羅性検査・冗長性検査は同じ機構で動く

決定木コンパイルの嬉しさは、網羅性検査(exhaustiveness) と冗長性検査(redundancy / 到達可能性) が同じ行列操作で得られることです。鍵となるのは有用性(usefulness) という1つの述語です。パターン行列 P に対し追加パターン q が「有用」とは、P のどの行にも当たらず q には当たる値が少なくとも1つ存在することを言います。有用性は、まさに特殊化 S とデフォルト D を使った再帰で判定できます。

網羅性検査は「全列がワイルドカードの行 (_ , ... , _) が P に対して有用か」を問うだけです。有用なら——どの既存パターンにも当たらない値があるなら——非網羅で、その有用性の証拠となる値がそのまま反例になります。これは決定木で言えば、compile の過程で Fail の葉が残ることに対応します。

冗長性検査は逆向きです。i 番目の節のパターンが、先行する 1 から i-1 番目までの行列に対して有用でないとき、その節には決して値が到達せず冗長です。決定木では、その節の本体を指す葉がどこからも参照されないことに対応します。

ガードと数えきれない型の扱い

理論が保守的に振る舞う場面があります。第一にガード節（if cond 付きパターン）です。cond は任意の式で真偽が静的に決まらないため、コンパイラはガード付き節を「マッチするとは限らない」と見なします。決定木では、ガード検査ノードが「真なら本体、偽なら残りの節の照合へ合流する」フォールスルー辺を持つ形になり、ガード付き節は網羅性の根拠に数えられません。論理的に全域を覆っていてもワイルドカード節を別途要求されるのは、健全性（漏れを見逃さない）を守るための意図的な割り切りです。

第二に、整数や文字列のように値が事実上数えきれない型です。全値を列挙できないので、検査器はリテラルや範囲を有限個の区間として近似し、覆われていない区間が残るかで網羅性を見ます。コンストラクタ集合が有限な代数的データ型と違い、ここでは「残りの値が一般に無数に存在する」という前提で反例（覆われていない代表値）を構成します。

まとめ

パターンマッチは、節を順に試す素朴法ではなく、各位置のコンストラクタを高々1回だけ検査する決定木へコンパイルされます。構築の核は、検査列をコンストラクタごとに展開する特殊化 S(C, P) と、残りを受けるデフォルト D(P) の再帰でした。タグが小整数なら検査ノードは分岐表になり、枝数によらず定数時間で目的の節へ飛べます。どの列を検査するかは NP 困難な最適化の近似で、ヒューリスティックが木の大きさと速度を決めますが、マッチの意味は変えません。

そして網羅性と冗長性は、決定木構築と同じ有用性判定から、Fail の葉と到達不能な葉として一度に得られます。決定木コンパイルとは、効率的な分岐コードの生成と静的な安全性検査を、ひとつの行列操作の上で同時に達成する仕組みなのです。