April 21, 2010
Lessons I should have learned, Episode 4: Coroutines in C
A while ago, I read this article on coroutines in C. One of the main downfalls of this technique is that since it uses the static keyword, it makes it much harder to write recursive coroutines, and nigh-impossible to have multiple coroutines using the same function.
Examples
Let’s first look at an example of how it can work. One way of efficiently computing Fibonacci numbers in a language like Haskell is to construct an infinite list of the Fibonacci values.
fibs a b = a : fibs b (a+b)
Since Haskell is lazily evaluated, such an infinite list is fine until you attempt to compute the whole thing. So, as long as you just say something like take 10 $ fibs 1 1 it will only compute how many you need.
One important use of Coroutines is as iterators. Consider the Haskell example from above. If we assume that we have such an infinite list of values, we may want to iterate over the list, inspecting the values as we go. The following C code achieves this using some helper macros we’ll describe below.
int fibs(int a, int b, CoroutineState *s) {
initializeCoroutineState(s, FibState, mystate);
mystate->a = a;
mystate->b = b;
yield(s,mystate->a);
recur (s,fibs(mystate->b, mystate->a + mystate->b, s->next));
finalizeCoroutine(s);
return 0;
}
Now, if we wanted to print out the first 10 of these values:
s = createCoroutineState();
for(i = 0; i < 10; i++) {
printf("%d ", fibs(1,1,s));
}
The yield method is similar to Python's yield key word. It returns a value, but also records where the yield was called so that the next time the function is executed it can begin again from that point.
Another example of how coroutines can be used as iterators is as iterators over a binary tree. Consider the following tree:
4 2 6 1 3 5 7
A standard way to traverse this tree is a post-order traversal. Consider the following code which traverses this tree and prints it out:
void print(Tree *t) {
if(t->left)
print(t->left);
if(t->right)
print(t->right);
printf("%d ", t->value);
}
Building a post-order iterator is slightly more complex. It involves creating a stack and pushing wrapped tree-nodes onto the stack. When one is popped, it is marked as 'visited' and then pushed onto the stack, followed by its right child then left child. However, we can use coroutines to achieve the same thing while staying true to the original traversal code:
int treePostOrderIterator(Tree *t, CoroutineState *s) {
initializeCoroutineState(s,TreeIteratorState, mystate);
mystate->tree = t;
if(mystate->tree->left)
recur (s, treePostOrderIterator(mystate->tree->left, s->next));
if(mystate->tree->right)
recur (s, treePostOrderIterator(mystate->tree->right, s->next));
yield (s,mystate->tree->value);
finalizeCoroutine(s);
return 0;
}
How it works
When I was learning to program, I learned that switch statements were just conditional structures that were equivalent to a series of if statements. While you can almost always get away with thinking about them this way, they aren't actually. Instead, think of switch statements as parameterized gotos. One of the less objectionable uses of goto is as a means of breaking out of nested loops. So, obviously goto can jump out of scopes. In fact, it can be used to jump into and out of any scope inside of a single function. The same is true of the cases of a switch statement. This is what makes Duff's device possible.
In order to facilitate recursion and having multiple coroutines running at once, we need to pass a mutable state parameter. This is an object of type struct CoroutineState.
typedef struct CoroutineState CoroutineState;
struct CoroutineState {
void *state; /* Pointer to a struct representing the internal state
of the coroutine. We need this since we have to
reinstate the scope whenever the function is
re-intered. */
long current; /* The line number of where the coroutine should
return. Used in 'yield' and 'recur' */
unsigned char done; /* A marker to show that a recurrence is completed */
CoroutineState *next; /* The next in the stack of states */
CoroutineState *parent; /* NULL if actually the parent, pointer otherwise */
CoroutineState *tail; /* Only the parent is guaranteed to know the tail */
};
Basically this struct stores everything needed to reinstate the coroutine when it is next called. This includes the line number it should begin executing on, a pointer to the user's saved values, and a stack containing the recursive calls.
Every coroutine begins with an invocation of the initializeCoroutineState macro. This is a macro that takes three parameters. The first is a CoroutineState object, the second is the type defining the user's saved values, and the last is the variable name to use to refer to this state.
#define initializeCoroutineState(coroutineState, UserStateType, userStateVar) \
UserStateType *userStateVar = (UserStateType*) coroutineState->state; \
switch(coroutineState->current) { \
case 0: \
if(coroutineState->state == 0) { \
coroutineState->state = (void*) malloc(sizeof (UserStateType)); \
bzero(coroutineState->state, sizeof(UserStateType)); \
} \
userStateVar = (UserStateType*) coroutineState->state; \
Note that there is a switch statement embedded here. This switch statement jumps to the appropriate line in the execution.
Every coroutine ends with finalizeCoroutine(s) which indicates that after this point the execution of the function should proceed normally. It also says that when this function returns that the coroutine is complete and should be removed from the stack. This is indicated internally with s->done =1;.
#define finalizeCoroutine(s) \ } \ s->done = 1; \ free(s->next); \ s->next = 0;
Now, to the meat of the matter. yield needs to return the value the user wants to yield, but also record where this occurred so that the switch statement from above will jump to here. It also needs to reinstate any variables that the user had in scope. Unfortunately there's no good way of doing that in C, so we have to do it manually. Thus the need for the helper struct. Before the return in the following macro, we're just manipulating the stack so that we can record where we are. Notice coroutineState->current = __LINE__;. __LINE__ is a macro that evaluates to the current line number in the program. So, here we're recording the line number and then after the return, we have case __LINE__:. This will cause the coroutine to begin executing after the return the next time it's called.
#define yield(coroutineState, value) \
do{ \
CoroutineState *parent = coroutineState ? coroutineState \
: coroutineState->parent; \
coroutineState->current = __LINE__; \
parent->tail = coroutineState; \
free(coroutineState->next); \
coroutineState->next = 0; \
return value; \
case __LINE__: 1; \
} while(0)
The last macro is perhaps the most interesting. It's the one that allows things like the infinite list iterator and the binary tree iterator. Basically, there are times when you want to have a recursive call and have the coroutine state stored along with having a return value bubble up.
The while loop is responsible for executing until the coroutine called below it is completed.
#define recur(coroutineState,func) \
do{ \
CoroutineState *parent = coroutineState ? coroutineState \
: coroutineState->parent; \
coroutineState->next = createCoroutineState(); \
coroutineState->next->parent = parent; \
parent->tail = coroutineState->next; \
while(!coroutineState->next->done) { \
CoroutineState *parent = coroutineState ? coroutineState \
: coroutineState->parent; \
typeof(func) tmp = func; \
coroutineState->current = __LINE__; \
if(!parent->tail->done) \
return tmp; \
case __LINE__: 1; \
} \
} while(0) \
Using it
In order to get this to work, you have to do one extra thing. You need to create a struct which you use to store your state rather than use local-variables in your functions. This is necessary since we'll be re-entering the functions later and that state would be lost. So, just put all the variables you would want to use into the struct. Then use this struct in the initializeCoroutineState and then whenever you use a local variable.
If you would normally return a computed value (not the result of a recursive call) then just say yield (value); If you are doing a recursive call and intend for the coroutine to proceed down the recurrence, just wrap it in a recur(s, yourRecursiveCall()).
Get it
I've posted the implementation as a library on GitHub: http://github.com/nathanwiegand/coroutines.
