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.