gistfile1.rb

module Node
  def inspect
    "<<#{self}>>"
  end
end

Number = Struct.new(:value) do
  include Node

  def to_s
    value.to_s
  end

  def reducible?
    false
  end
end

module BinaryOp
  def to_s
    "#{left} #{operator} #{right}"
  end

  def reducible?
    true
  end

  def reduce(environment)
    if left.reducible?
      self.class.new(left.reduce(environment), right)
    elsif right.reducible?
      self.class.new(left, right.reduce(environment))
    else
      return_type.new(left.value.send(operator, right.value))
    end
  end
end

Add = Struct.new(:left, :right) do
  include Node
  include BinaryOp

  def operator
    "+"
  end

  def return_type
    Number
  end
end

Multiply = Struct.new(:left, :right) do
  include Node
  include BinaryOp

  def operator
    "*"
  end

  def return_type
    Number
  end
end

expression = Add.new(
  Multiply.new(Number.new(1), Number.new(2)),
  Multiply.new(Number.new(3), Number.new(4)))
expression                         # => <<1 * 2 + 3 * 4>>
expression.reducible?              # => true
expression = expression.reduce({}) # => <<2 + 3 * 4>>
expression.reducible?              # => true
expression = expression.reduce({}) # => <<2 + 12>>
expression.reducible?              # => true
expression = expression.reduce({}) # => <<14>>
expression.reducible?              # => false

Boolean = Struct.new(:value) do
  include Node

  def to_s
    value.to_s
  end

  def reducible?
    false
  end
end

LessThan = Struct.new(:left, :right) do
  include Node
  include BinaryOp

  def operator
    "<"
  end

  def return_type
    Boolean
  end
end

Machine = Struct.new(:statement, :environment) do
  def step
    self.statement, self.environment = statement.reduce(environment)
  end

  def run
    while statement.reducible?
      puts "#{statement}, #{environment}"
      step
    end

    puts "#{statement}, #{environment}"
  end
end

Variable = Struct.new(:name) do
  include Node

  def to_s
    name.to_s
  end

  def reducible?
    true
  end

  def reduce(environment)
    environment[name]
  end
end

def run(expression, environment)
  machine = Machine.new(expression, environment)
  machine.run
end

expression = Add.new(
  Variable.new(:x),
  Variable.new(:y))
expression                      # => <<x + y>>

class DoNothing
  include Node

  def to_s
    "do-nothing"
  end

  def ==(other)
    other.is_a?(DoNothing)
  end

  def reducible?
    false
  end
end

Assign = Struct.new(:name, :expression) do
  def to_s
    "#{name} = #{expression}"
  end

  def reducible?
    true
  end

  def reduce(environment)
    if expression.reducible?
      [Assign.new(name, expression.reduce(environment)), environment]
    else
      [DoNothing.new, environment.merge(name => expression)]
    end
  end
end

statement = Assign.new(
  :x, Add.new(Variable.new(:x), Number.new(1)))

# run(statement, x: Number.new(2))

If = Struct.new(:condition, :consequence, :alternative) do
  include Node

  def to_s
    "if (#{condition}) { #{consequence} } else { #{alternative} }"
  end

  def reducible?
    true
  end

  def reduce(environment)
    if condition.reducible?
      [If.new(condition.reduce(environment), consequence, alternative),
        environment]
    else
      case condition
      when Boolean.new(true)
        [consequence, environment]
      when Boolean.new(false)
        [alternative, environment]
      end
    end
  end
end

statement = If.new(
  Variable.new(:x),
  Assign.new(:y, Number.new(1)),
  Assign.new(:y, Number.new(2)))
# run(statement, x: Boolean.new(true))
# run(statement, x: Boolean.new(false))

Sequence = Struct.new(:first, :second) do
  include Node

  def to_s
    "#{first}; #{second}"
  end

  def reducible?
    true
  end

  def reduce(environment)
    case first
    when DoNothing.new
      [second, environment]
    else
      reduced_first, reduced_environment = first.reduce(environment)
      [Sequence.new(reduced_first, second), reduced_environment]
    end
  end
end

statement = Sequence.new(
  Assign.new(:x, Add.new(Number.new(1), Number.new(1))),
  Assign.new(:y, Add.new(Variable.new(:x), Number.new(1))))
# run(statement, {})

While = Struct.new(:condition, :body) do
  include Node

  def to_s
    "while (#{condition}) { #{body} }"
  end

  def reducible?
    true
  end

  def reduce(environment)
    [If.new(condition, Sequence.new(body, self), DoNothing.new),
      environment]
  end
end

statement = While.new(
  LessThan.new(Variable.new(:x), Number.new(5)),
  Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3))))

# run(statement, x: Number.new(1))
# >> while (x < 5) { x = x * 3 }, {:x=><<1>>}
# >> if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<1>>}
# >> if (1 < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<1>>}
# >> if (true) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<1>>}
# >> x = x * 3; while (x < 5) { x = x * 3 }, {:x=><<1>>}
# >> x = 1 * 3; while (x < 5) { x = x * 3 }, {:x=><<1>>}
# >> x = 3; while (x < 5) { x = x * 3 }, {:x=><<1>>}
# >> do-nothing; while (x < 5) { x = x * 3 }, {:x=><<3>>}
# >> while (x < 5) { x = x * 3 }, {:x=><<3>>}
# >> if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<3>>}
# >> if (3 < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<3>>}
# >> if (true) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<3>>}
# >> x = x * 3; while (x < 5) { x = x * 3 }, {:x=><<3>>}
# >> x = 3 * 3; while (x < 5) { x = x * 3 }, {:x=><<3>>}
# >> x = 9; while (x < 5) { x = x * 3 }, {:x=><<3>>}
# >> do-nothing; while (x < 5) { x = x * 3 }, {:x=><<9>>}
# >> while (x < 5) { x = x * 3 }, {:x=><<9>>}
# >> if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<9>>}
# >> if (9 < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<9>>}
# >> if (false) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }, {:x=><<9>>}
# >> do-nothing, {:x=><<9>>}