ceph/src/boost/libs/coroutine2/doc/motivation.qbk

   1 [/
   2           Copyright Oliver Kowalke 2014.
   3  Distributed under the Boost Software License, Version 1.0.
   4     (See accompanying file LICENSE_1_0.txt or copy at
   5           http://www.boost.org/LICENSE_1_0.txt
   6 ]
   7
   8 [section:motivation Motivation]
   9
  10 In order to support a broad range of execution control behaviour the coroutine
  11 types of __acoro__ can be used to ['escape-and-reenter] loops, to
  12 ['escape-and-reenter] recursive computations and for ['cooperative] multitasking
  13 helping to solve problems in a much simpler and more elegant way than with only
  14 a single flow of control.
  15
  16
  17 [heading event-driven model]
  18
  19 The event-driven model is a programming paradigm where the flow of a program is
  20 determined by events. The events are generated by multiple independent sources
  21 and an event-dispatcher, waiting on all external sources, triggers callback
  22 functions (event-handlers) whenever one of those events is detected (event-loop).
  23 The application is divided into event selection (detection) and event handling.
  24
  25 [$../../../../libs/coroutine2/doc/images/event_model.png [align center]]
  26
  27 The resulting applications are highly scalable, flexible, have high
  28 responsiveness and the components are loosely coupled. This makes the event-driven
  29 model suitable for user interface applications, rule-based productions systems
  30 or applications dealing with asynchronous I/O (for instance network servers).
  31
  32
  33 [heading event-based asynchronous paradigm]
  34
  35 A classic synchronous console program issues an I/O request (e.g. for user
  36 input or filesystem data) and blocks until the request is complete.
  37
  38 In contrast, an asynchronous I/O function initiates the physical operation but
  39 immediately returns to its caller, even though the operation is not yet
  40 complete. A program written to leverage this functionality does not block: it
  41 can proceed with other work (including other I/O requests in parallel) while
  42 the original operation is still pending. When the operation completes, the
  43 program is notified. Because asynchronous applications spend less overall time
  44 waiting for operations, they can outperform synchronous programs.
  45
  46 Events are one of the paradigms for asynchronous execution, but
  47 not all asynchronous systems use events.
  48 Although asynchronous programming can be done using threads, they come with
  49 their own costs:
  50
  51 * hard to program (traps for the unwary)
  52 * memory requirements are high
  53 * large overhead with creation and maintenance of thread state
  54 * expensive context switching between threads
  55
  56 The event-based asynchronous model avoids those issues:
  57
  58 * simpler because of the single stream of instructions
  59 * much less expensive context switches
  60
  61 The downside of this paradigm consists in a sub-optimal program
  62 structure. An event-driven program is required to split its code into
  63 multiple small callback functions, i.e. the code is organized in a sequence of
  64 small steps that execute intermittently. An algorithm that would usually be expressed
  65 as a hierarchy of functions and loops must be transformed into callbacks. The
  66 complete state has to be stored into a data structure while the control flow
  67 returns to the event-loop.
  68 As a consequence, event-driven applications are often tedious and confusing to
  69 write. Each callback introduces a new scope, error callback etc. The
  70 sequential nature of the algorithm is split into multiple callstacks,
  71 making the application hard to debug. Exception handlers are restricted to
  72 local handlers: it is impossible to wrap a sequence of events into a single
  73 try-catch block.
  74 The use of local variables, while/for loops, recursions etc. together with the
  75 event-loop is not possible. The code becomes less expressive.
  76
  77 In the past, code using asio's ['asynchronous operations] was convoluted by
  78 callback functions.
  79
  80         class session
  81         {
  82         public:
  83             session(boost::asio::io_service& io_service) :
  84                   socket_(io_service) // construct a TCP-socket from io_service
  85             {}
  86
  87             tcp::socket& socket(){
  88                 return socket_;
  89             }
  90
  91             void start(){
  92                 // initiate asynchronous read; handle_read() is callback-function
  93                 socket_.async_read_some(boost::asio::buffer(data_,max_length),
  94                     boost::bind(&session::handle_read,this,
  95                         boost::asio::placeholders::error,
  96                         boost::asio::placeholders::bytes_transferred));
  97             }
  98
  99         private:
 100             void handle_read(const boost::system::error_code& error,
 101                              size_t bytes_transferred){
 102                 if (!error)
 103                     // initiate asynchronous write; handle_write() is callback-function
 104                     boost::asio::async_write(socket_,
 105                         boost::asio::buffer(data_,bytes_transferred),
 106                         boost::bind(&session::handle_write,this,
 107                             boost::asio::placeholders::error));
 108                 else
 109                     delete this;
 110             }
 111
 112             void handle_write(const boost::system::error_code& error){
 113                 if (!error)
 114                     // initiate asynchronous read; handle_read() is callback-function
 115                     socket_.async_read_some(boost::asio::buffer(data_,max_length),
 116                         boost::bind(&session::handle_read,this,
 117                             boost::asio::placeholders::error,
 118                             boost::asio::placeholders::bytes_transferred));
 119                 else
 120                     delete this;
 121             }
 122
 123             boost::asio::ip::tcp::socket socket_;
 124             enum { max_length=1024 };
 125             char data_[max_length];
 126         };
 127
 128 In this example, a simple echo server, the logic is split into three member
 129 functions - local state (such as data buffer) is moved to member variables.
 130
 131 __boost_asio__ provides with its new ['asynchronous result] feature a new
 132 framework combining event-driven model and coroutines, hiding the complexity
 133 of event-driven programming and permitting the style of classic sequential code.
 134 The application is not required to pass callback functions to asynchronous
 135 operations and local state is kept as local variables. Therefore the code
 136 is much easier to read and understand.
 137 [footnote Christopher Kohlhoff,
 138 [@ http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3964.pdf
 139 N3964 - Library Foundations for Asynchronous Operations, Revision 1]].
 140
 141         void session(boost::asio::io_service& io_service){
 142             // construct TCP-socket from io_service
 143             boost::asio::ip::tcp::socket socket(io_service);
 144
 145             try{
 146                 for(;;){
 147                     // local data-buffer
 148                     char data[max_length];
 149
 150                     boost::system::error_code ec;
 151
 152                     // read asynchronous data from socket
 153                     // execution context will be suspended until
 154                     // some bytes are read from socket
 155                     std::size_t length=socket.async_read_some(
 156                             boost::asio::buffer(data),
 157                             boost::asio::yield[ec]);
 158                     if (ec==boost::asio::error::eof)
 159                         break; //connection closed cleanly by peer
 160                     else if(ec)
 161                         throw boost::system::system_error(ec); //some other error
 162
 163                     // write some bytes asynchronously
 164                     boost::asio::async_write(
 165                             socket,
 166                             boost::asio::buffer(data,length),
 167                             boost::asio::yield[ec]);
 168                     if (ec==boost::asio::error::eof)
 169                         break; //connection closed cleanly by peer
 170                     else if(ec)
 171                         throw boost::system::system_error(ec); //some other error
 172                 }
 173             } catch(std::exception const& e){
 174                 std::cerr<<"Exception: "<<e.what()<<"\n";
 175             }
 176         }
 177
 178 In contrast to the previous example this one gives the impression of sequential
 179 code and local data (['data]) while using asynchronous operations
 180 (['async_read()], ['async_write()]). The algorithm is implemented in one
 181 function and error handling is done by one try-catch block.
 182
 183 [heading recursive descent parsing]
 184 Coroutines let you invert the flow of control so you can ask a recursive descent
 185 parser for parsed symbols.
 186
 187         class Parser{
 188            char next;
 189            std::istream& is;
 190            std::function<void(char)> cb;
 191
 192            char pull(){
 193                 return std::char_traits<char>::to_char_type(is.get());
 194            }
 195
 196            void scan(){
 197                do{
 198                    next=pull();
 199                }
 200                while(isspace(next));
 201            }
 202
 203         public:
 204            Parser(std::istream& is_,std::function<void(char)> cb_) :
 205               next(), is(is_), cb(cb_)
 206             {}
 207
 208            void run() {
 209               scan();
 210               E();
 211            }
 212
 213         private:
 214            void E(){
 215               T();
 216               while (next=='+'||next=='-'){
 217                  cb(next);
 218                  scan();
 219                  T();
 220               }
 221            }
 222
 223            void T(){
 224               S();
 225               while (next=='*'||next=='/'){
 226                  cb(next);
 227                  scan();
 228                  S();
 229               }
 230            }
 231
 232            void S(){
 233               if (std::isdigit(next)){
 234                  cb(next);
 235                  scan();
 236               }
 237               else if(next=='('){
 238                  cb(next);
 239                  scan();
 240                  E();
 241                  if (next==')'){
 242                      cb(next);
 243                      scan();
 244                  }else{
 245                      throw parser_error();
 246                  }
 247               }
 248               else{
 249                  throw parser_error();
 250               }
 251            }
 252         };
 253
 254         typedef boost::coroutines2::coroutine< char > coro_t;
 255
 256         int main() {
 257             std::istringstream is("1+1");
 258             // invert control flow
 259             coro_t::pull_type seq(
 260                     boost::coroutines2::fixedsize_stack(),
 261                     [&is](coro_t::push_type & yield) {
 262                         // create parser with callback function
 263                         Parser p( is,
 264                                   [&yield](char ch){
 265                                     // resume user-code
 266                                     yield(ch);
 267                                   });
 268                         // start recursive parsing
 269                         p.run();
 270                     });
 271
 272             // user-code pulls parsed data from parser
 273             // invert control flow
 274             for(char c:seq){
 275                 printf("Parsed: %c\n",c);
 276             }
 277         }
 278
 279 This problem does not map at all well to communicating between independent
 280 threads. It makes no sense for either side to proceed independently of the
 281 other. You want them to pass control back and forth.
 282
 283 There's yet another advantage to using coroutines. This recursive descent parser
 284 throws an exception when parsing fails. With a coroutine implementation, you
 285 need only wrap the calling code in try/catch.
 286
 287 With communicating threads, you would have to arrange to catch the exception
 288 and pass along the exception pointer on the same queue you're using to deliver
 289 the other events. You would then have to rethrow the exception to unwind the
 290 recursive document processing.
 291
 292 The coroutine solution maps very naturally to the problem space.
 293
 294
 295 [heading 'same fringe' problem]
 296
 297 The advantages of suspending at an arbitrary call depth can be seen
 298 particularly clearly with the use of a recursive function, such as traversal
 299 of trees.
 300 If traversing two different trees in the same deterministic order produces the
 301 same list of leaf nodes, then both trees have the same fringe.
 302
 303 [$../../../../libs/coroutine2/doc/images/same_fringe.png [align center]]
 304
 305 Both trees in the picture have the same fringe even though the structure of the
 306 trees is different.
 307
 308 The same fringe problem could be solved using coroutines by iterating over the
 309 leaf nodes and comparing this sequence via ['std::equal()]. The range of data
 310 values is generated by function ['traverse()] which recursively traverses the
 311 tree and passes each node's data value to its __push_coro__.
 312 __push_coro__ suspends the recursive computation and transfers the data value to
 313 the main execution context.
 314 __pull_coro_it__, created from __pull_coro__, steps over those data values and
 315 delivers them to  ['std::equal()] for comparison. Each increment of
 316 __pull_coro_it__ resumes ['traverse()]. Upon return from
 317 ['iterator::operator++()], either a new data value is available, or tree
 318 traversal is finished (iterator is invalidated).
 319
 320 In effect, the coroutine iterator presents a flattened view of the recursive
 321 data structure.
 322
 323         struct node{
 324             typedef std::shared_ptr<node> ptr_t;
 325
 326             // Each tree node has an optional left subtree,
 327             // an optional right subtree and a value of its own.
 328             // The value is considered to be between the left
 329             // subtree and the right.
 330             ptr_t       left,right;
 331             std::string value;
 332
 333             // construct leaf
 334             node(const std::string& v):
 335                 left(),right(),value(v)
 336             {}
 337             // construct nonleaf
 338             node(ptr_t l,const std::string& v,ptr_t r):
 339                 left(l),right(r),value(v)
 340             {}
 341
 342             static ptr_t create(const std::string& v){
 343                 return ptr_t(new node(v));
 344             }
 345
 346             static ptr_t create(ptr_t l,const std::string& v,ptr_t r){
 347                 return ptr_t(new node(l,v,r));
 348             }
 349         };
 350
 351         node::ptr_t create_left_tree_from(const std::string& root){
 352             /* --------
 353                  root
 354                  / \
 355                 b   e
 356                / \
 357               a   c
 358              -------- */
 359             return node::create(
 360                     node::create(
 361                         node::create("a"),
 362                         "b",
 363                         node::create("c")),
 364                     root,
 365                     node::create("e"));
 366         }
 367
 368         node::ptr_t create_right_tree_from(const std::string& root){
 369             /* --------
 370                  root
 371                  / \
 372                 a   d
 373                    / \
 374                   c   e
 375                -------- */
 376             return node::create(
 377                     node::create("a"),
 378                     root,
 379                     node::create(
 380                         node::create("c"),
 381                         "d",
 382                         node::create("e")));
 383         }
 384
 385         typedef boost::coroutines2::coroutine<std::string>   coro_t;
 386
 387         // recursively walk the tree, delivering values in order
 388         void traverse(node::ptr_t n,
 389                       coro_t::push_type& out){
 390             if(n->left) traverse(n->left,out);
 391             out(n->value);
 392             if(n->right) traverse(n->right,out);
 393         }
 394
 395         // evaluation
 396         {
 397             node::ptr_t left_d(create_left_tree_from("d"));
 398             coro_t::pull_type left_d_reader([&](coro_t::push_type & out){
 399                                                 traverse(left_d,out);
 400                                             });
 401
 402             node::ptr_t right_b(create_right_tree_from("b"));
 403             coro_t::pull_type right_b_reader([&](coro_t::push_type & out){
 404                                                 traverse(right_b,out);
 405                                              });
 406
 407             std::cout << "left tree from d == right tree from b? "
 408                       << std::boolalpha
 409                       << std::equal(begin(left_d_reader),
 410                                     end(left_d_reader),
 411                                     begin(right_b_reader))
 412                       << std::endl;
 413         }
 414         {
 415             node::ptr_t left_d(create_left_tree_from("d"));
 416             coro_t::pull_type left_d_reader([&](coro_t::push_type & out){
 417                                                 traverse(left_d,out);
 418                                             });
 419
 420             node::ptr_t right_x(create_right_tree_from("x"));
 421             coro_t::pull_type right_x_reader([&](coro_t::push_type & out){
 422                                                  traverse(right_x,out);
 423                                              });
 424
 425             std::cout << "left tree from d == right tree from x? "
 426                       << std::boolalpha
 427                       << std::equal(begin(left_d_reader),
 428                                     end(left_d_reader),
 429                                     begin(right_x_reader))
 430                       << std::endl;
 431         }
 432         std::cout << "Done" << std::endl;
 433
 434         output:
 435         left tree from d == right tree from b? true
 436         left tree from d == right tree from x? false
 437         Done
 438
 439
 440 [heading chaining coroutines]
 441
 442 This code shows how coroutines could be chained.
 443
 444         typedef boost::coroutines2::coroutine<std::string> coro_t;
 445
 446         // deliver each line of input stream to sink as a separate string
 447         void readlines(coro_t::push_type& sink,std::istream& in){
 448             std::string line;
 449             while(std::getline(in,line))
 450                 sink(line);
 451         }
 452
 453         void tokenize(coro_t::push_type& sink, coro_t::pull_type& source){
 454             // This tokenizer doesn't happen to be stateful: you could reasonably
 455             // implement it with a single call to push each new token downstream. But
 456             // I've worked with stateful tokenizers, in which the meaning of input
 457             // characters depends in part on their position within the input line.
 458             for(std::string line:source){
 459                 std::string::size_type pos=0;
 460                 while(pos<line.length()){
 461                     if(line[pos]=='"'){
 462                         std::string token;
 463                         ++pos;              // skip open quote
 464                         while(pos<line.length()&&line[pos]!='"')
 465                             token+=line[pos++];
 466                         ++pos;              // skip close quote
 467                         sink(token);        // pass token downstream
 468                     } else if (std::isspace(line[pos])){
 469                         ++pos;              // outside quotes, ignore whitespace
 470                     } else if (std::isalpha(line[pos])){
 471                         std::string token;
 472                         while (pos < line.length() && std::isalpha(line[pos]))
 473                             token += line[pos++];
 474                         sink(token);        // pass token downstream
 475                     } else {                // punctuation
 476                         sink(std::string(1,line[pos++]));
 477                     }
 478                 }
 479             }
 480         }
 481
 482         void only_words(coro_t::push_type& sink,coro_t::pull_type& source){
 483             for(std::string token:source){
 484                 if (!token.empty() && std::isalpha(token[0]))
 485                     sink(token);
 486             }
 487         }
 488
 489         void trace(coro_t::push_type& sink, coro_t::pull_type& source){
 490             for(std::string token:source){
 491                 std::cout << "trace: '" << token << "'\n";
 492                 sink(token);
 493             }
 494         }
 495
 496         struct FinalEOL{
 497             ~FinalEOL(){
 498                 std::cout << std::endl;
 499             }
 500         };
 501
 502         void layout(coro_t::pull_type& source,int num,int width){
 503             // Finish the last line when we leave by whatever means
 504             FinalEOL eol;
 505
 506             // Pull values from upstream, lay them out 'num' to a line
 507             for (;;){
 508                 for (int i = 0; i < num; ++i){
 509                     // when we exhaust the input, stop
 510                     if (!source) return;
 511
 512                     std::cout << std::setw(width) << source.get();
 513                     // now that we've handled this item, advance to next
 514                     source();
 515                 }
 516                 // after 'num' items, line break
 517                 std::cout << std::endl;
 518             }
 519         }
 520
 521         // For example purposes, instead of having a separate text file in the
 522         // local filesystem, construct an istringstream to read.
 523         std::string data(
 524             "This is the first line.\n"
 525             "This, the second.\n"
 526             "The third has \"a phrase\"!\n"
 527             );
 528
 529         {
 530             std::cout << "\nfilter:\n";
 531             std::istringstream infile(data);
 532             coro_t::pull_type reader(std::bind(readlines, _1, std::ref(infile)));
 533             coro_t::pull_type tokenizer(std::bind(tokenize, _1, std::ref(reader)));
 534             coro_t::pull_type filter(std::bind(only_words, _1, std::ref(tokenizer)));
 535             coro_t::pull_type tracer(std::bind(trace, _1, std::ref(filter)));
 536             for(std::string token:tracer){
 537                 // just iterate, we're already pulling through tracer
 538             }
 539         }
 540
 541         {
 542             std::cout << "\nlayout() as coroutine::push_type:\n";
 543             std::istringstream infile(data);
 544             coro_t::pull_type reader(std::bind(readlines, _1, std::ref(infile)));
 545             coro_t::pull_type tokenizer(std::bind(tokenize, _1, std::ref(reader)));
 546             coro_t::pull_type filter(std::bind(only_words, _1, std::ref(tokenizer)));
 547             coro_t::push_type writer(std::bind(layout, _1, 5, 15));
 548             for(std::string token:filter){
 549                 writer(token);
 550             }
 551         }
 552
 553         {
 554             std::cout << "\nfiltering output:\n";
 555             std::istringstream infile(data);
 556             coro_t::pull_type reader(std::bind(readlines,_1,std::ref(infile)));
 557             coro_t::pull_type tokenizer(std::bind(tokenize,_1,std::ref(reader)));
 558             coro_t::push_type writer(std::bind(layout,_1,5,15));
 559             // Because of the symmetry of the API, we can use any of these
 560             // chaining functions in a push_type coroutine chain as well.
 561             coro_t::push_type filter(std::bind(only_words,std::ref(writer),_1));
 562             for(std::string token:tokenizer){
 563                 filter(token);
 564             }
 565         }
 566
 567 [endsect]