Example: Templates for Loop Construction

Beginners in functional programming (FP) who have already acquired some knowledge of imperative programming often ask about ways to construct for-loops and while-loops in FP. A commonly given answer is that loop constructs are unnecessary in FP as they can be readily replaced with higher-order functions. Let us first see some thorny issues with this answer.

The following code in C implements a function that returns the sum of the first n natural numbers when applied to a natural number n:

tally (int n) {
  int i, res;
  for (i = 0, res = 0; i < n; i += 1) res += i;
  return res;

This function tally can be given the following equivalent implementation in ATS:

fun tally ( n: int ) : int = loop (0, 0) where { fun loop (i: int, res: int): int = if i < n then loop (i + 1, res + i) else res }

where the tail-recursive function loop is just a translation of the for-loop in C.

When someone claims that loop constructs can be replaced with higher-order functions, he or she probably means to construct loops with a function like the following one:

fun for_loop ( count: int, limit: int, fwork: (int) -<cloref1> void ) : void = ( // if count < limit then (fwork(count); for_loop(count+1, limit, fwork)) else () // end of [if] ) (* end of [for_loop] *)

For example, the following function tally2 is directly based on for_loop:

fun tally2 ( n: int ) : int = let val res = ref<int> (0) in for_loop (0, n, lam (i) => !res := !res + i); !res end // end of [tally2]

While both tally and tally2 return the same result when applied to a given natural number, they behave very differently at run-time. In particular, each call to tally2 creates a (persistent) reference on heap for temporary use; the reference becomes garbage immediately after the call returns. Compared to tally, tally2 is inefficient both time-wise and memory-wise.

To eliminate the need for reference creation in tally2, we turn for_loop into the following function template for_loop2:

// fun{ env:t@ype } for_loop2 ( count: int, limit: int , env: &env >> _, fwork: (int, &env >> _) -<cloref1> void ) : void = ( // if count < limit then ( fwork(count, env); for_loop2<env> (count+1, limit, env, fwork) ) else () // end of [if] // ) (* end of [for_loop2] *)

We can further turn tally2 into the following tally3 based on for_loop2:

fun tally3 ( n: int ) : int = let var res: int = 0 in for_loop2<int> (0, n, res, lam (i, res) => res := res + i); res end // end of [tally3]

While tally3 improves upon tally2, it is still a bit unsatisfactory. Clearly, the closure function formed before tally3 calls for_loop2 becomes garbage immediately after the call returns. It is plausible to expect that an optimizing C compiler (e.g., gcc and clang) can eliminate the need for actual closure formation when it compiles the C code generated from ATS source, but there is no guarantee. In order to have such a guarantee, we can evolve for_loop2 into the following function template for_loop3:

fun{ env:t@ype } for_loop3 ( count: int, limit: int, env: &env >> _ ) : void = ( // if count < limit then ( for_loop3$fwork<env>(count, env); for_loop3<env>(count+1, limit, env) ) else () // end of [if] // ) (* end of [for_loop3] *)

where for_loop3$fwork is given the interface below:

fun{ env:t@ype } for_loop3$fwork(count: int, env: &env >> _): void

Finally, we can turn tally3 into tally4 as follows:

fun tally4 ( n: int ) : int = let // var res: int = 0 // implement for_loop3$fwork<int> (i, res) = res := res + i // in for_loop3<int> (0, n, res); res end // end of [tally4]

By inspecting the C code generated by atsopt from compiling tally4, we can see that the C code is essentially equivalent to the implementation of tally in C (given at the beginning of this section).

By now, the reader probably agrees with me if I say the statement should at least be considered grossly inaccurate that claims loop constructs in FP can be readily replaced with higher-order functions. Please find on-line the file loopcons.dats containing the entirety of the code presented in this section plus some testing code.