A正規化されたIRをCPSに変換する
A正規化について非常に参考にさせてもらっているMatt Mightのブログ記事で
A later transformation to continuation-passing style (like that in Appel's book) is also simplified if transforming from A-Normal Form.
とあるので、これまでのA正規化されたIRに関してCPS変換がどのようになるのかを試してみた。
ちなみに（A正規形からではない）CPS変換についてもMatt Mightの記事を非常に参考にしている：
CPS形
<vexp> ::= <int> | <bool> | <var> | (Fn <var>* <cexp>) <aexp> ::= <vexp> | (Add <vexp> <vexp>) | (Lt <vexp> <vexp>) <cexp> ::= <aexp> | (Call <aexp> <aexp>*) | (If <aexp> <cexp> <cexp>)
Fnの中の式が
一つ重要なポイントとしてはLet式がなくなっていること。CPS変換の過程でLetは継続関数の呼び出しに変換されるのでCallとFnだけでLetが表現される。
また、継続自体も独自の式を持つのではなく、単に関数として表される。（このやり方に関してはいろいろ議論のあるところだが、今回は一番簡単なアプローチでやってみた）
let rec is_value = function | Int _ | Bool _ | Var _ -> true | Fn(_,e) -> is_cps e | _ -> false and is_atomic = function | Add(e1,e2) | Lt(e1,e2) -> is_value e1 && is_value e2 | e -> is_value e and is_cps = function | Call(f,es) -> List.fold_left (fun a b -> a && is_atomic b) (is_atomic f) es | If(e1,e2,e3) -> is_atomic e1 && is_cps e2 && is_cps e3 | e -> is_atomic e
実はこの記事を書くにあたって（コードを書いた後で）BNFで文法をちゃんと定義してみたら、OCamlのコードがバグっていることを発見した。さらにBNFに従って書くことでアドホック性が減ってかなりスッキリした。というわけで文法を定義するのは大事だと再認識。
CPS変換
それではCPS変換を行うコードを見ていく。
まずは新しい変数を作成するヘルパ関数：
let n = ref (-1) let gensym s = incr n; "k" ^ s ^ string_of_int !n
今回は「継続そのもの」と「継続に渡す値」の二つの異なる概念を表す変数を作成する必要があり、変換後のコードの理解しやすさのためにそれらを変数名で区別できるようにしたい。そのためgensymに文字列引数を渡せるようにした。
それでは変換の根本である二つの相互再帰的な関数を見ていく。
まずはアトミックな値を変換するためのtransform_m：
let rec transform_m = function | Fn(ss,e) -> let k = gensym "" in Fn(ss@[k],(transform_t e (Var k))) | e -> e
アトミックな式に関しては、関数式だけ「中身の式」にさらにCPS変換を加える必要があり、それ以外は変化なし。すでにA正規化されているためAddやLtの中の式を変換する必要はない（実はこれらの中にFn式が入っている場合は本当は変換が必要だが、それはそもそも型エラーなので今回の実装では無視）
そして一般的な式とその継続を受け取り、CPS形の式を返すtransform_t関数。ケースごとに見ていく：
and transform_t e k = match e with
まずアトミックな式：
| Fn _ | Var _ | Int _ | Bool _ | Add _ | Lt _ -> Call(k,[transform_m e])
これらはtransform_mした上で継続kの実引数として関数適用している。
関数適用：
| Call(f,es) -> let f = transform_m f in let es = List.map transform_m es in Call(f,es@[k])
関数・引数すベてにtransform_mし、引数の最後に継続を追加した形の関数適用式に修正している。A正規化されているおかげで関数・引数がすでにアトミックな式であることが保証されているので変換が楽になっている。
Let式：
| Let(s,e1,e2) -> transform_t e1 (Fn([s], transform_t e2 k))
Letはすでにかなり継続っぽい。本体の式を継続とみなして、変数束縛する対象の式を再帰的にtransform_tする。
最後にIf式：
| If(e1,e2,e3) -> If(e1, transform_t e2 k, transform_t e3 k)
すでにA正規化されているので条件式e1の部分は変更の必要がない。分岐先の二つの式をどちらも継続kとともにtransform_tしておく。
最後にプログラム全体の式をtransform_tと終端継続で変換するf関数：
let f e = transform_t e (let kv = gensym "v" in Fn([kv],Var(kv)))
やってみると実際A正規化してあることの恩恵は大きいように感じる。現在すべてが同じAst.t型の中での変換なので、変換の正しさの型システムによる保証がまったくないのが怖い点だが・・・
使ってみる
こんな感じのmain.mlモジュールを定義して使ってみる：
let f s = Lexing.from_string s |> Parser.f Lexer.f |> Alpha.f |> Anormal.f let () = let e = read_line () |> f in e |> Ast.to_string |> print_endline; e |> Anftocps.f |> Ast.to_string |> print_endline; e |> Anftocps.f |> Anftocps.is_cps |> string_of_bool |> print_endline;
まずはA正規形を出力、その後CPS形を出力し、ちゃんとCPS形の定義に沿っているかをチェックしている。
試しに以下の式を入力：
((if (< (+ 1 2) 3) (fn [x] (+ x 1)) (fn [x] (+ x 2))) (+ 1 2))
A正規形：
(let [g0 (+ 1 2)] (let [g1 (< g0 3)] (let [g2 (if g1 (fn [x.1] (+ x.1 1)) (fn [x.0] (+ x.0 2)))] (let [g3 (+ 1 2)] (g2 g3)))))
CPS形：
((fn [g0] ((fn [g1] (if g1 ((fn [g2] ((fn [g3] (g2 g3 (fn [kv0] kv0))) (+ 1 2))) (fn [x.1 k2] (k2 (+ x.1 1)))) ((fn [g2] ((fn [g3] (g2 g3 (fn [kv0] kv0))) (+ 1 2))) (fn [x.0 k1] (k1 (+ x.0 2)))))) (< g0 3))) (+ 1 2))
とりあえずうまくいっているようだ。目で追うのは大変だが・・・
