3impを3章まで読んだので備忘録です． 以前にschemeっぽいのを書いたのでもうちょっとマシなのを作りたいという ことです． 3impは，schemeの処理系をheapベース，stackベース，stringベースの三種類で 具体的に紹介してくれているありがたい論文です． 特に3章heapベースのVMの動きを書き残しておきます．
コンパイラ
schemeコード -> コンパイラ -> 中間コード -> VMで実行
という流れなので，まずschemeコードから中間コードへのコンパイラを作ります． 継続渡しとでもいうのかな． 基本的に前から後ろに命令が流れていきます． コンパイラの詳細は論文にあるので省略します．
;; schemeコード
(if #f 10 20)
↓
;; 中間コード
(constant #f (test (constant 10 (halt))
(constant 20 (halt))))
VMの仕様
レジスタと中間コードの仕様は以下の通りです． まず，VMには以下の5つのレジスタがあります．
- レジスタa - the accumulator
- 関数の返値，定数や変数のロード，関数の引数，条件式など汎用的に使う
- トップレベルまで返ってくると計算結果が格納されている
- 例: 10, (1 2 3)
- レジスタx - the next expression
- 次に評価すべき式(中間コード)を格納
- 実際は評価すべき式がリストとして渡されますが，car部分の式が次に評価すべき式
- 例: (constant #f (test …))
- レジスタe - the current environments
- 現在の変数の割り当て(環境)を格納
- クロージャ適用の際に，その引数が新しく追加され環境が更新される
- 変数名は特に意味がないので(後述します)，値だけ入れておく
- リストの先頭が直近のスコープです．
- 例: ((1 2 3) (#t #f) ()), ()
- レジスタr - the current rib
- 関数呼び出しの際に，引数のリストとして使われる
- 引数を評価したレジスタaの値を，consしていく
- 例: (1 2 3), ()
- レジスタs - the current stack
- コールフレーム
- 関数呼び出し時に追加され，呼び出し元の(x e r s)をこの順で格納
- 関数から戻るときはここに待避させたレジスタを復元
- call/ccで継続オブジェクトとして取り出したり，割り付けたりする
- 例: ((return) (1 2 3) () ()), ()
中間コードは以下の通りです．
- (halt)
- VMをhalt
- レジスタaの値を計算結果とする
- (refer var x)
- 変数varの値を現環境から取り出し，レジスタaに
- レジスタxに，引数x(次の命令)をセット
- (constant obj x)
- レジスタaにobjをセット
- レジスタxに，引数x(次の命令)をセット
- (close body x)
- bodyと現環境から，クロージャオブジェクトをつくりレジスタaに
- レジスタxに，引数x(次の命令)をセット
- (test then else)
- レジスタaが#fであれば，レジスタxをthenに
- それ以外であれば，レジスタxをelseに
- (assign var x)
- 現環境の変数varに，レジスタaをセット
- レジスタxに，引数x(次の命令)をセット
- (conti x)
- レジスタsから継続オブジェクトを作り，レジスタaにセット
- レジスタxに，引数x(次の命令)をセット
- 継続オブジェクトは，クロージャオブジェクトの一種として
- (nuate s var)
- スタックの復元
- コールフレームである引数sをレジスタsにセット
- 変数varの値(ここでは(0.0))を現環境から取り出し，レジスタaにセット
- レジスタxを(return)に
- (frame ret x)
- コールフレームを新しくつくる
- レジスタrを空に
- (引数ret レジスタe レジスタr レジスタs)をレジスタsにセット
- (argument x)
- レジスタaを，レジスタrにconsする
- レジスタxに，引数x(次の命令)をセット
- (apply)
- クロージャ適用
- レジスタaから，クロージャ本体bodyと環境eを取り出す
- レジスタxをbodyに
- 環境eにレジスタrを加えて，レジスタeにセット
- (return)
- レジスタsをもとに，レジスタのリスト(x e r s)を取り出し，
- それぞれのレジスタにセット
クロージャ定義&呼び出し
;; schemeコード
((lambda (x y z) (if x y z))
#f 2 3)
↓
;; 中間コード
(frame
(halt)
(constant
3
(argument
(constant
2
(argument
(constant
#f
(argument
(close
(refer
(0 . 0)
(test
(refer
(0 . 1)
(return))
(refer
(0 . 2)
(return))))
(apply)))))))))
この中間コードを実行したときの各レジスタの値の遷移です．
初期状態では，ほとんどのレジスタが空であり，レジスタxのみが次の命令を指す． 1.では，現在のx,e,r,sレジスタからコールフレームを作り，レジスタsに突っ込む． 2.から7.では，constantでレジスタaに値をロードしつつ，argumentでレジスタrに追加していく． 8.では，close命令の第一引数(closureオブジェクト)をレジスタaに，第二引数(関数適用)をレジスタxに追加する． 9.では，レジスタa(closureオブジェクト)から本体をレジスタxに，closureオブジェクトの環境にレジスタrを追加したものをレジスタeにセットする． レジスタrは空にする． 10.では，現環境eから(0.0)の位置にある値を取り出す． 11.では，レジスタaの中身をチェックして真であればtest命令の1つめの引数，偽であれば2つめの引数をレジスタxにセットする． 12.では，(0.2)の位置にある値を取り出して，レジスタaにセットする． 13.では，レジスタsから(x e r s)を取り出して，関数呼び出し前の状態を復元する．
0. ** a = () x = (frame (halt) (constant ...)) e = () r = () s = ()
1. *frame* a = () x = (constant 3 ...) e = () r = () s = ((halt) () () ())
2. *constant* a = 3 x = (argument ...) e = () r = () s = ((halt) () () ())
3. *argument* a = 3 x = (constant 2 ...) e = () r = (3) s = ((halt) () () ())
4. *constant* a = 2 x = (argument ...) e = () r = (3) s = ((halt) () () ())
5. *argument* a = 2 x = (constant #f ...) e = () r = (2 3) s = ((halt) () () ())
6. *constant* a = #f x = (argument ...) e = () r = (2 3) s = ((halt) () () ())
7. *argument* a = #f x = (close (refer ...) (apply)) e = () r = (#f 2 3) s = ((halt) () () ())
8. *close* a = ((refer (0 . 0) ...) ()) x = (apply) e = () r = (#f 2 3) s = ((halt) () () ())
9. *apply* a = ((refer (0 . 0) ...) ()) x = (refer (0 . 0) ...) e = ((#f 2 3)) r = () s = ((halt) () () ())
10. *refer* a = #f x = (test (refer ...) (refer ...)) e = ((#f 2 3)) r = () s = ((halt) () () ())
11. *test* a = #f x = (refer (0 . 2) (return)) e = ((#f 2 3)) r = () s = ((halt) () () ())
12. *refer* a = 3 x = (return) e = ((#f 2 3)) r = () s = ((halt) () () ())
13. *return* a = 3 x = (halt) e = () r = () s = ()
14. *halt* 計算結果a=3を返す
継続
;; schemeコード
(call/cc (lambda (k) (if (k #f) 10 20)))
↓
;; 中間コード
(frame
(halt)
(conti
(argument
(close
(frame
(test
(constant
10
(return))
(constant
20
(return)))
(constant
#f
(argument
(refer
(0 . 0)
(apply)))))
(apply)))))
継続オブジェクトはcontiで作られ，本体が(nuate s (0 . 0))，環境が空のクロージャとしてレジスタaにセットされる． frameが2回呼ばれるのは，一回目は継続オブジェクトを引数にしたλ式の呼び出し，二回目は継続オブジェクト(closureの一種) を呼び出す時です． まず，call/ccは継続オブジェクトを引数に関数を呼び出すということなので，2.でコールフレームを作る． 3.と4.でスタックから継続オブジェクトを作り引数にセットする． 5.でcloseの第一引数(frame …)と現環境からクロージャオブジェクトを作り，レジスタaにセット． 6.で，レジスタaから環境eとレジスタxをセットして，クロージャ適用． これから(if (k #f) 10 20)を評価していく．
7.で(k #f)の評価をする．これは関数呼び出しなので，コールフレームを新しく作る． 8.と9.で定数#fを引数リストに追加． 10.で現環境からk(継続オブジェクト)を取り出し，レジスタaにセット． 11.でその関数(継続オブジェクト)を適用する． 12.でスタックを継続オブジェクトから取り出してセットする．また，レジスタxをreturnにする． 13.でレジスタ群を復帰し，haltで#fが計算結果となる．
1. ** a = () x = (frame (halt) (conti ...)) e = () r = () s = ()
2. *frame* a = () x = (conti ...) e = () r = () s = ((halt) () () ())
3. *conti* a = ((nuate ...) ()) x = (argument ...) e = () r = () s = ((halt) () () ())
4. *argument* a = ((nuate ...) ()) x = (close (frame ...) (apply)) e = () r = (((nuate ...) ())) s = ((halt) () () ())
5. *close* a = ((frame ...) ()) x = (apply) e = () r = (((nuate ...) ())) s = ((halt) () () ())
6. *apply* a = ((frame ...) ()) x = (frame ...) e = ((((nuate ...) ()))) r = () s = ((halt) () () ())
7. *frame* a = ((frame ...) ()) x = (constant #f ...) e = ((((nuate ...) ()))) r = () s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
8. *constant* a = #f x = (argument ...) e = ((((nuate ...) ()))) r = () s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
9. *argument* a = #f x = (refer (0 . 0) ...) e = ((((nuate ...) ()))) r = (#f) s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
10.*refer* a = ((nuate ...) ()) x = (apply) e = ((((nuate ...) ()))) r = (#f) s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
11.*apply* a = ((nuate ...) ()) x = (nuate ...) e = ((#f)) r = () s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
12.*nuate* a = #f x = (return) e = ((#f)) r = () s = ((halt) () () ())
13.*return* a = #f x = (halt) e = () r = () s = ()
14.*halt* 計算結果a=#fを返す
クロージャオブジェクトが命令と定義時の環境のセットを格納していること， 継続オブジェクトはスタックを復元する命令を含むクロージャオブジェクトであること が分かります． ヒープベースでは，この第一級関数も第一級継続もそんなに難しくなく実装できそうです． ここまで読む人なんていないか． スタックベースに進もう．