scheme.rb

def tokenize(s)
  s.gsub(/[()]/, ' \0 ').split
end

def read_from(tokens)
  raise SyntaxError, 'unexpected EOF while reading' if tokens.length == 0
  case token = tokens.shift
  when '('
    l = []
    until tokens[0] == ')'
      l.push read_from(tokens)
    end
    tokens.shift
    l
  when ')'
    raise SyntaxError, 'unexpected )'
  else
    atom(token)
  end
end

def atom(token)
  [:Integer, :Float].each do |func|
    begin
      return send(func, token)
    rescue ArgumentError
    end
  end
  return token.to_sym
end

def read(s)
  read_from tokenize(s)
end
alias :parse :read

class Env < Hash
  def initialize(params=[], args=[], outer=nil)
    h = Hash[params.zip(args)]
    self.merge!(h)
    self.merge!(yield) if block_given?
    @outer = outer
  end

  def find(key)
    self.has_key?(key) ? self : @outer.find(key)
  end
end

def evaluate(x, env=$GLOBAL_ENV)
  case x
  when Symbol
    if x == '#f'.intern or x == '#t'.intern
      x
    else
      env.find(x)[x]
    end
  when Array
    case x.first
    when :quote
      _, exp = x
      exp
    when :if
      _, test, conseq, alt = x
      evaluate((evaluate(test, env) != '#f'.intern ? conseq : alt), env)
    when :set!
      _, var, exp = x
      env.find(var)[var] = evaluate(exp, env)
    when :define
      _, var, exp = x
      env[var] = evaluate(exp, env)
      nil
    when :lambda
      _, vars, exp = x
      lambda { |*args| evaluate(exp, Env.new(vars, args, env)) }
    when :begin
      x[1..-1].inject(nil) { |val, exp| val = evaluate(exp, env) }
    else
      proc, *exps = x.inject([]) { |mem, exp| mem << evaluate(exp, env) }
      proc[*exps]
    end
  else
    x
  end
end

def to_truth_f(fun)
  lambda do |*args|
    fun[*args] ? :'#t' : :'#f'
  end
end

$GLOBAL_ENV = Env.new do
  {
   :+       => ->x,y{x+y},
   :-       => ->x,y{x-y},
   :*       => ->x,y{x*y},
   :/       => ->x,y{x/y},
   :not     => ->x{x == :'#f' ? :'#t' : :'#f'},
   :>       => to_truth_f(->x,y{x>y}),
   :<       => to_truth_f(->x,y{x<y}),
   :>=      => to_truth_f(->x,y{x>=y}),
   :<=      => to_truth_f(->x,y{x<=y}),
   :'='     => to_truth_f(->x,y{x==y}),
   :equal?  => to_truth_f(->x,y{x.equal?(y)}),
   :eq?     => to_truth_f(->x,y{x.eql? y}),
   :length  => ->x{x.length},
   :cons    => ->x,y{[x,y]},
   :car     => ->x{x[0]},
   :cdr     => ->x{x[1..-1]},
   :append  => ->x,y{x+y},
   :list    => ->*x{[*x]},
   :list?   => to_truth_f(->*x{x.instance_of?(Array)}),
   :null?   => to_truth_f(->x{x.empty?}),
   :symbol? => to_truth_f(->x{x.instance_of?(Symbol)}),
   }
end

def to_string(exp)
  puts (exp.instance_of?(Array)) ? '(' + exp.map(&:to_s).join(' ') + ')' : "#{exp}"
end

require "readline"
def repr
  while line = Readline.readline('repr> ', true)
    val = evaluate(parse line)
    to_string(val) unless val.nil?
  end
end

scheme_spec.rb

require 'scheme'

describe 'tokenize' do
  it 'tokenizes normal tokens' do
    tokenize("asdf fdsa").should == ["asdf", "fdsa"]
  end

  it 'tokenizes parentheses' do
    tokenize("(asdf fdsa)").should == ["(", "asdf", "fdsa", ")"]
  end
end

describe 'read_from' do
  it 'returns atom' do
    read_from(['123']).should == 123
  end

  it 'returns list' do
    read_from(['(', 'asdf', 'fdsa', ')']).should == [:asdf, :fdsa]
  end
end

describe 'atom' do
  it 'converts number' do
    atom('123').should == 123
  end

  it 'converts symbol' do
    atom('asdf').should == :asdf
  end

  it 'converts float' do
    atom('0.001').should == 0.001
  end
end

describe Env do
  it 'is initialized with params' do
    Env.new([:a, :b], [1, 2]).should == {:a => 1, :b => 2}
  end

  describe '#find' do
    it 'returns self if it contains key' do
      env1 = Env.new([:b], [2])
      env2 = Env.new([:a], [1], env1)
      env2.find(:a).should == env2
    end

    it 'finds in outer env' do
      env1 = Env.new([:b], [2])
      env2 = Env.new([:a], [1], env1)
      env2.find(:b).should == env1
    end
  end

  it 'yields if block given' do
    Env.new() do
      {:a => 1}
    end.should == {:a => 1}
  end
end

describe 'evaluate' do
  def env
    Env.new([:a], [1])
  end

  it 'finds value in env' do
    evaluate(:a, env).should == 1
  end

  it 'quotes rest symbols' do
    evaluate([:quote, :asdf]).should == :asdf
  end

  it 'sees condition(true)' do
    evaluate([:if, 1, [:quote, :true], [:quote, :false]]).should == :true
  end

  it 'sees condition(false)' do
    evaluate([:if, '#f'.intern, [:quote, :true], [:quote, :false]]).should == :false
  end

  it 'sets environment' do
    e = env
    evaluate([:set!, :a, 2], e)
    e[:a].should == 2
  end

  it 'defines in environment' do
    e = env
    evaluate([:define, :b, 2], e)
    e[:b].should == 2
  end

  it 'creates lambda' do
    lam = evaluate([:lambda, [:x], :x])
    (lam [2]).should == 2
  end

  it 'creates lambda with current env' do
    lam = evaluate([:lambda, [], :a], env)
    (lam []).should == 1
  end

  it 'creates lambda with new env' do
    e = env
    lam = evaluate([:lambda, [], [:define, :a, 2]], e)
    e[:a].should == 1
  end

  it 'evaluates all expr' do
    e = env
    evaluate([:begin, [:define, :a, 2], [:define, :b, 3]], e)
    e[:a].should == 2
    e[:b].should == 3
  end

  it 'returns last expression' do
    evaluate([:begin, 2, 3]).should == 3
  end

  it 'applies function' do
    evaluate([[:lambda, [:x], :x], 2]).should == 2
  end

  it 'returns number' do
    evaluate(2).should == 2
  end
end