命令群を列にしよう - Scheme VM を書く

scheme

3impの実装は基本的に命令が Pair の入れ子になる。

(CONSTANT 3 (CONSTANT 4 (HALT)))

自分自身の引数が自分の中にある。
次の命令も自分の中にあるという構成。
これは VM を書くときに（人によっては）解りやすい。


しかし if による分岐時のコードの倍増（これは#0#的参照を利用すれば解決できる）が発生する。
パラメータや、次の命令を取得するのに car/cdr で辿らないといけないので、配列のようにO(1)よりは遅くなる。
など良くない点の方が多い。
Direct threaded code が面倒なのものこの構造のせい。


そこでこれを配列かベクタに置き換えようと思う。（というかこちらの方が普通の方法だろう）
前述の例であれば

#(CONSTANT 3 CONSTANT 4 HALT)

となる。

進めかた

大きな変更だから、処理系は動かなくなり時間もかかるであろう。

  • ブランチを作る
  • プリミティブな命令の設計
  • Gauche 版のコンパイラ/VMを書き直し。コンパイラ/VMともに少しずつテストと命令を足す。コンパイラは最速で動くように気を配る。
    • CONSTANT / HALT
    • IF
    • CLOSE / APPLY / FRAME / SHIFT / RETURN
    • CONTI / NUATE
    • その他
  • C++ 版のVMの実装
  • その他調整
    • Wiki
    • test-compile
    • テスト全般

プリミティブな命令の設計

LOCAL_JMP

引数分 pc を increment する。

TEST（分岐）
(begin (if #t (begin 3 4) 5) 6)

[ ] はまとまりを見やすくするためで実際には存在しない。

#([分岐条件 [TEST elseへのオフセット then LOCAL_JMP elseの長さ else] next
#([CONSTANT #t] [TEST 6 [[[CONSTANT 3] [CONSTANT 4]] [LOCAL_JMP 2]] [CONSTANT 5]] [CONSTANT 6]

TEST 直後の引数は else への offset。

CLOSE
(lambda (a) a)

#(CLOSE free-variableの数 引数の数 オプション引数? free-variableの列 bodyの列)
#(CLOSE 0 1 #f [] [[CONSTANT 3] [RETURN 1]])
FRAME/APPLY/ARGUMENT/REFER_GLOBAL
(a 2)

#(FRAME)          ; Frame作成（今までと違nextではなく pc を push する）
#(ARGUMENT)       ; accumulator を push
#(REFER_GLOBAL)   ; シンボルを lookup 後 accumulator にセット
#(APPLY 引数の数) ; 手続き呼出し

#(FRAME [CONSTANT 2] ARGUMENT [REFER_GLOBAL a] [APPLY 1])
RETURN
#(RETURN n)

スタックから pc, sp などを復帰。