ruby.rb

class Number < Struct.new(:value)
end

class Add < Struct.new(:left, :right)
end

class Number
  def to_s
    value.to_s
  end
  def inspect
    "<<#{self}>>"
  end
end

class Add
  def to_s
    "#{left} + #{right}"
  end
  def inspect
    "<<#{self}>>"
  end
end

class Number
  def reducible?
    false
  end
end

class Add
  def reducible?
    true
  end
  
  def reduce
    if left.reducible?
      Add.new(left.reduce, right)
    else right.reducible?
      Add.new(left, right.reduce)
    else
      Number.new(left.value + right.value)
    end
  end
end

class Machine < Struct.new(:expr)
  def step
    self.expr = expr.reduce
  end
  def run
    while expr.reducible?
      step
    end
    expr
  end
end


# BigStep
class Number < Struct.new(:value)
  def evaluate
    self
  end
end

class Add < Struct.new(:left, :right)
  def evaluate
    Number.new(left.evaluate.value + right.evaluate.value)
  end
end