Recursion, exception and continuations

Recursion, exception and continuations

[Tarizzo Martial]

Hello,

Here are some questions about CAML :

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

[2] Why is it not possible to define an exception locally, inside a
function. The Michel Mauny's tutorial seems to encourage the use of
exception as a control structure (a kind of common lisp catch/throw), but
it' annoying to be obliged to declare them at toplevel, which can then be
rapidly polluted by exception declarations (and naming can become difficult).

[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 ?

Thanks for answers.
*********************************
 Tarizzo Martial
 Prof. Sc Physiques
 Classes preparatoires
 Lycee J MOULIN
 57600 FORBACH

 Email: tarizzo@world-net.sct.fr
        74014.3307@compuserve.com
 Compuserve : 74014,3307
*********************************

Re: Recursion, exception and continuations

[Pierre Weis]

> [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

Re: Recursion, exception and continuations

[Francis Dupont]

 In your previous mail you wrote:

   [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 ?
   
=> I disagree Pierre Weis, the answer is yes and no because
of the toplevel. Here is a short summary of the problem:
a continuation is the functional abstraction of a context,
ie for the context C[ ] the associated continuation is fun x -> C[x].
 Obviously two types are involved in a context, the hole type and
the embracing type but there is usually only one type in a continuation
(the type of the hole/argument).
 It doesn't matter if the continuation is used in a program or in
*one* toplevel statement, but there is a problem if a toplevel statement
produces a continuation used in an other toplevel statement: the type
system can be broken or the extend of the continuation must be
constrained... See SML of New Jersey for correction attempts!

Regards

Francis.Dupont@inria.fr

PS: some continuation constructs have been proposed with different
scope, extend and typing rules and without the toplevel problem,
but there are not the Scheme callcc operator. Some of them can be
expansed in a CPS program of rather the same size (read papers
by Olivier Danvy & all).

Re: Recursion, exception and continuations

[Didier Remy]

>  It doesn't matter if the continuation is used in a program or in
> *one* toplevel statement, but there is a problem if a toplevel statement
> produces a continuation used in an other toplevel statement: the type
> system can be broken or the extend of the continuation must be
> constrained... See SML of New Jersey for correction attempts!

These problems have been studied in [1]. The conclusion was that
typechecking continuations is not a problem, even in the presence of a
toplevel, provided the right approach is taken. 

We also found very few good example of uses of continuations, aside the
implementation of corountines.  But this application of continuations is now
subsumed by threads in caml special light.

> PS: some continuation constructs have been proposed with different
> scope, extend and typing rules and without the toplevel problem,
> but there are not the Scheme callcc operator. Some of them can be
> expansed in a CPS program of rather the same size (read papers
>  by Olivier Danvy & all).

The zoology of continuation operators is also  studied in [1] in the
presence of a strongly typed system. 

   -Didier Remy.


[1] ftp.inria.fr:INRIA/Projects/cristal/Didier.Remy/prompt.dvi.Z

    Carl A. Gunter, Didier Rémy, Jon G. Riecke. "A Generalization of
    Exceptions and Control in ML". LFP'95, January 1995. 

    We add functional continuations and prompts to a language with an
    ML-style type system.  The operators significantly extend and
    simplify the control operators in SML/NJ, and can be themselves
    used to implement (simple) exceptions.  We prove that well-typed
    terms never produce run-time type errors and give a module for
    implementing them in the latest version of SML/NJ.
    (The code of the appendix is avalaible <A HREF="ftp://ftp.inria.fr/INRIA/Projects/cristal/Didier.Remy/prompt.sml">here</A>)