Journal InTime

_ SECDマシンにおける再帰

先日のICFPCに会社のチームで参加して、コンパイラの実装を少しだけ手伝った。

後でわかったが、ICFPCの仮想マシンの仕様はLispKitをベースにしていて、SECDマシンという有名なものらしい。

SECDマシンはスタックマシンで、データスタック、制御スタック（関数呼び出しや条件分岐時に復帰するための情報が積まれる）、環境フレーム（変数が格納される）という三つのスタックを持っている（環境フレームは親フレームへのポインタを持っていて、単純にpopされる代りに参照されなくなったらGCされるので、厳密にはスタックではない）。

Stack/Environment/Control/Dumpという4つのレジスタを持つのがSECDマシンという名前の由来。

例えば、((lambda (x) (+ x x)) 21)のようなプログラムは以下のように表現される。

LDC  21       ; 定数21をスタックにpushする。
LDF  body     ; bodyを本体とするクロージャを生成してスタックにpushする。
AP   1        ; 新しい環境フレームを生成して、21に関数を適用する。
RTN           ; 呼び出し元に戻る。
body:
LD   0 0      ; 0番目の環境フレームの0番目の変数（x）の値をスタックにpushする。
LD   0 0      ; 0番目の環境フレームの0番目の変数（x）の値をスタックにpushする。
ADD           ; スタックから二つの値をpopし、加算した結果をスタックにpushする。
RTN           ; 呼び出し元に戻る。

APは新しい環境フレームを生成して関数を適用するが、APと似た命令に環境フレームを生成しないRAPというものがあり、空の環境フレームを生成するDUMという命令とセットで利用する。

例えば、(letrec ((loop (lambda () (loop)))) (loop))のような再帰的なプログラムは以下のように表現される。

DUM 1         ; 空の環境フレームを生成する。
LDF loop      ; loopを本体とするクロージャを生成してスタックにpushする。
LDF main      ; mainを本体とするクロージャを生成してスタックにpushする。
RAP 1         ; DUMで生成した環境フレームを使用してloopにmainを適用する。
RTN
main:
LD 0 0        ; 0番目の環境フレームの0番目の変数（loop）の値をスタックにpushする。
AP 0          ; 関数を適用する
RTN           ; 呼び出し元に戻る。
loop:
LD 1 0        ; 1番目の環境フレームの0番目の変数（loop）の値をスタックにpushする。
AP 0
RTN           ; 呼び出し元に戻る。

DUMで生成した環境フレームがLDF loopで生成されるクロージャによって捕捉されるところがポイントで、これによってloop内のLD 1 0（loopの適用で環境フレームが積まれるのでLDの第1オペランドは1とする）でloop自身を参照できる。

上記の例でDUM/RAPの代りにAPを使うと、letrecの代りにletを使った場合のように、loop内でloop自身を参照できない。