Scheme に対する A正規化 - Scheme VM を書く

このネタ3回目。今渡こそリベンジ。
Core Scheme ではなくて Scheme に対する A正規化を考える。前回のまとめを書いたことで新しい視点が加わり、以前の誤りも見えてきた。
結局 A正規化すると、ソースコードがプリミティブな形式になるわけだから、その形式で Scheme 全体が表現できなくてはいけない。
A正規化された Core Scheme に登場する式は以下の通り。

M  ::=   V                             (return)
    |    (let (x V) M)                 (bind)
    |    (if0 V M M)                   (branch)
    |    (V V1 ... Vn)                 (tail call)
    |    (let ((x (V V1 ... Vn))) M)   (call)
    |    (O V1 ... Vn)                 (prim-op)
    |    (let ((x (O V1 ... Vn))) M)   (prim-op)

足りないのは

set!
define
let/lambda のbodyで複数の式を許す

の3つかな。

こういうのを考えてみた。どうだろうか。

M  ::=   V                              (return)
    |    (let1 x V M*)                  (bind)
    |    (if V M M)                     (branch)
    |    (V V1 ... Vn)                  (tail call)
    |    (let1 x (V V1 ... Vn) M*)      (call)
    |    (O V1 ... Vn)                  (prim-op)
    |    (let1 x (O V1 ... Vn) M*)      (prim-op)
    |    (lambda (V1 ... Vn) M*)        (closure)
    |    (set! x V)                     (assign)
    |    (define x M)                   (define)

M* ::=   M1 ... Mn

define は V ではなくて M にした。Vにすると「defineがトップレベルではなくなる」「クロージャのdefine時にクロージャのサイズが分からなくなる」の2つのデメリットがあるから。

3日くらいずっと悩んでいたのは let1 の body が複数の式がある場合の実装。
式が外にくくり出されることを考えると、複数の式を k に渡すのか？とか無駄に悩みまくり。
でもよく考えれば末尾の値が式の返す値だから、外にくくり出されるのは、body の末尾だけで良い。

A正規形補足

僕がA正規形を理解するのを妨げていたものは何だったか？それは入力と出力が似たようなものである例を選んでいたことだと思う。論文の例もそうなのだけど Schemeの式 =>(A正規化)=> Schemeの式を無意識に想定しているのだよね。
でも論文を読んであとから冷静に考えれば、A正規化された式というのは return, bind, branch などプリミティブな式の集まりであれば良い。必ずしも Scheme である必要はない。中間形式なのだから直接実行できる形式である必要は全くない。

例えば (let (a 0) M) という式は A正規化すると [BIND [a 0] M] だと言ってしまっても全然良いわけ。
するとこの先がずっと見えやすくなる。きっと[BIND [a 0] M] は env を新たに作成して a => 0 というレコードを作るんだろうなとか想像しやすくなる。
クロージャ変換してしまえば、もうネイティブコードを出力できそう。

さらに

A正規形のまとめを書いたら、、id:scinfaxi さんや、id:hayamizさん、id:yharaさんが反応して下さいました。
またA正規化に関して iwkさんやid:sumiiさんに大変有用なアドバイスを頂きました。
苦しかったけど、本当に書いて良かったなとうれしくなりました。皆さんありがとうございます。

さらさらに

ふと冷静になると、A正規化の概要が分かった時点で MinCaml のK正規化のコードを~~パクる~~参考にすれば良かったのではなかろうかと思った。こういう所が自分は不器用だよなあ。