アンダースタンディング コンピュテーション 2

ucrubyprogrammingbook

Posted onOct 17, 2014


変数を使えるようにする

変数を簡約するために、変数名から値へのマッピングとして環境を導入する。

$$\langle x, \sigma \rangle \rightsquigarrow_e \sigma(x)\ if\ x \in dom(\sigma)$$

実装は Hash を使うだけ。

class Variable < Struct.new(:name)
  def reduce(environment)
    environment[name]
  end
end

そして簡約できる項の #reduce に環境を渡せるようにする。

たとえば足し算はこんな感じ。

$$\frac{\langle e_1, \sigma \rangle \rightsquigarrow_e e’_1} {\langle e_1 + e_2, \sigma \rangle \rightsquigarrow_e e’_1 + e_2}$$

$$\frac{\langle e_2, \sigma \rangle \rightsquigarrow_e e’_2} {\langle v_1 + e_2, \sigma \rangle \rightsquigarrow_e v_1 + e’_2}$$

$$\langle n_1 + n_2, \sigma \rangle \rightsquigarrow_e n\ \mathsf{if}\ n = n_1 + n_2$$

class Add < Struct.new(:left, :right)
  def reduce(environment)
    if left.reducible?
      Add.new(left.reduce(environment), right)
    elsif right.reducible?
      Add.new(left, right.reduce(environment))
    else
      Number.new(left.value + right.value)
    end
  end
end

かけ算はこうなる。

$$\frac{\langle e_1, \sigma \rangle \rightsquigarrow_e e’_1} {\langle e_1 \ast e_2, \sigma \rangle \rightsquigarrow_e e’_1 \ast e_2}$$

$$\frac{\langle e_2, \sigma \rangle \rightsquigarrow_e e’_2} {\langle v_1 \ast e_2, \sigma \rangle \rightsquigarrow_e v_1 \ast e’_2}$$

$$\langle n_1 \ast n_2, \sigma \rangle \rightsquigarrow_e n\ \mathsf{if}\ n = n_1 \times n_2$$

class Multiply
  def reduce(environment)
    if left.reducible?
      Multiply.new(left.reduce(environment), right)
    elsif right.reducible?
      Multiply.new(left, right.reduce(environment))
    else
      Number.new(left.value * right.value)
    end
  end
end

less than (<) はこう。

$$\frac{\langle e_1, \sigma \rangle \rightsquigarrow_e e’_1} {\langle e_1 < e_2, \sigma \rangle \rightsquigarrow_e e’_1 < e_2}$$

$$\frac{\langle e_2, \sigma \rangle \rightsquigarrow_e e’_2} {\langle v_1 < e_2, \sigma \rangle \rightsquigarrow_e v_1 < e’_2}$$

$$\langle n_1 < n_2, \sigma \rangle \rightsquigarrow_e \tt{true}\ \mathsf{if}\ n_1 < n_2$$

$$\langle n_1 < n_2, \sigma \rangle \rightsquigarrow_e \tt{false}\ \mathsf{if}\ n_1 \geq n_2$$

class Reduce
  def reduce(environment)
    if left.reducible?
      LessThan(left.reduce(environment), right)
    elsif right.reducible?
      LessThan(left, right.reduce(environment))
    else
      Boolean.new(left.value < right.value)
    end
  end
end

仮想機械が環境を持てるようにする

class Machine < Struct.new(:expression, :environment)
  def step
    self.expression = expression.reduce(environment)
  end
end