高階関数は、コードの形を再利用するのにとても便利なプログラミングの機能です。 高階関数呼び出しへの引数として渡された関数はしばしば実行時にヒープ上に生成されたクロージャ関数で、その呼び出しの後ではもはや使われないことを意図しています。 もしそのクロージャ関数が線形なら、それはプログラマが明示的に解放する必要があります (そうでなければ型検査中に型エラーが発生します)。 もしそのクロージャ関数が非線形なら、そのメモリはガベージコレクション (GC) によって回収されなければなりません (そうでなければメモリリークになります)。
ヒープに確保されたクロージャ関数の生成は動的なメモリ確保 (DMA) を必要としています。 制限された環境 (例: 組み込みプログラミング) では、DMA は (完全には) サポートされていないかもしれません。 DMA のサポートのない環境でのクロージャ関数の生成の1つの選択肢は、呼び出し関数のスタックフレームにそれを保管することです。 ATS にはこれを行なうための特殊な構文があります。
スタックに確保されたクロージャの実例を見てみましょう。 次のコードは高階関数テンプレートを実装しています:
// fun {res:t@ype} ifold{n:nat} ( n: int(n) , fopr: (res, natLt(n)) -<cloref1> res, ini: res ) : res = let // fun loop {i:nat | i <= n} .<n-i>. (i: int(i), res: res): res = if i < n then loop(i+1, fopr(res, i)) else res // in loop(0, ini) end // end of [ifold] //
// typedef res = double // fun dotprod {n:nat} ( n: int(n) , A: arrayref(res, n) , B: arrayref(res, n) ) : res = ( ifold<res>(n, lam(res, i) => res + A[i]*B[i], 0.0) ) //
// fun dotprod {n:nat} ( n: int(n) , A: arrayref(res, n) , B: arrayref(res, n) ) : res = let // var fopr = lam@(res: res, i: natLt(n)): res => res + A[i]*B[i] // in ifold<res>(n, $UNSAFE.cast(addr@fopr), 0.0) end // end of [dotprod] //
dotprod の実装における (安全でない) キャスト削除するために、次のような ifold の変種を実装する必要があります:
// fun {res:t@ype} ifold_{n:nat} ( n: int(n) , fopr: &(res, natLt(n)) -<clo1> res, ini: res ) : res = let // fun loop {i:nat | i <= n} .<n-i>. ( i: int(i) , fopr: &(res, natLt(n)) -<clo1> res, res: res ) : res = if i < n then loop(i+1, fopr, fopr(res, i)) else res // end of [if] // in loop(0, fopr, ini) end // end of [ifold_] // (* ****** ****** *) // fun dotprod_ {n:nat} ( n: int(n) , A: arrayref(res, n) , B: arrayref(res, n) ) : res = let // var fopr = lam@(res: res, i: natLt(n)): res => res + A[i]*B[i] // in ifold_<res>(n, fopr, 0.0) end // end of [dotprod_] //
この章で用いたコード全体とテストコードは オンライン から入手できます。