iriya

iriyaのページ
－個人ページです。－

こんにちは iriya と申します．

SICPは2章の途中まで読んだことがあるのですが，1〜2年くらいずっと手つかずのままでした．
いい機会なので一緒に勉強させてもらいたいと思います．

SICPは翻訳したものを中心に使っていますが，よく分からない時は原書を読みます．
sicp.info というのがあって，Emacs で読めるので便利です．
http://www.neilvandyke.org/sicp-texi/

とりあえず環境とか書いておきますか．

PC: ThinkpadX61(NA7514I)
OS: Ubuntu7.10
エディター: GNU Emacs 22.1.1
処理系: Gauche 0.8.12

〜〜〜〜 以下 iriya の解答例 〜〜〜〜

Exercise 1.1

省略

Exercise 1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))
=>
-37/150

Exercise 1.3

再帰呼び出しによる解答

(define (sum-square-largest x y z)
  (cond ((and (< x y) (< x z)) ;; x is smallest
         (+ (* y y) (* z z)))
        (else (sum-square-largest y z x))))

詳しくは
http://lispuser.net/memo/lisp/2007-04-11-22-16.htmlを参照

Exercise 1.4

;; 例えば，
;; (a-plus-abs-b -3 -4)
;; => 1
;; となるが，これは b = -4 < 0 なので，if式の評価結果が - となり (- a b) と計算されたためである．
;; 評価モデルにおいて，演算子が組合せでも使える証拠になっている．

Exercise 1.5

作用的順序の評価
=> 無限ループ

正規順序の評価
=> 0

(test 0 (p)) において引数を評価すると，作用的順序であれば，0 を評価した後，(p) を評価する．
(define (p) (p)) より無限ループとなる．

正規順序であれば，(test 0 (p)) が展開されるので，if式の結果より 0 となる．

Exercise 1.6

new-if は通常の手続きなので，各要素を評価していく．
よって sqrt-iter を評価するので再帰的となり，無限ループに陥る．

Exercise 1.7

;; good-enough? テストがうまくいかない理由．
;; テキストにある good-enough? テストは以下のようなものである．
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))
;; また一番初めの予測値を 1.0 としている．

;; ここで以下の2つの場合の数を考える．

;; 小さい数字のとき，例えば1.0e-30を計算したいとする．
;;    このとき答えとして1.0e-15になってほしい．
;;    しかし improve による改善が十分に行われないうちに good-enough? が真を返す．
;;    これは good-enough? テストが，改善前の値と改善後の値を比較していないためである．
;;    小さい数の時に，単純に予測値の二乗と被開平数の差をとるだけならば，すぐに真が返ってしまう．

;; 大きい数字のとき，例えば1.0e30を計算したいとする．
;;    このとき答えとして1.0e15になってほしい．
;;    しかし，good-enough? テストで予測値の二乗を計算すると桁溢れがおこり，正しく計算できなくなる．

;; そこで guess の変化に注目して設計すると，大きい数，小さい数にたいして有効に働く．

(define (sqrt-iter old-guess new-guess x)
  (if (good-enough? old-guess new-guess x)
      new-guess
      (sqrt-iter new-guess (improve new-guess x)
                 x)))
(define (improve x y)
  (average x (/ y x)))
(define (average x y)
  (/ (+ x y) 2))
(define (good-enough? old-guess new-guess x)
  (< (abs (- 1.0 (/ old-guess new-guess))) 0.001))
(define (sqrt x)
  (sqrt-iter 1.0 x x))
(define (dis arg)
  (display arg)
  (newline))

(dis (sqrt 3.0))
=>
1.7320508100147274
(dis (sqrt 4.0))
=>
2.0000000929222947
(dis (sqrt 1.0e60))
=>
1.0000000031080746e30
(dis (sqrt 1.0e-12))
=>
1.0000001034612418e-6
(dis (sqrt 1.0e-48))
=>
1.0000000079534032e-24

Exercise 1.8

(define (cubic-root-iter old-guess new-guess x)
  (if (good-enough? old-guess new-guess x)
      new-guess
      (cubic-root-iter new-guess (improve new-guess x)
                     x)))
(define (improve new-guess x)
  (/ (+ (/ x (square new-guess)) (* 2 new-guess)) 3))
(define (square x) (* x x))
(define (good-enough? old-guess new-guess x)
  (< (abs (- 1.0 (/ old-guess new-guess))) 0.001))
(define (cubic-root x)
  (cubic-root-iter 1.0 x x))
(define (dis arg)
  (display arg)
  (newline))

(dis (cubic-root 8.0))
=>
2.000000001071189
(dis (cubic-root 1.0e90))
=>
1.0000000381223254e30
(dis (cubic-root 1.0e-90))
=>
1.0000000498918054e-30

Exercise 1.9

(define (inc x) (+ x 1))
(define (dec x) (- x 1))
;; recursive process
(define (plus-r a b)
  (if (= a 0)
      b
      (inc (plus-r (dec a) b))))
;; iterative process
(define (plus-i a b)
  (if (= a 0)
      b
      (plus-i (dec a) (inc b))))

Exercise 1.10

Ackermann関数はSICPの通り

(A 1 10)
=>
1024

(A 2 4)
=>
65536

(A 3 3)
=>
65536

;; (define (f n) (A 0 n))  => 2*n
;; (define (g n) (A 1 n))  => 2^n
;; (define (h n) (A 2 n))  => 2^2^2^2...