2014-07-31 (Thu) [長年日記]
_ 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自身を参照できない。