[ Eric S. Raymond]

... I want this feature [generators] a lot. Guido has agreed in principle that we ought to have generators, but there is not yet a well-defined path forward to them. Stackless may be the most promising route.

Actually, if we had a PEP <wink>, it would have recorded for all time that Guido gave a detailed description of how to implement generators with minor changes to the current code. It would also record that Steven Majewski had already done so some 5 or 6 years ago. IMO, the real reason we don't have generators already is that they keep getting hijacked by continuations (indeed, Steven gave up on his patches as soon as he realized he couldn't extend his approach to continuations).

I was going to explain coroutines separately, but I realized while writing this that the semantics of "yield" proposed above actually gives full coroutining.

Well, the Icon semantics for "suspend"-- which are sufficient for Icon's generators --are not sufficient for Icon's coroutines. It's for that very reason that Icon supports generators on all platforms (including JCon, their moral equivalent of JPython), but supports coroutines only on platforms that have the magical blob of platform-dependent machine-language cruft needed to trick out the C stack at coroutine context switches (excepting JCon, where coroutines are implemented as Java threads). Coroutines are plain harder. Generators are just semi-coroutines (suspend/yield *always* return "to the caller", and that makes life 100x easier in a conventional eval loop like Python's -- it's still "stack-like", and the only novel thing needed is a way to resume a suspended frame but still in call-like fashion). and-if-we-had-a-pep-every-word-of-this-reply-would-have-been- in-it-too<wink>-ly y'rs - tim

[Tim]

IMO, the real reason we don't have generators already is that they keep getting hijacked by continuations (indeed, Steven gave up on his patches as soon as he realized he couldn't extend his approach to continuations).

[esr]

This report of repeated "hijacking" doesn't surprise me a bit. In fact, if I'd thought about it I'd have *expected* it. We know from experience with other languages (notably Scheme) that call-with- current-continuation is the simplest orthogonal primitive that this whole cluster of concepts can be based on. Implementors with good design taste are going to keep finding their way back to it, and they're going to feel incompleteness and pressure if they can't get there.

On the one hand, I don't think I know of a language *not* based on Scheme that has call/cc (or a moral equivalent). REBOL did at first, but after Joe Marshal left, Carl Sassenrath ripped it out in favor of a more conventional implementation. Even the massive Common Lisp declined to adopt call/cc, the reasons for which Kent Pitman has posted eloquently and often on comp.lang.lisp (basically summarized by that continuations are, in Kent's view, "a semantic mess" in the way Scheme exposed them -- btw, people should look his stuff up, as he has good ideas for cleaning that mess w/o sacrificing the power (and so the Lisp world splinters yet again?)). So call/cc remains "a Scheme thing" to me after all these years, and even there by far the most common warning in the release notes for a new implementation is that call/cc doesn't work correctly yet or at all (but, in the meantime, here are 3 obscure variations that will work in hard-to-explain special cases ...). So, ya, we *do* have experience with this stuff, and it sure ain't all good. On the other hand, what implementors other than Schemeheads *do* keep rediscovering is that generators are darned useful and can be implemented easily without exotic views of the world. CLU, Icon and Sather all fit in that box, and their designers wouldn't touch continuations with a 10-foot thick condom <wink>.

This is why I'm holding out for continuation objects and call-with-continuation to be an explicit Python builtin. We're going to get there anyway; best to do it cleanly right away.

This can get sorted out in the PEP. As I'm sure someone else has screamed by now (because it's all been screamed before), Stackless and the continuation module are distinct beasts (although the latter relies on the former). It would be a shame if the fact that it makes continuations *possible* were to be held against Stackless. It makes all sorts of things possible, some of which Guido would even like if people stopped throwing continuations in his face long enough for him to see beyond them <0.5 wink -- but he doesn't like continuations, and probably never will>.

[Tim]

On the one hand, I don't think I know of a language *not* based on Scheme that has call/cc (or a moral equivalent).

[Jeremy Hylton]

ML also has call/cc, at least the Concurrent ML variant.

So it does! I've found 3 language lines that have full-blown call/cc (not counting the early versions of REBOL, since they took it out later), and at least one web page claiming "that's all, folks": 1. Scheme + derivatives (but not including most Lisps). 2. Standard ML + derivatives (but almost unique among truly functional languages): http://cm.bell-labs.com/cm/cs/what/smlnj/doc/SMLofNJ/pages/cont.html That page is pretty much incomprehensible on its own. Besides callcc (no "/"), SML-NJ also has related "throw", "isolate", "capture" and "escape" functions. At least some of them *appear* to be addressing Kent Pitman's specific complaints about the excruciating interactions between call/cc and unwind-protect in Scheme. 3. Unlambda. This one is a hoot! Don't know why I haven't bumped into it before: http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/ "Your Functional Programming Language Nightmares Come True" Unlambda is a deliberately obfuscated functional programming language, whose only data type is function and whose only syntax is function application: no lambdas (or other "special forms"), no integers, no lists, no variables, no if/then/else, ... call/cc is spelled with the single letter "c" in Unlambda, and the docs note "expressions including c function calls tend to be hopelessly difficult to track down. This was, of course, the reason for including it in the language in the first place". Not all frivolous, though! The page goes on to point out that writing an interpreter for Unlambda in something other than Scheme exposes many of the difficult issues (like implementing call/cc in a language that doesn't have any such notion -- which is, after all, almost all languages), in a language that's otherwise relentlessly simple-minded so doesn't bog you down with accidental complexities. Doesn't mean call/cc sucks, but language designers *have* been avoiding it in vast numbers -- despite that the Scheme folks have been pushing it (& pushing it, & pushing it) in every real language they flee to <wink>. BTW, lest anyone get the wrong idea, I'm (mostly) in favor of it! It can't possibly be sold on any grounds other than that "it works, for real Python programmers with real programming problems they can't solve in other ways", though. Christian has been doing a wonderful (if slow-motion <wink>) job of building that critical base of real-life users.

Jeremy Hylton wrote:

If someone is going to write a PEP, I hope they will explain how the implementation deals with the various Python C API calls that can call back into Python.

He will.

In the stackless implementation, builtin_apply is a thin wrapper around builtin_apply_nr. The wrapper checks the return value from builtin_apply_nr for Py_UnwindToken. If Py_UnwindToken is found, it calls PyEval_Frame_Dispatch. In this case, builtin_apply returns whatever PyEval_Frame_Dispatch returns; the frame dispatcher just executes stack frames until it is ready to return.

Correct.

How does this control flow at the C level interact with a Python API call like PySequence_Tuple or PyObject_Compare that can start executing Python code again? Say there is a Python function call which in turn calls PySequence_Tuple, which in turn calls a __getitem__ method on some Python object, which in turn uses a continuation to transfer control. After the continuation is called, the Python function will never return and the PySquence_Tuple call is no longer necessary, but there is still a call to PySequence_Tuple on the C stack. How does stackless deal with the return through this function?

Right. What you see here is the incompleteness of Stackless. In order to get this "right", I would have to change many parts of the implementation, in order to allow for continuations in every (probably even unwanted) place. I could not do this. Instead, the situation of these still occouring recursions are handled differently. continuationmodule guarantees, that in the context of recursive interpreter calls, the given stack order of execution is obeyed. Violations of this cause simply an exception.

I expect that any C function that may cause Python code to be executed must be wrapped the way apply was wrapper. So in the example, PySequence_Tuple may return Py_UnwindToken. This adds an extra return condition that every caller of PySequence_Tuple must check. Currently, the caller must check for NULL/exception in addition to a normal return. With stackless, I assume the caller would also need to check for "unwinding."

No, nobody else is allowed to return Py_UnwindToken but the few functions in the builtins implementation and in ceval. The continuationmodule may produce it since it knows the context where it is called. eval_code is supposed to be the main instance who checks for this special value. As said, allowing this in any context would have been a huge change to the whole implementation, and would probably also have broken existing extensions which do not expect that a standard function wants to do a callback.

Is this analysis correct? Or is there something I'm missing?

I see that the current source release of stackless does not do anything special to deal with C API calls that execute Python code. For example, PyDict_GetItem calls PyObject_Hash, which could in theory lead to a call on a continuation, but neither caller nor callee does anything special to account for the possibility. Is there some other part of the implementation that prevents this from being a problem?

This problem is no problem for itself, since inside the stackless modification for Python, there are no places where unexpected Py_UnwindTokens or continuations are produced. This is a closed system insofar. But with the continuation extension, it is of course a major problem. The final solution to the recursive interpreter/continuation problem was found long after my paper was presented. The idea is simple, solves everything, and shortened my implementation substantially: Whenever a recursive interpreter call takes place, the calling frame gets a lock flag set. This flag says "this frame is wrapped in a suspended eval_code call and cannot be a continuation". continuationmodule always obeys this flag and prevends the creation of continuations for such frames by raising an exception. In other words: Stack-like behavior is enforced in situations where the C stack is involved. So, a builtin or an extension *can* call a continuation, but finally, it will have to come back to the calling point. If not, then one of the locked frames will be touched, finally, in the wrong C stack order. But by reference counting, this touching will cause the attempt to create a continuation, and what I said above will raise an exception. Probably the wrong place to explain this in more detail here, but it doesn't apply to the stackless core at all which is just responsible for the necessary support machinery. ciao - chris -- Christian Tismer :^) <mailto:tismer@appliedbiometrics.com> Applied Biometrics GmbH : 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

[about recursion and continuations]

CT> Right. What you see here is the incompleteness of Stackless. In CT> order to get this "right", I would have to change many parts of CT> the implementation, in order to allow for continuations in every CT> (probably even unwanted) place. I could not do this.

CT> Instead, the situation of these still occouring recursions are CT> handled differently. continuationmodule guarantees, that in the CT> context of recursive interpreter calls, the given stack order of CT> execution is obeyed. Violations of this cause simply an CT> exception.

Let me make sure I understand: If I invoke a continuation when there are extra C stack frames between the mainloop invocation that captured the continuation and the call of the continuation, the interpreter raises an exception?

Not always. Frames which are not currently bound by an interpreter acting on them can always be jump targets. Only those frames which are currently in the middle of an opcode are forbidden.

If so, continuations don't sound like they would mix well with C extension modules and callbacks. I guess it also could not be used inside methods that implement operator overloading. Is there a simple set of rules that describe the situtations where they will not work?

Right. In order to have good mixing with C callbacks, extra work is necessary. The C extension module must then play the same frame dribbling game as the eval_loop does. An example can be found in stackless map. If the C extension does not do so, it restricts execution order in the way I explained. This is not always needed, and it is no new requirement for C developers to do so. Only if they want to support free continuation switching, they have to implement it. The simple set of rules where continuations will not work at the moment is: Generally it does not work across interpreter recursions. At least restrictions appear: - you cannot run an import and jump off to the caller's frame + but you can save a continuation in your import and use it later, when this recursive interpreter is gone. - all special class functions are restricted. + but you can for instance save a continuation in __init__ and use it later, when the init recursion has gone. Reducing all these restrictions is a major task, and there are situations where it looks impossible without an extra subinterpreter language. If you look into the implementation of operators like __add__, you will see that there are repeated method calls which all may cause other interpreters to show up. I tried to find a way to roll these functions out in a restartable way, but it is quite a mess. The clean way to do it would be to have microcodes, and to allow for continuations to be caught between them. this-is-a-stackless-3000-feature - ly y'rs - chris -- Christian Tismer :^) <mailto:tismer@appliedbiometrics.com> Applied Biometrics GmbH : 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

Gordon, Thanks for channeling Christian, if that's what writing a PEP on this entails :-). I am also a little puzzled about the subject of the PEP. I think you should hash it out with Barry "PEPmeister" Warsaw. There are two different issues -- the stackless implementation and the new control structure exposed to programmers (e.g. continuations, coroutines, iterators, generators, etc.). It seems plausible to address these in two different PEPs, possibly in competing PEPs (e.g. coroutines vs. continuations). Jeremy

Vladimir Marangozov wrote:

Gordon McMillan wrote:

...

But I can't figure out what the h*ll is being PEPed. ...

...

...

ceval.c and grammar changes (or Christian can make it so), it seems to me the PEPable issue is whether the value this can add is worth the price of a less linear implementation.

There's an essay + paper available, slides and an implementation.

Of which the most up to date is the implementation. The slides / docs describe an earlier, more complex scheme.

What's the problem about formalizing this in a PEP and addressing the controversial issues + explaining how they are dealt with?

That's sort of what I was asking. As far as I can tell, what's controversial is "continuations". That's not in scope. I would like to know what controversial issues there are that *are* in scope.

I mean, if you're a convinced long-time Stackless user and everything is obvious for you, this PEP should try to convince the rest of us -- so write it down and ask no more <wink>.

That's exactly wrong. If that were the case, I would be forced to vote -1 on any addition / enhancement to Python that I personally didn't plan on using. - Gordon