SICP読書録 #3 1.1.7 ニュートン法による平方根 -1.1.8 ブラックボックス抽象化としての手続き

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

1.1.7 例：ニュートン法による平方根

1.1.7.scm

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x) x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.0001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

数値xの平方根の推定値としてyがあるとき、yとx/yの平均を取ることでより良い推定値に更新できる。これを誤差が閾値より小さくなるまで繰り返す。

ループも使わず（再帰だけで）これだけの手続きが書けるんだぜ。

練習問題 1.6

ifが特殊形式でなければならないのはなぜか？

特殊形式とは、一般評価規則に従わない式。

(if <predicate> <then-clause> <else-clause>)

predicateが真の場合のみthen-clauseが評価され、そうでない場合のみelse-clauseが評価される。つまり、全てのオペランドが評価されてから手続きが呼ばれる、という一般評価規則には従わない。

そこんとこをよく理解していないAlyssa P. Hacker氏は、以下のような自家製ifを定義した。

ex1.1.6_0.scm

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

これを使って、先のsqrtを書き直すと、何が困るか？

ex1.1.6_1.scm

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x) x)))

else-claseが常に評価されるので再帰が終了せず、無限ループに陥る。

練習問題1.7

十分に良い推定値かどうかを判定するgood-enough?は、とても小さい数またはとても大きい数に対してはうまく動作しない。

ex1.7_0.scm

gosh> (sqrt 0.00001)
0.008234553210954832
gosh> (sqrt 2000000000000000000000)
; 終わらない（有効桁数内ではgood-enough?を満たすまで推定値を更新できない）

ちなみに組み込みのsqrtを使った結果はこちら。

ex1.7_1.scm

gosh> (sqrt 0.00001)
0.0031622776601683794
gosh> (sqrt 200000000000000000000)
1.4142135623730951e10

good-enough?で、推定値が更新される割合が十分に小さいかどうかを判断するようにしたらいいんじゃないか。

ex1.7_2.scm

(define (sqrt-iter guess guess-old x)
  (if (good-enough? guess guess-old)
    guess
    (sqrt-iter (improve guess x) guess x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess guess-old)
  (< (/ (abs (- guess guess-old)) guess-old) 0.0001))

(define (sqrt x)
  (sqrt-iter 1.0 2.0 x))

以下、実行結果。

ex1.7_3.scm

gosh> (sqrt 0.00001)
0.0031622776602038957
gosh> (sqrt 200000000000000000000)
1.4142135623730951e10

練習問題1.8

立方根を求めるなら、同じニュートン法の枠組みを使って、次の式に従って推定値を求めればいい。

y'= \frac{x/y^2+2y}{3}

以下、実装。
いちおう、先に定義した平方根のimproveと名前衝突しないように気を使ってみた。

ex1.8.scm

(define (cbrt-iter guess guess-old x)
  (if (good-enough? guess guess-old)
    guess
    (cbrt-iter (cbrt-improve guess x) guess x)))

(define (cbrt-improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

(define (good-enough? guess guess-old)
  (< (/ (abs (- guess guess-old)) guess-old) 0.0001))

(define (cbrt x)
  (cbrt-iter 1.0 2.0 x))

#1.1.8 ブラックボックス抽象化としての手続き

名前空間を汚さないように、先のsqrt、cbrtは次のように実装すればよかった。

(本文に掲載されてるコードとは異なります。こちらは練習問題1.7で改良したバージョン。
なんとなく、averageはグローバルに定義。本文中でもなぜかsqrtブロック内に書かれてなかった・・・）

1.1.8.scm

(define (average x y)
  (/ (+ x y) 2))

(define (sqrt x)
  (define (sqrt-iter guess guess-old)
    (if (good-enough? guess guess-old)
      guess
      (sqrt-iter (improve guess) guess)))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (good-enough? guess guess-old)
    (< (/ (abs (- guess guess-old)) guess-old) 0.0001))
  (sqrt-iter 1.0 2.0))

(define (cbrt x)
  (define (cbrt-iter guess guess-old)
    (if (good-enough? guess guess-old)
      guess
      (cbrt-iter (improve guess) guess)))
  (define (improve guess)
    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
  (define (good-enough? guess guess-old)
    (< (/ (abs (- guess guess-old)) guess-old) 0.0001))
  (cbrt-iter 1.0 2.0))

これをブロック構造という。

例えば、good-enough?において、guess、guess-oldは仮引数であり、その名前がなんであってもかまわない。これらは束縛変数と呼ばれる。
対して<、/、-、absは自由変数。
自由変数を書き換えちゃうと、手続きの動作に影響しちゃう。当然だけど。

ブロック内でxはいちいち渡さなくていい。
内部の手続きからは、それを囲むsqrt、cbrbの引数（束縛）も参照できる。
これをレキシカルスコーピングという。

内部の手続きから見れば、xは自由変数ということになる。