Revised**5 PEP on yield-from

Revision 6 of the PEP. * Changed wording slightly to avoid implying that StopIteration(value) can be caught inside the returning generator. * Added a suggestion that StopIteration be given a 'value' attribute. * Mentioned the idea of a GeneratorReturn exception in the Criticisms section. PEP: XXX Title: Syntax for Delegating to a Subgenerator Version: $Revision$ Last-Modified: $Date$ Author: Gregory Ewing <greg.ewing@canterbury.ac.nz> Status: Draft Type: Standards Track Content-Type: text/x-rst Created: 13-Feb-2009 Python-Version: 2.7 Post-History: Abstract ======== A syntax is proposed for a generator to delegate part of its operations to another generator. This allows a section of code containing 'yield' to be factored out and placed in another generator. Additionally, the subgenerator is allowed to return with a value, and the value is made available to the delegating generator. The new syntax also opens up some opportunities for optimisation when one generator re-yields values produced by another. Proposal ======== The following new expression syntax will be allowed in the body of a generator: :: yield from <expr> where <expr> is an expression evaluating to an iterable, from which an iterator is extracted. The iterator is run to exhaustion, during which time it behaves as though it were communicating directly with the caller of the generator containing the ``yield from`` expression (the "delegating generator"). When the iterator is another generator, the effect is the same as if the body of the subgenerator were inlined at the point of the 'yield from' expression. The subgenerator is allowed to execute a 'return' statement with a value, and that value becomes the value of the 'yield from' expression. In terms of the iterator protocol: * Any values that the iterator yields are passed directly to the caller. * Any values sent to the delegating generator using ``send()`` are sent directly to the iterator. (If the iterator does not have a ``send()`` method, it remains to be decided whether the value sent in is ignored or an exception is raised.) * Calls to the ``throw()`` method of the delegating generator are forwarded to the iterator. (If the iterator does not have a ``throw()`` method, the thrown-in exception is raised in the delegating generator.) * If the delegating generator's ``close()`` method is called, the iterator is finalised before finalising the delegating generator. * The value of the ``yield from`` expression is the first argument to the ``StopIteration`` exception raised by the iterator when it terminates. * ``return expr`` in a generator causes ``StopIteration(expr)`` to be raised. For convenience, the ``StopIteration`` exception will be given a ``value`` attribute that holds its first argument, or None if there are no arguments. Formal Semantics ---------------- The statement :: result = yield from expr is semantically equivalent to :: _i = iter(expr) try: _u = _i.next() while 1: try: _v = yield _u except Exception, _e: if hasattr(_i, 'throw'): _i.throw(_e) else: raise else: if hasattr(_i, 'send'): _u = _i.send(_v) else: _u = _i.next() except StopIteration, _e: _a = _e.args if len(_a) > 0: result = _a[0] else: result = None finally: if hasattr(_i, 'close'): _i.close() Rationale ========= A Python generator is a form of coroutine, but has the limitation that it can only yield to its immediate caller. This means that a piece of code containing a ``yield`` cannot be factored out and put into a separate function in the same way as other code. Performing such a factoring causes the called function to itself become a generator, and it is necessary to explicitly iterate over this second generator and re-yield any values that it produces. If yielding of values is the only concern, this is not very arduous and can be performed with a loop such as :: for v in g: yield v However, if the subgenerator is to interact properly with the caller in the case of calls to ``send()``, ``throw()`` and ``close()``, things become considerably more complicated. As the formal expansion presented above illustrates, the necessary code is very longwinded, and it is tricky to handle all the corner cases correctly. In this situation, the advantages of a specialised syntax should be clear. Generators as Threads --------------------- A motivating use case for generators being able to return values concerns the use of generators to implement lightweight threads. When using generators in that way, it is reasonable to want to spread the computation performed by the lightweight thread over many functions. One would like to be able to call a subgenerator as though it were an ordinary function, passing it parameters and receiving a returned value. Using the proposed syntax, a statement such as :: y = f(x) where f is an ordinary function, can be transformed into a delegation call :: y = yield from g(x) where g is a generator. One can reason about the behaviour of the resulting code by thinking of g as an ordinary function that can be suspended using a ``yield`` statement. When using generators as threads in this way, typically one is not interested in the values being passed in or out of the yields. However, there are use cases for this as well, where the thread is seen as a producer or consumer of items. The ``yield from`` expression allows the logic of the thread to be spread over as many functions as desired, with the production or consumption of items occuring in any subfunction, and the items are automatically routed to or from their ultimate source or destination. Concerning ``throw()`` and ``close()``, it is reasonable to expect that if an exception is thrown into the thread from outside, it should first be raised in the innermost generator where the thread is suspended, and propagate outwards from there; and that if the thread is terminated from outside by calling ``close()``, the chain of active generators should be finalised from the innermost outwards. Syntax ------ The particular syntax proposed has been chosen as suggestive of its meaning, while not introducing any new keywords and clearly standing out as being different from a plain ``yield``. Optimisations ------------- Using a specialised syntax opens up possibilities for optimisation when there is a long chain of generators. Such chains can arise, for instance, when recursively traversing a tree structure. The overhead of passing ``next()`` calls and yielded values down and up the chain can cause what ought to be an O(n) operation to become O(n\*\*2). A possible strategy is to add a slot to generator objects to hold a generator being delegated to. When a ``next()`` or ``send()`` call is made on the generator, this slot is checked first, and if it is nonempty, the generator that it references is resumed instead. If it raises StopIteration, the slot is cleared and the main generator is resumed. This would reduce the delegation overhead to a chain of C function calls involving no Python code execution. A possible enhancement would be to traverse the whole chain of generators in a loop and directly resume the one at the end, although the handling of StopIteration is more complicated then. Use of StopIteration to return values ------------------------------------- There are a variety of ways that the return value from the generator could be passed back. Some alternatives include storing it as an attribute of the generator-iterator object, or returning it as the value of the ``close()`` call to the subgenerator. However, the proposed mechanism is attractive for a couple of reasons: * Using the StopIteration exception makes it easy for other kinds of iterators to participate in the protocol without having to grow extra attributes or a close() method. * It simplifies the implementation, because the point at which the return value from the subgenerator becomes available is the same point at which StopIteration is raised. Delaying until any later time would require storing the return value somewhere. Criticisms ========== Under this proposal, the value of a ``yield from`` expression would be derived in a very different way from that of an ordinary ``yield`` expression. This suggests that some other syntax not containing the word ``yield`` might be more appropriate, but no acceptable alternative has so far been proposed. It has been suggested that some mechanism other than ``return`` in the subgenerator should be used to establish the value returned by the ``yield from`` expression. However, this would interfere with the goal of being able to think of the subgenerator as a suspendable function, since it would not be able to return values in the same way as other functions. The use of an argument to StopIteration to pass the return value has been criticised as an "abuse of exceptions", without any concrete justification of this claim. In any case, this is only one suggested implementation; another mechanism could be used without losing any essential features of the proposal. It has been suggested that a different exception, such as GeneratorReturn, should be used instead of StopIteration to return a value. However, no convincing practical reason for this has been put forward, and the addition of a ``value`` attribute to StopIteration mitigates any difficulties in extracting a return value from a StopIteration exception that may or may not have one. Also, using a different exception would mean that, unlike ordinary functions, 'return' without a value in a generator would not be equivalent to 'return None'. Alternative Proposals ===================== Proposals along similar lines have been made before, some using the syntax ``yield *`` instead of ``yield from``. While ``yield *`` is more concise, it could be argued that it looks too similar to an ordinary ``yield`` and the difference might be overlooked when reading code. To the author's knowledge, previous proposals have focused only on yielding values, and thereby suffered from the criticism that the two-line for-loop they replace is not sufficiently tiresome to write to justify a new syntax. By also dealing with calls to ``send()``, ``throw()`` and ``close()``, this proposal provides considerably more benefit. Copyright ========= This document has been placed in the public domain. .. Local Variables: mode: indented-text indent-tabs-mode: nil sentence-end-double-space: t fill-column: 70 coding: utf-8 End:

Hi Greg A few comments. First, I think the suggested expansion is not quite right:
Shouldn't this be "_u = _i.throw(e)" instead?
Second, I spend a looong time today thinking about how to make this fast.
True, but as long as it is only chains of generators I can sketch a solution that would give amortized constant time for finding the generator to resume. Unfortunately it is easy to construct a situation where what we have is actually a tree of generators, each using "yield from" its parent. Simple example: def foo(): yield 1 yield 2 yield 3 def bar(it): yield from it root = foo() child1 = bar(root) child2 = bar(root) print child1.next() # prints 1, yielded from root print child2.next() # prints 2, yielded from root In this example, both "child1" and "child2" are yielding from "root". So what we are dealing with is a set of dynamic trees under the operations "find_root" (to find the target when calling the generator methods), "link" (when doing yield from) and "delete_root" (each time a generator is exhausted). I strongly suspect that the lower bound for this problem is O(logn/loglogn) per operation, and I can see a number of ways to do it in O(logn) time. I am not sure any of them are fast enough to beat the simple O(n) solution in real code though. (I will see if I can find a version that has a chance). A thought just occurred to me... would it be acceptable to disallow "yield from" with a generator that is not "fresh"? That would make "child2.next()" above illegal and remove the problem with dealing with trees of generators.
I hope you can get that second version to work. All further optimization would probably have to start with something like that anyway. Best regards Jacob

Jacob Holm wrote:
Yes, I think possibly it should... but I need to wait until my brain stops hurting from thinking about all this before I'll know for certain... I'm no longer sure that the implementation I'm working on can be exactly described in terms of any Python expansion, anyway. One problem is that if the generator gets None from a yield, it has no way of knowing whether it came from a next() or a send(None), so it doesn't know which method to call on the subiterator. The best that it could do is if _v is None: _u = _i.next() else: _u = _i.send(_v) but I would have to modify my implementation as it currently stands to make it work like that. This may be the right thing to do, as it would bring things into line with the advertised equivalence of next() and send(None), and you would still get an exception if you tried to send something non-None to an object without a send() method.
I strongly suspect that the lower bound for this problem is O(logn/loglogn) per operation, and I can see a number of ways to do it in O(logn) time.
Before you bust too many neurons on O() calculations, be aware that the constant factors are important here. I'm relying on traversing a delegation chain using C calls taking negligible time compared to doing it in Python, so that it can be treated as a constant-time operation for all practical purposes regardless of the length of the chain. Testing will reveal whether this turns out to be true in real life... -- Greg

Greg Ewing wrote:
This is only a problem with the recursive implementation though, isn't it? treated as a 'next'. To me, the "communicating directly with the caller" bit is less important than the argument that the caller is still talking to a generator that *has* a send but may ignore the values sent.
Too late, but don't worry. I'm doing this for fun :) I think I can actually see a way to do it that should be fast enough, but I'd like to work out the details first. If it works it will be O(1) with low constants as long as you don't build trees, and similar to traversing a delegation chain in the worst case. All this depends on getting it working using delegation chains first though, as most of the StopIteration and Exception handling would be the same. Best regards Jacob

Bruce Frederiksen wrote:
Let's not let the limitations of what can be expressed directly in Python influence the implementation.
No, but I have an instinct that if something *can* be expressed using basic Python, there's a good chance it's conceptually sound. Anyway, for other reasons I've settled on an interpretation that can be expressed in Python, as it happens. I'll be releasing another draft of the PEP with suitable modifications. -- Greg

Replying to myself here... Jacob Holm wrote:
I have now worked out the details, and it is indeed possible to get O(1) for simple cases and amortized O(logN) in general, all with fairly low constants. I have implemented the tree structure as a python module and added a trampoline-based pure-python implementation of "yield-from" to try it out. It seems that this version beats a normal "for v in it: yield v" when the delegation chains get around 90 generators deep. This may sound like much, but keep in mind that this is all in python. I expect a C implementation of this would break even much sooner than that (hoping for <5). If you (or anyone else) is interested I can post the code here. (Or you can suggest a good place to upload it). Regards Jacob

On 28 Feb 2009, at 20:54, Jacob Holm wrote:
I'm sorry if I'm missing something obvious, but there are two things I can't work out: * What you are measuring the time complexity of. * What N stands for. I suspect that N is the 'delegation depth': the number of yield-from that have to be gone through. I imagine that you are measuring the time it takes to get the next element in the generator. These are guesses - can you correct me?
Can you give an example? -- Arnaud

Hi Arnaud Arnaud Delobelle wrote:
* What you are measuring the time complexity of.
The time for a single 'next', 'send', 'throw' or 'close' call to a generator or a single "yield from" expression, excluding the time spent running the user-defined code in it. (Does that make sense?) In other words, the total overhead of finding the actual user code to run and handling the return values/exceptions according to the PEP.
One interesting thing to note is that all non-contrived examples I have seen only build simple chains of iterators, and only do that by adding one at a time in the deepest nested one. This is the best possible case for my algorithm. If you stick to that, the time per operation is O(1). If we decided to only allow that, the algorithm can be simplified significantly.
Sure, here is the simple code I used for timing the 'next' call import itertools, time from yieldfrom import uses_from, from_ # my module... @uses_from def child(it): yield from_(it) def child2(it): for i in it: yield i def longchain(N): it = itertools.count() for i in xrange(N): it = child(it) # replace this with child2 to test the current # "for v in it: yield v" pattern. it.next() # we are timing the 'next' calls (not the setup of # the chain) so skip the setup by calling next once. return it it = longchain(90) times = [] for i in xrange(10): t1 = time.time() for i in xrange(100000): it.next() t2 = time.time() times.append(t2-t1) print min(times) This version takes about the same time whether you use child or child2 to build the chain. However, the version using yield..from takes the same time no matter how long the chain is, while the time for the "for v in it: yield v" version is linear in the length of the chain, and so would lose big-time for longer chains. I hope this answers your questions. Regards Jacob

Jacob Holm wrote:
How are you measuring 'time', though? Usually when discussing time complexities we're talking about the number of some fundamental operation being performed, and assuming that all such operations take the same time. What operations are you counting here?
I don't understand that limitation. If you keep a stack of active generators, you always have constant-time access to the one to be resumed next. There's some overhead for pushing and popping the stack, but it follows exactly the same pattern as the recursive calls you'd be making if you weren't using some kind of yield-from, so it's irrelevant when comparing the two. -- Greg

Greg Ewing wrote: the like. No hashing, no dynamic arrays, no magic, just plain' ol' fundamental operations as they would be in a C program :)
A \ R --- (whatever R is waiting for) / B Yes, A sees it as a stack [A,R,...], and B sees it as a stack [B,R,...], but the part of the stack following R is the same in the two. If R does a "yield from", the new iterator must appear at the top of both "stacks". Efficiently getting to the top of this "shared stack", and doing the equivalent of push, pop, ... is what I am trying to achieve. And I think I have succeeded.
This would be correct if it was somehow forbidden to create the scenario I sketched above. As long as that scenario is possible I can construct an example where treating it as a simple stack will either do the wrong thing, or do the right thing but slower than a standard "for v in it: yield v". Of course, you could argue that these examples are contrived and we don't have to care about them. I just think that we should do better if we can. FWIW, here is the example from above in more detail... def R(): yield 'A' yield 'B' yield from xrange(3) # we could do anything here really... r = R() def A(): yield from r a = A() def B() yield from r b = B() a.next() # returns 'A' b.next() # returns 'B' r.next() # returns 0 a.next() # returns 1 b.next() # returns 2 This is clearly legal based on the PEP, and it generalizes to a way of building an arbitrary tree with suspended generators as nodes. What my algorithm does is break this tree down into what is essentially a set of stacks. Managed such that the common case has just a single stack, and no matter how twisted your program is, the path from any generator to the root is split across at most O(logN) stacks (where N is the size of the tree). I hope this helps to explain what I think I have done... Best regards Jacob

Jacob Holm wrote:
Unless you're doing something extremely unusual, this situation wouldn't arise. The yield-from statement is intended to run the iterator to exhaustion, and normally you'd create a fresh iterator for each yield-from that you want to do. So A and B would really be yielding from different iterators, even if they were both iterating over the same underlying object. If you did try to share iterators between yield-froms like that, you would have to arrange things so that at least all but one of them broke out of the loop early, otherwise something is going to get an exception due to trying to resume an exhausted iterator. But in any case, I think you can still model this as two separate stacks, with R appearing in both stacks: [A, R] and [B, R]. Whichever one of them finishes yielding from R first pops it from its stack, and when the other one tries to resume R it gets an exception. Either that or it breaks out of its yield-from early and discards its version of R.
That depends on what you think the "right thing" is. If you think that somehow A needs to notice that B has finished yielding from R and gracefully stop doing so itself, then that's not something I intended and it's not the way the current prototype implementation would behave. So IMO you're worrying about a problem that doesn't exist. -- Greg

Greg Ewing wrote:
I am not worried about R running out, each of A and B would find out about that next time they tried to get a value. I *am* worried about R doing a yield-from to X (the xrange in this example) which then needs to appear in both stacks to get the expected behavior from the PEP.
The right thing is whatever the PEP specifies :) You are the author, so you get to decide... I am saying that what the PEP currently specifies is not quite so simple to speed up as you and Arnaud seem to think. (Even with a simple stack, handling 'close' and 'StopIteration' correctly is not exactly trivial)
So IMO you're worrying about a problem that doesn't exist.
No, I am worrying about a problem that so far has only appeared in contrived examples designed to expose it. Any real-life examples I have seen of the "yield from" feature would work perfectly well with a simple stack-based approach. However, I have seen several ideas for speeding up long chains of "yield from"s beyond the current C implementation, and most of them fail either by giving wrong results (bad) or by slowing things down in admittedly unusual cases (not so bad, but not good). Anyway... it is 3 in the morning. As I told Arnaud, I will try to find some time this week to write some more of these crazy examples. Regards Jacob

On 3/1/09, Jacob Holm <jh@improva.dk> wrote:
Greg Ewing wrote:
Jacob Holm wrote:
[naming that for which R waits]
But in any case, I think you can still model this as two separate stacks, with R appearing in both stacks: [A, R] and [B, R].
[A, R, X] and [B, R, X]
I would assume that the second one tries to resume, gets the StopIteration from X, retreats to R, gets the StopIteration there as well, and then continues after its yield-from. If that didn't happen, I would wonder whether (theoretical speed) optimization was leading to suboptimal semantics.
I have to wonder whether any optimization will be a mistake. At the moment, I can't think of any way to do it without adding at least an extra pointer and an extra if-test. That isn't much, but ... how often will there be long chains, vs how often are generators used without getting any benefit from this sort of delegation? -jJ

Jim Jewett wrote:
how often will there be long chains,
My suspicion is not very often. The timing tests I did suggest that the biggest benefit will be from simply removing most of the delegation overhead from a single level of delegation, and you don't need any fancy algorithm for that. My experiments with traversing binary trees suggest that the delegation overhead isn't all that great a problem until the tree is about 20 levels deep, or 1e6 nodes. Even then it doesn't exactly kill you, but even so, my naive implementation shows a clear improvement. -- Greg

Jacob Holm wrote:
Yes, and I tried running it on my prototype implementation. It gives exactly the results you suggested, and any further next() calls on a or b raise StopIteration. You're right that there's no need to break out early in the case of generators, since it seems they just continue to raise StopIteration if you call next() on them after they've finished. Other kinds of iterators might not be so forgiving.
What's wrong with it appearing in both stacks, though, as long as it gives the right result?
It's a bit tricky to handle all the cases correctly, but that has nothing to do with speed. I should perhaps point out that neither of my suggested implementations actually use separate stacks like this. The data structure is really more like the shared stack you suggest, except that it's accessed from the "bottoms" rather than the "top". This is only a speed issue if the time taken to find the "top" starting from one of the "bottoms" is a significant component of the total running time. My conjecture is that it won't be, especially if you do it iteratively in a tight C loop. Some timing experiments I did suggest that the current implementation (which finds the "top" using recursion in C rather than iteration) is at least 20 times faster at delegating a next() call than using a for-loop, which is already a useful improvement, and the iterative method can only make it better. So until someone demonstrates that the simple algorithm I'm using is too slow in practice, I don't see much point in trying to find a smarter one. -- Greg

Greg Ewing wrote:
Could it be possible to design it so that the yield path of generators are passed down or forwarded to sub-generators when they are called? If that can be done then no matter how deep they get, it works as if it is always only one generator deep. So... result = yield from sub-generator Might be sugar for ... (very rough example) sub-generator.forward(this_generator_yield_path) # set yield path sub_generator.run() # pass control to sub-generator result = sub_generator.return_value # get return value if set Of course the plumbing in this may takes some creative rewriting of generators so the yield path can be passed around. Being able to get the yield path might also be useful in other ways, such as error reporting. Cheers, Ron

Ron Adam wrote:
Could it be possible to design it so that the yield path of generators are passed down or forwarded to sub-generators when they are called?
It's really the other way around -- you would need some way of passing the yield path *up* to a generator's caller. E.g. if A is yielding from B is yielding from C, then A needs a direct path to C. Possibly some scheme could be devised to do this, but I don't feel like spending any brain cycles on it until the current scheme is shown to be too slow in practice. Premature optimisation and all that. -- Greg

Greg Ewing wrote:
So when A.next() is called it in effect does a C.next() instead. Is that correct? And when C's yield statement is executed, it needs to return the value to A's caller. So the .next() methods need to be passed up, while the yield return path needs to be passed down? OK, I guess I need to look at some byte/source code. ;-)
Right I agree. I have an intuitive feeling that being able to expose and redirect caller and return values may useful in more ways than just generators. ie.. general functions, translators, encoders, decorators, and possibly method resolution. <shrug> then again, there may not be any easy obvious way to do it. Ron

2009/3/6 Ron Adam <rrr@ronadam.com>:
Greg Ewing wrote:
[...]
This is what the toy python implementation that I posted last month does. I think Jacob Holm did something more sophisticated that does this as well (I haven't seen it!).
So the .next() methods need to be passed up, while the yield return path needs to be passed down?
Can you draw a picture? :) -- Arnaud

Arnaud Delobelle wrote:
I do, and here is the most readable version so far. If you look very closely, you will notice a certain similarity to the version you posted. It turned out there was an easy fix for the 'closing' problem i mentioned, and a hack based on gi_frame that allowed me to use a generator function for the wrapper after all, so the _generator_iterator_wrapper below is heavily based on your code. The rest is there to implement the tree structure I mentioned, instead of just a simple stack. The speed of this version on simple long chains is still about 6 times slower than your code. This can be improved to about 1.5 times by inlining most of the function calls and eliminating the RootPath class, but the resulting code is close to unreadable and therefore not well suited to explain the idea. Most of the remaining slowdown compared to "for v in it: yield v" is due to attribute lookups and simple integer computations. In fact, I would be surprised if a C version of this wasn't going to be faster even for just a single "yield from". Anyway, here it is Jacob """Tree structure implementing the operations needed by yield-from. """ class Node(object): """A Node object represents a single node in the tree. """ __slots__ = ('parent', # the parent of this node (if any) 'chain', # the chain this node belongs to (if any) 'child', # the child of this node in the chain (if any) 'size', # The number of descendants of this node # (including the node itself) that are not # descendants of 'child', plus the number of # times any of these nodes have been accessed. ) def __init__(self): self.parent = None # We are not actually using this one, but # it is cheap to maintain. self.chain = None self.child = None self.size = 0 class Chain(object): """A Chain object represents a fragment of the path from some node towards the root. Chains are long-lived, and are used to make shortcuts in the tree enabling operations to take O(logN) rather than O(N) time. (And even enabling O(1) for certain usage patterns). """ __slots__ = ('top', # topmost node in the chain 'size', # The sum of sizes of all nodes in the chain 'parent', # the parent node of top in the tree 'rp_child', # the child of this chain in the current # root path ) def __init__(self, *nodes): """Construct a chain from the given nodes. The nodes must have a size>0 assigned before constructing the chain, and must have their 'chain' pointer set to None. The nodes are linked together using their 'child' pointers, and get their 'chain' pointers set to the new chain. First node in the list will be at the bottom of the chain, last node in the list becomes the value of the 'top' field. The size of the new chain is the sum of the sizes of the nodes. """ top = None size = 0 for node in nodes: assert node.chain is None assert node.child is None assert node.size > 0 node.chain = self node.child = top size += node.size top = node parent = None for node in reversed(nodes): node.parent = parent parent = node self.top = top self.size = size self.parent = None self.rp_child = None class RootPath(object): """A RootPath represents the whole path from the root to some given node. RootPaths need to be 'acquired' before use and 'released' after. Acquiring the path establishes the necessary down-links, ensures the path has length O(logN), and gives an efficient way of detecting and avoiding loops. """ __slots__ = ('base', # The node defining the path 'root', # The root node of the tree ) def __init__(self, base): """Construct the RootPath representing the path from base to its root. """ assert isinstance(base, Node) self.base = base self.root = None def acquire(self, sizedelta=0): """Find the root and take ownership of the tree containing self.base. Create a linked list from the root to base using the Chain.rp_child pointers. (Using self as sentinel in self.base.rp_child). Optionally adds 'sizedelta' to the size of the base node for the path and updates the rest of the sizes accordingly. If the tree was already marked (one of the chains had a non-None rp_child pointer), back out all changes and return None, else return the root node of the tree. """ assert self.root is None node = self.base assert node is not None rp_child = self while True: chain = node.chain assert chain is not None if chain.rp_child is not None: # Some other rootpath already owns this tree. Undo the # changes so far and raise a RuntimeError if rp_child is not self: while True: chain = rp_child rp_child = chain.rp_child chain.rp_child = None if rp_child is self: break node = rp_child.parent node.size -= sizedelta chain.size -= sizedelta return None assert chain.rp_child is None node.size += sizedelta chain.size += sizedelta chain.rp_child = rp_child rp_child = chain node = rp_child.parent if node is None: break self.root = root = rp_child.top assert root.chain is not None assert root.chain.parent is None # Tricky, this rebalancing is needed because cut_root # cannot do a full rebalancing fast enough without maintaining # a lot more information. We may actually have traversed a # (slightly) unbalanced path above. Rebalancing here makes # sure that it is balanced when we return, and the cost of # traversing the unbalanced path can be included in the cost # of rebalancing it. The amortized cost is still O(logn) per # operation as it should be. self._rebalance(self, False) return root def release(self): """Release the tree containing this RootPath. """ assert self.root is not None chain = self.root.chain assert chain is not None while chain is not self: child = chain.rp_child chain.rp_child = None chain = child self.root = None def cut_root(self): """Cut the link between the root and its child on the root path. Release the tree containing the root. If the root was the only node on the path, return None. Else return the new root. """ root = self.root assert root is not None chain = root.chain assert chain.parent is None assert root is chain.top child = chain.rp_child assert child is not None if child is self: # only one chain if root is self.base: # only one node, release tree chain.rp_child = None self.root = None return None else: # multiple chains if root is child.parent: # only one node from this chain on the path. root.size -= child.size chain.size -= child.size child.parent = None chain.rp_child = None self.root = newroot = child.top newroot.parent = None return newroot # Multiple nodes on the chain. Cut the topmost off and put it # into its own chain if necessary. (This is needed when the # node has other children) newroot = root.child assert newroot newroot.parent = None self.root = chain.top = newroot chain.size -= root.size root.child = None root.chain = None Chain(root) self._rebalance(self, True) return newroot def link(self, node): """Make the root of this tree a child of a node from another tree. Return the root of the resulting tree on succes, or None if the tree for the parent node couldn't be acquired. """ root = self.root assert root is not None chain = root.chain assert chain.parent is None assert isinstance(node, Node) rp = RootPath(node) newroot = rp.acquire(chain.size) if newroot is None: return None self.root = newroot node.chain.rp_child = chain root.parent = chain.parent = node self._rebalance(chain.rp_child, False) return newroot def _rebalance(self, stop, quick): # check and rebalance all the chains starting from the root. # If 'quick' is True, stop the first time no rebalancing took # place, else continue until the child is 'stop'. gpchain = None pchain = self.root.chain chain = pchain.rp_child while chain is not stop: parent = chain.parent if 2*(pchain.size-parent.size) <= chain.size: # Unbalanced chains. Move all ancestors to parent from # pchain into this chain. This may look like an # expensive operation, but the balancing criterion is # chosen such that every time a node is moved from one # chain to another, the sum of the sizes of everything # *after* the node in its chain is at least # doubled. This number is only decreased by cut_root # (where it may be reset to zero), so a node can move # between chains at most log_2(N) times before if # becomes the root in a cut_root. The amortized cost # of keeping the tree balanced is thus O(logN). The # purpose of the balancing is of course to keep the # height of the tree down. Any node that is balanced # according to this criterion has # # 2*(pchain.size-self.size) > 2*(pchain.size-self.parent.size) # > self.size # # and so # # pchain.size > 1.5*self.size # # Therefore, the number of chains in any balanced # RootPath is at most log_1.5(N), and so the cost per # operation is O(logN). # Compute size of elements to move and set their 'chain' # pointers. p = pchain.top movedsize = p.size p.chain = chain while p is not parent: p = p.child movedsize += p.size p.chain = chain # update sizes parent.size -= chain.size chain.size = pchain.size pchain.size -= movedsize parent.size += pchain.size # update child, top and parent links pchain.top, parent.child, chain.top \ = parent.child, chain.top, pchain.top chain.parent = pchain.parent pchain.parent = parent # update rp_child links pchain.rp_child = None # pchain is no longer on the path if gpchain is not None: assert gpchain is not None assert gpchain.rp_child is pchain gpchain.rp_child = chain assert (pchain.top is None)==(pchain.size==0) # if pchain.top is None: # # # pchain has become empty. If coding this in C, # # remember to free the memory. elif quick: break else: gpchain = pchain pchain = chain chain = pchain.rp_child ############################################################################### """Yield-from implementation """ import sys # _getframe, used only in an assert import types # GeneratorType import functools # wraps class _iterator_node(Node): # Wrapper for turning an unknown iterator into a node in the tree. __slots__ = ('iterator', # the wrapped iterator ) locals().update((k, Node.__dict__[k]) for k in ('parent', 'chain', 'child', 'size')) def __init__(self, iterator): self.iterator = iterator Node.__init__(self) self.size = 1 Chain(self) class _generator_iterator_wrapper(_iterator_node): # Wrapper for turning a generator using "yield from_(expr)" into a # node in the tree. __slots__ = () locals().update((k, _iterator_node.__dict__[k]) for k in ('parent', 'chain', 'child', 'size', 'iterator')) def __new__(cls, iterator): self = _iterator_node.__new__(cls) _iterator_node.__init__(self, iterator) return self.__iter__() # we don't hold on to a reference to # this generator, because a) we don't # need to, and b) when the last # user-code reference to it goes away, # the generator is automatically closed # and we get a chance to clean up the # rest of the cycles created by this # structure. def __iter__(self): val = exc = None rp = RootPath(self) while True: try: if rp.acquire(1) is None: raise ValueError('generator already executing') while True: try: gen = rp.root.iterator try: if exc is not None: throw = getattr(gen, 'throw', None) try: if throw is None: raise exc ret = throw(exc) finally: del throw exc = None elif val is None: ret = gen.next() else: ret = gen.send(val) except: close = getattr(gen, 'close', None) try: if close is not None: close() raise finally: del close finally: del gen except Exception, e: if rp.cut_root() is None: raise if isinstance(e, StopIteration): val, exc = getattr(e, 'val', None), None else: val, exc = None, e else: if type(ret) is from_: if rp.link(ret.node) is not None: val = None else: exc = ValueError('generator already executing') continue break finally: if rp.root is not None: rp.release() try: val = yield ret except Exception, e: exc = e class from_(object): """This class is used together with the uses_from decorator to simulate the proposed 'yield from' statement using existing python features. Use: @uses_from def mygenerator(): ... result = yield _from(expr) ... raise StopIteration(result) To get the equivalent effect of the proposed: def mygenerator(): ... result = yield from expr ... return result Any use other than directly in a yield expression within a generator function decorated with 'uses_from' is unsupported, and could eat your harddrive for all I care. Unsupported uses include, but are not limited to: subclassing, calling methods, reading or writing attributes, storing in a variable, and passing as argument to a builtin or other function. """ __slots__ = ('node',) def __init__(self, iterable): # get the code object for the wrapper, for comparison func_code = _generator_iterator_wrapper.__iter__.func_code # verify that from_ is only used in a wrapped generator function if __debug__: frame = sys._getframe(2) assert frame is not None and frame.f_code is func_code, ( "from_ called from outside a @uses_from generator function.") if type(iterable) is types.GeneratorType: frame = iterable.gi_frame if frame is not None and frame.f_code is func_code: # this is a wrapped generator, extract the node for it # by peeking at it's locals. self.node = frame.f_locals['self'] else: # an unwrapped generator, create a new node. self.node = _iterator_node(iterable) else: # some other iterable, create a new node. self.node = _iterator_node(iter(iterable)) def uses_from(func): """Decorator for generator functions/methods that use "yield from_(expr)" This class is used together with the from_ class to simulate the proposed 'yield from' statement using existing python features. Use: @uses_from def mygenerator(): ... result = yield _from(expr) ... raise StopIteration(result) To get the equivalent effect of the proposed: def mygenerator(): ... result = yield from expr ... return result Any other use than as a decorator for a normal generator function/method is at your own risk. I wouldn't do it if I were you. Seriously. """ @functools.wraps(func) def wrapper(*args, **kwargs): return _generator_iterator_wrapper(func(*args, **kwargs)) return wrapper

On 3/1/09, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Jacob Holm wrote:
I think the problem might come up with objects that are using the iterator protocol destructively. For example, imagine A and B as worker threads, and R as a work queue.
I would expect that to be interpreted as a StopIteration and handled gracefully. If that doesn't seem reasonable, then I wonder if the whole protocol is still too fragile. -jJ

Jim Jewett wrote:
I've just done what I should have done in the first place and checked the documentation. From the Library Reference, section 3.5, Iterator Types: "The intention of the protocol is that once an iterator's next() method raises StopIteration, it will continue to do so on subsequent calls. Implementations that do not obey this property are deemed broken. (This constraint was added in Python 2.3; in Python 2.2, various iterators are broken according to this rule.)" So according to modern-day rules at least, Jacob's example will work fine. -- Greg

Hi Greg A few comments. First, I think the suggested expansion is not quite right:
Shouldn't this be "_u = _i.throw(e)" instead?
Second, I spend a looong time today thinking about how to make this fast.
True, but as long as it is only chains of generators I can sketch a solution that would give amortized constant time for finding the generator to resume. Unfortunately it is easy to construct a situation where what we have is actually a tree of generators, each using "yield from" its parent. Simple example: def foo(): yield 1 yield 2 yield 3 def bar(it): yield from it root = foo() child1 = bar(root) child2 = bar(root) print child1.next() # prints 1, yielded from root print child2.next() # prints 2, yielded from root In this example, both "child1" and "child2" are yielding from "root". So what we are dealing with is a set of dynamic trees under the operations "find_root" (to find the target when calling the generator methods), "link" (when doing yield from) and "delete_root" (each time a generator is exhausted). I strongly suspect that the lower bound for this problem is O(logn/loglogn) per operation, and I can see a number of ways to do it in O(logn) time. I am not sure any of them are fast enough to beat the simple O(n) solution in real code though. (I will see if I can find a version that has a chance). A thought just occurred to me... would it be acceptable to disallow "yield from" with a generator that is not "fresh"? That would make "child2.next()" above illegal and remove the problem with dealing with trees of generators.
I hope you can get that second version to work. All further optimization would probably have to start with something like that anyway. Best regards Jacob

Jacob Holm wrote:
Yes, I think possibly it should... but I need to wait until my brain stops hurting from thinking about all this before I'll know for certain... I'm no longer sure that the implementation I'm working on can be exactly described in terms of any Python expansion, anyway. One problem is that if the generator gets None from a yield, it has no way of knowing whether it came from a next() or a send(None), so it doesn't know which method to call on the subiterator. The best that it could do is if _v is None: _u = _i.next() else: _u = _i.send(_v) but I would have to modify my implementation as it currently stands to make it work like that. This may be the right thing to do, as it would bring things into line with the advertised equivalence of next() and send(None), and you would still get an exception if you tried to send something non-None to an object without a send() method.
I strongly suspect that the lower bound for this problem is O(logn/loglogn) per operation, and I can see a number of ways to do it in O(logn) time.
Before you bust too many neurons on O() calculations, be aware that the constant factors are important here. I'm relying on traversing a delegation chain using C calls taking negligible time compared to doing it in Python, so that it can be treated as a constant-time operation for all practical purposes regardless of the length of the chain. Testing will reveal whether this turns out to be true in real life... -- Greg

Greg Ewing wrote:
This is only a problem with the recursive implementation though, isn't it? treated as a 'next'. To me, the "communicating directly with the caller" bit is less important than the argument that the caller is still talking to a generator that *has* a send but may ignore the values sent.
Too late, but don't worry. I'm doing this for fun :) I think I can actually see a way to do it that should be fast enough, but I'd like to work out the details first. If it works it will be O(1) with low constants as long as you don't build trees, and similar to traversing a delegation chain in the worst case. All this depends on getting it working using delegation chains first though, as most of the StopIteration and Exception handling would be the same. Best regards Jacob

Bruce Frederiksen wrote:
Let's not let the limitations of what can be expressed directly in Python influence the implementation.
No, but I have an instinct that if something *can* be expressed using basic Python, there's a good chance it's conceptually sound. Anyway, for other reasons I've settled on an interpretation that can be expressed in Python, as it happens. I'll be releasing another draft of the PEP with suitable modifications. -- Greg

Replying to myself here... Jacob Holm wrote:
I have now worked out the details, and it is indeed possible to get O(1) for simple cases and amortized O(logN) in general, all with fairly low constants. I have implemented the tree structure as a python module and added a trampoline-based pure-python implementation of "yield-from" to try it out. It seems that this version beats a normal "for v in it: yield v" when the delegation chains get around 90 generators deep. This may sound like much, but keep in mind that this is all in python. I expect a C implementation of this would break even much sooner than that (hoping for <5). If you (or anyone else) is interested I can post the code here. (Or you can suggest a good place to upload it). Regards Jacob

On 28 Feb 2009, at 20:54, Jacob Holm wrote:
I'm sorry if I'm missing something obvious, but there are two things I can't work out: * What you are measuring the time complexity of. * What N stands for. I suspect that N is the 'delegation depth': the number of yield-from that have to be gone through. I imagine that you are measuring the time it takes to get the next element in the generator. These are guesses - can you correct me?
Can you give an example? -- Arnaud

Hi Arnaud Arnaud Delobelle wrote:
* What you are measuring the time complexity of.
The time for a single 'next', 'send', 'throw' or 'close' call to a generator or a single "yield from" expression, excluding the time spent running the user-defined code in it. (Does that make sense?) In other words, the total overhead of finding the actual user code to run and handling the return values/exceptions according to the PEP.
One interesting thing to note is that all non-contrived examples I have seen only build simple chains of iterators, and only do that by adding one at a time in the deepest nested one. This is the best possible case for my algorithm. If you stick to that, the time per operation is O(1). If we decided to only allow that, the algorithm can be simplified significantly.
Sure, here is the simple code I used for timing the 'next' call import itertools, time from yieldfrom import uses_from, from_ # my module... @uses_from def child(it): yield from_(it) def child2(it): for i in it: yield i def longchain(N): it = itertools.count() for i in xrange(N): it = child(it) # replace this with child2 to test the current # "for v in it: yield v" pattern. it.next() # we are timing the 'next' calls (not the setup of # the chain) so skip the setup by calling next once. return it it = longchain(90) times = [] for i in xrange(10): t1 = time.time() for i in xrange(100000): it.next() t2 = time.time() times.append(t2-t1) print min(times) This version takes about the same time whether you use child or child2 to build the chain. However, the version using yield..from takes the same time no matter how long the chain is, while the time for the "for v in it: yield v" version is linear in the length of the chain, and so would lose big-time for longer chains. I hope this answers your questions. Regards Jacob

Jacob Holm wrote:
How are you measuring 'time', though? Usually when discussing time complexities we're talking about the number of some fundamental operation being performed, and assuming that all such operations take the same time. What operations are you counting here?
I don't understand that limitation. If you keep a stack of active generators, you always have constant-time access to the one to be resumed next. There's some overhead for pushing and popping the stack, but it follows exactly the same pattern as the recursive calls you'd be making if you weren't using some kind of yield-from, so it's irrelevant when comparing the two. -- Greg

Greg Ewing wrote: the like. No hashing, no dynamic arrays, no magic, just plain' ol' fundamental operations as they would be in a C program :)
A \ R --- (whatever R is waiting for) / B Yes, A sees it as a stack [A,R,...], and B sees it as a stack [B,R,...], but the part of the stack following R is the same in the two. If R does a "yield from", the new iterator must appear at the top of both "stacks". Efficiently getting to the top of this "shared stack", and doing the equivalent of push, pop, ... is what I am trying to achieve. And I think I have succeeded.
This would be correct if it was somehow forbidden to create the scenario I sketched above. As long as that scenario is possible I can construct an example where treating it as a simple stack will either do the wrong thing, or do the right thing but slower than a standard "for v in it: yield v". Of course, you could argue that these examples are contrived and we don't have to care about them. I just think that we should do better if we can. FWIW, here is the example from above in more detail... def R(): yield 'A' yield 'B' yield from xrange(3) # we could do anything here really... r = R() def A(): yield from r a = A() def B() yield from r b = B() a.next() # returns 'A' b.next() # returns 'B' r.next() # returns 0 a.next() # returns 1 b.next() # returns 2 This is clearly legal based on the PEP, and it generalizes to a way of building an arbitrary tree with suspended generators as nodes. What my algorithm does is break this tree down into what is essentially a set of stacks. Managed such that the common case has just a single stack, and no matter how twisted your program is, the path from any generator to the root is split across at most O(logN) stacks (where N is the size of the tree). I hope this helps to explain what I think I have done... Best regards Jacob

Jacob Holm wrote:
Unless you're doing something extremely unusual, this situation wouldn't arise. The yield-from statement is intended to run the iterator to exhaustion, and normally you'd create a fresh iterator for each yield-from that you want to do. So A and B would really be yielding from different iterators, even if they were both iterating over the same underlying object. If you did try to share iterators between yield-froms like that, you would have to arrange things so that at least all but one of them broke out of the loop early, otherwise something is going to get an exception due to trying to resume an exhausted iterator. But in any case, I think you can still model this as two separate stacks, with R appearing in both stacks: [A, R] and [B, R]. Whichever one of them finishes yielding from R first pops it from its stack, and when the other one tries to resume R it gets an exception. Either that or it breaks out of its yield-from early and discards its version of R.
That depends on what you think the "right thing" is. If you think that somehow A needs to notice that B has finished yielding from R and gracefully stop doing so itself, then that's not something I intended and it's not the way the current prototype implementation would behave. So IMO you're worrying about a problem that doesn't exist. -- Greg

Greg Ewing wrote:
I am not worried about R running out, each of A and B would find out about that next time they tried to get a value. I *am* worried about R doing a yield-from to X (the xrange in this example) which then needs to appear in both stacks to get the expected behavior from the PEP.
The right thing is whatever the PEP specifies :) You are the author, so you get to decide... I am saying that what the PEP currently specifies is not quite so simple to speed up as you and Arnaud seem to think. (Even with a simple stack, handling 'close' and 'StopIteration' correctly is not exactly trivial)
So IMO you're worrying about a problem that doesn't exist.
No, I am worrying about a problem that so far has only appeared in contrived examples designed to expose it. Any real-life examples I have seen of the "yield from" feature would work perfectly well with a simple stack-based approach. However, I have seen several ideas for speeding up long chains of "yield from"s beyond the current C implementation, and most of them fail either by giving wrong results (bad) or by slowing things down in admittedly unusual cases (not so bad, but not good). Anyway... it is 3 in the morning. As I told Arnaud, I will try to find some time this week to write some more of these crazy examples. Regards Jacob

On 3/1/09, Jacob Holm <jh@improva.dk> wrote:
Greg Ewing wrote:
Jacob Holm wrote:
[naming that for which R waits]
But in any case, I think you can still model this as two separate stacks, with R appearing in both stacks: [A, R] and [B, R].
[A, R, X] and [B, R, X]
I would assume that the second one tries to resume, gets the StopIteration from X, retreats to R, gets the StopIteration there as well, and then continues after its yield-from. If that didn't happen, I would wonder whether (theoretical speed) optimization was leading to suboptimal semantics.
I have to wonder whether any optimization will be a mistake. At the moment, I can't think of any way to do it without adding at least an extra pointer and an extra if-test. That isn't much, but ... how often will there be long chains, vs how often are generators used without getting any benefit from this sort of delegation? -jJ

Jim Jewett wrote:
how often will there be long chains,
My suspicion is not very often. The timing tests I did suggest that the biggest benefit will be from simply removing most of the delegation overhead from a single level of delegation, and you don't need any fancy algorithm for that. My experiments with traversing binary trees suggest that the delegation overhead isn't all that great a problem until the tree is about 20 levels deep, or 1e6 nodes. Even then it doesn't exactly kill you, but even so, my naive implementation shows a clear improvement. -- Greg

Jacob Holm wrote:
Yes, and I tried running it on my prototype implementation. It gives exactly the results you suggested, and any further next() calls on a or b raise StopIteration. You're right that there's no need to break out early in the case of generators, since it seems they just continue to raise StopIteration if you call next() on them after they've finished. Other kinds of iterators might not be so forgiving.
What's wrong with it appearing in both stacks, though, as long as it gives the right result?
It's a bit tricky to handle all the cases correctly, but that has nothing to do with speed. I should perhaps point out that neither of my suggested implementations actually use separate stacks like this. The data structure is really more like the shared stack you suggest, except that it's accessed from the "bottoms" rather than the "top". This is only a speed issue if the time taken to find the "top" starting from one of the "bottoms" is a significant component of the total running time. My conjecture is that it won't be, especially if you do it iteratively in a tight C loop. Some timing experiments I did suggest that the current implementation (which finds the "top" using recursion in C rather than iteration) is at least 20 times faster at delegating a next() call than using a for-loop, which is already a useful improvement, and the iterative method can only make it better. So until someone demonstrates that the simple algorithm I'm using is too slow in practice, I don't see much point in trying to find a smarter one. -- Greg

Greg Ewing wrote:
Could it be possible to design it so that the yield path of generators are passed down or forwarded to sub-generators when they are called? If that can be done then no matter how deep they get, it works as if it is always only one generator deep. So... result = yield from sub-generator Might be sugar for ... (very rough example) sub-generator.forward(this_generator_yield_path) # set yield path sub_generator.run() # pass control to sub-generator result = sub_generator.return_value # get return value if set Of course the plumbing in this may takes some creative rewriting of generators so the yield path can be passed around. Being able to get the yield path might also be useful in other ways, such as error reporting. Cheers, Ron

Ron Adam wrote:
Could it be possible to design it so that the yield path of generators are passed down or forwarded to sub-generators when they are called?
It's really the other way around -- you would need some way of passing the yield path *up* to a generator's caller. E.g. if A is yielding from B is yielding from C, then A needs a direct path to C. Possibly some scheme could be devised to do this, but I don't feel like spending any brain cycles on it until the current scheme is shown to be too slow in practice. Premature optimisation and all that. -- Greg

Greg Ewing wrote:
So when A.next() is called it in effect does a C.next() instead. Is that correct? And when C's yield statement is executed, it needs to return the value to A's caller. So the .next() methods need to be passed up, while the yield return path needs to be passed down? OK, I guess I need to look at some byte/source code. ;-)
Right I agree. I have an intuitive feeling that being able to expose and redirect caller and return values may useful in more ways than just generators. ie.. general functions, translators, encoders, decorators, and possibly method resolution. <shrug> then again, there may not be any easy obvious way to do it. Ron

2009/3/6 Ron Adam <rrr@ronadam.com>:
Greg Ewing wrote:
[...]
This is what the toy python implementation that I posted last month does. I think Jacob Holm did something more sophisticated that does this as well (I haven't seen it!).
So the .next() methods need to be passed up, while the yield return path needs to be passed down?
Can you draw a picture? :) -- Arnaud

Arnaud Delobelle wrote:
I do, and here is the most readable version so far. If you look very closely, you will notice a certain similarity to the version you posted. It turned out there was an easy fix for the 'closing' problem i mentioned, and a hack based on gi_frame that allowed me to use a generator function for the wrapper after all, so the _generator_iterator_wrapper below is heavily based on your code. The rest is there to implement the tree structure I mentioned, instead of just a simple stack. The speed of this version on simple long chains is still about 6 times slower than your code. This can be improved to about 1.5 times by inlining most of the function calls and eliminating the RootPath class, but the resulting code is close to unreadable and therefore not well suited to explain the idea. Most of the remaining slowdown compared to "for v in it: yield v" is due to attribute lookups and simple integer computations. In fact, I would be surprised if a C version of this wasn't going to be faster even for just a single "yield from". Anyway, here it is Jacob """Tree structure implementing the operations needed by yield-from. """ class Node(object): """A Node object represents a single node in the tree. """ __slots__ = ('parent', # the parent of this node (if any) 'chain', # the chain this node belongs to (if any) 'child', # the child of this node in the chain (if any) 'size', # The number of descendants of this node # (including the node itself) that are not # descendants of 'child', plus the number of # times any of these nodes have been accessed. ) def __init__(self): self.parent = None # We are not actually using this one, but # it is cheap to maintain. self.chain = None self.child = None self.size = 0 class Chain(object): """A Chain object represents a fragment of the path from some node towards the root. Chains are long-lived, and are used to make shortcuts in the tree enabling operations to take O(logN) rather than O(N) time. (And even enabling O(1) for certain usage patterns). """ __slots__ = ('top', # topmost node in the chain 'size', # The sum of sizes of all nodes in the chain 'parent', # the parent node of top in the tree 'rp_child', # the child of this chain in the current # root path ) def __init__(self, *nodes): """Construct a chain from the given nodes. The nodes must have a size>0 assigned before constructing the chain, and must have their 'chain' pointer set to None. The nodes are linked together using their 'child' pointers, and get their 'chain' pointers set to the new chain. First node in the list will be at the bottom of the chain, last node in the list becomes the value of the 'top' field. The size of the new chain is the sum of the sizes of the nodes. """ top = None size = 0 for node in nodes: assert node.chain is None assert node.child is None assert node.size > 0 node.chain = self node.child = top size += node.size top = node parent = None for node in reversed(nodes): node.parent = parent parent = node self.top = top self.size = size self.parent = None self.rp_child = None class RootPath(object): """A RootPath represents the whole path from the root to some given node. RootPaths need to be 'acquired' before use and 'released' after. Acquiring the path establishes the necessary down-links, ensures the path has length O(logN), and gives an efficient way of detecting and avoiding loops. """ __slots__ = ('base', # The node defining the path 'root', # The root node of the tree ) def __init__(self, base): """Construct the RootPath representing the path from base to its root. """ assert isinstance(base, Node) self.base = base self.root = None def acquire(self, sizedelta=0): """Find the root and take ownership of the tree containing self.base. Create a linked list from the root to base using the Chain.rp_child pointers. (Using self as sentinel in self.base.rp_child). Optionally adds 'sizedelta' to the size of the base node for the path and updates the rest of the sizes accordingly. If the tree was already marked (one of the chains had a non-None rp_child pointer), back out all changes and return None, else return the root node of the tree. """ assert self.root is None node = self.base assert node is not None rp_child = self while True: chain = node.chain assert chain is not None if chain.rp_child is not None: # Some other rootpath already owns this tree. Undo the # changes so far and raise a RuntimeError if rp_child is not self: while True: chain = rp_child rp_child = chain.rp_child chain.rp_child = None if rp_child is self: break node = rp_child.parent node.size -= sizedelta chain.size -= sizedelta return None assert chain.rp_child is None node.size += sizedelta chain.size += sizedelta chain.rp_child = rp_child rp_child = chain node = rp_child.parent if node is None: break self.root = root = rp_child.top assert root.chain is not None assert root.chain.parent is None # Tricky, this rebalancing is needed because cut_root # cannot do a full rebalancing fast enough without maintaining # a lot more information. We may actually have traversed a # (slightly) unbalanced path above. Rebalancing here makes # sure that it is balanced when we return, and the cost of # traversing the unbalanced path can be included in the cost # of rebalancing it. The amortized cost is still O(logn) per # operation as it should be. self._rebalance(self, False) return root def release(self): """Release the tree containing this RootPath. """ assert self.root is not None chain = self.root.chain assert chain is not None while chain is not self: child = chain.rp_child chain.rp_child = None chain = child self.root = None def cut_root(self): """Cut the link between the root and its child on the root path. Release the tree containing the root. If the root was the only node on the path, return None. Else return the new root. """ root = self.root assert root is not None chain = root.chain assert chain.parent is None assert root is chain.top child = chain.rp_child assert child is not None if child is self: # only one chain if root is self.base: # only one node, release tree chain.rp_child = None self.root = None return None else: # multiple chains if root is child.parent: # only one node from this chain on the path. root.size -= child.size chain.size -= child.size child.parent = None chain.rp_child = None self.root = newroot = child.top newroot.parent = None return newroot # Multiple nodes on the chain. Cut the topmost off and put it # into its own chain if necessary. (This is needed when the # node has other children) newroot = root.child assert newroot newroot.parent = None self.root = chain.top = newroot chain.size -= root.size root.child = None root.chain = None Chain(root) self._rebalance(self, True) return newroot def link(self, node): """Make the root of this tree a child of a node from another tree. Return the root of the resulting tree on succes, or None if the tree for the parent node couldn't be acquired. """ root = self.root assert root is not None chain = root.chain assert chain.parent is None assert isinstance(node, Node) rp = RootPath(node) newroot = rp.acquire(chain.size) if newroot is None: return None self.root = newroot node.chain.rp_child = chain root.parent = chain.parent = node self._rebalance(chain.rp_child, False) return newroot def _rebalance(self, stop, quick): # check and rebalance all the chains starting from the root. # If 'quick' is True, stop the first time no rebalancing took # place, else continue until the child is 'stop'. gpchain = None pchain = self.root.chain chain = pchain.rp_child while chain is not stop: parent = chain.parent if 2*(pchain.size-parent.size) <= chain.size: # Unbalanced chains. Move all ancestors to parent from # pchain into this chain. This may look like an # expensive operation, but the balancing criterion is # chosen such that every time a node is moved from one # chain to another, the sum of the sizes of everything # *after* the node in its chain is at least # doubled. This number is only decreased by cut_root # (where it may be reset to zero), so a node can move # between chains at most log_2(N) times before if # becomes the root in a cut_root. The amortized cost # of keeping the tree balanced is thus O(logN). The # purpose of the balancing is of course to keep the # height of the tree down. Any node that is balanced # according to this criterion has # # 2*(pchain.size-self.size) > 2*(pchain.size-self.parent.size) # > self.size # # and so # # pchain.size > 1.5*self.size # # Therefore, the number of chains in any balanced # RootPath is at most log_1.5(N), and so the cost per # operation is O(logN). # Compute size of elements to move and set their 'chain' # pointers. p = pchain.top movedsize = p.size p.chain = chain while p is not parent: p = p.child movedsize += p.size p.chain = chain # update sizes parent.size -= chain.size chain.size = pchain.size pchain.size -= movedsize parent.size += pchain.size # update child, top and parent links pchain.top, parent.child, chain.top \ = parent.child, chain.top, pchain.top chain.parent = pchain.parent pchain.parent = parent # update rp_child links pchain.rp_child = None # pchain is no longer on the path if gpchain is not None: assert gpchain is not None assert gpchain.rp_child is pchain gpchain.rp_child = chain assert (pchain.top is None)==(pchain.size==0) # if pchain.top is None: # # # pchain has become empty. If coding this in C, # # remember to free the memory. elif quick: break else: gpchain = pchain pchain = chain chain = pchain.rp_child ############################################################################### """Yield-from implementation """ import sys # _getframe, used only in an assert import types # GeneratorType import functools # wraps class _iterator_node(Node): # Wrapper for turning an unknown iterator into a node in the tree. __slots__ = ('iterator', # the wrapped iterator ) locals().update((k, Node.__dict__[k]) for k in ('parent', 'chain', 'child', 'size')) def __init__(self, iterator): self.iterator = iterator Node.__init__(self) self.size = 1 Chain(self) class _generator_iterator_wrapper(_iterator_node): # Wrapper for turning a generator using "yield from_(expr)" into a # node in the tree. __slots__ = () locals().update((k, _iterator_node.__dict__[k]) for k in ('parent', 'chain', 'child', 'size', 'iterator')) def __new__(cls, iterator): self = _iterator_node.__new__(cls) _iterator_node.__init__(self, iterator) return self.__iter__() # we don't hold on to a reference to # this generator, because a) we don't # need to, and b) when the last # user-code reference to it goes away, # the generator is automatically closed # and we get a chance to clean up the # rest of the cycles created by this # structure. def __iter__(self): val = exc = None rp = RootPath(self) while True: try: if rp.acquire(1) is None: raise ValueError('generator already executing') while True: try: gen = rp.root.iterator try: if exc is not None: throw = getattr(gen, 'throw', None) try: if throw is None: raise exc ret = throw(exc) finally: del throw exc = None elif val is None: ret = gen.next() else: ret = gen.send(val) except: close = getattr(gen, 'close', None) try: if close is not None: close() raise finally: del close finally: del gen except Exception, e: if rp.cut_root() is None: raise if isinstance(e, StopIteration): val, exc = getattr(e, 'val', None), None else: val, exc = None, e else: if type(ret) is from_: if rp.link(ret.node) is not None: val = None else: exc = ValueError('generator already executing') continue break finally: if rp.root is not None: rp.release() try: val = yield ret except Exception, e: exc = e class from_(object): """This class is used together with the uses_from decorator to simulate the proposed 'yield from' statement using existing python features. Use: @uses_from def mygenerator(): ... result = yield _from(expr) ... raise StopIteration(result) To get the equivalent effect of the proposed: def mygenerator(): ... result = yield from expr ... return result Any use other than directly in a yield expression within a generator function decorated with 'uses_from' is unsupported, and could eat your harddrive for all I care. Unsupported uses include, but are not limited to: subclassing, calling methods, reading or writing attributes, storing in a variable, and passing as argument to a builtin or other function. """ __slots__ = ('node',) def __init__(self, iterable): # get the code object for the wrapper, for comparison func_code = _generator_iterator_wrapper.__iter__.func_code # verify that from_ is only used in a wrapped generator function if __debug__: frame = sys._getframe(2) assert frame is not None and frame.f_code is func_code, ( "from_ called from outside a @uses_from generator function.") if type(iterable) is types.GeneratorType: frame = iterable.gi_frame if frame is not None and frame.f_code is func_code: # this is a wrapped generator, extract the node for it # by peeking at it's locals. self.node = frame.f_locals['self'] else: # an unwrapped generator, create a new node. self.node = _iterator_node(iterable) else: # some other iterable, create a new node. self.node = _iterator_node(iter(iterable)) def uses_from(func): """Decorator for generator functions/methods that use "yield from_(expr)" This class is used together with the from_ class to simulate the proposed 'yield from' statement using existing python features. Use: @uses_from def mygenerator(): ... result = yield _from(expr) ... raise StopIteration(result) To get the equivalent effect of the proposed: def mygenerator(): ... result = yield from expr ... return result Any other use than as a decorator for a normal generator function/method is at your own risk. I wouldn't do it if I were you. Seriously. """ @functools.wraps(func) def wrapper(*args, **kwargs): return _generator_iterator_wrapper(func(*args, **kwargs)) return wrapper

On 3/1/09, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Jacob Holm wrote:
I think the problem might come up with objects that are using the iterator protocol destructively. For example, imagine A and B as worker threads, and R as a work queue.
I would expect that to be interpreted as a StopIteration and handled gracefully. If that doesn't seem reasonable, then I wonder if the whole protocol is still too fragile. -jJ

Jim Jewett wrote:
I've just done what I should have done in the first place and checked the documentation. From the Library Reference, section 3.5, Iterator Types: "The intention of the protocol is that once an iterator's next() method raises StopIteration, it will continue to do so on subsequent calls. Implementations that do not obey this property are deemed broken. (This constraint was added in Python 2.3; in Python 2.2, various iterators are broken according to this rule.)" So according to modern-day rules at least, Jacob's example will work fine. -- Greg
participants (6)
-
Arnaud Delobelle
-
Bruce Frederiksen
-
Greg Ewing
-
Jacob Holm
-
Jim Jewett
-
Ron Adam