[pypy-dev] Stacklets

[Armin Rigo]

Hi all,

Some progress report from my side: I am working on "stacklets", which
is, as the name implies, similar to Stackless.  It is a rewrite of
tealets, which was itself a greenlet-like replacement for Stackless
Python.  (Yes, "tealet" because of "greenlet": green tea... last time
I can do the joke, though, as tealets go away.)

Basically a "stacklet" is just a one-shot continuation.  The name
"stacklet" is going to be internal; at app-level it's just called a
continuation.  It's the most basic primitive I could eventually arrive
at, which is not surprising at all, given that it *is* well known to
be the most basic primitive in functional programming.  See for
example http://en.wikipedia.org/wiki/Call-with-current-continuation.
(Of course it is possible to emulate it using other primitives, e.g.
http://sigusr2.net/2011/Aug/09/call-cc-for-python.html, but that's
abstraction inversion, really.)

In the stacklet branch you get a new built-in module called
"_continuation" which has only one function: "new", also exposed under
the name "callcc", for the reference to various functional programming
languages.  Doing "_continuation.new(func, args...)" calls "func(c,
args...)" with 'c' being a new Continuation object.  Calling
"c.switch()" will switch back to the point where 'c' was created, and
this point will return another continuation 'c2' that can be used to
come back again.  After a number of switches the function func() can
return; it should return yet another Continuation, the one to jump to
next.

- Continuations are objects with a "switch()" method instead of
directly callables, because that seemed more Pythonic

- One shot: once you resume a continuation, the object cannot be
switched to any more

- Garbage collectable: if a pending continuation dies, then every
resource reachable only by resuming it dies too

- Support for exceptions: if func() terminates by raising an
exception, the exception is propagated in the parent (see below)

- Implemented like greenlets by moving around part of the C stack,
which is easily compatible with the JIT

- See http://en.wikipedia.org/wiki/Call-with-current-continuation for
a list of what can easily be built on top of them.

Once I'm done refactoring the GC to support them (in particular with
shadowstack, which requires a bit of care), I will write a greenlet.py
module at app-level implementing full greenlets (which should be less
than 100 lines of code).  It should be useful as a demo of how
higher-level abstractions can be implemented on top of continuations.
Ah, I should also write a CPython wrapper around the core, which is
already written in C, to expose the same continuations for CPython.


One (longish, sorry) word about propagating exceptions: this is not
usually a concern of functional programming languages, so I had to
come up with a way to define where an exception goes.  It goes to the
'parent', which is defined in a greenlet-like way: the parent of a
'func' is the piece of C stack that originally started 'func'.  I
think that this way is the most correct one.  Let me explain.  One
goal of stacklets is to give a "composable" concept, where
"composable" is defined as: if two pieces of code independently use
continuations, and if both pieces work fine when run in isolation,
then they should work fine when run together too.  Stackless Python's
tasklets are composable: you don't have actually references to
tasklets, but only to channel objects, which does the trick (I can
give more details if anyone is interested).  Greenlets on the other
hand are not, and neither are coroutines.  Basic continuations
(without exceptions) are composable again.

Internally, even with pypy+stacklets, continuations form a tree
similar to greenlets, but this tree is not exposed to app-level,
because doing so would break composability.  For example, you could
ask the question "what is my 'parent' piece of stack" and jump there;
to see how this can be wrong, consider the following call chain:

    e() -> _continuation.new() -> f() -> g() -> h()

where g() is in some other module but calls back your own h().  In
this case the 'parent' piece of stack is not well-defined: h() would
expect that it is e(), but maybe g() internally did another
_continuation.new() too.  However, in case of exceptions, then it is
*still* the correct thing to do to propagate the exception into the
parent.  If h() raises, it is propagated back to g(), back to f(), and
back to e(), even if g() internally did another _continuation.new().
Every level is free to capture the exception or let it propagate if
it's of an unknown class, just like normally.  So h() might raise an
exception and expect e() to catch it, which will work just like it
does in the normal case: it will work as long as g(), which is in
another module, doesn't explicitly catch exceptions of the same class
as well.  I suppose this is already well-known, but I couldn't find an
obvious reference.  (For example, looking at Ruby doesn't help much
because its callcc seems slightly different.)


A bientôt,

Armin.