ceph/src/boost/libs/coroutine/doc/intro.qbk

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