Continuations and threads (was Re: Iterators & generators)

[Paul Prescod]

Aahz Maruch wrote:
> 
> ...
> 
> Okay, now I'm starting to get this (be very, very frightened).  Now, can
> you (or someone) provide an equally simple explanation of the
> differences between continuations and threads?  

I'm not sure if I believe what Tim said about implementing threads with
continuations or vice versa. A continuation is, in my mind, only vaguely
related to a thread.

Okay, imagine you are going through a Python program and you could all
of a sudden say to the interpreter: "remember this stack frame and all
variables in scope. Give it to me as a Python object. I'll do something
with it later." It's like groundhog day. You can *go back in time* to
somewhere you were before. Actually its the opposite of groundhog day
because what will have changed is globals and things relating to I/O. So
its like the little town in groundhog day is stuck in time but you can
tell that time is progressing because you can see news from the outside
world on television. So its more like the Truman show. Only in reverse.
:) That clears things up, right?

Anyhow, consider what you need to do to implement exception handling.
You need to say: "if this exception ever occurs, I want you to jump back
to this point in the program's execution." Well, that can be implemented
with continuations.

error=None

def SomeFunction():
	if somethingIsNotRight():
		error="Something stinks!"
		jumpBackToOnError()

jumpBackToOnError=currentContinuation()

if error:
	print "An error occurred", error
else:
	SomeFunction()

It's ugly (low-level) but it works. You could have a hashtable mapping
exception types to continuations. There are ways to avoid all of the
global variables also.

Okay, next consider coroutines. Two flows of control that go back and
forth between each other:

out=0

def producer():
    global producer_continuation, consumer_continuation, data
    while 1:
	producer_continuation=currentContinuation()
	data = readSomeData()
	consumer_continuation( )

def consumer():
   global producer_continuation, consumer_continuation, data
   while 1:
	consumer_continuation=currentContinuation()
	producer_continuation( )
	print data

producer_continuation=None
consumer_continuation=None
data=None

You might want to include some exit condition!

You could combine the exception handling pattern with the coroutine
pattern so that your exception continuation jumps into the middle of a
loop:

while 1:
	print error
	error_count=error_count+1
	next_error()

Not much more exciting than a callback but it would be if there was a
lot of local state that a callback would need to store in an object
somewhere.

You can also use continuations to implement back-tracking. You try one
path and if it fails you "jump back" and try the other. If you have
several days to expend in mind-altering time-travelling code obfuscation
you should try to puzzle out the strategy used by schelog to implement
prolog in Scheme using continuations.

http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/impl/prolog/schelog/0.html

Ahh, for the good old days when I could spend hours on things that might
or might not ever have any job relevance.

Sigh-I-need-to-go-back-to-school-or-get-Tim-Peter's-job-ly 'yrs

-- 
 Paul Prescod  - ISOGEN Consulting Engineer speaking for himself
"The calculus and the rich body of mathematical analysis to which it
gave rise made modern science possible, but it was the algorithm that
made possible the modern world." 
        - from "Advent of the Algorithm" David Berlinski
	http://www.opengroup.com/mabooks/015/0151003386.shtml