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:intro Introduction] 9 10[heading Definition] 11 12In computer science routines are defined as a sequence of operations. The 13execution of routines forms a parent-child relationship and the child terminates 14always before the parent. Coroutines (the term was introduced by Melvin 15Conway [footnote Conway, Melvin E.. "Design of a Separable Transition-Diagram Compiler". 16Commun. ACM, Volume 6 Issue 7, July 1963, Article No. 7]), 17are a generalization of routines (Donald Knuth [footnote Knuth, Donald Ervin (1997). 18"Fundamental Algorithms. The Art of Computer Programming 1", (3rd ed.)]). 19The principal difference between coroutines and routines 20is that a coroutine enables explicit suspend and resume of its progress via 21additional operations by preserving execution state and thus provides an 22[*enhanced control flow] (maintaining the execution context). 23 24 25[heading How it works] 26 27Functions foo() and bar() are supposed to alternate their execution (leave and 28enter function body). 29 30[$../../../../libs/coroutine2/doc/images/foo_bar.png [align center]] 31 32If coroutines were called exactly like routines, the stack would grow with 33every call and would never be popped. A jump into the middle of a coroutine 34would not be possible, because the return address would be on top of 35stack entries. 36 37The solution is that each coroutine has its own stack and control-block 38(__fcontext__ from __boost_context__). 39Before the coroutine gets suspended, the non-volatile registers (including stack 40and instruction/program pointer) of the currently active coroutine are stored in 41the coroutine's control-block. 42The registers of the newly activated coroutine must be restored from its 43associated control-block before it is resumed. 44 45The context switch requires no system privileges and provides cooperative 46multitasking convenient to C++. Coroutines provide quasi parallelism. 47When a program is supposed to do several things at the same time, coroutines 48help to do this much more simply and elegantly than with only a single flow of 49control. 50The advantages can be seen particularly clearly with the use of a recursive 51function, such as traversal of binary trees (see example 'same fringe'). 52 53 54[heading characteristics] 55Characteristics [footnote Moura, Ana Lucia De and Ierusalimschy, Roberto. 56"Revisiting coroutines". ACM Trans. Program. Lang. Syst., Volume 31 Issue 2, 57February 2009, Article No. 6] of a coroutine are: 58 59* values of local data persist between successive calls (context switches) 60* execution is suspended as control leaves coroutine and is resumed at certain time later 61* symmetric or asymmetric control-transfer mechanism; see below 62* first-class object (can be passed as argument, returned by procedures, 63 stored in a data structure to be used later or freely manipulated by 64 the developer) 65* stackful or stackless 66 67Coroutines are useful in simulation, artificial intelligence, concurrent 68programming, text processing and data manipulation, supporting 69the implementation of components such as cooperative tasks (fibers), iterators, 70generators, infinite lists, pipes etc. 71 72 73[heading execution-transfer mechanism] 74Two categories of coroutines exist: symmetric and asymmetric coroutines. 75 76An asymmetric coroutine knows its invoker, using a special operation to 77implicitly yield control specifically to its invoker. By contrast, all symmetric 78coroutines are equivalent; one symmetric coroutine may pass control to any 79other symmetric coroutine. Because of this, a symmetric coroutine ['must] 80specify the coroutine to which it intends to yield control. 81 82[$../../../../libs/coroutine2/doc/images/foo_bar_seq.png [align center]] 83 84Both concepts are equivalent and a fully-general coroutine library can provide 85either symmetric or asymmetric coroutines. 86 87 88[heading stackfulness] 89In contrast to a stackless coroutine a stackful coroutine can be suspended 90from within a nested stackframe. Execution resumes at exactly the same point 91in the code where it was suspended before. 92With a stackless coroutine, only the top-level routine may be suspended. Any 93routine called by that top-level routine may not itself suspend. This prohibits 94providing suspend/resume operations in routines within a general-purpose library. 95 96[heading first-class continuation] 97A first-class continuation can be passed as an argument, returned by a 98function and stored in a data structure to be used later. 99In some implementations (for instance C# ['yield]) the continuation can 100not be directly accessed or directly manipulated. 101 102Without stackfulness and first-class semantics, some useful execution control 103flows cannot be supported (for instance cooperative multitasking or 104checkpointing). 105 106[endsect] 107
