Continuations and threads (was Re: Iterators & generators)

[Harald Hanche-Olsen]

+ Thomas Wouters <thomas at xs4all.net>:

| On Thu, Feb 17, 2000 at 05:36:48PM -0500, Harald Hanche-Olsen wrote:
| > | and say "can't/won't finish this now, I'll store the state
| > | (frame) and let other execution contexts call me when I should
| > | continue".  When you want to resume the context, you "call" the
| > | continuation, which resumes running the suspended execution
| > | context at the next line after the call to suspend.
| > 
| > So far, this is not all that different from
| > coroutines/generators/threads/whatever.  To my mind, one of the
| > mindboggling things about continuations is that you can call the
| > same continuation multiple times, whereas when you call a
| > coroutine/generator, its program counter advances, so that the
| > next time you call it, you are really calling a new continuation.
| 
| If this is so, you could see 'a continuation' as a class of object
| that is defined in a running process, and when instantiated produces
| a python (thread ? process ? stackframe ?

The latter comes closest.  In fact, the continuation must contain not
only the current stack frame, but (a reference to) the whole chain of
them back to the top.  After all, the continuation represents the
future of the computation, and all those stack frames are surely
needed for that future.

| And the continuation[-class] stays valid regardless of what other
| instances of the continuation or other parts of the program do ?

Yep.

| What would a traceback generated by an exception in a continuation
| look like, by the way ?

It would show you all those stack frames that were saved with the
continuation in the first place.  In particular, the backtrace of the
function invoking the continuation would be nowhere in sight.  It is
lost forever, unless it is stored in a variable somewhere, as a result
of yet another continuation creating call.

| > maybe-posting-some-Scheme-code-could-obfuscate-the-issue-furhter-ly y'rs,
| 
| Probably, except that i dont know any Scheme, so it would probably
| fail to confuse me (unless it has well-known keywords do something
| not-very-well-known ;)

Okay, so I tried doing it in Python.  Maybe that will confuse you
enough?

The following code is written for a hypothetical Python which supports
a new function which I will name call_cc.  It's almost like Scheme's
call/cc, except it allows ekstra arguments (for convenience, since
lambdas are more awkward in Python than in Scheme).

If you say call_cc(proc, arg, ...) then proc will be called with the
continuation of the call to call_cc as its first argument, and the
remaining arguments (if any) thereafter.  If proc returns normally,
then call_cc returns normally, with the return value from proc.  If
the continuation is invoked (always with a single argument), then
call_cc returns with that arguments as its value.  The latter may
happen many times, both before and after (or instead of) the former.

Now to my example.  I hope and think it's correct - but for natural
reasons I cannot test it.  It is a simple generator class.  Thereafter
is an example of using this class for the (rather silly) purpose of
generating Fibonacci numbers.

class Generator:
    def __init__(self):
        self.resume = self.firsttime
    def firsttime(self, ignore):
        self.body()
    def body(self):
        raise NotImplementedError
    def generate(self, value):
        call_cc(self.leave, value)
    def leave(self, resume, value):
        self.resume = resume
        self.exit(value)
    def enter(self, exit):
        self.exit = exit
        self.resume(None)
    def __call__(self):
        return call_cc(self.enter)

class Fibonacci(Generator):
    def body(self):
        self.generate(1)
        self.generate(1)
        a = b = 1
        while 1:
            a, b = b, a + b
            self.generate(b)

Running this would look as follows:

>>> fib = Fibonacci()
>>> fib()
1
>>> fib()
1
>>> fib()
2
>>> fib()
3
>>> fib()
5
>>> fib()
8
>>>

What's going on?  I am entering teaspoon feeding mode here, as there
is no other way to explain it:

My first call to fib() enters (as do they all) via the __call__
method, which simply calls enter with a continuation.  What is
this continuation?  It is the future of the computation upon return
from that call_cc invocation.  That future is to return the returned
value to the caller of __call__, that is of fib itself.  This
continuation is stored in exit.  It should now be clear that if
anybody calls exit(something), then that something will be
returned as the value of the first call to fib().  enter proceeds
to call resume(None) -- later, resume will be a continuation,
and so it must be given an argument, though that argument will be
ignored here.  This time around, resume is firsttime, which calls
body, which proceeds to call generate(1).

Now, things are getting interesting!  generate calls leave with a
continuation and the value (1), and leave squirrels that continuation
away in resume before calling exit(1), which as we saw will cause the
first call to fib() to return the value 1.  But what *is* that
continuation?  It is the future of the computation upon return from
that call_cc invocation.  And that future is:  To throw away the
return value, then return None as the value of the call to generate.
Clearly, if that continuation is ever called, body will resume
executing after its first call to generate.

Confused yet?  To add insult to injury I will go through what happens
next time:  We call fib() again; enter stores the new return
continuation in the exit variable, and the cycle repeats itself.
Except this time around, resume holds a continuation from the
previous time, and when enter calls it, body behaves like generate
just returned, and keeps on executing.

This is the way in which continuations can be used to create
generators.  Coroutines are pretty much the same thing.  At first
glance, it may look like I only use backwards continuations here;
i.e., I never call a continuation after the procedure defining it has
exited.  But I *do* call it after the invocation of another
continuation has thrown us out of that procedure's execution frame,
which is nearly as "bad", and which shows that this is hard to
implement in a stack-based setting.

if-you-could-follow-this-you-can-follow-any-argument-
no-matter-how-convoluted-ly y'rs,
-- 
* Harald Hanche-Olsen     <URL:http://www.math.ntnu.no/~hanche/>
- "There arises from a bad and unapt formation of words
   a wonderful obstruction to the mind."  - Francis Bacon