Re: C coroutines in ANSI C

[Dave Dodge <dododge@...>]

On Wed, Aug 03, 2005 at 09:07:27PM +0200, Mike Pall wrote:
> Luiz Henrique de Figueiredo wrote:
> > I found what seems to be an implementation of C coroutines in ANSI C:
> > 	http://www.sics.se/~adam/pt/index.html

>From a glance at the examples, the main problem that sticks out is
that all of the variables have to be static.  Note that even local
loop counters within the functions are static.  I think this is
because the library has no way of actually saving/restoring stack
data.  This means that none of the coroutine functions are reentrant,
so for example you can't start two coroutines in parallel using the
same function.  It'll work only for situations where each coroutine is
unique.

> This goes back to a two decades old invention called
> "Duff's device", wrapped into a few macros (look at
> lc-switch.h). In C it's legal to mix a switch statement
> with other control-flow changing statements.
[...]
> The real problem is elsewhere. You need to store the context
> somewhere and retrieve it on resume. You need to figure out
> stack rewinding in case you want to be able to resume more
> than one stack level (I bet you don't want to write your whole
> program in one function?).

A generic approach would be a C-to-C translator.  Basically you add
something like a "resumable" function-specifier to the C grammar,
and perhaps a "yield" keyword, so that you can do things like this:

  resumable int foo(int a,int b)
  {
    int x = bar(a)
    yield;
    int y = bar(b)
    return x + y;
  }

Then a translator takes this and rewrites foo() into proper C
(probably several functions) that uses Duff-style jumps or goto
statements.  In addition, it takes all of the values that need to be
preserved across a resume operation and moves them into a state
structure which is passed into the function whenever it is resumed.

This also has to handle resumed subfunctions.  For example the
translator has to know whether "bar" is also resumable, because
calling a resumable function may require several steps, and if bar
yields, foo needs to return a yield status immediately and then jump
right back into bar when it's resumed.

You'd get something like:

  typedef struct{
    /* y can still be a local variable */
    int a,b,x;
    int returnvalue;

    /* where to jump into foo when resuming */
    int resumeposition;         

    /* assuming bar is resumable, the state of bar when it has yielded */
    void * nextsubfunctionstate;
  }STATE_foo;

  /* set up a state for invoking foo */
  STATE_foo * SETUP_foo(int a,int b) { ... create a new state ... }

  /* resume foo */
  resume_status_t RESUME_foo(STATE_foo * s)
  {
     ... very nasty and mostly unreadable C code ...
  }

  /* gets the final return value from foo and deallocates the state */
  int FINISH_foo(STATE_foo *) { ... }

You might need to limit the incoming C code to certain features, for
example if the code to be translated depends on preprocessor
interaction that could be difficult.  There are interesting cases such
as multiple scopes in the same function using the same variable names.
If scopes are parallel (for example if/then clauses), then you can use
a union to keep the amount of overall state data small.  And so on.

I was looking at this exact problem a few weeks ago before deciding
that I could probably do without C coroutines after all, and save
myself the headache of writing that translator.

I did come across a paper where someone did something very similar:

  http://www.cs.berkeley.edu/~billm/paper-callcc.pdf
  http://www.cs.berkeley.edu/~billm/presentation-callcc.ppt

I think the paper mentions some performance problems with this
approach, though.  I wouldn't be too surprised, since local variables
stored in the state structure will require a more indirection to get
to them.  The generator would have to be pretty smart, for example
only saving variables into the resume state structure when absolutely
necessary.

The advantage is that the resulting code can be pure ANSI C; no real
stack context switching is required.

                                                  -Dave Dodge