Awesome, Scott, although I am still struggling to get my mind contraverted around/inside/between the concepts. I appreciate the scheduling examples. What about exceptions/handlers?
I will have to get back to this on the weekend. Real job to do in the meantime, you know...
thanks, Rob
-----Original Message----- From: Scott A Crosby [mailto:crosby@qwes.math.cmu.edu] Sent: Friday, February 01, 2002 12:16 PM To: Withers, Robert Cc: 'squeak-dev@lists.squeakfoundation.org' Subject: [DOC] Call/CC Re: [Q][Goodie] continuations (was: RE: Tail Call)
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
On Fri, 1 Feb 2002, Withers, Robert wrote:
Awesome, Scott, although I am still struggling to get my mind contraverted around/inside/between the concepts. I appreciate the scheduling examples. What about exceptions/handlers?
Easy!
Processor>>error self callCC: [:cont | self exnhandler value: true]
Processor>>errorIn: aBlock ^self callCC: [:cont | self exnHandler: self cont false.]
Or, a more sophisticated example that handles objects and nested exn handlers.
Processor>>error: errorObj self callCC: [:cont | self exnhandler value: errorObj]
Processor>>errorIn: aBlock :handle: aHandleBlock oldhandle _ self exnHandler. err _ self callCC: [:cont | self exnHandler: self cont nil.] err ifNil: [^nil] self exnHandler: oldhandle. aHandleBlock value: err.
--
Scott
-----Original Message----- From: Scott A Crosby [mailto:crosby@qwes.math.cmu.edu] Sent: Friday, February 01, 2002 12:16 PM To: Withers, Robert Cc: 'squeak-dev@lists.squeakfoundation.org' Subject: [DOC] Call/CC Re: [Q][Goodie] continuations (was: RE: Tail Call)
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
-- No DVD movie will ever enter the public domain, nor will any CD. The last CD and the last DVD will have moldered away decades before they leave copyright. This is not encouraging the creation of knowledge in the public domain.
On Fri, 1 Feb 2002, Scott A Crosby wrote:
On Fri, 1 Feb 2002, Withers, Robert wrote:
Awesome, Scott, although I am still struggling to get my mind contraverted around/inside/between the concepts. I appreciate the scheduling examples. What about exceptions/handlers?
Easy!
But this sort of stuff ain't.... Unless I have a day or two to burn trying to reason through it all:
http://citeseer.nj.nec.com/40028.html
Heh, read it and cry. I do. :)
Scott
squeak-dev@lists.squeakfoundation.org