boost.png (6897 bytes) Home Libraries People FAQ More

PrevUpHomeNext

Symmetric coroutines

Introduction

The type of coroutines we have described so far is usually referred as asymmetric. The asymmetry is due to the fact that the caller/callee relation between a coroutine's context and caller's context is fixed. The control flow must necessarily go from the caller context to the coroutine context and back to the caller. In this model a coroutine A can obviously call coroutine B, but A becomes the caller. B cannot directly yield to the caller of A but must relinquish control to A by yielding. For example, this control flow is not possible for example:

A yield to B yield to C yield to A yield to B ... etc
This is not completely true. We will show a code transformation that demonstrates how asymmetric coroutines have the same expressive power of symmetric coroutines.

Control flow with symmetric coroutines instead is not stack-like. A coroutine can always yield freely to any other coroutine and is not restricted to return to its caller. The previous control flow is possible.

Syntax

While asymmetric coroutines are the main abstraction provided by Boost.Coroutine, a symmetric coroutine facility is also provided.

The coroutine class template has a yield_to() member function that stops the current coroutine and yields control to a different coroutine. It works exactly like yield(), except that the control is not returned to the caller but is given to another coroutine, specified as the first argument. The target coroutine can be any other coroutine as long as one of these conditions is true:

From the above conditions it follows that a coroutine can yield to itself (in this case yield_to is as if had returned immediately).

If coroutine A yields to coroutine B, the caller of A becomes the caller of B. If B ever does a normal yield, the control is given back to the caller of A.

Do not confuse calls with yields to. The first verb implies an invocation of coroutine::operator(), while the second an invocation of coroutine::yield_to. A coroutine that yields to a second does not call the second one.

As Boost.Coroutine strives for type safety, it requires that the return type of the yielded coroutine be the same of the yielder. For example, given these three coroutines:

typedefcoroutine<int(char*, float&)> coroutine1_type;
typedefcoroutine<int(int, float)> coroutine2_type;
typedefcoroutine<void *(const& char)> coroutine3_type;

coroutine1_type coroutine1(coroutine1_body);
coroutine2_type coroutine2(coroutine2_body);
coroutine3_type coroutine2(coroutine3_body);

This code is legal:

//in coroutine1_body:
self.yield_to(coroutine2, 10, 0.0);

This is not:

//in coroutine1_body
self.yield_to(coroutine3, 'a'); // return type mismatch!

There is no restriction on the argument type.

yield_to() is like goto on steroid. While it can be extremely expressive and powerful, if it used without care and discipline can easily lead to spaghetti code.

Producer/consumer revisited (again)

We have explored the consumer and producer driven versions of this path before. In this third installment we will implement the pattern with the producer and the consumer as peer symmetric coroutines. The implementation is straight forward. These the our consumer and the producer bodies:

void producer_body(producer_type::self& self, 
                   std::string base, 
                   consumer_type& consumer) {
  std::sort(base.begin(), base.end());
  do {
    self.yield_to(consumer, base);
  } while (std::next_permutation(base.begin(), base.end()));
}

void consumer_body(consumer_type::self& self, 
                   const std::string& value,
                   producer_type& producer) {
  std::cout << value << "\n";
  while(true) {
    std::cout << self.yield_to(producer)<< "\n";
  } 
}

Creating the coroutines themselves is done as usual:

producer_type producer;
consumer_type consumer;
  
producer = producer_type
  (boost::bind
   (producer_body, 
    _1, 
    "hello", 
    boost::ref(consumer)));

consumer = consumer_type
  (boost::bind
   (consumer_body, 
    _1,
    _2,
    boost::ref(producer)));

Note how we default construct both producer and consumer before actually initializing them with the bodies: we need to pass to each coroutine a reference to the other. Also note the use of boost::ref to prevent boost::bind to try to copy our non copyable coroutines.

We can start the machinery indifferently from the producer:

...
producer();
...

Or from the consumer:

...
consumer (std::string());
...

We need to provide an argument to the consumer because it expect to receive a value the first time it is called. For simplicity we provided an empty string. A better solution would have had the consumer accept boost::optional<const std::string&>.

Symmetric and asymmetric coroutine transformation

It can be demonstrated [Moura04] that both symmetric and asymmetric coroutines have the same expressive power, that is each type can be expressed in term of the other. We now will show how.

An asymmetric coroutine call can be implemented with yield_to by yielding to the called coroutine and passing as a parameter a reference to the caller coroutine. yield can be implemented with a yield_to the caller. This transformation is extremely simple and intuitive. In fact the lowest levels of the library only deal with a special swap_context function. swap_context works as an argument-less yield_to. Both yield and yield_to are implemented in terms of this function.

Implementing yield_to with only asymmetric coroutines is a bit more involved, but still straight forward. In fact we already did implement a form of it in our scheduler example. A dispatch loop invokes the first coroutine. This coroutine then chooses the next coroutine to run by returning to the dispatcher the address of the target coroutine. The dispatch loop then execute that coroutine and so on.

In conclusion Boost.Coroutine could implement only one of the two models and not loose expressiveness. Given a choice we would implement asymmetric coroutines because they are simpler to understand, safer and have a broader application. We decided to provide both models for convenience.

Copyright 2006 Giovanni P. Deretta

PrevUpHomeNext