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)control0
can easily implement all of them, and that's what the paper I linked basically does, using a control operator with control0
-like semantics.shift0
and control
can easily implement shift
.shift
couldn't implement control
, but it was disproved in Shift to control, also proving that any control operator can implement each other (this is my logical conclusion, it is known that they can, but I'm not sure that this is the why)call/cc
and set!
, but if you remove set!
, call/cc
becomes helpless. And delimited continuations can express mutable state, or any computational effect.call/cc
application with set!
, that code is just emulating delimited continuations.