Coroutine

The state of some types of calculations is very convenient to set by a place in the execution thread. For example, one of the sensors of normal random numbers generates a pair of uniform random numbers and, under certain conditions, turns it into a normal pair. There are two ways to display a table of normal numbers.

  // method 1: outside the sensor
 // sensor
 alg Entry point ()
   endless cycle
     x: = uniform Random ()
     y: = uniform Random ()
     if the pair (x, y) is “good”
       (a, b): = convert B Normal (x, y)
       if not tab (a) or not tab (b)
         Stop

 // tab
 i: = 0
 alg tab (a: fractional): boolean
   if i> = N
     return FALSE
   i: = i + 1
   print a
   return TRUE 

  // method 2: outside tab
 // sensor
 memorized: = NaN
 alg sensor (): fractional
   if memorized - not NaN
     a: = memorized
     memorized: = NaN
   otherwise
     cycle
       x: = uniform Random ()
       y: = uniform Random ()
     before (x, y) - a “good” couple
     (a, memorized): = convert B to Normal (x, y)
   return a

 // tab
 alg Entry point ()
   for i: = 1..N
     output sensor () 

It can be seen that the algorithm that is "outside" will be more compact, because it has one more way to store its state - the position in the execution thread (that is, the instruction counter ). The one inside is forced by the exit to maintain this position in temporary variables (“i” in the first case and “remembered” in the second).

If we assume that each algorithm will have its own counter of commands, and the yield command can transfer information from the algorithm to the algorithm, then we can take the best of both methods.

  // on coroutines
 // sensor
 alg sensor ()
   endless cycle
     x: = uniform Random ()
     y: = uniform Random ()
     if the pair (x, y) is “good”
       (a, b): = convert B Normal (x, y)
       if not yield (Entry point, a) or not yield (Entry point, b)
         Stop
 
 // tab
 alg Entry point ()
   for i: = 1..N
     output ( yield (sensor, TRUE))
   yield (sensor, FALSE) // the sensor algorithm will end

If we have two processor cores and a non-blocking synchronization , we get a great way to parallelize the generation of numbers and the output of the table. However, if there is no one or the other, nothing good will happen: most of the time it will take context switching .

However, you can transfer control from module to module as in Windows 3.x , without multithreading and synchronization: the yield command (“yield”) overwrites the processor register file , at the same time transferring some information from the module to the module. Without two stacks, in the general case it is impossible, however, some compilers ( C # ) in the simplest cases are able to automatically convert the code to method 2.

Coroutines are more generalized than routines . A subprogram always has one entry point, a coroutine has a start entry point and a sequence of returns and subsequent entry points located inside them. A subprogram can return only once, a coroutine can return control several times. The runtime of a subprogram is determined by the LIFO principle (the last subprogram called is completed first), the runtime of a coroutine is determined by its use and necessity.

Here is a simple example where a coroutine can be useful. Suppose you want to implement a relationship between a consumer and a manufacturer, where one part of the program produces elements and puts them in the queue , and the other removes them and uses them. The following code does this:

  var q: = new queue

  coroutine produce
     loop
         while q is not full
             create some new items
             add the items to q
         yield to consume

  coroutine consume
     loop
         while q is not empty
             remove some items from q
             use the items
         yield to produce

Each coroutine transfers control using the yield directive. Despite the fact that this example is often used to illustrate the principles of multi-threaded code, the implementation of the described method of transferring control does not require several threads: the yield directive can be implemented as a direct transfer of control to another coroutine - inside one execution thread.

For a coroutine, you can have several input and output points, and any subprogram can be implemented as a coroutine. Indeed, according to Knuth , "a subprogram is a special case of a coroutine."

Each time a subroutine is called, execution starts at the starting point. Similarly, the first time a coroutine is called, execution starts at the starting point of the coroutine. However, in subsequent calls, execution continues from the point of the last return.

The subroutine returns a value only once; the return of several values ​​requires using the collection as the return value. If in some languages ​​this is acceptable, for example Forth and Pearl , then other languages, for example C , support only one return value, and therefore it is necessary to return a reference to the collection. In contrast, a coroutine can return a result several times, returning a plurality of values ​​requires only calling the coroutine several times.
Coroutines that return many values ​​are often called generators .

Subprograms require one stack for operation, which can be allocated at the beginning of program execution.
A coroutine, having the ability to call other coroutines of the same level as it is, is better implemented using continuations . Then it may be necessary to allocate additional stacks, and therefore this is (mainly) implemented in high-level languages ​​with support for the garbage collector . Creating coroutines can be conditionally effective only when using pre-allocated stacks and caching previously created ones.

Coroutines can be useful for implementing the following:

• A state machine inside one subroutine, where the state is determined by the current entry / exit point (increases the readability of the text).
• The model of actors .
• Generators that are useful for I / O and generalized traversal of data structures .

• AngelScript
• C # (yield and await statements)
• Forth (initially does not support, but support is easily implemented by means of the Fort itself)
• Io
• JavaScript (starting with ES6 )
• Julia ^[1]
• Lua
• Modula-2
• Perl 5 ( Coro )
• Perl 6
• Python
• Ruby
• Simula
• Tcl (starting from 8.6)
• PHP (since 5.5)
• Scala
• Kotlin
• Go
• C ++ (since C ++ 20 ) ^[2]

Since extensions are used to implement coroutines, languages ​​that support them can easily implement coroutine support.

Most of today's popular programming languages , including C and derivatives ( C ++ up to version C ++ 20 ^[2] ), do not have direct support for coroutines in a language or standard library (this is due, for the most part, to the requirements for the stack implementation of routines).

In a situation where coroutines, as a natural way to implement components, are not available, a typical solution is to create coroutines using a set of Boolean flags and other variable states to support the external state between calls. Conditions inside the code lead to the execution of various sequences of commands during successive calls in accordance with the values ​​of state variables. Another typical solution is to implement the state machine yourself using a large switch statement . Such implementations are difficult to support and maintain.

Threads are a suitable alternative for coroutines in most modern designs. Streams provide opportunities for controlling the interaction of "simultaneously" executing sections of code. Therefore, it is a solution to large and complex problems, it includes powerful integrated capabilities and has the attendant complexity for learning. However, despite other alternatives, threads are widely available in the C environment, are close to most programmers , and are usually implemented, documented, and maintained.

Various attempts to implement coroutines in C have had varying success. Most noticeable:

• Coroutines in C by Simon Tatham ( Simon Tatham ) (Eng.) - using the " Duff device "
• Protothreads
• Portable Coroutine Library (PCL )
• Coro (English)
• Reentrant coroutines in C ++
• Boost.Coroutine

In other languages:

• C # uses coroutines as internal implementation details of the yield (sequence generator function) and await (asynchronous function) statements
• Python
  • PEP 342 (English) ;
  • Greenlets (English) ;
  • gevent
• Io
  • Coroutine
• Ruby
  • Coroutine (Japanese) ;
• Perl
  • Coro (English) ;
• Lua has built-in coroutine support;
• Functional programming languages often implement coroutines, for example Scheme , Lisp , Haskell .

In the Windows API, “fibers” ( fibers , a pun based on the fact that the thread of execution is thread , “thread”) are coroutines.

• Iterator
• Channel
• Generator

• Donald Knut . The Art of Programming, Volume 1. Basic Algorithms = The Art of Computer Programming, vol. 1. Fundamental Algorithms. - 3rd ed. - M .: "Williams" , 2006. - S. 720. - ISBN 0-201-89683-4 . Section 1.4.2: Coroutines, pp. 229–236