ページ数かぞえ間違えた。まだ半分いってないや。ようやく3.3節に入ったところ。

実は、3章に入ってしばらく、いまいち面白くなかった。主な原因は、set! の使い方を覚えましょう的な雰囲気にあると思う。語弊のない言い方をすると、set! を通して Scheme を深く理解するきっかけをつかむ、っていうところかなあ。ここから先の解説は、関数型プログラミングというより、「コンピュータから見た（Scheme の）プログラム」なのかもしれない。ああ、そもそもそういう趣旨の書名だったか。

もしかしたら、関数型プログラミングにだけ興味がある人は、2章まで読めば十分なのかもしれない。

もちろん、まったく面白くないわけではない。当たり前だけど。ようするに自分が知らないことを気づかせてくれれば面白いので、たとえば exercise 3.16～3.17 は、リストの本当の姿、つまり cons セルとしての姿を実感させてくれて面白い。

リスト x = (a b c) には、いくつの cons セルがあるか。SICPでは、まずナイーブな方法が例示されている。

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))
(define x (list 'a 'b 'c))

gosh> (count-pairs x)
3

これの何が問題かっていうと、リスト内の cons セルを示している car や cdr がある場合に意図した答えにならないこと。

gosh> (set-car! x (cdr x))
gosh> (count-pairs x)
5

自分は、絵を書かないとわからなかった。最初、x はこうなっている。!は、下向き矢印↓のつもり。

x-->|*|*|-->|*|*|-->|*|/|
     !       !       !
    |a|     |b|     |c|

たしかに、consセルが3つある。ここで、(set-car! x (cdr x)) すると、x のリスト表記は ((b c) b c) になる。絵で書くと、こう。

     ________
     |       !
x-->|*|*|-->|*|*|-->|*|/|
             !       !
            |b|     |c|

これを count-pairs で調べると、2個目の cons セルより後ろを2回数えてしまうので、実際の cons セルは 3 つのままなのに結果が5になる。ちなみに、消えた a については忘れていい。キーワードはガーベジコレクションらしい。

この問題を回避する count-pairs を書けというのが exercise 3.17。同じやつを2回数えなければいいだけなんだけど、「同じ」って何？という哲学的な命題と対峙しなければいけない。実際には哲学ではないので、eq? の本当の意味を理解しているかどうかがポイントになるんだと思う。僕の回答。

;; ex. 3.17
(define (count-pairs x)
  (define aux-pairs '())
  (define (member-eq? c ls)
    (cond ((or (null? ls) (null? (cdr ls)) (null? c)) #f)
          ((eq? c (car ls)) #t)
          (else
           (member-eq? c (cdr ls)))))
  (define (aux-count x)
    (cond ((not (pair? x))
           '())
          ((member-eq? x aux-pairs)
           '())
          (else
           (set! aux-pairs (cons x aux-pairs))
           (append (aux-count (car x))
                   (aux-count (cdr x))))))
  (aux-count x)
  (length aux-pairs))

gosh> (count-pairs x)
3

こんな小さな問題で、やたらにいろいろなことが示唆されているので、やめられない。
これなら、(set-cdr! (cddr x) x) みたいな循環しているリストに対しても、正しい答えが得られる。一見すると終わりがないものにケリをつける方法っていうのは、それだけで魔法みたいで、やっぱりやめられない。

ちなみにこんなことをわざわざ書いているのは、独習で不足しがちな「説明してみることで自分の理解度を確認する」という作業を補っているだけです。Webって本当に便利ですね。したがって、あらゆる記事は、きちんと理解した人間による解説ではありません。