funterpreter.rb

# Based on conversations with Dan Friedman and Jason Hemann
# To evaluate use Sonic Pi...


define :valof do |exp, env={}|
  return exp      if exp.is_a? Numeric
  return env[exp] if exp.is_a? Symbol
  if exp.is_a?(Array) && exp[0] == :lambda
    lambda do |a|
      x = exp[1][0]
      b = exp[2]
      valof(b,
            lambda do |y|
              if (x == y)
                a
              else
                env[y]
              end
      end)
    end
  elsif exp.is_a?(Array) && exp[0] == :zero?
    if valof(exp[1], env) == 0
      1
    else
      0
    end
  elsif exp.is_a?(Array) && exp[0] == :sub1
    [0, valof(exp[1], env) - 1].max
  elsif exp.is_a?(Array) && exp[0] == :*
    sleep 0.01
    valof(exp[1], env) * valof(exp[2], env)
  elsif exp.is_a?(Array) && exp[0] == :let
    s = exp[1][0]
    v = valof(exp[1][1], env)
    env = lambda do |y|
      if (s == y)
        v
      else
        env[y]
      end
    end
    valof(exp[2], env)
  elsif exp.is_a?(Array) && exp[0] == :if
    if valof(exp[1], env) == 1
      valof(exp[2], env)
    else
      valof(exp[3], env)
    end
  elsif exp.is_a?(Array)
    valof(exp[0], env).call(valof(exp[1], env))
  end
end

define :read do |s, exp=[]|

  s = s.strip
  return exp if s.empty?

  m = s.match(/\A(\d+)(.*)/m)
  return read(m[2], exp << m[1].to_i) if m

  m = s.match(/\A([a-zA-Z0-9?*!]+)(.*)/m)
  return read(m[2], (exp << m[1].to_sym)) if m

  m = s.match(/\A\((.*)/m)
  if m
    rest, res = read(m[1])
    return read(rest, (exp << res))
  end

  m = s.match(/\A\)(.*)/m)
  return m[1], exp if m

  raise "oops, bad syntax (and bad error message)!"
end

define :my_eval do |s|
  valof(read(s)[0], {})
end


puts "starrrrting......"
assert_equal read(""), []
assert_equal read("()"), [[]]
assert_equal read("5"), [5]
assert_equal read("foo"), [:foo]
assert_equal read("foo bar"), [:foo, :bar]

assert_equal read("5 3"), [5, 3]
assert_equal read("(5 3)"), [[5, 3]]
assert_equal read("(foo bar)"), [[:foo, :bar]]
assert_equal read("(5 3) 7"), [[5, 3], 7]
assert_equal read("(5 3) (7)"), [[5, 3], [7]]
assert_equal read("(5 (3)) (7)"), [[5, [3]], [7]]
assert_equal read("(lambda (x) 3)"), [[:lambda, [:x], 3]]
assert_equal read("((lambda (x) 7) 6)"), [[[:lambda, [:x], 7], 6]]
assert_equal read("(if (zero? 0) 100 200)"), [[:if, [:zero?, 0], 100, 200]]

assert_equal my_eval("(let (x 2) (* x x))"), 4


assert_equal valof(5), 5
assert_equal valof(:x, {:x => 3}), 3
assert_equal valof([:lambda, [:x], 7]).class, Proc
assert_equal valof([[:lambda, [:x], 7], 6]), 7
assert_equal valof([:zero?, 0]), 1
assert_equal valof([:zero?, 1]), 0
assert_equal valof([:if, [:zero?, 0], 100, 200]), 100
assert_equal valof([:if, [:zero?, 1], 100, 200]), 200
assert_equal valof([[:lambda, [:x], 3], 5]), 3

assert_equal my_eval("5"), 5
assert_equal my_eval("(if (zero? 0) 100 200)"), 100
assert_equal my_eval("((lambda (x) 3) 5)"), 3
assert_equal my_eval("((lambda (x) x) 5)"), 5
assert_equal my_eval("(sub1 5)"), 4
assert_equal my_eval("(sub1 0)"), 0
assert_equal my_eval("(let (x 1) x)"), 1

assert_equal my_eval("(let (! 1) !)"), 1
assert_equal my_eval("(* 5 2)"), 10

assert_equal my_eval("(let (x (lambda (y) 3)) (x))"), 3

assert_equal my_eval("((let (! (lambda (!)
           (lambda (n)
             (if (zero? n)
                 1
               (* n ((! !) (sub1 n)))))))
   (lambda (n)
     ((! !) n)))
 5)"), 5 * 4 * 3 * 2