Boost C++ Libraries

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.

'same fringe' problem

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

chaining coroutines

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);
    }
}

asynchronous operations with boost.asio

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);
}