... & Kontext: Verzögerte Ausführung

"Konsole & Kontext" ist eine gemeinsame Serie von Golo Roden und Michael Wiedeking, in der sich die beiden regelmäßig mit Konzepten der (funktionalen) Programmierung beschäftigen. Während "Konsole & …" die praktische Anwendung dieser Konzepte in JavaScript und Node.js zeigt, erläutert "... & Kontext" deren jeweiligen eher theoretischen Hintergrund.

Was macht man eigentlich, wenn man einen Satz Zahlen braucht, aber man keine Ahnung hat, wie viele davon? Na ja, man schreibt eine Generator, der peu à peu sämtliche Elemente liefert. Das ist beispielsweise im Falle einer Sequenz zufälliger Zahlen trivial:

class RandomIntGenarator implements IntGenerator {
    int getNext() {
        return Random.nextInt();
    }
}

Dieser Generator hat möglicherweise einen Zustand, wenn die Zahlen nicht ganz so zufällig sind und doch irgendwie aufeinander aufbauen. Liefert man etwa in einem Generator alle positiven ganzen Zahlen, muss man ja wissen, welche Zahl zuletzt geliefert wurde. Also muss man sich diese merken.

class PositiveIntGenarator implements IntGenerator {
    int i = 0;
    int getNext() {
        if (i == Integer.MAX_VALUE) {
            throw new NoSuchElementException();
        }
        return ++i;
    }
}

Im Gegensatz zu dem RandomIntGenarator ist der PositiveIntGenarator aber begrenzt. Ob es dabei in Ordnung ist, in diesem Fall eine Exception zu werfen, hängt von den Anforderungen ab, die an die getNext-Methode gestellt werden.

Wie dem auch sei, es gibt für diese Art der Generatoren auch eine nebeneffektfreie Variante, wenn man die Verantwortung für die Speicherung des letzten Werts einfach abgibt und bei Bedarf dem Generator übergibt.

class PositiveIntGenarator implements StatelessIntGenerator {
    int getNext(int last) {
        return last + 1;
    }
}

Natürlich ist es nicht immer so einfach. Ganz besonders dann nicht, wenn man zum Generieren Hilfe von einer rekursiven Struktur braucht. Wie schon beim letzten Mal erwähnt, bieten sich für das Traversieren durch rekursive, baumartige Strukturen gleichermaßen rekursive Funktionen an. Hier tut sich dann aber das Problem auf, wie denn die rekursiv gefundenen Werte an den Generator übermittelt werden können.

Der nahe liegende Versuch, erst die Rekursion dazu zu nutzen, um alle Elemente etwa in einer Liste zu speichern, um dann dem Generator die einzelnen Elemente nacheinander zukommen zu lassen, ist leider zum Scheitern verurteilt, wenn es sich um eine unendliche Baumstruktur handelt. Man benötigt also eine Methode, die es ermöglicht, die einzelnen Elemente nur nach Bedarf zu liefern, ohne dabei die Rekursion verlassen zu müssen.

Eine syntaktisch elegante Methode dafür ist das Markieren etwa mit yield. Traversiert man eine rekursive Struktur, so kann man alle in Frage kommenden Elemente mit einem yield markieren. Das markierte Element wird dann beim getNext zur Verfügung gestellt, ohne dass die Rekursion verlassen werden muss.

void traverse(Node node) {
    if (node.isLeaf()) {
        LeafNode leaf = (LeafNode) node;
        yield leaf.value;
    } else {
        BinaryNode binode = (BinaryNode) node;
        traverse(binode.left);
        traverse(binode.right)
    }
}

So, oder so ähnlich, könnte ein yield-Konstrukt aussehen. In C# ist das beispielsweise – ungeachtet des Umstands, dass man dort yield return schreiben muss – leider nicht ganz so elegant möglich. Dort muss man nämlich zunächst einmal kundtun, welcher Art die Elemente sind, die man geliefert wissen will. Eine Funktion muss vergleichbar zu obigem Generator einen IEnumerator liefern, der aber zusätzlich noch Auskunft darüber gibt, ob weitere Elemente vorhanden sind. Dieser wird in C# indirekt über ein IEnumerable bereitgestellt, das auf Wunsch den eigentlichen IEnumerator liefert. Bemerkenswert ist dann, dass die Funktion als Ergebnis ein IEnumerable<T> liefert, obwohl immer ein Element vom Typ T mit yield return zurückgegeben werden muss.

IEnumerable<T> Traverse(Node node) {
    if (node.isLeaf()) {
        LeafNode leaf = (LeafNode) node;
        yield return leaf.value;
    } else {
        BinaryNode binode = (BinaryNode) node;
        for (T v in Traverse(binode.left)) {
            yield return v;
        }
        for (T v in Traverse(binode.right)) {
            yield return v;
        }
    }
}

Falls dieses Beispiel syntaktisch nicht ganz korrekt ist, so möge man mir das verzeihen, da ich gerade keinen C#-Compiler zur Hand hatte.

Diese zusätzliche Komplexität ist dem Umstand geschuldet, dass in C# alle Funktionen, die ein yield enthalten, in eine Zustandsmaschine umgewandelt werden, die sich bei jedem yield den aktuellen Zustand merkt, um die Routine verlassen zu können und um beim nächsten Aufruf an exakt dieser Stelle fortsetzen zu können. Dazu werden insbesondere auch die Rekursionen "flachgeklopft".

Dieses Flachklopfen erklärt auch, warum beim Traversieren der Kinder left und right nicht einfach deren IEnumerables zurückgegeben werden können, sondern nur deren einzelnen Elemente. Das bedeutet auch tatsächlich, dass bei jedem rekursiven Aufruf eine neue Zustandsmaschine erzeugt wird, die in den Schleifen abgearbeitet und anschließend verworfen wird (falls das jemanden, der am Nanosekundensyndrom leidet, interessiert).

Unabhängig von der Implementierung sind aber die Vorteile nicht zu unterschätzen. Selbst unbegrenzte rekursive Strukturen werden nur so weit durchlaufen, wie es nötig ist. Diese sehr "faule" Sicht (engl. lazy) auf die Strukturen erlaubt es also, auch mit unendlich großen Strukturen und Strömen zu arbeiten, ohne auf Ergebnisse verzichten zu müssen.

Dabei versteht es sich natürlich von selbst, dass es sich dabei durchaus lohnt, die Anzahl der Durchläufe zu begrenzen; andernfalls müsste man dann ja doch noch unangemessen lange auf die Ergebnisse warten. ()