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

これは、

である。

次に命令 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 は無関係だろうか、それとも対応付いているだろうか。ちょっと頭を冷やして考えよう。