Skip to content

Instantly share code, notes, and snippets.

@dahlia
Created September 2, 2010 07:52
Show Gist options
  • Save dahlia/562017 to your computer and use it in GitHub Desktop.
Save dahlia/562017 to your computer and use it in GitHub Desktop.
30 minutes Lisp in Ruby
# 30 minutes Lisp in Ruby
# Hong Minhee <http://dahlia.kr/>
#
# This Lisp implementation does not provide a s-expression reader.
# Instead, it uses Ruby syntax like following code:
#
# [:def, :factorial,
# [:lambda, [:n],
# [:if, [:"=", :n, 1],
# 1,
# [:*, :n, [:factorial, [:-, :n, 1]]]]]]
#
# Enter the REPL:
#
# $ ruby lisp.rb
# >>>
#
require 'rational'
module Lisp
SPECIAL_FORMS = {:def => lambda do |name, value|
value = value.analyze_form
lambda do |env|
val = value.call(env)
env[name] = val
if val.is_a?(Lambda) && val.name
val.name = name
end
val
end
end,
:lambda => lambda do |params, body|
eval_body = body.analyze_form
lambda do |env|
Lambda.new(env, params, eval_body)
end
end,
:quote => lambda do |form|
lambda {|env| form }
end,
:if => lambda do |cond, trueval, falseval|
cond = cond.analyze_form
trueval = trueval.analyze_form
falseval = falseval.analyze_form
lambda do |env|
val = cond.call(env) ? trueval : falseval
val.call(env)
end
end}
class ::Symbol
def analyze_form
lambda {|env| env[self] }
end
end
class ::Numeric
def analyze_form
lambda {|env| self }
end
end
class ::String
def analyze_form
lambda {|env| self }
end
end
class ::Array
def analyze_form
if SPECIAL_FORMS.include?(self.first)
return SPECIAL_FORMS[self.first].call(*self[1..-1])
end
list = self.map {|form| form.analyze_form }
lambda do |env|
lst = list.map {|analyze| analyze.call(env) }
lst.first.call(*lst[1..-1])
end
end
end
class Quote
attr_accessor :form
def initialize(form)
self.form = form
end
def analyze_form
lambda {|env| self.form }
end
end
class Lambda
attr_accessor :environment, :parameters, :body, :name
def initialize(environment, parameters, body, name = nil)
self.environment = environment
self.parameters = parameters
self.body = body
self.name = name
end
def call(*args)
env = Environment[self.parameters.zip(args)]
env.superenv = self.environment
body.call(env)
end
def inspect
self.name ? "#<Lisp::Lambda #{self.name}>" : "#<Lisp::Lambda>"
end
end
class Environment < Hash
attr_accessor :superenv
def initialize(superenv = nil)
self.superenv = superenv
end
def [](key)
include?(key, true) ? super(key) : self.superenv && self.superenv[key]
end
def empty?
super && (!self.superenv || self.superenv.empty?)
end
def include?(key, without_superenv = false)
result = super(key)
unless without_superenv
result ||= self.superenv && self.superenv.include?(key)
end
result
end
def has_key?(key, without_superenv = false)
include?(key, without_superenv)
end
def key?(key, without_superenv = false)
include?(key, without_superenv)
end
def keys(without_superenv = false)
without_superenv ? super : (super + self.superenv.keys).uniq
end
def evaluate(form)
form.analyze_form.call(self)
end
end
module Runtime
def initialize_environment
Environment[:car, lambda {|lst| lst.empty? ? nil : lst.first },
:cdr, lambda {|lst| lst.empty? ? nil : lst[1..-1] },
:null, lambda { nil },
:and, lambda {|*args| args.all? },
:or, lambda {|*args| args.any? },
:list, lambda {|*args| args },
:append, lambda {|a, b| a + b },
:apply, lambda {|proc, args| proc.call(*args) },
:eval, lambda {|form, env| env.evaluate(form) },
:+, lambda {|*args| args.inject(0) {|x, y| x + y } },
:-, lambda do |v, *args|
args.empty? ? -v : args.inject(v) {|x, y| x - y }
end,
:*, lambda {|*args| args.inject(1) {|x, y| x * y } },
:/, method(:Rational),
:div, lambda {|*args| args.inject(1.0) {|x, y| x / y } },
:%, lambda {|*args| args.inject(1) {|x, y| x % y } },
:"=", lambda {|a, b| a == b},
:>, lambda {|a, b| a > b},
:<, lambda {|a, b| a < b},
:>=, lambda {|a, b| a >= b},
:<=, lambda {|a, b| a <= b},
:string, lambda {|*args| args.map {|x| x.to_s }.join },
:hash, lambda {|*args| Hash[*args] },
:symbol?, lambda {|v| v.isa?(Symbol) },
:number?, lambda {|v| v.isa?(Numeric) },
:string?, lambda {|v| v.isa?(String) },
:list?, lambda {|v| v.isa?(Array) },
:quote?, lambda {|v| v.isa?(Quote) },
:function?, lambda {|v| v.respond_to?(:call) },
:hash?, lambda {|v| v.isa?(Hash) }]
end
end
end
class Lisp::REPL
include Lisp::Runtime
attr_accessor :environment
def initialize
self.environment = initialize_environment()
end
def loop
require 'readline'
while buf = Readline.readline('>>> ', true)
begin
form = eval(buf)
result = self.environment.evaluate(form)
puts "==> #{result.inspect}"
rescue Exception => e
puts "!!! #{e.backtrace.first} #{e} (#{e.class.name})"
for stack in e.backtrace[1..-1]
puts " from #{stack}"
end
end
end
end
end
if __FILE__ == $0
repl = Lisp::REPL.new
repl.loop()
end
@alex-lx
Copy link

alex-lx commented May 3, 2013

Cool

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment