Generators in C++

May 26, 2008

Filed under: Source code — Andrew @ 6:19 pm

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

Abstraction foreach() can be imagined as some function/object that is returning next value of collection/sequence each time it is getting invoked. Such functions are known as generators.

Here is my version of generator() for the C++. It is based on the bright idea of Simon Tatham – “coroutines in C“.

First of all sample, here is a declaration of our generator function in C++:

#include "generator.h"

generator(descent) 
{
   int i;
   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 - return next number in [1..10], reversed.
   stop(0); // stop, end of sequence. End of body of the generator.
};

Having declared such generator we can use it as:

int main(int argc, char* argv[])
{
  descent gen;
  do
    printf("next number is %d\n", gen());
  while (gen);
  return 0;
}

That is pretty simple and should be intuitively clear, no?

Here is full source of the generator.h file:

// 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

#ifndef __generator_h_
#define __generator_h_

struct _generator
{
  int _line;
  _generator():_line(-1) {}
  operator bool() const { return _line != 0; }
};

#define generator(NAME) struct NAME : public _generator

#define emit(T)     T operator()() { \
                     if(_line < 0) { _line=0;}\
                     switch(_line) { case 0:;

#define stop(V)     } _line = 0; return (V); }

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

#endif // __generator_h_

Enjoy!

5 Comments

  1. I do not think that it may boost development. Take into account, plase, that this approach forces a developer to know how it’s implemented. Needless to say that it uses MACROs!!! The idea is great, somehow

    Comment by metalliova — June 23, 2008 @ 3:29 pm

  2. […] Previous version of generators had design problem – it required some special stop value. That is the same kind of problem as with iterators in C++. In some cases it is not possible to choose such a value. […]

    Pingback by Terra Informatica » Generators in C++ revisited. — June 26, 2008 @ 7:00 am

  3. why “do” end “while (0)
    in yield ?

    Comment by Patrick — September 30, 2008 @ 11:40 am

  4. Yes, in principle it could be just scope block:

    #define yield(V) {\\
       _line=__LINE__; \\
       _rv = (V); return true; case __LINE__: _line=__LINE__;\\
     }

    Simon initially used do/while(0) so I just left it “as is”.

    But some form of ‘{‘ ‘}’ brackets is definitely needed there to
    handle properly things like if(condition) $yield(something);

    Comment by Andrew — September 30, 2008 @ 2:10 pm

  5. Here is what I’ve ended up with:

    struct _generator
      {
        int _line;
        _generator() { rewind(); }
        void rewind() { _line = 0; }
      };
    
      #define $generator(NAME) struct NAME : public tool::_generator
    
      #define $emit(T)       bool operator()(T& _rv) { switch(_line) { case 0:;
      #define $emit2(T1,T2)  bool operator()(T1& _rv1, T2& _rv2) { switch(_line) { case 0:;
      
      #define $yield(V)      { _line=__LINE__; _rv = (V); return true; case __LINE__: _line=__LINE__; }
      #define $yield2(V1,V2) { _line=__LINE__; _rv1 = (V1); _rv2 = (V2); return true; case __LINE__: _line=__LINE__; }
    
      #define $stop  } _line = 0; return false; }

    It also has $yield2 when you need to emit two values.

    Comment by Andrew — September 30, 2008 @ 2:14 pm

RSS feed for comments on this post. TrackBack URI

Sorry, the comment form is closed at this time.