box の実装 - Scheme VM を書く

代入を導入するために box を実装する。（例の論文のまんまです）

box 導入の背景

bind された変数をヒープ上の environment に置くのではなく、スタックに置くようになったことで

continuation 作成時に bind 情報がコピーされて少なくとも2ヵ所に分散する
free variable を保持した display closure を導入したことでコピーが保持される

ことが発生し、代入をサポートする場合、代入時に各コピーを更新する必要が発生する。

これを実行時に行うのはオーバヘッドが高く現実的ではない。
かといって、全ての変数をヒープ上に確保するのも無駄になってしまう。（代入される変数は少数だから）

これを解決するために box という仕組みを導入する。

box とは？

仕組みは簡単、コンパイル時に代入される変数を見つけておいて、代入される変数は特別扱いしてヒープ上にデータ構造(box)を保持する。
スタック上にその変数が置かれる場合には値ではなくて、box への参照が置かれる。
continuation や display closure でこの box を共有することで上記の問題が解決される。
しかも代入が起こる変数だけに適用するのでヒープの確保も最低限で済む。

Scheme はレキシカルなスコープを持つから、コンパイル時に代入を見つけるのはとても簡単。
set! を探せば良い。

実装

box は何かの参照であれば良いので今回は pair を使う。

(define (box v)
  (cons 'box v))

(define (set-box! b v)
  (set-cdr! b v))

(define (unbox b)
  (cdr b))

...
     [box (n x)
       (index-set! s n (box (index s n)))
       (VM a x f c s)]
...	
     [assign-local (n x)
       (set-box! (index f n) a)
       (VM a x f c s)]
     [assign-free (n x)
       (set-box! (index-closure c n) a)
       (VM a x f c s)]

というわけで Scheme で書いた VM では以下のようなものが動くようになった。

((lambda (a) (set! a 12) a) 2)
((lambda (a) ((lambda () (set! a 101))) a) 100)

処理を追う

((lambda (a) (set! a 12) a) 2)
=> (frame () (constant 2 (argument (close 0 (box 0 (constant 12 (assign-local 0 (return 1)))) (apply)))))

呼び出される手続きの中で box を作成してスタック上に置く。
コンパイル時に決まるスタック上の index を使用してこの box に対してアクセスし代入を実行する。
よし分かった。

さあ C++ の VM にも box を作ろう。 → できた！