sexp.rb

def tokenize(text)
  text.scan /\(|\)|\w+|\d+|\S+|\+/
end

def parse_step(e)
  sexp = []
  stack = [sexp]
  while ")" != (tk = e.next)
    tk = parse_step(e) if tk == '('
    sexp.push tk
  end
  return sexp
end

def parse(e)
  sexps = []
  while e.next == '('
    sexps.push parse_step(e)
  end
rescue
  sexps
end

def execute(env, sexp)
  case sexp
  when /\d+/
    sexp.to_i
  when /\w+/
    env[sexp]
  when /".*"/
    sexp[1..-2]
  when Array
    fn, *params = sexp
    env[fn].call(env, *params)
  end
end

def define_primitives(env)
  env['define'] = lambda do |env, fn, *args|
    body = args[-1]
    env[fn] = lambda do |env, *params|
      params = params.map{|exp| execute(env, exp)}
      env = env.clone.merge(Hash[args[0..-2].zip(params)])
      execute(env, body)
    end
  end

  env['+'] = lambda do |env, a, b|
    execute(env, a) + execute(env, b)
  end

  env['-'] = lambda do |env, a, b|
    execute(env, a) - execute(env, b)
  end

  env['=='] = lambda do |env, a, b|
    execute(env, a) == execute(env, b)
  end

  env['if'] = lambda do |env, cond, a, b|
    return execute(env, a) if execute(env, cond)
    return execute(env, b)
  end

  env['puts'] = lambda do |env, e|
    puts execute(env, e)
  end

  env
end

text = <<EOF
(define fibnacci n
  (if (== n 0)
    0
    (+ n (fibnacci (- n 1)))))
(puts (fibnacci 3))
(puts 123)
EOF

env = define_primitives({})
e = tokenize(text).each
parse(e).each do |sexp|
  execute(env, sexp)
end