SICP読書録 #15 1.3.4 返り値としての手続き

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

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

## 1.3.4 返り値としての手続き

本題に入る前に、関数の不動点を求める手続きを再掲しておこう。

```_.scm
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2))
      tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
        next
        (try next))))
  (try first-guess))
```

関数 $x \mapsto x/y$ の不動点を求めることで、$x$の平方根を求めることができる、という例を1.3.3で取り上げた。
この際、平均緩和法というテクニックを利用したのだが、これを手続きにして抽象化してしまおう。

```_.scm
(define (average-damp f)
  (lambda (x) (average x (f x))))
```

これは、手続きを返す手続きだ。
これを使って平方根を求める手続きを書きなおそう。

```_.scm
(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y)))
               1.0))
```

sqrt手続きはこれでずいぶん見通しがよくなった。fixed-pointが不動点探索、average-dampが平均緩和法を表し、そして関数 $y\mapsto x/y$ がそのまま表れている。

例えば$x$の三乗根は $y\mapsto x/y^2$ の不動点だ。ここまでのお膳立てが整ってれば、すぐ応用できる。

```_.scm
(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y))))
               1.0))
```

## ニュートン法

$Dg(x)$は$g$の導関数だとする。

```math
Dg(x)=\frac{g(x+dx)-g(x)}{dx}
```

これを手続きにしよう。

```_.scm
(define dx 0.000001)
(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
```

ところで、$x \mapsto g(x)$が微分可能ならば、方程式$g(x)=0$の解は以下に示す関数$x \mapsto f(x)$の不動点となる。

```math
  f(x) = x - \frac{g(x)}{Dg(x)}
```

すでに不動点探索の手続きfixed-pointがあるんだから、以下のように実装できる。

```_.scm
(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))
```

$x$の平方根を求めるには、関数 $y \mapsto y^2-x$ のゼロ点を求めればいい。

```_.scm
(define (sqrt x)
  (newtons-method
   (lambda (y) (- (square y) x)) 1.0))
```

##抽象化とファーストクラス手続き

ここまで、平方根を求める手続きを2つ実装した。
比較のため、ちょっと修正を加えた上で並べてみよう。

```_.scm
(define (sqrt-fixed-point x)
  (fixed-point 
   (average-damp (lambda (y) (/ x y))) 
   1.0))

(define (sqrt-newton x)
  (fixed-point 
   (newton-transform (lambda (y) (- (square y) x)))
   1.0))
```

これだけ似てるんなら、そのパターンを取り出して抽象化できる。

```_.scm
(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))
```

それぞれのsqrt手続きを書き直してみよう。

```_.scm
(define (sqrt-fixed-point-2 x)
  (fixed-point-of-transform
    (lambda (y) (/ x y)) average-damp 1.0))

(define (sqrt-newton-2 x)
  (fixed-point-of-transform
    (lambda (y) (- (square y) x)) newton-transform 1.0))
```

こんな芸当が可能なのは、Lispでは手続きがファーストクラスの地位を持っているから、
つまり、次のような特権を持っているからなのだ。

- 変数によって名前をつけることができる。
- 手続きに引数として渡すことができる
- 手続きの返り値になることができる。
- データ構造に組み込むことができる。

### 練習問題1.40

newtons-methodを利用して、方程式$x^3+ax^2+bx+c=0$の解を求める。
以下のような手続きを作っておけばOK。

```_.scm
(define (cubic a b c)
  (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))
```

検算しながら動かしてみよう。

```_.scm
gosh> (newtons-method (cubic 2 3 4) 1)
-1.650629191485064
gosh> ((cubic 2 3 4) -1.650629191485064)
-2.0879387108152514e-10

gosh> (newtons-method (cubic 10 9 8) 1)
-9.108322961992677
gosh> ((cubic 10 9 8) -9.108322961992677)
1.9895196601282805e-13
```

### 練習問題1.41

引数が１つの手続きを引数として受け取り、その手続きを２回適用する手続きを返す手続きdoubleを作ってみよう。早口言葉みたい。

```_.scm
(define (double p) (lambda (x) (p (p x))))
```

実行結果。incは引数に1を足す手続き。

```_.scm
gosh> ((double inc) 3)
5
gosh> (((double (double double)) inc) 5)
21 ; 2^2^2=16回incを適用する
```

### 練習問題1.42

$f,g$はそれぞれ１引数関数だったとき、$x\mapsto f(g(x))$ とすることを合成という。
合成を行う手続きcomposeを作ってみよう。

```_.scm
(define (compose f g) (lambda (x) (f (g x))))
```

実行結果。

```_.scm
gosh> ((compose square inc) 6)
49 ; (6+1)^2
```