3imp スタックベース compile/VM の begin 形式とクロージャ

2017 年 12 月 5 日追記 この稿の説明には勘違いが含まれています。 式の並びを入れ子 lambda に変換しなくても、 それぞれの式から求めた変数の集合の和集合を求めることで、 正しい集合を求めることができ、 必要な box 化をおこなうことができます。

Dybvig Three Implementation Models for Scheme (以下 3imp) でbegin 形式と lambda 形式の本体が並びのとき、 入れ子の lambda 形式へ変換するのは、 スタックベース compile のためです。 ヒープベース compile/VM では begin 形式と lambda 形式の本体が並びのときでも、 frame 命令を使ってコンパイルすれば良いだけだと前回説明しましたが、 スタックベース compile/VM では動作がおかしくなる場合が生じます。

3imp スタックベース VM は、 ヒープにスタックを作らず、 ベクタとスタック・ポインタでスタックを作り、 ローカル変数割り当てと読み書きを高速にしています。 その際、 手続き実行が終わると、 スタック・ポインタを戻してベクタ上の領域を上書きして再利用する方式をとっています。 しかも、 スタックに格納しているのは値であって、 左辺値は値を入れるアドレスで代用しています。 そのため、 手続きを作るには、 スタックから値をヒープに新しく確保した変数オブジェクトに移しておいて、 手続きには移した先の左辺値を書き込むと同時にスタックの内容も同じ左辺値に書き直さないといけません。 ヒープに作った変数オブジェクトのことを 3imp では box と名づけています。 その上で、 VM では既に box になっている変数はその左辺値を手続きへ移す動作をするので、 一つの変数に対してすべての手続きで同じ左辺値を共用できるようになります。

もしも 3imp のスタックベース VM が手続きを作るときに常に box に置き換えるならば、 話は簡単でした。 この場合は、 並びを入れ子 lambda 形式に変換する必要はありません。 問題は、 効率化のために、 lambda 形式内で set! しない自由変数に対して box を作らずに値を手続きへコピーするコードに compile することです。 そのため、 束縛変数であっても、 並びの後ろの方で set! しているなら、 自由変数に set! していると compile が判断できなければいけません。

例えば、 次の例では x を box にして外側と内側で左辺値を共用する必要があります。

(lambda (a b c x y)
  (set! a (lambda (z) (cons x y)))
  (set! x b)
  (c x y))

ここで、 並びを入れ子の lambda 形式へ変換すると、変換前の束縛変数は変換後の lambda 形式にとっては自由変数になります。 これで、 スタックベース compile は束縛変数であっても set! されているものを box へ置き換える VM コードを事前に生成できます。

上の例を入れ子 lambda 形式へ変換すると、 内側に 2 つの lambda 形式ができ、 x が set! されている自由変数になり、 y は参照だけの自由変数になります。

(lambda (a b c x y)
  ((lambda (t)                         ; この lambda 形式の自由変数は b c x y、 x にセットしているので x を box にする 
    ((lambda (t)                       ; この lambda 形式の自由変数は c x y、 x は既に box なので左辺値をコピーする
        (c x y))
      (set! x b)))
    (set! a (lambda (z) (cons x y))))) ; この lambda 形式の自由変数は x y、 x は既に box なので左辺値をコピーする

これで、 x は外側と内側の両方の lambda 形式で box への左辺値へ変化します。

            a  b  c    y                b  c    y                c    y                  y
 スタック #(値 値 値 x 値)     手続き #(値 値 x 値)     手続き #(値 x 値)     手続き #(x 値)
                     |                        |                     |                  |
                     +------------------------+---------------------+------------------+--->(box . 値)