| [/ |
| Copyright Oliver Kowalke 2009. |
| 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:intro Introduction] |
| |
| [heading Definition] |
| |
| In computer science routines are defined as a sequence of operations. The |
| execution of routines forms a parent-child relationship and the child terminates |
| always before the parent. Coroutines (the term was introduced by Melvin |
| Conway [footnote Conway, Melvin E.. "Design of a Separable Transition-Diagram Compiler". |
| Commun. ACM, Volume 6 Issue 7, July 1963, Article No. 7]), |
| are a generalization of routines (Donald Knuth [footnote Knuth, Donald Ervin (1997). |
| "Fundamental Algorithms. The Art of Computer Programming 1", (3rd ed.)]. |
| The principal difference between coroutines and routines |
| is that a coroutine enables explicit suspend and resume of its progress via |
| additional operations by preserving execution state and thus provides an |
| [*enhanced control flow] (maintaining the execution context). |
| |
| |
| [heading How it works] |
| |
| Functions foo() and bar() are supposed to alternate their execution (leave and |
| enter function body). |
| |
| [$../../../../libs/coroutine/doc/images/foo_bar.png [align center]] |
| |
| If coroutines were called exactly like routines, the stack would grow with |
| every call and would never be popped. A jump into the middle of a coroutine |
| would not be possible, because the return address would be on top of |
| stack entries. |
| |
| The solution is that each coroutine has its own stack and control-block |
| (__fcontext__ from __boost_context__). |
| Before the coroutine gets suspended, the non-volatile registers (including stack |
| and instruction/program pointer) of the currently active coroutine are stored in |
| the coroutine's control-block. |
| The registers of the newly activated coroutine must be restored from its |
| associated control-block before it is resumed. |
| |
| The context switch requires no system privileges and provides cooperative |
| multitasking convenient to C++. Coroutines provide quasi parallelism. |
| When a program is supposed to do several things at the same time, coroutines |
| help to do this much more simply and elegantly than with only a single flow of |
| control. |
| The advantages can be seen particularly clearly with the use of a recursive |
| function, such as traversal of binary trees (see example 'same fringe'). |
| |
| |
| [heading characteristics] |
| Characteristics [footnote Moura, Ana Lucia De and Ierusalimschy, Roberto. |
| "Revisiting coroutines". ACM Trans. Program. Lang. Syst., Volume 31 Issue 2, |
| February 2009, Article No. 6] of a coroutine are: |
| |
| * values of local data persist between successive calls (context switches) |
| * execution is suspended as control leaves coroutine and is resumed at certain time later |
| * symmetric or asymmetric control-transfer mechanism; see below |
| * first-class object (can be passed as argument, returned by procedures, |
| stored in a data structure to be used later or freely manipulated by |
| the developer) |
| * stackful or stackless |
| |
| Coroutines are useful in simulation, artificial intelligence, concurrent |
| programming, text processing and data manipulation, supporting |
| the implementation of components such as cooperative tasks (fibers), iterators, |
| generators, infinite lists, pipes etc. |
| |
| |
| [heading execution-transfer mechanism] |
| Two categories of coroutines exist: symmetric and asymmetric coroutines. |
| |
| An asymmetric coroutine knows its invoker, using a special operation to |
| implicitly yield control specifically to its invoker. By contrast, all symmetric |
| coroutines are equivalent; one symmetric coroutine may pass control to any |
| other symmetric coroutine. Because of this, a symmetric coroutine ['must] |
| specify the coroutine to which it intends to yield control. |
| |
| [$../../../../libs/coroutine/doc/images/foo_bar_seq.png [align center]] |
| |
| Both concepts are equivalent and a fully-general coroutine library can provide |
| either symmetric or asymmetric coroutines. For convenience, Boost.Coroutine |
| provides both. |
| |
| |
| [heading stackfulness] |
| In contrast to a stackless coroutine a stackful coroutine can be suspended |
| from within a nested stackframe. Execution resumes at exactly the same point |
| in the code where it was suspended before. |
| With a stackless coroutine, only the top-level routine may be suspended. Any |
| routine called by that top-level routine may not itself suspend. This prohibits |
| providing suspend/resume operations in routines within a general-purpose library. |
| |
| [heading first-class continuation] |
| A first-class continuation can be passed as an argument, returned by a |
| function and stored in a data structure to be used later. |
| In some implementations (for instance C# ['yield]) the continuation can |
| not be directly accessed or directly manipulated. |
| |
| Without stackfulness and first-class semantics, some useful execution control |
| flows cannot be supported (for instance cooperative multitasking or |
| checkpointing). |
| |
| [endsect] |