This kind of low level impl. where suspension points are known at runtime only, cannot be implemented in jython (at least not in a non costly and reasonable way). Jython codebase is likely to just allow generators with suspension points known at compilation time. regards. ----- Original Message ----- From: Neil Schemenauer <nas@arctrix.com> To: <python-dev@python.org> Sent: Sunday, March 18, 2001 3:17 AM Subject: [Python-Dev] Simple generators, round 2

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

_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev

On Mon, Mar 19, 2001 at 04:49:37PM +0100, Christian Tismer wrote:

A possible bug may be in frame_resume, where you are doing + f->f_back = tstate->frame; without taking care of the prior value of f_back.

Good catch. There is also a bug when f_suspendvalue is being set (Py_XDECREF should be called first). [Christian on disallowing resume on frame already running]

1) introduce a lock flag for frames which are currently executed by some interpreter on the C stack. This is what Stackless does currently. Maybe you can just use your new f_suspendvalue field. frame_resume must check that this value is not NULL on entry, and set it zero before resuming.

Another good catch. It would be easy to set f_stackbottom to NULL at the top of PyEval_EvalFrame. resume already checks this to decide if the frame is resumable.

2) Do not expose the resume and suspend methods to the Python user, and recode Generator.py as an extension module in C. This should prevent abuse of frames.

I like the frame methods. However, this may be a good idea since Jython may implement things quite differently.

Proposal for a different interface: I would change the interface of PyEval_EvalFrame to accept a return value passed in, like Stackless has its "passed_retval", and maybe another variable that explicitly tells the kind of the frame call, i.e. passing the desired why_code. This also would make it easier to cope with the other needs of Stackless later in a cleaner way. Well, I see you are clearing the f_suspendvalue later. Maybe just adding the why_code to the parameters would do. f_suspendvalue can be used for different things, it can also become the place to store a return value, or a coroutine transfer parameter.

In the future, there will not obly be the suspend/resume interface. Frames will be called for different reasons: suspend with a value (generators) return with a value (normal function calls) transfer with a value (coroutines) transfer with no value (microthreads)

The interface needs some work and I'm happy to change it to better accommodate stackless. f_suspendvalue and f_stackbottom are pretty ugly, IMO. One unexpected benefit: with PyEval_EvalFrame split out of eval_code2 the interpreter is 5% faster on my machine. I suspect the compiler has an easier time optimizing the loop in the smaller function. BTW, where is this stackless light patch I've been hearing about? I would be interested to look at it. Thanks for your comments. Neil

[Neil]

One unexpected benefit: with PyEval_EvalFrame split out of eval_code2 the interpreter is 5% faster on my machine. I suspect the compiler has an easier time optimizing the loop in the smaller function.

[Christian]

Really!? I thought you told about a speed loss?

You must be referring to an earlier post I made. That was purely speculation. I didn't time things until the weekend. Also, the 5% speedup is base on the refactoring of eval_code2 with the added generator bits. I wouldn't put much weight on the apparent speedup either. Its probably slower on other platforms. Neil

On Mon, Mar 19, 2001 at 09:21:59AM -0800, Neil Schemenauer wrote:

Also, the 5% speedup is base on the refactoring of eval_code2 with the added generator bits.

Ugh, that should say "based on the refactoring of eval_code2 WITHOUT the generator bits". engage-fingers-before-brain-ly y'rs Neil

Neil Schemenauer wrote:

On Mon, Mar 19, 2001 at 06:25:43PM +0100, Christian Tismer wrote:

...

I believe this is going to be the best possible efficient implementation of generators. And I'm very confident that it will make it into the core with ease and without the need for a PEP.

I sure hope not. We need to come up with better APIs and a better interface from Python code. The current interface is not efficiently implementable in Jython, AFAIK. We also need to figure out how to make things play nicely with stackless. IMHO, a PEP is required.

Yes, sure. What I meant was not the current code, but the simplistic, straightforward approach.

My plan now is to look at how stackless works as I now understand some of the issues. Since no stackless light patch exists writing one may be a good learning project. Its still a long road to 2.2. :-)

Warning, *unreadable* code. If you really want to read that, make sure to use ceval_pre.c, this comes almost without optimization. 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 on comparing fringes of two trees]:

In Icon you need to create co-expressions to solve this problem, because its generators aren't explicitly resumable, and Icon has no way to spell "kick a pair of generators in lockstep". But explicitly resumable generators are in fact "good enough" for this classic example, which is usually used to motivate coroutines.

Apparently they are good for lots of other things too. Tonight I implemented passing values using resume(). Next, I decided to see if I had enough magic juice to tackle the coroutine example from Gordon's stackless tutorial. Its turns out that I didn't need the extra functionality. Generators are enough. The code is not too long so I've attached it. I figure that some people might need a break from 2.1 release issues. I think the generator version is even simpler than the coroutine version. Neil # Generator example: # The program is a variation of a Simula 67 program due to Dahl & Hoare, # who in turn credit the original example to Conway. # # We have a number of input lines, terminated by a 0 byte. The problem # is to squash them together into output lines containing 72 characters # each. A semicolon must be added between input lines. Runs of blanks # and tabs in input lines must be squashed into single blanks. # Occurrences of "**" in input lines must be replaced by "^". # # Here's a test case: test = """\ d = sqrt(b**2 - 4*a*c) twoa = 2*a L = -b/twoa R = d/twoa A1 = L + R A2 = L - R\0 """ # The program should print: # d = sqrt(b^2 - 4*a*c);twoa = 2*a; L = -b/twoa; R = d/twoa; A1 = L + R; #A2 = L - R #done # getlines: delivers the input lines # disassemble: takes input line and delivers them one # character at a time, also inserting a semicolon into # the stream between lines # squasher: takes characters and passes them on, first replacing # "**" with "^" and squashing runs of whitespace # assembler: takes characters and packs them into lines with 72 # character each; when it sees a null byte, passes the last # line to putline and then kills all the coroutines from Generator import Generator def getlines(text): g = Generator() for line in text.split('\n'): g.suspend(line) g.end() def disassemble(cards): g = Generator() try: for card in cards: for i in range(len(card)): if card[i] == '\0': raise EOFError g.suspend(card[i]) g.suspend(';') except EOFError: pass while 1: g.suspend('') # infinite stream, handy for squash() def squash(chars): g = Generator() while 1: c = chars.next() if not c: break if c == '*': c2 = chars.next() if c2 == '*': c = '^' else: g.suspend(c) c = c2 if c in ' \t': while 1: c2 = chars.next() if c2 not in ' \t': break g.suspend(' ') c = c2 if c == '\0': g.end() g.suspend(c) g.end() def assemble(chars): g = Generator() line = '' for c in chars: if c == '\0': g.end() if len(line) == 72: g.suspend(line) line = '' line = line + c line = line + ' '*(72 - len(line)) g.suspend(line) g.end() if __name__ == '__main__': for line in assemble(squash(disassemble(getlines(test)))): print line print 'done'

On Sun, Mar 25, 2001 at 12:07:20AM -0500, Tim Peters wrote:

If you give me a coroutine program, and let me add a "control loop", ...

This is exactly what I started doing when I was trying to rewrite your Coroutine.py module to use generators.

A. Simple to implement in CPython without threads, and at least possible likewise even for Jython.

I'm not sure about Jython. The sys._getframe(), frame.suspend(), and frame.resume() low level interface is nice. I think Jython must know which frames are going to be suspended at compile time. That makes it hard to build higher level control abstractions. I don't know much about Jython though so maybe there's another way. In any case it should be possible to use threads to implement some common higher level interfaces. Neil

...

...

...

...

"TP" == Tim Peters <tim.one@home.com> writes:

...

I'm not sure about Jython. The sys._getframe(), frame.suspend(), and frame.resume() low level interface is nice. I think Jython must know which frames are going to be suspended at compile time.

TP> Yes, Samuele said as much. My belief is that generators don't TP> become *truly* pleasant unless "yield" ("suspend"; whatever) is TP> made a new statement type. Then Jython knows exactly where TP> yields can occur. As in CLU (but not Icon), it would also be TP> fine by me if routines *used* as generators also needed to be TP> explicitly marked as such (this is a non-issue in Icon because TP> *every* Icon expression "is a generator" -- there is no other TP> kind of procedure there). If "yield" is a keyword, then any function that uses yield is a generator. With this policy, it's straightforward to determine which functions are generators at compile time. It's also Pythonic: Assignment to a name denotes local scope; use of yield denotes generator. Jeremy

Jeremy Hylton <jeremy@alum.mit.edu>:

If "yield" is a keyword, then any function that uses yield is a generator. With this policy, it's straightforward to determine which functions are generators at compile time.

But a function which calls a function that contains a "yield" is a generator, too. Does the compiler need to know about such functions? 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 +--------------------------------------+