Stackless Python

Stackless Python is a reimplementation of the PythonLanguage that doesn't use the native (or so-called "C") runtime stack to represent the virtual machine stack.

This change enabled a number of interesting features, including a port to the stack-limited Palm platform (PalmPython) and the implementation of continuations and coroutines (see ContinuationExplanation).

After a period of inactivity, Stackless was reinvigorated by ChristianTismer? and is, as of spring 2004, under active development. For more information, see http://www.stackless.com/, especially the mailing list.

This web site gives much more info: http://www.onlamp.com/pub/a/python/2000/10/04/stackless-intro.html.

As of December 2004, it's back to inactive. Looks like most of Tismer's interest is now in PyPy, a project that looks about as vaprous as PerlSix.

And it does not have continuations anymore.

Could someone clarify whether StacklessPython has continuations or not? And if it doesn't, what is its main selling point? Also, what's so bad about multiple stacks anyway? My C-based FlowBasedProgramming implementation (called THREADS) has no trouble switching stacks... It has been suggested that it's not stackless at all, but just has multiple stacks - otherwise how does it handle "local" variables? Comments?

I am attaching a conversation with WolfgangKeller? on StacklessPython ("Stackless" for short) below.

I am beginning to understand why "Stackless": the problem seems to be that Python is an interpreter, and the base version mixed interpreter state and program data on the same stack. This seems to relate to an idea I had, that a neat application architecture, using FlowBasedProgramming (FBP) concepts, would be to have each FBP process running its own interpreter if it requires one, so the interpreter doesn't have to handle task switching. This should give a much leaner interpreter. An added advantage is that you could then mix interpreted and compiled processes together in a single application. --PaulMorrison

StacklessPython is nifty because it adds continuations. What the heck is one you ask? Here's what I think they are:

Multi-tasking systems have to have the ability to save the state of a task, and then restore that state with all of its accompanying bits so that the program can happily continue on its way.

A continuation is just that, it's a saved state. (Also see ContinuationExplanation.) What makes this cool is that you can have python code save a copy of its state this way and then access any of the aforementioned accompanying bits to change them or just read them.

One minor example of continuations: You can write your own 'loops' where you only change one variable and then run that saved state again

If you extend the idea of continuations just slightly, you get coroutines....

actually, if you restrict the idea of continuations, you get coroutines, (resumable) exceptions, flow control, gotos..

Coroutines are continuations that call each other, rather than themselves. This means you can have the equivalent of 'micro-threads' such that when each coroutine hits a point where it has to wait, it calls another coroutine to do something and then at some point the first coroutine will be called again. (Also see ContinuationsAndCoroutines.)

Okay, how is this useful? What good is the whole idea?

One of my friends wrote a prototype of a persistent Python CGI interpreter where getting input from the webserver is actually a function call.

this idea has been predated from AviBryant with Borges (written in Ruby) and SeasideFramework (SmallTalk) and various Scheme and LISP clones exist (UncommonWeb? is the bigger project)

Someone else has suggested that you could have a quick distributed python by saving these states and passing them across the network to another interpreter. (though there would need to be a bit more infrastructure for this to work). Someone else has mentioned a successful implementation of this idea would be perfect for independent agents.

Yes, both SISC and KaliScheme do that.

A pretty average computer should be able to run at least hundreds of these continuations without severe load (from what has been said on the newsgroup, I haven't tried that many). Therefore, you could have one coroutine for each character in a role-playing game, or for each unit in a strategy game, or for each Sim in your economic simulation.

EveOnline uses StacklessPython to do just that.

Random bits:

From what I've heard and read, Lisp has had coroutines for years.

The SchemeLanguage has had continuations since 1975. They aren't part of CommonLisp, although LispMachines had stack groups.

[Since version 1.0] StacklessPython is back and better than ever. In a CS geek sort of way. If you pop over to http://www.stackless.com you'll see that ChristianTismer? is now working on implementing CommunicatingSequentialProcesses in Python. A lot of the stuff with continuations in the old implementation seemed clever but pointless whereas the new approach (implementing CSP via LimboLanguage/AlefLanguage style tasklets and channels) seems like something with realistic uses besides impressive benchmarks. --AdewaleOshineye

Is the stackless implementation of continuations better than, for example, a threaded implementation? What implementation does regular Python use?

Regular Python doesn't have continuations. Continuations can't be implemented using only threads. Continuations are much more powerful than that; you can implement threads with continuations, but not the other way around. The stackless implementation should be understood in opposition to a stack-based implementation. I would say that there are tradeoffs between the two, but in the context of Python, stackless has a HUGE advantage. The nice thing about a stack is that it's usually very quick to operate, so function calls can be fast; but many high level languages, especially Python, make function calls so slow that you could be using MUCH slower structures and never notice the slowness. The nice thing about the stackless stucture is that it doesn't assume a linear block of memory like the C stack does, and many of the basic operations that you want to do with continuations are very simple and quick.

Continuations can be implemented with threads: see http://www.cs.indiana.edu/~dyb/pubs/LaSC-10-3-pp223-236.pdf

Er, that document talks about "one-shot subcontinuations" (see SingleUseContinuation for what that means), not regular continuations, and by the way, there are various things you can do with continuations that you can't do with SingleUseContinuations. DavidPiepgrass

Is this similar to Mobile Maude?

These comments are from WolfgangKeller?. The questions are from me --PaulMorrison

Stackless is excellent for every kind of application that needs to handle asynchronous threads. Especially for I/O-bound applications, where each thread usually wastes a lot of time waiting for something, you can enormously speed up things by using _lots_ (tens or hundreds of thousands) of threads in parallel and thus "interleaving" the waiting time, so that there's always at least one thread which has everything it needs to process.

Another issue (which you address in http://www.jpaulmorrison.com/fbp/method.htm if I understood it right):

Python is not only an excellent "middleware" language (as it interfaces with practically everything easily, including Java and .net), it's also an excellent prototyping language, with development times which are typically a fraction of those for the same application in Java. And once the Python prototype is finished, all you have to do to turn it into a productive application is to profile it and re-implement those modules which are considered too slow for example with Pyrex, which gives your "prototype" native C(++) speed.

 >> I would assume that [FlowBasedProgramming] ports and the network definition 
 >> would have to be added.  I didn't get much out of  ChristianTismer?'s 
 >> web site..

Unfortunately he's too busy earning his living and trying to keep the Stackless implementation in sync with the "mainstream" Python versions. :-(

 >> What on earth is Pickling?  :-)

A very simple Python persistence/serialisation module.

 >> Also, as I posted on SourceForge and the wiki, what is so great about 
 >> getting rid of stacks - or am I reading too much into "stackless"?  :-)

The name of "Stackless" is somewhat misleading (or at least bad PR ;-) . Getting rid of the C stack in Stackless is just a means for the aim of handling a lot of concurrent tasklets (=microthreads) with reasonable ressource requirements. IMHO Stackless should be renamed into something like "Microthreaded Python" "Parallel Python" or something like that... Or even better, the main Python implementation should be "Stackless"ed.

CategoryObjectFunctionalPatterns CategoryContinuation