consごっこ



表面だけ見ると Ruby の Array、 Hash っぽいけど中身は cons セル、というものを書いてみました。

試してみたくなって、なんとなく書いてみた、という感じのものです。 cons セルさえあれば基本的なデータ構造が作れてなんとかなるんだな、という感触がふんわり得られればOK。 なので、効率の悪さは無視します。

あまり調べずに適当に書いたので、一般的な LispScheme とは命名や動作が微妙に違っている気がします。


まず 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