step2.rb

class Plus < Struct.new :a, :b
  def to_s
    "(#{a} + #{b})"
  end
end
class Val < Struct.new :value
  def to_s
    value.to_s
  end
end
class Var < Struct.new :x
  def to_s
    x.to_s
  end
end
class App < Struct.new :f, :arg
  def to_s
    "(#{f} #{arg})"
  end  
end
class Lamb < Struct.new :x, :body
  def to_s
    "(\\#{x}.#{body})"
  end  
end
class Cont < Struct.new :x, :body
  def to_s
    "(cont \\#{x}.#{body})"
  end
end
class CallCC < Struct.new :x, :body
  def to_s
    "(callcc \\#{x}.#{body})"
  end
end

class Small
  attr_reader :stack, :expr, :env 
  def initialize(expr, maxsteps=30)
    @expr = expr
    @env = {}
    @stack = []
    @maxsteps = maxsteps
  end 

  def eval
    i = 0
    loop do
      step
      i += 1
      fail "expression too big" if i > @maxsteps
      if is_terminal?
        puts "evaluated in %d steps" % i
        return @expr
      end
    end
  end

  def is_terminal?
    is_value?(@expr) && @stack.empty?
  end

  def is_value?(expr)
    case expr
    when Val, Cont, Lamb
      true
    else  
      false
    end 
  end

  def ret
    if @stack.empty?
      p "stack is emtpy, returning #{@expr}"
      return @expr
    else  
      cont, env = @stack.pop
      @expr = cont.call(@expr)
      @env = env
    end
  end

  def reify
    @stack.map(&:first).reduce do |acc, f|
      ->(x) { acc.call(f.call(x)) }
    end
  end

  def step
    case @expr
    when Plus
      if is_value?(@expr.a)
        if is_value?(@expr.b)
          fail "expected a constant found #{@expr}" if !(@expr.a.is_a?(Val)) || !(@expr.b.is_a?(Val))
            
          @expr = Val.new(@expr.a.value + @expr.b.value)
        else
          a = @expr.a
          cont = ->(x){ Plus.new(a, x) }
          @stack.push([cont, @env])
          @expr = @expr.b
        end
      else
        b = @expr.b
        cont = ->(x){ Plus.new(x, b) }
        @stack.push([cont, @env])
        @expr = @expr.a
      end
    when App
      if @expr.f.is_a?(Lamb)
        if is_value?(@expr.arg)
          @env = @env.merge({ @expr.f.x => @expr.arg })
          @expr = @expr.f.body
        else
          f = @expr.f
          cont = ->(x) { App.new(f, x) }
          @stack.push([cont, @env])
          @expr = @expr.arg
        end
      elsif @expr.f.is_a?(Cont)
        if is_value?(@expr.arg)
          @stack = []
          @env = @env.merge({ @expr.f.x => @expr.arg })
          @expr = @expr.f.body
        else
          f = @expr.f
          cont = ->(x) { App.new(f, x) }
          @stack.push([cont, @env])
          @expr = @expr.arg
        end
      else
        arg = @expr.arg
        cont = ->(x) { App.new(x, arg) }
        @stack.push([cont, @env])
        @expr = @expr.f
      end 
    when Var
      fail "unbound variable #{@expr.x}" unless @env.key? @expr.x
      @expr = @env[@expr.x]
    when Val, Cont, Lamb
      ret
    when CallCC
      current_continuation = reify.call(Var.new(:K))
      cont = Cont.new(:K, current_continuation)
      @env = @env.merge({ @expr.x => cont })
      @expr = @expr.body
    else
      fail "invalid expr #{@expr}"
    end

    self
  end 
end

def val(a)
  case a
  when Integer
    Val.new(a)
  when Symbol
    Var.new(a)
  else
    a
  end
end

def plus(a, b)
  a = val(a)
  b = val(b)
  Plus.new(a, b)
end

def callCC(x, body)
  CallCC.new(x, val(body))
end

def cont(x, expr)
  Cont.new(x, val(expr))
end

def lamb(x, b)
  Lamb.new(x, val(b))
end

def app(a, b)
  App.new(val(a), val(b))
end

# Small stands for small-steps semantics

# (+ 1 2 3 4)
s = Small.new(plus(1, plus(2, plus(3, 4))))
puts s.eval # evaluates to 10

# (+ 1 2 (call/cc (lambda (k) (plus 3 (k 4)))))
s = Small.new(plus(1, plus(2, callCC(:k,
  plus(3, app(:k, 4))))))
puts s.eval # evaluates to 7
# when we call (k 4) the (callCC ...) expression
# is replaced by 4 so that the 3 in (plus 3 ...)
# is skipped