簡易アセンブリの相対ラベル

正規表現構文解析器の仮想マシンをいじって遊びたいとき、 簡易アセンブリを使えるようにしておきたくなります。 例えば、 Russ Cox の RE1 仮想マシン相当のアセンブリで、 命令列を直打ちするには次のようにするとしましょう。 ラベルと命令コードを Symbol インスタンスとして、 split や jmp 命令のオペランドになるアドレスをラベルで指定できるようにしておきます。

program = asm [
# (a+)(b+)
      :save,  2,
:L1,  :char,  'a',
      :split, :L1, :L2,
:L2,  :save,  3,
      :save,  4,
:L3,  :char,  'b',
      :split, :L3, :L4,
:L4,  :save,  5,
      :match,
]
#=> [[:save, 2],
#    [:char, "a"],
#    [:split, 1, 3],
#    [:save, 3],
#    [:save, 4],
#    [:char, "b"],
#    [:split, 5, 7],
#    [:save, 5],
#    [:match]]

話を単純にするため、 入れ子の配列へアセンブルし、 split や jmp 命令のオペランドを配列の添字で表した絶対アドレスで扱うことにします。

ところで、 この手のコードでは局所的なアドレス参照が圧倒的に多いため、 命令の直前にあるラベル、 もしくは直後のラベル、 みたいな記述が利用できると、 さらに楽になるでしょう。 例えば、 D. Knuth の MIX アセンブリでは、 整数ラベルを利用でき、 オペランド B1 だと直前の整数ラベル 1 を、 オペランド F1 だと直後のラベル 1 を参照することができるようになっています。 同様のラベルは GNU アセンブリ (gas) でも利用できます。

program = asm [
# (a+)(b+)
      :save,  2,
1,    :char,  'a',
      :split, :B1, :F1,
1,    :save,  3,
      :save,  4,
1,    :char,  'b',
      :split, :B1, :F1,
1,    :save,  5,
      :match,
]

整数ラベルは何度も登場することができるため、 ラベルの定義位置のアドレスの配列にしておくのが自然でしょう。 ラベル定義位置を dic ハッシュに入れることにすると、 上の場合は、 次のようになっているものとします。

dic = {
  1 => [1, 3, 5, 7],
}

命令を格納するアドレスを dot で現すものとしましょう。 すると、 最初の split 命令の dot は 2 です。 この命令のオペランドは B1 と F1 となっています。 B1 に対応するラベル 1 のアドレスは 1 であり、 F1 に対応するラベル 1 のアドレスは 3 です。 このように、 dot アドレスにある命令のオペランドのアドレスを求めるには、 B1 に対して、 dic のラベル 1 の配列の中で、 dot 未満のアドレス集合 (1) の中から最大値 1 を選びます。 F1 に対して、 dot より大きなアドレス集合 (3, 5, 7) の中から最小値 3 を選びます。

素朴にラベルのアドレス解決手続きを記述すると、 このようになります。 なお、 オペランドが F1 や B1 以外のシンボル L1 等だったときは、 dic ハッシュにそのまま L1 からアドレスが関連付けされているものとしましょう。

def asm_addr(dic, operand, dot)
  if Symbol === operand
    if %r/\AB(\d+)\z/ =~ operand.to_s
      dic[$1.to_i]&.select {|x| x < dot }&.max
    elsif %r/\AF(\d+)\z/ =~ operand.to_s
      dic[$1.to_i]&.select {|x| x > dot }&.min
    else
      dic[operand]
    end or raise "label #{operand} not found"
  else
    operand
  end
end

同じ数値ラベルを多く使うことを考慮すると、 もう少し工夫したくなってきます。 数値ラベルに dic で関連付けしてあるアドレスの配列が昇順だとして、 二分探索を使いましょう。 F1 のような、 dot より大きなうちから最小値を探すのは bsearch の動きそのものなので、 簡単です。 一方、 B1 のような、 dot より小さなうちから最大値を探すには、 少し工夫が必要です。 まず、 dot 以上のうちの最小値の位置を bsearch_index で見つけます。 見つからないときは、 配列サイズを位置にしておきます。 そして、 この見つけた位置の一つ前に、 求めたいアドレスが入っているはずです。

def asm_addr(dic, operand, dot)
  if Symbol === operand
    if %r/\AB(\d+)\z/ =~ operand.to_s
      ary = dic[$1.to_i] \
      and i = ary.bsearch_index {|x| x >= dot } || ary.size \
      and i > 0 and ary[i - 1]
    elsif %r/\AF(\d+)\z/ =~ operand.to_s
      dic[$1.to_i]&.bsearch {|x| x > dot }
    else
      dic[operand]
    end or raise "label #{operand} not found"
  else
    operand
  end
end

アセンブリは 2 パスで書いておきます。

パス 1 では、 命令を生成せずに、 すべてのラベルにアドレスを関連付けします。 ニモニックとオペランドを読み飛ばし、 ラベルへのアドレスを登録していきます。 整数ラベルは配列にアドレスを順に格納していき、 シンボル・ラベルはそのままアドレスに関連付けます。

def asm_pass1(src, dic, dot)
  sp = 0
  while sp < src.size
    case src[sp]
    when :char, :save, :jmp
      dot += 1
      sp += 2
    when :match
      dot += 1
      sp += 1
    when :split
      dot += 1
      sp += 3
    when Integer
      n = src[sp]
      dic[n] ||= []
      dic[n] << dot
      sp += 1
    when Symbol
      sym = src[sp]
      dic[sym] = dot
      sp += 1
    else
      raise "invalid source"
    end
  end
end

パス 2 では、 dic を使って、 命令を生成します。 ラベルを読み飛ばし、 オペランドを dic を使ってアドレスを解決し、 ニモニックと合わせて命令を作ります。

def asm_pass2(src, dic, program)
  sp = 0
  while sp < src.size
    case src[sp]
    when :char, :save
      program << [src[sp], src[sp + 1]]
      sp += 2
    when :match
      program << [src[sp]]
      sp += 1
    when :jmp
      x = asm_addr(dic, src[sp + 1], program.size)
      program << [src[sp], x]
      sp += 2
    when :split
      x = asm_addr(dic, src[sp + 1], program.size)
      y = asm_addr(dic, src[sp + 2], program.size)
      program << [src[sp], x, y]
      sp += 3
    when Integer, Symbol
      sp += 1
    end
  end
  program
end

asm は両方のパスを順に実行します。

def asm(src)
  dic = {}
  asm_pass1(src, dic, 0)
  asm_pass2(src, dic, [])
end

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