突然ですがRubyでSchemeのサブセットを実装します。継続と末尾再帰最適化ありの。その１：データ構造とパーサ
Scheme/Lispを実装してみようって企画はたまにあるのですが*1、どれもこれも無限ループするとスタックオーバーフローする始末。末尾再帰最適化もないような代物にSchemeを名乗る資格はございませんことよ。
というわけで、この私がRubyでScheme（末尾再帰最適化あり）を実装してみようという企画でございますよ！三日くらいでさっさと片付けたいところです。
データ構造
これはできるだけrubyネイティブの型をそのまま利用する方向で。Consのみ新たに定義しますが、symbolもnumberもrubyのを流用します。必要なメソッドを後からひっつけたりできるので物凄くつぶしがききますねrubyは。ダックタイプだし。
パース
最初の難関。真面目にやろうとすると割と面倒なので、適当におわらせましょう。
まずデータ構造と補助関数。
class Cons def initialize(a,d) @car=a @cdr=d end attr_accessor :car attr_accessor :cdr def to_a return [car] if cdr.nil? return [car] + cdr.to_a if cons? cdr raise 'not proper list' end def length return 1 if cdr.nil? return 1 + cdr.length end def to_s str="(" cur=self while cons? cur.cdr str+=cur.car.to_s + " " cur=cur.cdr end str+=cur.car.to_s str+=" . " +cur.cdr.to_s unless cur.cdr.nil? str+=")" return str end end def nil.to_s "()" end def cons?(s) s.kind_of?(Cons) end def cons(car,cdr) return Cons.new(car,cdr) end def list(*ss) return nil if ss.length==0 return cons(ss.first,list(*ss[1...ss.length])) end
nil.to_sを書き換えて大丈夫なのか少々不安なんですが気にしないことにしましょう。現時点では期待通りに動いています。
で、次にパース部分。実験的なものですからエラー処理なんかはいいかげんでいいですね。
def parse_s(src) src=src.gsub(/\s+/,",").gsub("(","list(") eval(src) end
ずぎゃーん。本当に素敵ですねrubyは……
irb(main):056:0> s=parse_s("(:lambda 1 2 3 4 (:foo :a :b :c ()))") => #<Cons:0x299c7ec @cdr=#<Cons:0x299c670 @cdr=#<Cons:0x299c544 @cdr=#<Cons:0x29 9c4cc @cdr=#<Cons:0x299c364 @cdr=#<Cons:0x299c238 @cdr=nil, @car=#<Cons:0x299ce7 c @cdr=#<Cons:0x299cc9c @cdr=#<Cons:0x299cae4 @cdr=#<Cons:0x299ca94 @cdr=#<Cons: 0x299ca30 @cdr=nil, @car=nil>, @car=:c>, @car=:b>, @car=:a>, @car=:foo>>, @car=4 >, @car=3>, @car=2>, @car=1>, @car=:lambda> irb(main):057:0> s.to_s => "(lambda 1 2 3 4 (foo a b c ()))" irb(main):058:0> s.length => 6 irb(main):060:0> s.cdr.cdr.cdr.cdr.cdr.car.to_s => "(foo a b c ())"
ちゃんとうごいてるみたいですね。すばらしい。
