Toy VM(6) 整理
整理しよう。わたしの手元にあるのは、
http://webdocs.cs.ualberta.ca/~you/courses/325/Mynotes/Fun/SECD-slides.html
を実装した SECD マシン (A)だ。コンパイラとセットで、let,lambda,letrec くらいを実行できる。コメント込みで高々200行だ。自分で作ったのだから中身はある程度分かっている。
当面の目的は、 Gauche の命令列の一部が Gauche と同じ仕組みで動く VM (B)だ。Gauche VM そのもの (C)は、まだ読み解けない。いまは、(B)を作りながら(C)を理解しようとしている。走りながら考える、ってことだ。
まずは、「(B)は SECD マシン(A)の変形で作れる」、としよう。でも、(A)と(C)には幾つか違いがある。
一つ目。(C)は 値レジスタ(val0)なるものを持っていて、これを計算結果を保持するのに使う。
二つ目。(C)は命令列をベクタで持ち、プログラムカウンタを使う。
まずは SECD マシンの動きを改めて追いかけよう。無名関数で 5の2乗を計算してみる。
gosh> (run '((lambda (n) (* n n)) 5))
Step | Stack | Env | Code | Dump |
---|---|---|---|---|
1 | s | e | (NIL LDC 5 CONS LDF (LD (1 . 1) LD (1 . 1) * RTN) AP . c) | d |
2 | (NIL . s) | e | (LDC 5 CONS LDF (LD (1 . 1) LD (1 . 1) * RTN) AP . c) | d |
3 | (5 NIL . s) | e | (CONS LDF (LD (1 . 1) LD (1 . 1) * RTN) AP . c) | d |
4 | ( (5) . s) | e | (LDF (LD (1 . 1) LD (1 . 1) * RTN) AP . c) | d |
5 | ( ( (LD (1 . 1) LD (1 . 1) * RTN) . e) (5) . s) | e | (AP . c) | d |
6 | NIL | ( (5) . e) | (LD (1 . 1) LD (1 . 1) * RTN) | (s e c . d) |
7 | (5 . NIL) | ( (5) . e) | (LD (1 . 1) * RTN) | (s e c . d) |
8 | (5 5 . NIL) | ( (5) . e) | (* RTN) | (s e c . d) |
9 | (25 . NIL) | ( (5) . e) | (RTN) | (s e c . d) |
10 | (25 . s) | e | c | d |
言葉を整理しよう。
- クロージャ: Step 4 で作られる、関数と環境を cons したもの。
- 環境: リストのリスト。コンパイル時の環境と実行時の環境とがある。
- 継続: Step 5 で保存されて、Step 9 で元に戻される。
- Step 1-3. NIL, LDC, CONS。スタック S に (5) を積む。 このリスト(5)は、関数の引数に相当し、 v と略す。
- Step 4. LDF。 square 本体を f と書くと、f と現在の環境 e からクロージャを作り、スタックに積む。
この時点で、スタックには (f . e) v 、すなわち、クロージャと引数が積まれている。
- Step 5. AP。関数の適用。実行前に、環境を保存した継続フレーム(s e c)を d に設定。
関数の本体 f をスタック C に設定し、クロージャから取り出した環境を E に設定し、計算を続行する。
- Step 6-7. f の本体。環境は実引数のリスト。環境から値 5 を取ってスタックに積む。
- Step 8. かけ算 * を実行し、結果をスタックに積む。
- Step 9. RTN。保存していた継続フレームを元に戻す。ただしスタックのトップだけはそのまま。 Step 5 は、 ( (f . e2) v . s) e (AP . c) d だったので、 関数適用が終わった。
さあ、比較しよう。
PRE_CALL は、手続き呼び出しの前に、 RET 実行後に実行すべきコードと環境を保存する。
- PRE_CALL は、最適化を外した状態でも、常に生成される訳ではない。まだその理由は分かっていない。
- CALL と PRE_CALL の関係もまだ怪しい。
gosh> (disasm (lambda () (+ 7 (+ 8 9)))) main_code (name=#f, code=0x763960, size=19, const=2, stack=13): args: #f 0 CONST 7 2 PUSH 3 PRE-CALL(2) 14 5 CONST 8 7 PUSH 8 CONST 9 10 PUSH 11 GREF #<identifier secd#+>; + 13 CALL(2) ; (+ 8 9) 14 PUSH 15 GREF #<identifier secd#+>; + 17 TAIL-CALL(2) ; (+ 7 (+ 8 9)) 18 RET #<undef> gosh> (run '(+ 7 (+ 8 9))) secd (s e (LDC 9 LDC 8 + LDC 7 + . c) d) ;; LDC 9 ( (9 . s) e (LDC 8 + LDC 7 + . c) d) ;; LDC 8 ( (8 9 . s) e (+ LDC 7 + . c) d) ;; + ( (17 . s) e (LDC 7 + . c) d) ;; LDC 7 ( (7 17 . s) e (+ . c) d) ;; + ( (24 . s) e c d) ;; 24 ( (24 . s) e c d) stop
おっと、これは例が悪い。これでは、dump スタックが全く使われていない。SECD マシンで dump が使われるのは関数を呼ぶ時だ。gauche 側は + を呼び出している一方、secd 側はプリミティブな命令 + を実行している。あと評価の順番が違う。gauche は先に 7 をスタックに積んでいるけど、secd は 7 を積むのは最後だ。
冗長になるけど、こんな例はどうだろう。
(let ((plus (lambda (x y) (+ x y)))) (plus 7 (plus 8 9))) 24 gosh> (disasm (lambda () (let ((plus (lambda (x y) (+ x y)))) (plus 7 (plus 8 9))))) main_code (name=#f, code=0x1047c08, size=21, const=1, stack=17): args: #f 0 CLOSURE #<lambda 0> ; (lambda (x y) (+ x y)) 2 PUSH 3 LOCAL-ENV(1) ; (let ((plus (lambda (x y) (+ x y)))) (pl ... 4 CONST 7 6 PUSH 7 PRE-CALL(2) 17 9 CONST 8 11 PUSH 12 CONST 9 14 PUSH 15 LREF(0,0) ; plus 16 CALL(2) ; (plus 8 9) 17 PUSH 18 LREF(0,0) ; plus 19 TAIL-CALL(2) ; (plus 7 (plus 8 9)) 20 RET internal_closure_0 (name=plus, code=0xc4ca0, size=8, const=1 stack=5): args: #f 0 LREF(0,1) ; x 1 PUSH 2 LREF(0,0) ; y 3 PUSH 4 GREF #<identifier secd#+>; + 6 TAIL-CALL(2) ; (+ x y) 7 RET #<undef>
LOCAL-ENV, LREF, internal_closure_0 という分かっていないのが出てきたけど、さっきよりは比較できそうだ。LREF は LD 相当だろう。
手で追いかけてみよう。
以下、長くなるので、(lambda (x y) (+ x y)) の部分と、 (plus 7 (plus 8 9)) の部分をそれぞれ記号で略記する。
plus-body = (LD (1 . 2) LD (1 . 1) + RTN) let-body = (NIL NIL LDC 9 CONS LDC 8 CONS LD (1 . 1) AP CONS LDC 7 CONS LD (1 . 1) AP RTN)
まずクロージャ plus を保存する。このクロージャは引数リストの一部になる。
- :S s :E e :C (NIL LDF plus-body CONS LDF let-body AP . c) :D d
- :S (NIL . s) :E e :C (LDF plus-body CONS LDF let-body AP . c) :D d
- :S ( (plus-body . e) NIL . s) :E e :C (CONS LDF let-body AP . c) :D d
- :S ( ( (plus-body . e)) . s) :E e :C (LDF let-body AP . c) :D d
これは、
- :S (引数リスト . s) :E e :C (LDF let-body AP . c) :D d
である。
次に命令 LDF によって、クロージャ let-body を保存する。
- :S ( ( let-body . e) ( (plus-body . e)) . s) :E e :C (AP . c) :D d
これは、
- :S (クロージャ 引数リスト . s) :E e :C (AP . c) :D d
である。
次に命令 AP によって、現在の継続を保存した上で、let-body 本体をコードスタックに移し実行する。
- :S NIL :E ( ( (plus-body . e)) . e) :C let-body :D (s e c . d)
これは、
- :S NIL :E (引数リスト . e) :C let-body :D (s e c . d)
である。
以下、let-body を順に評価する。
- :S (NIL . NIL) :E ( ( (plus-body . e)) . e) :C (NIL LDC 9 CONS LDC 8 CONS LD (1 . 1) AP CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
- :S (NIL NIL . NIL) :E ( ( (plus-body . e)) . e) :C (LDC 9 CONS LDC 8 CONS LD (1 . 1) AP CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
- :S (9 NIL NIL . NIL) :E ( ( (plus-body . e)) . e) :C (CONS LDC 8 CONS LD (1 . 1) AP CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
- :S ( (9) NIL . NIL) :E ( ( (plus-body . e)) . e) :C (LDC 8 CONS LD (1 . 1) AP CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
- :S (8 (9) NIL . NIL) :E ( ( (plus-body . e)) . e) :C (CONS LD (1 . 1) AP CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
引数リスト (8 9) をスタックに積む。
- :S ( (8 9) NIL . NIL) :E ( ( (plus-body . e)) . e) :C (LD (1 . 1) AP CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
命令 LD によって、環境からクロージャを取り出し、スタックに積む。
- :S ( (plus-body . e) (8 9) NIL . NIL) :E ( ( (plus-body . e)) . e) :C (AP CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
命令 AP によって、継続、すなわち (CONS LDC 7 CONS LD (1 . 1) AP RTN) をダンプスタックに保存し、plus-body を評価する。
- :S NIL :E ( (8 9) . e) :C plus-body :D ( (NIL . NIL) ( ( (plus-body . e)) . e) (CONS LDC 7 CONS LD (1 . 1) AP RTN) s e c . d)
次に plus-body の実行に移る。
- :S (9 . NIL) :E ( (8 9) . e) :C (LD (1 . 1) + RTN) :D ( (NIL . NIL) ( ( (plus-body . e)) . e) (CONS LDC 7 CONS LD (1 . 1) AP RTN) s e c . d)
- :S (8 9 . NIL) :E ( (8 9) . e) :C (+ RTN) :D ( (NIL . NIL) ( ( (plus-body . e)) . e) (CONS LDC 7 CONS LD (1 . 1) AP RTN) s e c . d)
- :S (17 . NIL) :E ( (8 9) . e) :C (RTN) :D ( (NIL . NIL) ( ( (plus-body . e)) . e) (CONS LDC 7 CONS LD (1 . 1) AP RTN) s e c . d)
足し算の実行後は、命令 RTN によって、保存していた継続を復帰する。
- :S (17 NIL . NIL) :E ( ( (plus-body . e)) . e) :C (CONS LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
再び引数リストを作る。
- :S ( (17) . NIL) :E ( ( (plus-body . e)) . e) :C (LDC 7 CONS LD (1 . 1) AP RTN) :D (s e c . d)
- :S (7 (17) . NIL) :E ( ( (plus-body . e)) . e) :C (CONS LD (1 . 1) AP RTN) :D (s e c . d)
- :S ( (7 17) . NIL) :E ( ( (plus-body . e)) . e) :C (LD (1 . 1) AP RTN) :D (s e c . d)
再び環境から 命令 LD によってクロージャを取り出す。
- :S ( (plus-body . e) (7 17) . NIL) :E ( ( (plus-body . e)) . e) :C (AP RTN) :D (s e c . d)
命令 AP によって、継続、すなわち(RTN)をダンプスタックに保存し、再び plus-body を評価する。
- :S NIL :E ( (7 17) . e) :C plus-body :D (NIL ( ( (plus-body . e)) . e) (RTN) s e c . d)
- :S (17 . NIL) :E ( (7 17) . e) :C (LD (1 . 1) + RTN) :D (NIL ( ( (plus-body . e)) . e) (RTN) s e c . d)
- :S (7 17 . NIL) :E ( (7 17) . e) :C (+ RTN) :D (NIL ( ( (plus-body . e)) . e) (RTN) s e c . d)
- :S (24 . NIL) :E ( (7 17) . e) :C (RTN) :D (NIL ( ( (plus-body . e)) . e) (RTN) s e c . d)
命令 RTN によって、保存していた継続を復帰する。
- :S (24 . NIL) :E ( ( (plus-body . e)) . e) :C (RTN) :D (s e c . d)
もう一度命令 RTN によって、保存していた継続を復帰する。
- :S (24 . s) :E e :C c :D d
以上。
さて、 SECD マシンの継続の保存と、PRE-CALL は無関係だろうか、それとも対応付いているだろうか。ちょっと頭を冷やして考えよう。