...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
In order to support a broad range of execution control behaviour coroutine<>::push_type and coroutine<>::pull_type can be used to escape-and-reenter loops, to escape-and-reenter recursive computations and for cooperative multitasking helping to solve problems in a much simpler and more elegant way than with only a single flow of control.
The advantages can be seen particularly clearly with the use of a recursive function, such as traversal of trees. If traversing two different trees in the same deterministic order produces the same list of leaf nodes, then both trees have the same fringe.
Both trees in the picture have the same fringe even though the structure of the trees is different.
The same fringe problem could be solved using coroutines by iterating over the leaf nodes and comparing this sequence via \cpp{std::equal()}. The range of data values is generated by function traverse() which recursively traverses the tree and passes each node's data value to its coroutine<>::push_type. coroutine<>::push_type suspends the recursive computation and transfers the data value to the main execution context. boost::coroutines::coroutine<>::pull_type::iterator, created from coroutine<>::pull_type, steps over those data values and delivers them to std::equal() for comparison. Each increment of boost::coroutines::coroutine<>::pull_type::iterator resumes traverse(). Upon return from iterator::operator++(), either a new data value is available, or tree traversal is finished (iterator is invalidated).
struct node{ typedef boost::shared_ptr<node> ptr_t; // Each tree node has an optional left subtree, // an optional right subtree and a value of its own. // The value is considered to be between the left // subtree and the right. ptr_t left,right; std::string value; // construct leaf node(const std::string& v): left(),right(),value(v) {} // construct nonleaf node(ptr_t l,const std::string& v,ptr_t r): left(l),right(r),value(v) {} static ptr_t create(const std::string& v){ return ptr_t(new node(v)); } static ptr_t create(ptr_t l,const std::string& v,ptr_t r){ return ptr_t(new node(l,v,r)); } }; node::ptr_t create_left_tree_from(const std::string& root){ /* -------- root / \ b e / \ a c -------- */ return node::create( node::create( node::create("a"), "b", node::create("c")), root, node::create("e")); } node::ptr_t create_right_tree_from(const std::string& root){ /* -------- root / \ a d / \ c e -------- */ return node::create( node::create("a"), root, node::create( node::create("c"), "d", node::create("e"))); } // recursively walk the tree, delivering values in order void traverse(node::ptr_t n, boost::coroutines::coroutine<std::string>::push_type& out){ if(n->left) traverse(n->left,out); out(n->value); if(n->right) traverse(n->right,out); } // evaluation { node::ptr_t left_d(create_left_tree_from("d")); boost::coroutines::coroutine<std::string>::pull_type left_d_reader( [&]( boost::coroutines::coroutine<std::string>::push_type & out){ traverse(left_d,out); }); node::ptr_t right_b(create_right_tree_from("b")); boost::coroutines::coroutine<std::string>::pull_type right_b_reader( [&]( boost::coroutines::coroutine<std::string>::push_type & out){ traverse(right_b,out); }); std::cout << "left tree from d == right tree from b? " << std::boolalpha << std::equal(boost::begin(left_d_reader), boost::end(left_d_reader), boost::begin(right_b_reader)) << std::endl; } { node::ptr_t left_d(create_left_tree_from("d")); boost::coroutines::coroutine<std::string>::pull_type left_d_reader( [&]( boost::coroutines::coroutine<std::string>::push_type & out){ traverse(left_d,out); }); node::ptr_t right_x(create_right_tree_from("x")); boost::coroutines::coroutine<std::string>::pull_type right_x_reader( [&]( boost::coroutines::coroutine<std::string>::push_type & out){ traverse(right_x,out); }); std::cout << "left tree from d == right tree from x? " << std::boolalpha << std::equal(boost::begin(left_d_reader), boost::end(left_d_reader), boost::begin(right_x_reader)) << std::endl; } std::cout << "Done" << std::endl; output: left tree from d == right tree from b? true left tree from d == right tree from x? false Done
The following example demonstrates how coroutines could be chained.
typedef boost::coroutines::coroutine<std::string> coro_t; // deliver each line of input stream to sink as a separate string void readlines(coro_t::push_type& sink, std::istream& in){ std::string line; while(std::getline(in,line)) sink(line); } void tokenize(coro_t::push_type& sink, coro_t::pull_type& source){ // This tokenizer doesn't happen to be stateful: you could reasonably // implement it with a single call to push each new token downstream. But // I've worked with stateful tokenizers, in which the meaning of input // characters depends in part on their position within the input line. BOOST_FOREACH(std::string line, source){ std::string::size_type pos = 0; while(pos < line.length()){ if (line[pos] == '"'){ std::string token; ++pos; // skip open quote while (pos < line.length() && line[pos] != '"') token += line[pos++]; ++pos; // skip close quote sink(token); // pass token downstream } else if (std::isspace(line[pos])){ ++pos; // outside quotes, ignore whitespace } else if (std::isalpha(line[pos])){ std::string token; while (pos < line.length() && std::isalpha(line[pos])) token += line[pos++]; sink(token); // pass token downstream } else { // punctuation sink(std::string(1,line[pos++])); } } } } void only_words(coro_t::push_type& sink,coro_t::pull_type& source){ BOOST_FOREACH(std::string token,source){ if (!token.empty() && std::isalpha(token[0])) sink(token); } } void trace(coro_t::push_type& sink, coro_t::pull_type& source){ BOOST_FOREACH(std::string token,source){ std::cout << "trace: '" << token << "'\n"; sink(token); } } struct FinalEOL{ ~FinalEOL(){ std::cout << std::endl; } }; void layout(coro_t::pull_type& source,int num,int width){ // Finish the last line when we leave by whatever means FinalEOL eol; // Pull values from upstream, lay them out 'num' to a line for (;;){ for (int i = 0; i < num; ++i){ // when we exhaust the input, stop if (!source) return; std::cout << std::setw(width) << source.get(); // now that we've handled this item, advance to next source(); } // after 'num' items, line break std::cout << std::endl; } } // For example purposes, instead of having a separate text file in the // local filesystem, construct an istringstream to read. std::string data( "This is the first line.\n" "This, the second.\n" "The third has \"a phrase\"!\n" ); { std::cout << "\nfilter:\n"; std::istringstream infile(data); coro_t::pull_type reader(boost::bind(readlines, _1, boost::ref(infile))); coro_t::pull_type tokenizer(boost::bind(tokenize, _1, boost::ref(reader))); coro_t::pull_type filter(boost::bind(only_words, _1, boost::ref(tokenizer))); coro_t::pull_type tracer(boost::bind(trace, _1, boost::ref(filter))); BOOST_FOREACH(std::string token,tracer){ // just iterate, we're already pulling through tracer } } { std::cout << "\nlayout() as coroutine::push_type:\n"; std::istringstream infile(data); coro_t::pull_type reader(boost::bind(readlines, _1, boost::ref(infile))); coro_t::pull_type tokenizer(boost::bind(tokenize, _1, boost::ref(reader))); coro_t::pull_type filter(boost::bind(only_words, _1, boost::ref(tokenizer))); coro_t::push_type writer(boost::bind(layout, _1, 5, 15)); BOOST_FOREACH(std::string token,filter){ writer(token); } } { std::cout << "\nfiltering output:\n"; std::istringstream infile(data); coro_t::pull_type reader(boost::bind(readlines,_1,boost::ref(infile))); coro_t::pull_type tokenizer(boost::bind(tokenize,_1,boost::ref(reader))); coro_t::push_type writer(boost::bind(layout,_1,5,15)); // Because of the symmetry of the API, we can use any of these // chaining functions in a push_type coroutine chain as well. coro_t::push_type filter(boost::bind(only_words,boost::ref(writer),_1)); BOOST_FOREACH(std::string token,tokenizer){ filter(token); } }
In the past the code using asio's asynchronous operations was scattered by callbacks. Boost.Asio provides with its new asynchronous result feature a new way to simplify the code and make it easier to read. boost::asio::yield_context uses internally Boost.Coroutine:
void echo(boost::asio::ip::tcp::socket& socket,boost::asio::yield_context yield){ char data[128]; // read asynchronous data from socket // execution context will be suspended until // some bytes are read from socket std::size_t n=socket.async_read_some(boost::asio::buffer(data),yield); // write some bytes asynchronously boost::asio::async_write(socket,boost::asio::buffer(data,n),yield); }