Introduction to Programming in ATS:
Prev	Chapter 17. From Genericity to Late-Binding	Next

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:

int
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.

Prev	Home	Next
Templates as a Special Form of Functors	Up	Template-Based Support for Late-Binding