Filter
Top Products
38 CHAPTER 4. EFFECTIVE CAML
up above, with each instance of the function having its own stack frame, and when
the calls are finished the stack pointer SP moves back up.
Therefore, our implementation of fact requires n stack frames when applied to
argument n. By contrast, consider the following implementation of the factorial
function:
#let rec tfact x n =
if n = 0 then x
else tfact (x * n) (n - 1);;
tfact : int -> int -> int = <fun>
#let fact n = tfact 1 n;;
fact : int -> int = <fun>
#fact 6;;
it : int = 720
Although tfact is also recursive, the recursive call is the whole expression; it
does not occur as a proper subexpression of some other expression involving values
of variables. Such a call is said to be a tail call (because it is the very last thing the
calling function does), and a function where all recursive calls are tail calls is said
to be tail recursive.
What is significant about tail calls? When making a recursive call to tfact,
there is no need to preserve the old values of the local variables. Exactly the
same, fixed, area of storage can be used. This of course depends on the compiler’s
being intelligent enough to recognize the fact, but most compilers, including CAML
Light, are. Consequently, re-coding a function so that the recursive core of it is
tail recursive can dramatically cut down the use of storage. For functions like the
factorial, it is hardly likely that they will be called with large enough values of n to
make the stack overflow. However the naive implementations of many list functions
can cause such an effect when the argument lists are long.
The additional argument x of the tfact function is called an accumulator, be-
cause it accumulates the result as the recursive calls rack up, and is then returned
at the end. Working in this way, rather than modifying the return value on the way
back up, is a common way of making functions tail recursive.
We have remarked that a fixed area of storage can be used for the arguments to
a tail recursive function. On this view, one can look at a tail recursive function as
a thinly-veiled imperative implementation. There is an obvious parallel with our C
implementation of the factorial as an iterative function:
int fact(int n)
{ int x = 1;
while (n > 0)
{ x = x * n;
n = n - 1;
}
return x;
}
The initialization x = 1 corresponds to our setting of x to 1 by an outer wrapper
function fact. The central while loop corresponds to the recursive calls, the only
difference being that the arguments to the tail recursive function make explicit
that part of the state we are interested in assigning to. Rather than assigning and
looping, we make a recursive call with the variables updated. Using similar tricks
and making the state explicit, one can easily write essentially imperative code in
an ostensibly functional style, with the knowledge that under standard compiler
optimizations, the effect inside the machine will, in fact, be much the same.