SICP 読み (277) 5.3 記憶の割り当てとごみ集め

SICP scheme

頑張ってトレイスかけてみます。トリビア面白スギでヤレるかどうか微妙ッス。紙ベースで途中までヤッてるんですが、メモに愚痴が色々書いてある。

  • relocate-old-result-in-new の test な pointer-to-pair? 微妙スギ
  • 数値なのかポインタなのかが分からん

等など。とりあえず基本的にはポインタだという事で無理矢理 (以下略
それは良いとして broken heart が無いパターンから。例示されているナニを基に以下のような感じ

(define the-cars '(p4 n3 x n4 n1 x n2))
(define the-cdrs '(p1 p3 x e0 p6 x e0))
(define new-cars '())
(define new-cdrs '())

で、おそらく途中までになると思いますがなんとかログを残してみます。まず

  • begin-garbage-collection
  • relocate-old-result-in-new
  • pair
  • reassign-root

なラベルの手続きまでが済んだ時点での状態としては

gosh> the-cars
(b n3 x n4 n1 x n2)
gosh> the-cdrs
(p0 p3 x e0 p6 x e0)
gosh> new-cars
(p4)
gosh> new-cdrs
(p1)
gosh>

で、それぞれの変数の状態は

  • free : 1
  • scan : 0
  • old : 0 (root)
  • cont : reassign-root
  • new : 0 (free)

な感じ。oldcr と root はスルーで。この時点のポイントとしては new-* なソレに先頭要素が移動したけど、参照しているポインタは元のまま、という事。これをこの後に解決する感じ。reassign-root で root が設定された後は

  • gc-loop
  • relocate-old-result-in-new
  • pair

が順に処理されるんですが、gc-loop 内で old に new-cars の先頭要素が設定されております。で、relocate-continue に update-car が設定されて relocate (ry が。
上記の pair が終わった時点での状態は、というと

gosh> the-cars
(b n3 x n4 b x n2)
gosh> the-cdrs
(p0 p3 x e0 p1 x e0)
gosh> new-cars
(p4 n1)
gosh> new-cdrs
(p1 p6)
gosh>

になっていてこの時点での主要な変数の状態は

  • free : 2
  • scan : 0
  • old : p4 (ポインタ)
  • cont : update-car
  • new : 1 (free)

な形のはず。
現時点で把握しているのは、この後に先頭要素の cdr が new-{car, cdr} に格納されて先頭要素の参照先が new-{car, cdr} なアドレスになれば (以下略
ここまでが現時点で追い掛けきれている全部です。別途最後まできちんと見切れて、失恋対な例まで見切ったログが残れば満足なんですが、今日はもう駄目ッス。