john7rv

ラムダ計算のβ簡約はどのような順番で行われるのでしょうか
例えばSchemeで掛け算をする関数を作って
足し算と引き算の答えをその関数に渡して実行したとします

(define multi-xy (lambda (x y)
                   (* x y)))

(multi-xy (+ 2 5) (- 9 6))

プログラムを実行するとこの計算はどのような順番で行われのでしょう
２つの評価方法が有ります

先行評価とも呼ばれる方法です。世の中の大部分のプログラミング言語はこの方法で評価していきます。
上記のmulti-xyのコードであれば

(multi-xy (+ 2 5) (- 9 6))

まず内側で一番右の

(- 9 6)

から始めます
(- 9 6)を計算すれば3なのでβ簡約して

(multi-xy (+ 2 5) 3)

次に左の(+ 2 5)をβ簡約します
(+ 2 5)を計算すれば7なのでそれもβ簡約して

(multi-xy 7 3)

そしてmulti-xyもβ簡約して

(* 7 3)
>21

となります
一番内側の右から評価していき外側に評価していくやり方です

遅延評価と呼ばれる方法です。
または正規評価とも言われます。
HaskellやMirandaなどがこの方式を取っています。
SchemeとOCamlでは部分的に遅延評価にする機能があります
ラムダ計算もこの方式になります。
必要になってから計算するとも言われます。
まず外側から計算しますが
引数の評価や計算は行いません。
なので遅延評価と呼ばれます。

(multi-xy (+ 2 5) (- 9 6))

一番外側のmulti-xyからβ簡約します

(* (+ 2 5) (- 9 6))

そして内側の左のS式をβ簡約して

(* 7 (- 9 6))

右側のS式をβ簡約して

(* 7 3)

となります
必要に応じて評価しているとも言えます
(注：実際のSchemeのプログラムは指定しない限り先行評価で行われます。上記の例はもし遅延評価で行われたらとして説明のために書いています)
遅延評価は必要になるまで計算実行を遅らせ、不必要な計算は行わないので
無限リストなどの無限ループになりかねない構造も扱うことができます

関数内部に引数を渡す際
引数の内容をまず値まで評価(β簡約)してから渡すものを
値呼びもしくは値渡しと言います

関数内部に引数を渡す際
引数を評価せずにそのまま関数内の各処理命令に渡すものを
名前呼びもしくは名前渡しと言います

例えば
(2+3)という関数を引数に渡された関数Fがあるとします
func F(x)
{
add()
multi()
};
F(2+3);
この場合値渡しなら最初から５を
add()とmulti()に渡します
add(5)
multi(5)
名前渡しなら各関数に(2+3)をそのまま渡し
関数ごとに計算します
add(2+3)
multi(2+3)
つまり
名前渡しだと2+3を２回計算しなければならなくなり処理が重くなります
しかし
名前渡しは必要になったときに評価する遅延評価と同じなので
無限ループなどを扱うときには役に立ちます

言語全体で遅延評価がデフォルトで行われるプログラミング言語にはHaskellとMirandaやGoferがあります
SchemeやOCamlは指定することで指定部分を遅延評価にすることができます
Pythonでは組み込み関数などが遅延評価になっています
他にも関数型言語には遅延評価の考えを取り入れている言語があります