ATS のコアは値渡し (call-by-value) 評価に基づいていますが、ATS は遅延評価 (call-by-need) も直接サポートしています。
(サンク (thunk) を作ることによって) 式の評価を遅延もしくは中断するための特殊な言語コンストラクタ $delay があります。 また、(サンクによって表わされる) 中断された評価を再開するための特殊な関数 lazy_force があります。 種 (t@ype) => type の抽象型コンストラクタ lazy は型に適用されると (ボックス化された) 型を形作ります。 型 T の式 exp が与えられたとき、型 lazy(T) の値 $delay(exp) は exp の中断された評価を表わしています。 なんらかの型 T について型 lazy(T) の値 V が与えられたとき、 V に対する lazy_force 呼び出しは V によって表現される中断された評価を再開します。 もしその呼び出しあ返ったなら、その返値は型 T になります。 関数テンプレート lazy_force のインターフェイスは次のように与えられます:
このとき記号 !laz は遅延評価 (lazy-evaluation) に関連する効果を表わします。 ATS における特殊な前置演算子 ! は lazy_force の多重定義であることに注意してください。prelude/SATS/stream.sats では、遅延ストリームを表現するために次の型 stream_con と stream が相互再帰的に宣言されています:
datatype stream_con (a:t@ype+) = | stream_nil of ((*void*)) | stream_cons of (a, stream(a)) where stream (a:t@ype) = lazy (stream_con(a))
次のコードはエラトステネスの篩 (Sieve of Eratosthenes) の一般的な実装です:
// fun from (n: int): stream (int) = $delay (stream_cons (n, from (n+1))) // fun sieve ( ns: stream(int) ) :<!laz> stream(int) = $delay let // // [val-] means no warning message from the compiler // val-stream_cons(n, ns) = !ns in stream_cons (n, sieve (stream_filter_cloref<int> (ns, lam x => x mod n > 0))) end // end of [$delay let] // end of [sieve] // val thePrimes = sieve(from(2)) //
関数テンプレート stream_filter_cloref は次のようなインターフェイスを持ちます:
fun{a:t@ype} stream_filter_cloref (xs: stream(a), pred: a -<cloref> bool):<!laz> stream(a) // end of [stream_filter_cloref]
遅延評価の別の例を見てみましょう。 次のコードは、フィボナッチ数列を計算する興味深いアプローチを示しています:
// val _0_ = $UNSAFE.cast{int64}(0) val _1_ = $UNSAFE.cast{int64}(1) // val // the following values are defined mutually recursively rec theFibs_0 : stream(int64) = $delay (stream_cons(_0_, theFibs_1)) // fib0, fib1, ... and theFibs_1 : stream(int64) = $delay (stream_cons(_1_, theFibs_2)) // fib1, fib2, ... and theFibs_2 : stream(int64) = // fib2, fib3, fib4, ... ( stream_map2_fun<int64,int64><int64> (theFibs_0, theFibs_1, lam (x, y) => x + y) ) (* end of [val/and/and] *) //
fun{ a1,a2:t0p}{b:t0p } stream_map2_cloref ( xs1: stream (a1), xs2: stream (a2), f: (a1, a2) -<fun> b ) :<!laz> stream (b) // end of [stream_map2_cloref]
さらに別の遅延評価の例を見てみましょう。 ハミング数 (Hamming number) は素因数として 2, 3, 5 のみを持つ自然数です。 次のコードは、全てのハミング数から成るストリームを生成する率直な方法を示しています:
// val compare_int_int = lam (x1: int, x2: int): int =<fun> compare(x1, x2) // macdef merge2 (xs1, xs2) = stream_mergeq_fun<int> (,(xs1), ,(xs2), compare_int_int) // val rec theHamming : stream(int) = $delay ( stream_cons (1, merge2 (merge2 (theHamming2, theHamming3), theHamming5)) ) (* end of [val] *) and theHamming2 : stream(int) = stream_map_fun<int><int> (theHamming, lam x => 2 * x) and theHamming3 : stream(int) = stream_map_fun<int><int> (theHamming, lam x => 3 * x) and theHamming5 : stream(int) = stream_map_fun<int><int> (theHamming, lam x => 5 * x) //
fun{a:t0p} stream_mergeq_fun ( xs1: stream (a), xs2: stream (a), (a, a) -<fun> int ) :<!laz> stream (a) // end of [stream_mergeq_fun]
遅延ストリームを用いると、無限なデータの錯覚をたやすく作り出すことができます。 この錯覚は、メモ化 (memoization) に対して単純なプログラミングインターフェイスと自動化サポートによって産み出され、 しばしば優雅さと魅力を両立したプログラミングスタイルを可能にします。
一般的に、遅延評価に基づいたプログラムの時間的計算量 (time-complexity) と空間的計算量 (space-complexity) を見積ることは困難です。 これは深刻な弱点です。 線形遅延ストリームを用いることで、この弱点を本質的に克服することができます。
この章で紹介したコード全体は オンライン から入手できます。