SICP 積極制御評価器と CEK マシンの関係

サスマン「計算機プログラムの構造と解釈 第二版」(以下 SICP) 5.4 節記載の Scheme積極制御評価器 (Creative Commons 版の翻訳)は、 いきなりレジスタ計算機のアセンブリのソースがずらずらと並んでいて見落としがちですけど、 CEK マシンを実装したものになっています。 というよりも、 時系列ではおそらく逆で、 この評価器や ML の評価器の動作を整理していった結果として、 CEK マシンへと至ったのが真相なのでしょう。

CEK マシンのレジスタとの対応関係を読み取ると、 K レジスタが参照する継続オブジェクトのメンバを頻繁に利用するため、 メンバをレジスタへ割り当ててあることがわかります。 レジスタ名や値の表記には、 SICP だけでなく、 Dybvig Three Implementation Models for Scheme (以下 3imp) のヒープベース VM との関係を見る目的も兼ねて、 3imp VMレジスタ表記にも一部合わせてあります。 ちなみに、 3imp ヒープベース VM は、 スタックベース VM への布石として、 あれはあれで興味深いものです。

レジスタ

              CEK マシン    3imp VM     積極制御評価器
                      C     x           exp
                      E     e           env
     K=(tag C E K fn R)     s           スタック
                  K.tag                 continue
                    K.C                 unev
                    K.K                 スタックを使ってリストにしていないのでなし。
                   K.fn     aが兼ねる   proc
                    K.R     r           args

              K (val a)     a           val

CEK マシンは 2 フェーズでλ関数を評価します。 最初のフェーズは CEK の 3 組で始まり、 評価対象の式 M を C レジスタに置いて状態遷移を開始します。 このフェーズが進み値 a が得られると次のフェーズに移り、 K レジスタの継続へ値を摘要します。 ここでは継続摘要を K (val a) と表記することにします。さらに、 積極制御評価器は apply フェーズを加えて 3 フェーズになっているので、 これも便宜的に K (apply) と書くことで apply フェーズに入ることを示すことにします。

最初の CEK で始まるフェーズは、 積極制御評価器の eval_dispatch ラベルで始まる箇所に相当します。 continue、unev、env レジスタをスタックへプッシュして、 それらを上書きする箇所で継続を成長させています。 継続摘要フェーズへ移るときは、 val レジスタに値を置いて、 continue レジスタの指すラベルへジャンプします。

a は定数 (数値、文字列、クロージャ・オブジェクト)
x はシンボル
M M+ M* X はリスト、  M* は () であっても良く、 M+ は (M . M*)

                             a E K  ->  K (val a)           ;(number? a)
                             a E K  ->  K (val a)           ;(string? a)
                     (quote a) E K  ->  K (val a) 
                             x E K  ->  K (val a)           ;a==(ref (varf x E))
               (lambda X . M+) E K  ->  K (val (procedure E X . M+))     ;注1
                    (set! x M) E K  ->  M E (kst x  E K)
                  (define x M) E K  ->  M E (kdf x  E K)
         (define (x . X) . M+) E K  ->  (lambda X . M+) E (kdf x E K)
                   (if M . M+) E K  ->  M E (kif M+ E K)
                     (begin M) E K  ->  M E K
                (begin M . M+) E K  ->  M E (ksq M+ E K)
                      (M . M*) E K  ->  M E (kfn M* E K)

注1: lambda 形式の本体 M+ に含まれる define 形式を letrec へ置き換える処理を
     おこなってからクロージャを作成する *べき* だが、 SICP の実装では省いてある。
     SICP 「4.1.6 内部定義」と「5.5.6 文面アドレス」参照。

継続適応フェーズの左辺は E レジスタに依存しないので省いています。 SICP では、 個々の遷移をラベルに分けて記述してあります。 その中での、 スタックへの save/restore 操作と状態遷移の K の変化がぴったりと一致しています。

  (kst x        E K) (val a)        ->  K (val OK)          ;(setf! (varf x E) a)
  (kdf x        E K) (val a)        ->  K (val OK)          ;(define-var x a E)
  (kif (M . M*) E K) (val a)        ->  M E K               ;a != #f
  (kif (M1 M)   E K) (val #f)       ->  M E K
  (kif (M1)     E K) (val #f)       ->  K (val #f)
  (ksq (M . M+) E K) (val a)        ->  M E (ksq M+ E K)
  (ksq (M)      E K) (val a)        ->  M E K
  (kfn (M . M*) E K) (val fn)       ->  M E (kap M* E K fn ())
  (kap (M . M*) E K fn R) (val a)   ->  M E (kap M* E K fn R1)
  (kfn ()       E K) (val fn)       ->  (kap () E K fn ()) (apply)
  (kap ()       E K fn R) (val a)   ->  (kap () E K fn R1) (apply)
                                                            ;R1==(append R (list a))

最後は apply フェーズです。 ここも左辺から E レジスタを省いています。 ラベルは apply-dispatch になっていて、 このフェーズは proc と args レジスタを使います。 プリミティブ摘要では val に計算結果を置いて、 continue にジャンプします。 アプリケーションではクロージャ・オブジェクトの環境にフレームをつないで env レジスタに置き、 CEK フェーズに入ります。

(kap () E' K (primitive op)         R) (apply)  ->  K (val (apply-primitive op R))
(kap () E' K (procedure E X M)      R) (apply)  ->  M ((X . R) . E) K
(kap () E' K (procedure E X M . M+) R) (apply)  ->  M #0=((X . R) . E) (ksq M+ #0# K)