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ück erhalten. 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. Die Wiederaufnahme geschieht durch Aufruf der Methode next() des Generator-Objekts.

def fib():
       """ Fibonacci-Folge als Koroutine """
       i1, i2 = 0, 1
       while True:
               yield i2
               i1, i2 = i2, i1+i2
 
zahlen = fib()
for i in range(10):
       print zahlen.next()

In Python 2.5 wurde die Syntax des yield-Schlüsselworts erweitert, um die Übergabe von Parametern in die andere Richtung zu ermöglichen. Damit können Koroutinen vollständig in Python implementiert werden^[3].

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^[4]. In diesem Ansatz wird ausgenutzt, dass die case-Statements bei C nicht auf derselben Ebene stehen müssen wie das zugehörige switch-Statement:

#include <stdio.h>
 
// Fibonacci-Folge als Coroutine
int fib()
{
    static int i1, i2 = 1, state;
    int tmp;
 
    switch (state) {
    case 0:
        while (1) {
            state = 1;
            return i2;
 
    case 1:                  // Gehoert zu switch(state)
            tmp = i2;
            i2 = i1 + i2;
            i1 = tmp;
        }                 // while
    }                             // switch
}
 
int main()
{
    int i;
 
    for (i = 0; i < 10; ++i)
        printf("%d\n", fib());
    return 0;
}

Diese Konstruktion lässt sich durch Benutzung von Macros optisch etwas besser präsentieren. Wenn der Status in einer globalen Variablen vorgehalten wird, kann im Unterschied zu Python von jeder Koroutine jedoch immer nur eine Instanz ablaufen. Wird der Status hingegen in einer Thread-local Storage gespeichert, können dennoch mehrere Instanzen von Koroutinen parallel ablaufen.

D

D unterstützt gut in objektorientierter Umgebung nutzbare Koroutinen über die alternative Standardbibliothek Tango 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 tango.core.Thread;
import tango.io.Stdout;
 
class FibonacciGenerator {
 
        private Fiber fiber;
        private uint fibonacci = 1;
 
        private void run() {
                uint oldFibonacci = 0;
                uint tmp;
 
                while (true) {
                        Fiber.yield();
                        tmp = fibonacci;
                        fibonacci += oldFibonacci;
                        oldFibonacci = tmp;
                }
        }
 
        this() {
                fiber = new Fiber(&run);
        }
 
        uint next() {
                fiber.call();
                return fibonacci;
        }
}
 
void main() {
        FibonacciGenerator fibGen = new FibonacciGenerator();
 
        for (uint i = 0; i < 10; i++) {
                Stdout.format("{}\n", fibGen.next());
        }
}

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

Referenzen

1. ↑ M.E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, Vol. 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. ↑ Simon Tatham: Coroutines in C