[Python-Dev] Simple generators, round 2

[Neil Schemenauer]

I've got a different implementation.  There are no new keywords
and its simpler to wrap a high level interface around the low
interface.

    http://arctrix.com/nas/python/generator2.diff

What the patch does:

    Split the big for loop and switch statement out of eval_code2
    into PyEval_EvalFrame.

    Add a new "why" flag for ceval, WHY_SUSPEND.  It is similar to
    WHY_RETURN except that the frame value stack and the block stack
    are not touched.  The frame is also marked resumable before
    returning (f_stackbottom != NULL).

    Add two new methods to frame objects, suspend and resume.
    suspend takes one argument which gets attached to the frame
    (f_suspendvalue).  This tells ceval to suspend as soon as control
    gets back to this frame.  resume, strangely enough, resumes a
    suspended frame.  Execution continues at the point it was
    suspended.  This is done by calling PyEval_EvalFrame on the frame
    object.

    Make frame_dealloc clean up the stack and decref f_suspendvalue
    if it exists.

There are probably still bugs and it slows down ceval too much
but otherwise things are looking good.  Here are some examples
(the're a little long and but illustrative).  Low level
interface, similar to my last example:

    # print 0 to 999
    import sys

    def g():
        for n in range(1000):
            f = sys._getframe()
            f.suspend((n, f))
        return None, None

    n, frame = g()
    while frame:
        print n
        n, frame = frame.resume()

Let's build something easier to use:

    # Generator.py
    import sys

    class Generator:
        def __init__(self):
            self.frame = sys._getframe(1)
            self.frame.suspend(self)
            
        def suspend(self, value):
            self.frame.suspend(value)

        def end(self):
            raise IndexError

        def __getitem__(self, i):
            # fake indices suck, need iterators
            return self.frame.resume()

Now let's try Guido's pi example now:

    # Prints out the frist 100 digits of pi
    from Generator import Generator

    def pi():
        g = Generator()
        k, a, b, a1, b1 = 2L, 4L, 1L, 12L, 4L
        while 1:
            # Next approximation
            p, q, k = k*k, 2L*k+1L, k+1L
            a, b, a1, b1 = a1, b1, p*a+q*a1, p*b+q*b1
            # Print common digits
            d, d1 = a/b, a1/b1
            while d == d1:
                g.suspend(int(d))
                a, a1 = 10L*(a%b), 10L*(a1%b1)
                d, d1 = a/b, a1/b1

    def test():
        pi_digits = pi()
        for i in range(100):
            print pi_digits[i],

    if __name__ == "__main__":
        test()

Some tree traversals:

    from types import TupleType
    from Generator import Generator

    # (A - B) + C * (E/F)
    expr = ("+", 
             ("-", "A", "B"),
             ("*", "C",
                  ("/", "E", "F")))
               
    def postorder(node):
        g = Generator()
        if isinstance(node, TupleType):
            value, left, right = node
            for child in postorder(left):
                g.suspend(child)
            for child in postorder(right):
                g.suspend(child)
            g.suspend(value)
        else:
            g.suspend(node)
        g.end()

    print "postorder:",
    for node in postorder(expr):
        print node,
    print

This prints:

    postorder: A B - C E F / * +

Cheers,

  Neil