Re: continuation efficiency

[Neil Jerram]

>>>>> "Thomas" == Thomas Bushnell, BSG <address@hidden> writes:

    Thomas> Martin Grabmueller <address@hidden> writes:
    >> call/cc does a full copy of the machine stack, to be able to
    >> install it again when the continuation is invoked.  This
    >> requires memory allocation and copying, which is a bit slow.
    >> 
    >> call/ec, on the other hand, does not need to preserve the
    >> stack, since it only allows calls upwards in the call chain.
    >> Think of call/ec as throw/catch and you'll see.  So call/ec is
    >> less powerful, but faster (in Guile, other Schemes may vary).

    Thomas> This all depends on the *implementation*.  The original
    Thomas> post implied that call/ec was not a primitive.  If it is
    Thomas> implemented as a wrapper around call/cc, then how can it
    Thomas> be more efficient?

Right now, `catch' and `throw' are builtins in Guile, *not*
implemented on top of `call/cc' (which is also a builtin, of course).
The `catch' and `throw' builtins avoid copying the stack.  And
`call/ec' can be implemented using `catch' and `throw', and so avoid
copying the stack.

I've appended a node (`Exception Implementation') from the Guile
reference manual that may help clarify the situation.

        Neil


How Guile Implements Exceptions
-------------------------------

   It is traditional in Scheme to implement exception systems using
`call-with-current-continuation'.  Continuations (*note
Continuations::) are such a powerful concept that any other control
mechanism -- including `catch' and `throw' -- can be implemented in
terms of them.

   Guile does not implement `catch' and `throw' like this, though.  Why
not?  Because Guile is specifically designed to be easy to integrate
with applications written in C.  In a mixed Scheme/C environment, the
concept of "continuation" must logically include "what happens next" in
the C parts of the application as well as the Scheme parts, and it
turns out that the only reasonable way of implementing continuations
like this is to save and restore the complete C stack.

   So Guile's implementation of `call-with-current-continuation' is a
stack copying one.  This allows it to interact well with ordinary C
code, but means that creating and calling a continuation is slowed down
by the time that it takes to copy the C stack.

   The more targeted mechanism provided by `catch' and `throw' does not
need to save and restore the C stack because the `throw' always jumps
to a location higher up the stack of the code that executes the
`throw'.  Therefore Guile implements the `catch' and `throw' primitives
independently of `call-with-current-continuation', in a way that takes
advantage of this _upwards only_ nature of exceptions.