CEK マシンな SICP Scheme 評価器 (その4)

Flanagan 等の論文の図 2 の CEK マシンで、Core Scheme の let と手続き適用の状態遷移がそれぞれ別に定義してあるのは Scheme よりも ML 系統のプログラミング言語を念頭に置いているのだろうと考えていたのですけど、実際に CEK マシンとして Scheme 評価器を書いてみると、そうではなくて Scheme の場合も let の状態遷移はシーケンスの評価のためにあるのではなかろうかという気がしてきました。どうでもいいといえばいいのでしょうけど、Scheme の let と名前が衝突しているため、 まぎらわしいので以降では Flanagan 等 の Core Scheme の let をここでは let1 と書くことにします。

シーケンスの状態遷移と let1 の状態遷移は良く似ています。let1 は次のように遷移します。

(let1 (x M1) M2) E K -> M1 E (lt x M2 E . K) -> (Rt v1) E' (lt x M2 E . K) -> M2 E{x:=v1} K

一方、式が 2 つのシーケンスは次のように遷移します。

(begin M1 M2) E K -> M1 E (begin (M2) nil E . K) -> (Rt v1) E' (begin (M2) nil E . K) -> M2 E K

これを次のように書き直すと、let1 の変数束縛をバイパスした状態遷移に対応しています。

(begin M1 M2) E K -> M1 E (lt _ M2 E . K) -> (Rt v1) E' (lt _ M2 E . K) -> M2 E K

このことから、シーケンスは変数束縛をバイパス可能な入れ子の let1 へ展開できることがわかります。バイパス指定は、上のように _ と書いてもいいでしょうし、いっそのこと nil でもいいのではないでしょうか。展開のパターンは次のようになるのでしょう。

(begin) => 'nil
(begin M1) => M1
(begin M1 M2) => (let1 (nil M1) M2)
(begin M1 M2 M3) => (let1 (nil M1) (let1 (nil M2) M3))
(begin M1 M2 M3 M4) => (let1 (nil M1) (let1 (nil M2) (let1 (nil M3) M4)))
...

パターンにしたがって、展開ルーチンを書いてみます。

LET1 = Atom['let1']

def expand_begin(exp) expand_sequence(exp.last) end

def expand_sequence(exp)
  if ! pair?(exp)
    list(QUOTE, nil)
  else
    list_enum(exp).reverse_each.inject(nil) {|m, x|
      m ? list(LET1, list(nil, x), m) : x
    }
  end
end

lambda 形式では、上の展開ルーチンを使って body を展開します。

def scanout_lambda(exp)
  parameters = list_enum(exp.last.first).inject([]) {|a, t| a << t }
  body = exp.last.last
  body1 = list_enum(body).reverse_each.inject(body) {|b, x|
    if pair?(x) and x.first == DEFINITION
      v = symbol?(x.last.first) ? x.last.first : x.last.first.first
      cons(list(DEFINITION, v, list(QUOTE, UNBOUND)), b)
    else
      b
    end
  }
  cons(LAMBDA, cons(parameters, expand_sequence(body1)))
end

let と letrec は元のまま lambda 形式へ展開しますが、let* は let1 へ展開した方が簡潔になります。

def expand_letstar(exp)
  bindings = exp.last.first
  body = expand_sequence(exp.last.last)
  list_enum(bindings).reverse_each.inject(body) {|m, x|
    list(LET1, list(x.first, x.last.first), m)
  }
end

cond も let1 を使って展開するように書き直せます。

def expand_cond(exp)
  return false if exp.last.nil?
  clause = exp.last.first
  rest = exp.last.last
  if clause.first == ELSE
    rest.nil? or raise SyntaxError, "ELSE clause isn't last -- EXPAND-COND"
    clause.last.nil? ? false : seq_to_exp(clause.last)
  elsif pair?(clause.last) && clause.last.first != THENPASS
    list(IF, clause.first, seq_to_exp(clause.last), expand_cond(exp.last))
  else
    t = Atom.new('t')   # gensym
    list(LET1, list(t, clause.first),
      list(IF, t,
        (if ! pair?(clause.last)
         then t
         else list(clause.last.last.first, t)   # THENPASS
         end),
        expand_cond(exp.last)))
  end
end

def seq_to_exp(seq)
  if seq.nil?
    seq
  elsif seq.last.nil?
    seq.first
  else
    expand_sequence(seq)
  end
end

CEK の状態遷移からシーケンスのものを外して let1 用に変えるなら、 or と and も展開するようにしないといけないでしょう。or は let1 と if の入れ子で、and は if の入れ子に展開できます。

def expand_or(exp)
  if ! pair?(exp.last)
    list(QUOTE, false)
  else
    list_enum(exp.last).reverse_each.inject(nil) {|m, x|
      if m.nil?
        x
      else
        t = Atom.new('t')
        list(LET1, list(t, x), list(IF, t, t, m))
      end
    }
  end
end

def expand_and(exp)
  if ! pair?(exp.last)
    list(QUOTE, true)
  else
    list_enum(exp.last).reverse_each.inject(nil) {|m, x|
      m ? list(IF, x, m) : x
    }
  end
end

これで CEK の状態遷移を書き直します。SEQUENCE、AND、OR の状態遷移を継続のものともども削除して、LET1 の状態遷移にさしかえます。また AP の状態遷移もシーケンスを使わないように書き直します。

SYNTAX_EXPANDER = {
  SEQUENCE => :expand_begin,
  LET => :expand_let,
  LETREC => :expand_letrec,
  LETSTAR => :expand_letstar,
  COND => :expand_cond,
  OR => :expand_or,
  AND => :expand_and,
}

def cek_eval(exp, env)
    case c
    when Pair
      case c.first
      when LET1 # (let1 (x m1) m2)
        c1 = c.last.first.last.first
        k1 = [LET1, c.last.first.first, c.last.last.first, e, k]
        c, e, k = c1, e, k1
    when Rt
      case k.first
      when LET1
        v1 = c.x
        x1, c1, e1, k1 = k[1], k[2], k[3], k[4]
        e1 = Pair.new([[x1, v1]], e1) if symbol?(x1)
        c, e, k = c1, e1, k1
      when :AP
        ap = k[1] + [c.x]
        c1, e1, k1 = k[2], k[3], k[4]
        if pair?(c1)
          c2 = c1.first
          k2 = [:AP, ap, c1.last, e1, k1]
          c, e, k = c2, e1, k2
        else
          operator = ap.shift
          case operator
          when Primitive
            c2 = Rt.new(__send__(operator.op, *ap))
            c, e, k = c2, e1, k1
          when Procedure
            m = operator.m
            c2 = m
            e2 = Pair.new(operator.x.zip(ap), operator.e)
            c, e, k = c2, e2, k1
          else
            raise "eval: unknown operator #{operator.inspect}"
          end
        end
      end
    end
end

シーケンスを let1 に展開するようにするだけで、 Core Scheme の状態遷移にだいぶ近づきました。set! と define、プリミティブ適用に違いが残っていますが、set! と define は継続で環境を操作することと、プリミティブかどうかは変数を参照しない限り決定しないため、これらの違いは残したままにすることにします。