Koroutine

In der Informatik sind Koroutinen (auch Coroutinen) eine Verallgemeinerung des Konzepts einer Prozedur oder Funktion. Der prinzipielle Unterschied zwischen Koroutinen und Prozeduren ist, dass Koroutinen ihren Ablauf unterbrechen und später wieder aufnehmen können, wobei sie ihren Status beibehalten.

Koroutinen stellen also eine hohe Abstraktionsebene einer Funktion, oder Prozedur dar, die einen Lebenszyklus besitzt. Dadurch ist ein hoher Grad an Parallelisierung möglich. Funktionen oder Prozeduren sind in diesem Fall wörtlich zu nehmen, da eine Koroutine keine Abhängigkeit zu einem externen Zustand haben sollte. Die Funktionsparameter der Koroutine allein müssen vollständig genügen, damit im Funktionskörper die Berechnung korrekt durchlaufen kann.

Unter den ältesten Programmiersprachen, die Koroutinen unterstützen, sind Simula oder Modula-2. Auch moderne Sprachen wie Python kennen ähnliche Konzepte. In einigen weit verbreiteten Sprachen wie C oder Java gestaltet sich die Implementierung jedoch schwierig. Der Begriff selbst stammt von Melvin Conway, der ihn 1963 in einer Veröffentlichung über Compilerbau^[1] benutzte. Donald Knuth bezeichnet Prozeduren als Spezialfall von Koroutinen.^[2]

Koroutinen können generell in Sprachen, die sie nicht direkt unterstützen, simuliert werden. Dabei ist ein sprachunabhängiger Weg, vergleichbares Verhalten zu programmieren, die Benutzung von Threads, die wechselseitig ablaufen und nach Abgabe der Kontrolle abwarten, bis sie die Kontrolle zurückerhalten. Eine andere Möglichkeit, die in jeder Programmiersprache funktioniert, ist das Aufrollen von Koroutinen. Hierbei muss die Koroutine ihren Status selbst vorhalten (beispielsweise in einer globalen Variablen) und dann bei jedem Aufruf an die entsprechende Stelle ihres Codes springen. Da es in vielen Programmiersprachen nicht möglich ist, in die Mitte eines Blocks (beispielsweise in eine Schleife) zu springen, müssen solche Konstrukte in so einem Fall ebenfalls durch Simulationen ersetzt werden.

Die Programmiersprache Python unterstützt Koroutinen über die asyncio API. Seit Python 3.5 gibt es hierzu die Schlüsselwörter await und async.^[3] Eine Koroutine wird mittels async def definiert. await wartet auf die Fertigstellung einer Koroutine und gibt während der Wartezeit die Ausführungskontrolle zurück. Koroutinen können nebenläufig ausgeführt werden und ermöglichen dadurch ein kooperatives Multitasking.

import asyncio
import time

async def waitprint(s):
    # time.sleep() würde den Thread blockieren, await asyncio.sleep() nicht
    await asyncio.sleep(1)
    print(s)

async def main():
    # Führe Koroutinen nebenläufig aus
    task1 = asyncio.create_task(waitprint('Eins'))
    task2 = asyncio.create_task(waitprint('Zwei'))
    task3 = asyncio.create_task(waitprint('Drei'))
    await asyncio.gather(task1, task2, task3)

start = time.time()
asyncio.run(main())
print('Dauer:', time.time() - start, 's') # etwas über eine Sekunde

Eine andere Möglichkeit ist die Verwendung von Generatoren als Koroutine. Dabei kann mit dem Schlüsselwort yield der Ablauf einer Funktion vorübergehend unterbrochen werden. Intern wird jedoch bei Aufruf einer solchen Generator-Funktion ein Objekt erzeugt, das den Status vorhält. Realisiert wird dies, indem bei Abgabe der Kontrolle das vollständige Stackframe zwischengespeichert und bei Wiederaufnahme wiederhergestellt wird. Es ist möglich, einem Generator bei der Objektinstanziierung Parameter zu übergeben.

# 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 wurde die Syntax des yield-Schlüsselworts erweitert, um kooperatives Multitasking zu ermöglichen.^[4] In Python 3 folgten Erweiterungen zur Nutzung von Generatoren als Koroutinen, unter anderem durch die Einführung der Schlüsselwörter async und await. In Version 3.11 wurde diese Funktionalität wieder entfernt.^[5] Generatoren mit dem Schlüsselwort yield sind weiterhin Teil der Sprache, für die Schlüsselwörter async und await ist jedoch die asyncio API vorgesehen.

C unterstützt weder Koroutinen noch vergleichbare Konstrukte. Es gibt jedoch verschiedene Möglichkeiten, sie zu simulieren. Eine davon geht auf Simon Tatham zurück und ist auch wegen der Verwendung in dem populären SSH-Client PuTTY bekannt.^[6]

#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;
}

Da der Status in globalen Variablen vorgehalten wird, kann im Unterschied zu Python von jeder Koroutine jedoch immer nur eine Instanz ablaufen. Deswegen wird der Status in einem Thread-local Storage gespeichert, damit dennoch mehrere Instanzen von Koroutinen parallel ablaufen können, wenn man mehrere Threads gestartet hat.

Boost.Coroutine, offizieller Bestandteil der Boost-Libraries, ermöglicht die Verwendung von Koroutinen in C++. Im Gegensatz zu Python sind die Koroutinen von Boost.Coroutine jeweils mit einem Stack assoziiert. Somit sind Umschaltungen und Sprünge aus Unterfunktionen heraus möglich. Durch die interne Verwendung von Boost.Context werden ARM, MIPS, PowerPC, SPARC und X86 auf POSIX, Mac OS X und Windows unterstützt. C++ 20 unterstützt nativ die Implementierung von Koroutinen.

#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;
}

Mit der Version C++20 wurden Koroutinen in die Sprache integriert.

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 unterstützt gut in objektorientierter Umgebung nutzbare Koroutinen unter dem Namen Fibers. Die Umschaltung geschieht intern durch eine einfache Vertauschung des Stackpointers und ist bisher nur für x86 (Windows und Posix) und PowerPC verfügbar.

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!
}

Vorteile sieht man besonders deutlich bei Verwendung von rekursiven Funktion wie beispielsweise bei der Traversierung von Binärbäumen.

Tool Command Language unterstützt gut nutzbare Koroutinen bereits im Sprachkern, wie grundsätzlich bei Tcl plattformunabhängig.^[7]

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 unterstützt Koroutinen als eingebautes Sprachelement (nur 64-bit version).

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

(do 10
   (println (fibo)) )

// Die `sequence`-Function erzeugt eine Koroutine.
// Mit dem Aufrufen von `yield` wird der Sequenz ein Wert bereitgestellt und die
// Koroutine unterbrochen.
fun fibonacci(): Sequence<Int> = sequence {
    var last = 0
    var current = 1

    while (true) {
        yield(current)
        val next = last + current
        last = current
        current = next
    }
}

// Durch `take(7)` wird die Koroutine insgesamt siebenmal unterbrochen und
// sechsmal fortgesetzt.
fun main() {
    println(fibonacci().take(7).toList())
    // [1, 1, 2, 3, 5, 8, 13]
}

1. ↑ M.E. Conway: Design of a separable transition-diagram compiler. Communications of the ACM, Band 6, Nr. 7, Juli 1963.
2. ↑ Donald Knuth, Fundamental Algorithms. Third Edition. Addison-Wesley, 1997, ISBN 0-201-89683-4. Section 1.4.2: Coroutines, S. 193–200.
3. ↑ https://peps.python.org/pep-0492/
4. ↑ PEP 342
5. ↑ Coroutines and Tasks. Abschnitt Generator-based Coroutines. 2. Februar 2023, abgerufen am 2. Februar 2023. 
6. ↑ Simon Tatham: Coroutines in C
7. ↑ Erläutert werden sie auf der zugehörigen Manual Page zu coroutine.