Konsole & …: Verzögerte Ausführung

Inhaltsverzeichnis

"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.

Um alle Primzahlen innerhalb eines Intervalls mit einem naiven Algorithmus zu berechnen, genügen einige wenige Funktionen. Die erste Funktion, getFactors, ermittelt alle positiven Teiler der ihr übergebenen Zahl:

var getFactors = function (value) {
  var factors = [];

  for (var guess = 1; guess <= value; guess++) {
    if (value % guess === 0) {
      factors.push(guess);
    }
  }

  return factors;
};

Danach überprüft die Funktion isPrime, ob die ihr übergebene Zahl genau zwei positive Teiler besitzt, was der Definition einer Primzahl gemäß Wikipedia entspricht:

"Eine Primzahl ist eine natürliche Zahl, die genau zwei natürliche Zahlen als Teiler hat."

Selbstverständlich ist das Vorgehen unnötig langsam, weshalb bereits kleine Änderungen die Leistung deutlich steigern könnten. Für das Ziel dieses Blogeintrags sei das jedoch vernachlässigt:

var isPrime = function (value) {
  return getFactors(value).length === 2;
};

Die Funktion getPrimes ruft isPrime schließlich in einer Schleife auf und ermittelt so alle Primzahlen innerhalb des ihr übergebenen Intervalls:

var getPrimes = function (min, max) {
  var primes = [];

  for (var guess = min; guess <= max; guess++) {
    if (isPrime(guess)) {
      primes.push(guess);
    }
  }

  return primes;
};

Der Aufruf dieser Funktion gibt die gesuchten Primzahlen als Array zurück:

var primes = getPrimes(1, 20);
// => [ 2, 3, 5, 7, 11, 13, 17, 19 ]

Obwohl das Ergebnis rein mathematisch gesehen korrekt ist, weist das Vorgehen zusätzlich zu der bereits erwähnten bewussten Einfachheit des Algorithmus einige grundlegende Probleme auf. Diese werden sichtbar, wenn man für die Parameter min und max weitaus höhere Zahlen als 1 und 20 angibt.

Ruft man getPrimes beispielsweise mit den Zahlen 10.000.000 und 10.000.500 auf, benötigt die Funktion auf einem MacBook Pro, das mit einem Intel Core i7 mit 2,2 GHz und 8 ]GByte RAM ausgestattet ist, bereits knapp 30 Sekunden. Die Ausgabe hingegen erfolgt dann innerhalb von Sekundenbruchteilen.

Wählt man ein niedriger angesiedeltes, aber inhaltlich größeres Intervall, erfolgt die Berechnung zwar schneller – belegt aber auch mehr Speicher: Die Berechnung aller Primzahlen im Intervall von 1 bis 100.000 belegt über 9 MByte Speicher, zuvor waren es nur knapp 6 MByte. Das entspricht einem Zuwachs von rund 50 Prozent.

Letztlich lassen sich all diese Problem auf eine gemeinsame Ursache zurückführen: Das Array, das die Primzahlen enthält, muss stets vollständig berechnet werden, bevor man darauf zugreifen kann. Je größer das übergebene Intervall ist, desto langwieriger und speicheraufwendiger ist die Berechnung.

Berechnungen unterbrechen

Wäre es nicht praktisch, die Berechnung regelmäßig unterbrechen zu können? Wäre dies möglich, könnte man jede Primzahl direkt nach ihrer Berechnung ausgeben und erste Ergebnisse so weitaus zügiger darstellen. Außerdem würde der Speicherbedarf sinken, und der Anwender hätte zudem die Möglichkeit, die Berechnung zu einem beliebigen Zeitpunkt abzubrechen.

Genau dies ermöglicht das yield-Schlüsselwort, das in Version 6 von ECMAScript spezifiziert wird: Wie auch das Schlüsselwort return gibt yield einen Wert an den Aufrufer zurück, beendet im Gegensatz zu jenem die Funktion aber nicht, sondern pausiert sie lediglich. Ein erneuter Aufruf setzt die Funktion anschließend an der Stelle fort, an der sie mit yield unterbrochen wurde.

Allerdings erlaubt JavaScript den Einsatz von yield ausschließlich in speziellen Funktionen, den sogenannten Generatoren. Um einen solchen zu erzeugen, benötigt man eine Generatorfunktion, die mit dem zusätzlichen Kennzeichner * hinter dem function-Schlüsselwort definiert wird. Der Aufruf der Generatorfunktion gibt dann den eigentlichen Generator zurück:

var createGenerator = function * () { /* ... */ },
    generator = createGenerator();

Der erzeugte Generator verfügt über eine Funktion next, mit der sich die Ausführung starten und nach einer Unterbrechung fortsetzen lässt. Das Ergebnis eines Aufrufs von next ist stets ein Objekt, das außer dem eigentlichen Ergebnis noch ein zusätzliches Flag enthält, das angibt, ob weitere Aufrufe des Generators möglich sind:

var getSquares = function * () {
  yield 1;
  yield 4;
  yield 9;
  yield 16;
};

var squares = getSquares();
squares.next(); // => { value: 1, done: false }
squares.next(); // => { value: 4, done: false }
squares.next(); // => { value: 9, done: false }
squares.next(); // => { value: 16, done: false }
squares.next(); // => { value: undefined, done: true }

Um die generierten Werte bequem in einer Schleife durchlaufen zu können, kennt JavaScript ab ECMAScript 6 die for..of-Schleife: Sie erwartet einen Generator und liefert ähnlich der for..in-Schleife in jedem Durchlauf einen weiteren generierten Wert:

for (var square of getSquares()) {
  console.log(square);
}
// => 1, 4, 9, 16

Bemerkenswert ist die Verzahnung zwischen der getSquares-Funktion und der for..of-Schleife: Anders als im eingangs gewählten Primzahlenbeispiel gibt das Programm die Quadratzahlen direkt nach dem Aufruf von yield aus. Selbstverständlich muss man die einzelnen Werte nicht von Hand angeben, sondern kann diese auch berechnen.

Auf die gleiche Art lässt sich auch die Berechnung der Primzahlen anpassen. Hierzu muss lediglich die Funktion getPrimes durch eine passende Generatorfunktion ersetzt werden:

var getPrimes = function * (min, max) {
  for (var guess = min; guess <= max; guess++) {
    if (isPrime(guess)) {
      yield guess;
    }
  }
};

Nun lässt sich diese Funktion mit einer for..of-Schleife verwenden. Sie gibt die Primzahlen direkt nach deren Berechnung aus. Obwohl die Berechnung aller Primzahlen gleich lang dauert wie zuvor, wirkt sie schneller. Außerdem belegt die Funktion nun weniger Speicher:

for (var prime of getPrimes(1, 100000)) {
  console.log(prime);
}
// => 2, 3, 5, 7, 11, ...

Unendliche Generatoren

Besonders interessant ist die Möglichkeit, unendliche Generatorfunktionen zu schreiben: Da ein Generator immer nur auf Aufforderung aktiv wird, muss es nicht zwingend ein Abbruchkriterium geben. Daher könnte man beispielsweise auf die Angabe der Intervallgrenzen verzichten, um unendlich viele Primzahlen zu berechnen:

var getPrimes = function * () {
  for (var guess = 1;; guess++) {
    if (isPrime(guess)) {
      yield guess;
    }
  }
};

Diese Möglichkeit lässt sich auch für andere Zwecke geschickt ausnutzen. Beispielsweise kann man auf diese Art leicht einen Zufallszahlengenerator entwickeln, der bei jedem Aufruf eine neue Zufallszahl zurückgibt. Auch zur Simulation von Sensordaten oder zur Berechnung von unendlichen Reihen sind Generatorfunktionen geeignet.

Bislang unterscheidet sich das yield-Schlüsselwort in JavaScript kaum von der Implementierung in anderen Sprachen, beispielsweise in C#. Sieht man von der Syntax ab, lässt sich der Code quasi eins zu eins übertragen:

public IEnumerable<int> GetPrimes()
{
  for (int guess = 1;; guess++)
  {
    if (IsPrime(guess))
    {
      yield return guess;
    }
  }
)

Ein wesentlicher Unterschied zu C# besteht allerdings darin, dass der Aufruf von next in JavaScript die Angabe eines Parameters zulässt, der als Rückgabewert von yield verarbeitet wird. Das ermöglicht eine bidirektionale Kommunikation zwischen Generator und aufrufendem Code, um beispielsweise den weiteren Ablauf des Generators zu steuern.

Außerdem steht zusätzlich zur Funktion next auch die Funktion throw zur Verfügung, die das externe Auslösen einer Ausnahme innerhalb des Generators ermöglicht. Das eröffnet interessante Möglichkeiten zur Ablaufsteuerung.

Kompatibilität beachten

Da zur Verwendung von yield & Co. allerdings ECMAScript 6 erforderlich ist, ist die Unterstützung für Generatorfunktionen noch nicht so verbreitet, wie es wünschenswert wäre. Node.js unterstützt sie ab Version 0.11, wobei beim Aufruf auf der Kommandozeile zusätzlich der Parameter --harmony anzugeben ist:

$ node --harmony app.js

Anschließend lassen sich Generatorfunktionen aber wie beschrieben verwenden. Auch die for..of-Schleife steht nach Angabe des --harmony-Flags zur Verfügung.

Zusätzlich zu den in dieser Folge gezeigten Möglichkeiten erlaubt das yield-Schlüsselwort, Koroutinen in Node.js zu implementieren. Sie bieten eine syntaktisch komfortable Alternative zu Callbacks, um asynchronen Code zu schreiben. Wie das funktioniert, wird das Thema der nächsten Folge sein.

tl;dr: yield ist das Schlüsselwort in JavaScript, das die Implementierung von Generatorfunktionen ermöglicht. Es hilft nicht nur, Speicherplatz zu sparen, sondern kann auch die Reaktivität von Anwendungen erhöhen. Da es sich um eine Funktion aus ECMAScript 6 handelt, ist die Unterstützung allerdings noch nicht so weit verbreitet wie es wünschenswert wäre. ()