Higher-order functions are a very convenient programming feature for supporting certain forms of code reuse. Often a function passed as an argument to a higher-order function call is a closure-function created on heap at run-time, and it is most likely of no more use after the call. If the closure-function is linear, then it needs to be freed explicitly by the programmer (or a type-error would occur during typechecking). If the closure-function is non-linear, then its memory should be reclaimed through garbage-collection (GC) (or the memory is leaked).
Creating heap-allocated closure-functions implies the need for dynamic memory allocation (DMA). In a restricted environment (e.g., one for embedded programming), DMA may not be (fully) supported. One option for constructing a closure-function in the absence of support for DMA is to store it in the stack-frame of the calling function, and there is special systax in ATS for doing so.
Let us see a concrete example of stack-allocated closure. The following code implements a higher-order function template:
// 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] //
In order to remove the (unsafe) cast in the implementation of dotprod, we need to implement a slight variant of ifold as follows:
// 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_] //
Please find on-line the entirety of the code used in this chapter plus some testing code.