Copyright © 2015 by 桜川貴司
多くのプログラミング言語では、函数や手続きを呼び出す前にそれらの引数の値を求めます。しかし、引数の値が真に必要になってから求めるという方法もあります。後者の評価順序で計算を行うことを一般に遅延評価(lazy evaluation)あるいは必要呼び(call-by-need)と言います。それに対し前者を先行評価(eager evaluation)と言います。プログラミング言語によっては遅延評価を取り入れたもの、あるいはそれが標準の評価方法のものもあります。
Schemeは基本的に先行評価を行いますが、一部遅延評価の方法も取り入れていて、そのように指定すれば使用することができる仕様となっています。ただし、遅延評価用の特別なデータや函数を用いて、式の評価を遅延することや、評価を遅延している式を評価することを陽に指定する方式です。そのため、先行評価の場合と同じように書けば自動的に遅延評価となる言語とは異なり、意識的な指定が必要となります。これは欠点と見ることもできますが、意識的に評価順序を細かく指定でき、最適化が可能になるという意味では利点であると言えます。
(delay S式)
の値は、S式の部分をプロミス(promise)としたものです。プロミスとは、評価が遅延されている状態の式のことです(ここでdelayは函数ではありません。delayが普通の函数だとすると、それを呼び出す前にS式の部分を評価してしまいます)。
(force プロミス)
とすると、プロミスの評価を行って、それの結果の値が式全体の値となります。
(promise? x)
は、xがプロミスの時に#t、それ以外では#fとなります(これはRacket5.3.6には無いようです)。Schemeではこれら3つ(2つ)のプリミティブを利用して、遅延評価を行うプログラムを書くことができます。
遅延評価を行う利点としては、まず、利用しないかもしれない引数を、本当に必要になってから評価することで、実行時間やメモリ使用量を減らせる場合があることを挙げられます。ただし、評価を遅らせるために必要なデータの置き場所とそれらを管理する時間が必要になりますので、遅延評価により却って遅くなったりメモリの必要量が増える場合も多々あります。次の利点として、先行評価のみでは行えなかったようなアルゴリズムやデータの表現が可能になることを挙げられます。例えば無限リストはそのままでは計算機の中に収まりませんが、遅延評価により必要になった時点で要素の値を計算するようにすることで、見かけ上無限リストを扱うことができる場合があります。後で挙げるエラトステネスの篩の遅延評価版はこれを利用しています。
delayとforceの使用例:
> (define x (delay (* 10 20)))
> x
#<promise>
> (force x)
200
> (define (d-add1 x) (delay (+ 1 (force x))))
> (d-add1 x)
#<promise>
> (force (d-add1 x))
201
> (force (d-add1 (d-add1 x)))
202
次のソースプログラム例は、以前作成したエラトステネスの篩によるnまでの素数を求めるプログラムを変更し、無限に長いリストを遅延評価により仮想的に作成することで、nまでというように限定せずに素数の列を求めるプログラムです。
lazy-primes.rkt (Firefoxで参照してください。)
ただし、d-primesという函数そのものは原理的には上限なく動くアルゴリズムを記述していますが、実際の処理系の各種の制限や、d-writeという函数により出力する部分を制限することで、有限部分しか出力されないことになります。(d-primeswrite -1)とすると、メモリやスタックの許す限り素数を出力し続けることとなります。