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" の略である。

となる。


分かったぞつまり、 は クロージャ の特殊な場合で1引数の継続なのだ。やっと理解できた。
さて 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) は、クロージャ へと評価される。その評価結果を x に束縛して M の評価へと継続する。

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 のプリミティブはどうするか考察する

あたりかな。