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