Name: Anonymous 2005-12-21 8:09
Because I'm learning it, almost done through the tutorial, and it looks great.
call/cc
captures the whole continuation, not part of it. This means that if you're writing a continuation-based green threads library using call/cc
, it will not only capture the current continuation of the thread, but also the scheduler's. This is easily fixed by delimiting the captured continuation with (prompt (next-thread-cont))
. Usually, call/cc
is affected by prompts (like in the usual CPS implementation of single prompt shift
/reset
), but its interface remains horrible and useful only for early returns and few other things (IMHO).*F*
operators) that act all almost the same, but differ when you nest them (note: prompt
and reset
are the same thing, I'll be using prompt
here)(prompt E[(control0 k expr)])
(-F-) captures the continuation E[]
, and reifies it as (λ (x) E[x])
, it is then passed to a procedure (λ (k) expr)
, reducing to: ((λ (k) expr) (λ (x) E[x]))
.(prompt E[(shift0 k expr)])
(-F+) is the same thing, but the captured continuation is reified as (λ (x) (prompt E[x])
, reducing to ((λ (k) expr) (λ (x) (prompt E[x]))
.(prompt E[(control k expr)])
(+F-) reifies the continuation the same as control0
, but it introduces a prompt
at the bottom, reducing to (prompt ((λ (k) expr) (λ (x) E[x])))
.(prompt E[(shift k expr)])
(+F+), logically, does the same thing as shift0
, introducing a prompt
at the bottom: (prompt ((λ (k) expr) (λ (x) (prompt E[x]))))
.shift
and reset
, it's really simple, in CPS:(reset E) => (λ (cc) (cc (E (λ (x) x))))
(shift E) => (λ (cc) (E (λ (retval) (λ (kk) (kk (cc retval)))) (λ (x) x)))
reset
sets the continuation of E
(a thunk) to the empty continuation λx.x
, and applies its return value to the old continuation cc
. shift
reifies the current continuation cc
into a function that takes one argument retval
and a continuation kk
, and applies cc
to retval
and its result to kk
, and sets the continuation of E
(an unary function) to the empty continuation, so that it will immediately return to the nearest reset
.shift
's reified continuation has a nested application in it, and CPS taught us that it is wrong and evil, so we transform that application in standard CPS: (cc x kk)
. kk
is acting as a continuation for cc
, which is a continuation, so it is a continuation to a continuation, or a metacontinuation. And as you can see, there's one in reset
too! (the transformation is left as an exercise for the reader)shift
/reset
implementation in terms of call/cc
and set!
uses the same approach, storing the metacontinuation in some mc
variable.call/cc
affected by this? The usual CPS transformation is(call/cc E) => (λ (cc) (E (λ (x) (λ (kk) (cc x))) cc))
x
to the old one, and doesn't change the continuation of E
.reset
resets a continuation to the empty continuation, and uses the old one as metacontinuation for it, so call/cc
will only capture the partial continuation to the nearest reset
.control
, and their 0
variants? And wouldn't various applications of reset
interfere with each other? Yes, they would. The solution is prompt tags. A prompt tag is just a mark in a continuation frame, and this definition is as useful as saying that monads are monoids in the category of endofunctors, so let's make an example of how they're implemented in non-CPS:(prompt-at *tag* ...)
marks the activation record with *tag*, (control0-at *tag* k ...)
starts copying the activation records and it stops right before a record marked with *tag*, possibly raising an exception of some sort when it can't find one, and reifies it as above. The end.control-at
and shift-at
stop right after the tag, shift0-at
and shift-at
introduce one in the captured continuation. The end. (Yes, it's that simple)