Hi Bijan and all,
That is a very good analogy, to me, at least at the design level. However, it's application is confusing, to say the least, especially when you consider it's implications in the squeak environment. I have a great need to understand it, however, because 'E' uses them to resolve the promises that are created from an eventual send. Eventual send semantics are my next little project (and I don't mean to just talk about it).
I have attached a continuation (call/cc) changeset, that came from Vassily Bykov. I do hope he doesn't mind me reposting it. It is for a non-BlockClosure image. I have been comparing it's implementation of continuations, with that of Boris' BlockClosure test case. They are very different, I think, since Vassily's Continuation class has a #captureSenderChain method where the entire stack is copied for later restore and proceed, as you discuss. Boris' continuation, on the other hand, seems to be just the BlockClosure he passes as the continuation block.
It is my feeling that an 'absolute' continuation (my term), like Vassily's Continuation, which captures the entire sender chain, may not be appropriate in the Squeak UI environment. When I highlight the example: #testAccumulator and doIt, followed by activating the Continuation, the Continuation stack includes those methods which processes the event loop and sent the mouse event to ultimately evaluate the doIt. I don't think these things should be in the continuation stack. Does it make sense for the user to be able to control how much stack is closed over?
Finally, could somebody explain what call/cc semantics are and how that differs from a continuation?
cheers, Rob
-----Original Message----- From: Bijan Parsia [mailto:bparsia@email.unc.edu] Sent: Friday, February 01, 2002 9:24 AM To: squeak-dev@lists.squeakfoundation.org Subject: Re: Tail Call
On Fri, 1 Feb 2002, Jerzy Karczmarczuk wrote:
Anthony Hannan:
Is tail recursion required for continuations? I really
don't understand
continuations, can you give me some pointers?
Scott Crosby says:
Tail recursion is not needed for continuations. You only
need closures,
but without tail recursions, continuations-style
programming can overflow
the stack much easier.
[snip]
I would be more categorical and I would say YES. Otherwise
there is no point
whatsoever in speaking about them. They are functional
models of "goto".
I won't argue with Scott, just tell a few more words from a
different
perspective.
[snip]
I'd still say "no". You don't need tail call optimization (TCO) to implement have explicit continuations. And you don't need TCO to use explicit, full, resumable continuations to use them to implement a variety of control flow structures (exceptions, for example), and even have that be somewhat practical. You do need them for general practical use of Continuation Passing Style (CPS), and I agree that CPS is the best reason to want them (in general, you're prolly better off implementing your control flow with a less general mechanism).
Let me add a more informal, sloganny account of continuations: continuations are "dynamic" closures. That is, just as closures "close over" the lexical environment, continuations "close over" the *invoking* environment (the analogy is with dynamic scoping of variables). By "freezing" a copy of the calling stack, continuations let you "continue" the compuation from that point any number of times. (Sorta like snapshotting the image after a debugger popped up. No matter what you do after that, you can always roll back to that snapshotted moment and "continue" in a different (or the the same!) way.)
Making fully resumable, indefinite extent, multiply invokable closures or continuations available to the host language is, in general, more heavyweight than alternatives (at least for the implementer). But when you need them, you need them.
(Note that a snapshot saves a lot more than the current continuation :))
Cheers, Bijan Parsia.
On Fri, 1 Feb 2002, Withers, Robert wrote:
Hi Bijan and all,
That is a very good analogy, to me, at least at the design level. However, it's application is confusing, to say the least, especially when you consider it's implications in the squeak environment. I have a great need to understand it, however, because 'E' uses them to resolve the promises that are created from an eventual send. Eventual send semantics are my next little project (and I don't mean to just talk about it).
Ok. In the case of a CPS style execution environment, the continuations are all explicit arguments.. But, since the real squeak runtime uses a stack to represent the continuation thats implicit as the return continuation... Normally, in most languages, you can never 'get your hands on it'. Call/CC (which means 'call with current continuation' is a way that gets your hands on that continuation..
Conceptually, CallCC should return a block that, when #value:, immediatly jumps back to the continuation. That invocation will not return [*]
foo ^(self callCC: [:continuation | self bar: continuation]) +10
bar: continuation continuation value: 15 ^16
You invoke foo, which passes a continuation of '{}+10' into the block, which gets passed to bar, which, when it invokes it, immediatly jumps back to the {}+10, which jumps back to foo which adds 10 which is then returned.
How about something like:
Processor class>>yield: self callCC: [:cont | newCont _ self suspendedCont. self suspendedCont: cont. newCont value: nil]
Which allows cooperative multithreading! Each time you invoke it, copies the old saved continuation thats in an instance variable, then saves the current one, then 'restarts' the first by invoking it with 'nil'! Now, if you had a queue there, or a heap.. Multipriority cooperative multithreading. :)
--
Now, in implementation terms in something like squeak, thats quite a bit uglier, because you can't take a stack of methodcontexts and pretend its an anonymous block that takes a single argument. Ergo, to get it, you do things like clone the entire methodcontext stack.
In the other examples we've given, we're not trying to access that 'system level' implicit continuation. We're making explicit continuations ourselves as blocks we pass them explicitly as arguments. Thats why those examples differ from callCC.
I have attached a continuation (call/cc) changeset, that came from Vassily Bykov. I do hope he doesn't mind me reposting it. It is for a non-BlockClosure image. I have been comparing it's implementation of continuations, with that of Boris' BlockClosure test case. They are very different, I think, since Vassily's Continuation class has a #captureSenderChain method where the entire stack is copied for later restore and proceed, as you discuss. Boris' continuation, on the other hand, seems to be just the BlockClosure he passes as the continuation block.
It is my feeling that an 'absolute' continuation (my term), like Vassily's Continuation, which captures the entire sender chain, may not be appropriate in the Squeak UI environment. When I highlight the example: #testAccumulator and doIt, followed by activating the Continuation, the Continuation stack includes those methods which processes the event loop and sent the mouse event to ultimately evaluate the doIt. I don't think these things should be in the continuation stack. Does it make sense for the user to be able to control how much stack is closed over?
Nominally a callCC style continuation is a single unit. This would indicate that, for example, the code is misarchitected. You might be able to avoid it, for example, by always spawning doIts in a different (clean) process, then have some special magic that suspends the UI process until that one finishes (or errors).
[*] There's some funky subtletly there. Invokign the current continuation never returns, because, nominally, the toplevel never returns... But, you can implement things like [fork] as:
fork: aBlock self callCC: [:cont | self suspendedCont: [ :unused | aBlock value: true] cont. cont value: false]
exit: self callCC: [:cont | self suspendedCont value: nil]
Basically, take the current continuation, add it to the suspended context's queue, then continue the continuation you were passed, continuting it with either true or false, depending on which child you are. :) Now for this to actually work, you'll need the current process to #yield as above to allow the fork.
And exit just throws away the current continuation, and loads and restarts one of the saved ones.
Continuations this way can be mind-blowing. :) I'm half reconstructing all of this stuff on the fly. Its great! :) I've not gotten this deep in a while.
Finally, could somebody explain what call/cc semantics are and how that differs from a continuation?
If you have any other questions, Post away.
Scott
squeak-dev@lists.squeakfoundation.org