Rubyで書いたLISP級マクロ付きインタプリタ

LISP級マクロ付きのインタプリタをRubyで書いてみました。
書き方は、じっくり書いていきますが、haXeで書くより綺麗に書けたと思います。
次はphpでざくざくっと書いてみようと思います。

以下ソースです。

class Lexer

  def initialize src
    @src = src.sub("\r\n","\v").sub("\r", "\v").sub("\n", "\v")
  end

  def lex
    case @src
      when /^[\v\t ]*([0-9]+)(.*$)/
        @src = $2
        return $1.to_i
      when /^[\v\t ]*[\v][\v\t ]*([(\[{])(.*$)/
        @src = $2
        return "n" + $1
      when /^[\v\t ]*([()\[\]{},;]|[+*\-\/=<>]+)(.*$)/
        @src = $2
        return $1
      when /^[\v\t ]*'([a-zA-Z_][a-zA-Z_0-9]*)(.*$)/
        @src = $2
        return $1.intern
      when /^[\v\t ]*([a-zA-Z_][a-zA-Z_0-9]*)(.*$)/
        @src = $2
        return $1
      when /^[\v\t ]*(.*)(.*$)/
        return nil
    end
  end

  def tokens
    ts = []
    while (token = lex) != nil
      ts.push(token)
    end
    ts
  end

end

class Parser
  def initialize
    @opLs = {">"=>190, "<"=>190, "+" => 10, "-" => 10, "*" => 20, "/" => 20, "," => 2, "else" => 1}
    @opRs = {"=" => 5}
    @opPs = {"(" => ")","[" => "]", "{"=>"}","n(" => ")","n[" => "]", "n{"=>"}"}
    @opMs = {"(" => 200, "[" => 200, "{"=>200}
    @opSs = {"fun" => "(", "if" => "(","mac" => "("}
    @opBs = {"++"=> 30, ";" => 1}
  end

  def parse(src)
    lexer = Lexer.new(src)
    @tokens = lexer.tokens
    t = expn(0)
    while @tokens.length > 0
      t = ["@", t, expn(0)]
    end
    t
  end

  def expn p
    return "vid" if @opPs.value?(@tokens.first)
    t = @tokens.shift

    if @opSs.include?(t) && @opSs[t] == @tokens.first
      op = @tokens.shift
      e = expn(0)
      raise "error" unless((op2 = @tokens.shift) == @opPs[op])
      t = ["S"+t+op+op2, e, expn(0)]
    elsif @opPs.include?(t)
      t = t[1..-1] if (t[0] == "n")
      t2 = expn(0)
      raise "error" unless((t3 = @tokens.shift) == @opPs[t])
      t = ["P"+t+t3, t2]
    end

    while true
      if @opMs.include?(@tokens.first) && (tagp = @opMs[@tokens.first]) >= p
        op = @tokens.shift
        e = expn(0)
        raise "error" unless((op2=@tokens.shift) == @opPs[op])
        t = ["M"+op+op2, t, e]
      elsif @opBs.include?(@tokens.first) && (tagp = @opBs[@tokens.first]) >= p
        op = @tokens.shift
        t = ["B"+op, t]
        p = tagp
      elsif @opLs.include?(@tokens.first) && (tagp = @opLs[@tokens.first]) > p
        op = @tokens.shift
        t = ["L"+op, t, expn(tagp)]
      elsif @opRs.include?(@tokens.first) && (tagp = @opRs[@tokens.first]) >= p
        op = @tokens.shift
        #p "R"+op
        t = ["R"+op, t, expn(tagp)]
      else
        break
      end
    end
    t
  end
end

class Env
  def initialize parent = nil
    @env = {}
    @env["parent"] = parent unless(parent == nil)
  end
  def include?(name)
    @env.include?(name)
  end
  def [](name)
    return @env[name] if(@env.include?(name))
    return @env["parent"][name] if(@env.include?("parent"))
    return nil
  end
  
  def []=(name, value)
    rc = put(@env, name, value)
    if rc == nil
      @env[name] = value
      value
    else
      rc
    end
  end

  def put(env, name, value)
   if env.include?(name)
      env[name] = value
      value
    elsif env.include?("parent")
      put(env["parent"], name, value)
    else
      nil
    end
  end

end

class Calc
  def initialize
    @parser = Parser.new
  end
  def eval src
    exp = @parser.parse(src)
    p exp
    @env = Env.new
    @env["macros"] = []
    exp = macroExpand(exp, @env)
    p exp
    execute exp
  end

  def macroExpand(a, e)
    macros = e["macros"]
    macros.each{|obj|
      @env = Env.new(@env)
      rc = macroMatch(obj[1], a)
      if rc
        r = execute(obj[2])
        @env = @env["parent"]
        return r
      end
      @env = @env["parent"]
    }
    if a.instance_of?(Array)
      if a[0] == "Smac()"
        macros.push(a)
        return nil
      elsif a[0] == "M()" && a[1] == "add" &&  a[2].instance_of?(Array) && a[2][0] == "L,"
          return ["L+", macroExpand(a[2][1], e), macroExpand(a[2][2],e)]
      else
          return [a[0],macroExpand(a[1], e),macroExpand(a[2],e)]
      end
    else
      a
    end
  end


  def macroMatch (a,b)
    if(a.instance_of?(Array))
        return a[0]==b[0] && macroMatch(a[1],b[1]) && macroMatch(a[2], b[2])
    elsif a.instance_of?(Symbol)
      @env[a.to_s] = b
      return true
    else
      return a == b
    end
  end
  
  def execute exp
    if exp.instance_of?(Array)
      case exp[0]
      when "L+"; execute(exp[1]) + execute(exp[2])
      when "L-"; execute(exp[1]) - execute(exp[2])
      when "L*"; execute(exp[1]) * execute(exp[2])
      when "L/"; execute(exp[1]) / execute(exp[2])
      when "R="; @env[exp[1]] = execute(exp[2])
      when "B;"; execute(exp[1])
      when "B++"; dt = @env[exp[1]]; @env[exp[1]] = dt + 1; dt
      when "@"; execute(exp[1]); execute(exp[2])
      when "P()"; execute(exp[1])
      when "P{}"; execute(exp[1])
      when "P[]"; execute(exp[1])
      when "M()";
        case exp[1]
        when "p"; p(execute(exp[2]));
        else
          
          fun = execute(exp[1])
          back = @env
          @env = Env.new
          bind(fun[1], exp[2])
          @env["parent"] = fun[3]
          a = execute(fun[2])
          @env = back
          a
        end
      when "Sfun()"; ["fun", exp[1], exp[2], @env]
      when "fun"; exp
      when "Sif()"
        l1 = execute(exp[1])
        if exp[2].instance_of?(Array) && exp[2][0]=="Lelse"
          unless l1 == 0
            execute(exp[2][1])
          else
            execute(exp[2][2])
          end
        else
          unless l1 == 0
            execute(exp[2])
          else
            nil
          end
        end
      end
    elsif exp.instance_of?(String)
      case exp
      when "vid"; exp
      else @env[exp]
      end
    else
      exp
    end
  end

  def bind(p, l)
    case p
    when String; @env[p] = l;
    when Array
      raise "error" unless(p.length == 3)
      raise "error" unless(l.length == 3)
      raise "error" unless(p[0] == "L,")
      raise "error" unless(l[0] == "L,")
      bind(p[1], l[1])
      bind(p[2], l[2])
    else; raise "error"
    end
  end
  
end

calc = Calc.new
p calc.eval("mac(mul('a,'b))a*b mul(2,3)")