計算機プログラムの構造と解釈 1.1.5

1.1.5 keyword
置換えモデル、作用的順序、正規順序

置換えモデル

人間がプロセスを理解しやすくするためのモデル。
以下のように手続き定義を展開していく。

(f 5)
fの本体を取りだし、
(sum-of-squares (+ a 1) (* a 2))
仮パラメタaを引数5に。

(sum-of-squares (+ 5 1) (* 5 2))
(+ 5 1) (* 5 2)を計算してから、sum-of-squareの本体を取りだし、以下繰り返し。
(+ (square 6) (square 10))
(+ 36 100)
136

実際の処理とは関係ないし、置換えで表現できることは限られている
(3章の可変データでこのモデルは破綻する)

作用的順序

今まで読んできた評価の方法。
解釈系が演算子と被演算子を評価して、結果の手続きを結果の引数に作用させる。
例
(sum-of-square (+ 5 1) (* 5 2))のとき

演算子を評価-->結果の手続き
(sum-of-square (a,b)) --> (+ (square a) (square b))

被演算子を評価-->結果の引数
(+ 5 1) --> 6
(* 5 2) --> 10

結果の手続きを結果の引数に作用
(+ (square 6) (square 10))

正規順序

完全に展開する。

(sum-of-square (+ 5 1) (* 5 2))は
(+ (square 6) (square 10))とならず、
(+ (square + 5 1) (square * 5 2))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)) )
となる。
(+ 5 1)と(* 5 2)をそれぞれ2回計算することになるので、効率が悪い。

正規順序と作用順序

正規順序は「完全に展開し、簡約する」
作用順序は「引数を評価し、作用させる」
置換えでモデル化できる式に関しては２つとも同じ結果になる。つまり違う結果のときがある。
(同じ結果にならない例は問題1.5で後述)

Lispは作用的順序の評価を行うが、理由は(+ 5 1)(* 5 2)を2回計算するような多重評価をさけるためと、正規順序が置換えでモデル化できる範囲を越えたとたんに複雑化するから。
ただし、正規順序の評価も有効な道具であり、部分的に用いることがある。(3章ストリーム処理と4.2節参照)