Re: Recursion, exception and continuations

[Pierre Weis <weis@pauillac.inria.fr>]

> [1] Is tail recursion always handled correctly by CAML, i.e. in a constant
> stack space ? 

Tail recursion is not guaranteed to be optimized by the compiler in
Caml, although compilers tend to implement this optimization.

> [2] Why is it not possible to define an exception locally, inside a
> function.

Local definition of exceptions is a bit difficult to implement, hence
compilers may not implement it. Local exceptions are featured in Caml
V3.1 but not in Caml Light or Caml Special Light.

Beside implementation problems local exceptions leads to efficiency
problems when not used properly. In effect, local exceptions must be
generative, that is: each local exception definition must generate a
new exception, different from any other previously defined exception,
and different from any exception that may be defined in the future. To
achieve this behaviour, the compiler must dynamically allocate some
data structure for the exception and compare the exceptions via the
``eq'' predicate. Hence, the usual constant folding problem in
functions applies: consider

let f1 = function x ->
 exception Local_exc in
 try ...
 with Local_exc -> ...
;;

and

let f2 =
 exception Local_exc in
 function x ->
  try ...
  with Local_exc -> ...
;;

f1 is not equivalent to f2, since f2 allocates Local_exn once and for
all and let it local to the closure of f2. In contrast f1 allocates a
new Local_exc at each invocation of f1 (in particular if f1 is
recursive and raises Local_exc in one of its recursive call nested
deeper, it cannot be handled by the try ... with ..., since it is not
the same exception). 

This cannot be optimized by the compiler, since semantically different
behaviour is required. As you may guess, f2 is generally what the user
means: he wants to define once and for all a local exception for its
function. Unfortunately, the user always writes f1 that seems more
natural than f2. This has to consequences:
1) If f is recursive the behaviour of the f2 encoding appears like a
bug of the compiler, or at least a very strange behaviour of local exception
2) If f is not recursive, then the natural encoding, f1, is less
efficient than the strange f2 definition, since f1 allocates some
structure in memory at each call.

These two problems desappear with global definitions of exceptions.
On the other hand, you may argue that local exception are for advanced
programmers that are perfectly aware of generativity in function
definitions and master strange definitions of the shape
 let f =
  let ... in
  (function ...) 

> it' annoying to be obliged to declare them at toplevel, which can then be
> rapidly polluted by exception declarations (and naming can become difficult).

This must be tempered by the existence of modules: you define your
exceptions locally to the modules that contains the function that
needs the exception. The ``local'' exception may be kept local to the
module and not exported to the outside. Hence the name space is not
``polluted'' by exception definitions. But I must agree that a local
exception may be useful in this case.

> [3] I appreciate the type system of CAML, but is a such system compatible
> with access to continuations, as it is possible to do in Scheme ?

Yes it is. Unfortunately, as you may know, explicit continuation
manipulations are difficult to implement efficiently, and tend to clobber
simple and efficient compilation of the rest of the language.

On the other hand, there is no difficulty to manipulate continuations
explicitely, I mean ``by hand'', since functions are first class
citizens in Caml, you may write functions in continuation passing style.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis