Toy VM(2)

scheme

Gauche の命令列の一部だけが動くおもちゃの vm を作ってスタックマシンを理解しよう、の続き。時間が空いてしまったので何もかも忘れている。以下、何もかも途中だけど自分のために記録。

SECD Machine をある程度理解した今の頭で、やりたいことの骨格を改めて書いてみた。

  • 手続き vm は、手続き vm-code が生成する gauche の命令列のリスト版、を実行する。
  • 未だちゃんと扱っていないが gauche はプログラムカウンタ pc を使う(SECD では明示的な pc を使っていなかった)。
  • val0 レジスタを使う。
  • stack 操作を gauche のまねをする。

命令について。

  • CONST; 値を val0 にセット。
  • PUSH; スタックに val0 を push

以下のセットが分かれば今回の目的は達成されたと言って良い。

  • CONT レジスタの扱い。
  • RET; 継続の扱いが必要。
  • PRE-CALL; 今のところ何もしていない。
  • CALL, TAIL-CALL; 継続の扱いが必須

TODO;

  • identifier の理解はかなり怪しい。Common Lisp とは違う、とだけ頭に入れておく。
gosh> (vm-code '(* (+ 6 2) 3))
((PRE-CALL 2) 11 (CONST) 6 (PUSH) (CONST) 2 (PUSH) (GREF) #<identifier tgvm#+> (CALL 2) (PUSH) (CONST) 3 (PUSH) (GREF) #<identifier tgvm#*> (TAIL-CALL 2) (RET))
gosh> (vm 's 'e 0 'd (vm-code '(* (+ 6 2) 3)) ())
24

(define (vm s e pc d base val0)
  (define (identifier->proc id)
    (cond
     ((equal? id '+) +)
     ((equal? id '-) -)
     ((equal? id '*) *)
     ((equal? id '>) >)
     ((equal? id '<) <)
     (else (errorf "Unknown id:~a" id))))
  ;;
  (let ((c (list-tail base pc)))
    ;;#?=(list :s s :e e :pc pc :d d :val0 val0)
    (match c
      ((('CONST) val . c)
       (vm s e (+ pc 2) d base val))

      ((('PUSH) . c)
       (vm (cons val0 s) e (+ pc 1) d base val0))

      ((('GREF) var . c)
       (vm s e (+ pc 2) d base (identifier->proc var)))

      ((('RET) . c) ;; TODO
       val0)

      ((('PRE-CALL proc-id) location . c) ;; TODO
       (vm s e (+ pc 2) d base val0))

      ;; CALL
      ((('CALL nargs) . c)
       (unless (procedure? val0)
         (errorf "val0 is not PROC: ~a" val0))
       (let ((args ()))
         (for-each (lambda (n)
                     (set! args (cons (pop! s) args))) (iota nargs))
         (vm s e (+ pc 1) d base (apply val0 args))))

      ((('TAIL-CALL nargs) . c)
       (unless (procedure? val0)
         (errorf "val0 is not PROC: ~a" val0))
       (let ((args ()))
         (for-each (lambda (n)
                     (set! args (cons (pop! s) args))) (iota nargs))
         (vm s e (+ pc 1) d base (apply val0 args))))

      ;; base condition
      (else
       (values (list :s s :e e :pc pc :d d :val0 val0) 'stop)))))

メモ

マクロだとか定義の場所。すぐ忘れる。

  • TAIL-CALL -> vminsn.scm
  • DISCARD-ENV -> vm.c
  • RETURN-OP -> vm.c
  • POP_CONT -> vm.c

Reading Gauche

プログラム断片。http://practical-scheme.net/wiliki/wiliki.cgi?Gauche%3aYAGHG も改めて参考にしつつ。とにかく最小の例 -- 正しい TAIL-CALLあるいは CALL の例 -- が欲しい。

gosh> (vm-code '(begin (+ 1 2) 1))
((PRE-CALL 2) 11 (CONST) 1 (PUSH) (CONST) 2 (PUSH) (GREF) #<identifier tgvm#+> (CALL 2) (CONST) 1 (RET))

これかな。PRE-CALL で次に実行するPC (= 11) を保存しておいて、CALL の後でそれを復帰させる。
今の自作のコードは根本的に間違っていて、かつ、たまたま動いているように見えてるだけだ。うーん。