計算機プログラムの構造と解釈(SICP) 勉強メモ4
"関数型言語の関数は数学の関数と同じだ!!!"
くらいのことを言われ(書かれ)ていたので、数学の関数とプログラミングの手続きの間の重要な違い、というのには目から鱗だった。
;;1.1.7 Newton法による平方根 ;これまでに紹介した手続きは、通常の数学の関数によく似ている。 ;つまり一個か複数のパラメタから決まる値を規定する。 ;しかし、数学の関数と計算機の手続きの間には重要な違いがある。 ;手続きは実効的でなければならない。 ; ;例えば平方根を計算する問題を考える。平方根の関数を ;√x = >= 0 かつ y^2 = x であるような y ;のように定義出来る。これは完全に正当な数学の関数を述べている。 ;これを使うと、ある数がもう一つの数の平方根であるかどうかを調べ、また一般的に平方根に関する事実を導くことが出来る。 ;一方、この定義は手続きを述べてはいない。 ;平方根をどう見つけたら良いかについて、殆ど何も言っていない。この定義をLisp風に言い換えても役に立たない。 (define (sqrt x) (the y (and (>= y 0) (= (square y) x)))) ;これでは何も解決しない。 ; ;関数と手続きの違いは、ものの在り方の記述と、ことのなし方の違いの反映である。 ;あるいはよく言われるように、平叙文的知識と命令文的知識の違いである。 ;我々は数学では通常平叙文的(何である)記述に関心を持つが、一方、計算機科学では命令文(どうする)記述に関心を持つ。 ;平叙文的記述と命令文的記述は、数学と計算機科学のように、密接に関係している。 ;例えばプログラムの出した答えが「正しい」というのは、プログラムについての平叙文的声明である。 ;プログラムが指定した「何である」の知識があれば、自動的に「どうする」の知識が生成出来るようにしようというのである。 ;これは一般的には出来ないが、進展の見えた領域もある。4章でこの考え方を再訪しよう。 ; ;平方根はどう計算するのか? ;通常は次々と近似をとるNewton法を使う。 ;数xの平方根の値の予測値yがあれば、yとx/yの平均値をとるという単純な計算で、更に良い(真の平方根に近い)予測値が得られる。 ;; ;sqrt-iter: number number -> number ;目的:数xの平方根の値の予測値yがある。yとx/yの平均値を取り、更に良い予測値を得る。 ;parm: guess 予測値 ; x 平方根を取りたい値x ;return:更に良い予測値 ;; (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) ;sqrt 平方根(square root)の略 ;iter iterrator? ;guess 推測する 予測値 ;enough イナフ (通例数量が)十分な、必要なだけの ;good-enough しゃあないな、そういうこととして理解してやろう。納得出来る。 ;good-enough? 近似値だから「大体あってる?」「許容できる?」かな? ;; ;improve: number number -> number ;目的:yとx/yの平均値を取り、予測値を改善する。 ;parm: guess 予測値 ; x 平方根を取りたい値x ;return:更に良い予測値 ;; (define (improve guess x) (average guess (/ x guess))) ;improve 改善する。"この手順を続けると平方根のますますよい近似が得られる"の部分。 ;; ;average: number number -> number ;目的:xとyの平均値を取る ;parm:x 平方根を取りたい値 ; y 予測値 ;return:平均値 ;; (define (average x y) (/ (+ x y) 2)) ;; ;good-enough?: number number -> number ;目的:「よりよい」の意味を定義する。ただしこの定義はそう良いテストではない(問題1.7参照)。 ; 考え方はその二乗と被開閉数の差が、前もって決めた許容値(ここでは0.001)より小さくなるまで答えを改善するというものである。 ;param:guess 予測値 ; x 平方根を取りたい値 ;return:bool ;; (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) ;abs: absolute value,絶対値を返す。 ;; ;sqrt: number -> number ;目的:xの平方根をNewton法を使って求める。 ;param: x 平方根を求めたい値 ;return: xの平方根 ;; (define (sqrt x) (sqrt-iter 1.0 x)) ;常にどんな数の平方根も1であると予測することが出来る。 ;最初の予測値を1ではなく、1.0にしたことに注意しよう。 ;Schemeでは10を6で割ると5/3になるが、10.0を6.0で割ると1.6666666666666667になる。 (sqrt 9) (sqrt (+ 100 37)) (sqrt (+ (sqrt 2) (sqrt 3))) (square (sqrt 1000)) ;この言語に、計算機に何かを何回も実行させる反復(ループ)構文がないのは驚きである。 ;特別な構文がなくても反復が実行できることを示した。