Generators in C++

Introduction

As we know, iterators in C++ is a good but not a perfect abstraction. The concept of foreach() (D, Python, Ruby, etc.) appears as a more generic solution. At least, foreach() does not require an artificial iterator::end() to be defined for the collection.

The foreach() abstraction can be imagined as some function/object that returns the next value of collection/sequence each time it gets invoked. Such functions are known as generators.

The proposed implementation of the generator/yield feature is provided below in full.

Background

This version of generator() for C++ is based on the bright idea of Simon Tatham - "coroutines in C". In particular, on the idea of using switch/case for this implementation.

Declaring a Generator

To declare a generator, you will use $generator, $yield, $emit, and $stop "keywords" that are macro definitions in fact.

And here is a typical implementation of a generator that emits numbers from 10 to 1 in descending order:

include "generator.h"

$generator(descent)
{
   // place for all variables used in the generator
   int i; // our counter

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // a.k.a. yield in Python,
                    // returns next number in [1..10], reversed.
   $stop; // stop, end of sequence. End of body of the generator.
};

Having such a descending generator declared, we will use it as:

int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "get next" generator invocation
    printf("next number is %d\n", n);
  return 0;
}

The gen(n) thing is in fact an invocation of the bool operator()(int& v) method defined "under the hood" of our generator object. It returns true if the parameter v was set, and false if our generator cannot provide more elements - was stopped.

As you may see, for(int n; gen(n);) looks close enough to the construction for(var n in gen) used in JavaScript for exactly the same purpose. Expressiveness is the beauty of the approach.

generator.h

And here is the source code of the generator implementation:

#ifndef __generator_h__
#define __generator_h__

// generator/continuation for C++
// author: Andrew Fedoniouk @ terrainformatica.com
// idea borrowed from: "coroutines in C" Simon Tatham,
//   http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

class _generator
{
protected:
  int _line;
public:
  _generator():_line(0) {}
};

#define $generator(NAME) struct NAME : public _generator

#define $emit(T) bool operator()(T& _rv) { \
                    switch(_line) { case 0:;

#define $stop  } _line = 0; return false; }

#define $yield(V)     \
        do {\
            _line=__LINE__;\
            _rv = (V); return true; case __LINE__:;\
        } while (0)
#endif

That is a bit cryptic, but if you would read the original article of Simon Tatham, then you will get an idea of what is going on here.

Limitations of the Approach

One obvious limitation - $yield cannot be placed inside a switch as $emit() declares a switch by itself.

History

This approach of making generators in C++ was originally published in two articles in my blog:

• Generators in C++
• Generators in C++ revisited