Gcodeへのコンパイルと(正格な)評価器

Compiling to Gcode - 趣味的にっきの続きです。
G-machine COSC406 Compiler Implementation Techniques p.18までソースからGcodeへのコンパイルと(正格な)評価器を実装してみました。

require 'pp'

class ApNode
  def initialize(left, right)
    @left, @right = left, right
  end
  attr_reader :left, :right

  def inspect
    @left.inspect + '@' + @right.inspect
  end
end

class OpCode
  def initialize(arg = nil)
    @arg = arg
  end

  def inspect
    self.class.to_s.sub(/OpCode/, '') + (@arg ? ' ' + @arg.inspect : '')
  end
end

class OpCodePush < OpCode
  def evaluate(stack)
    stack.push(stack[-2 - @arg].right)
  end  
end

class OpCodePushInt < OpCode
  def evaluate(stack)
    stack.push(@arg)
  end  
end

class OpCodePushGlobal < OpCodePushInt
end

class OpCodeMkap < OpCode
  def evaluate(stack)
    f = stack.pop
    g = stack.pop
    stack.push(ApNode.new(f, g))
  end  
end

class OpCodeSlide < OpCode
  def evaluate(stack)
    @arg.times { stack.shift }
  end  
end

class OpCodeUnwind < OpCode
  def evaluate(stack)
    while stack.last.is_a?(ApNode)
      stack.push(stack.last.left)
    end
  end  
end

def comp_sc(f, xs, e)
  # p [:comp_sc, f, xs, e]
  xs1 = xs.inject([{}, 0]) {|(h, i), x| h[x] = i; [h, i + 1] }.first
  comp_r(e, xs1, xs.size)
end

def comp_r(e, q, d)
  # p [:comp_r, e, q, d]
  comp_c(e, q) + [OpCodeSlide.new(d + 1), OpCodeUnwind.new()]
end

def comp_c(e, q)
  # p [:comp_c, e, q]
  case e
  when Symbol
    if e.to_s =~ /\A[A-Z]/
      [OpCodePushGlobal.new(e)]
    else
      [OpCodePush.new(q[e])]
    end
  when Integer
    [OpCodePushInt.new(e)]
  when Array
    case e.size
    when 0
      []
    when 1
      comp_c(e.first, q)
    else
      e0, e1 = e[0 .. -2], e[-1]
      q1 = q.inject({}) {|h, (k, v)| h[k] = v + 1; h }
      comp_c(e1, q) + comp_c(e0, q1) + [OpCodeMkap.new]
    end
  else
    raise 'invalid e.'
  end
end

def evaluate(codes, stack)
  while stack.last.is_a?(Symbol)
    # pp stack.last
    codes[stack.last].each do |op| 
      pp [op, stack]
      op.evaluate(stack)
    end
  end
  stack
end

if $0 == __FILE__
  src = [
    [:S,    [:f, :g, :x], [:f, :x, [:g, :x]]],
    [:K,    [:x, :y    ], [:x              ]],
    [:I,    [:x        ], [:x              ]],
    [:MAIN, [          ], [:S, :K, :I, 3   ]]
  ]

  codes = src.inject({}) do |cs, (f, xs, e)| 
    cs[f] = comp_sc(f, xs, e)
    cs
  end
  # pp codes

  pp evaluate(codes, [:MAIN]) # => [3]
end