libs/coroutine/doc/html/coroutine/intro.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Introduction</title>
   5 <link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
   7 <link rel="home" href="../index.html" title="Chapter&#160;1.&#160;Coroutine">
   8 <link rel="up" href="../index.html" title="Chapter&#160;1.&#160;Coroutine">
   9 <link rel="prev" href="overview.html" title="Overview">
  10 <link rel="next" href="motivation.html" title="Motivation">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="overview.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="motivation.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
  27 <a name="coroutine.intro"></a><a class="link" href="intro.html" title="Introduction">Introduction</a>
  28 </h2></div></div></div>
  29 <h4>
  30 <a name="coroutine.intro.h0"></a>
  31       <span class="phrase"><a name="coroutine.intro.definition"></a></span><a class="link" href="intro.html#coroutine.intro.definition">Definition</a>
  32     </h4>
  33 <p>
  34       In computer science routines are defined as a sequence of operations. The execution
  35       of routines forms a parent-child relationship and the child terminates always
  36       before the parent. Coroutines (the term was introduced by Melvin Conway <a href="#ftn.coroutine.intro.f0" class="footnote" name="coroutine.intro.f0"><sup class="footnote">[1]</sup></a>), are a generalization of routines (Donald Knuth <a href="#ftn.coroutine.intro.f1" class="footnote" name="coroutine.intro.f1"><sup class="footnote">[2]</sup></a>. The principal difference between coroutines and routines is that
  37       a coroutine enables explicit suspend and resume of its progress via additional
  38       operations by preserving execution state and thus provides an <span class="bold"><strong>enhanced
  39       control flow</strong></span> (maintaining the execution context).
  40     </p>
  41 <h4>
  42 <a name="coroutine.intro.h1"></a>
  43       <span class="phrase"><a name="coroutine.intro.how_it_works"></a></span><a class="link" href="intro.html#coroutine.intro.how_it_works">How
  44       it works</a>
  45     </h4>
  46 <p>
  47       Functions foo() and bar() are supposed to alternate their execution (leave
  48       and enter function body).
  49     </p>
  50 <p>
  51       <span class="inlinemediaobject"><img src="../../../../../libs/coroutine/doc/images/foo_bar.png" align="middle" alt="foo_bar"></span>
  52     </p>
  53 <p>
  54       If coroutines were called exactly like routines, the stack would grow with
  55       every call and would never be popped. A jump into the middle of a coroutine
  56       would not be possible, because the return address would be on top of stack
  57       entries.
  58     </p>
  59 <p>
  60       The solution is that each coroutine has its own stack and control-block (<span class="emphasis"><em>boost::contexts::fcontext_t</em></span>
  61       from <span class="bold"><strong>Boost.Context</strong></span>). Before the coroutine
  62       gets suspended, the non-volatile registers (including stack and instruction/program
  63       pointer) of the currently active coroutine are stored in the coroutine's control-block.
  64       The registers of the newly activated coroutine must be restored from its associated
  65       control-block before it is resumed.
  66     </p>
  67 <p>
  68       The context switch requires no system privileges and provides cooperative multitasking
  69       convenient to C++. Coroutines provide quasi parallelism. When a program is
  70       supposed to do several things at the same time, coroutines help to do this
  71       much more simply and elegantly than with only a single flow of control. The
  72       advantages can be seen particularly clearly with the use of a recursive function,
  73       such as traversal of binary trees (see example 'same fringe').
  74     </p>
  75 <h4>
  76 <a name="coroutine.intro.h2"></a>
  77       <span class="phrase"><a name="coroutine.intro.characteristics"></a></span><a class="link" href="intro.html#coroutine.intro.characteristics">characteristics</a>
  78     </h4>
  79 <p>
  80       Characteristics <a href="#ftn.coroutine.intro.f2" class="footnote" name="coroutine.intro.f2"><sup class="footnote">[3]</sup></a> of a coroutine are:
  81     </p>
  82 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
  83 <li class="listitem">
  84           values of local data persist between successive calls (context switches)
  85         </li>
  86 <li class="listitem">
  87           execution is suspended as control leaves coroutine and is resumed at certain
  88           time later
  89         </li>
  90 <li class="listitem">
  91           symmetric or asymmetric control-transfer mechanism; see below
  92         </li>
  93 <li class="listitem">
  94           first-class object (can be passed as argument, returned by procedures,
  95           stored in a data structure to be used later or freely manipulated by the
  96           developer)
  97         </li>
  98 <li class="listitem">
  99           stackful or stackless
 100         </li>
 101 </ul></div>
 102 <p>
 103       Coroutines are useful in simulation, artificial intelligence, concurrent programming,
 104       text processing and data manipulation, supporting the implementation of components
 105       such as cooperative tasks (fibers), iterators, generators, infinite lists,
 106       pipes etc.
 107     </p>
 108 <h4>
 109 <a name="coroutine.intro.h3"></a>
 110       <span class="phrase"><a name="coroutine.intro.execution_transfer_mechanism"></a></span><a class="link" href="intro.html#coroutine.intro.execution_transfer_mechanism">execution-transfer
 111       mechanism</a>
 112     </h4>
 113 <p>
 114       Two categories of coroutines exist: symmetric and asymmetric coroutines.
 115     </p>
 116 <p>
 117       An asymmetric coroutine knows its invoker, using a special operation to implicitly
 118       yield control specifically to its invoker. By contrast, all symmetric coroutines
 119       are equivalent; one symmetric coroutine may pass control to any other symmetric
 120       coroutine. Because of this, a symmetric coroutine <span class="emphasis"><em>must</em></span>
 121       specify the coroutine to which it intends to yield control.
 122     </p>
 123 <p>
 124       <span class="inlinemediaobject"><img src="../../../../../libs/coroutine/doc/images/foo_bar_seq.png" align="middle" alt="foo_bar_seq"></span>
 125     </p>
 126 <p>
 127       Both concepts are equivalent and a fully-general coroutine library can provide
 128       either symmetric or asymmetric coroutines. For convenience, Boost.Coroutine
 129       provides both.
 130     </p>
 131 <h4>
 132 <a name="coroutine.intro.h4"></a>
 133       <span class="phrase"><a name="coroutine.intro.stackfulness"></a></span><a class="link" href="intro.html#coroutine.intro.stackfulness">stackfulness</a>
 134     </h4>
 135 <p>
 136       In contrast to a stackless coroutine a stackful coroutine can be suspended
 137       from within a nested stackframe. Execution resumes at exactly the same point
 138       in the code where it was suspended before. With a stackless coroutine, only
 139       the top-level routine may be suspended. Any routine called by that top-level
 140       routine may not itself suspend. This prohibits providing suspend/resume operations
 141       in routines within a general-purpose library.
 142     </p>
 143 <h4>
 144 <a name="coroutine.intro.h5"></a>
 145       <span class="phrase"><a name="coroutine.intro.first_class_continuation"></a></span><a class="link" href="intro.html#coroutine.intro.first_class_continuation">first-class
 146       continuation</a>
 147     </h4>
 148 <p>
 149       A first-class continuation can be passed as an argument, returned by a function
 150       and stored in a data structure to be used later. In some implementations (for
 151       instance C# <span class="emphasis"><em>yield</em></span>) the continuation can not be directly
 152       accessed or directly manipulated.
 153     </p>
 154 <p>
 155       Without stackfulness and first-class semantics, some useful execution control
 156       flows cannot be supported (for instance cooperative multitasking or checkpointing).
 157     </p>
 158 <div class="footnotes">
 159 <br><hr style="width:100; text-align:left;margin-left: 0">
 160 <div id="ftn.coroutine.intro.f0" class="footnote"><p><a href="#coroutine.intro.f0" class="para"><sup class="para">[1] </sup></a>
 161         Conway, Melvin E.. "Design of a Separable Transition-Diagram Compiler".
 162         Commun. ACM, Volume 6 Issue 7, July 1963, Article No. 7
 163       </p></div>
 164 <div id="ftn.coroutine.intro.f1" class="footnote"><p><a href="#coroutine.intro.f1" class="para"><sup class="para">[2] </sup></a>
 165         Knuth, Donald Ervin (1997). "Fundamental Algorithms. The Art of Computer
 166         Programming 1", (3rd ed.)
 167       </p></div>
 168 <div id="ftn.coroutine.intro.f2" class="footnote"><p><a href="#coroutine.intro.f2" class="para"><sup class="para">[3] </sup></a>
 169         Moura, Ana Lucia De and Ierusalimschy, Roberto. "Revisiting coroutines".
 170         ACM Trans. Program. Lang. Syst., Volume 31 Issue 2, February 2009, Article
 171         No. 6
 172       </p></div>
 173 </div>
 174 </div>
 175 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 176 <td align="left"></td>
 177 <td align="right"><div class="copyright-footer">Copyright &#169; 2009 Oliver Kowalke<p>
 178         Distributed under the Boost Software License, Version 1.0. (See accompanying
 179         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 180       </p>
 181 </div></td>
 182 </tr></table>
 183 <hr>
 184 <div class="spirit-nav">
 185 <a accesskey="p" href="overview.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="motivation.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
 186 </div>
 187 </body>
 188 </html>