toy VM

scheme

Gauche の命令列の一部だけが動くおもちゃの vm を作ってスタックマシンを理解しよう。目標は、加減乗除と lambdaと関数適用が動く vm を作ること。
半年くらいまえに浅くやっていたものを、3imp で少し成長したのでもう一歩進める。

準備

  • 最適化があるとわかりにくいので、vm-compiler-flag-set! を使って最適化をしないようにする。gosh にオプションをつけてもよい。-fno-inline, -fno-combine-instructions 。
  • compile されたプログラムをリストで取得して操作したいので、compile.scm に数行足して make しなおす。
;; add compile-pass* to gauche compile.scm and "make"
;; (define (compile-pass1 program)
;;   (pass1 program (make-bottom-cenv)))
;;
;; (define (compile-pass2 iform)
;;   (pass2 iform))
;;
;; (define (compile-pass3 iform)
;;   (pass3 iform
;;          (make-compiled-code-builder 0 0 '%toplevel #f #f)
;;          '() 'tail))

;; utility in gauche.internal module
(define compile-pass1 (with-module gauche.internal compile-pass1))
(define compile-pass2 (with-module gauche.internal compile-pass2))
(define compile-pass3 (with-module gauche.internal compile-pass3))
(define vm-code->list (with-module gauche.internal vm-code->list))
(define vm-compiler-flag-set!
  (with-module gauche.internal vm-compiler-flag-set!))
(define vm-compiler-flag-clear!
  (with-module gauche.internal vm-compiler-flag-clear!))

(define (vm-code program)
  (vm-code->list (compile-pass3 (compile-pass1 program))))

(define (opt flag)
  (let1 set/clear (if flag vm-compiler-flag-clear! vm-compiler-flag-set!)
    (map set/clear
         (list
          (with-module gauche.internal SCM_COMPILE_NOINLINE_CONSTS)
          (with-module gauche.internal SCM_COMPILE_NOINLINE_GLOBALS)
          (with-module gauche.internal SCM_COMPILE_NOINLINE_LOCALS)))))

(define (disable-opt) (opt #f)) ;; set vm-compiler-flag to disable optimize
(define (enable-opt) (opt #t)) ;; clear vm-compiler-flag to enable optimize

使用例。

gosh> (opt #f)
(#<undef> #<undef> #<undef>)
gosh> (vm-code '(+ 1 2 3))
((CONSTI-PUSH 1) (CONSTI-PUSH 2) (CONSTI-PUSH 3) (GREF-TAIL-CALL 3) #<identifier toy#+> (RET))
gosh> (opt #t)
(#<undef> #<undef> #<undef>)
gosh> (vm-code '(+ 1 2 3))
((CONSTI 6) (RET))

参考資料

いくつか参考にできる資料がある。

これとプログラムソース。


スタックマシンの構造

VM を define-class で定義されたクラスにする。いくつかの構造は scheme の構造(単なるリストとかベクトルとか、ハッシュテーブルとか)に置き換える。
ほんものの VM ではないので速度や効率は気にしなくてよい。

src/gauche/vm.h と Reading Gauche を見くらべて。

  • expr
  • val0

スタックマシンだけどレジスタを持っている。

  • pc
  • code
  • sp
  • stack

スタックはとりあえずただのリストを使おう。sp は当面無視。

  • env
  • cont
  • argp

命令

現在200個が定義されている。うち、57 個は combined (合成命令?)のため、基本は 143 個。
理解しなければならない命令は多分これだけ。Gauche VM 全体では200個なので 12/200 = 6%か。

  • BF
  • CALL
  • CLOSURE
  • CONST
  • GREF
  • GREF-TAIL-CALL (合成命令)
  • LREF
  • LREF0
  • PRE-CALL
  • PUSH
  • TAIL-CALL
  • RET

この命令は vminsn.scm で定義される。さらに C のマクロを呼び出しているので、C のマクロの階層(vm.c)まで降りれば正確な定義が分かる。クラスのインスタンスから対話環境で情報を取ることもできる(http://d.hatena.ne.jp/yamanetoshi/20090304 が参考になる)。

gosh> (use gauche.vm.insn)
gosh> (use gauche.interactive)
gosh> (map (lambda (x)
             (describe (cdr x)))
                  (class-slot-ref <vm-insn-info> 'all-insns))
#<insn VALUES-RET> is an instance of class <vm-insn-info>
slots:
  name      : VALUES-RET
  code      : 199
  num-params: 1
  operand-type: none
  combined  : (VALUES RET)
  body      : (begin ($values) (RETURN-OP) NEXT)
  base-variant: #f
  push-variant: #f
  ret-variant: #f
  all-insns : ((VALUES-RET . #<insn VALUES-RET>) (LREF30-CDR . #<insn LREF
#<insn LREF30-CDR> is an instance of class <vm-insn-info>
slots:
  name      : LREF30-CDR
  code      : 198
  num-params: 0
  operand-type: none
  combined  : (LREF30 CDR)
  body      : #f
  base-variant: #f
  push-variant: #f
  ret-variant: #f
  all-insns : ((VALUES-RET . #<insn VALUES-RET>) (LREF30-CDR . #<insn LREF
以下略
CONSTI

VAL0 に値をセット。vmins.scm での定義はよく分からない。

PUSH

たぶんOK。

RET

これがちゃんと書ければだいぶ Gauche VM の構造を理解したことになる。RETURN_OP を実行。
RETURN_OP は vm.c で定義されるマクロ。さらに POP_CONT を呼び出す。POP_CONT は vm.c を見ると３パターン。よくわからないけどとりあえず２番目が"普通"の場合と想定。
1) CONT->argp が NULL => C-continuation の場合
2) IN_STACK_P(CONT) のとき
3) それ以外

将来構想

  • visualize
  • スタックマシンと無限レジスタマシンの間の変換方法。

メモ

  • RET をちゃんと作るだけで結構大変かもしれない。
  • まずは SECD。（VM の人にとっては超常識っぽい。が手元の本にはのってない。うーん）