From generators to coroutines

So far we have learned to use generators, a special kind of coroutines. We have seen that generators are function objects with no parameters and that return a sequence of values. We can generalize this concept to function objects that have zero, one or more parameters and return zero, one or more values. A generic coroutine is, not surprisingly, implemented with the coroutine template class.

All examples in this sections will assume that the following using directive is in effect:

#include <boost/coroutine/coroutine.hpp>

The accumulator coroutine

Let's start with a very simple coroutine that takes as parameter an integer and returns the sum of that integer and all integers passed before. In practice it acts as an accumulator. As usual, we start by declaring its type:

typedef coro::coroutine<int(int)> coroutine_type;

The syntax is deliberately similar to the one used in Boost.Function. This is the coroutine body:

int accumulator_body(coroutine_type::self& self, int val) {
  while(true) {
    val += self.yield(val);
  }
}

This is code is not very different from our first generator example. Still there are some differences. For example yield() now returns a value. Soon we will see what this value represent. The syntax used to declare a coroutine is not surprising:

coroutine_type accumulator(accumulator_body); 

And even its usage is straight forward:

...
for(int i = 0; i < 1000; ++i)
   std::cout << accumulator(i);
...

This will print all values in the mathematical series a[i] = a[i-1] + i. Let's see how the flow control evolves.

When accumulator goes out of scope, the coroutine is destroyed in the same way generators are destroyed: it is resumed and yield() throws an instance of exit_exception.

Copyability

While you can freely copy a generator, you can't do the same with coroutines: during the development of Boost.Coroutine it has been deemed that giving reference counted shallow copying to coroutines was too risky. Coroutines usually have a longer lifetime and are more complex. Different coroutines can interact in dynamic ways, especially with the ability to yield to another coroutine (yield_to() will be introduced in an advanced section).

The possibility of creating a cycle was very high and very hard to debug, thus the possibility of copying a coroutine object has been removed. Coroutines instead are Movable: you can return a coroutine from a function, copy construct and assign from a temporary, and explicitly __move__() them, but you can't for example add them to a standard container, unless your standard library already has support for movable types (currently in the draft standard). A coroutine is also Swappable and DefaultConstructible.

Unfortunately most libraries expect copyable types and do not support moving. For interoperability with this libraries you should use a shared_ptr to manage the lifetime of a coroutine.

Boost.Coroutine also provides the shared_coroutine that acts as a counted reference to a coroutine object. You should use this class template with care because potentially reopens the cycle loophole, and use it only as a temporary workaround for lack of movability.

Exiting a coroutine and the coroutine_exited exception

A coroutine can be exited from inside its body exactly like a generator by invoking coroutine::self::exit(), but the semantics from the point of view of the caller are different. consider this piece of code that represent a call to the object my_coroutine of type coroutine<int()>()

int i = my_coroutine();

If my_coroutine returns to the caller by invoking exit(), there is no value can be returned from operator() and be assigned to i. Instead a coroutine_exited exception is thrown fromoperator()`.

A coroutine can also be exited by throwing any other exception from inside the body and letting the stack unwind below the coroutine main body. The coroutine is terminated and operator() will throw an instance of abnormal_exit exception.

Finally a coroutine can be exited from outside its body by calling coroutine::exit(). It behaves exactly as if the coroutine had exited out of scope.

Other member and friend functions

coroutine provides a set of member functions to query its state; these are exited(), empty(), waiting() and pending(). exited() returns true if a coroutine has been exited (by throwing an exception, by calling exit() or by a plain return), empty() returns true if a coroutine has not been assigned. waiting() and pending() are related to the event waiting mechanics and will be explained later.

Both coroutine::swap() and a friend swap() are provided with the usual semantics.

coroutine::self provides a result() member function that returns the value returned by the last yield() (or as a parameter to the body if yield() has not been called yet).

The coroutine::self::yield_to() member function will be explained in an advanced section about symmetric coroutines.

Multiple arguments and return values

A coroutine can have more than one argument. For example the coroutine accumulator2 is similar to accumulator, but it takes two parameters and accumulate only the larger of the two values:

typedef coro::coroutine<int(int, int)> coroutine_type;

int accumulator2_body(coroutine_type::self& self,
                      int arg1,
                      int arg2) {
  int i = 0;
  while(true) {
     i +=  std::max(arg1, arg2);
     boost::tie(arg1, arg2) = self.yield(i);
  }
}

coroutine_type accumulator2(accumulator2_body);

Note that yield now returns two values in the form of a boost::tuple<int, int>. accumulator2 can be called like any other binary function or function object:

...
int i = accumulator2(0, 1);
...

Multiple return values are also handled with tuples. The coroutine muladd returns the partial sum and the partial product of the argument passed so far:

typedef coro::coroutine<boost::tuple<int, int>(int)> coroutine_type;

boost::tuple<int, int> muladd_body
  (coroutine_type::self& self, 
   int val) {
  int prod = 0;
  int sum = 0;
  while(true) {
    prod += val;
    sum  += val;
    val = self.yield(boost::make_tuple(prod, sum));
  }
}

coroutine_type muladd(muladd_body);

Again, muladd behaves like any other function that return a tuple:

...
int prod;
int sum;
boost::tie(prod, sum) = muladd(0);
...

Notice that there is a slight asimmetry between the first and the second example. In the call to accumulator2 there is no need to call boost::make_tuple(...), the arguments to operator() are automatically packed in the tuple that is returned by yield(). On the other hand, in the call to yield() in muladd_body, the result types must manually packed in a tuple. It would be nice if this syntax could be used:

...
self.yield(prod, sum);
...

Boost.Coroutine in fact allows this user friendlier syntax, but it is not enabled by default because it could conflict with generic code. To enable it coroutine_type must be redefined like this:

typedef coro::coroutine<coro::tuple_traits<int, int>(int)> coroutine_type;

The coroutine class template recognizes the special coro::tuple_traits type and enables yield() to automatically pack its arguments.

Behind generators

To complete the tour of the basic capabilities of Boost.Coroutine we will return to the generator class template and explain how it is implemented in term of coroutines. This is its definition:

template<typename ValueType>
class generator : public std::iterator<std::input_iterator_tag, ValueType> {
  typedef shared_coroutine<ValueType()> coroutine_type;
public:
  typedef typename coroutine_type::result_type value_type;
  typedef typename coroutine_type::self self;

  generator() {}

 generator(const generator& rhs) :
    m_coro(rhs.m_coro),
    m_val(rhs.m_val) {}

  template<typename Functor>
  generator(Functor f) :
    m_coro(f), 
    m_val(assing()) {}

  value_type operator*() {
    return *m_val;
  }

  generator& operator++() {
    m_val = assing();
  }

  generator operator++(int) {
     generator t(*this);
     ++(*this);
     return t;
  }

  friend operator==(const generator& lhs, const generator& rhs) {
    lhs.m_val == rhs.m_val;
  }
private:
  boost::optional<vale_type> assign() {
    try {
      return m_coro? m_coro() :  boost::optional<value_type>();
    } catch (coroutine_exited) {
      return boost::optional<value_type>()
    }
  }

  coroutine_type m_coro;
  boost::optional<value_type> m_val;
};

generator has two members variables:

The first two member functions are the default constructor and the copy constructor. There is nothing peculiar in them. Note how a default constructed generator has an empty m_val and thus is a past-the-end iterator.

The third member constructs the generator from a function or function object parameter. The argument is forwarded to the m_coro member to initialize the internal coroutine. m_val is then initialized by a call to assing().

operator* simply returns *m_val, that is the current value stored in the optional. The result of dereferencing a past-the-end iterator is undefined.

The prefix operator++ simply reassign the result of assign() to m_val.

The postfix operator++ is implemented in terms of the prefix operator++ in the usual way.

operator== compares two generators for equality by comparing their m_val members. Notice that two past-the-end iterators have both empty m_val and compare equally.

assign() is responsible of returning the next value in the sequence by invoking the underlying coroutine and eventually signaling the end of iteration. It first checks the coroutine for liveness (through coroutinesafe-bool conversion). If the coroutine is live it returns the result of a call to the coroutine. If the coroutine is dead (it has exited or has never been initialized) it returns an empty optional. Notice that the call to the coroutine could throw a coroutine_exited exception if the coroutine exited, without yielding a value, by invoking exit(). In that case an empty optional is returned.

The try {...} catch(coroutine_exited) {...} idiom is frequent in code that use coroutines that are expected to terminate via exit() (that this, the exit() termination path is not "exceptional"). Boost.Coroutine provides a way to simplify this code by completely eliminating the exception. For example assign() can be rewritten as:

boost::optional<vale_type> assing() {
  return m_coro? m_coro(std::nothrow) :  boost::optional<value_type>();
}

Notice the extra std::nothrow parameter. If the first parameter to a coroutine<result_type(...)>::operator() is an object of type std::nothrow_t, the return type of the operator is modified to boost::optional<result_type>. The optional will contain the normal result value in the case of a normal yield() or return statement, or will be empty if the coroutine has been exited via exit(). Notice that if result_type was void it will remain unchanged (no optional will be returned), but no exception will be thrown.

If the coroutine terminates because of an uncaught exception not of type exit_exception, operator()(std::nothrow) will still throw an abnormal_exit exception.

If a coroutine takes one or more parameters, std::nothrow must be the first parameter. For example a coroutine my_coro of type:

typedef coro::coroutine<int(long, double, char)> coroutine_type;

Will be invoked like this:

boost::optional<int> res = my_coro(std::nothrow, 10000L, 10.7, 'a');

Example: producer/consumer revisited

A previous example presented a consumer driven version of the producer/consumer pattern. We will now implement a producer driven example of the same scenario:

typedef coroutine<void(const std::string&)> coroutine_type;

template<typename Consumer>
void producer(Consumer consumer, std::string base) {
  std::sort(base.begin(), base.end());
  do {
    consumer(base);
  } while (std::next_permutation(base.begin(), base.end()));
}

void consumer(coroutine_type::self& self, const std::string& value) {
  std::cout << value << "\n";
  while(true) {
    std::cout << self.yield()<< "\n";
  } 
}

Here we take advantage of the capability to pass arguments in a coroutine invocation to reverse the leading role of the pattern. Extending this pattern to support filter functions is left as an exercise for the reader.

Conclusions

We have now terminated our tour on the basic capabilities of coroutine and generator. The next section will describe more advanced features, including symmetric coroutines and event handling.