3impのchap4.1の備忘録です． schemeから，第一級関数，継続，末尾最適化を取り除いた簡単な例です．

レジスタ

a: accumulator，汎用的に使う
x: 次の命令
e: 一つ外側のスコープのフレーム
s: スタックトップ

コールフレーム

静的リンク(pushed last)
1st argument
  :
  :
last argument
next expression(返りアドレス)
動的リンク(pushed last)

命令

継続はないから，conti,nuateはない．

  • (halt)
    • VMをhaltする．
    • accumulatorの値を結果とする
  • (refer n m x)
    • 静的リンクをたどる
    • n…現在のフレームからのオフセット
  • (constant obj x)
    • 定数objをaccumulatorにつっこみ，xをセット
  • (close vars body x)
    • functionalを作る
  • (test then else)
    • accumulatorがnullかどうかチェックし，nextかelseをnext expressionにセットする．
  • (assign var x)
    • varにaccumulatorを束縛
    • 次の式をxにセットする．
  • (frame x ret)
    • 動的リンクとretからフレームの土台を作る
  • (argument x)
    • accumulatorの値をスタックにプッシュ
    • 次の式をxにセットする．
  • (apply)
    • 静的リンクを取り出して，プッシュ
    • 次の式をclosure本体にする．
    • この時点でフレームが完成する
  • (return n)
    • 動的リンクとnext expressionを除いたフレームのサイズ
    • つまりフレームトップからnを引くと，next expression, 動的リンクが取り出せる
    • これでフレームを消して，動的リンク元のフレームに戻る

例

((lambda (x y) (x y))
  (lambda (x) (if x 10 20))
  #f)

(frame (halt) 
       (constant
          #f 
          (argument
            (close
              (refer 0 0 (test (constant 10 (return 2)) (constant 20 (return 2))))
              (argument
                (close 
                  (frame (return 3) (refer 0 1 (argument (refer 0 0 (apply)))))
                  (apply)))))))

1. frame (halt)

    s=2 -> |     (halt)      |  ret先
           |     0           |  動的リンクe
    e=0 -> |-----------------|

2. constant #f
    
    a = #f

3. argument (close ...

    s=3 -> |    #f           |  第2引数
           |    (halt)       |  ret先
           |    0            |  動的リンクe
    e=0 -> |-----------------|
    
4. close (refer 0 0 ...

    a = ( (refer 0 0 ...) 0 )   本体とリンクの集まり

5. argument

    s=4 -> |((refer00...) 0) |  第1引数
           |  #f             |  第2引数
           |  (halt)         |  ret先
           |  0              |  動的リンクe
    e=0 -> |-----------------|

6. close (frame (return 3) ...

    a = ( (frame (return 3) ...) 0)

7. apply

    s=3 -> |   0             |  静的リンクe (クロージャの定義の環境)
    e=4 -> |((refer00...) 0) |  第1引数
           |  #f             |  第2引数
           |  (halt)         |  ret先
           |  0              |  動的リンクe
   _e=0 -> |-----------------|

8. frame (return 3) ...

    s=7 -> | (return 3)      |  ret先
           |   4             |  動的リンクe

           |   0             |  静的リンクe (クロージャの定義の環境)
    e=4 -> |((refer00...) 0) |  第1引数
           |  #f             |  第2引数
           |  (halt)         |  ret先
           |  0              |  動的リンクe
   _e=0 -> |-----------------|

9. refer 0 1

    a = (index e 1) = #f

10. argument (refer 0 0

    s=8 -> | #f              |  第1引数
           | (return 3)      |  ret先
           |   4             |  動的リンクe

           |   0             |  静的リンクe (クロージャの定義の環境)
    e=4 -> |((refer00...) 0) |  第1引数
           |  #f             |  第2引数
           |  (halt)         |  ret先
           |  0              |  動的リンクe
   _e=0 -> |-----------------|

11. refer 0 0 (apply

    a = (index e 0) = ((refer00...) 0)

12. apply

    s=9 -> |  0              |  静的リンクe
    e=8 -> | #f              |  第1引数
           | (return 3)      |  ret先
           |   4             |  動的リンクe

           |   0             |  静的リンクe (クロージャの定義の環境)
  _e=4 ->  |((refer00...) 0) |  第1引数
           |  #f             |  第2引数
           |  (halt)         |  ret先
           |  0              |  動的リンクe
   _e=0 -> |-----------------|

13. refer 0 0 (test

  a = #f

14. test

  x = (constant 20 ...)

15. constant 20

  a = 20

16. return 2

    s=5 -> |   0             |  静的リンクe (クロージャの定義の環境)
    e=4 -> |((refer00...) 0) |  第1引数
           |  #f             |  第2引数
           |  (halt)         |  ret先
           |  0              |  動的リンクe
   _e=0 -> |-----------------|

17. return 3

  s,e=0 -> |-----------------|

18. halt

  レジスタaの20を返す