Generators and Coroutines in C++, Part 1

12 Oct 2008

Python has a pretty interesting concept of generators: functions that, uhh, generate values. And a whole host of tools (see itertools) that iterate or compute on the results that are generated. (Which are apparently inspired by Haskell, section 8.1). Here's a simple generator (function ZeroToNine). It's too simple, but think of any function that generates something. Maybe the results of a parser, maybe a network read, maybe just computing something.

def ZeroToNine():
    for i in range(10):
       yield i

for i in ZeroToNine():
   print i

I played around trying to fake this in C++ in the STL way. You end up having to write a lot of boiler plate code to simulate STL's concept of an iterator, and/or chop up your code in un-natural functions for use in std::for_each, std::transform or std::generate. STL's data structures are one thing, but the STL for functional programming leaves much to be desired. Boost has some interesting, uhh, contortions to C++ to attempt to simplify this, but at some point you aren't even sure what language you are programming in. And good luck trying to read the Boost source code. Basically the STL way sucked for making generators.

Then I was thinking "hmmm,maybe co-routines". Previously I've used things like libevent and some crazy assembly language stuff to do co-routines. But it turns out there is another way. Check this:

#include 
#include 
using namespace std;

class Range {
private:
  int i, iend;
  int __s;

public:
  Range(int start, int end)
    : i(start), iend(end), __s(0)  { }

  int operator() (void) {
    switch (__s) {
    case 0:;
      __s = 30;
      for (; i < iend; ++i) {
        return i;
      case 30: ;
      }
      break;

      default:
        throw std::runtime_error("error -- should never happen");
    }

    throw std::runtime_error("normal end");
  }
};

Yes, that's right -- the case 30 statement is inside the for loop! This is legal and compiles.

And finally:

int main() {
  Range r(0,3);
  try {
    while (true) {
      cout << "r = " << r() << "\n";
    }
  } catch (std::runtime_error& e) {
    cout << e.what() << "\n";
  }
}

Compiles, works, prints. Some clever folks have invented macros to do all the switch-trickery so your editor or source -code checker doesn't vomit. I didn't use the macros so you code see the madness . The main reference is by Simon Tatham. Another variation is described by CodePost.org. (Oh, just found Protothreads). Here's a version using the CodePort.org macros:

#define cr_context   int __s;
#define cr_init()    __s = 0;
#define cr_start()   switch (__s) { case 0:
#define cr_return(x) { __s = __LINE__; return x; case __LINE__: ; }
#define cr_end()     { break; default: for (;;) ; } } __s = 0; 

class Range {
private:
  int i;
  int iend;
  cr_context;

public:

  typedef int value_type;

  Range(int start, int end)
    : i(start), iend(end)
  {
    cr_init();
  }

  int operator() (void) {
    cr_start();
    for (; i < iend; ++i) {
      cr_return(i);
    }
    cr_end();
    throw std::runtime_error("all done");
  }
};

That is pretty easy to read and follow. The exceptions and initialization could be improved, and I'm pretty sure CodePost.org's macros aren't optimal but you get the idea.

Range isn't the most interesting example, but now with templates and some basic STL, you are probably able to duplicate most of the python generator and iterator functions. Now is this a good idea? Is this useful? Is it fast? I don't know yet!


Comment 2009-01-20 by None

That looks like a variant of duffs device, but I'm not sure how well duffs plays with modern C++ code...

What happens when that for loop has something constructed at the top and destructed at the end?

for (; i < iend; ++i)
String s = "asdf";
return i;
case 30: ;
}

If we goto 30, is s initialized with "asdf", or is the destructor called on the uninitialized variable? Does the language standard handle this case?


Comment 2009-01-20 by None

Hi Brendan, yeah it's duff's device rewired. I wrote about that in some other post.... That's said, I think this is more "interesting" than useful. If someone is dying for generators and co-routines it's probably easier just to use libevent to get "real" coroutines. --nickg