Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

What's bad about Python?

Name: Anonymous 2005-12-21 8:09

Because I'm learning it, almost done through the tutorial, and it looks great.

Name: Anonymous 2011-07-21 3:43

>>93
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).

There are four control operator (called *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])))).

How to implement them? For plain 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)))
So, 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.
As you can see, 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)
The shift/reset implementation in terms of call/cc and set! uses the same approach, storing the metacontinuation in some mc variable.
So, how is call/cc affected by this? The usual CPS transformation is
(call/cc E) => (λ (cc) (E (λ (x) (λ (kk) (cc x))) cc))
or, it disregards the new continuation and applies x to the old one, and doesn't change the continuation of E.
But 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.

This is cool and all, but what about 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:

Let's assume that the implementation uses a chain of activation records,
(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)

The CPS implementation of them is longer, and it's all about masturbation over metacontinuations and sequences of continuations, which is better explained here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.8645&rep=rep1&type=pdf (hint: ignore the monads part if you're not interested in them)

This post is too long.

Name: Anonymous 2011-07-22 3:12

>>99
Maybe I'm stupid
Oh, no, you're not. That's a legitimate question, instead, I dind't mention that.

Yes, they can, but for some pairs it's a bit tricky:
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.
For many years, many believed that 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)

>>98
If so, what is that useful for?
Nothing, you can do anything delimited continuations do with call/cc and set!, but if you remove set!, call/cc becomes helpless. And delimited continuations can express mutable state, or any computational effect.

So, nothing, really, if you've got mutable state, you can just drop delimited continuations, the only advantages are efficiency, readability, ease of use, theoretical beauty, and the lack of need of harmful mutable state.
Also, most of the time you don't need to capture the whole continuation.
When you see some strange nested call/cc application with set!, that code is just emulating delimited continuations.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List