一章の復習
置き換えモデルは、手続きの適用をその定義で置き換えていくこと。置き換えモデルには作用的順序と正規順序があり、前者は披演算子を先に置き換え、後者は演算子(一番外側の手続き)からおきかえていく。作用的順序は一番内側から置き換えていくので最内簡約、正規順序は一番外側から置き換えていくので最外簡約とも言う.
再帰的プロセスとは遅延演算の列を膨張させながら計算を進行する計算プロセスである.遅延演算は後で計算する必要のある処理のことである.一般の実装では遅延演算の情報はスタックに詰まれていく.
反復的プロセスとはプロセスの状態がすべて一定個数の変数に格納されているプロセスのことである.なので、スタックは伸びない.
反復的プロセスのアルゴリズムの設計には不変量が有用な場合がある.不変量とは状態の移り変わりにたいして不変なままであるもののことである.本書では 累乗の計算で ab^n を不変量として用いるアルゴリズムなどが出てきた.
Θ(f(n))という記法は増加の程度を表す.g(n) = Θ(f(n))の時、g(n)はnが十分な大きさの時f(n)の定数倍以内に収まるのであった.
xがf(x)の不動点であるとは、x = f(x) となることである。この不動点というのはどうやら様々な利用ができるようだ.本書ではn乗根やNewton法のために用いている.
Newton法とは f(x) = 0 となるxを求める手法である. g(x) = x - f(x)/f'(x) として、g(x)の不動点が答えである.
第1級の身分を持つ要素とは
- 変数として名前が付けられる
- 手続きに引数として渡せる
- 手続きの結果として返される
- データ構造に組み込める
である。
反復改良法(iterative improvement)とは、予測値の終了判定と予測値の改善を繰り返すことで良い解を見つけるアルゴリズムのことである.
プログラマはプログラムの根底にある抽象を見つけ、より強力な抽象化ができるよう、その上に構成し、一般化するように努めなければならない.これはプログラムを可能な限り抽象的に書くべしというのではない。 経験をつんだプログラマは、自分の仕事に適した抽象のレベルを選ぶことを知っている.しかし抽象を使って考えることができるのは、新しい状況になったときに、すぐ応用できるため、大切である。