Mailing List Archive

>>>>> "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

Jeremy Hylton:

> 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.

If i understand what you mean by state machine programming, it's pretty
inherently uncompartmented, all the combinations of state variables need
to be accounted for, so the number of states grows factorially on the
number of state vars, in general it's awkward. The advantage of going
with what functional folks come up with, like continuations, is that it
tends to be well compartmented - functional. (Come to think of it, i
suppose that compartmentalization as opposed to state is their mania.)

As abstract as i can be (because i hardly know what i'm talking about)
(but i have done some specifically finite state machine programming, and
did not enjoy it),

Ken
klm@digicool.com

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

Aaron Watters writes:
> Frankly, I think I thought I understood this once but now I know I
> don't.

8^) That's what I said when I backed into the idea via medusa a
couple of years ago.

> How're continuations more powerful than coroutines? And why can't
> they be implemented using threads (and semaphores etc)?

My understanding of the original 'coroutine' (from Pascal?) was that
it allows two procedures to 'resume' each other. The classic
coroutine example is the 'samefringe' problem: given two trees of
differing structure, are they equal in the sense that a traversal of
the leaves results in the same list? Coroutines let you do this
efficiently, comparing leaf-by-leaf without storing the whole tree.

continuations can do coroutines, but can also be used to implement
backtracking, exceptions, threads... probably other stuff I've never
heard of or needed.

The reason that Scheme and ML are such big fans of continuations is
because they can be used to implement all these other features. Look
at how much try/except and threads complicate other language
implementations. It's like a super-tool-widget - if you make sure
it's in your toolbox, you can use it to build your circular saw and
lathe from scratch.

Unfortunately there aren't many good sites on the web with good
explanatory material. The best reference I have is "Essentials of
Programming Languages". For those that want to play with some of
these ideas using little VM's written in Python:

http://www.nightmare.com/software.html#EOPL

-Sam

Jeremy Hylton writes:
> 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.

For simple problems, state machines are ideal. Medusa uses state
machines that are built out of Python methods. But past a certain
level of complexity, they get too hairy to understand. A really good
example can be found in /usr/src/linux/net/ipv4. 8^)

-Sam

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