関数型言語の勉強にSICPを読もう - (30) 3章 - 標準部品化力、オブジェクトおよび状態 (138-151ページ)

新しい単語やよく聞くけど意味をきちんと理解できていない単語などが出てくる。(frames, bindings, unbound, enclosing environment, shadow)

問題3.9

再帰版は factorialの環境が横並びにできる。
反復版は factorialが1個、その横に fact-iterが横並び。

問題3.10

lambda板に比べてletはlambaが入れ子になっていると考えられるから、フレームが二重構造になっている。

lambda版は引数がフレーム束縛されていてそれが set! で変更されていたけど、letは1つ中のlambdaで束縛されている。

問題3.11

略。
絵を描くのは苦手です。

可変リスト構造

set-cdr!, set-car!とconsの違いについて。
このあたりは他の言語をやっているのでばっちり分かるよ。

問題3.12

1回目の(cdr x) は (b)。
2回目の(cdr x) は (b c d)になる。appendは x を変更してしまうのです。

問題3.13

make-cycleは手続き名のとおり輪を作る。
last pair の cdr が先頭の対を指すようになる。
(last-pair z)は無限ループ。

問題3.14

これは結構悩んだ。
loopの第一引数だったものがloopの中のloopで第二引数になっているのがポイントで結果としては逆順にソートされると思う。
破壊的にソートするので 最後に (display v)したら (a)とかなっていてこれには気づかなかった。

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

(define v (list 'a 'b 'c 'd))
(display v)

(define w (mystery v))
(display w)
(display v)

問題3.15

今まで意識していなかったけど、共有でいろいろとはまりそうなのは他の言語と同じなんだな。
略。

問題3.16

何も返さないってのがかなり悩んだ。
何も返さない=0だと思っていたのだけど、良く考えたら無限ループの事を指していることに気づいた。

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

;; 3
(define a (cons 'x (cons 'x (cons 'x 'x))))
(display (count-pairs a))
(display "\n")

;; 4
(define a (cons 'x 'x))
(define b (cons 'y a))
(define c (cons a b))
(display (count-pairs c))
(display "\n")

;; 7
(define a (cons 'x 'x))
(define b (cons a a))
(define c (cons b b))
(display (count-pairs c))
(display "\n")

;; nothing
(define a (cons 'x 'x))
(set-cdr! a a)
(display (count-pairs a))

※「SICPを読もう」の目次はこちら


計算機プログラムの構造と解釈
Gerald Jay Sussman Julie Sussman Harold Abelson 和田 英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404