Scheme Interpreter in Ruby (a Ruby port of the Peter Norvig's "lis.py")

lisp.rb

# -*- coding: utf-8 -*-
# Scheme Interpreter in Ruby
# (a Ruby port of the Peter Norvig's "lis.py")

class Env < Hash
  def initialize(parms = [], args = [], outer = nil)
    @outer = outer
    update(Hash[parms.zip(args)])
  end

  def find(var)
    if self.has_key? var
      self
    else
      @outer.find(var)
    end
  end
end

def add_globals(env)
  [:+, :-, :*, :/].each do |s|
    env[s] = ->(*x) { x.reduce { |a, e| a.send(s, e) } }
  end
  [:>, :<, :>=, :<=].each do |s|
    env[s] = ->(x, y) { x.send(s, y) }
  end
  env.update({
               :not     => ->(x) { !x },
               :'='     => ->(x, y) { x == y },
               :equal?  => ->(x, y) { x == y },
               :eq?     => ->(x, y) { x.equal? 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?   => ->(x) { x.is_a? Array },
               :null?   => ->(x) { x == [] },
               :symbol? => ->(x) { x.is_a? Symbol }
             })
end

def evaluate(x, env)
  if x.is_a? Symbol             # variable reference
    env.find(x)[x]
  elsif !x.is_a? Array          # constant literal
    x
  elsif x[0] == :quote          # (quote exp)
    x[1]
  elsif x[0] == :if             # (if test conseq alt)
    _, test, conseq, alt = x
    evaluate(evaluate(test, env) ? conseq : alt, env)
  elsif x[0] == :set!           # (set! var exp)
    _, var, exp = x
    env.find(var)[var] = evaluate(exp, env)
  elsif x[0] == :define         # (define var exp)
    _, var, exp = x
    env[var] = evaluate(exp, env)
  elsif x[0] == :lambda         # (lambda (var*) exp)
    _, vars, exp = x
    ->(*args) { evaluate(exp, Env.new(vars, args, env)) }
  elsif x[0] == :begin          # (begin exp*)
    x[1..-1].map { |exp| evaluate(exp, env) }[-1]
  else                          # (proc exp*)
    exps = x.map { |exp| evaluate(exp, env) }
    exps[0].call(*exps[1..-1])
  end
end

def read(s)
  read_from(tokenize(s))
end

alias parse read

def tokenize(s)
  s.gsub('(', ' ( ').gsub(')', ' ) ').split
end

def read_from(tokens, cont_tokens_proc = nil)
  raise 'unexpected EOF while reading' if tokens.empty?
  token = tokens.shift
  if '(' == token
    l = []
    while tokens[0] != ')'
      if tokens.empty? && !cont_tokens_proc.nil?
        tokens.concat(cont_tokens_proc.call) while tokens.empty?
        break if tokens[0] == ')'
      end
      l << read_from(tokens, cont_tokens_proc)
    end
    tokens.shift                # pop off ')'
    l
  elsif ')' == token
    raise 'unexpected )'
  else
    atom token
  end
end

def atom(token)
  begin
    Integer(token)
  rescue
    begin
      Float(token)
    rescue
      token.to_sym
    end
  end
end

def to_string(exp)
  if exp.is_a? Array
    '(' + exp.map { |x| to_string x }.join(' ') + ')'
  else
    exp.to_s
  end
end

def repl(prompt = 'lisp.rb> ')
  env = add_globals(Env.new)
  tokens_proc = ->() { tokenize(gets) }
  while true
    print prompt
    puts to_string(evaluate(read_from(tokens_proc.call, tokens_proc), env))
  end
end

if __FILE__ == $0
  repl
end