consごっこ (2)

Ruby Lisp

前

consのデータをメモリに置くとどうなるのか、というのを軽く試してみるつもりだったのが、 もうちょっと育ってしまいました。

※ C言語云々と言っているところはかなりうろ覚えで適当です。だいぶ忘れてます……。

※ また、既存のよく知られた何かに準拠している訳ではなく、思いつきで作った適当なものです。 実際の Lisp 処理系が以下のようになっているのかよく分かってません。 どうなってるんでしょうか。

  • メモリはただの配列
    • 添字がアドレス
    • 内容は整数（値またはアドレス）
  • 整数は1つのアドレスを占有する
  • consセルは car と cdr で隣接した2つのアドレスを占有する

初期状態:

（アドレス: 内容）
0: nil ... 0番地は nil を表す。変更しない。
1: nil ... 未使用。以下同じ
2: nil
...

assign_int(:a, 11) assign_int(:b, 22) を実行すると、空いている場所に値が入れられ、変数に束縛される。

C言語だと int a = 11; int b = 22; みたいな感じ？

0: nil
1: 11 ... a
2: 22 ... b
3: nil
...

値のアドレスを使って cons セルを作成。

cons セルの car部、cdr部には必ずアドレスを入れる（即値は入れない）。 car と cdr は隣接して配置する（car のアドレスの次の番地が cdr）。

C言語だと cons* c1 = cons(&a, &b); みたいな感じ？

0: nil
1: 11 ... a
2: 22 ... b
3: 1 ... c1 の car
4: 2 ... c1 の cdr
5: nil
...
  • c1 の car のアドレスは 3（内容＝参照先アドレスは 1）
  • c1 の cdr のアドレスは 4（内容＝参照先アドレスは 2）
  • それぞれの参照先アドレスを辿ると aの値=11, bの値=22 が得られる。

……というところから出発して、 ついでに free みたいなこともできる？   変数名の管理が必要？   ついでに GC ぽいものも作れる？   ……などと思いつきでいじってたら以下のようになりました。

  • $env で変数名と型（数またはcons）、アドレスの対応を管理
※ こういうイメージ
$env:
  a:
    type: int
    addr: 1
  b:
    type: int
    addr: 2
  c1:
    type: cons
    addr: 3 ... consセルの先頭アドレス

  • $in_use_flags で各番地ごとの使用・未使用を管理

    • 使用中の場合 true
    • 初期状態では 0 番地のみ true

  • unbind

    • free っぽい何か？
    • unbind(name) では $env からキー（変数名）を削除するだけ

  • sweep

    • GC っぽい何か？
    • 参照されている（＝使われている）アドレスは $env を見るとすべて分かる
    • それ以外のアドレスのフラグを false にする

  • 領域の確保と変数の束縛

    • メモリを先頭から見ていって、必要なサイズの領域が未使用だったらそこを使う
      • 未使用かどうかは $in_use_flags を見て判断
    • 領域確保時に $in_use_flags のフラグを true に更新
    • allocate(size) すると、確保した領域の先頭のアドレスを返す
    • $env に登録（束縛）
class EnvItem
  attr_reader :type, :addr

  def initialize(type, addr)
    @type = type # :int | :cons
    @addr = addr
  end

  def to_s
    "(#{@type} #{@addr})"
  end
end

def all_free?(addrs)
  addrs.all? { |addr| $in_use_flags[addr] == false }
end

def find_free_addr(size)
  addrs =
    (1...$in_use_flags.size)
      .each_cons(size)
      .find { |addrs| all_free?(addrs) }

  if addrs.nil?
    raise "no free space"
  end

  addrs[0]
end

def allocate(size)
  addr = find_free_addr(size)
  (0...size).each { |offset|
    $in_use_flags[addr + offset] = true
  }
  addr
end

def assign_int(name, val)
  addr = allocate(1)
  $mem[addr] = val
  $env[name] = EnvItem.new(:int, addr)
  addr
end

def assign_cons(name, car_addr, cdr_addr)
  addr = allocate(2)
  $mem[addr    ] = car_addr
  $mem[addr + 1] = cdr_addr
  $env[name] = EnvItem.new(:cons, addr)
  addr
end

def unbind(name)
  $env.delete(name)
end

def sweep
  in_use_addrs =
    $env.values
      .flat_map { |item|
        case item.type
        when :int
          [item.addr]
        when :cons
          [item.addr, item.addr + 1]
        end
      }

  (1...$mem.size)
    .reject { |addr| in_use_addrs.include?(addr) }
    .each { |addr| $in_use_flags[addr] = false }
end

def name_to_addr(name)
  $env[name].addr
end

def dump_mem
  $mem.zip($in_use_flags).each_with_index { |x, i|
    val, in_use_flag = x
    puts "% 4d %s %s" % [i, in_use_flag ? "*" : " ", val.inspect]
  }
end

初期化:

MEM_SIZE = 14
$mem = Array.new(MEM_SIZE)
$in_use_flags = Array.new(MEM_SIZE){ false }

NIL_ADDR = 0
$mem[NIL_ADDR] = nil
$in_use_flags[NIL_ADDR] = true

$env = {}

# 変数 a, b, c を assign
assign_int(:a, 11)
assign_int(:b, 22)
assign_int(:c, 33)

unbind(:b) # ... まだフラグは true のままで、$env から消えるだけ
sweep() # ... b のアドレスのフラグが false になる

# b が使っていた場所が空いているので、そこが使われる
assign_int(:d, 44)

変数を使ってリストを作成。

# c1, c2, c3 を assign
assign_cons(:c1, name_to_addr(:a), NIL_ADDR)
assign_cons(:c2, name_to_addr(:d), name_to_addr(:c1))
assign_cons(:c3, name_to_addr(:c), name_to_addr(:c2))

# 変数の場合と同様に unbind/sweep して c3 をなかったことに
unbind(:c3)
sweep()

# c3 が使っていた場所が空いているので、そこが使われる
assign_cons(:c4, name_to_addr(:c), name_to_addr(:c2))

この状態でメモリと使用状況をダンプするとこう（* が付いているものが使用中）:

   0 * nil
   1 * 11 ... a
   2 * 44 ... d
   3 * 33 ... c
   4 * 1  ... c1 の car => a のアドレス
   5 * 0  ... c1 の cdr => nil
   6 * 2  ... c2 の car => d のアドレス
   7 * 4  ... c2 の cdr => c1 の先頭アドレス
   8 * 3  ... c4 の car => c のアドレス
   9 * 6  ... c4 の car => c2 の先頭アドレス
  10   nil
  11   nil
  12   nil
  13   nil

c4 からリストをたどってみる:

def walk_list(addr)
  puts "--------"

  if addr == NIL_ADDR
    puts "リストの終端に達した"
    return
  end

  car_pos = addr
  cdr_pos = addr + 1
  puts "car の位置: #{car_pos}"
  puts "cdr の位置: #{cdr_pos}"

  car_content = $mem[car_pos]
  cdr_content = $mem[cdr_pos]
  puts "car の内容（参照先アドレス）: #{car_content}"
  puts "cdr の内容（参照先アドレス）: #{cdr_content}"

  # car の内容（参照先アドレス）を使った操作
  puts "★ car: #{ $mem[car_content] }"

  # cdr の内容（参照先アドレス）を使った操作
  walk_list(cdr_content)
end

walk_list(name_to_addr(:c4))

結果:

--------
car の位置: (Addr 8)
cdr の位置: (Addr 9)
car の内容（参照先アドレス）: (Addr 3)
cdr の内容（参照先アドレス）: (Addr 6)
★ car: 33
--------
car の位置: (Addr 6)
cdr の位置: (Addr 7)
car の内容（参照先アドレス）: (Addr 2)
cdr の内容（参照先アドレス）: (Addr 4)
★ car: 44
--------
car の位置: (Addr 4)
cdr の位置: (Addr 5)
car の内容（参照先アドレス）: (Addr 1)
cdr の内容（参照先アドレス）: (Addr 0)
★ car: 11
--------
リストの終端に達した

動きますね。

ためしに、unbind のたびに sweep するのをやめて最後に1回だけ sweep を実行した場合:

   0 * nil
   1 * 11
   2   22
   3 * 33
   4 * 44
   5 * 1
   6 * 0
   7 * 4
   8 * 5
   9   3
  10   7
  11 * 3
  12 * 7
  13   nil

歯抜けになりました（これはこれで期待通り）。

ふーむ……こんなんでいいんでしょうか。