1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.79.1"> 7<link rel="home" href="../index.html" title="Chapter 1. Coroutine"> 8<link rel="up" href="../index.html" title="Chapter 1. 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 © 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> 189
