SICPのexcercise 3.21から3.27

• どっかに記録を残しておかないとどこやったか忘れてしまうのでメモ。

3.16

listの中のペアの数を数える関数count-pairの間違った実装が与えられるので、間違った答えを出すような反例を作れという問題。

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

(define (f1)
  (define p1 '(1 . 2))
  (define p2 '(3 . 4))
  (define p3 '(5 . 6))
  (set-cdr! p1 p2)
  (set-cdr! p2 p3)
  p1)
(count-pairs (f1))

(define (f2)
  (define p1 '(1 . 2))
  (define p2 '(3 . 4))
  (define p3 '(5 . 6))
  (set-cdr! p1 p2)
  (set-cdr! p2 p3)
  (set-car! p2 p3)
  p1)
(count-pairs (f2))

(define (f3)
  (define p1 '(1 . 2))
  (define p2 '(3 . 4))
  (define p3 '(5 . 6))
  (set-cdr! p1 p2)
  (set-cdr! p2 p3)
  (set-car! p1 p2)
  (set-car! p2 p3)
  p1)
(count-pairs (f3))

(define (f4)
  (define p1 '(1 . 2))
  (define p2 '(3 . 4))
  (define p3 '(5 . 6))
  (set-cdr! p1 p2)
  (set-cdr! p2 p3)
  (set-cdr! p3 p1)
  p1)
(count-pairs (f4))

3.17

さっきのcount-pairsを正しくしろという問題。

(define (count-pairs x)
  (define (in? ls b)
    (cond ((eq? '() ls) #f)
	  ((eq? (car ls) b) #t)
	  (else (in? (cdr ls) b))))
  (define visited '())
  (define (iter a)
    (cond
     ((pair? a) (cond ((in? visited a) 0)
		      (begin
			(set! visited (cons a visited))
			(+ 1
			   (iter (car a))
			   (iter (cdr a))))))
     (else 0)))
  (iter x))

3.18

cdr cdr cdr と辿ると無限ループになってしまうようなリストかどうかを検査せよという問題。

(define (loop? ls)
  (define (in? ls b)
    (cond ((eq? '() ls) #f)
	  ((eq? (car ls) b) #t)
	  (else (in? (cdr ls) b))))
  (define visited '())
  (define (iter ls2)
    (cond ((eq? ls2 '()) #f)
	  ((in? visited ls2) #t)
	  (else
	   (begin
	     (set! visited (cons ls2 visited))
	     (iter (cdr ls2))))))
  (if (pair? ls) (iter ls) #f))

3.21

本文中のqueueの実装に合わせたプリンターを実装する問題

(define (print-queue q)
  (define (iter p)
    (if (null? p)
	()
	(cons (car p) (iter (cdr p)))))
  (iter (front-ptr q)))

3.27

schemeで以下のようにメモ化を実装。

(define (memoize f)
  (let ((table (make-table))) ; [b]
    (lambda (x) ; [c]
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

この時、

(define memo-fib
  (memoize (lambda (n) ; [a]
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

はきちんとメモ化された動作をするけど、

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
(define memo-fib-2 (memoize fib))

は駄目な理由を考えようという問題。
memo-fibがどういう素性の物かを考える。

• まず、[a]のmemoize呼び出しで、global environmentをenclosing environmentとするenvironment Aが作成される。
• さらに、この中で、[b]のletによってAをenclosing environmentとするenvironment Bが作成される。
• メモの実体となるtableは、environment Bの中に作成される。
• memo-fibの実体=[a]のmemoize呼び出しの返り値=[b]のletの返り値=[c]のlambda式による関数オブジェクト。
  • このオブジェクトはenvironment Bの中に作成されている。
• 従って、memo-fibの実際の呼び出しでは、environment Bをenclosing envirionmentとする環境が作成され、その中で評価が実行される。
  • 故に、environment Bの中のtableを参照してメモを読み出す事が可能。

同様に、memo-fib-2がどういう素性の物かを考える。

• fibは、再帰呼び出しでfibを呼ぶ。
• fibは、メモ化されずに定義されている関数である。
• 従って、memo-fib-2を呼び出すと、最初の1回だけはテーブルを参照しに行くけれども、再帰的に呼び出されるfibの中ではメモの検索は行われないので、結局メモ化の有難味が無い。
  • 但し、(memo-fib-2 3) (memo-fib-2 3)と同じ引数で複数回評価すると、2回目以降の評価ではメモの値が返される。
  • 最上位のfib呼び出しだけはメモ化されているから。

memoizeを

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
	(if previously-computed-result (print x " is found.")
	    (print x " is not found"))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

のように書き換えると確かめられる。