Co-Routine Refactoring

Co-Routine Refactoring

Say that you are given an arbitrary function in C code that typically runs in a blink of an eye and returns a value, and you need to be able to run it incrementally or partially for some reason.  And you want to do this without making large structural changes to the original function.  You could be implementing concurrency in a single thread, stepping through the function, implementing a generator, or making a generalization of a generator such as a symmetric co-routine.

int fun(int a, int b, int c)
{
  int d=0;
  int e=42;
  int f=2;
  int i=0;

A:

  foo(&d, &e, &f, &i);
B:
  for(i=0;i<10 font="font" i="i">
  {
    int g;
C:
    bar(&d, &e, &f, &i);

    baz(&g);
D:
  }
E:
  buxx(&d, &e);
F:
}

So this is our original function.  We want to be able to stop and inspect it at the points that are labeled.  If we want to be able to exit at D and resume at D by just calling fun, then we would have to live with the restriction that foo can't depend on anything that gets modified in the loop.  Eventually, this restriction is likely to get violated if this is a complex function and the transformation will have to be done anyhow.

The first part of this transformation is to pack all local variables and parameters into a structure to completely save the state of where we are:

struct fun_task {
  int a,b,c,d,e,f,g,i;
};

The next step is to figure out a state machine that gives us the stopping points that we need.  We can inspect fun_task at this point, which happens to be every single piece of state that is going on in this function:

//A steppable version of our previous function, 
// where you can use the source of this function
// as documentation on how to drive the 
// lower level set of functions:
int fun(a,b,c)
{
  int ret;
  int done=0;
  fun_task t;
  fun_init(a,b,c,&t);  //Up to A:
  do {
    //fun_loopBody decides what to 
    //do next based on its internal state.
    //it could be an FSM or more typical code, etc.
    done = fun_loopBody(&t); //C to D
  }while (!done);
  ret = fun_end(&t); //E to F
  return ret;
}

So, the single function fun is replaced with a bunch of functions that trace the life of the fun_task.  Where this gets interesting is when you add more parameters to the task functions.  If you add a parameter to loopBody called is_printable, and add debugging statements conditional on this parameter, then is_printable can vary per iteration rather than having to be the same after each iteration.  loopBody can *set* variables on each iteration as well.  So, this really is a co-routine with the ability to yield with parameters, resume with parameters, and to even let the caller inspect and manipulate state.  One tedious task that has to be dealt with because there is no language support for restoring context (ie: autos and parameters), is that these little functions reference the context like this:

  bool fun_loopBody(fun_task* t)
  {
    bar(&(t->d), &(t->e), &(t->f), &(t->i));
    baz(&(t->g));    
    int done = !((t->i) < 10);
    i++;
    return done;
  }

There is no construct in C to pass in a parameter to bind a struct to the autos like this fictitious item:

bool fun_loopBody[fun_task]()
{
  bar(&d,&e,...);
  ...
}

So we end up doing it manually as above.  Also note that yet another approach to this would be to mark the function somehow to automatically generate the function prototypes for stepping through the task, so that the original code can continue to look like a simple function.  (That would mean that you would also have to mark it up with parameters for yielding and resuming as well at these points)

OOP Digression and State Machines

Notice that this is kind of similar to OOP, in the sense that all state for this task is created inside of a struct and used for the duration.  The fun_* methods would just be methods in that case.  But there is a huge difference in that the methods have a very definite legal grammar on their calling order, and this aspect of these methods is far more important than any of the other aspects of OOP.  In fact, the type system can be used to document this order by taking a different perspective on OOP.  The first thing would be to separate the idea of the type of the state object from the set of methods that are allowed.  Conceptually, the id of the object (its pointer) would stay the same, though the interface would change based on what state it's in.  Ie:

//FlushedFile can only read/write/close
FlushedFile f = File("/etc/passwd").open();

//We can't close until it's flushed 
//- notice that the type *changed*
UnflushedFile f = f.read(&buffer);
//f.close() isn't available until it becomes a flushed file

FlushedFile f = f.flush();
f.close();

So, this concept is called "Protocols" in languages that implement it, like Sing#.  In Erlang, message passing order is probably the most important thing to document, which is why they don't think too much about type safety beyond preserving the integrity of the run-time system.  Anyways, it either passes around state from object to object when implemented as OO, or changes available methods based on known state (or possible states known at compile-time) if that is supported.

A major problem with the OO way of thinking is that the type system generally only documents what the function signatures are.  It's even more messed up when the concept of 'messages' gets warped in a concurrent context (where the messages should behave like an incoming mailbox like Erlang where work happens inside the object in a way that looks single-threaded to the object, rather than executing in the caller's thread like C/Java do).  But in any case, the concept of messages is the most important thing to get right, and it's basically neglected.  Beyond constructors and destructors, it's quite a rare thing for the type system to provide good hints as to the intended calling (messaging) order.  But a well defined specification should at least do these things:

• Document exactly what the object requires, generally through dependency injection where real dependencies are just on interfaces.
• Document legal calling orders (messages) that imposes enough constraints on the state machine that the code so that you don't end up having to support wrong usage that worked in earlier versions of the calling code, or write too much documentation on how to do it right.
• Try to have functions/methods per state so that the state machine is not so damn implicit.  When you look at a stack trace, the names of functions on the stack should be obvious when naming states.  The (nested) FSM that you would draw on the markerboard should bear some resemblance to the actual code.  This is a little more difficult to do in the absence of tail calls (where switches often emerge in their place), but it's important to do this where possible.

Back to C Functions and Refactoring In General

So, the concept of coroutines/tasks in C is basically just one of taking a function and breaking it into pieces by pulling all of its state (autos and parameters) into a struct.  It is more general than an object, since it is up to you to decide if you want to segregate the state into multiple pieces.  This is a more useful pattern than it may seem to be at first because of what happens when you try to refactor C code.

I judge the goodness of a language (and development environment) largely on how easy it is to turn crappy code into good code over a long period.  One major weakness of many languages when it comes to refactoring is that a lot of languages don't support multiple return values.  If most languages did support multiple return values, then function extraction would be trivial to do automatically in an IDE.  For example:

int foo(int x)
{
  int a=0;
  int b=0;
A:
  a = 1 + b;
  b = 2 * c;
B:
}

Extract A to B as a function if you have multiple returns:

int foo(int x)
{
  int a;
  int b=0;
  int c=0;
  a, b = doAtoB(b,c);
}

With multiple return values, it is very clear that b,c are in values, and a, b are out values.  We didn't have to pass in a pointer to a and wonder if doAtoB uses the original value of a, which is uninitialized.  With only single values returns, you would need to return structures (which are allocated in their own chunk of memory somewhere), or use the function pointers where it's not clear if the value is read and written, or just written.  Google's language Go actually uses this feature to lay down the law that the last parameter returned is an error code, and you are never to try to mix actual return values with error codes (ie: a comparator that returns a possibly negative integer, yet returns -1 when something went wrong, which can cause infinite loops in sorting algorithms by creating inconsistent sorting orders where a < b && b < a, etc.)

But the pattern of pulling all autos and parameters into a struct makes it very easy to break a giant function into a bunch of pieces without having to worry about changing how it behaves.  The alternative to this is to break into a bunch of smaller functions with a *lot* of parameters.  But the big downside to this is that these parameters can expose private types in the method signatures, or change the overall semantics of the function when it becomes unclear how to plug parameters back in when going from step to step.  In a big struct, some state may exist for a little longer than is strictly required, but pulling loop bodies into a single line function is now a very mechanical process.  Then perhaps with a little re-ordering of the code in the function, the parts can be given sensible names and put into functions that require no further commentary.