Lambda the Ultimate

Coroutines in C
started 5/23/2003; 7:49:52 PM - last post 5/26/2003; 10:19:42 PM

5/23/2003; 7:49:52 PM (reads: 591, responses: 6)

An interesting variant of Duff's device, with a few macros for syntactic sugar. As the author argues, "Coding standards aim for clarity. By hiding vital things like switch, return and case statements inside "obfuscating" macros, the coding standards would claim you have obscured the syntactic structure of the program, and violated the requirement for clarity. But you have done so in the cause of revealing the algorithmic structure of the program, which is far more likely to be what the reader wants to know!"

andrew cooke - Re: Coroutines in C

5/24/2003; 11:56:22 AM (reads: 592, responses: 1)

I was surprised to see that he doesn't use setjmp/longjmp (it really is a kind of Duff's device!) - I believe that you can use those to implement coroutines (since they allow you to save/replace the stack) and that Io actually does implement co-routines this way (ie via setjmp).

I think the technique shown here is also called trampolining.

Alex Sauer-Budge - Re: Coroutines in C

5/24/2003; 1:46:54 PM (reads: 606, responses: 0)

Michel Schinz and Martin Odersky write in Tail call elimination on the Java Virtual Machine:

A trampoline is an outer function which repeatedly calls an inner function. Each time the inner function wishes to tail call another function, it does not call it directly but simply returns its identity (e.g. as a closure) to the trampoline, which then does the call itself. Unlimited stack growth is thus avoided, but some performance is inevitably lost, mostly because all the calls made by the trampoline are calls to statically unknown functions.

And reference David Tarditi, Anurag Acharya, and Peter Lee. No assembly required: Compiling standard ML to C.

Ehud Lamm - Re: Coroutines in C

5/25/2003; 2:23:34 PM (reads: 537, responses: 0)

Trampoling is a useful technique. A good survey showing how to use it to do cool thingd is Trampolined Style by Steven E. Ganz, Daniel P. Friedman, and Mitchell Wand (ICFP 1999).

LtU research paper page has the link, as well as link other papers we mention here routinely.

Kimberley Burchett - Re: Coroutines in C

5/26/2003; 1:03:56 PM (reads: 510, responses: 0)

The main problem with the technique as described is the requirement to use static variables. However this can be got around by the standard technique of passing a pointer to some state as the first parameter. This is exactly what the article suggests, mentioning a "ctx" parameter. However an even better solution is to use C++, since "passing a pointer to some state as the first parameter" is exactly the purpose of the implicit "this" parameter. Here's a C++ version of one of his examples:

class Decompressor {
private:
     int c, len;
public:
     int read() {
         crBegin();
         while (1) {
             c = getchar();
             if (c == EOF)
                 break;
             if (c == 0xFF) {
                 len = getchar();
                 c = getchar();
                 while (len--)
                     crReturn(c);
             }
             else {
                 crReturn(c);
             }
         }
         crReturn(EOF);
         crFinish;
     }
}

Also, C++ constructors can be used to automatically provide the "initialization" call needed by the parser example. It seems C++ was made for this technique.

sean - Re: Coroutines in C

5/26/2003; 3:57:08 PM (reads: 493, responses: 0)

But that's so clean! This, on the other hand, is more in the spirit of the original:

#include <iostream>
using namespace std;
class Coro {
public:
    Coro() : st(0) { }
protected:
    int st;
};
#define coreturn(x) do { \
    this->st = __LINE__; return (x); case __LINE__: ; \
} while (0)
#define coro(x) class x : public Coro
#define coro_start(ret, args...) \
public: \
    ret operator() (args) { \
	switch (st) { \
	case 0:
#define coro_end(x) default:  return x; } }
coro(accum) {
    int i, sum;
    coro_start(int, int x);
    sum = 0;
    for (i = 0; i < 5; i++)
	coreturn(sum += x);
    coro_end(-1);
};
int main() {
    accum f, g;
    for (int i = 0; i < 3; i++)
	cout << f(i) << endl;
    g = f;
    cout << g(3) << ", " << f(3) << endl;
}

Ken Hirsch - Re: Coroutines in C

5/26/2003; 10:19:42 PM (reads: 485, responses: 0)

Okay, how about a recursive co-routine (using sean's macros):

#include <iostream>
#include <algorithm>
#include "coro.h"
using namespace std;


coro(Perm) {
  int i;
  Perm *recur;
  coro_start(char *, char *s);


  if (!s[0]) {
    coreturn(s);
  } else {
    for (i=0; s[i]; i++) {
	recur = new Perm();
	swap(s[0],s[i]);
	while ((*recur)(s+1))
	  coreturn(s);
	swap(s[0],s[i]);
	delete recur;
    }
  }
  coro_end(NULL);
};


int
main(int argc, char ** argv)
{
  char *s;
  Perm permute;


  if (argc != 2) {
    cerr << "usage: " << argv[0] << " abc\n";
    exit(1);
  }


  while (s = permute(argv[1])) {
    cout << s << "\n";
  }
  exit(0);
}

;