[Python-Dev] 'stackless' python?

[rushing at nightmare.com]

Guido van Rossum writes:
 > Perhaps it would help to explain what a continuation actually does
 > with the run-time environment, instead of giving examples of how to
 > use them and what the result it?

This helped me a lot, and is the angle used in "Essentials of
Programming Languages":

Usually when folks refer to a 'stack', they're refering to an
*implementation* of the stack data type: really an optimization that
assumes an upper bound on stack size, and that things will only be
pushed and popped in order.

If you were to implement a language's variable and execution stacks
with actual data structures (linked lists), then it's easy to see
what's needed: the head of the list represents the current state.  As
functions exit, they pop things off the list.

The reason I brought this up (during a lull!) was that Python is
already paying all of the cost of heap-allocated frames, and it didn't
seem to me too much of a leap from there.

 > 1. All program state is somehow contained in a single execution stack.
Yup.

 > 2. A continuation does something equivalent to making a copy of the
 > entire execution stack.
Yup.
 > I.e. are there mutable *objects* in Scheme?
 > (I know there are mutable and immutable *name bindings* -- I think.)

Yes, Scheme is pro-functional... but it has arrays, i/o, and set-cdr!,
all the things that make it 'impure'.

I think shallow copies are what's expected.  In the examples I have,
the continuation is kept in a 'register', and call/cc merely packages
it up with a little function wrapper.  You are allowed to stomp all
over lexical variables with "set!".

 > 3. Calling a continuation probably makes the saved copy of the
 > execution stack the current execution state; I presume there's also a
 > way to pass an extra argument.
Yup.
 > 4. Coroutines (which I *do* understand) are probably done by swapping
 > between two (or more) continuations.
Yup.  Here's an example in Scheme:

http://www.nightmare.com/stuff/samefringe.scm

Somewhere I have an example of coroutines being used for parsing, very
elegant.  Something like one coroutine does lexing, and passes tokens
one-by-one to the next level, which passes parsed expressions to a
compiler, or whatever.  Kinda like pipes.

 > 5. Other control constructs can be done by various manipulations of
 > continuations.  I presume that in many situations the saved
 > continuation becomes the main control locus permanently, and the
 > (previously) current stack is simply garbage-collected.  Of course
 > the lazy copy makes this efficient.

Yes... I think backtracking would be an example of this.  You're doing
a search on a large space (say a chess game).  After a certain point
you want to try a previous fork, to see if it's promising, but you
don't want to throw away your current work.  Save it, then unwind back
to the previous fork, try that option out... if it turns out to be
better then toss the original.

 > If this all is close enough to the truth, I think that
 > continuations involving C stack frames are definitely out -- as Tim
 > Peters mentioned, you don't know what the stuff on the C stack of
 > extensions refers to.  (My guess would be that Scheme
 > implementations assume that any pointers on the C stack point to
 > Scheme objects, so that C stack frames can be copied and
 > conservative GC can be used -- this will never happen in Python.)

I think you're probably right here - usually there are heavy
restrictions on what kind of data can pass through the C interface.
But I know of at least one Scheme (mzscheme/PLT) that uses
conservative gc and has c/c++ interfaces. [... dig dig ...]