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

3 年経て改めて考えてみたところ、 無駄と切り捨てたのが、 CEK マシンの素のそれだと、 今頃になって気がついたので、 自己ツッコミ。 なお、 いつものように慣例に合わせて、 R. K. Dybvig, Three Implementation Models for Scheme (1987) を 3imp と略します。

3imp ヒープ・ベース VM と CEK マシン
作成した継続を即座に廃棄するだけで、 こんなコードを生成するのは無駄です。

; 3imp の入れ子リスト表記に戻してます。
(frame (argument (M2 (argument (constant 0 (argument (refer f (apply)))))))
       (constant 10 (return)))

    a ()           (frame C2 C1)) E K
->  a ()   (constant 10 (return)) E (() C2 E K)
-> 10 ()                (return)  E (() C2 E K)
-> 10 ()      (argument (M2 ...)) E k
-> 10 (10)              (M2 ...)  E k

そもそも論として、 継続渡しスタイル (CPS: continuation passing style) の評価器を状態遷移機械に翻訳したものが CEK マシンに相当します。 ですので、 基本に立ち返るには、 超循環評価器で定数や変数参照をどう扱っていたかを思い出すことです。

(define (eval control environment continuation)
 (cond
  ((self-evaluating? control) (continuation control))
  ((quoted? control) (continuation (text-of-quotation control)))
  ((variable? control) (continuation (lookup-variable-value control environment)))
  ((lambda? control)
   (continuation (make-compound-procedure (lambda-parameters control)
                                          (lambda-body control)
                                          environment)))
  ...))

すると、 定数・参照・関数閉包は、 適用で記述することになります (単純化して継続の引数は単値とします)。 さて、 3imp ヒープ・ベース VM での評価値の適用は、 評価値をレジスタ a に置いて return 命令を実行します。 ゆえに、 これらに return 命令を付けたものこそが、 素の CEK マシンとしてふるまうと言えます。

   a       r' (constant V (return)) E' (r C E K)
-> V       r'             (return)  E' (r C E K)
-> V       r                     C  E  K

   a       r'    (refer x (return)) E' (r C E K)
-> E'[x]   r'             (return)  E' (r C E K)
-> E'[x]   r                     C  E  K

   a       r'   (close C' (return)) E' (r C E K)
-> (C' E') r'             (return)  E' (r C E K)
-> (C' E') r                     C  E  K

しかしながら、 原則にこだわりすぎると効率が劣るため、 refer 命令等を return の動作を含む CEK マシン流儀で定義せず、 SECD マシン流儀で定義してあるのでしょう。 SECD マシン流儀に最適化できるのは、 冒頭の frame 命令との組み合わせるパターンに限り、 それ以外では CEK マシン流儀に return 付きへコンパイルするのが妥当でしょう。 実際、 3imp のコンパイラはそのように動作します。

余談ながら、 やはり frame 命令は読みにくいので嫌になります。 (frame C2 C1) 命令は、 ((lambda (a) C2) C1) に由来していました。 ですが、 等価な (let ((a C1)) C2) で書いた方が読みやすくなるのは容易に想像できます。 そこで、 ダジャレで (letme C1 C2) 命令をでっち上げてコードを記述することにしましょう。

;   a r (frame C2 C1) E K -> a () C1 E (r C2 E K)
;   a r (letme C1 C2) E K -> a () C1 E (r C2 E K)

; (if (= n 0) r (factorial (- n 1) (* n r))) を 
; CEK マシン流儀でコンパイル
(letme (letme (constant 0 (return))
        (argument
         (letme (refer n (return))
          (argument
           (letme (refer = (return))
            (apply))))))
 (test
  (refer r (return))
  (letme (letme (constant 1 (return))
          (argument
           (letme (refer n (return))
            (argument
             (letme (refer - (return))
              (apply))))))
   (argument
    (let (letme (refer r (return))
            (argument
             (letme (refer n (return))
              (argument
               (letme (refer * (return))
                (apply))))))
     (argument
      (letme (refer factorial (return))
       (apply))))))))

; (letme (refer x (return)) C) を (refer x C) に最適化すると
(letme (constant 0 (argument (refer n (argument (refer = (apply))))))
 (test
  (refer r (return))
  (letme (constant 1 (argument (refer n (argument (refer - (apply))))))
   (argument
    (letme (refer r (argument (refer n (argument (refer * (apply))))))
     (argument
      (apply)))))))