Implementing a generator in C++0x

Question

The python keyword yield has been a great conceptual abstraction for me, allowing me to distill the important parts of an algorithm to human-readable form. We have previously discussed:

Python generators in various languages

where an answer was given for a windows only library in C++. In addition I've found another example using a funky macro expansion in the question:

Generators in C++ — invalid use of nonstatic data member

The edge of my computer science knowledge tells me that a yield function has something to do with co-routines and monads, but I'm not quite how this fits into what C++ or C++0x can accomplish.

It seems that in C++, without the using of a macro-expansion or a windows only fiber (thread), yeild can not be implemented. Is this true? Does the question change with the additional language features of C++0x?

Answer 1

You can map yield python mechanism to C++ iterators.

See Boost Function Input Iterator and the example:

The Function Input Iterator allows for creating iterators that encapsulate a nullary function object and a state object which tracks the number of times the iterator has been incremented. A Function Input Iterator models the InputIterator concept and is useful for creating bounded input iterators.

Like the Generator Iterator, the Function Input Iterator takes a function that models the Generator concept (which is basically a nullary or 0-arity function object). Each increment of the function Function Input Iterator invokes the generator function and stores the value in the iterator. When the iterator is dereferenced the stored value is returned.

Answer 2

yield is basically a way to implement a restricted form of coroutines.

If you want to badly enough, you can (as in, "people have") implemented relatively complete coroutines in C using setjmp and longjmp. In C++, you can probably do the same, though I'm not entirely sure. The problem with C++ becomes one of deciding what dtors to execute when. Offhand, I think the answer is that dtors shouldn't be affected by the coroutine usage, but I haven't really thought about it much. Assuming that's correct, then roughly the same code should probably work for C++ as for C.

C++0x adds full support for threads and such. Though it can be clumsy and/or increase overhead, pretty much anything you could hope to do with fibers, you can also do with threads. As such, it would support the idiom quite a bit more directly, so implementation would be quite a bit easier.

Answer 3

Hmm I've never used generators myself but from what I understand you want some function that returns an iterator that implements the increment operator ++. Pseudo code:

int f(int x) {
    for(int i = 0; i < x; ++i) {
        yield(i);
    }
}

for(iterator it = make_generator(std::bind(f, 5));
    it != generator_end();
    ++it)
{
    do_something(*it);
}

// iterator specialized for the return type of f
template<typename T>
iterator<T> make_generator(Function<T (void)> f) {
    ...
}

You will need to construct the iterator from pointer to function f, and you can pass any arguments to f by using std::bind.

Now at each iteration you need to effectively call f at some point and the function yield must do some stack manipulation to save the current stack, return the yielded value and restore the stack when the function gets called again. You only need to save the stack up to the point where f is called (no need for entire stack), but this could be tricky to implement. You'll probably have to save the stack pointer before you call f, then make a copy of the contents of (previous stack pointer..current stack pointer) somewhere.