[ 目次, 前節, 次節, 索引 ]

   この考えを示すために, 1.3.3節の終りにあった不動点の例をもう一度見よう. が関数y x/yの不動点であるという認識から始め, 新しい平方根手続きを不動点探索として書いた. 次いで近似を収束させるために, 平均緩和を使った. 平均緩和はそれ自身有用な一般的技法である. つまりある関数fに対し, xでの値がxとf(x)の平均である関数を考える.

   平均緩和の考え方を次の手続きで表す.

(define (average-damp f)
  (lambda (x) (average x (f x))))

((average-damp square) 10)
55

   average-dampを使うと平方根の手続きが次のように書ける:

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y)))
               1.0))

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

Newton法

   Newton法を手続きとして実装するには, 微分を表さなければならない. 「微分」は平均緩和と同様に, 関数を関数に変換する何かである. 例えば関数x x³の微分は関数x 3x²である. 一般にgが関数でdx が微小なら, gの微分Dgはxにおけるその値が(dxの微小な極限で)



で与えられる関数である. そこで微分は(dxを例えば0.00001として)

(define dx 0.00001)

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

   average-dampと同様に, derivも引数として手続きをとり, 値として手続きを返す手続きである. 例えばx x³の5での微分の近似値をとると(正確な値は75)

(define (cube x) (* x x x))

((deriv cube) 5)
75.00014999664018

   derivの助けがあれば, Newton法が不動点プロセスとして表せる.

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))


(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x))
                  1.0))

抽象と第一級手続き

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

   この抽象を使うと, 本節の初めの第一の平方根計算(y x/yを平方緩和した不動点)をこの一般的方法の特殊化として書き直せる:

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (/ x y))
                            average-damp
                            1.0))

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

   1.3節の初めの方で, 合成手続きは, それにより計算の一般的方法がプログラム言語の確かな要素として表せるが故に, 極めて重要な抽象機構であることを見た. また高階手続きがあると, 更なる抽象を作り出すためにこれらの一般的方法が操作出来るようになることも知った.

   われわれはプログラマとして, プログラムの根底にある抽象を見つけ, より強力な抽象化が出来るよう, その上に構成し, 一般化するよう努めなければならない. これはプログラムを可能な限り抽象的に書くべしというのではない; 経験を積んだプログラマは, 自分の仕事に適した抽象のレベルを選ぶことを知っている. しかし抽象を使って考えることが出来るのは, 新しい状況になった時に, すぐ応用出来るため, 大切である. 高階手続きの重要さは, それにより抽象をプログラム言語の要素として確かに表せ, 他の計算要素のように扱えるという点にある.

   一般にプログラム言語には, 計算要素を扱う方法にいろいろな制限があるものだ. 制限の殆んどない要素は 第一級(first-class)身分を持つという. 第一級要素の「権利と特権」は:64

• 変数として名前がつけられる.

• 手続きに引数として渡せる.

• 手続きの結果として返される.

• データ構造に組み込める.65

である. Lispは他の通常のプログラム言語と違い, 手続きに完全な第一級身分を授与した. そのため, 効率のよい実装は難しくなったが, 表現力として得たものは絶大である.66

問題 1.40

newtons-methodの手続きと一緒に

(newtons-method (cubic a b c) 1)

(((double (double double)) inc) 5)

((compose square inc) 6)
49

((repeated square 2) 5)
625

59 この組合せは, その演算子自身が組合せであることに注意しよう. こういう組合せが作れることは, 問題1.4で見たが, それはたわいない例であった. 今からそういう組合せが---高階手続きが値として返した手続きを作用させる時---本当に必要であることを見ていく.

60 更なる一般化は問題1.45 参照

61 微積分の入門書には通常Newton法をx_n+1 = x_n - g(x_n)/Dg(x_n)の近似値の列を使う方法と書いてある. プロセスを扱う言語があり, 不動点の考え方を使えば, この方法の記述は単純になる.

62 Newton法がいつでも収束するとは限らないが,うまくいく場合には, 反復の度に近似値の解に対する精度の桁数が倍になることが示される. そういう場合, Newton法は区間二分法よりずっと速く収束する.

63 平方根を見つける時は, Newton法はどういう初期値から出発しても正しい解に急速に収束する.

64 プログラム言語要素の第一級身分という考えは英国の計算機科学者 Christopher Strachey(1916--1975)による.

65 この例は2章でデータ構造を紹介した後で見よう.

66 第一級手続きの実装の大きな代価は, 手続きを値として返すためには, 手続きを実行しない時でも, 自由変数のための記憶場所をとっておく必要があることだ. 4.1節で学ぶSchemeの実装では, これらの変数は手続きの環境の中に格納してある.

[ 目次, 前節, 次節, 索引 ]