[scheme][メモ]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)))))))

シンボル集合のリストによる安直実装

毎度ながら、 内容の薄い懐古趣味を一席。
K. Dybvig Three Implementation Models for Scheme, 1987 (以下、 3imp) では、 手続きをフラット・クロージャコンパイルするのに、 自由変数と束縛変数の集合演算を用います。 その集合演算には、 リストによる安直実装が例示してあります。 3imp の set-union 関数と set-intersect 関数を転載してみます。 記法は私好みに修正してあります。

; 3imp 93 page より転載。
(define (set-member? x U)       ; x ∈ U
 (cond
  ((null? U) #f)
  ((eq? x (car U)) #t)
  (else (set-member? x (cdr U)))))

(define (set-cons x U)          ; {x} ∪ U
 (if (set-member? x U)
  U
  (cons x U)))

; (set-union '(a b c d e) '(b d f g h)) => (e c a b d f g h)
(define (set-union U1 U2)       ; U1 ∪ U2
 (if (null? U1)
  U2
  (set-union (cdr U1) (set-cons (car U1) U2))))

; (set-intersect '(a b c d e) '(b d f g h)) => (b d)
(define (set-intersect U1 U2)   ; U1 ∩ U2
 (cond
  ((null? U1) '())
  ((set-member? (car U1) U2) (cons (car U1) (set-intersect (cdr U1) U2)))
  (else (set-intersect (cdr U1) U2))))

set-union 関数は末尾呼び出しのループで、 set-intersect 関数は非末尾呼び出しで書いてあります。 set-union の実行例で、 U2 の前に U1 にしか含まれない要素が U1 の出現順の逆にならんでいるのは、 ループで書いているためです。 一方、 set-intersect では再帰呼び出しの結果を cons するので U1 中の出現順に並びます。
本来、 set-union 関数と set-intersect 関数は、 両方とも同じ流儀で記述できるはずです。 書き直してみましょう。 まず、 数学による定義から直訳し、 set-union 関数を非末尾呼び出しで書いてみます。 3imp の set-intersect はこちらに属すので略します。

; (set-union '(a b c d e) '(b d f g h)) => (a c e b d f g h)
(define (set-union U1 U2)
 (cond
  ((null? U1) U2)
  ((set-member? (car U1) U2) (set-union (cdr U1) U2))
  (else (cons (car U1) (set-union (cdr U1) U2)))))

非末尾呼び出しでは、 U1 中の出現順に並べた結果が得られます。 ですが、 集合ですから、 要素の並び順は関係ありません。 末尾呼び出しで蓄積変数へ cons することで、 逆順の結果にしても平気です。

; (set-union '(a b c d e) '(b d f g h)) => (e c a b d f g h)
(define (set-union U1 U2)
 (let loop ((U1 U1) (U2 U2) (V U2))
  (cond
   ((null? U1) V)
   ((set-member? (car U1) U2) (loop (cdr U1) U2 V))
   (else (loop (cdr U1) U2 (cons (car U1) V))))))

; (set-intersect '(a b c d e) '(b d f g h)) => (d b)
(define (set-intersect U1 U2)
 (let loop ((U1 U1) (U2 U2) (V '()))
  (cond
   ((null? U1) V)
   ((set-member? (car U1) U2) (loop (cdr U1) U2 (cons (car U1) V)))
   (else (loop (cdr U1) U2 V)))))

3imp の set-union はこちらに属していますが、 set-cons を展開して表記を上に揃えると蓄積変数をケチっていることがわかります。 そのため、 set-member? で先頭側に付け加えた一致するはずがない要素との比較が生じてしまい、 最遅ケースが蓄積変数を使うよりも遅くなります。

; 3imp の set-union に set-cons を展開したもの
(define (set-union U1 U2)
 (cond
  ((null? U1) U2)
  ((set-member? (car U1)) (set-union (cdr U1) U2))
  (else (set-union (cdr U1) (cons (car U1) U2)))))

おまけで、 3imp が破壊操作する自由変数を探すのに使う set-minus 関数も、 set-intersect と同じ流儀の非末尾呼び出しで書いてあります。 これも、 蓄積変数を使った末尾呼び出しで書き直すことができます。

; (set-minus '(a b c d e) '(b d f g)) => (e c a)
(define (set-minus U1 U2)
 (let loop ((U1 U1) (U2 U2) (V '()))
  (cond
   ((null? U1) V)
   ((set-member? (car U1) U2) (loop (cdr U1) U2 V))
   (else (loop (cdr U1) U2 (cons (car U1) V))))))

流儀を統一しておいた方が美しかっただろうとは思えます。 3imp が流儀を統一していないのは、 末尾呼び出しでもそうでなくても、 どちらでも集合演算が記述できるどころか、 流儀を混ぜて使っても平気なことを示すため、 という深淵なる思慮があったのかもしれません。 ま。 でも、 末尾呼び出し流儀では、 蓄積変数ぐらいは使って欲しかったと思ったりしたのでした。

赤黒木による順序付き集合

Guy E. Blelloch, et. al., "Just Join for Parallel Ordered Sets" (2016) のアルゴリズムruby に直訳することで、 赤黒木の非破壊 join 関数で順序付き集合演算を書いていきます。

join 関数は既に見たように、 2本の木の間にキーをはさんで新しい木を求める働きをします。 この関数は、 左側の木に含まれるすべてのキーは新しくはさみたいキーよりも小さく、 右側の木に含まれるすべてのキーは大きいことを、 前提にしていました。 この前提があるため、 join 関数はキーの大小関係は事前に解決済みとして、 バランス崩れの調整に専念できていました。

join 関数がうまく動作するには、 あらかじめ指定したキーよりも小さなキーだけを含む木と、 大きなキーだけを含む木に分割しておく必要があります。 その機能を提供するのが、 split 関数です。 指定したキーとの大小比較をおこないながら、 木を根から葉へと降りていき、 見つからなかったときも見つかったときも根へ戻りながら、 指定したキーよりも小さなキーを含む木と大きなキーを含む木それぞれを join 関数を使って組み立てます。 この関数は、 3 つの値の組を返します。 組の先頭に小さなキーだけを含む木、 中央にキーを含んでいるかどうかを示す真偽値、 組の最後に大きなキーだけを含む木が入ります。

  def split(tree, key)
    if tree.null?
      [NULL, false, NULL]
    else
      if key == tree.key
        [tree.left, true, tree.right]
      elsif key < tree.key
        tree_prime_ll, b, tree_prime_lr = split(tree.left, key)
        [tree_prime_ll, b, join(tree_prime_lr, tree.key, tree.right)]
      else
        tree_prime_rl, b, tree_prime_rr = split(tree.right, key)
        [join(tree.left, tree.key, tree_prime_rl), b, tree_prime_rr]
      end
    end
  end

split 関数でキーからの大小で分割した 2 本の木の間にキーをはさんで join すると挿入したことになります。

  def insert_into_tree(tree, key)
    tree_prime_left, _, tree_prime_right = split(tree, key)
    join(tree_prime_left, key, tree_prime_right)
  end

2 本の木のうち、 一方に含まれるキーを木の入れ子構造を辿りながら、 もう一方をそのキーで分割し、 それぞれに再帰的に挿入をおこなっていくと、 両方の木に含まれるすべてのキーをもつ木を効率良く作ることができます。

  def union_tree(tree1, tree2)
    if tree1.null?
      tree2
    elsif tree2.null?
      tree1
    else
      left1, _, right1 = split(tree1, tree2.key)
      tree_left = union_tree(left1, tree2.left)
      tree_right = union_tree(right1, tree2.right)
      join(tree_left, tree2.key, tree_right)
    end
  end

木からキーを削除した新しい木を作るには、 split 関数で分割した 2 本の木を間にキーを挟まずに連結しなければなりません。

  def delete_from_tree(tree, key)
    tree_left, _, tree_right = split(tree, key)
    join2(tree_left, tree_right)
  end

一方、 join 関数は必ず間にはさむキーを必要とします。 そのため、 左側の木から最右側のキーを取り除いた木、 取り除かれた最右側のキー、 右側の木を join 関数で連結することにします。

  def join2(tree_left, tree_right)
    if tree_left.null?
      tree_right
    else
      tree_prime_left, key_last = split_last(tree_left)
      join(tree_prime_left, key_last, tree_right)
    end
  end

左側の木を、 最右側のキーを取り除いた木と最右側のキーに分けるには、 左側の最右の葉の直上まで降りて、 join 関数で最右側のキーを取り除いた木のバランスを調整します。

  def split_last(tree)
    if tree.right.null?
      [tree.left, tree.key]
    else
      tree_prime_right, key_last = split_last(tree.right)
      [join(tree.left, tree.key, tree_prime_right), key_last]
    end
  end

このように、 キーを削除するのに、 split 関数を使って指定したキーの前後で木を分割し、 分割した左側の木をさらに最右キーとそれ以外の木に分割し、 指定したキー以外を join 関数で連結しています。 このやりかたは、 2分探索木でキーを削除するときの方法と同じで、 それを join 関数を使って書き直したわけです。

join2 関数を使うことで、 tree1 から tree2 に含まれるキーを取り除く関数を作れます。 tree2 の入れ子構造に従い、 tree2 のキーで tree1 を分割し、 それぞれに再帰的に取り除きをおこなってから join2 関数で連結していきます。

  def difference_tree(tree1, tree2)
    if tree1.null?
      NULL
    elsif tree2.null?
      tree1
    else
      left1, _, right1 = split(tree1, tree2.key)
      tree_left = difference_tree(left1, tree2.left)
      tree_right = difference_tree(right1, tree2.right)
      join2(tree_left, tree_right)
    end
  end

tree1 と tree2 の両方に含まれるキーだけを抽出するには、 split 関数で求まる組の中央にキーが含まれているかどうかを表す真偽値を使います。 tree1 を tree2 のキーで分割し、 含まれているときだけ、 そのキーをはさんで連結し、 含まれないときはキーをはさまずに連結します。

  def intersect_tree(tree1, tree2)
    if tree1.null?
      NULL
    elsif tree2.null?
      NULL
    else
      left1, b, right1 = split(tree1, tree2.key)
      tree_left = intersect_tree(left1, tree2.left)
      tree_right = intersect_tree(right1, tree2.right)
      if b
        join(tree_left, tree2.key, tree_right)
      else
        join2(tree_left, tree_right)
      end
    end
  end