データの表現方法とLispの基本関数
Lisp処理系の設計の大半はデータ構造の設計です。ある意味、Lispは一定の抽象的な仕様を満たすデータ操作ルーチン集にすぎませんから、具体的なデータ構造が決まると、どのような実装になるかが、おおよそ決まります。
ここでは、データの表現方法として、consセル以外はすべてRubyのデータをそのまま使うことにします。LispのnilはRubyのnilで表現します。LispのシンボルはRubyのシンボルで表現します。シンボルの大域変数値はInterpクラスのインスタンス変数@symbolに格納します。こうすることで実装が簡単になります。とりわけ、Lispの組込み関数をRubyで自然に実現できます。
例えばLispの加算と乗算は、加算や乗算を行うProcオブジェクトをシンボル:'+'と:'*'の大域変数値としてセットすることで実現できます。
@symbol = {}
@symbol[:'+'] = proc {|*x| x.inject(0) {|a, b| a + b}}
@symbol[:'*'] = proc {|*x| x.inject(1) {|a, b| a * b}}
下記のようにL2Lispで加算や乗算を行うとき、内部でこのProcオブジェクトが呼び出されています。
> (+ 1 2 3 4) 10 > (* 1 2 3 4) 24 >
このことは+や*の値から直接確認できます。RubyのProcオブジェクトの文字列表現が見られます。
> + #<Proc:0x0001cac0@L2Lisp.rb:346> > * #<Proc:0x0001c818@L2Lisp.rb:347>
consセルを表すCellクラス
Lispは、可変長の列であるリスト（list）を、consセルをノードとする二分木で表現します。各consセルはcarおよびcdrと名付けられた枝または葉を持ちます。
Rubyにはconsセルに直接該当するものがありませんから、クラスとして定義します。最低限carとcdrの属性だけあれば十分ですが、便宜のため、文字列化メソッドを用意します。
さらに、Rubyのデータ構造として自然に扱えるようにeachイテレータを用意し、Enumerableモジュールをインクルードします。これによりlengthメソッドはinject(0) {|x, y| x + 1}と簡潔に定義できます。各要素への関数の適用結果をArrayでなくconsセルとして得るために、Enumerable#collectに似たmapcarも用意します。
eachイテレータはLispのmapc関数に相当します。mapcarイテレータはLispのmapcar関数に相当します。LL = L2Lisp # 便宜上の短縮名 MAX_EXPANSIONS = 5 # 再帰的に印字する深さ class Cell include Enumerable attr :car, true attr :cdr, true def initialize(car, cdr) @car = car @cdr = cdr end def inspect return LL.str(self) end def each # Lispのmapcに相当 j = self begin yield j.car j = j.cdr end while Cell === j j.nil? or raise ProperListExpected, j end def mapcar # Lispのmapcarに相当 c = yield @car x = y = Cell.new(c, nil) j = @cdr while Cell === j c = yield j.car y = y.cdr = Cell.new(c, nil) j = j.cdr end j.nil? or raise ProperListExpected, j return x end def length return inject(0) {|x, y| x + 1} end def _repr(print_quote, reclevel, printed) if printed.has_key?(self) reclevel -= 1 return ['...'] if reclevel == 0 else printed[self] = true end case @cdr when nil s = LL.str(@car, print_quote, reclevel, printed) return [s] when Cell s = LL.str(@car, print_quote, reclevel, printed) t = @cdr._repr(print_quote, reclevel, printed) return t.unshift(s) else s = LL.str(@car, print_quote, reclevel, printed) t = LL.str(@cdr, print_quote, reclevel, printed) return [s, '.', t] end end end # Cell # 引数の文字列表現を得る def str(x, print_quote=true, reclevel=MAX_EXPANSIONS, printed={}) case x when Cell return '(' + x._repr(print_quote, reclevel, printed).join(' ') + ')' when Symbol then return x.to_s when String, Exception then return (print_quote) ? x.inspect : x else return x.inspect end end module_function :str
実際にconsセルで作られるデータ構造は、本来の意味での二分木に限りません。閉路、つまりループ構造を作ることがあります。これは決してまれなことではなく、ある程度以上のLispプログラムによく現れます。ですから文字列化メソッドには、ループ構造をもつ循環リストに出会っても無限ループや無限再帰呼出しに陥らないことが求められます。
そこで、木構造のconsセルから再帰的に文字列表現を得るとき、文字列化済みのconsセルを「ハッシュ表」に登録することで無限再帰呼出しを防止することにします。上記コードのprinted引数がそのハッシュ表です。下記の実験では循環リストを作っていますが、一定レベル以上は...で代用されることが確認できます。
$ jirb irb(main):001:0> require "L2Lisp" => true irb(main):002:0> def cons(x, y) L2Lisp::Cell.new(x, y) end => nil irb(main):003:0> a = cons(1, cons(2, nil)) => (1 2) irb(main):004:0> a.car = a => ((((((...) 2) 2) 2) 2) 2) irb(main):005:0>
Lispのリストは、長さ1以上の場合はconsセルで表現されますが、長さ0の場合はnilで表現されます。nilにはeachメソッドがないため、リスト一般に対する繰返しを記述するときは場合分けが必要です。場合分けを省くため、特異メソッドとしてnil.eachを定義する方法は、L2Lispを他のプログラムに組み込むときに不具合が出るおそれがあります。下記のようなモジュール関数を定義します。
def mapc(x, &block) case x when Cell then x.each(&block) when nil then ; else raise ProperListExpected, x end end module_function :mapc
基本5関数の実現
Lispの基本5関数car、cdr、cons、atom、eqは下記のように実現できます。
@symbol[:car] = proc {|x| (x.nil?) ? nil : x.car}
@symbol[:cdr] = proc {|x| (x.nil?) ? nil : x.cdr}
@symbol[:cons] = proc {|x, y| Cell.new(x, y)}
@symbol[:atom] = proc {|x| (Cell === x) ? nil : :t}
@symbol[:eq] = proc {|x, y| (x == y) ? :t : nil}
Rubyの==演算子は、文字列などいくつかのクラスに対し表現が等価かどうかを判別します。つまり、一般的なLispのeqよりも広い範囲で真を返します。しかし、nilとconsセルについてはeqと同じように振舞いますから、Lispとしては問題ありません。
==演算子をequal?メソッドに替えると一般的なeqに近くなりますが、他の変更も必要になります。実験してみてください。実際のソース・ファイルを読んだ方は、atomの定義がこれより少し複雑になっていることに気付いたことと思います。これはマクロ引数の捕捉問題の対策のためです。詳しくは「続々L2Lisp:マクロの健全化」をみてください。
