lis.rb

class String
  def tokenize()
    return self.gsub(/(\(|\))/){|s| " " + s + " " }.split(' ');
  end
end


def parse(tokens)
  if(tokens.length == 0)
    raise "error"
  end
  tk = tokens.shift
  if(tk == "(")
    acc = []
    while ( (tk = tokens.shift) != ")")
      if(tk == "(")
        acc.unshift(parse(tokens.unshift(tk)))
      else
        acc.unshift(to_atom(tk))
      end
    end
    return acc.reverse
  elsif(tk == ")")
    raise "error"
  else
    return to_atom(tk)
  end
end

def eval(x, env = $global_env)
  if(x.is_a? Numeric)
        return x
  elsif (x.is_a? String)
    return env.find(x)[x]
  elsif(! (x.is_a?  Array) )
    raise "Error"
  elsif(x[0] == 'quote')
    return x[1]
  elsif(x[0] == 'if')
    if ( eval(x[1],env) )
      return eval(x[2], env)
    else
      return eval(x[3], env)
    end
  elsif(x[0] == 'set!')
    return env.find(x[1]).store(x[1], eval(x[2], env))
  elsif(x[0] == 'define')
    return env.this.store(x[1], eval(x[2], env))
  elsif(x[0] == 'lambda')
    return Proc.new{| *args |
      r = nil
      ev = Env.new(env)
      x[1].each_index{|i|
        ev.store(x[1][i], args[i])
      }
      for s in x[2..-1] do
        r = eval(s, ev)
      end
      r
    }
  elsif(x[0] == 'begin')
    val = []
    x[1..-1].each{|s|
      val = eval(s, env)
    }
    return val
  else
    exps = x.collect{|s| eval(s, env)}
    return funcall(exps[0], exps[1..-1])
  end
end

def to_atom(x)
  if ( /^\d+$/ =~ x )
    return x.to_i
  elsif ( /^\d*\.\d+$/ =~ x)
    return x.to_f
  else
    return x
  end
end

class Env < Hash
  @outer = nil
  def initialize(outer = nil)
    @outer = outer
    super()
  end
  def find(key)
    if( self.member?(key) )
      return self
    elsif( @outer )
      return @outer.find(key)
    else
      return nil
    end
  end
end

def funcall(fn, args)
  return fn.call(*args)
end

$global_env = Env.new()
$global_env.store("+", Proc.new{|x, y| x + y })

print parse("(a 2 (b c d))".tokenize()),"\n"
print eval(parse("2".tokenize())),"\n"
print eval(parse("(+ 2 3)".tokenize())),"\n"
print eval(parse("((lambda (a b) (+ a b)) 10 20)".tokenize())),"\n"