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.
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]
Implementierung
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.
Python
Die Programmiersprache Python unterstützt die Implementation von Koroutinen mit dem verwandten Konstrukt der Generatoren. 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.
# 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 Generatoren zum kooperativen Multitasking ähnlich wie mit async und await zu nutzen.[3] In Version 3.7 wurden die Schlüsselwörter async und await hinzugefügt. In Version 3.10 wird die Funktionalität entfernt, Generatoren als Koroutinen zu nutzen.[4] Es ist möglich Generatoren Parameter zu senden.
C
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.[5]
#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.
C++
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 stackful, sodass mit jeder Koroutine ein Stack assoziiert ist. 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.
#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 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.
Tcl
Tool Command Language unterstützt gut nutzbare Koroutinen bereits im Sprachkern, wie grundsätzlich bei Tcl plattformunabhängig.[6]
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 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)) )
Einzelnachweise
- M.E. Conway: Design of a separable transition-diagram compiler. Communications of the ACM, Band 6, Nr. 7, Juli 1963.
- Donald Knuth, Fundamental Algorithms. Third Edition. Addison-Wesley, 1997, ISBN 0-201-89683-4. Section 1.4.2: Coroutines, S. 193–200.
- PEP 342
- Simon Tatham: Coroutines in C
- Erläutert werden sie auf der zugehörigen Manual Page zu coroutine.