表面だけ見ると Ruby の Array、 Hash っぽいけど中身は cons セル、というものを書いてみました。
試してみたくなって、なんとなく書いてみた、という感じのものです。 cons セルさえあれば基本的なデータ構造が作れてなんとかなるんだな、という感触がふんわり得られればOK。 なので、効率の悪さは無視します。
あまり調べずに適当に書いたので、一般的な Lisp や Scheme とは命名や動作が微妙に違っている気がします。
まず ConsCell クラスと cons メソッド。
class ConsCell attr_reader :car, :cdr def initialize(first, rest) @car = first @cdr = rest end def _to_s(x) x.nil? ? "nil" : x.to_s end def to_s "(#{ _to_s(@car) } . #{ _to_s(@cdr) })" end end def cons(first, rest) ConsCell.new(first, rest) end
puts cons(1, nil) #=> (1 . nil) puts cons(1, 2) #=> (1 . 2) puts cons(cons(1, 2), 3) #=> ((1 . 2) . 3)
それから car, cdr, list メソッド。
def car(cell) cell.car end def cdr(cell) cell.cdr end def list(*args) return nil if args.empty? first, *rest = args cons(first, list(*rest)) end
puts car(cons(1, 2)) #=> 1 puts cdr(cons(1, 2)) #=> 2 puts cdr(cons(1, cons(2, 3))) #=> (2 . 3) puts list(1, 2, 3) #=> (1 . (2 . (3 . nil)))
リスト操作処理をいくつか。
def list_nth(xs, i) return car(xs) if i == 0 list_nth(cdr(xs), i - 1) end def list_size(xs, n = 0) return n if xs.nil? list_size(cdr(xs), n + 1) end def list_append(xs, x) return cons(x, nil) if xs.nil? first = car(xs) rest = cdr(xs) cons( first, list_append(rest, x) ) end
Ruby の Array っぽく使えるクラスを作ってみます。
起点となる cons セルを @cell
に保持しておいて、あとはさっき作った操作用メソッドを呼ぶだけ。
中身は Lisp でガワだけオブジェクト指向っぽく使えるようにした、みたいな感じでしょうか。
class ConsArray def initialize(*args) @cell = list(*args) end def size list_size(@cell) end def [](i) list_nth(@cell, i) end def <<(x) @cell = list_append(@cell, x) end def to_s @cell.to_s end end
それっぽく動くことがふんわり分かればよいだけなので、とりあえず size
[]
<<
だけ作ってみました。
同様に、Ruby の Hash っぽく使えるクラスも作ってみました。 ConsHash という名前が微妙ですね。
def alist_create(args) return nil if args.nil? first = car(args) second = car(cdr(args)) rest = cdr(cdr(args)) cons( cons(first, second), alist_create(rest) ) end def alist_get(alist, key) return nil if alist.nil? pair = car(alist) if car(pair) == key cdr(pair) else alist_get(cdr(alist), key) end end def alist_key?(alist, key) return false if alist.nil? pair = car(alist) if car(pair) == key true else alist_key?(cdr(alist), key) end end def alist_delete(alist, key) return if alist.nil? pair = car(alist) if car(pair) == key cdr(alist) else cons( pair, alist_delete(cdr(alist), key) ) end end def alist_set(alist, key, val) cons( cons(key, val), alist_delete(alist, key) ) end class ConsHash def initialize(*pairs) args = pairs.flatten @cell = alist_create(list(*args)) end def key?(key) alist_key?(@cell, key) end def [](key) alist_get(@cell, key) end def []=(key, val) @cell = alist_set(@cell, key, val) end def delete(key) @cell = alist_delete(@cell, key) end def to_s @cell.to_s end end