ミニマルなA正規化コードサンプル解説
言語処理系の実装の手法として「A正規化」というものがある。
元のソースプログラムを変換して最適化や機械語へのコンパイルなどがやりやすい形にする、処理系IRの選択肢一つである。CPS（継続渡しスタイル）のIRと非常に似ている。
The Essence of Compiling with Continuationsという論文で提唱されたIRで、CPSよりソースプログラムに対する変更が軽い割りに最適化などに関しては概ねCPSと同等のことができる、というのが論文著者たち（Felleisen含む）の主張。
その後Compiling with Continuations, ContinuedやCompiling without Continuations, Compiling with Continuations or without? Whateverなどこの話題でいろいろと仁義なき戦いが繰り広げられる。
個人的に一番わかりやすいA正規化の解説はMatt Mightの以下のブログ記事だった：
今回もこれをタネというか簡略化した上でほぼなぞる形で、非常に簡単な非チューリング完全言語のA正規化をやっていく。
ミニ言語
まずは対象言語の紹介から。
整数、和、そしてlet束縛とそれによって導入される変数、といった４つのASTノードを持つ非常に簡単な言語だ。
type t = | Int of int | Add of t * t | Var of string | Let of string * t * t
例によって構文解析をサボってS式を採用している。
なのでソースコードはこんな感じ：
(+ (let [x 5] (+ (+ x 3) x)) (+ (+ 3 4) (let [y 3] y)))
A正規化
A正規化とはネストしたASTをlet束縛を使ってより直線的に表現する変換である。
例えばこのような式を：
(+ (+ 1 2) (+ 3 4))
このような（let以外は）ネストしていないASTに変換する：
(let [x (+ 1 2)] (let [y (+ 3 4)] (+ x y)))
新しいASTの型を定義することもできるが、今回は同一のAST型内での変換として実装している。
実装としてはAnormal.mlなどといったモジュールにnormalize関数を定義する：
let rec normalize m k = match m with | A.Let(v,e1,e2) -> normalize e1 (fun x -> A.Let(v,x, normalize e2 k)) | A.Add(e1,e2) -> normalize_name e1 (fun x -> normalize_name e2 (fun y -> k (A.Add(x,y)))) | _ -> k m
A.xのようになっているのはAstモジュールの略で、この関数定義の前にmodule A = AstのようにAliasを定義してある。
ここでいうkは（CPS変換などでもお馴染みな）継続に関連している（ただし継続そのものではない）。ある式の継続、つまり周りすべてのコンテキストのA正規化したものを作る関数がkである。
IntやVarはそのままだがLetやAddに関しては再帰的にnormalize、あるいは相互再帰的にnormalize_nameを呼び出している。
normalize_name：
and normalize_name m k = normalize m (fun n -> if is_value(n) then k n else let g = gensym () in A.Let(g,n,k (A.Var g)))
相互再帰的にnormalizeを呼び出した後、その結果がアトミックな値（IntやVar）ならそのまま、アトミックでないなら新しい変数を作ってその変数に結果を束縛するLetを作る、という流れになる。
アトミックな値かどうかを調べるis_valueの定義：
let is_value = function | A.Int _ | A.Var _ -> true | A.Add _ | A.Let _ -> false
新しい変数を作るgensym：
let n = ref (-1) let gensym () = incr n; "g" ^ string_of_int !n
最後にAnormal.fをAnormal.normalizeを使って定義：
let f m = normalize m (fun x -> x)
α変換
深く考えずに上記のA正規化をすると、ソースプログラムでは起きない変数のシャドーイングが起きる可能性がある。
例えば：
(let [x 5] (+ (let [x 3] x) x))
のようなコードをA正規化すると：
(let [x 5] (let [x 3] (+ x x)))
となってしまって結果が8ではなく6になってしまう。
それを避けるためには、変数をすべてユニークなものにするα変換をすればいい：
let rec g env e = match e with | A.Int _ -> e | A.Add(e1,e2) -> A.Add(g env e1, g env e2) | A.Var s -> A.Var(List.assoc s env) | A.Let(s,e1,e2) -> let s' = genid s in A.Let(s', g env e1, g ((s,s')::env) e2) let f = g []
行っているのは：
- Letに遭遇するとその変数に対して新しくユニークな変数を割り当て、変数環境に元の変数と新しい変数のマッピングを追加
- Varに遭遇するとその変数に対応する新しい変数を環境から探してVarの中身を入れ替える
の二点。
変数割り当てのgenidは以下の通り：
let n = ref (-1) let genid s = incr n; s ^ "." ^ string_of_int !n
Anormal.gensymとは変数が被らないようになっているのがポイント（元のプログラムに出てくる変数はすべてxxx.nという形になる）
この実装はMinCamlを参考にしている。
使い方
最終的に入力をパーサに渡してα変換、A正規化そして文字列としての出力、という流れとなる：
let f s = Lexing.from_string s |> Parser.f Lexer.f |> Alpha.f |> Anormal.f |> Ast.to_string |> print_endline let () = read_line () |> f
使ってみると以下の通り：
(let [x 5] (+ (let [x 3] x) x)) (let [x.0 5] (let [x.1 3] (+ x.1 x.0)))
前述の変数がシャドーイングされそうな例でもα変換がうまくいっているのがわかる。
ネストの深いコードも：
(+ (let [x 5] (+ (+ x 3) x)) (+ (+ 3 4) (let [y 3] y))) (let [x.1 5] (let [g0 (+ x.1 3)] (let [g1 (+ g0 x.1)] (let [g2 (+ 3 4)] (let [y.0 3] (let [g3 (+ g2 y.0)] (+ g1 g3)))))))
直線的なものに正規化されている。
現在非常に簡単な言語ではあるがA正規化の大まかな流れはできたかと思う。ここにifを使った条件分岐と関数定義・適用を追加するとしっかりとした言語になってくる。（A正規化とifは少々難しい関係があるのでその点についても近いうちに書きたい）
今回のコード
今回のコードは以下のgistに全部載っている：
