SICP 3.3.1をのんびり自習
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! はポインタ操作をするからだ。それらは決して値そのものを扱っているのではない。これらを使う際は、必ずポインタ図を描きながらプログラムを書く必要がある。