Posted at

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

hiroshi-manabe様の日本語訳を使わせてもらいます。

練習問題等はGaucheで実行。

前回はこちら


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$の導関数だとする。

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)$の不動点となる。

  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

引数が1つの手続きを引数として受け取り、その手続きを2回適用する手続きを返す手続き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$はそれぞれ1引数関数だったとき、$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