A-normal form 再学習 その2 - Scheme VM
ここに書いてある内容は古いです。A正規形まとめをご参照ください。
Figure 8 の (ar x, M, E, K) が分からなかったので見直したら CPS Compilers に説明があった。周辺を読んでみる。
大雑把に意訳すると
抽象 CPS コンパイラは continuation を普通の closure として扱うが、実践的なコンパイラでは、continuation と closure を区別することが多い。データフローの解析効率を向上させたり、メモリ割り当て戦略を区別したりするためである。
このような現実の closure と continuation の違いを扱うために、continuation には "ar" というタグでマーキングする。これは "active record" の略である。
となる。
分かったぞつまり、
さて Figure 8 を自然言語で説明していこう。
Value の参照
Value とは定数、変数、手続きのいずれか。
<V, E, K> -> <M' ,E'[x := γ(V, E)], K'> where K=<ar x, M', E', K'>
V を参照するときは、V の値をγにより取り出し x に束縛する。この状態で参照に引き続く継続に x の値が渡る。
要は V の値を次の継続用の E に束縛して、継続するということ。
if0
<if0 V M1 M2), E, K> -> <M1, E, K> where γ(V, E) = 0 <M2, E, K> where γ(V, E) != 0
V の値を取り出し、それが 0 であるかどうかで M1, M2 のいずれかを評価する。
これはより一般的な if に拡張しても問題ないと思う。
注意点としては、条件部が V なこと。これは (if0 (let ...) M1 M2) という形が許されないことを意味する。
手続き呼び出し
<(V V1 ... Vn), E, K> -> <M', E'[x1 := V1*, ... , xn := Vn*], K> where γ(V, E) = <cl x1 ... xn, M', E'> and for 1 <= i <= n, Vi* = γ(Vi, E)
一見挫折しそうな見ためですがもう分かるよ。
引数 V1 ... Vn の値をγ(Vi, E) で取り出し、E' に束縛してやり、M' を評価します。
ここで E' と M' とは closure オブジェクトの environment と body である。
ここでも注意すべきは、どの場所にも Value のみが許されるということ (a (let ...) 3) はダメ。
演算子
<(O V1 ... Vn), E, K> -> <M', E'[x := δ(O, V1*, ..., Vn*)], K'> if δ(O, V1*, ..., Vn*) is defined, where K = <ar x, M', E', K'> and for 1 <= i<= n, Vi* = γ(Vi, E)
演算子を抽象化したδに引数の値を渡して、次の継続の environment E' に束縛して継続する。
同じく引数には Value のみ。
let その1
let にはいくつか形式があるがまずは単純な場合から。
<(let (x V) M), E, K> -> <M, E[x := γ(V, E)], K>
これは簡単。 V の値を取り出して、x に束縛し、M の評価をするだけ。
let その2
手続き呼び出しが束縛される場合。
<(let (x (V V1 ... Vn)) M), E, K> -> <M', E'[x1 := V1*, ... xn := Vn*], <ar x, M, E, K>> where γ(V, E) = <cl x1 ... xn, M', E'> and for 1 <= i <= n, Vi* = γ(Vi, E)
手続き呼び出しは (V V1 ... Vn) は、クロージャ
let その3
演算子適用が束縛される場合。
<(let (x (O V1 ... Vn)) M), E, K> -> <M, E[x := δ(O, V1*, ..., Vn*)], K> if δ(O, V1*, ..., Vn*) is defined, and for 1 <= i<= n, Vi* = γ(Vi, E)
演算子適用結果を x に束縛し M を評価する。
さて
次は
- この変換ルールと自分の実装が等しいか
- このルールには定義されてない Scheme のプリミティブはどうするか考察する
あたりかな。