Toy VM(7) - cranebirdの日記

ようやく分かってきた。
「継続」というのは、結局、様々な本や解説で書かれているとおり、これから行う計算でしかないんだ。

Gauche の VM。
SECD マシン。
扱いは違うように見えるけど。

SECD マシンは、命令列もスタックもリストだった。このことが、少し比較をしにくくしている。
命令列をリストではなくベクトルで持つ SECD マシンを書こう。

まず VM を書く。わたしが書いた SECD マシンは実際は単なる関数だった。今度はオブジェクトとして書く。ただの入れ物だ。

命令列の処理のしかたはいくらでもある。ようは、命令の種類によって何かの処理が書ければいい。
scheme で書いたときは util.match によるパターンマッチがまさにぴったりのユーティリティだった。
Common Lisp で書く場合でも、パターンマッチは無くても cond や case を使えばいい。
けど、今回は dispatch という総称関数を定義してみよう。ようするに、処理を分岐できればいいんだ。
dispatch は、「総称」すると -- つまり、ひとまとめにして何か名前をつけてやるならば --
「特定の命令と VM のインスタンスを受け取って処理する」だ。

(defgeneric dispatch (insn vm)
  (:documentation "dispatch vm instruction."))

Common Lisp の総称関数は eql specializer なるものを使える。実践 Common Lisp 24.7 。これを使うと、特定の命令ごとに処理が書ける。
命令を定義するときは、繰り返しが多くなりそうだから、マクロを定義しておく。
べったりと書いてもいいけど、後のことを考えて。反復練習をしたい訳じゃないんだから。

(defmacro def-insn (name (vm) &rest body)
  (let ((insn (gensym)))
  `(defmethod dispatch ((,insn (eql ,(as-keyword name))) (,vm vm))
     (declare (ignore ,insn))
     ,@body)))

こんな風に定義してやる。

(def-insn ldc (vm)
  (let ((c (fetch-operand vm)))
    (stack-push vm c)
    (incr-pc vm)
    (next vm)))

とにかく早く動くようにする。まずは LDC 命令。次に算術演算子。ここまでは簡単だ。

次が SEL だ。if を実現するための分岐。
ここまできてからまごついた。そもそもベクトルで命令を持つのだから、SECD マシンのように命令列を入れ子 - リスト - にしちゃだめだ。

;; リスト版
(LDC 1 SEL (LDC 2 JOIN) (LDC 3 JOIN))

;; リスト版
SEL     (x.s) e (SEL ct cf.c) d   ->  s e c' (c.d)
                 where c' = ct if x is T, and cf if x is F
JOIN    s e (JOIN.c) (cr.d)  ->  s e cr d

分岐 SEL, JOIN の実装もそもそも変えなきゃならない。ベクトルだから入れ子構造は取れないから、 ct, cf はそのままは使えない。

試行錯誤して、以下のようにコンパイルすればいいと考えた。（今のところ。もうすこし先に進めたら間違いがわかるかもしれないけど）

(if 1 2 3) =>
#(:LDC 1 :SEL 6 9 12 :LDC 2 :JOIN :LDC 3 :JOIN :STOP)

ここで SEL の後の数字３つはプログラムカウンタだ。６は６番目の要素（２度目の:LDC）に対応する。それぞれ ct, cf, cont に対応する。

先に VM 側を作ってやって、動作することを確認。
あとはコンパイルしてこのベクトルを作れればいい。これにはわたしの腕だと2パス必要だった。一度プログラム全体を処理して
ラベルを登録して、後で実際の値に置き換える。

さあもう少しだ。

続く。