Coroutine

In computer science , coroutines (also known as coroutines ) are a generalization of the concept of a procedure or function . The main difference between coroutines and procedures is that coroutines can interrupt their flow and resume later while maintaining their status.

Among the oldest programming languages that support coroutines are Simula or Modula-2 . Modern languages ​​like Python also have similar concepts. However, in some widely used languages ​​such as C or Java , implementation is difficult. The term itself comes from Melvin Conway, who used it in 1963 in a publication on compiler construction. Donald Knuth calls procedures a special case of coroutines.

implementation

Coroutines can generally be simulated in languages ​​that do not directly support them. A language-independent way of programming comparable behavior is the use of threads that run reciprocally and wait after control has been relinquished until they regain control. Another way that works in any programming language is by rolling up coroutines. Here, the coroutine must keep its status itself (for example in a global variable) and then jump to the appropriate place in its code with each call. Since it is not possible in many programming languages to jump to the middle of a block (for example in a loop ), such constructs must also be replaced by simulations in such a case.

python

The Python programming language supports the implementation of coroutines with the related construct of the generators . The process of a function can be temporarily interrupted with the keyword yield . However, when such a generator function is called, an object is generated internally that holds the status. This is achieved by temporarily storing the complete stack frame when control is handed over and restoring it when resuming.

# Fibonaccifolge als Generator
def fibonacci(limit):
    first, second = 0, 1

    for _ in range(limit):
        first, second = second, first + second
        yield first

for number in fibonacci(10):
    print(number)

In Python 2.5, the syntax of the yield keyword was extended to use generators for cooperative multitasking similar to that with asyncand await. In version 3.7 the keywords asyncand were awaitadded. In version 3.10 the functionality to use generators as coroutines has been removed. It is possible to send generator parameters.

C.

C does not support coroutines or similar constructs. However, there are several ways to simulate them. One of them goes back to Simon Tatham and is also known for its use in the popular SSH client PuTTY .

#include <stdio.h>
#include <threads.h>

thread_local int first = 0, second = 1;

// Fibonaccifolge als Koroutine
int fibonacci() {
    int swap = first;
    first = second;
    second += swap;

    return first;
}

void reset_fibonacci() {
    first = 0;
    second = 1;
}

int main() {
    for (int i = 0; i < 10; ++i)
        printf("%d\n", fibonacci());

    reset_fibonacci();

    return 0;
}

Since the status is held in global variables, in contrast to Python, only one instance of each coroutine can run. Therefore, the status is saved in a thread-local storage, so that several instances of coroutines can still run in parallel if several threads have been started.

C ++

Boost.Coroutine, an official part of the Boost Libraries , enables the use of coroutines in C ++. In contrast to Python, the coroutines of Boost.Coroutine are stackful, so that a stack is associated with each coroutine. This enables switchings and jumps from sub-functions. By using Boost.Context internally, ARM, MIPS, PowerPC, SPARC and X86 are supported on POSIX, Mac OS X and Windows.

#include <boost/coroutine2/all.hpp>
#include <iostream>

using coro_t = boost::coroutines2::coroutine<int>;

int main() {
    coro_t::pull_type source([](coro_t::push_type& sink) {
        int first = 0, second = 1;

        for (int i = 0; i < 10; ++i) {
            int swap = first;
            first = second;
            second += swap;

            sink(first);
        }
    });

    for (auto i: source)
        std::cout << i << std::endl;

    return 0;
}

C #

using System;
using System.Collections.Generic;

public class MainClass {
    public static IEnumerable<int> fibonacci(int limit) {
        int first = 0, second = 1;

        for (int i = 0; i < limit; ++i) {
            int swap = first;
            first = second;
            second += swap;

            yield return first;
        }
    }

    public static void Main(string[] args) {
        foreach (int i in fibonacci(10))
            Console.WriteLine(i);
    }
}

D.

D supports coroutines under the name Fibers that can be used well in an object-oriented environment. The switchover takes place internally by simply swapping the stack pointer and is currently only available for x86 (Windows and Posix) and PowerPC.

import core.thread: Fiber;
import std.stdio: write;
import std.range: iota;

/**
 * Iterates over `range` and applies
 * the function `Fnc` to each element x
 * and returns it in `result`. Fiber yields
 *after each application.
**/
void fiberedRange(alias Fnc, R, T)(R range, ref T result) {
    while (!range.empty) {
        result = Fnc(range.front);
        Fiber.yield();
        range.popFront;
    }
}

void main() {
    int squareResult, cubeResult;
    
    // Create a fiber that is initialized
    // with a delegate that generates a square
    // range.
    auto squareFiber = new Fiber({
        fiberedRange!(x => x*x)(iota(1,11), squareResult);
    });
    
    // .. and here is which creates cubes!
    auto cubeFiber = new Fiber({
        fiberedRange!(x => x * x * x)(iota(1,9), cubeResult);
    });

    // if state is TERM the fiber has finished
    // executing its associated function.
    squareFiber.call();
    cubeFiber.call();
    while (squareFiber.state != Fiber.State.TERM &&
        cubeFiber.state != Fiber.State.TERM) {
        write(squareResult, " ", cubeResult);
        squareFiber.call();
        cubeFiber.call();
        write("\n");
    }

    // squareFiber could still be run because
    // it has not finished yet!
}

The advantages are particularly evident when using recursive functions such as traversing binary trees .

Tcl

Tool Command Language already supports usable coroutines in the language core, as is basically platform-independent with Tcl.

proc f {} {
    yield [set a 0]
    yield [set b 1]
    
    while 1 {
        yield [incr a $b]
        lassign [list $b $a] a b
    }
}

coroutine fib f

for {set i 0} {$i < 10} {incr i} {
    puts [fib]
}

PicoLisp

PicoLisp supports coroutines as a built-in language element (64-bit version only).

(de fibo ()
   (co 'fibo
      (let (A 0  B 1)
         (loop
            (yield
               (swap 'B (+ (swap 'A B) B)))))))

(do 10
   (println (fibo)) )

Individual evidence

1. ^ ME Conway: Design of a separable transition diagram compiler. Communications of the ACM, Volume 6, No. 7, July 1963.
2. ^ Donald Knuth, Fundamental Algorithms. Third edition. Addison-Wesley, 1997, ISBN 0-201-89683-4 . Section 1.4.2: Coroutines , pp. 193-200.
3. ↑ PEP 342
4. ↑ [1]
5. ↑ Simon Tatham: Coroutines in C
6. ↑ They are explained on the corresponding manual page for coroutine .