読者です 読者をやめる 読者になる 読者になる

SICP 3.3.1をのんびり自習

Scheme

SICPのサブセクション3.3.1を自習する。
まずは、last-pair, append! を教科書通り実装する。

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

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

(define a (list 1 2))
(define b (list 3 4))

(append! a b)
=>(1 2 3 4)

a
=>(1 2 3 4)

b
=>(3 4)

よし、ちゃんと動作している。
教科書的にはここまでの動作確認だが、
もうちょっと色々試してみる。
もう1回、append!してみる。

(append! a b)
=> (1 2 . #0=(3 4 . #0#))

a
=> (1 2 . #0=(3 4 . #0#))

何やら怪しげな値が返ってきた。???なんだこれ?
さらに試してみる。

(append! (list 1 2) b)
=> (1 2 . #0=(3 4 . #0#))

bにループができている気がする。

b
=> #0=(3 4 . #0#)

(cdr b)
=> #0=(4 3 . #0#)

(cddr b)
=> #0=(3 4 . #0#)

(cdddr b)
=> #0=(4 3 . #0#)

やはりaにもbループができている。うひょー。こんなつもりじゃなかったんだ。

私が期待(予想)していた動作は、通常のappendと同じ動作。通常の関数型appendは以下のように動作する。
(define a (list 1 2))
=> a

(define b (list 3 4))
=> b

(append a b)
=>(1 2 3 4)

(append a b b)
=>(1 2 3 4 3 4)

(define c (append a b))
=>c

c
=>(1 2 3 4)

(append c b)
=>(1 2 3 4 3 4)

なぜ動作が違うのだろうか?原因は簡単に予想がつく。命令型append!はポインタ操作set-cdr!を使っているから、2回目の(append! a b)でループができてしまったのだろう。SICPのポインタの図示方法に従ってポインタ図を描けば、確かに2回目でループができる。

もう一個、試しに、
(define d (list 1 2 3))
=> d

(append! d d)
=> #0=(1 2 3 . #0#)

これも、ループする。
注意して扱わないと、バグのゴキブリホイホイ状態になりそうな予感がする。

【結論】命令型append!と関数型appendは、異なる動作をするケースがある。なぜなら命令型のset-car!, set-cdr! はポインタ操作をするからだ。それらは決して値そのものを扱っているのではない。これらを使う際は、必ずポインタ図を描きながらプログラムを書く必要がある。