Chapter 28. 線形遅延ストリーム

ATS では、線形ストリームに基づいた遅延評価もサポートされています。 私が知る範囲では、線形遅延ストリームは現在のところ ATS 言語独自の機能です。

実際には、 (非線形の) 遅延ストリームにはたいがいガベージコレクション (GC) のサポートが必要になります。 一般的には GC の挙動を予測することはとても困難なため、より強い正確さが必要とされる場面において遅延評価は適切でないかもしれません。 線形遅延ストリームを用いると、ストリームを表現する値を回収する GC が不要になります。 そのような値は安全な作法で明示的に解放できるのです。

特殊コンストラクタ $ldelay は (線形サンク (linear thunk) を作ることによって) 式の評価を遅延もしくは中断します。 また、特殊関数のペア lazy_vt_force と lazy_vt_free はそれぞれ (線形サンクによって表わされる) 中断された評価の再開と解放を行ないます。 delay と異なり、$ldelay は線形遅延ストリームを作るために2つの式に適用されます; 1つ目の式はその評価を中断させるため; 2つ目の式を評価すると1つ目の式が含む全ての線形値を解放します。

種 (vt@ype) => vtype の抽象型コンストラクタ lazy_vt は、観型に適応されると (ボックス化された) 観型を形作ります。 型 T の式 exp1 と型 void の式 exp2 が与えられたとき、値 $ldelay(exp1, exp2) は型 lazy_vt(T) です; $ldelay(exp1, exp2) に対して lazy_vt_force を呼び出すと中断されていた exp1 の評価が再開されます; $ldelay(exp1, exp2) に対して lazy_vt_free を呼び出すと (exp1 に含まれる線形値を解放するために) exp2 の評価が開始されます。

関数テンプレート lazy_vt_force は次のようなインターフェイスを持ちます:

fun{a:vt@ype} lazy_vt_force (lazyval: lazy_vt(a)): (a)

関数 lazy_vt_free は次のようなインターフェイスを持ちます:

fun lazy_vt_free {a:vt@ype} (lazyval: lazy_vt(a)): void

prelude/SATS/stream_vt.sats にて、線形遅延ストリームを表現する次の観型 stream_vt_con と stream_vt が相互再帰的に宣言されています:

datavtype
stream_vt_con (a:vt@ype+) =
  | stream_vt_nil of ((*void*)) | stream_vt_cons of (a, stream_vt(a))
where stream_vt (a:vt@ype) = lazy_vt (stream_vt_con(a))

次のコードは、全ての素数が線形ストリームとしてコンストラクトされるエラトステネスの篩 (Sieve of Eratosthenes) を実装しています:

//
fun
from (n: int): stream_vt (int) =
  $ldelay (stream_vt_cons (n, from (n+1)))
//
fun sieve
(
  ns: stream_vt(int)
) : stream_vt(int) = $ldelay
(
let
//
// [val-] means no warning message from the compiler
//
  val ns_con = !ns
  val-@stream_vt_cons(n, ns1) = ns_con
  val n = n
  val ns1_ = ns1
  val ((*void*)) = ns1 := sieve (stream_vt_filter_cloptr<int> (ns1_, lam x => x mod n > 0))
  prval ((*void*)) = fold@(ns_con)
in
  ns_con
end // end of [let]
,
~ns // [ns] is freed
) (* end of [$ldelay] *) // end of [sieve]
//
val thePrimes = sieve(from(2))
//

関数テンプレート stream_vt_filter_cloptr は次のインターフェイスを持ちます:

fun{a:t0p}
stream_vt_filter_cloptr
  (xs: stream_vt (a), pred: (&a) -<cloptr> bool): stream_vt (a)
// end of [stream_vt_filter_cloptr]

この章で紹介したコード全体は オンライン から入手できます。 上記の実装がメモリリークをしていないことを確認するために valgrind のようなツールを使うこともたやすいでしょう。