307 lines
12 KiB
Plaintext
307 lines
12 KiB
Plaintext
[/
|
|
Copyright Oliver Kowalke 2009.
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt
|
|
]
|
|
|
|
[section:motivation Motivation]
|
|
|
|
In order to support a broad range of execution control behaviour __push_coro__ and
|
|
__pull_coro__ 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.
|
|
|
|
|
|
[heading '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.
|
|
|
|
[$../../../../libs/coroutine/doc/images/fringe.png [align center]]
|
|
|
|
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 __push_coro__.
|
|
__push_coro__ suspends the recursive computation and transfers the data value to
|
|
the main execution context.
|
|
__pull_coro_it__, created from __pull_coro__, steps over those data values and
|
|
delivers them to ['std::equal()] for comparison. Each increment of __pull_coro_it__
|
|
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
|
|
|
|
|
|
[heading 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);
|
|
}
|
|
}
|
|
|
|
|
|
|
|
[heading 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.
|
|
__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);
|
|
}
|
|
|
|
[endsect]
|