SICP 読み (278) 5.3 記憶の割り当てとごみ集め
昨晩、力尽きてるなぁ。どこまでヤッたんでしょうか (ため息
てーか、自分で見返してみても意味が分かりにくい。通過したラベルと属性値だけ列挙してみます。微妙なエントリになる可能性大。
イチからリトライ、って昨晩と同じトコで力尽きたら笑うな。まずは最初の状態。
gosh> the-cars (p4 n3 x n4 n1 x n2) gosh> the-cdrs (p1 p3 x e0 p6 x e0) gosh> new-cars () gosh> new-cdrs ()
で、begin-garbage-collection が済んだ時点でのレジスタの値は以下。
- free : 0
- scan : 0
- old : 0 (root)
- new : - (最初の assign は pair な手続き)
- cont : reassign-root
この後
- 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)
- new : 0
- cont : reassign-root
次に jmp するのは gc-loop になる。あと、root レジスタの値は new-{car, cdr} の先頭って思ってて良いのかな。gc-loop な処理が終了した時点では *-c?r は変化ナシ。レジスタの値は以下になっているはず。
- free : 1
- scan : 0
- old : 4 (the-c?r の p4)
- new : 0
- cont : update-car
で
- relocate-old-result-in-new
- pair
の後には update-car に jmp するんですが、jmp 直前の *-c?r の状態が以下。
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 : 4 (the-c?r の p4)
- new : 1 (new-c?r の p1)
- cont : update-car
これで update-car に jmp して一連の手続きが終わったら
gosh> the-cars (b n3 x n4 b x n2) gosh> the-cdrs (p0 p3 x e0 p1 x e0) gosh> new-cars (p1 n1) gosh> new-cdrs (p1 p6) gosh>
あるいはレジスタが以下。
- free : 2
- scan : 0
- old : 1 (the-c?r の p1)
- new : 1 (new-c?r の p1)
- cont : update-cdr
この後は
- relocate-old-result-in-new
- pair
な命令が実行された後に update-cdr に jmp しますが、jmp 直前の状態が以下。
gosh> the-cars (b b x n4 b x n2) gosh> the-cdrs (p0 p2 x e0 p1 x e0) gosh> new-cars (p1 n1 n3) gosh> new-cdrs (p1 p6 p3) gosh>
レジスタは以下
- free : 3
- scan : 0
- old : 1 (the-c?r の p1)
- new : 2 (new-c?r の p2)
- cont : update-cdr
この状態から update-cdr した直後の状態は以下になる。
gosh> the-cars (b b x n4 b x n2) gosh> the-cdrs (p0 p2 x e0 p1 x e0) gosh> new-cars (p1 n1 n3) gosh> new-cdrs (p2 p6 p3) gosh>
レジスタは以下
- free : 3
- scan : 1
- old : 1 (the-c?r の p1)
- new : 2 (new-c?r の p2)
- cont : update-cdr
これで new-* の最初の要素が完全な状態に。これで gc-loop に jmp らしい。gc-loop 終了時のレジスタの内容が以下。
- free : 3
- scan : 1
- old : n1
- new : 2 (new-c?r の p2)
- cont : update-car
これで relocate-old-result-in-new に jmp するんですが、これは pair に branch しないパターンだな。relocate (略) の終了時のレジスタの状態が以下
- free : 3
- scan : 1
- old : n1
- new : n1
- cont : update-car
で、update-car に jmp ッスか??
って同じ値 (取り出したものを再度セットしている) なのか。このあたりは微妙なハンドル入ってそうでいやらしいなぁ。(何
ええと pair の場合の update-car は new-car の要素のアドレスで書き換えなんだけど、pair じゃない場合は new に現在の値を入れとく訳か。update-car 終了時点のレジスタの状態 (*-c?r は変更ないはずなので略) は以下
- free : 3
- scan : 1
- old : p6 (the-c?r の p6)
- new : n1
- cont : update-cdr
で、relocate-(略) に jmp して pair 終了時点のナニが以下
gosh> the-cars (b b x n4 b x b) gosh> the-cdrs (p0 p2 x e0 p1 x p3) gosh> new-cars (p1 n1 n3 n2) gosh> new-cdrs (p2 p6 p3 e0) gosh>
レジスタが以下
- free : 4
- scan : 1
- old : p6 (the-c?r の p6)
- new : p3 (new-c?r の p3)
- cont : update-cdr
で、update-cdr なんですが終了時点の状態が以下になる、と
gosh> the-cars (b b x n4 b x b) gosh> the-cdrs (p0 p2 x e0 p1 x p3) gosh> new-cars (p1 n1 n3 n2) gosh> new-cdrs (p2 p3 p3 e0) gosh>
レジスタが以下
- free : 4
- scan : 2
- old : p6 (the-c?r の p6)
- new : p3 (new-c?r の p3)
- cont : update-cdr
これで再度 gc-loop に戻る訳ですか。なんとなく順調。gc-loop 終了時点のレジスタの状態は以下になっているはず
- free : 4
- scan : 2
- old : n3
- new : p3 (new-c?r の p3)
- cont : update-car
で、relocate (略) では old が pair でないので new も n3 になって update-car 終了時点のナニが以下になるはず (*-c?r は変更されないので略)
- free : 4
- scan : 2
- old : p3 (the-c?r の p3)
- new : p3 (new-c?r の p3)
- cont : update-cdr
なんとなくスッ飛ばしてしまいそうな感じがする。気を付けて追い掛ける。ここから relocate-(略) に jmp するんですが、pair 終了時の状態は以下のはず。
gosh> the-cars (b b x b b x b) gosh> the-cdrs (p0 p2 x p4 p1 x p3) gosh> new-cars (p1 n1 n3 n2 n4) gosh> new-cdrs (p2 p3 p3 e0 e0) gosh>
レジスタが以下
- free : 5
- scan : 2
- old : p3 (the-c?r の p3)
- new : p4 (new-c?r の p4)
- cont : update-cdr
これで全ての要素は移動できましたが、new-* のポインタがまだ微妙。ここで update-cdr したらほぼ終了なのかな。update-cdr 終了時点のソレは以下
gosh> the-cars (b b x b b x b) gosh> the-cdrs (p0 p2 x p4 p1 x p3) gosh> new-cars (p1 n1 n3 n2 n4) gosh> new-cdrs (p2 p3 p4 e0 e0) gosh>
レジスタが以下
- free : 5
- scan : 3
- old : p3 (the-c?r の p3)
- new : p4 (new-c?r の p4)
- cont : update-cdr
で、gc-loop に戻る。終了時点のレジスタの状態が以下
- free : 5
- scan : 3
- old : n2
- new : p4 (new-c?r の p4)
- cont : update-car
で、これ以降は car も cdr も pair ではないのでさくさく進んで scan が 5 になって終了、ですね。良かった良かった。
失恋対がある場合
もやっとこ。まず *-c?r な初期値を以下としてみます。
gosh> the-cars (p5 p5 n3 x n4 n1 x n2) gosh> the-cdrs (p1 p2 p4 x e0 p7 x e0) gosh> new-cars () gosh> new-cdrs ()
これはこんな状態だと思ってるんですが良いのだろうか。
gosh> (define l1 '(1 2)) l1 gosh> (define l2 '(() 3 4)) l2 gosh> (set-car! l2 l1) #<undef> gosh> (define l '(() ())) l gosh> (set-car! l l1) #<undef> gosh> (set-cdr! l l2) #<undef> gosh> l (#0=(1 2) #0# 3 4) gosh>
なんか違う気がする。とりあえず正誤はスルーとして順に見ていきます。レジスタの初期値はさっきと同じで良いはず。
- free : 0
- scan : 0
- old : 0 (root)
- new : - (最初の assign は pair な手続き)
- cont : reassign-root
この状態から relocate-(略) に突入。pair 終了時にどうなるかというと以下。
gosh> the-cars (b p5 n3 x n4 n1 x n2) gosh> the-cdrs (p0 p2 p4 x e0 p7 x e0) gosh> new-cars (p5) gosh> new-cdrs (p1)
以下がレジスタ
- free : 1
- scan : 0
- old : p0 (the-c?r の p0)
- new : p0 (new-c?r の p0)
- cont : reassign-root
大丈夫かな。で、gc-loop の終了時点なレジスタが以下
- free : 1
- scan : 0
- old : p5 (the-c?r の p5)
- new : p0 (new-c?r の p0)
- cont : update-car
で、relocate-(略) に jmp して pair 終了時点なソレが以下
gosh> the-cars (b p5 n3 x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p5 n1) gosh> new-cdrs (p1 p7)
以下がレジスタ
- free : 2
- scan : 0
- old : p5 (the-c?r の p5)
- new : p1 (new-c?r の p1)
- cont : update-car
次の update-car 終了時点の状態が以下
gosh> the-cars (b p5 n3 x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1) gosh> new-cdrs (p1 p7)
以下がレジスタ
- free : 2
- scan : 0
- old : p1 (the-c?r の p1)
- new : p1 (new-c?r の p1)
- cont : update-cdr
で、再度 relocate-(略) に jmp して pair 終了時点の状態が以下。ここで失恋対が登場するはず。ただ、ここでは単純にコピるだけなのか。
gosh> the-cars (b b n3 x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1 p5) gosh> new-cdrs (p1 p7 p2)
以下がレジスタ
- free : 3
- scan : 0
- old : p1 (the-c?r の p1)
- new : p2 (new-c?r の p2)
- cont : update-cdr
で、update-cdr 終了時の状態が以下
gosh> the-cars (b b n3 x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1 p5) gosh> new-cdrs (p2 p7 p2)
以下がレジスタ
- free : 3
- scan : 1
- old : p1 (the-c?r の p1)
- new : p2 (new-c?r の p2)
- cont : update-cdr
失恋対な処理に行くまでもう少しかかるな。これで gc-loop に jmp して終了時点のレジスタの状態が以下
- free : 3
- scan : 1
- old : n1
- new : p2 (new-c?r の p2)
- cont : update-car
ちょっとスルーして update-car 終了時のレジスタの状態が以下になる (*-c?r は変わらない)
- free : 3
- scan : 1
- old : p7 (the-c?r の p7)
- new : p2 (new-c?r の p2)
- cont : update-cdr
げ、p7 かよ、と言いつつ relocate-(略) 方面に去って pair 終了時の状態が以下
gosh> the-cars (b b n3 x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1 p5 n2) gosh> new-cdrs (p2 p7 p2 e0)
以下がレジスタ
- free : 4
- scan : 1
- old : p7 (the-c?r の p7)
- new : p3 (new-c?r の p3)
- cont : update-cdr
で、update-cdr 終了後は以下になる
gosh> the-cars (b b n3 x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1 p5 n2) gosh> new-cdrs (p2 p3 p2 e0)
以下がレジスタ
- free : 4
- scan : 2
- old : p7 (the-c?r の p7)
- new : p3 (new-c?r の p3)
- cont : update-cdr
やれやれ、と言いつつ gc-loop に戻って終了した瞬間のレジスタが以下
- free : 4
- scan : 2
- old : p5 (the-c?r の p5)
- new : p3 (new-c?r の p3)
- cont : update-car
を、ようやくキたな。relocate-(略) 方面に去るんですが、broken-heart は pair 認定で良いよな。already-moved が終わった時点でのレジスタの状態が以下
- free : 4
- scan : 2
- old : p5 (the-c?r の p5)
- new : p1 (new-c?r の p1)
- cont : update-car
で、update-car に jmp して終わったらどうなるか、というと
gosh> the-cars (b b n3 x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1 p1 n2) gosh> new-cdrs (p2 p3 p2 e0)
- free : 4
- scan : 2
- old : p2 (the-c?r の p2)
- new : p1 (new-c?r の p1)
- cont : update-cdr
で、再度 relocate-(略) 方面に去った後のナニが以下
gosh> the-cars (b b b x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1 p1 n2 n3) gosh> new-cdrs (p2 p3 p2 e0 p4)
- free : 5
- scan : 2
- old : p2 (the-c?r の p2)
- new : p4 (new-c?r の p4)
- cont : update-cdr
で、update-cdr で new-cdr の p2 を p4 にして scan が加算で以下
gosh> the-cars (b b b x n4 b x n2) gosh> the-cdrs (p0 p2 p4 x e0 p1 x e0) gosh> new-cars (p1 n1 p1 n2 n3) gosh> new-cdrs (p2 p3 p4 e0 p4)
- free : 5
- scan : 3
- old : p2 (the-c?r の p2)
- new : p4 (new-c?r の p4)
- cont : update-cdr
ここから先はスルーで良いかな。ちょっとフン詰まりがヌケてすっきり感満点って感じがします。わははは。
蛇足
都合二時間の現実トウヒでありました。ちょっとヤリ杉。
