On Thu, 27 January 2000, "Vassili Bykov" wrote:
Excellent summary Vassili! Sorry I missed it before. --jtg
From: Jarvis, Robert P. (Contingent) [mailto:Jarvisb@timken.com]
OK, I'll exhibit my ignorance :-). What are continuations, and what are they useful for? Same questions for coroutines.
Continuations is a big topic. They are pretty mind-bending, so no explanation can replace actual use of them. I am attaching my continuations (still work in 2.7) for playing with.
Continuations is an abstraction for non-local control transfer used (among some other languages) in Scheme as the foundation for all the other non-local control tricks. Things like non-timeslicing multitasking, exceptions, catch/throw can all be implemented using continuations.
First of all, to get matters straight, what one could implement using continuations could be implemented by "regular" Smalltalk means or is already available, as objects and blocks, exceptions and processes. Within Smalltalk, using those would of course be a better solution. This is what I meant saying that continuations are far out of Smalltalk thinking. I still find it neat that they can be implemented in Squeak at the image level. (You can almost, but not quite, do that in VW--or maybe YOU can).
Here is what continuations are. Suppose we have a piece of code that reads "quux := aFoo bar". While the #bar message send is in progress, we can say that the piece of code "quux := ..." expects the value returned by "aFoo bar" to substitute it in place of the ellipsis. We can express this expectation as a block "[:a | quux := a]". We can imagine that once "aFoo bar" completes, the execution continues by invoking that block, with the result returned from the #bar message as the argument. This one-argument block is called the continuation of the message send--because it describes how execution continues after the message send returns.
As far as most languages are concerned, continuations are only a theoretical concept. Scheme, on the other hand, makes them first class. It provides a function call-with-current-continuation, often also available as call/cc, expecting a one-argument function. It then calls that function passing the continuation of the (call/cc ...) as the argument. The continuation behaves as a one-argument function; calling it has an effect of returning from the (call/cc ...) form. If you feel OK about reading some Scheme, here is a stupid but simple example
(define (foo n) (call/cc (lambda (cont) (if (zero? n) (cont 'zero)) 'non-zero)))
Here, the continuation is used for non-local exit. A similar thing in Smalltalk, shown on c.l.s a couple of times by Eliot Miranda and myself would be
Block{Context,Closure,whatever}>>valueWithExit ^self value: [:result | ^result]
MyClass>>foo: n | temp | temp := [:exit | n = 0 ifTrue: [exit value: #zero]. #non-zero] valueWithExit
(without the #valueWithExit thing, you could not have #zero assigned to "temp", ^ would just leave the method).
The funky part is, you can hold onto a continuation object and call it multiple times, thus causing one function call return multiple times along the same call chain. For example, in Scheme after you evaluate
(begin (call/cc (lambda (cont) (set! print-again cont))) (display "Hello again"))
you could many times evaluate
(print-again 'bogus)
and each time it would print "Hello again", because control "escapes" into the continuation and returns along its sender chain--that is the call/cc will return (with 'bogus as the value which is ignored) and will then move on to the next form.
See a test method at the class side of Continuation class in the attached change set. In this implementation, Block methods #valueWithCurrentContinuation and #valueWithCC are the analogs of call-with-current-continuation and call/cc.
Alan (Knight) already mentioned that you can mimic this stuff by explicitly passing blocks around. This is true by definition--continuations behave *almost* like functions of one argument (incidentally, allowing them to have may arguments yields a language with multiple return values). What all the fuss is about then? Theoretically, execution of any program can be viewed in terms of continuations. In languages with first class continuations (Scheme or Squeak with the attached file-in), you can "lift" a contunuation as a "real" object off a syntactically "normal" program. In a language without first-class continuations, but with closures, you can manually chop and slice your program into continuations expressed as blocks.
How about this summary of how continuations are different from a bunch of blocks passed all over:
Continuations allow to introduce non-standard evaluation rules in code that uses standard syntax.
It is getting late, so I'll wrap up here. (I am not sure anyone will read this far anyway. :-) Just a few interesting points before the end.
A continuation may look just like a function of one argument (a one-argument block in the Smalltalk version), but the catch is it has weird call semantics. In the "print-again" example, evaluating
(begin (print-again) (display "and goodbye"))
will never print "goodbye" because calling a continuation, speaking in technical terms, replaces the call stack so (print-again) will never return to the caller. You can see the gory details in the code.
Why does call/cc have the confusing form of accepting a function that will receive the actual continuation? Could we just have something like get/cc, a no-argument function that returns its own continuation? get/cc is less general. It can be implemented using call/cc, in a very cool way:
(define (get/cc) (call/cc call/cc))
(proving that it works is an exercise to the reader). There are a couple of pragmatic considerations as well.
Finally, people have been known to insist that the correct implementation of call/cc is:
(define (call/cc foo) (display "cc: Segmentation fault. Core dumped."))
A good book discussing all that is Lisp in Small Pieces by Christian Queinnec.
Cheers,
--Vassili
______________________________________________________ Jan Theodore Galkowski www.smalltalk.org/ http://www.scguild.com/usr/1707I.html demiourgos@smalltalk.org www.marssociety.org/ ********************************************** PGP Key Fingerprint: 2757 F86D AA51 677D 38D7 964B 9A8D 7852 A494 3790 ********************************************** Get my Public Key from my home page at: http://home.stny.rr.com/algebraist/ **********************************************
______________________________________________
Get free e-mail at http://www.britannica.com
squeak-dev@lists.squeakfoundation.org