2010年10月15日金曜日

(Lisp (を書いて学ぶ) Ruby)

Peter Norvigせんせーの記事の邦訳、((Pythonで) 書く (Lisp) インタプリタ) を写経してみました。Rubyで。

class String
def tokenize()
return self.gsub(/(\(|\))/){|s| " " + s + " " }.split(' ');
end
end

def parse(tokens)
if(tokens.length == 0)
raise "error"
end
tk = tokens.shift
if(tk == "(")
acc = []
while ( (tk = tokens.shift) != ")")
if(tk == "(")
acc.unshift(parse(tokens.unshift(tk)))
else
acc.unshift(to_atom(tk))
end
end
return acc.reverse
elsif(tk == ")")
raise "error"
else
return to_atom(tk)
end
end

def eval(x, env = $global_env)
if(x.is_a? Numeric)
return x
elsif (x.is_a? String)
return env.find(x)[x]
elsif(! (x.is_a? Array) )
raise "Error"
elsif(x[0] == 'quote')
return x[1]
elsif(x[0] == 'if')
if ( eval(x[1],env) )
return eval(x[2], env)
else
return eval(x[3], env)
end
elsif(x[0] == 'set!')
return env.find(x[1]).store(x[1], eval(x[2], env))
elsif(x[0] == 'define')
return env.store(x[1], eval(x[2], env))
elsif(x[0] == 'lambda')
return Proc.new{| *args |
r = nil
ev = Env.new(env)
x[1].each_index{|i|
ev.store(x[1][i], args[i])
}
for s in x[2..-1] do
r = eval(s, ev)
end
r
}
elsif(x[0] == 'begin')
val = []
x[1..-1].each{|s|
val = eval(s, env)
}
return val
else
exps = x.collect{|s| eval(s, env)}
return exps[0].call(*exps[1..-1])
end
end

def to_atom(x)
if ( /^\d+$/ =~ x )
return x.to_i
elsif ( /^\d*\.\d+$/ =~ x)
return x.to_f
else
return x
end
end

class Env < Hash
@outer = nil
def initialize(outer = nil)
@outer = outer
super()
end
def find(key)
if( self.member?(key) )
return self
elsif( @outer )
return @outer.find(key)
else
return nil
end
end
end

$global_env = Env.new()
$global_env.store("+", Proc.new{|x, y| x + y })

print parse("(a 2 (b c d))".tokenize()),"\n"
print eval(parse("2".tokenize())),"\n"
print eval(parse("(+ 2 3)".tokenize())),"\n"
print eval(parse("((lambda (a b) (+ a b)) 10 20)".tokenize())),"\n"
print eval(parse("(define a 2)".tokenize())),"\n"
print eval(parse("a".tokenize())),"\n"
print eval(parse("(set! a 10)".tokenize())),"\n"
print eval(parse("a".tokenize())),"\n"

メモ

  • to_i は文字列が数字でない場合0を返す。先頭が数字なら、可能なぶんだけ数値にする。
  • アスタリスクは可変長引数や配列の展開?を表す
  • アットマークから始まるシンボルはメンバ変数
  • ドルマークから始まるシンボルはグローバル変数
  • 例外を投げるにはraiseを使う

0 件のコメント:

コメントを投稿