Coroutines

[Dustin Laurence <dustin at laurences dot net>]

I'm pretty sure this is stepping into deep quicksand, but I'll ask
anyway...I'm interested in writing an FE for a language that has
stackable coroutines (Lua-style, where you can yield and resume
arbitrarily far down the call stack).  I'm trying to wrap my head around
what would be involve and how awful it would be.

There are a few "coroutines in C" packages packages laying around, but
they don't seem to be stackable (I'm sure the ones based on Duff's
device aren't).  Since you can't switch call stacks from C I think what
I want is impossible at that level.  So I'd appreciate any comments or
info on the following possibilities, or any others I didn't think of:

1. Build with pthreads.  This has to be doable and even straightforward,
but it seems like full threading machinery is very heavyweight for this.
Most coroutines are conceptually a strictly user-space control structure
and would be much faster implemented that way.  Also, that would make
the FE depend on pthreads, which I bet is undesirable.

2. Build with a purely user-space threads package.  This ought to
eliminate a bunch of locking and context switching overhead, so it seems
like a plausible idea.  But it may still be too general and in any case
it has the disadvantage of importing the package into GCC itself when I
get to building the FE.

3. Non-portable library.  Perhaps yield() and friends can be made to
work with a bit of in-line assembly to set and restore the stack pointer
and registers to/from a chunk of heap (obtained with malloc or mmap I
guess, if you can get the right access bits).  This seems plausible, but
it has the disadvantage of requiring an implementation for every
architecture.  Nasty for a GCC FE if avoidable, unless it made it into
glibc (seems unlikely).  (For a few seconds it seems like longjmp()
hackery would be sufficient, but you oughtn't think about jumping back
down the stack with longjmp() and you still haven't answered the
question of how you're going to allow the caller to call other functions
and coroutines in between resume() calls.)

4. GCC extension.  Perhaps there is a way to do this in RTL, I just
don't know nearly enough to say.  If so, then the non-portable code is
confined to things that already have to be maintained.  It also would
allow fully stackable C coroutines as a GCC extension, though I don't
know if anyone but me would care about such a thing.  Perhaps the
absence of such an extension is a subtle hint of how deep that quicksand
is. :-)  OTOH if it is possible I'd consider trying to write it, if my
GCC-fu ever reaches the requisite level (my rank is somewhere below
"pale piece of pigs ear" right now).

Any enlightenment is most welcome, even if only to tell me what a stupid
idea it is. :-)

Dustin

Attachment: pgp00000.pgp
Description: PGP signature