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

[hiroshi-manabe様の日本語訳](https://github.com/hiroshi-manabe/sicp-pdf)を使わせてもらいます。
練習問題等は[Gauche](http://practical-scheme.net/gauche/index-j.html)で実行。

[前回はこちら](https://qiita.com/shuetsu@github/items/b94938c6dbfc9aea2de6)

# 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

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

```math
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`は自由変数ということになる。