[racket] design and use of continuation barriers
Taylor R Campbell
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.
First, is there any document generally describing the rationale for
the design of continuation barriers and advice about when to use them?
Here are two possible implementations of continuation barriers, from
an initial naive (and incorrect) understanding. One precludes
non-local exit; the other also precludes re-entry.
(define (call-with-continuation-barrier procedure)
(dynamic-wind
(let ((once? #f))
(lambda ()
(if once? (error "Re-entry prohibited."))
(set! once? #t)))
procedure
(lambda () 0)))
(define (call-with-continuation-barrier procedure)
(let ((done? #f))
(dynamic-wind
(let ((once? #f))
(lambda ()
(if once? (error "Re-entry prohibited."))
(set! once? #t)))
(lambda () (begin0 (procedure) (set! done? #t)))
(lambda ()
(if (not done?) (error "Non-local exit prohibited."))))))
If only full continuations are involved, no escape-only continuations
or delimited continuations, the latter definition is the correct one,
I believe. However, escape-only continuations and prompt aborts can
cross continuation barriers, but trigger the exit procedure in the
latter definition.
(call-with-current-continuation call-with-continuation-barrier)
;Error!
(call-with-escape-continuation call-with-continuation-barrier)
;OK by PLT Scheme, error by the second definition
(call-with-continuation-prompt
(lambda ()
(call-with-continuation-barrier
(lambda ()
(abort-current-continuation (default-continuation-prompt-tag)
values)))))
;OK by PLT Scheme, error by the second definition
Consequently, there are cases where replacing correct uses of
CALL-WITH-ESCAPE-CONTINUATION by CALL-WITH-CURRENT-CONTINUATION break
a program, which is puzzling to me. Furthermore, the following
definition of CALL-WITH-CURRENT-CONTINUATION is incorrect, because I
can use it to cross continuation barriers that can't be crossed by the
built-in CALL-WITH-CURRENT-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, 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? I am sure that part of what confuses me is that I don't know
what the general intended use of continuation barriers is.
There is one problem with the definition: it doesn't work if there is
a continuation barrier between the current continuation and the
nearest prompt tag. So here's a nefarious way around that, which I
believe behaves semantically like CALL-WITH-CURRENT-CONTINUATION
(except perhaps for DYNAMIC-WIND execution) but can cross more
continuation barriers:
(define (call-with-nefarious-continuation procedure)
((with-handlers
((exn:fail:contract:continuation?
(lambda (exception)
exception ;ignore
(lambda ()
(call-with-current-continuation procedure)))))
(call-with-composable-continuation
(lambda (composable-continuation)
(call-with-current-continuation
(lambda (full-continuation)
(lambda ()
(procedure
(lambda arguments
(define (return) (apply values arguments))
((with-handlers
((exn:fail:contract:continuation?
(lambda (exception)
exception ;ignore
(lambda ()
(abort-current-continuation
(default-continuation-prompt-tag)
(lambda ()
(composable-continuation return)))))))
(full-continuation return)))))))))))))
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
Matthew Flatt
> 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.
Taylor R Campbell
From: Matthew Flatt <mfl...@cs.utah.edu>
At Fri, 9 Jul 2010 14:56:16 +0000, Taylor R Campbell wrote:
> 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:
Excellent, thank you for the prompt and detailed reply!
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.
What should I do if I want to preclude only multiple uses of the
continuation, but still allow single uses even if they are non-local?
For example, consider
(define (walker->streamer walker)
(lambda (object)
(lazy
(reset (walker object
(lambda (element)
(shift k (stream-cons element (lazy (k))))))
stream-nil)))).
(I use SHIFT and RESET here for brevity; of course this should use
explicit prompt tags in practice.) Now if I write
(define (walk-list list procedure)
(let loop ()
(if (pair? list)
(begin (procedure (car list))
(set! list (cdr list))
(loop))))),
it may be too painful for me to contemplate multiple uses of any of
PROCEDURE's continuations, but WALK-LIST behaves perfectly nicely as
an argument to WALKER->STREAMER. Erecting a continuation barrier
about the call to PROCEDURE precludes this, though.
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.
I don't understand this last clause, that the GUI loop would be
duplicated before the pre-thunk could complain. Are you worried that
throwing into A will trigger DYNAMIC-WIND entrance procedures up in
the `(GUI)' frames that shouldn't be run more than once? If so, can't
those detect being run more than once and signal an error, as you
suggested below in the setup code?
Is the problem that you want the exception handler enclosing B to
handle the error, rather than any exception handler in the GUI's
dynamic context? This seems to me to be the only real difference.
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.
That sounds to me like a mistake on the part of the programmer, but
abstractions or idioms appropriate for cleaning up are a separate
discussion, so I'll refrain from getting into that for the moment.
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.
Can you be more specific about where continuation barriers are placed?
I just tried jumping about inside and outside handled extents and the
handlers themselves, and didn't hit any continuation barriers:
((call-with-current-continuation
(lambda (outside)
(lambda ()
(with-handlers
((continuation?
(lambda (inside)
((call-with-current-continuation
(lambda (handler)
(outside
(lambda ()
(handler
(lambda () (inside (lambda () 0))))))))))))
(list 1 ((call-with-current-continuation raise))))))))
;Value: (1 0)
It doesn't make a difference whether I pass a second argument to RAISE
-- either #T or #F. I've tried various different configurations and
nestings of calls to OUTSIDE, INSIDE, and HANDLER, too.
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.
So can full continuations now be used to exit across continuation
barriers just like exit-only continuations and prompt aborts, or are
exit-only continuations and prompt aborts now also prohibited from
exiting across continuation barriers?
Taylor R Campbell
From: Taylor R Campbell <campbel...@mumble.net>
What should I do if I want to preclude only multiple uses of the
continuation, but still allow single uses even if they are non-local?
Sorry, should've spent half a minute thinking about that before making
my message even longer by asking it.
(define (guarantee-single-return procedure)
(let ((returned? #f))
(begin0 (procedure)
(if returned? (error "Multiple return prohibited."))
(set! returned? #t))))
Matthew Flatt
> 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.
>
> I don't understand this last clause, that the GUI loop would be
> duplicated before the pre-thunk could complain. Are you worried that
> throwing into A will trigger DYNAMIC-WIND entrance procedures up in
> the `(GUI)' frames that shouldn't be run more than once? If so, can't
> those detect being run more than once and signal an error, as you
> suggested below in the setup code?
If GUI has `dynamic-wind's inside, it seems more likely that it could
deal with restarts --- or, yes, at least detect and prevent them.
I was more concerned with what happens when the pre-thunk at `A'
discovers a problem. If it raises an exception at that point, then the
GUI will see the escape and may attempt clean-up actions that crash. I
guess "too late" in this case is tied up with my view that libraries
often will include escape-handling code without restart-handling code
(and that it should be ok for them to be written that way).
> 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.
>
> Can you be more specific about where continuation barriers are placed?
> I just tried jumping about inside and outside handled extents and the
> handlers themselves, and didn't hit any continuation barriers:
>
> ((call-with-current-continuation
> (lambda (outside)
> (lambda ()
> (with-handlers
> ((continuation?
> (lambda (inside)
> ((call-with-current-continuation
> (lambda (handler)
> (outside
> (lambda ()
> (handler
> (lambda () (inside (lambda () 0))))))))))))
> (list 1 ((call-with-current-continuation raise))))))))
> ;Value: (1 0)
The `with-handlers' form escapes before applying a handler procedure.
To install an exception handler that is called in the dynamic extent of
`raise', use `call-with-exception-handler'.
> 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.
>
> So can full continuations now be used to exit across continuation
> barriers just like exit-only continuations and prompt aborts,
Yes.