Re: FW: FW: [Python-Dev] Simple generator implementation
[Uche Ogbuji]
Quite interesting. I brought up this *exact* point at the Stackless BOF at IPC9. I mentioned that the immediate reason I was interested in Stackless was to supercharge the efficiency of 4XSLT. I think that a stackless 4XSLT could pretty much annihilate the other processors in the field for performance.
Hmm. I'm interested in clarifying the cost/performance boundaries of the various approaches. I don't understand XSLT (I don't even know what it is). Do you grok the difference between full-blown Stackless and Icon-style generators?
To a decent extent, based on reading your posts carefully.
The correspondent I quoted believed the latter were on-target for XSLT work, and given the way Python works today generators are easier to implement than full-blown Stackless. But while I can speak with some confidence about the latter, I don't know whether they're sufficient for what you have in mind.
Based on a discussion with Christian at IPC9, they are. I should have been more clear about that. My main need is to be able to change a bit of context and invoke a different execution path, without going through the full overhead of a function call. XSLT, if written "naturally", tends to involve huge numbers of such tweak-context-and-branch operations.
If this is some flavor of one-at-time tree-traversal algorithm, generators should suffice.
class TreeNode: # with self.value # self.children, a list of TreeNode objects ... def generate_kids(self): # pre-order traversal suspend self.value for kid in self.children: for itskids in kid.generate_kids(): suspend itskids
for k in someTreeNodeObject.generate_kids(): print k
So the control-flow is thoroughly natural, but you can only suspend to your immediate invoker (in recursive traversals, this "walks up the chain" of generators for each result). With explicitly resumable generator objects, multiple trees (or even general graphs -- doesn't much matter) can be traversed in lockstep (or any other interleaving that's desired).
Now decide <wink>.
Suspending only to the invoker should do the trick because it is typically a single XSLT instruction that governs multiple tree-operations with varied context. At IPC9, Guido put up a poll of likely use of stackless features, and it was a pretty clear arithmetic progression from those who wanted to use microthreads, to those who wanted co-routines, to those who wanted just generators. The generator folks were probably 2/3 of the assembly. Looks as if many have decided, and they seem to agree with you. -- Uche Ogbuji Principal Consultant uche.ogbuji@fourthought.com +1 303 583 9900 x 101 Fourthought, Inc. http://Fourthought.com 4735 East Walnut St, Ste. C, Boulder, CO 80301-2537, USA Software-engineering, knowledge-management, XML, CORBA, Linux, Python
def generate_kids(self): # pre-order traversal suspend self.value for kid in self.children: for itskids in kid.generate_kids(): suspend itskids
Can I make a suggestion: If we're going to get this generator stuff, I think it would read better if the suspending statement were yield x rather than suspend x because x is not the thing that we are suspending! Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
Greg Ewing <greg@cosc.canterbury.ac.nz> wrote:
stuff, I think it would read better if the suspending statement were
yield x
rather than
suspend x
I agree; this really improves readability. I'm sure someone knows of precedence for the "suspend" keyword, but the only one I recall seeing before is "yeild" (Sather). -Fred -- Fred L. Drake, Jr. <fdrake at acm.org> PythonLabs at Digital Creations
Greg Ewing <greg@cosc.canterbury.ac.nz> wrote:
stuff, I think it would read better if the suspending statement were
yield x
rather than
suspend x
Fred Drake wrote:
I agree; this really improves readability.
Indeed, shortly after i wrote my generator examples, i wished i'd written "generate x" rather than "suspend x". "yield x" is good too. -- ?!ng Happiness comes more from loving than being loved; and often when our affection seems wounded it is only our vanity bleeding. To love, and to be hurt often, and to love again--this is the brave and happy life. -- J. E. Buchrose
the real fred wrote:
I agree; this really improves readability. I'm sure someone knows of precedence for the "suspend" keyword
Icon (the suspend keyword "leaves the generating function in suspension")
but the only one I recall seeing before is "yeild" (Sather).
I associate "yield" with non-preemptive threading (yield to anyone else, not necessarily my caller). Cheers /F
Fredrik Lundh <fredrik@effbot.org>:
I associate "yield" with non-preemptive threading (yield to anyone else, not necessarily my caller).
Well, this flavour of generators is sort of a special case subset of non-preemptive threading, so the usage is not entirely inconsistent. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
On Thu, Mar 22, 2001 at 01:39:05PM +1200, Greg Ewing wrote:
Fredrik Lundh <fredrik@effbot.org>:
I associate "yield" with non-preemptive threading (yield to anyone else, not necessarily my caller).
Well, this flavour of generators is sort of a special case subset of non-preemptive threading, so the usage is not entirely inconsistent.
I prefer yield, but I'll yield to suspend as long as we get coroutines or suspendable frames so I can finish my Python-embedded MUX with task-switching Python code :-) -- Thomas Wouters <thomas@xs4all.net> Hi! I'm a .signature virus! copy me into your .signature file to help me spread!
I also like "yield", but when talking about Icon-style generators to people who may not be familiar with them, I'll continue to use "suspend" (since that's the word they'll see in the Icon docs, and they can get many more examples from the latter than from me).
On the subject of keyword preferences, I like yield best because I first saw iterators (Icon's generators) in CLU and CLU uses yield. Jeremy
Jeremy Hylton:
On the subject of keyword preferences, I like yield best because I first saw iterators (Icon's generators) in CLU and CLU uses yield.
For me the benefit of "yield" is that it connotes both transfer of value and transfer of control, just like "return", while "suspend" only connotes transfer of control. "This tree yields 20 Kilos of fruit each year" and "When merging, yield to the vehicles to your right". Neil
Uche Ogbuji wrote:
[Uche Ogbuji]
Quite interesting. I brought up this *exact* point at the Stackless BOF at IPC9. I mentioned that the immediate reason I was interested in Stackless was to supercharge the efficiency of 4XSLT. I think that a stackless 4XSLT could pretty much annihilate the other processors in the field for performance.
Hmm. I'm interested in clarifying the cost/performance boundaries of the various approaches. I don't understand XSLT (I don't even know what it is). Do you grok the difference between full-blown Stackless and Icon-style generators?
To a decent extent, based on reading your posts carefully.
The correspondent I quoted believed the latter were on-target for XSLT work, and given the way Python works today generators are easier to implement than full-blown Stackless. But while I can speak with some confidence about the latter, I don't know whether they're sufficient for what you have in mind.
Based on a discussion with Christian at IPC9, they are. I should have been more clear about that. My main need is to be able to change a bit of context and invoke a different execution path, without going through the full overhead of a function call. XSLT, if written "naturally", tends to involve huge numbers of such tweak-context-and-branch operations.
If this is some flavor of one-at-time tree-traversal algorithm, generators should suffice.
class TreeNode: # with self.value # self.children, a list of TreeNode objects ... def generate_kids(self): # pre-order traversal suspend self.value for kid in self.children: for itskids in kid.generate_kids(): suspend itskids
for k in someTreeNodeObject.generate_kids(): print k
So the control-flow is thoroughly natural, but you can only suspend to your immediate invoker (in recursive traversals, this "walks up the chain" of generators for each result). With explicitly resumable generator objects, multiple trees (or even general graphs -- doesn't much matter) can be traversed in lockstep (or any other interleaving that's desired).
Now decide <wink>.
Suspending only to the invoker should do the trick because it is typically a single XSLT instruction that governs multiple tree-operations with varied context.
At IPC9, Guido put up a poll of likely use of stackless features, and it was a pretty clear arithmetic progression from those who wanted to use microthreads, to those who wanted co-routines, to those who wanted just generators. The generator folks were probably 2/3 of the assembly. Looks as if many have decided, and they seem to agree with you.
Here the exact facts of the poll: microthreads: 26 co-routines: 35 generators: 44 I think this reads a little different. ciao - chris -- Christian Tismer :^) <mailto:tismer@tismer.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Kaunstr. 26 : *Starship* http://starship.python.net/ 14163 Berlin : PGP key -> http://wwwkeys.pgp.net/ PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF where do you want to jump today? http://www.stackless.com/
[Tim]
The correspondent I quoted believed the latter ["simple" generators] were on-target for XSLT work ... But ... I don't know whether they're sufficient for what you have in mind.
[Uche Ogbuji]
Based on a discussion with Christian at IPC9, they are. I should have been more clear about that. My main need is to be able to change a bit of context and invoke a different execution path, without going through the full overhead of a function call. XSLT, if written naturally", tends to involve huge numbers of such tweak-context-and- branch operations. ... Suspending only to the invoker should do the trick because it is typically a single XSLT instruction that governs multiple tree- operations with varied context.
Thank you for explaining more! It's helpful.
At IPC9, Guido put up a poll of likely use of stackless features, and it was a pretty clear arithmetic progression from those who wanted to use microthreads, to those who wanted co-routines, to those who wanted just generators. The generator folks were probably 2/3 of the assembly. Looks as if many have decided, and they seem to agree with you.
They can't: I haven't taken a position <0.5 wink>. As I said, I'm trying to get closer to understanding the cost/benefit tradeoffs here. I've been nagging in favor of simple generators for a decade now, and every time I've tried they've gotten hijacked by some grander scheme with much muddier tradeoffs. That's been very frustrating, since I've had good uses for simple generators darned near every day of my Python life, and "the only thing stopping them" has been a morbid fascination with Scheme's mistakes <wink>. That phase appears to be over, and *now* "the only thing stopping them" appears to be a healthy fascination with coroutines and uthreads. That's cool, although this is definitely a "the perfect is the enemy of the good" kind of thing. trying-leave-a-better-world-for-the-children<wink>-ly y'rs - tim
participants (10)
-
Christian Tismer -
Fred L. Drake -
Fredrik Lundh -
Greg Ewing -
Jeremy Hylton -
Ka-Ping Yee -
Neil Hodgson -
Thomas Wouters -
Tim Peters -
Uche Ogbuji