関数型プログラミング事始め (31) 遅延評価(1)

関数型プログラミングがはじめての方へ贈る入門の書
前節：高階関数(3)　次節：未公開
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)

遅延評価は関数引数の評価の順番が来ても、直ぐに評価するのではなく、後で遅延して評価することです。 つまり遅延評価は関数引数を左側優先・内側優先の通常の評価順序（正格評価）ではない評価順序（非正格評価）を手動で実装するための手法となります。これにより、引数の評価を呼び出した関数で使わないような無駄を省くことができ、効率的な評価ができます。しかし遅延評価は言わば、評価を手動で制御することになり、これはプログラマにとって面倒なものになるので、気をつけて使う必要があります。

3.3 遅延評価

遅延評価は左側優先評価(leftmost evaluation)・内側優先評価(innermost evaluation)の正格評価(strict evaluation)ではなく、評価を手動で遅延することで、評価順序を制御することができます。なおここでは、関数の実行を評価(evaluation)と呼んでいます。

ここではOK! ISLispを使って遅延評価を見ていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。

> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>

(1) 遅延評価手始め

最初に通常の評価順序である左側優先・内側優先の正格評価を見ていくことにします。

ISLisp>(defun add (x y) (+ x y))
ADD
ISLisp>(add (+ 1 2) (+ 3 4))
10

関数addは2個の引数を加算して、その結果を返す関数です。そして(add (+ 1 2) (+ 3 4))の評価は、内側優先であるため(add …)の評価の前に、内側の(+ 1 2)と(+ 3 4)を先に評価します。そして左側優先であるため、(1) (+ 1 2)の項を評価して3になります。(2) 次にその項の右側の項(+ 3 4)を評価して7になります。これで内側の評価が終わったので、外側の(3) (add …)の項を評価します。関数addでは(1)と(2)び評価結果3と7を受け取って、(+ 3 7)を評価して10を返します。これが通常の関数評価の順序である正格評価です。

次に遅延評価の例を紹介します。

ISLisp>(defun dadd (x y) (+ (funcall x) (funcall y)))
DADD
ISLisp>(dadd (lambda () (+ 1 2)) (lambda () (+ 3 4)))
10

関数dadd (delay add)は、引数xの関数をfuncallで実行し、次に引数yの関数をfuncallで実行します。それぞれの実行結果を加算して、値として返します。

(dadd (lambda () (+ 1 2)) (lambda () (+ 3 4)))を実行すると、daddの引数の(lambda () (+ 1 2))が実行され(+ 1 2)のラムダ式(匿名関数)が生成され、(lambda () (+ 3 4))も同様に(+ 3 4)の匿名関数が生成されます。

引数の実行結果を受けてdaddが実行されます。daddの中でfuncallによって(+ 1 2)の関数が実行されて3が返され、次に(+ 3 4)の関数が実行され7が返されます。そして(+ 3 7)が実行されて10が返されます。

この動作では実質的には、(1) daddが評価、(2) (+ 1 2)が評価、(3) (+ 3 4)が評価されるという評価順序になります。このように外側優先評価(outmost evaluation)になります。

このように、内側優先・左側優先の正格評価の機構しか持たないLispでは、上記のようにラムダ式（匿名関数）で関数渡しをすることで（無理やり、強制的に）実装します。

(2) 遅延評価の例

遅延評価の例として、2個の引数のうち、1個だけを評価したい場合の例を考えます。第1引数が真(t)のときは第2引数の値を返し、第1引数が偽(nil)のときは第3引数の値を返す関数を考えます。

ISLisp>(defun cadd0 (c then else) (if c then else))
CADD0
ISLisp>(cadd0 t (+ 1 2) (+ 3 4))
3
ISLisp>(cadd0 nil (+ 1 2) (+ 3 4))
7

このcadd0では、第2引数と第3引数はどちらか1個のみを実行するだけでいいにも関わらず、両方を実行するのはどちらかは無駄になります。

ISLisp>(defun cadd (c then else) (if c (funcall then) (funcall else)))
CADD
ISLisp>(cadd t (lambda () (+ 1 2)) (lambda () (+ 3 4)))
3
ISLisp>(cadd nil (lambda () (+ 1 2)) (lambda () (+ 3 4)))
7

遅延評価をするcaddではcの真理値による第2引数か第3引数のどちらか1個のみを実行します。もう一方の引数を無駄に実行しません。
(cadd t (lambda () (+ 1 2)) (lambda () (+ 3 4)))では、第1引数が真(t)であるので、第2引数の(lambda () (+ 1 2))の(+ 1 2)のみが実行され、(+ 3 4)は実行しません。無駄になりません。

このように無駄な関数実行がないのが遅延評価のメリットです。利点です。長所です。重要なことなので多めに言いました。

Schemeのdelayやforceなどのように遅延評価機能を言語仕様として備えている言語では上記のように手作りする必要はありません。逆に言えば、関数型プログラミング言語では一般的に遅延評価の機能を持っています。
通常のLispは遅延評価はありませんが、でも立派な関数型プログラミング言語です。その理由は次の節で言い訳します。

(3) マクロによる構文糖衣

daddやcaddのように、引数にラムダ式を追加するのは面倒です。Schemeなどには便利な遅延評価機能があるのに、普通のLispにはないのは不公平です。ということでLispの持つ強力なマクロ機能で、遅延評価の構文糖衣（シンタックスシュガー）を作ってみます。なお構文糖衣とは、プログラム構文が簡単にできるようにプログラムの意味論を変えずに、プログラムを見やすくします。

ISLisp>
(defmacro madd (c then else)
    `(cadd ,c (lambda () ,then) (lambda () ,else)) )
MADD
ISLisp>(madd t (+ 1 2) (+ 3 4))
3
ISLisp>(madd nil (+ 1 2) (+ 3 4))
7

マクロmaddにより、前述(2)の(cadd c (lambda () then) (lambda () else))に展開します。そして(madd t (+ 1 2) (+ 3 4))のようにシンプルに書くことができます。これは(cadd t (lambda () (+ 1 2)) (lambda () (+ 3 4)))に展開され、第2引数か第3引数のどちらか1個のみが実行されます。

(予告) (4) 遅延評価の演習

次回は遅延評価の演習を紹介します。お楽しみに！