Filter
Top Products
4.2. WRITING EFFICIENT CODE 37
The setify function is supposed to turn a list into a set by eliminating any duplicate
elements.
4.2 Writing efficient code
Here we accumulate some common tricks of the trade, which can often make CAML
programs substantially more efficient. In order to justify some of them, we need to
sketch in general terms how certain constructs are executed in hardware.
4.2.1 Tail recursion and accumulators
The principal control mechanism in functional programs is recursion. If we are
interested in efficient programs, it behoves us to think a little about how recursion
is implemented on conventional hardware. In fact, there is not, in this respect
at least, much difference between the implementation of CAML and many other
languages with dynamic variables, such as C.
If functions cannot be called recursively, then we are safe in storing their local
variables (which includes the values of arguments) at a fixed place in memory — this
is what FORTRAN does. However, this is not possible in general if the function
can be called recursively. A call to a function f with one set of arguments may
include within it a call to f with a different set of arguments. The old ones would
be overwritten, even if the outer version of f needs to refer to them again after the
inner call has finished. For example, consider the factorial function yet again:
#let rec fact n = if n = 0 then 1
else n * fact(n - 1);;
A call to fact 6 causes another call to fact 5 (and beyond), but when this
call is finished and the value of fact 5 is obtained, we still need the original value
of n, namely 6, in order to do the multiplication yielding the final result. What
normally happens in implementations is that each function call is allocated a new
frame on a stack. Every new function call moves the stack pointer further down
1
the
stack, creating space for new variables. When the function call is finished the stack
pointer moves up and so the unwanted inner variables are discarded automatically.
A diagram may make this clearer:
SP
✲
n = 0
n = 1
n = 2
n = 3
n = 4
n = 5
n = 6
This is an imagined snapshot of the stack during execution of the innermost
recursive call, i.e. fact 0. All the local variables for the upper stages are stacked
1
Despite the name, stacks conventionally grow downwards.