「Scheme手習い」10章に入る前に、少し離れて東大のScheme演習から。
cf. Scheme演習 第２回
問2（if文）
次のような新しい if 文を関数として定義した。
(define (new-if test then-exp else-exp) (cond (test then-exp) (else else-exp)))例えば、(new-if (= 1 2) (+ 3 4) (+ 5 6)) などとすれば、正しく 11 を返す。（確かめてみよ。）
これを使って、fac4 を次のように定義した。
(define (fac4 n) (new-if (= n 0) 1 (* n (fac4 (- n 1)))))これを使って (fac4 3) としたら、無限ループにおちいってしまった。（確かめてみよ。）これはなぜか。
まずは前半がちゃんと動くのかを確かめてみよう。
gosh> (define (new-if test then-exp else-exp)
(cond (test then-exp)
(else else-exp)))
new-if
gosh> (new-if (= 1 2) (+ 3 4) (+ 5 6))
11
うん、動いてるね。
つぎは後半だ。本当に無限ループに陥るのか確かめてみよう。
gosh> (define (fac4 n)
(new-if (= n 0)
1
(* n (fac4 (- n 1)))))
fac4
gosh> (fac4 3)
out of memory (32). aborting...
うーん、無限ループなのかどうかはよくわからないけど、時間がかかった上にメモリが足りなくなって Gauche ごと落ちてしまった。とにかく、期待どおりに動かないのは確かなようだ。
で、なぜかといえば、if文が特殊形式（東大のScheme演習のページではシンタックス形式、Gauceh のユーザマニュアルでは Special Form と呼んでいる）なのにたいして、new-if は単なる関数適用だ。Scheme は正格評価なので、(new-if ...) の値を決める前に、その引数である (= n 0)、1、(* n (fac4 (- n 1))) のすべてを評価する。言い換えると (fac4 3) を評価する前に (fac4 2) を評価する必要があるわけだ。同様に、(fac4 2) の前に (fac4 1) を、(fac4 1) の前に (fac4 0)を、さらに (fac4 0) の前には (fac4 -1) を･･････といった具合で永遠に続くことになる。これが無限ループの正体だ。
問3（関数を返す関数）
関数 f(x) の導関数 f'(x) は、小さい数 dx を使って近似的に下のように表せる。
[math]f'(x)=\frac{f(x+dx)-f(x)}{dx}[/math]
1 引数関数 f と小さい数 dx を受けとったら、その導関数を返すような関数 deriv を作れ。すなわち、((deriv f dx) n) のように実行すると、結果として f'(n) の値を返す。
> (define (f1 x) (* x x)) > ((deriv f1 0.001) 5) 10.001000000002591
これは簡単。
(define deriv
(lambda (f dx)
(lambda (x)
(/ (- (f (+ x dx)) (f x)) dx))))
(define f1
(lambda (x) (* x x)))
(print ((deriv f1 0.001) 5))
^o^ > gosh deriv.scm 10.001000000002591
OK。つぎ、問3の後半部分。
Newton 法を使って、1 引数の関数 f が与えられた時にf(x) = 0 の実数解を１つ求めるプログラムを作れ。精度は、f(x) と 0 の差の絶対値が 0.001 以下とする。
- 用いる dx は0.001とする。
- 実際に、f(x) = x2 – 4 やその他の関数に対して適用してみよ。
これにはヒントが与えられている。
おさらいとヒント
一般の関数に対する Newton 法は、関数 f(x) とその導関数 f'(x) が与えられたとき、その零点の近似値を次の式で更新していく。
[math]a_{n+1}=a_n-\frac{f(a_n)}{f'(a_n)}[/math]
従って、f(an) と 0 との誤差が 0.001 以下になるまで、順に an を求めていく補助再帰関数を定義し、適当な初期値をその補助関数に与えてやればよい。
これでどうだ。
(define deriv
(lambda (f dx)
(lambda (x)
(/ (- (f (+ x dx)) (f x)) dx))))
(define newton
(lambda (f init)
(if (< (abs (- (f init) 0)) 0.001)
init
(newton f (- init (/ (f init) ((deriv f 0.001) init)))))))
(define f
(lambda (x)
(- (* x x) 4)))
(print (newton f 1.0))
^o^ > gosh newton.scm 2.0000002513546535
まあ、うまくいってるかな。