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

前の問題、検証不足と言いつつ次の問題に着手。append も append! もさほど時間がかからなかった。週末は脳の疲労が困憊状態だったのでしょうか。特に append! 方面は帰りのバスの中でさくっと出来た。

問題 5.22

まず append の定義は問題 3.12 によれば以下。

(define (append x y)
 (if (null? x)
     y
     (cons (car x) (append (cdr x) y))))

で、上記なレジスタ計算機のコードが以下。微妙な検証には一応パス。(何

(controller
 (assign cont (label done))
 loop
 (test (op null?) (reg x))
 (branch (label term))
 (save cont)
 (assign tmp (op car) (reg x))
 (save tmp)
 (assign cont (label after-cons))
 (assign x (op cdr) (reg x))
 (goto (label loop))
 after-cons
 (restore x)
 (assign val (op cons) (reg x) (reg val))
 (restore cont)
 (goto (reg cont))
 term
 (assign val (reg y))
 (goto (reg cont))
 done)

こっちはスタック使わざるを得ないのですが、以下の append! は

(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)
(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

繰返しな形で記述可能だのぅ、と思ってたら凄いコンパクトに書けた。

(controller
 (assign val (reg x))
 (assign ret (op cdr) (reg x))
 loop
 (test (op null?) (reg ret))
 (branch (label done))
 (assign ret (op cdr) (reg ret))
 (goto (label loop))
 done
 (perform (op set-cdr!) (reg ret) (reg y))
 )

これはこれは。って大丈夫かなぁ。
次のエントリは 5.4 節になってくると思うんですが、読むという作業が必要になってくるという意味では進捗が微妙になってくるかも。

追記

駄目ぢゃん。ret が微妙。以下でどうか。

(controller
 (assign val (reg x))
 (assign ret (reg x))
 loop
 (assign tmp (cdr ret))
 (test (op null?) (reg tmp))
 (branch (label done))
 (assign ret (op cdr) (reg ret))
 (goto (label loop))
 done
 (perform (op set-cdr!) (reg ret) (reg y))
 )

なんか違う気がしますが明日検証 (何

さらに追記

x が '() なケイスの考慮が抜けてます。スデに終わってるので明日追記ってコトで。(を

次の日

朝です。元の scheme なコードを見てみると last-pair に渡される x はリストが前提で書いてあるように見えるのでこのままにしとこ。(こら