[pypy-dev] Stacklets

[Armin Rigo]

Hi Anto,

On Fri, Aug 12, 2011 at 2:22 PM, Antonio Cuni <anto.cuni at gmail.com> wrote:
> Are the caller/callee genlets symmetrical?

Yes; gen.next() is exactly like gen.send(None), just like with
generators.  Well it's maybe just rambling and the interface will
change again next hour, but the idea is as follows.

If you try to build "local" properties that define how the stack of
frames is supposed to look like, you end up with (assuming only one
thread):

- there is one bottommost frame, and one topmost frame;

- every frame apart the bottommost one has one predecessor (f_back),
and every frame apart the topmost one has one successor.

Looks completely obvious, but actually it's not.  With the properties
described above, you can't forbid a situation where you have one
normal-looking stack plus N detached "cycles" of frames, where
following f_back or the other way around ends up in a circle.  (Here I
get my math logic hat: actually you can't give so-called "first-order
properties" that would prevent this case; you can only prevent it by
adding properties that talk about sets of frames, as opposed to single
frames.)

So, from this strange observation comes "gen.send()".  What it does is
change the frames in such a way that the two properties described
above are preserved.  More precisely, "gen.send()" takes the frame f
that "gen" references (which is always the bottommost frame in the
generator), and exchanges f.f_back with the topmost frame.  After
doing that, f.f_back points to what used to be the top frame, and the
new top frame is the old f.f_back.  It's a "local" transformation that
respects the two properties above.  That's how calling "gen.send(i)"
in the generator causes the generator to be suspended: we jump to
f.f_back.  Then the generator frame has a cyclic f_back chain, i.e.
f.f_back points to the topmost frame of the generator itself.  Then
when later we call again "gen.send()", the same exchange is done
again, and we jump to f.f_back, which is this time the topmost frame
of the generator.

If you compare that with Python's normal generators, the only
difference (apart from supporting multiple-frames generators) is that
in a suspended generator frame, the f_back is not set to None, but to
a cycle.

I agree that this is arguably completely obscure; well it was nice
from the logician me :-)

At least it has good properties, e.g. it generalizes without problem
to multiple threads --- just say that when there are N threads
running, there are N frames without an f_back and N frames which are
not the f_back of another.  It clearly points out (in theory) the fact
that the detached circles of frames don't belong to any particular
thread.


A bientôt,

Armin.