coroutines vs. continuations vs. threads
The illustrious Sam Rushing avers:
Continuations are more powerful than coroutines, though I admit they're a bit esoteric. I programmed in Scheme for years without seeing the need for them. But when you need 'em, you *really* need 'em. No way around it.
Frankly, I think I thought I understood this once but now I know I don't. How're continuations more powerful than coroutines? And why can't they be implemented using threads (and semaphores etc)? ...I'm not promising I'll understand the answer... -- Aaron Watters === I taught I taw a putty-cat!
"AW" == Aaron Watters <arw@ifu.net> writes:
AW> The illustrious Sam Rushing avers:
Continuations are more powerful than coroutines, though I admit they're a bit esoteric. I programmed in Scheme for years without seeing the need for them. But when you need 'em, you *really* need 'em. No way around it.
AW> Frankly, I think I thought I understood this once but now I know AW> I don't. How're continuations more powerful than coroutines? AW> And why can't they be implemented using threads (and semaphores AW> etc)? I think I understood, too. I'm hoping that someone will debug my answer and enlighten us both. A continuation is a mechanism for making control flow explicit. A continuation is a means of naming and manipulating "the rest of the program." In Scheme terms, the continuation is the function that the value of the current expression should be passed to. The call/cc mechanisms lets you capture the current continuation and explicitly call on it. The most typical use of call/cc is non-local exits, but it gives you incredible flexibility for implementing your control flow. I'm fuzzy on coroutines, as I've only seen them in "Structure Programming" (which is as old as I am :-) and never actually used them. The basic idea is that when a coroutine calls another coroutine, control is transfered to the second coroutine at the point at which it last left off (by itself calling another coroutine or by detaching, which returns control to the lexically enclosing scope). It seems to me that coroutines are an example of the kind of control structure that you could build with continuations. It's not clear that the reverse is true. I have to admit that I'm a bit unclear on the motivation for all this. As Gordon said, the state machine approach seems like it would be a good approach. Jeremy
The estimable Aaron Watters queries:
The illustrious Sam Rushing avers:
Continuations are more powerful than coroutines, though I admit they're a bit esoteric. I programmed in Scheme for years without seeing the need for them. But when you need 'em, you *really* need 'em. No way around it.
Frankly, I think I thought I understood this once but now I know I don't. How're continuations more powerful than coroutines? And why can't they be implemented using threads (and semaphores etc)?
I think Sam's (immediate <wink>) problem is that he can't afford threads - he may have hundreds to thousands of these suckers. As a fuddy-duddy old imperative programmer, I'm inclined to think "state machine". But I'd guess that functional-ophiles probably see that as inelegant. (Safe guess - they see _anything_ that isn't functional as inelegant!). crude-but-not-rude-ly y'rs - Gordon
The ineffible Gordon McMillan retorts:
As a fuddy-duddy old imperative programmer, I'm inclined to think "state machine". But I'd guess that functional-ophiles probably see that as inelegant. (Safe guess - they see _anything_ that isn't functional as inelegant!).
As a fellow fuddy-duddy I'd agree except that if you write properlylayered software you have to unrole and rerole all those layers for every transition of the multi-level state machine, and even though with proper discipline it can be implemented without becoming hideous, it still adds significant overhead compared to "stop right here and come back later" which could be implemented using threads/coroutines(?)/continuations. I think this is particularly true in Python with the relatively high function call overhead. Or maybe I'm out in left field doing cartwheels... I guess the question of interest is why are threads insufficient? I guess they have system limitations on the number of threads or other limitations that wouldn't be a problem with continuations? If there aren't a *lot* of situations where coroutines are vital, I'd be hesitant to do major surgery. But I'm a fuddy-duddy. -- Aaron Watters === I did! I did!
Aaron Watters wrote:
The ineffible Gordon McMillan retorts:
As a fuddy-duddy old imperative programmer, I'm inclined to think "state machine". But I'd guess that functional-ophiles probably see that as inelegant. (Safe guess - they see _anything_ that isn't functional as inelegant!).
As a fellow fuddy-duddy I'd agree except that if you write properlylayered software you have to unrole and rerole all those layers for every transition of the multi-level state machine, and even though with proper discipline it can be implemented without becoming hideous, it still adds significant overhead compared to "stop right here and come back later" which could be implemented using threads/coroutines(?)/continuations.
Coroutines are most elegant here, since (fir a simple example) they are a symmetric pair of functions which call each other. There is neither the one-pulls, the other pushes asymmetry, nor the need to maintain state and be controlled by a supervisor function.
I think this is particularly true in Python with the relatively high function call overhead. Or maybe I'm out in left field doing cartwheels... I guess the question of interest is why are threads insufficient? I guess they have system limitations on the number of threads or other limitations that wouldn't be a problem with continuations? If there aren't a *lot* of situations where coroutines are vital, I'd be hesitant to do major surgery.
For me (as always) most interesting is the possible speed of coroutines. They involve no threads overhead, no locking, no nothing. Python supports it better than expected. If the stack level of two code objects is the same at a switching point, the whole switch is nothing more than swapping two frame objects, and we're done. This might be even cheaper than general call/cc, like a function call. Sam's prototype works already, with no change to the interpreter (but knowledge of Python frames, and a .dll of course). I think we'll continue a while. continuously - 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
Co-Christian-routines Tismer continues:
Aaron Watters wrote:
The ineffible Gordon McMillan retorts:
As a fuddy-duddy old imperative programmer, I'm inclined to think "state machine". But I'd guess that functional-ophiles probably see that as inelegant. (Safe guess - they see _anything_ that isn't functional as inelegant!).
As a fellow fuddy-duddy I'd agree except that if you write properlylayered software you have to unrole and rerole all those layers for every transition of the multi-level state machine, and even though with proper discipline it can be implemented without becoming hideous, it still adds significant overhead compared to "stop right here and come back later" which could be implemented using threads/coroutines(?)/continuations.
Coroutines are most elegant here, since (fir a simple example) they are a symmetric pair of functions which call each other. There is neither the one-pulls, the other pushes asymmetry, nor the need to maintain state and be controlled by a supervisor function.
Well, the state maintains you, instead of the other way 'round. (Any other ex-Big-Blue-ers out there that used to play these games with checkpoint and SyncSort?). I won't argue elegance. Just a couple points: - there's an art to writing state machines which is largely unrecognized (most of them are unnecessarily horrid). - a multiplexed solution (vs a threaded solution) requires that something be inside out. In one case it's your code, in the other, your understanding of the problem. Neither is trivial. Not to be discouraging - as long as your solution doesn't involve using regexps on bytecode <wink>, I say go for it! - Gordon
[Aaron Watters]
... I guess the question of interest is why are threads insufficient? I guess they have system limitations on the number of threads or other limitations that wouldn't be a problem with continuations?
Sam is mucking with thousands of simultaneous I/O-bound socket connections, and makes a good case that threads simply don't fly here (each one consumes a stack, kernel resources, etc). It's unclear (to me) that thousands of continuations would be *much* better, though, by the time Christian gets done making thousands of copies of the Python stack chain.
If there aren't a *lot* of situations where coroutines are vital, I'd be hesitant to do major surgery. But I'm a fuddy-duddy.
Go to Sam's site (http://www.nightmare.com/), download Medusa, and read the docs. They're very well written and describe the problem space exquisitely. I don't have any problems like that I need to solve, but it's interesting to ponder! alas-no-time-for-it-now-ly y'rs - tim
Tim Peters wrote:
[Aaron Watters]
... I guess the question of interest is why are threads insufficient? I guess they have system limitations on the number of threads or other limitations that wouldn't be a problem with continuations?
Sam is mucking with thousands of simultaneous I/O-bound socket connections, and makes a good case that threads simply don't fly here (each one consumes a stack, kernel resources, etc). It's unclear (to me) that thousands of continuations would be *much* better, though, by the time Christian gets done making thousands of copies of the Python stack chain.
Well, what he needs here are coroutines and just a single frame object for every minithread (I think this is a "fiber"?). If these fibers later do deep function calls before they switch, there will of course be more frames then. -- 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
participants (5)
-
Aaron Watters -
Christian Tismer -
Gordon McMillan -
Jeremy Hylton -
Tim Peters