Filter
Top Products
14 CHAPTER 2. A TASTE OF CAML
Note carefully that variable binding is static, i.e. the first binding of x is still
used until an inner binding occurs, and any uses of it until that point are not affected
by the inner binding.
4
For example:
#let x = 1;;
x : int = 1
#let f w = w + x;;
f : int -> int = <fun>
#let x = 2;;
x : int = 2
#f 0;;
it : int = 1
2.4 Evaluation rules
In essence, CAML is quite simple to understand, since it just evaluates expressions.
However there are subtle questions over the precise order of evaluation. For example,
consider the following recursive function:
#let rec f x = f(x + 1);;
f : int -> ’a = <fun>
#f 2;;
Interrupted.
Evaluation of f 2 looped indefinitely, until interrupted by ctrl/c. Now suppose
we use f in another expression, but in a way that doesn’t require f to be evaluated
on any arguments:
#(fun x -> 1) (f 2);;
Interrupted.
Even so, an indefinite loop results. The reason is that according to CAML’s
evaluation rules, all arguments to a function are evaluated before being inserted
in the function body. This strategy is called eager, in contrast to cleverer lazy
approaches that try to avoid evaluating subexpressions until they are definitely
needed (and then no more than once).
CAML adopts eager evaluation for two main reasons. Choreographing the reduc-
tions and sharings that occur in lazy evaluation is quite tricky, and implementations
tend to be relatively inefficient and complicated. Unless the programmer is very
careful, memory can fill up with pending unevaluated expressions, and in general
it is hard to understand the space behaviour of programs. In fact many imple-
mentations of lazy evaluation try to optimize it to eager evaluation in cases where
there is no semantic difference. By contrast, in CAML, we always first evaluate the
arguments to functions and only then inserts them in the body — this is simple
and efficient, and is easy to implement using standard compiler technology.
The second reason for preferring eager evaluation is that CAML is not a pure
functional language, but includes imperative features (variables, assignments etc.).
Therefore the order of evaluation of subexpressions can make a big difference. If
lazy evaluation is used, it seems to become difficult for the programmer to visualize,
4
The first version of LISP used dynamic binding, where a rebinding of a variable propagated to
earlier uses of the variable. This was in fact originally regarded as a bug, but soon programmers
started to appreciate its convenience. The feature survived for a long time in many LISP dialects,
but eventually the view that static binding is better prevailed. In Common LISP, static binding
is the default, but dynamic binding is available if desired via the keyword special.