[DOC] Call/CC Re: [Q][Goodie] continuations (was: RE: Tail Call)

Scott A Crosby crosby at qwes.math.cmu.edu
Fri Feb 1 17:15:35 UTC 2002


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





More information about the Squeak-dev mailing list