関数型プログラミング事始め (32) 遅延評価(2)
関数型プログラミングがはじめての方へ贈る入門の書
前節：遅延評価(1) 次節：遅延評価(3)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)
(4) 遅延評価の演習
遅延評価は関数の評価戦略（実行順序の戦略）を手動で定義するためのひとつの手法です。ここでは遅延評価の演習として、竹内郁雄氏のたらい回し関数(tarai関数)を取り上げます。
（なお、筆者は1980年代に竹内氏のAI専用マシンであるLispマシン「ELIS」の開発に携わっていました。なにもかも、みな懐かしいです。）
OK! ISLispを使って遅延評価の演習をしていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。
> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>
(a) tarai関数(たらい回し関数)
以下のtarai関数(たらい回し関数)は竹内郁雄氏が1976年に考案したプログラムです。この関数は非常にシンプルな形をしていますが、引数をたらい回しにして、関数の実行回数を非常に多くして、ベンチマークに使えるようにしたものです。別名として竹内関数とも呼ばれています。
ISLisp>
(defun tarai (x y z)
(if (<= x y)
y
(tarai (tarai (- x 1) y z) (tarai (- y 1) z x) (tarai (- z 1) x y)) ))
TARAI
ISLisp>(tarai 12 6 0)
12
(tarai 12 6 0)は再帰が多すぎるので(tarai 3 2 1)で実行の様子を見てみます。(tarai 3 2 1)が実行されると、最初は(tarai (- x 1) y z)に対応する(tarai 2 2 1)が実行されます。(tarai 2 2 1)は(if (<= x y) y …)で(if (<= 2 2) 2 …)のように真となるのでyの2を返します。
元の(tarai 3 2 1)に戻り、2番目の引数である(tarai (- y 1) z x)に対応する(tarai 1 1 3)が実行され、1が返ります。
そして元の(tarai 3 2 1)に戻り、3番目の引数である(tarai (- z 1) x y)に対応する(tarai 0 3 2)が実行され、3が返ります。
そしてさらに元の(tarai 3 2 1)に戻り、(tarai (tarai (- x 1) y z) (tarai (- y 1) z x) (tarai (- z 1) x y))の3個の引数の評価が終わりましたので、(tarai 2 1 3)を実行します。後は同様に実行すると最終的に3が返ります。
tarai関数は値としてyを返しますので、結局zの値は使っていませんので、使い捨てになります。
なおtarai関数でyの値ではなくzの値を返す版の関数はtak関数と呼ばれています。これはtarai関数を見たジョン・マッカーシー氏が記憶違いをしてzを返す関数にしてしまったものです。このtak関数も広まっていますが、再帰呼び出しの階数はtaraiよりも格段に少なくなります。
(b) 遅延評価版のtarai関数
それではtarai関数を遅延評価で実装してみます。その関数をdtaraiとします。
ISLisp>
(defun dtarai (x y z)
(let ((x (if (numberp x) x (funcall x)))
(y (if (numberp y) y (funcall y))) )
(if (<= x y)
y
(let ((z (if (numberp z) z (funcall z))))
(dtarai (lambda () (dtarai (- x 1) y z))
(lambda () (dtarai (- y 1) z x))
(lambda () (dtarai (- z 1) x y)) )))))
DTARAI
ISLisp>(dtarai 12 6 0)
12
dtaraiでは引数をラムダ式の関数で渡すことで評価をif文のthen節のyになったときに初めて実行するように、評価を遅延させています。numberpの関数は引数が数値かどうかを判定する関数で、遅延するために関数引数のときは偽を返し、実行した結果の数値であったときは真を返すようにしています。これで値が必要になったときのみ、funcallで実行するようにしています。
このように値が必要になったときに評価するものを、call by need(必須評価)と呼んでいます。このような評価戦略の機構を持たないプログラミング言語では、遅延評価を用いて、手動で実装する必要があります。
実際に(tarai 12 6 0)と(dtarai 12 6 0)を比較してみます。OK! ISLispには拡張機能として、timeマクロが用意されていて、引数の実行時間などを計測することができますので、それを使った結果を以下に示します。
ISLisp>(time (tarai 12 6 0))
Elapse time = 1.578 sec.
GC: 0 Stack Used: 1125
CONS: 0 (GC: 0)
SYMBOL: 0 (GC: 0)
HEADER: 0 (GC: 0)
VECTOR: 0 (GC: 0)
12
ISLisp>(time (dtarai 12 6 0))
Elapse time = 0.000 sec.
GC: 0 Stack Used: 564
CONS: 864 (GC: 0)
SYMBOL: 0 (GC: 0)
HEADER: 324 (GC: 0)
VECTOR: 540 (GC: 0)
12
tarai6 (tarai 12 6 0)では1.578秒かかり、スタックの消費量が 1125個であったのに対し、dtarai6 (dtarai 12 6 0)では計測不可の0秒で、スタック消費量も564個になっています。
計測するPCが高性能であったときは tarai7 (tarai 14 7 0)で計測してみてください。
(c) チート版のtarai関数
tarai関数では結局zの値は使いません。そこでzの評価をしない遅延評価版のtarai関数を以下のように作ってみます。
ISLisp>
(defun dtarai (x y z)
(let ((x (if (numberp x) x (funcall x)))
(y (if (numberp y) y (funcall y))) )
(if (<= x y)
y
(dtarai (lambda () (dtarai (- x 1) y z))
(lambda () (dtarai (- y 1) z x))
(lambda () (dtarai (- z 1) x y)) ))))
DTARAI
ISLisp>(time (dtarai 12 6 0))
Elapse time = 0.000 sec.
GC: 0 Stack Used: 498
CONS: 756 (GC: 0)
SYMBOL: 0 (GC: 0)
HEADER: 288 (GC: 0)
VECTOR: 396 (GC: 0)
12
チート版のdtaraiのスタック消費量が498個となり、チートを使わない版と比較して少なくなっています。これはzの値を使わないということを知っていてのチートですから、卑怯です。秘密にしておきましょう。
(予告) (5) 評価戦略
遅延評価で手動で評価戦略を定義してきました。次回は評価戦略について紹介する予定です。お楽しみに！
いいなと思ったら応援しよう！
