3imp ヒープ・ベース・コンパイラ/VM と CEK マシンの関係

Dybvig Three Implementation Models for Scheme (以下 3imp) のヒープ・ベース VM は、 VM だけでは CEK マシンから逸脱する動作もできてしまいますが、 コンパイラで CEK マシンに等価になるようにコード生成して制限をかけています。

複合手続きのアプリケーション評価を取り上げます。 CEK マシンでは 2 フェーズの状態遷移をおこなっていました。 式から継続を作成するフェーズと、 式評価の結果を継続に摘要するフェーズを交互に繰り返します。 アプリケーションの S 式を先頭から昇順に評価していく場合、 最初に得る式を継続メンバに記録してから実引数を評価してリストを作成していきます。 そして最後の実引数を評価してから apply フェーズへ移って、 実引数とクロージャの仮引数で新しい環境フレームを作ってクロージャの環境に追加して新しい環境を作ります。 それから、 できた新しい環境で手続き本体を評価します。

(M M1 M2 M3) E K
-> M  E (kfn (M1 M2 M3) E K)
     -> (kfn (M1 M2 M3) E K) (val (procedure Xf (Mf) Ef))
-> M1 E (kap    (M2 M3) E K (procedure Xf (Mf) Ef) ())
     -> (kap    (M2 M3) E K (procedure Xf (Mf) Ef) ())         (val a1)
-> M2 E (kap       (M3) E K (procedure Xf (Mf) Ef) (a1))
     -> (kap       (M3) E K (procedure Xf (Mf) Ef) (a1))       (val a2)
-> M3 E (kap         () E K (procedure Xf (Mf) Ef) (a1 a2))
     -> (kap         () E K (procedure Xf (Mf) Ef) (a1 a2))    (val a3)
     -> (kap         () E K (procedure Xf (Mf) Ef) (a1 a2 a3)) (apply)
-> Mf ((Xf . (a1 a2 a3)) . Ef) K

ところが、 Scheme は、 実引数をどのような順番で評価してもかまわないことになっているので、 実引数の最後から先頭へと逆順に評価しても良いわけです。 そうすることで、 引数のリストを cons で低コストに作れるようになりますし、 継続で手続きを覚えておく必要もなくなります。

(M M1 M2 M3) E K
-> M3 E (arg (M2 M1 M) E K         ())
     -> (arg (M2 M1 M) E K         ()) (val a3)
-> M2 E (arg    (M1 M) E K       (a3))
     -> (arg    (M1 M) E K       (a3)) (val a2)
-> M1 E (arg       (M) E K    (a2 a3))
     -> (arg       (M) E K    (a2 a3)) (val a1)
-> M  E (apply      () E K (a1 a2 a3))
     -> (apply      () E K (a1 a2 a3)) (val (procedure Xf (Mf) Ef))
-> Mf ((Xf . (a1 a2 a3)) . Ef) K

アプリケーションを逆順に書き直すなら、 ついでに継続でおこなう処理も一緒に書き込んでしまいます。 これで、 どの継続摘要をどのタイミングでおこなうべきかをコード化できるため、 評価を 1 フェーズでおこなえるようになります。

(M M1 M2 M3) E K
== M3      E (((arg) M2 (arg) M1 (arg) M (apply)) E K         ()) A
-> (arg)   E (      (M2 (arg) M1 (arg) M (apply)) E K         ()) (val a3)
-> M2      E (         ((arg) M1 (arg) M (apply)) E K       (a3)) (val a3)
-> (arg)   E (               (M1 (arg) M (apply)) E K       (a3)) (val a2)
-> M1      E (                  ((arg) M (apply)) E K    (a2 a3)) (val a2)
-> (arg)   E (                        (M (apply)) E K    (a2 a3)) (val a1)
-> M       E (                          ((apply)) E K (a1 a2 a3)) (val a1)
-> (apply) E (                                 () E K (a1 a2 a3)) (val (procedure Xf (Mf) Ef))
-> Mf ((Xf . (a1 a2 a3)) . Ef) K

だいぶ 3imp VM に近づきました。 さらに、 環境レジスタ e と実引数リスト r を書き換えるのは手続きを apply するときだけなので、 途中の M3、M2、M1、M がアプリケーションのときに限ってそれぞれで継続を作成するようコード化すると 3imp VM になります。

ところで、 3imp VM は CEK マシン用なので、 apply 命令はジャンプします。 そのため、 単に apply するだけで末尾ジャンプできます。 さらに、 ジャンプと同時にレジスタ r のリストを空にしておくことで、 ジャンプ先ですぐに実引数リストを作り始めることができるように工夫してあります。 なお、 arg は命令コードでは argument です。 さらに、 3imp VM入れ子リスト構造になっており、 そのままではとても読みにくいのでフラットに並べ替えたリストに書き直しておきます。

(M M1 M2 M3) e s r a
== (M3 (argument) M2 (argument) M1 (argument) M (apply)) e s         () a
->    ((argument) M2 (argument) M1 (argument) M (apply)) e s         () a3
->               (M2 (argument) M1 (argument) M (apply)) e s       (a3) a3
->                  ((argument) M1 (argument) M (apply)) e s       (a3) a2
->                             (M1 (argument) M (apply)) e s    (a2 a3) a2
->                                ((argument) M (apply)) e s    (a2 a3) a1
->                                           (M (apply)) e s (a1 a2 a3) a1
->                                             ((apply)) e s (a1 a2 a3) (procedure Xf (Mf) Ef)
->                             Mf ((Xf . (a1 a2 a3)) . Ef) s         () (procedure Xf (Mf) Ef)

まず継続作成が不要な簡単な場合から。 例えば、 M3、 M1、 M が定数か変数参照のときは、 環境レジスタ e も、 実引数リスト・レジスタ r も変化しません。 なので、 これらには継続作成は不要です。

(f 0 M2 10)
== ((constant 10) (argument) M2 (argument) (constant 0) (argument) (refer f) (apply))

M2 がアプリケーションのとき、 環境レジスタ e と実引数リスト・レジスタ r を上書きするので、 継続を作成する必要があります。 継続を作成する命令は frame の名称になっていて、 「すぐに実行する部」と「後で実行する部」の両方を指定します。 「後で実行する部」は M2 の評価結果を実引数リストへ加えるところから後半の部分すべてになります。 frame 命令の状態遷移はとても簡単です。 継続レジスタ s へ「後で実行する部」と 2 つのレジスタ e r の内容をセーブしてから、 r レジスタのリストを空にします。 そして「すぐに実行する部」の遷移を始めます。

M2 のアプリケーション評価が終わると、 どこかで継続摘要がおこなわれて、 frame で作成しておいた継続の遷移が始まります。 継続摘要をおこなう命令は return で、 定数評価の直後に挿入するのがパターンです。 また、 apply 命令でプリミティブ摘要をするときも、 return と同じ継続摘要をおこなうように遷移させます。

(f 0 (g x) 10)
== ((constant 10) (argument)
    (frame
      ((argument) (constant 0) (argument) (refer f) (apply))  ; 後で実行する部
      ((refer x) (argument) (refer g) (apply))))              ; すぐに実行する部

遷移

((frame C M)) e  s           r  a  ->  M e (C e r . s) () a
((return))    e' (C e r . s) r' a  ->  C e s           r  a

極端な話、 実引数の定数の評価に frame と return を挿入しても正しく動作しますが、 作成した継続を即座に廃棄するだけで、 こんなコードを生成するのは無駄です。

((frame
   ((argument) M2 (argument) (constant 0) (argument) (refer f) (apply))
   ((constant 10) (return))))

   ((frame C M))            e s              () a 
-> ((constant 10) (return)) e (C e () . s)   () a
-> ((return))               e (C e () . s)   () 10
-> ((argument) M2 ...)      e s              () 10
-> (M2 ...)                 e s            (10) 10