* Re: Recursion, exception and continuations
1996-03-09 16:02 Recursion, exception and continuations Tarizzo Martial
@ 1996-03-11 11:07 ` Pierre Weis
1996-03-11 11:45 ` Francis Dupont
1 sibling, 0 replies; 4+ messages in thread
From: Pierre Weis @ 1996-03-11 11:07 UTC (permalink / raw)
To: Tarizzo Martial; +Cc: caml-list
> [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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Recursion, exception and continuations
1996-03-09 16:02 Recursion, exception and continuations Tarizzo Martial
1996-03-11 11:07 ` Pierre Weis
@ 1996-03-11 11:45 ` Francis Dupont
1996-03-11 13:42 ` Didier Remy
1 sibling, 1 reply; 4+ messages in thread
From: Francis Dupont @ 1996-03-11 11:45 UTC (permalink / raw)
To: Tarizzo Martial; +Cc: caml-list
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).
^ permalink raw reply [flat|nested] 4+ messages in thread