だめぽ

資料

Augustsson, L. (1985). Compiling pattern matching. In: Jouannaud, JP. (eds) Functional Programming Languages and Computer Architecture. FPCA 1985. Lecture Notes in Computer Science, vol 201. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15975-4_48
Simon L. Peyton Jones, The Implementation of Functional Programming Languages, Prentice Hall, 1987
- 第5章がPhilip WadlerによるEfficient Compilation of Pattern-Matching
- バックトラック法っぽい
Fabrice Le Fessant and Luc Maranget. 2001. Optimizing pattern matching. In Proceedings of the sixth ACM SIGPLAN international conference on Functional programming (ICFP '01). Association for Computing Machinery, New York, NY, USA, 26–37. https://doi.org/10.1145/507635.507641
- バックトラック法の改善、or-patternを実装している
MARANGET, L. (2007). Warnings for pattern matching. Journal of Functional Programming, 17(3), 387-421. doi:10.1017/S0956796807006223
Luc Maranget, Compiling Pattern Matching to good Decision Trees, ML'08
κeen, コンパイル技法: パターンマッチ
John Reppy and Mona Zahir, Compiling Successor ML Pattern Guards, ML Family Workshop 2019

だめぽ

Standard ML/Successor MLの場合

パターンの構成要素

ワイルドカード、変数
レコード
- 他の言語ではコンストラクターが複数の値をもてたりするけど、Standard MLでは複数の値を持てるのはレコードだけ
- (pat1, pat2) みたいに書いた時、 pat2 中のnested matchでは pat1 で束縛した変数が見える
  - ただし、 { ... = pat1, a = pat2 } は { a = pat2, ... = pat1 } の構文糖衣なので、 pat2 から pat1 は見えない。実行順も pat2 が先。
コンストラクター
- 定数（整数、文字、文字列）
  - Int8.int や Word8.word や char はソースコード中に全パターン列挙される可能性があるが、それ以外はコンストラクターが無限と扱って良さそう
- ref
  - 参照セルからの読み出しがあるので、nested matchの副作用と干渉しうる
- true, false
- ::, nil
- ユーザー定義のデータ型
  - コンストラクターの数は有限で、コンパイル時に判明している
- 例外 exn
  - コンストラクターは無限にある（実行時にも増える可能性がある）
conjunction: pat1 as pat2
- ~~決してマッチしないパターンを書ける：true as false~~ →4.11.5で決してマッチしないパターンは禁止されている（ので、処理系はこういうのを検出してエラーを出す必要がある）
- pat2 からは pat1 で束縛した変数が見える（nested matchで有用）
- nested matchを使うと x as pat1 with pat2 = x みたいに書けそう
disjunction: pat1 | pat2
- pat2 が冗長な場合は警告が出されるべき（4.11.3）だが、pat1 が冗長な場合の警告は要求されていない
nested match: pat1 with pat2 = exp
- 副作用が起こりうるので要注意
（拡張）vector #[pat1, pat2, ...]
- レコードとコンストラクターの組み合わせに近そう

矛盾するデータ型と、網羅性、冗長性

signatureを使うと矛盾するデータ型の仕様を書けて、functorを使うと矛盾するデータ型に対するパターンマッチみたいなことをできる。そういうコードは決して呼ばれることはないのだが、網羅性や（非）冗長性をどうするか。例：

signature S = sig
    datatype t = T
    datatype u = U
    sharing type t = u
    val x : t
end
functor F (S : S) = struct
val y = case S.x of
            S.T => "T"
          | S.U => "U" (* これは冗長判定されるのかどうか *)
end;

参照セルの読み出しと副作用

nested matchがあるとパターンマッチの途中でマッチ対象の参照セルの値が変わる可能性が考えられる。

case ref 0 of
    ref 42 => 1
  | x with false = (x := 42; true) => 2
  | ref 42 => 3

の3番目の節の ref 42 は冗長ではなく、このパターンマッチは3を返す、的な。

この件は網羅性検査にも影響する可能性があり、

datatype t = A | B | C
case ref C of
    ref A => 1
  | ref B => 2
  | x with false = (x := A; true) => 3
  | ref C => 4

は Match 例外を投げる。

conjunctionとnested match

conjunction pat1 as pat2 は「pat1 と pat2 の共通部分を表すパターン」を計算して適宜部分式に名前をつければ良いように思えるが、nested matchがあるとそう単純にはいかない。例えば、

fun f x = case x of
              (_ :: a with [] = (print "A\n"; a)) as (_ :: _ :: _) => 1
            | _ => 2;
val _ = f [1];

のパターンを

fun f x = case x of
              (_ :: (a as (_ :: _)) with [] = (print "A\n"; a)) => 1
            | _ => 2;
val _ = f [1];

と書き換えると実行結果が変わる。

だめぽ

LunarMLに実装するにあたって

中間言語

中間言語にjoin pointとswitchを用意する。

switchの効率的な実現

JavaScriptバックエンドではswitchを使える。

Luaにはswitchはない。if文の羅列にする必要がある。

だめぽ

パターンの列に対して実装したい操作

網羅性検査
- 特に、「単一のパターンが網羅的かどうか」という判断を束縛時またはnested matchで利用する。disjunctive patternがあると一般のマッチの検査と同じことが必要になりそう。
- 網羅的でない場合は、マッチしない値の例を出力できると良い。
- 冗長的でないパターン列にワイルドカードパターンを追加して冗長性が生まれるなら、網羅的である（冗長性検査ができれば網羅性検査ができる）。
冗長性検査
- 真の部分パターン列が網羅的になった場合は冗長性がある（網羅性検査ができれば冗長性検査ができる）
- disjunctive patternの各部分についても冗長性を検査したい。
二つのパターンに対して共通のマッチする値があるかどうか
- conjunctive patternの検査に必要。

だめぽ

二つのパターンに対して共通のマッチする値があるかどうか

パターンの有限列に対して、それら全てにマッチする値があるかどうかを表す述語 $\mathrm{Compat}\colon \mathrm{Pattern}^*\to\mathrm{Bool}$ を考える。これは次の規則で計算できる：

\begin{aligned} \mathrm{Compat}\{\}&=\mathrm{True}, \\ \mathrm{Compat}\{\mathtt{\_},p_2,\ldots,p_n\}&=\mathrm{Compat}\{p_2,\ldots,p_n\}, & \text{(wildcard)} \\ \mathrm{Compat}\{r_1\&r_2,p_2,\ldots,p_n\}&=\mathrm{Compat}\{r_1,r_2,p_2,\ldots,p_n\}, & \text{(conjunction)} \\ \mathrm{Compat}\{(r_1|r_2),p_2,\ldots,p_n\}&=\mathrm{Compat}\{r_1,p_2,\ldots,p_n\}\lor \mathrm{Compat}\{r_2,p_2,\ldots,p_n\}, & \text{(disjunction)} \\ \mathrm{Compat}\{c_1(r_1^1,\ldots,r_a^1),\ldots,c_n(r_1^n,\cdots,r_a^n)\} &=\begin{cases} \mathrm{Compat}\{r_1^1,\ldots,r_1^n\}\land\cdots\land\mathrm{Compat}\{r_a^1,\ldots,r_a^n\} & (c_1=\cdots=c_n) \\ \mathrm{False} & \text{(otherwise)} \end{cases} \end{aligned}

$\mathrm{Compat}$ の計算のためには、nested matchは無視して良い。つまり、追加のパターンマッチは常に成功しうると考えて、 $\mathrm{Compat}\{r\mathbin{\mathtt{with}}?,p_2,\ldots,p_n\}=\mathrm{Compat}\{r,p_2,\ldots,p_n\}$ である。

（Compatはcompatibleの略。）

パターンの有限列に対して、それら全てにマッチする値をマッチさせるパターン（そういう値が存在しなければ $\bot$ ）を表す関数 $\mathrm{I}\colon\mathrm{Pattern}^*\to\mathrm{Pattern}\cup\{\bot\}$ は次の規則で計算できる：

\begin{aligned} \mathrm{I}\{\}&=\mathtt{\_}, \\ \mathrm{I}\{\mathtt{\_},p_2,\ldots,p_n\}&=\mathrm{I}\{p_2,\ldots,p_n\}, & \text{(wildcard)} \\ \mathrm{I}\{r_1\&r_2,p_2,\ldots,p_n\}&=\mathrm{I}\{r_1,r_2,p_2,\ldots,p_n\}, & \text{(conjunction)} \\ \mathrm{I}\{(r_1|r_2),p_2,\ldots,p_n\}&=(\mathrm{I}\{r_1,p_2,\ldots,p_n\}|\mathrm{I}\{r_2,p_2,\ldots,p_n\}), & \text{(disjunction)} \\ \mathrm{I}\{c_1(r_1^1,\ldots,r_a^1),\ldots,c_n(r_1^n,\cdots,r_a^n)\} &=\begin{cases} c_1(\mathrm{I}\{r_1^1,\ldots,r_1^n\},\ldots,\mathrm{I}\{r_a^1,\ldots,r_a^n\}) & (c_1=\cdots=c_n) \\ \bot & \text{(otherwise)} \end{cases} \end{aligned}

ただし $(\bot|p)=(p|\bot)=p$ , $c(\ldots,\bot,\ldots)=\bot$ と約束する。

nested matchは別途考える必要がある。

（関数の名前は、IntersectionのIを取った。）