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

レジスタ

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

コールフレーム

1
2
3
4
5
6
7
静的リンク(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, 動的リンクが取り出せる
    • これでフレームを消して,動的リンク元のフレームに戻る

1
2
3
((lambda (x y) (x y))
  (lambda (x) (if x 10 20))
  #f)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
(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
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
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を返す