Continuations and threads (was Re: Iterators & generators)

[Tim Peters]

[Paul Prescod]
> I'm not sure if I believe what Tim said about implementing threads with
> continuations or vice versa.

This is going to turn into another Vladimir "locality of reference"
three-msg gloss on a toss-away parenthetical comment <wink>.  Like I said,
this stuff gets very involved very fast, and without a precise model of
computation to build on is just going to thrash (another parallel to LOR
...).

I really should *not* have said that continuations can be implemented via
threads.  My apologies for that.  They can be <wink>, but not with the
flavor of threads most people are most likely to think of (the other thing
needed is hinted at below).

> A continuation is, in my mind, only vaguely related to a thread.

Threads can certainly be implemented via continuations, so far as the formal
denotational semantics go.  But those formal semantics don't cover the
pragmatics of parallel execution, so in some practical contexts it's a
worthless observation.

It's of real value in Python, though, because Python's flavor of threads are
currently constrained, by the global lock, to act much more like coroutines
than "real threads" (the co-transfers are implicit instead of explicit, but
other than that they *are* just coroutines).  A great deal of the potential
practical value of Christian's Stackless approach lies exactly here.  Sam
Rushing has written eloquently about this, so visit his site and read his
papers on Medusa & friends.  Short course:  whenever you find yourself
building a hairy state machine to implement a protocol, suspect that there's
an *elegant* approach straining to break free of that cruft.

> 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?

No <wink>, but it goes part of the way in a helpful direction.  What you
described there is no more than what C's setjmp/longjmp accomplishes, and
that isn't enough.  *If* setjmp captured not only the current stack frame,
but *all* stack frames on the entire call stack-- and longjmp resumed
execution via a copy of the whole banana --then you'd be within spitting
distance of a real continuation implementation (albeit not a reasonably
*practical* one).

And that's probably the clearest "operational model" for C programmers.  In
theory, it's much simpler, and *so* much simpler that it's very hard to
explain!  "Continuations in theory" are more basic even than ordinary
subroutine calls.  In fact, they were discovered during attempts to
rigorously define the semantics of "goto" stmts, and in an odd but real
sense continuations are "more basic" than gotos.  In the theoretical
framework, it's pretty much a trivial (in retrospect) fiddling of functions
modeling "program state".  If you take continuations as primitive,
everything else follows easily; the difficulty here is that "everyone
already knows" how subroutine calls work, so try to build continuations on
*top* of that assumed model.  It's backwards, and the need to invert your
brain in order to "get it" is much of what Christian means when he said he
had to "redefine truth".

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

You'll have to borrow Guido's time machine, then -- I stopped writing
compilers in '94, and am still writing c.l.py msgs based on the little I
haven't yet forgotten.

luckily-nothing-new-has-been-discovered-since-'39<wink>-ly y'rs  - tim