猫型エンジニアのブログ

プログラム/ネットワーク系の技術関連をまとめたページです 

1.1.7~1.1.8

1.1.7 例:Newton法による平方根

数学の平方根の関数:平方根の定義を与える。(ありようの記述)
計算機科学の平方根の手続き:平方根の計算方法を与える。(なし方の記述)
数学では通常平叙文的(対象が何か)であり、計算機科学では通常命令文的(対象をどうするか)である。
上の指摘にはなるほどと納得してしまった。

与えられた数の平方根を計算するプログラムは以下のとおり。
ここから急に関数が複雑化しており新しい文法などは一切でていないが、手続きの中に補助関数が全部で4つ必要となっている。

なお、このプログラムには再帰はあるが繰り返しのループ文はない。

> (define (sqrt x)
    (sqrt-iter 1.0 x))
> (define (sqrt-iter guess x)
    (if (good-enough? guess x)
         guess
         (sqrt-iter (improve guess x) x)))
> (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
> (define (improve guess x)
    (average guess (/ x guess)))
> (define (average x y)
    (/ (+  x y) 2))
> (define (square x) (* x x ))

memo
二乗根 square root -> sqrt

1.1.8 ブラックボックス抽象としての手続き

sqrtを実装する際には複数の補助関数を用いた。
各補助手続きの実装の細部を呼び出し元は意識する必要はない。
各補助手続きはブラックボックス・再利用可能な部品として扱える。

局所名

手続きがブラックボックスとして動作するためには、各手続きの中のパラメタは局所的である必要がある(C言語等で引数を値渡しとして渡すのと同じ理由)。

束縛変数:手続き定義に使用されている仮パラメタの名称に束縛されている変数。仮パラメタの名称と同じなら変数名として何を用いてもよい。
有効範囲:名前が束縛されている式の範囲
自由変数:手続き定義に使用されている仮パラメタの名称と一致しない変数。自由変数の評価においては、その手続きの外側の環境を参照する。

手続きの中において、束縛変数の名前を置き換えても手続きの意味は変化しないが、自由変数の名前を置き換えると意味が変化する。

内部定義とブロック構造

名前の保護:補助手続きの名前の衝突を防ぐために、下のように補助関数の定義を手続きの内部で行う(内部定義・ブロック構造)。

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))

上のブロック構造はさらに簡略化することができる。ブロック構造内部の補助手続きには、仮パラメタとしてxがあるが、これはsqrtのxの有効範囲内にある。そのためこれらのxを、以下のように自由変数にすることができる(自由変数を評価する際は、その外側の環境を参照する)。

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))