Christian Tismer wrote:

rushing@nightmare.com wrote:

[...]

...

I haven't tested it thoroughly, but I have successfully saved and invoked (and reinvoked) a continuation. Caveat: I have to turn off Py_DECREF in order to keep it from crashing.

It is possible, but a little hard. To take a working snapshot of the current thread's stack, one needs not only the stack snapshot which continue.c provides, but also a restorable copy of all frame objects involved so far. A copy of the current frame chain must be built, with proper reference counting of all involved elements. And this is the crux: The current stack pointer of the VM is not present in the frame objects, but hangs around somewhere on the machine stack. Two solutions: 1) modify PyFrameObject by adding a field which holds the stack pointer, when a function is called. I don't like to change the VM in any way for this. 2) use the lasti field which holds the last VM instruction offset. Then scan the opcodes of the code object and calculate the current stack level. This is possible since Guido's code generator creates code with the stack level lexically bound to the code offset. Now we can incref all the referenced objects in the frame. This must be done for the whole chain, which is copied and relinked during that. This chain is then held as a property of the continuation object. To throw the continuation, the current frame chain must be cleared, and the saved one is inserted, together with the machine stack operation which Sam has already. A little hefty, isn't it? ciao - chris -- Christian Tismer :^) mailto:tismer@appliedbiometrics.com Applied Biometrics GmbH : Have a break! Take a ride on Python's Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net 10553 Berlin : PGP key -> http://wwwkeys.pgp.net PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF we're tired of banana software - shipped green, ripens at home

Tim Peters wrote: [to Sam]

The other point being that you want to avoid "inside out" logic, though, right? Earlier you posted a kind of ideal:

Recently I've written an async server that needed to talk to several other RPC servers, and a mysql server. Pseudo-example, with possibly-async calls in UPPERCASE:

auth, archive = db.FETCH_USER_INFO (user) if verify_login(user,auth): rpc_server = self.archive_servers[archive] group_info = rpc_server.FETCH_GROUP_INFO (group) if valid (group_info): return rpc_server.FETCH_MESSAGE (message_number) else: ... else: ...

I assume you want to capture a continuation object in the UPPERCASE methods, store it away somewhere, run off to your select/poll/whatever loop, and have it invoke the stored continuation objects as the data they're waiting for arrives.

If so, that's got to be the nicest use for continuations I've seen! All invisible to the end user. I don't know how to fake it pleasantly without threads, either, and understand that threads aren't appropriate for resource reasons. So I don't have a nice alternative.

It can always be done with threads, but also without. Tried it last night, with proper refcounting, and it wasn't too easy since I had to duplicate the Python frame chain. ...

Suppose the driver were in a script instead:

thing(5) # line 1 print repr(saved) # line 2 saved.throw(0) # line 3 saved.throw(0) # line 4

Then the continuation would (eventually) "return to" the "print repr(saved)" and we'd get an infinite output tail of:

Continuation object at 80d30d0> n== 2 n== 1 n== 0 Done! Continuation object at 80d30d0> n== 2 n== 1 n== 0 Done!

This is at the moment exactly what happens, with the difference that after some repetitions we GPF due to dangling references to too often decref'ed objects. My incref'ing prepares for just one re-incarnation and should prevend a second call. But this will be solved, soon.

and never reach line 4. Right? That's the part that Guido hates <wink>.

Yup. With a little counting, it was easy to survive: def main(): global a a=2 thing (5) a=a-1 if a: saved.throw (0) Weird enough and needs a much better interface. But finally I'm quite happy that it worked so smoothly after just a couple of hours (well, about six :) ciao - chris -- Christian Tismer :^) mailto:tismer@appliedbiometrics.com Applied Biometrics GmbH : Have a break! Take a ride on Python's Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net 10553 Berlin : PGP key -> http://wwwkeys.pgp.net PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF we're tired of banana software - shipped green, ripens at home

Tim Peters wrote:

[Christian Tismer]

...

... Yup. With a little counting, it was easy to survive:

def main(): global a a=2 thing (5) a=a-1 if a: saved.throw (0)

Did "a" really need to be global here? I hope you see the same behavior without the "global a"; e.g., this Scheme:

(Hüstel) Actually, I inserted the "global" later. It worked as well with a local variable, but I didn't understand it. Still don't :-)

Or does brute-force frame-copying cause the continuation to set "a" back to 2 each time?

No, it doesn't. Behavior is exactly the same with or without global. I'm not sure wether this is a bug or a feature. I *think* 'a' as a local has a slot in the frame, so it's actually a different 'a' living in both copies. But this would not have worked. Can it be that before a function call, the interpreter turns its locals into a dict, using fast_to_locals? That would explain it. This is not what I think it should be! Locals need to be copied.

...

and needs a much better interface.

Ya, like screw 'em and use threads <wink>.

Never liked threads. These fibers are so neat since they don't need threads, no locking, and they are available on systems without threads.

...

But finally I'm quite happy that it worked so smoothly after just a couple of hours (well, about six :)

Yup! Playing with Python internals is a treat.

to-be-continued-ly y'rs - tim

throw(42) - chris -- Christian Tismer :^) mailto:tismer@appliedbiometrics.com Applied Biometrics GmbH : Have a break! Take a ride on Python's Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net 10553 Berlin : PGP key -> http://wwwkeys.pgp.net PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF we're tired of banana software - shipped green, ripens at home

[Christian Tismer]

...

...

... Yup. With a little counting, it was easy to survive:

def main(): global a a=2 thing (5) a=a-1 if a: saved.throw (0)

[Tim]

...

Did "a" really need to be global here? I hope you see the same behavior without the "global a"; [which he does, but for mysterious reasons]

[Christian]

Actually, the frame-copying was not enough to make this all behave correctly. Since I didn't change the interpreter, the ceval.c incarnations still had copies to the old frames. The only effect which I achieved with frame copying was that the refcounts were increased correctly.

All right! Now you're closer to the real solution <wink>; i.e., copying wasn't really needed here, but keeping stuff alive was. In Scheme terms, when we entered main originally a set of bindings was created for its locals, and it is that very same set of bindings to which the continuation returns. So the continuation *should* reuse them -- making a copy of the locals is semantically hosed. This is clearer in Scheme because its "stack" holds *only* control-flow info (bindings follow a chain of static links, independent of the current "call stack"), so there's no temptation to run off copying bindings too. elegant-and-baffling-for-the-price-of-one<wink>-ly y'rs - tim

...

...

...

...

"CT" == Christian Tismer writes:

[Tim Peters]

...

This is clearer in Scheme because its "stack" holds *only* control-flow info (bindings follow a chain of static links, independent of the current "call stack"), so there's no temptation to run off copying bindings too.

CT> The Python stack, besides its intermingledness with the machine CT> stack, is basically its chain of frames. The value stack pointer CT> still hides in the machine stack, but that's easy to change. So CT> the real Scheme-like part is this chain, methinks, with the CT> current bytecode offset and value stack info. CT> Making a copy of this in a restartable way means to increase the CT> refcount of all objects in a frame. Would it be correct to undo CT> the effect of fast locals before splitting, and redoing it on CT> activation? Wouldn't it be easier to increase the refcount on the frame object? Then you wouldn't need to worry about the recounts on all the objects in the frame, because they would only be decrefed when the frame is deallocated. It seems like the two other things you would need are some way to get a copy of the current frame and a means to invoke eval_code2 with an already existing stack frame instead of a new one. (This sounds too simple, so it's obviously wrong. I'm just not sure where. Is the problem that you really need a seperate stack/graph to hold the frames? If we leave them on the Python stack, it could be hard to dis-entangle value objects from control objects.) Jeremy

I'm home sick today, so tortured myself <0.9 wink>. Sam mentioned using coroutines to compare the fringes of two trees, and I picked a simpler problem: given a nested list structure, generate the leaf elements one at a time, in left-to-right order. A solution to Sam's problem can be built on that, by getting a generator for each tree and comparing the leaves a pair at a time until there's a difference. Attached are solutions in Icon, Python and Scheme. I have the least experience with Scheme, but browsing around didn't find a better Scheme approach than this. The Python solution is the least satisfactory, using an explicit stack to simulate recursion by hand; if you didn't know the routine's purpose in advance, you'd have a hard time guessing it. The Icon solution is very short and simple, and I'd guess obvious to an average Icon programmer. It uses the subset of Icon ("generators") that doesn't require any C-stack trickery. However, alone of the three, it doesn't create a function that could be explicitly called from several locations to produce "the next" result; Icon's generators are tied into Icon's unique control structures to work their magic, and breaking that connection requires moving to full-blown Icon coroutines. It doesn't need to be that way, though. The Scheme solution was the hardest to write, but is a largely mechanical transformation of a recursive fringe-lister that constructs the entire fringe in one shot. Continuations are used twice: to enable the recursive routine to resume itself where it left off, and to get each leaf value back to the caller. Getting that to work required rebinding non-local identifiers in delicate ways. I doubt the intent would be clear to an average Scheme programmer. So what would this look like in Continuation Python? Note that each place the Scheme says "lambda" or "letrec", it's creating a new lexical scope, and up-level references are very common. Two functions are defined at top level, but seven more at various levels of nesting; the latter can't be pulled up to the top because they refer to vrbls local to the top-level functions. Another (at least initially) discouraging thing to note is that Scheme schemes for hiding the pain of raw call/cc often use Scheme's macro facilities. may-not-be-as-fun-as-it-sounds<wink>-ly y'rs - tim Here's the Icon: procedure main() x := [[1, [[2, 3]]], [4], [], [[[5]], 6]] every writes(fringe(x), " ") write() end procedure fringe(node) if type(node) == "list" then suspend fringe(!node) else suspend node end Here's the Python: from types import ListType class Fringe: def __init__(self, value): self.stack = [(value, 0)] def __getitem__(self, ignored): while 1: # find topmost pending list with something to do while 1: if not self.stack: raise IndexError v, i = self.stack[-1] if i < len(v): break self.stack.pop() this = v[i] self.stack[-1] = (v, i+1) if type(this) is ListType: self.stack.append((this, 0)) else: break return this testcase = [[1, [[2, 3]]], [4], [], [[[5]], 6]] for x in Fringe(testcase): print x, print Here's the Scheme: (define list->generator ; Takes a list as argument. ; Returns a generator g such that each call to g returns ; the next element in the list's symmetric-order fringe. (lambda (x) (letrec {(produce-value #f) ; set to return-to continuation (looper (lambda (x) (cond ((null? x) 'nada) ; ignore null ((list? x) (looper (car x)) (looper (cdr x))) (else ; want to produce this non-list fringe elt, ; and also resume here (call/cc (lambda (here) (set! getnext (lambda () (here 'keep-going))) (produce-value x))))))) (getnext (lambda () (looper x) ; have to signal end of sequence somehow; ; assume false isn't a legitimate fringe elt (produce-value #f)))} ; return niladic function that returns next value (lambda () (call/cc (lambda (k) (set! produce-value k) (getnext))))))) (define display-fringe (lambda (x) (letrec ((g (list->generator x)) (thiselt #f) (looper (lambda () (set! thiselt (g)) (if thiselt (begin (display thiselt) (display " ") (looper)))))) (looper)))) (define test-case '((1 ((2 3))) (4) () (((5)) 6))) (display-fringe test-case)

Cleaning up, clarifying, trying to understand... Tim Peters wrote:

[Christian Tismer]

...

I tried the most simple thing, and this seemed to be duplicating the current state of the machine. The frame holds the stack, and references to all objects. By chance, the locals are not in a dict, but unpacked into the frame. (Sometimes I agree with Guido, that optimization is considered harmful :-)

I don't see that the locals are a problem here -- provided you simply leave them alone <wink>.

This depends on wether I have to duplicate frames or not. Below...

...

The Python stack, besides its intermingledness with the machine stack, is basically its chain of frames.

Right.

...

The value stack pointer still hides in the machine stack, but that's easy to change.

I'm not sure what "value stack" means here, or "machine stack". The latter means the C stack? Then I don't know which values you have in mind that are hiding in it (the locals are, as you say, unpacked in the frame, and the evaluation stack too). By "evaluation stack" I mean specifically f->f_valuestack; the current *top* of stack pointer (specifically stack_pointer) lives in the C stack -- is that what we're talking about?

Exactly!

Whichever, when we're talking about the code, let's use the names the code uses <wink>.

The evaluation stack pointer is a local variable in the C stack and must be written to the frame to become independant from the C stack. Sounds better now?

...

So the real Scheme-like part is this chain, methinks, with the current bytecode offset and value stack info.

Curiously, f->f_lasti is already materialized every time we make a call, in order to support tracing. So if capturing a continuation is done via a function call (hard to see any other way it could be done <wink>), a bytecode offset is already getting saved in the frame object.

You got me. I'm just completing what is partially there.

...

Making a copy of this in a restartable way means to increase the refcount of all objects in a frame.

You later had a vision of splitting the frame into two objects -- I think.

My wrong wording. Not splitting, but duplicting. If a frame is the current state, I make it two frames to have two current states. One will be saved, the other will be run. This is what I call "splitting". Actually, splitting must occour whenever a frame can be reached twice, in order to keep elements alive.

Whichever part the locals live in should not be copied at all, but merely have its (single) refcount increased. The other part hinges on details of your approach I don't know. The nastiest part seems to be f->f_valuestack, which conceptually needs to be (shallow) copied in the current frame and in all other frames reachable from the current frame's continuation (the chain rooted at f->f_back today); that's the sum total (along with the same frames' bytecode offsets) of capturing the control flow state.

Well, I see. You want one locals and one globals, shared by two incarnations. Gets me into trouble.

...

Would it be correct to undo the effect of fast locals before splitting, and redoing it on activation?

Unsure what splitting means, but in any case I can't conceive of a reason for doing anything to the locals. Their values aren't *supposed* to get restored upon continuation invocation, so there's no reason to do anything with their values upon continuation creation either. Right? Or are we talking about different things?

Let me explain. What Python does right now is: When a function is invoked, all local variables are copied into fast_locals, well of course just references are copied and counts increased. These fast locals give a lot of speed today, we must have them. You are saying I have to share locals between frames. Besides that will be a reasonable slowdown, since an extra structure must be built and accessed indirectly (right now, i's all fast, living in the one frame buffer), I cannot say that I'm convinced that this is what we need. Suppose you have a function def f(x): # do something ... # in some context, wanna have a snapshot global snapshot # initialized to None if not snapshot: snapshot = callcc.new() # continue computation x = x+1 ... What I want to achieve is that I can run this again, from my snapshot. But with shared locals, my parameter x of the snapshot would have changed to x+1, which I don't find useful. I want to fix a state of the current frame and still think it should "own" its locals. Globals are borrowed, anyway. Class instances will anyway do what you want, since the local "self" is a mutable object. How do you want to keep computations independent when locals are shared? For me it's just easier to implement and also to think with the shallow copy. Otherwise, where is my private place? Open for becoming convinced, of course :-) ciao - chris -- Christian Tismer :^) mailto:tismer@appliedbiometrics.com Applied Biometrics GmbH : Have a break! Take a ride on Python's Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net 10553 Berlin : PGP key -> http://wwwkeys.pgp.net PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF we're tired of banana software - shipped green, ripens at home

Jeremy Hylton wrote:

...

...

...

...

...

"CT" == Christian Tismer writes:

CT> What I want to achieve is that I can run this again, from my CT> snapshot. But with shared locals, my parameter x of the snapshot CT> would have changed to x+1, which I don't find useful. I want to CT> fix a state of the current frame and still think it should "own" CT> its locals. Globals are borrowed, anyway. Class instances will CT> anyway do what you want, since the local "self" is a mutable CT> object.

CT> How do you want to keep computations independent when locals are CT> shared? For me it's just easier to implement and also to think CT> with the shallow copy. Otherwise, where is my private place? CT> Open for becoming convinced, of course :-)

I think you're making things a lot more complicated by trying to instantiate new variable bindings for locals every time you create a continuation. Can you give an example of why that would be helpful?

I'm not sure wether you all understand me, and vice versa. There is no copying at all, but for the frame. I copy the frame, which means I also incref all the objects which it holds. Done. This is the bare minimum which I must do.

(Ok. I'm not sure I can offer a good example of why it would be helpful to share them, but it makes intuitive sense to me.)

The call_cc mechanism is going to let you capture the current continuation, save it somewhere, and call on it again as often as you like. Would you get a fresh locals each time you used it? or just the first time? If only the first time, it doesn't seem that you've gained a whole lot.

call_cc does a copy of the state which is the frame. This is stored away until it is revived. Nothing else happens. As Guido pointed out, virtually the whole frame chain is duplicated, but only on demand.

Also, all the locals that are references to mutable objects are already effectively shared. So it's only a few oddballs like ints that are an issue.

Simply look at a frame, what it is. What do you need to do to run it again with a given state. You have to preserve the stack variables. And you have to preserve the current locals, since some of them might even have a copy on the stack, and we want to stay consistent. I believe it would become obvious if you tried to implement it. Maybe I should close my ears and get something ready to show? ciao - chris -- Christian Tismer :^) mailto:tismer@appliedbiometrics.com Applied Biometrics GmbH : Have a break! Take a ride on Python's Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net 10553 Berlin : PGP key -> http://wwwkeys.pgp.net PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF we're tired of banana software - shipped green, ripens at home

Tim Peters wrote:

[Christian] [... clarified stuff ... thanks! ... much clearer ...]

But still not clear enough, I fear.

...

... If a frame is the current state, I make it two frames to have two current states. One will be saved, the other will be run. This is what I call "splitting". Actually, splitting must occour whenever a frame can be reached twice, in order to keep elements alive.

That part doesn't compute: if a frame can be reached by more than one path, its refcount must be at least equal to the number of its immediate predecessors, and its refcount won't fall to 0 before it becomes unreachable. So while you may need to split stuff for *some* reasons, I can't see how keeping elements alive could be one of those reasons (unless you're zapping frame contents *before* the frame itself is garbage?).

I was saying that under the side condition that I don't want to change frames as they are now. Maybe that's misconcepted, but this is what I did: If a frame as we have it today shall be resumed twice, then it has to be copied, since: The stack is in it and has some state which will change after resuming. That was the whole problem with my first prototype, which was done hoping that I don't need to change the interpreter at all. Wrong, bad, however. What I actually did was more than seems to be needed: I made a copy of the whole current frame chain. Later on, Guido said this can be done on demand. He's right. [Scheme sample - understood]

GETLOCAL and SETLOCAL simply index off of the fastlocals pointer; it doesn't care where that points *to*

Point taken. The pointer doesn't save time of access, it just saves allocating another structure. So we can use something else without speed loss. [have to cut a little]

So recall your uses of Icon generators instead: like Python, Icon does have loops, and two-level scoping, and I routinely build loopy Icon generators that keep state in locals. Here's a dirt-simple example I emailed to Sam earlier this week:

procedure main() every result := fib(0, 1) \ 10 do write(result) end

procedure fib(i, j) local temp repeat { suspend i temp := i + j i := j j := temp } end

[prints fib series]

If Icon restored the locals (i, j, temp) upon each fib resumption, it would generate a zero followed by an infinite sequence of ones(!).

Now I'm completely missing the point. Why should I want to restore anything? At a suspend, which when done by continuations will be done by temporarily having two identical states, one is saved and another is continued. The continued one in your example just returns the current value and immediately forgets about the locals. The other one is continued later, and of course with the same locals which were active when going asleep.

Think of a continuation as a *paused* computation (which it is) rather than an *independent* one (which it isn't <wink>), and I think it gets darned hard to argue.

No, you get me wrong. I understand what you mean. It is just the decision wether a frame, which will be reactivated later as a continuation, should use a reference to locals like the reference which it has for the globals. This causes me a major frame redesign. Current design: A frame is: back chain, state, code, unpacked locals, globals, stack. Code and globals are shared. State, unpacked locals and stack are private. Possible new design: A frame is: back chain, state, code, variables, globals, stack. variables is: unpacked locals. This makes the variables into an extra structure which is shared. Probably a list would be the thing, or abusing a tuple as a mutable object. Hmm. I think I should get something ready, and we should keep this thread short, or we will loose the rest of Guido's goodwill (if not already). ciao - chris -- Christian Tismer :^) mailto:tismer@appliedbiometrics.com Applied Biometrics GmbH : Have a break! Take a ride on Python's Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net 10553 Berlin : PGP key -> http://wwwkeys.pgp.net PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF we're tired of banana software - shipped green, ripens at home

Sam (& others), I thought I understood what continuations were, but the examples of what you can do with them so far don't clarify the matter at all. Perhaps it would help to explain what a continuation actually does with the run-time environment, instead of giving examples of how to use them and what the result it? Here's a start of my own understanding (brief because I'm on a 28.8k connection which makes my ordinary typing habits in Emacs very painful). 1. All program state is somehow contained in a single execution stack. This includes globals (which are simply name bindings in the botton stack frame). It also includes a code pointer for each stack frame indicating where the function corresponding to that stack frame is executing (this is the return address if there is a newer stack frame, or the current instruction for the newest frame). 2. A continuation does something equivalent to making a copy of the entire execution stack. This can probably be done lazily. There are probably lots of details. I also expect that Scheme's semantic model is different than Python here -- e.g. does it matter whether deep or shallow copies are made? I.e. are there mutable *objects* in Scheme? (I know there are mutable and immutable *name bindings* -- I think.) 3. Calling a continuation probably makes the saved copy of the execution stack the current execution state; I presume there's also a way to pass an extra argument. 4. Coroutines (which I *do* understand) are probably done by swapping between two (or more) continuations. 5. Other control constructs can be done by various manipulations of continuations. I presume that in many situations the saved continuation becomes the main control locus permanently, and the (previously) current stack is simply garbage-collected. Of course the lazy copy makes this efficient. If this all is close enough to the truth, I think that continuations involving C stack frames are definitely out -- as Tim Peters mentioned, you don't know what the stuff on the C stack of extensions refers to. (My guess would be that Scheme implementations assume that any pointers on the C stack point to Scheme objects, so that C stack frames can be copied and conservative GC can be used -- this will never happen in Python.) Continuations involving only Python stack frames might be supported, if we can agree on the the sharing / copying semantics. This is where I don't know enough see questions at #2 above). --Guido van Rossum (home page: http://www.python.org/~guido/)

[GvR]

... Perhaps it would help to explain what a continuation actually does with the run-time environment, instead of giving examples of how to use them and what the result it?

Paul Wilson (the GC guy) has a very nice-- but incomplete --intro to Scheme and its implementation: ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html You can pick up a lot from that fast. Is Steven (Majewski) on this list? He doped most of this out years ago.

Here's a start of my own understanding (brief because I'm on a 28.8k connection which makes my ordinary typing habits in Emacs very painful).

1. All program state is somehow contained in a single execution stack. This includes globals (which are simply name bindings in the botton stack frame).

Better to think of name resolution following lexical links. Lexical closures with indefinite extent are common in Scheme, so much so that name resolution is (at least conceptually) best viewed as distinct from execution stacks. Here's a key: continuations are entirely about capturing control flow state, and nothing about capturing binding or data state. Indeed, mutating bindings and/or non-local data are the ways distinct invocations of a continuation communicate with each other, and for this reason true functional languages generally don't support continuations of the call/cc flavor.

It also includes a code pointer for each stack frame indicating where the function corresponding to that stack frame is executing (this is the return address if there is a newer stack frame, or the current instruction for the newest frame).

Yes, although the return address is one piece of information in the current frame's continuation object -- continuations are used internally for "regular calls" too. When a function returns, it passes control thru its continuation object. That process restores-- from the continuation object --what the caller needs to know (in concept: a pointer to *its* continuation object, its PC, its name-resolution chain pointer, and its local eval stack). Another key point: a continuation object is immutable.

2. A continuation does something equivalent to making a copy of the entire execution stack. This can probably be done lazily. There are probably lots of details.

The point of the above is to get across that for Scheme-calling-Scheme, creating a continuation object copies just a small, fixed number of pointers (the current continuation pointer, the current name-resolution chain pointer, the PC), plus the local eval stack. This is for a "stackless" interpreter that heap-allocates name-mapping and execution-frame and continuation objects. Half the literature is devoted to optimizing one or more of those away in special cases (e.g., for continuations provably "up-level", using a stack + setjmp/longjmp instead).

I also expect that Scheme's semantic model is different than Python here -- e.g. does it matter whether deep or shallow copies are made? I.e. are there mutable *objects* in Scheme? (I know there are mutable and immutable *name bindings* -- I think.)

Same as Python here; Scheme isn't a functional language; has mutable bindings and mutable objects; any copies needed should be shallow, since it's "a feature" that invoking a continuation doesn't restore bindings or object values (see above re communication).

3. Calling a continuation probably makes the saved copy of the execution stack the current execution state; I presume there's also a way to pass an extra argument.

Right, except "stack" is the wrong mental model in the presence of continuations; it's a general rooted graph (A calls B, B saves a continuation pointing back to A, B goes on to call A, A saves a continuation pointing back to B, etc). If the explicitly saved continuations are never *invoked*, control will eventually pop back to the root of the graph, so in that sense there's *a* stack implicit at any given moment.

4. Coroutines (which I *do* understand) are probably done by swapping between two (or more) continuations.

5. Other control constructs can be done by various manipulations of continuations. I presume that in many situations the saved continuation becomes the main control locus permanently, and the (previously) current stack is simply garbage-collected. Of course the lazy copy makes this efficient.

There's much less copying going on in Scheme-to-Scheme than you might think; other than that, right on.

If this all is close enough to the truth, I think that continuations involving C stack frames are definitely out -- as Tim Peters mentioned, you don't know what the stuff on the C stack of extensions refers to. (My guess would be that Scheme implementations assume that any pointers on the C stack point to Scheme objects, so that C stack frames can be copied and conservative GC can be used -- this will never happen in Python.)

"Scheme" has become a generic term covering dozens of implementations with varying semantics, and a quick tour of the web suggests that cross-language Schemes generally put severe restrictions on continuations across language boundaries. Most popular seems to be to outlaw them by decree.

Continuations involving only Python stack frames might be supported, if we can agree on the the sharing / copying semantics. This is where I don't know enough see questions at #2 above).

I'd like to go back to examples of what they'd be used for <wink> -- but fully fleshed out. In the absence of Scheme's ubiquitous lexical closures and "lambdaness" and syntax-extension facilities, I'm unsure they're going to work out reasonably in Python practice; it's not enough that they can be very useful in Scheme, and Sam is highly motivated to go to extremes here. give-me-a-womb-and-i-still-won't-give-birth-ly y'rs - tim

[Christian Tismer]

I've put quite many hours into a non-recursive ceval.c already.

Does that mean 6 or 600 <wink>?

Should I continue? At least this would be a little improvement, also if the continuation thing will not be born. ?

Guido wanted to move in the "flat interpreter" direction for Python2 anyway, so my belief is it's worth pursuing. but-then-i-flipped-a-coin-with-two-heads-ly y'rs - tim

I think it makes sense to avoid being obscure or unclear in order to minimize the size of the patch or the diff. Realistically, it's unlikely that anything like your original patch is going to make it into the CVS tree. It's primary value is as proof of concept and as code that the rest of us can try out. If you make large changes, but they are clearer, you'll help us out a lot. We can worry about minimizing the impact of the changes on the codebase after, after everyone has figured out what's going on and agree that its worth doing. feeling-much-more-confident-because-I-didn't-say-continuation-ly yr's, Jeremy

[Sam]

...

...

Continuations are more powerful than coroutines, though I admit they're a bit esoteric.

[Tim]

...

"More powerful" is a tedious argument you should always avoid <wink>.

[Sam]

More powerful in the sense that you can use continuations to build lots of different control structures (coroutines, backtracking, exceptions), but not vice versa.

"More powerful" is a tedious argument you should always avoid .

...

Then the continuation would (eventually) "return to" the "print repr(saved)" and we'd get an infinite output tail [...] and never reach line 4. Right?

Yes... the continuation object so far isn't very usable.

But it's proper behavior for a continuation all the same! So this aspect shouldn't be "fixed".

... let/cc stores the continuation in a variable binding, while introducing a new scope. It requires a change to the underlying language:

Isn't this often implemented via a macro, though, so that (let/cc name code) "acts like" (call/cc (lambda (name) code)) ? I haven't used a Scheme with native let/cc, but poking around it appears that the real intent is to support exception-style function exits with a mechanism cheaper than 1st-class continuations: twice saw the let/cc object (the thingie bound to "name") defined as being invalid the instant after "code" returns, so it's an "up the call stack" gimmick. That doesn't sound powerful enough for what you're after.

[nice let/cc call/cc tutorialette] ... In order to do useful work like passing values back and forth between coroutines, we have to have some way of returning a value from the continuation when it is reinvoked.

Somehow, I suspect that's the least of our problems <0.5 wink>. If continuations are in Python's future, though, I agree with the need as stated.

I should emphasize that most folks will never see call/cc 'in the raw', it will usually have some nice wrapper around to implement whatever construct is needed.

Python already has well-developed exception and thread facilities, so it's hard to make a case for continuations as a catch-all implementation mechanism. That may be the rub here: while any number of things *can* be implementated via continuations, I think very few *need* to be implemented that way, and full-blown continuations aren't easy to implement efficiently & portably. The Icon language was particularly concerned with backtracking searches, and came up with generators as another clearer/cheaper implementation technique. When it went on to full-blown coroutines, it's hard to say whether continuations would have been a better approach. But the coroutine implementation it has is sluggish and buggy and hard to port, so I doubt they could have done noticeably worse. Would full-blown coroutines be powerful enough for your needs? assuming-the-practical-defn-of-"powerful-enough"-ly y'rs - tim

[Sam]

... Except that since the escape procedure is 'first-class' it can be stored away and invoked (and reinvoked) later. [that's all that 'first-class' means: a thing that can be stored in a variable, returned from a function, used as an argument, etc..]

I've never seen a let/cc that wasn't full-blown, but it wouldn't surprise me.

The let/cc's in question were specifically defined to create continuations valid only during let/cc's dynamic extent, so that, sure, you could store them away, but trying to invoke one later could be an error. It's in that sense I meant they weren't "first class". Other flavors of Scheme appear to call this concept "weak continuation", and use a different verb to invoke it (like call-with-escaping-continuation, or call/ec). Suspect the let/cc oddballs I found were simply confused implementations (there are a lot of amateur Scheme implementations out there!).

...

Would full-blown coroutines be powerful enough for your needs?

Yes, I think they would be. But I think with Python it's going to be just about as hard, either way.

Most people on this list are comfortable with coroutines already because they already understand them -- Jeremy can even reach across the hall and hand Guido a helpful book <wink>. So pondering coroutines increase the number of brain cells willing to think about the implementation. continuation-examples-leave-people-still-going-"huh?"-after-an- hour-of-explanation-ly y'rs - tim