bobuhiro11's diary

3imp ヒープ型VM

06 Feb 2014

3impを3章まで読んだので備忘録です. 以前にschemeっぽいのを書いたのでもうちょっとマシなのを作りたいという ことです. 3impは,schemeの処理系をheapベース,stackベース,stringベースの三種類で 具体的に紹介してくれているありがたい論文です. 特に3章heapベースのVMの動きを書き残しておきます.

コンパイラ

schemeコード -> コンパイラ -> 中間コード -> VMで実行

という流れなので,まずschemeコードから中間コードへのコンパイラを作ります. 継続渡しとでもいうのかな. 基本的に前から後ろに命令が流れていきます. コンパイラの詳細は論文にあるので省略します.

;; schemeコード
(if #f 10 20)

;; 中間コード
(constant #f (test (constant 10 (halt))
                   (constant 20 (halt))))

VMの仕様

レジスタと中間コードの仕様は以下の通りです. まず,VMには以下の5つのレジスタがあります.

中間コードは以下の通りです.

クロージャ定義&呼び出し

;; schemeコード
((lambda (x y z) (if x y z))
  #f 2 3)

;; 中間コード
(frame
  (halt)
  (constant
    3
    (argument
      (constant
        2
        (argument
          (constant
            #f 
            (argument
              (close
                (refer
                  (0 . 0)
                  (test
                    (refer
                      (0 . 1)
                      (return))
                    (refer
                      (0 . 2)
                      (return)))) 
                (apply)))))))))

この中間コードを実行したときの各レジスタの値の遷移です.

初期状態では,ほとんどのレジスタが空であり,レジスタxのみが次の命令を指す. 1.では,現在のx,e,r,sレジスタからコールフレームを作り,レジスタsに突っ込む. 2.から7.では,constantでレジスタaに値をロードしつつ,argumentでレジスタrに追加していく. 8.では,close命令の第一引数(closureオブジェクト)をレジスタaに,第二引数(関数適用)をレジスタxに追加する. 9.では,レジスタa(closureオブジェクト)から本体をレジスタxに,closureオブジェクトの環境にレジスタrを追加したものをレジスタeにセットする. レジスタrは空にする. 10.では,現環境eから(0.0)の位置にある値を取り出す. 11.では,レジスタaの中身をチェックして真であればtest命令の1つめの引数,偽であれば2つめの引数をレジスタxにセットする. 12.では,(0.2)の位置にある値を取り出して,レジスタaにセットする. 13.では,レジスタsから(x e r s)を取り出して,関数呼び出し前の状態を復元する.

0.  **          a = ()                         x = (frame (halt) (constant ...))  e = ()         r = ()       s = ()
1.  *frame*     a = ()                         x = (constant 3 ...)               e = ()         r = ()       s = ((halt) () () ())
2.  *constant*  a = 3                          x = (argument ...)                 e = ()         r = ()       s = ((halt) () () ())
3.  *argument*  a = 3                          x = (constant 2 ...)               e = ()         r = (3)      s = ((halt) () () ())
4.  *constant*  a = 2                          x = (argument ...)                 e = ()         r = (3)      s = ((halt) () () ())
5.  *argument*  a = 2                          x = (constant #f ...)              e = ()         r = (2 3)    s = ((halt) () () ())
6.  *constant*  a = #f                         x = (argument ...)                 e = ()         r = (2 3)    s = ((halt) () () ())
7.  *argument*  a = #f                         x = (close (refer ...) (apply))    e = ()         r = (#f 2 3) s = ((halt) () () ())
8.  *close*     a = ((refer (0 . 0) ...) ())   x = (apply)                        e = ()         r = (#f 2 3) s = ((halt) () () ())
9.  *apply*     a = ((refer (0 . 0) ...) ())   x = (refer (0 . 0) ...)            e = ((#f 2 3)) r = ()       s = ((halt) () () ())
10. *refer*     a = #f                         x = (test (refer ...) (refer ...)) e = ((#f 2 3)) r = ()       s = ((halt) () () ())
11. *test*      a = #f                         x = (refer (0 . 2) (return))       e = ((#f 2 3)) r = ()       s = ((halt) () () ())
12. *refer*     a = 3                          x = (return)                       e = ((#f 2 3)) r = ()       s = ((halt) () () ())
13. *return*    a = 3                          x = (halt)                         e = ()         r = ()       s = ()
14. *halt*      計算結果a=3を返す

継続

;; schemeコード
(call/cc (lambda (k)  (if (k #f) 10 20)))

;; 中間コード
(frame
  (halt)
  (conti
    (argument
      (close
        (frame
          (test
            (constant
              10
              (return))
            (constant
              20 
              (return)))
          (constant
            #f
              (argument
                (refer
                  (0 . 0)
                  (apply)))))
        (apply)))))

継続オブジェクトはcontiで作られ,本体が(nuate s (0 . 0)),環境が空のクロージャとしてレジスタaにセットされる. frameが2回呼ばれるのは,一回目は継続オブジェクトを引数にしたλ式の呼び出し,二回目は継続オブジェクト(closureの一種) を呼び出す時です. まず,call/ccは継続オブジェクトを引数に関数を呼び出すということなので,2.でコールフレームを作る. 3.と4.でスタックから継続オブジェクトを作り引数にセットする. 5.でcloseの第一引数(frame …)と現環境からクロージャオブジェクトを作り,レジスタaにセット. 6.で,レジスタaから環境eとレジスタxをセットして,クロージャ適用. これから(if (k #f) 10 20)を評価していく.

7.で(k #f)の評価をする.これは関数呼び出しなので,コールフレームを新しく作る. 8.と9.で定数#fを引数リストに追加. 10.で現環境からk(継続オブジェクト)を取り出し,レジスタaにセット. 11.でその関数(継続オブジェクト)を適用する. 12.でスタックを継続オブジェクトから取り出してセットする.また,レジスタxをreturnにする. 13.でレジスタ群を復帰し,haltで#fが計算結果となる.

1. **         a = ()               x = (frame (halt) (conti ...))  e = ()                   r = ()                 s = ()
2. *frame*    a = ()               x = (conti ...)                 e = ()                   r = ()                 s = ((halt) () () ())
3. *conti*    a = ((nuate ...) ()) x = (argument ...)              e = ()                   r = ()                 s = ((halt) () () ())
4. *argument* a = ((nuate ...) ()) x = (close (frame ...) (apply)) e = ()                   r = (((nuate ...) ())) s = ((halt) () () ())
5. *close*    a = ((frame ...) ()) x = (apply)                     e = ()                   r = (((nuate ...) ())) s = ((halt) () () ())
6. *apply*    a = ((frame ...) ()) x = (frame ...)                 e = ((((nuate ...) ()))) r = ()                 s = ((halt) () () ())

7. *frame*    a = ((frame ...) ()) x = (constant #f ...)           e = ((((nuate ...) ()))) r = ()                 s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
8. *constant* a = #f               x = (argument ...)              e = ((((nuate ...) ()))) r = ()                 s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
9. *argument* a = #f               x = (refer (0 . 0) ...)         e = ((((nuate ...) ()))) r = (#f)               s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
10.*refer*    a = ((nuate ...) ()) x = (apply)                     e = ((((nuate ...) ()))) r = (#f)               s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
11.*apply*    a = ((nuate ...) ()) x = (nuate ...)                 e = ((#f))               r = ()                 s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))

12.*nuate*    a = #f               x = (return)                    e = ((#f))               r = ()                 s = ((halt) () () ())
13.*return*   a = #f               x = (halt)                      e = ()                   r = ()                 s = ()
14.*halt*     計算結果a=#fを返す

クロージャオブジェクトが命令と定義時の環境のセットを格納していること, 継続オブジェクトはスタックを復元する命令を含むクロージャオブジェクトであること が分かります. ヒープベースでは,この第一級関数も第一級継続もそんなに難しくなく実装できそうです. ここまで読む人なんていないか. スタックベースに進もう.

参考


comments powered by Disqus < piでベアメタルプログラミング 3imp 4.1 スタックベース >