Create a gist now

Instantly share code, notes, and snippets.

@igjit /lisp.rb
Last active Dec 20, 2015

What would you like to do?
Scheme Interpreter in Ruby (a Ruby port of the Peter Norvig's "lis.py")
# -*- 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment