スタックベースVMの詳細 - Scheme VM のお勉強

手続き呼出し

(compile '((lambda (a) a) 4) '() '())
=> (frame () (constant 4 (argument (close (refer 0 0 (return 2)) (apply)))))

1.(frame (ret x)) は environment をスタックに push し、ret をスタックにプッシュする。
そして x を next expression にセット。

=============
   e =>'()
=============
  next=>'()
=============

2.(constant (obj x)) はヒープベースと挙動が同じ。
accumulator に 4 をセットし next expression に (argument ...) をセットする。

3.(argument (x)) はスタックに accumulator の値を push する。
そして next expression に (close ...) をセットする。

=============
   e =>'()
=============
  next=>'()
=============
  arg=> 4
=============

4.(close (body x)) は (body e) なリストを accumulator にセットする。
そして next expression に (apply) をセットする。

=====================
   e   => '()
=====================
  next => '()
=====================
  arg  => 4
======================

5.(apply)は accumulator に (body link) の形で functional があるので、body を next expression にセットする。
現在のスタック register を environment にセットする。
link をスタックに push する。

=====================
   e   => '()
=====================
  next => '()
=====================
  arg  => 4
======================
  link => '()
======================

6.(refer (n m x)) は x を next expression にセットする。
environment にセットされているスタックレジスタ（ポインタ）を基準に(n, m) な変数を参照し accumulator にセットする。
ここはあとで引数を増やして検証する。

7.(return n) は、まずスタックポインタ n だけ減算する。
その位置 s に対して s が、next expression。
s - 1 が environment 。
s - 2 が元のスタックレジスタである。

まとめると手続き呼出し時には

frame で environment と next expression が pushされる
argument で引数が push される
apply で environment (static link)が push される
refer でスタック上の引数が参照される
return でスタックから environment と next expression を復帰して実行再開する

という流れ。

引数が増えた場合

(compile '((lambda (a b) b) 4 5) '() '())
=> (frame () (constant 5 (argument (constant 4 (argument (close (refer 0 1 (return 3)) (apply)))))))

まず return で減算されるスタックポインタの数が引数の個数分だけ違う。
refer 時のスタック参照位置が異なる。
というところかな。

手続き呼出しが連続する場合

(compile '((lambda (a b) ((lambda (c) b) 3) 4 5) '() '()))
=> (frame () (constant () (argument (constant () (argument (close (frame (return 3)
     (constant 3 (argument (close (refer 1 1 (return 2)) (apply))))) (apply)))))))

予想通り。

まとめ

いわゆる実マシンがスタックを利用して手続き呼出しをするのと仕組みは同じ。