123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567 |
- [/
- Copyright Oliver Kowalke 2014.
- 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 the coroutine
- types of __acoro__ 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 event-driven model]
- The event-driven model is a programming paradigm where the flow of a program is
- determined by events. The events are generated by multiple independent sources
- and an event-dispatcher, waiting on all external sources, triggers callback
- functions (event-handlers) whenever one of those events is detected (event-loop).
- The application is divided into event selection (detection) and event handling.
- [$../../../../libs/coroutine2/doc/images/event_model.png [align center]]
- The resulting applications are highly scalable, flexible, have high
- responsiveness and the components are loosely coupled. This makes the event-driven
- model suitable for user interface applications, rule-based productions systems
- or applications dealing with asynchronous I/O (for instance network servers).
- [heading event-based asynchronous paradigm]
- A classic synchronous console program issues an I/O request (e.g. for user
- input or filesystem data) and blocks until the request is complete.
- In contrast, an asynchronous I/O function initiates the physical operation but
- immediately returns to its caller, even though the operation is not yet
- complete. A program written to leverage this functionality does not block: it
- can proceed with other work (including other I/O requests in parallel) while
- the original operation is still pending. When the operation completes, the
- program is notified. Because asynchronous applications spend less overall time
- waiting for operations, they can outperform synchronous programs.
- Events are one of the paradigms for asynchronous execution, but
- not all asynchronous systems use events.
- Although asynchronous programming can be done using threads, they come with
- their own costs:
- * hard to program (traps for the unwary)
- * memory requirements are high
- * large overhead with creation and maintenance of thread state
- * expensive context switching between threads
- The event-based asynchronous model avoids those issues:
- * simpler because of the single stream of instructions
- * much less expensive context switches
- The downside of this paradigm consists in a sub-optimal program
- structure. An event-driven program is required to split its code into
- multiple small callback functions, i.e. the code is organized in a sequence of
- small steps that execute intermittently. An algorithm that would usually be expressed
- as a hierarchy of functions and loops must be transformed into callbacks. The
- complete state has to be stored into a data structure while the control flow
- returns to the event-loop.
- As a consequence, event-driven applications are often tedious and confusing to
- write. Each callback introduces a new scope, error callback etc. The
- sequential nature of the algorithm is split into multiple callstacks,
- making the application hard to debug. Exception handlers are restricted to
- local handlers: it is impossible to wrap a sequence of events into a single
- try-catch block.
- The use of local variables, while/for loops, recursions etc. together with the
- event-loop is not possible. The code becomes less expressive.
- In the past, code using asio's ['asynchronous operations] was convoluted by
- callback functions.
- class session
- {
- public:
- session(boost::asio::io_service& io_service) :
- socket_(io_service) // construct a TCP-socket from io_service
- {}
- tcp::socket& socket(){
- return socket_;
- }
- void start(){
- // initiate asynchronous read; handle_read() is callback-function
- socket_.async_read_some(boost::asio::buffer(data_,max_length),
- boost::bind(&session::handle_read,this,
- boost::asio::placeholders::error,
- boost::asio::placeholders::bytes_transferred));
- }
- private:
- void handle_read(const boost::system::error_code& error,
- size_t bytes_transferred){
- if (!error)
- // initiate asynchronous write; handle_write() is callback-function
- boost::asio::async_write(socket_,
- boost::asio::buffer(data_,bytes_transferred),
- boost::bind(&session::handle_write,this,
- boost::asio::placeholders::error));
- else
- delete this;
- }
- void handle_write(const boost::system::error_code& error){
- if (!error)
- // initiate asynchronous read; handle_read() is callback-function
- socket_.async_read_some(boost::asio::buffer(data_,max_length),
- boost::bind(&session::handle_read,this,
- boost::asio::placeholders::error,
- boost::asio::placeholders::bytes_transferred));
- else
- delete this;
- }
- boost::asio::ip::tcp::socket socket_;
- enum { max_length=1024 };
- char data_[max_length];
- };
- In this example, a simple echo server, the logic is split into three member
- functions - local state (such as data buffer) is moved to member variables.
- __boost_asio__ provides with its new ['asynchronous result] feature a new
- framework combining event-driven model and coroutines, hiding the complexity
- of event-driven programming and permitting the style of classic sequential code.
- The application is not required to pass callback functions to asynchronous
- operations and local state is kept as local variables. Therefore the code
- is much easier to read and understand.
- [footnote Christopher Kohlhoff,
- [@ http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3964.pdf
- N3964 - Library Foundations for Asynchronous Operations, Revision 1]].
- void session(boost::asio::io_service& io_service){
- // construct TCP-socket from io_service
- boost::asio::ip::tcp::socket socket(io_service);
- try{
- for(;;){
- // local data-buffer
- char data[max_length];
- boost::system::error_code ec;
- // read asynchronous data from socket
- // execution context will be suspended until
- // some bytes are read from socket
- std::size_t length=socket.async_read_some(
- boost::asio::buffer(data),
- boost::asio::yield[ec]);
- if (ec==boost::asio::error::eof)
- break; //connection closed cleanly by peer
- else if(ec)
- throw boost::system::system_error(ec); //some other error
- // write some bytes asynchronously
- boost::asio::async_write(
- socket,
- boost::asio::buffer(data,length),
- boost::asio::yield[ec]);
- if (ec==boost::asio::error::eof)
- break; //connection closed cleanly by peer
- else if(ec)
- throw boost::system::system_error(ec); //some other error
- }
- } catch(std::exception const& e){
- std::cerr<<"Exception: "<<e.what()<<"\n";
- }
- }
- In contrast to the previous example this one gives the impression of sequential
- code and local data (['data]) while using asynchronous operations
- (['async_read()], ['async_write()]). The algorithm is implemented in one
- function and error handling is done by one try-catch block.
- [heading recursive descent parsing]
- Coroutines let you invert the flow of control so you can ask a recursive descent
- parser for parsed symbols.
- class Parser{
- char next;
- std::istream& is;
- std::function<void(char)> cb;
- char pull(){
- return std::char_traits<char>::to_char_type(is.get());
- }
- void scan(){
- do{
- next=pull();
- }
- while(isspace(next));
- }
- public:
- Parser(std::istream& is_,std::function<void(char)> cb_) :
- next(), is(is_), cb(cb_)
- {}
- void run() {
- scan();
- E();
- }
- private:
- void E(){
- T();
- while (next=='+'||next=='-'){
- cb(next);
- scan();
- T();
- }
- }
- void T(){
- S();
- while (next=='*'||next=='/'){
- cb(next);
- scan();
- S();
- }
- }
- void S(){
- if (std::isdigit(next)){
- cb(next);
- scan();
- }
- else if(next=='('){
- cb(next);
- scan();
- E();
- if (next==')'){
- cb(next);
- scan();
- }else{
- throw parser_error();
- }
- }
- else{
- throw parser_error();
- }
- }
- };
- typedef boost::coroutines2::coroutine< char > coro_t;
- int main() {
- std::istringstream is("1+1");
- // invert control flow
- coro_t::pull_type seq(
- boost::coroutines2::fixedsize_stack(),
- [&is](coro_t::push_type & yield) {
- // create parser with callback function
- Parser p( is,
- [&yield](char ch){
- // resume user-code
- yield(ch);
- });
- // start recursive parsing
- p.run();
- });
- // user-code pulls parsed data from parser
- // invert control flow
- for(char c:seq){
- printf("Parsed: %c\n",c);
- }
- }
- This problem does not map at all well to communicating between independent
- threads. It makes no sense for either side to proceed independently of the
- other. You want them to pass control back and forth.
- There's yet another advantage to using coroutines. This recursive descent parser
- throws an exception when parsing fails. With a coroutine implementation, you
- need only wrap the calling code in try/catch.
- With communicating threads, you would have to arrange to catch the exception
- and pass along the exception pointer on the same queue you're using to deliver
- the other events. You would then have to rethrow the exception to unwind the
- recursive document processing.
- The coroutine solution maps very naturally to the problem space.
- [heading 'same fringe' problem]
- The advantages of suspending at an arbitrary call depth 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/coroutine2/doc/images/same_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 ['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).
- In effect, the coroutine iterator presents a flattened view of the recursive
- data structure.
- struct node{
- typedef std::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")));
- }
- typedef boost::coroutines2::coroutine<std::string> coro_t;
- // recursively walk the tree, delivering values in order
- void traverse(node::ptr_t n,
- coro_t::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"));
- coro_t::pull_type left_d_reader([&](coro_t::push_type & out){
- traverse(left_d,out);
- });
- node::ptr_t right_b(create_right_tree_from("b"));
- coro_t::pull_type right_b_reader([&](coro_t::push_type & out){
- traverse(right_b,out);
- });
- std::cout << "left tree from d == right tree from b? "
- << std::boolalpha
- << std::equal(begin(left_d_reader),
- end(left_d_reader),
- begin(right_b_reader))
- << std::endl;
- }
- {
- node::ptr_t left_d(create_left_tree_from("d"));
- coro_t::pull_type left_d_reader([&](coro_t::push_type & out){
- traverse(left_d,out);
- });
- node::ptr_t right_x(create_right_tree_from("x"));
- coro_t::pull_type right_x_reader([&](coro_t::push_type & out){
- traverse(right_x,out);
- });
- std::cout << "left tree from d == right tree from x? "
- << std::boolalpha
- << std::equal(begin(left_d_reader),
- end(left_d_reader),
- 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]
- This code shows how coroutines could be chained.
- typedef boost::coroutines2::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.
- for(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){
- for(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){
- for(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(std::bind(readlines, _1, std::ref(infile)));
- coro_t::pull_type tokenizer(std::bind(tokenize, _1, std::ref(reader)));
- coro_t::pull_type filter(std::bind(only_words, _1, std::ref(tokenizer)));
- coro_t::pull_type tracer(std::bind(trace, _1, std::ref(filter)));
- for(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(std::bind(readlines, _1, std::ref(infile)));
- coro_t::pull_type tokenizer(std::bind(tokenize, _1, std::ref(reader)));
- coro_t::pull_type filter(std::bind(only_words, _1, std::ref(tokenizer)));
- coro_t::push_type writer(std::bind(layout, _1, 5, 15));
- for(std::string token:filter){
- writer(token);
- }
- }
- {
- std::cout << "\nfiltering output:\n";
- std::istringstream infile(data);
- coro_t::pull_type reader(std::bind(readlines,_1,std::ref(infile)));
- coro_t::pull_type tokenizer(std::bind(tokenize,_1,std::ref(reader)));
- coro_t::push_type writer(std::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(std::bind(only_words,std::ref(writer),_1));
- for(std::string token:tokenizer){
- filter(token);
- }
- }
- [endsect]
|