[racket] design and use of continuation barriers

At Fri, 9 Jul 2010 14:56:16 +0000, Taylor R Campbell wrote:
> I have several questions about continuation barriers.  I have tested
> some examples in PLT Scheme v4.2.4, because that's what I have handy;
> if the semantics has changed significantly in Racket, let me know
> before wasting time with the rest of this message.

There have been no changes until just now.

> First, is there any document generally describing the rationale for
> the design of continuation barriers and advice about when to use them?

No, so here's an attempt:


Use a continuation barrier when calling unknown code and when it's too
painful to contemplate multiple instantiations of the continuation
leading to the call.

One example is a GUI event loop, where some unknown code is invoked as
a callback.  (I'll draw continuations as a downward-growing chain of
continuation frames.)

     (GUI)
       |
  (button push)
       |
   (callback)

The callback path for a button push is probably different from the one
for a menu selection:

     (GUI)
       |
  (menu select)
       |
   (callback2)

If `callback' captures its continuation and `callback2' invokes it,
then the GUI toolkit will try to continue the button push twice, which
will probably lead to a crash. A continuation barrier before each
callback prevents such problems.


That's an example of when to use a continuation barrier, but I think
you have in mind the fact that there are other ways to solve the
problem:

 * `dynamic-wind' --- A `dynamic-wind' could be used to guard against
   an escape from `callback2' that would enter `callback'.

   Using `dynamic-wind' turns out not to be enough if you have with
   multiple threads:

         (GUI)         (...)    (...)
           |             |        |
      (button push)     (B)      (C)
           |
          (A)

   A `dynamic-wind' post-thunk there could prevent applying the
   continuation `B' at `A', so you won't lose the GUI loop. For
   applying `A' at `B', however, a guard in a `dynamic-wind' pre-thunk
   may be too late; the GUI loop would be duplicated before the
   pre-thunk could complain.

 * Delimited continuations --- Assuming that the continuation above
   `GUI' contains no unknown code, a continuation prompt can solve the
   problem especially cleanly. A prompt before `callback' means that
   `callback' can only capture a continuation up to the point of the
   button push, and `callback2' changes the continuation only below
   the menu selection.

   In fact, `callback' and `callback2' might be happier in that world;
   replace "GUI" with "continuation-based web framework" and change
   the two GUI events to steps in a web session, and that's exactly
   why you want delimited continuations for web servers.

   A delimited continuation also solves the multiple-thread problem.


As another example for barriers, imagine that the GUI event-handling
loop does not exist a priori, and it is instead started explicitly by
some unknown code:

    (setup)
       |
     (GUI)
       |
     (...)
       |
   (callback)

Let's consider the possibilities without barriers, first.

Note that delimited continuations no longer solve the problem if you
also have prompt tags.  The `setup' code might set a prompt with a
different tag than the one used for a prompt in `callback', and then
`callback' could capture or install a continuation with that tag,
avoiding the prompt set before `callback'.

A `dynamic-wind' can still fix the problem. A `dynamic-wind' before
`callback' isn't good enough, since that would be too late to catch a
jump back down into GUI. A pre-thunk check at the start of the GUI
could prevent jumps back in after the GUI has exited, though (and that
approach also works with threads). As before, a `dynamic-wind' before
`callback' could still prevent escapes that would lose the GUI event
loop.


More realistically, in a setting where the GUI is started explicitly,
the GUI probably can support escapes ok. That is, a `dynamic-wind'
post thunk for the GUI probably just cleans up and lets the GUI go
away.

In fact, for many similar cases, a programmer is more likely to use
`with-handlers' to handle escapes than `dynamic-wind'... and this is
where we start to want barriers after all. Allowing a jump back into
stateful code is often so difficult that the programmer doesn't even
consider the possibility. The programmer just uses `with-handlers' to
deal with escapes, and doesn't add a `dynamic-wind' at the start of to
prevent jumping back in. It's somewhat easier to remember a
continuation barrier at the point where unknown callback is invoked;
more importantly, a continuation barrier can be used without knowing
the start of the code that most be protected.

Imagine that the relevant code isn't a GUI toolkit that obviously
needs protecting, but some library function that has no explicit
callbacks to untrusted code.  The continuation seems to involve just
the library's own code:

    (...)
      |
    (L-1)
      |
    (L-2)

Unless the implementor of the library has been unusually careful,
however, the current exception handler is an implicit callback that is
always possible to invoke. The library implementor is unlikely to
consider that possibility and add suitable protection to the
continuation before `L-1'.

To help library implementers, a continuation barrier is installed just
before before an exception handler is called. That way, if it is
possible for an exception to be raised, the implementer of `L-1' and
`L-2' can just use `with-handlers' to clean up, instead of having to
worry about jumps into the library.

Along similar lines, a barrier is used before dispatching to functions
that implement an I/O port, since programmers typically do not think
of `write' as call to untrusted code. Other extensible datatypes of
core constructs use barriers similarly. In all cases, there's a clear
place to put a barrier before the "callback", and using a barrier
instead of `dynamic-wind' relives the programmer from explicitly
identifying the start of every sensitive continuation.


> (define (call-with-current-continuation procedure)
>   (call-with-composable-continuation
>    (lambda (continuation)
>      (procedure (lambda arguments
>                   (abort-current-continuation
>                       (default-continuation-prompt-tag)
>                     (lambda ()
>                       (apply values arguments))))))))
>
> Can anyone explain to me what is wrong with my definition of
> CALL-WITH-CURRENT-CONTINUATION, 

Except for the `dynamic-wind' interaction that you noted, I can't point
to any problem.

See also the implementation of `call/cc' for R6RS --- in the
"base.rkt" library in the "rnrs" collection --- in a Racket version
before 5.0.0.9. The "rnrs" variant of `call/cc' combines `call/ec' and
the original `call/cc', so it can use the escape continuation when
needed just to escape.

> and why full continuations may not be
> used for non-local exits across a continuation barrier, while
> escape-only continuations and prompt aborts can be used for exactly
> that?

After reviewing all the details, I've concluded that it was just
laziness on my part.

The immediate problem was a limitation of the implementation. A
barrier-allowed escape is implemented differently than an
full-continuation jump, and the implementation of the Racket run-time
system attaches certain clean-up actions only to the escape
implementation.

The "rnrs" implementation worked around that limitation, but it had
the problem that the argument to `call/cc' is not always called in
tail position. The lack of tail recursion is detectable only by using
continuation marks, though, since it is called in tail position if the
current continuation has already been captured. Since R6RS does not
include continuation marks, the `call/cc' plus `call/ec' trick seemed
ok.

I've just pushed a change to Racket to use the "rnrs" trick
internally. Since the trick is implemented within the run-time system,
it can also hide the continuation-mark difference. In fact, given the
continuation machinery that we developed a couple of years ago, the
change was pretty easy; I just hadn't thought about it enough.