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.
Re-hi, On Thu, Aug 11, 2011 at 10:46 AM, Armin Rigo <arigo@tunes.org> wrote:
I suppose this is already well-known, but I couldn't find an obvious reference.
Ah, I think it's what you get if you assume that your language has callcc but no exceptions, and explicitly implement exceptions on top of callcc. At every call you would pass an extra argument, which is the continuation to switch to in case of an exception. It usually just comes from the parent, but is changed in situations where we'd do a "try:". I need to check that (theoretically) doing this would give the exact same behavior as what I'm writing right now to support (real) exceptions with continuations. A bientôt, Armin.
Re-hi, On Thu, Aug 11, 2011 at 10:59 AM, Armin Rigo <arigo@tunes.org> wrote:
Ah, I think it's what you get if you assume that your language has callcc but no exceptions, and explicitly implement exceptions on top of callcc.
Ok, after a fruitful discussion on IRC (thanks Da_Blitz), here's yet another slightly different concept, almost as primitive as the previous one, but capable of doing the obvious right thing with exceptions. It also has all the good properties of Python generators, so let's call it "genlets" for now. (For example, you can raise in a Python generator, or resume a suspended generator in a different thread, and the right thing occurs; this also occurs with genlets.) Moreover, we can give it an interface very similar to generators. A genlet object has a primitive method send(x), a wrapper next() that just calls send(None), and is an iterator. Example: @genlet def f(gen, a, b): for i in range(a, b): gen.send(i) for x in f(10, 20): print x Of course this example is designed to show the similarity with generators. The 'gen' received by the generator as a first argument is the same object as the one iterated over in the 'for' loop below; this means more symmetrical usages are possible, too, using another method gen1.switch(gen2, x) to do a "symmetrical switch" from gen1 to gen2, as opposed to send() which does a going-into or getting-out-of operation. This looks like a "Pythonic" enough interface, just because it is very similar to the existing one of generators. It is also rather primitive, although good enough to directly use like the example above. I can give a more precise definition of what send() and switch() do, but I think I'll leave that for the next e-mail :-) Does the API presented here makes sense? A bientôt, Armin
Hi Armin, On 11/08/11 18:46, Armin Rigo wrote:
Moreover, we can give it an interface very similar to generators. A genlet object has a primitive method send(x), a wrapper next() that just calls send(None), and is an iterator. Example:
@genlet def f(gen, a, b): for i in range(a, b): gen.send(i)
for x in f(10, 20): print x
I'm not sure to fully understand how it would work. Let's rewrite it this way: def f_inner(gen, a, b): ... f = genlen(f_inner) ... When I call f(10, 20), it returns a genlet object, which is an iterator with a next() method. When the for loop calls gen.next(), the execution of f_inner is resumed until it calls gen.send(i), and then "i" is used as a return value for next(). Is it correct so far? What I don't get is how all these calls interact with the C stack. I suppose that when I call "gen.send(i)" the C stack for f_inner is saved inside and moved away (and "gen" has a reference to it), and then it resumed later when I call gen.next(). But, what happens to the C stack of the code which executes "for x in f(10, 20)"? Is it saved as soon as I switch to the genlet? Are the caller/callee genlets symmetrical? Is there a concept of "main genlet" or something like that? thanks, Anto
Hi Anto, On Fri, Aug 12, 2011 at 2:22 PM, Antonio Cuni <anto.cuni@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.
Hi, The "stacklet" branch has been merged now. The "_continuation" module is available on all PyPys with or without the JIT on x86 and x86-64 since a few days, and it will of course be part of release 1.6.1. There is an almost-complete wrapper "greenlet.py". For documentation and current limitations see here: http://doc.pypy.org/en/latest/stackless.html . A bientôt, Armin.
2011/9/1 Armin Rigo <arigo@tunes.org>:
Hi,
The "stacklet" branch has been merged now. The "_continuation" module is available on all PyPys with or without the JIT on x86 and x86-64 since a few days, and it will of course be part of release 1.6.1. There is an almost-complete wrapper "greenlet.py". For documentation and current limitations see here:
http://doc.pypy.org/en/latest/stackless.html .
A bientôt,
Armin. _______________________________________________ pypy-dev mailing list pypy-dev@python.org http://mail.python.org/mailman/listinfo/pypy-dev
Hello Armin, I'm interested in porting _stackless to stacklets (and also probably making it inter-thread). Where can I find reference API documentation for channels and tasklets because I think it's probably would be simpler to rewrite some parts of code completely. -- Best regards, Alexander Sedov
Hi, 2011/9/23 Александр Седов <elec.lomy.ru@gmail.com>:
I'm interested in porting _stackless to stacklets (and also probably making it inter-thread).
Thanks! Work in this direction is already well advanced. More precisely, the directory pypy/module/_stackless is obsolete and gone, and the pure Python module lib_pypy/stackless.py has been ported to use _continuation. (I wonder somehow why we had all this code in pypy/module/_stackless that seems not needed any more.) But it is not multi-thread-safe so far, which is probably an easy fix, using a thread-local instead of all these global variables initialized in _init() in stackless.py. Note also that there is a branch "continulet-pickle" that could do with help from someone with more motivation than me to finish this. So far you can pickle continulets, greenlets, and coroutines, but not tasklets. It looks messy because of early-optimization issues from stackless.py --- e.g. it would be much more natural for it to switch to the main tasklet every time it needs to do the scheduling and choose the next tasklet to switch to, instead of being clever and switching directly to the target tasklet; this "unwanted cleverness" prevents pickling from working at all, because it sees too much unrelated stuff in a suspended tasklet. All in all what I would be most happy with, at this point, is if someone would step up and finish porting and maintaining stackless.py. Ideally it would be someone that needs this code for his own projects, too.
Where can I find reference API documentation for channels and tasklets
At the Stackless Python original web site. A bientôt, Armin.
Hi Armin and Folks: ________________________________ From: Armin Rigo <arigo@tunes.org> To: Александр Седов <elec.lomy.ru@gmail.com> Cc: pypy-dev@python.org Sent: Friday, September 23, 2011 4:38 PM Subject: Re: [pypy-dev] Stacklets
Thanks! Work in this direction is already well advanced. More precisely, the directory pypy/module/_stackless is obsolete and gone, and the pure Python module lib_pypy/stackless.py has been ported to use _continuation. (I wonder somehow why we had all this code in pypy/module/_stackless that seems not needed any more.)
I downloaded the latest build looked at stackless.py and wrote a simple test. When I have time, I will try incorporate and test my new (and very unofficial) stackless features. I also should have enough code to run weird examples that ought to stress the system. That said, I'm really impressed that continulets was ported so fast. Kudos to Rodrigo! A suggestion. Perhaps it would be good to keep the test for whether CPython is the interpreter and greenlets ought to be used? In this fashion, someone that does want to use pypy-c can still play with stackless. And one authoritative copy of stackless.py can be kept (as opposed to hacking a version for greenlets).
But it is not multi-thread-safe so far, which is probably an easy fix, using a thread-local instead of all these global variables initialized in _init() in stackless.py.
In the stackless mailing list, there is a conversation about some gotchas concerning threads and tasklets that one may want to read. Although the conversation revolves around C Stackless Python based internals, the 50000ft view is about threads dying with tasklets binded to them.
So far you can pickle continulets, greenlets, and coroutines, but not tasklets. It looks messy because of early-optimization issues from stackless.py .
All I know about pickling is that one cannot pickle a tasklet with cstate. Or a blocked tasklet. I don't know how that translates into the pypy world.
--- e.g. it would be much more natural for it to switch to the main tasklet every time it needs to do the scheduling and choose the next tasklet to switch to, instead of being clever and switching directly to the target tasklet; this "unwanted cleverness" prevents pickling from working at all, because it sees too much unrelated stuff in a suspended tasklet
This makes the scheduler sound like a generator trampoline. Also adds an additional context switch, if I understand things correctly.
All in all what I would be most happy with, at this point, is if someone would step up and finish porting and maintaining stackless.py. Ideally it would be someone that needs this code for his own projects, too.
Seems that Rodrigo did a pretty good job. What is left to be done? Cheers, Andrew
Hi, 2011/9/24 Andrew Francis <andrewfr_ice@yahoo.com>:
A suggestion. Perhaps it would be good to keep the test for whether CPython is the interpreter and greenlets ought to be used?
Feel free to propose concrete improvements. As I said already, I implemented the code so far but I don't really have deep interest myself in this feature. If someone wants seriously to start working on it, I can give a few hints. Otherwise, I'm sorry but I'm not going to take an active part in design discussions about how stackless features could be improved. A bientôt, Armin.
Hi Armin: ________________________________ From: Armin Rigo <arigo@tunes.org> To: Andrew Francis <andrewfr_ice@yahoo.com> Cc: Александр Седов <elec.lomy.ru@gmail.com>; "pypy-dev@python.org" <pypy-dev@python.org> Sent: Monday, September 26, 2011 9:05 AM Subject: Re: [pypy-dev] Stacklets
Feel free to propose concrete improvements.
Welll the easiest thing to do is to see if import _continuation fails. And if it does fail, try to import greenlets. Also keep the old greenlet code. This is very much the way the previous stackless.py worked.
As I said already, I implemented the code so far but I don't really have deep interest myself in this feature. If someone wants seriously to start working on it, I can give a few hints.
I would be happy to work with other folks that are interested in the stackless.py module. I have a patchy knowledge of PyPy but a decent knowledge of stackless.py and stackless. Let me study continuations and the existing stackless.py module. In this fashion, I can make every hint I ask count.
Otherwise, I'm sorry but I'm not going to take an active part in design discussions about how stackless features could be improved.
As discussed on IRC, I think an approach that would work is fork stackless.py in two. One branch would be conventional. That that, it would track C basedStackless but incorporate stuff like continuelets and bug fixes and more conservative features. The other branch would be experimental. Wilder stuff would be done there. Cheers, Andrew
On Tue, Sep 27, 2011 at 1:21 AM, Andrew Francis <andrewfr_ice@yahoo.com> wrote:
Welll the easiest thing to do is to see if import _continuation fails. And if it does fail, try to import greenlets. Also keep the old greenlet code. This is very much the way the previous stackless.py worked.
Wouldn't that complicate the code unnecessarily? Perhaps a better way would be to put the burden on the greenlet users and if they wish to share the implementation, they should write an emulation layer for continuations.
As discussed on IRC, I think an approach that would work is fork stackless.py in two. One branch would be conventional. That that, it would track C basedStackless but incorporate stuff like continuelets and bug fixes and more conservative features.
The other branch would be experimental. Wilder stuff would be done there.
Sounds like a good idea to me. As long as any new or altered features do not make it into what is labelled as an implementation of the Stackless API without also being accepted into Stackless itself. Cheers, Richard.
Hello Richard: ________________________________ From: Richard Tew <richard.m.tew@gmail.com> To: Andrew Francis <andrewfr_ice@yahoo.com> Cc: Armin Rigo <arigo@tunes.org>; "pypy-dev@python.org" <pypy-dev@python.org> Sent: Monday, September 26, 2011 7:50 PM Subject: Re: [pypy-dev] Stacklets On Tue, Sep 27, 2011 at 1:21 AM, Andrew Francis <andrewfr_ice@yahoo.com> wrote: AF> Welll the easiest thing to do is to see if import _continuation fails. And AF> if it does fail, try to import greenlets. Also keep the old greenlet code. This is very much the way AF>the previous stackless.py worked.
Wouldn't that complicate the code unnecessarily?
It complicates the code a bit more. However Stackless Python's big problem is that people do not want to install another Python interpreter. Stackless.py with greenlets gives folks one less excuse not to test drive Stackless.
Perhaps a better way would be to put the burden on the greenlet users and if they wish to share the implementation, they should write an emulation layer for continuations.
How can this be better? My own experiences: I greatly benefited from not having to worry about greenlets and being allowed to focus solely on select(). If users have to write their own emulation layer, I see major two things happening: 1) folks walk away. 2) One gets a proliferation of emulation layers - wasted manpower. As it stands the PyPy developers made the right choice. As an example, look at the number of spinoffs from Stackless and stackless.py due to a lack of networking. AF> The other branch would be experimental. Wilder stuff would be done there.
Sounds like a good idea to me. As long as any new or altered features do not make it into what is labelled as an implementation of the Stackless API without also being accepted into Stackless itself.
Richard, in the long run, people will use whatever solves their problems and creates opportunities. I don't know about you but I'm interested in using PyPy and stackless.py to prototype new concurrency constructs that I want to use.... and in the process, throwing the prototypes out there to see what sticks. Cheers, Andrew
On 09/27/2011 05:03 PM, Andrew Francis wrote:
Sounds like a good idea to me. As long as any new or altered features do not make it into what is labelled as an implementation of the Stackless API without also being accepted into Stackless itself.
Richard, in the long run, people will use whatever solves their problems and creates opportunities. I don't know about you but I'm interested in using PyPy and stackless.py to prototype new concurrency constructs that I want to use.... and in the process, throwing the prototypes out there to see what sticks.
Throwing a prototype out is not the same as giving the prototype a semi-official blessing by packaging it with PyPy in the stackless module. I agree with Richard. Carl Friedrich
Hi Carl: ________________________________ From: Carl Friedrich Bolz <cfbolz@gmx.de> To: pypy-dev@python.org Sent: Tuesday, September 27, 2011 11:15 AM Subject: Re: [pypy-dev] Stacklets
Throwing a prototype out is not the same as giving the prototype a semi-official blessing by packaging it >with PyPy in the stackless module. I agree with Richard.
The only blessing I read out a potential packaging is that the powers-that-be are saying: "it is cool to experiment." However the solution to that is simple: don't package experimental with PyPy but make folks aware it exists. The reason I suggested an experimental branch is two fold. 1) Keeping unendorsed features out of a version of stackless.py that ought to track Stackless Python. 2) Have a central place to experiment with new features and get feedback. At the risk of this sounding like a rant or being off-topic, it seems to me the big picture that is getting lost is that stackless.py and PyPy makes it easier for individuals to prototype new ideas for Stackless Pythons and probably Python in general. Take join patterns. To date, I have read about join patterns being implemented in Java, Erlang, Scala, ML, Polyphonic C#, and Lua. What gives? Cheers, Andrew
On Wed, Sep 28, 2011 at 2:16 AM, Andrew Francis <andrewfr_ice@yahoo.com> wrote:
At the risk of this sounding like a rant or being off-topic, it seems to me the big picture that is getting lost is that stackless.py and PyPy makes it easier for individuals to prototype new ideas for Stackless Pythons and probably Python in general. Take join patterns. To date, I have read about join patterns being implemented in Java, Erlang, Scala, ML, Polyphonic C#, and Lua. What gives?
Can't you do that in another file that doesn't represent itself as an implementation of Stackless with no loss to your freedoms? This way, anyone who would use stackless.py would get the stable set of features and API that Stackless has had for over five years now and likely the ability to switch between the two implementations. Or am I misunderstanding? Cheers, Richard.
Hello Richard: ________________________________ From: Richard Tew <richard.m.tew@gmail.com> To: Andrew Francis <andrewfr_ice@yahoo.com> Cc: Carl Friedrich Bolz <cfbolz@gmx.de>; "pypy-dev@python.org" <pypy-dev@python.org> Sent: Tuesday, September 27, 2011 7:57 PM Subject: Re: [pypy-dev] Stacklets
Can't you do that in another file that doesn't represent itself as an implementation of Stackless with no loss to your freedoms?
Yes Richard, I can give a file another name. If I called the experimental module something-that-I-read-in-a-paper-and-decided-to-implement-in-StacklessPy-because-I-do-not-like-hacking-in-C.py, would that satisfy you? Regardless of name, this other file sitting in an experimental branch claiming to be a representation of stackless.py would implement the entire Stackless API and about 60% of the current stackless.py's code base. More importantly, quirks and bugs in the overlapping 60% of the code base, I would be inclined to fix in the legitimate stackless.py as well. "What's in a name? that which we call a rose by any other name would smell as sweet"
This way, anyone who would use stackless.py would get the stable set of features and API that Stackless has had for over five years now and likely the ability to switch between the two implementations.
And what is stopping folks from using a stackless.py that moves lockstep with Stackless Python, while there is a stackless_v3.py lay in an experimental branch? Isn't this sort of like Python 2.x existing while Python 3.x was being worked on and put as alphas?
Or am I misunderstanding?
Yes Richard you are misunderstanding. What I am working on (or have in mind) is not Concurrence, or a gEvent like package but potential new Stackless Python features. And you know this. To me the real issue is NIH invented here. One of the things that will complicate Stackless Python's world is that advances courtesy of PyPy make experimenting with Stackless Python and bypassing C based Stackless Python increasingly the most attractive evolutionary path. Rather than quibbling, figure out how to take best advantage of this. Cheers, Andrew
participants (6)
-
Andrew Francis -
Antonio Cuni -
Armin Rigo -
Carl Friedrich Bolz -
Richard Tew -
Александр Седов