A Tutorial on Programming Features in ATS:
PrevNext

Chapter 27. Stack-Allocated Closure-Functions

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]
//

Essentially, ifold(n, fopr, ini) evaluates the expression fopr(...fopr(fopr(ini, 0), 1)..., n-1). For instance, the function dotprod for computing the dot product (or inner product) of two vectors can be implemented with a call to 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)
)
//

The second argument passed to the call to ifold is a closure created on heap at run-time, and it is of no more use after the call returns. The function dotprod can also be implemented as follows: 

//
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]
//

The keyword lam@ (instead of lam) initiates the creation of an unboxed closure at a given location. In the above case, the variable fopr is located in the stack-frame of dotprod, and the created closure is stored in the memory reserved for fopr. It is the obligation of the compiler of ATS to make sure that the memory is large enough for storing the closure. The call to the (unsafe) cast turns the address of fopr into a boxed closure so that it can be passed to ifold.

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_]
//

Note that the second argument of ifold_ is call-by-reference. The anotated arrow -<clo1> is used to form function types for unboxed closures. So only a left value (representing some unboxed closure) can be passed as the second argument to a call to ifold_, and what is really passed at run-time is the address of the left value. The function dotprod can be safely implemented as dotprod_ with a call to ifold_.

Please find on-line the entirety of the code used in this chapter plus some testing code.

PrevHomeNext
Linear Closure-FunctionsUpLinear Stream-Based Lazy Evaluation