Iteratoren und Generatoren

Introduced in JavaScript 1.7

Es kommt bei der Programmierung immer wieder vor, dass man Elemente einer Kollektion verarbeiten möchte. Bei JavaScirpt gibt es für das Iterieren über Elemente einer solchen Ansammlung verschiedene Möglichkeiten. Angefangen von einfachen for- und for each-Schleifen über map(), filter()bis zu Array-Comprehensions. Iteratoren und Generatoren, die mit JavaScript 1.7 eingeführt wurden, verankern das Prinzip der Iteration direkt im Kern der Sprache und verfügen über Mechanismen für die Beeinflussung des Verhaltens von for...in und for each-Schleifen.

Iteratoren

Ein Iterator ist ein Objekt, das darüber bescheid weiß, wie der Zugriff auf die Elemente nacheinander stattfinden muss, während es sich die aktuelle Position innerhalb der Sequenz merkt. Bei JavaScript ist ein Iterator ein Objekt, das eine Methode next() zur Verfügung stellt, welche das nächste Element der Sequenz zurückliefert. Diese Methode kann optional eine StopIteration-Exception auslösen, wenn das Ende der Sequenz erreicht ist.

Einmal erstellt kann ein Iterator-Objekt zum einen explizit angesprochen werden, indem die Methode next() wiederholt aufgerufen wird. Zum anderen kann der Zugriff auch implizit stattfinden, indem die Schleifenkonstrukte for...in und for each von JavaScript eingesetzt werden.

Einfache Iteratoren für Objekte und Arrays können mit der Funktion  Iterator() erstellt werden:

var lang = { name: 'JavaScript', birthYear: 1995 };
var it = Iterator(lang);

Nachdem der Iterator einmal initalisiert wurde, kann die Methode next() aufgerufen werden, um Schlüssel-Wert-Paare von dem Objekt abzurufen:

var pair = it.next(); // Das Paar ist: ["name", "JavaScript"]
pair = it.next(); // Das Paar ist: ["birthYear", 1995]
pair = it.next(); // Eine StopIteration-Exception wird ausgeworfen

Anstatt der direkten Benutzung der next()-Methode kann auch eine for...in-Schleife zum Einsatz kommen. Die Schleife bricht automatisch ab, wenn die StopIteration-Exception ausgelöst wird.

var it = Iterator(lang);
for (var pair in it)
  print(pair); // gibt [key, value] Paare aus

Möchte man nur über die Schlüssel des Objekts iterieren, übergibt man ein zweites Argument true an die Iterator()-Funktion:

var it = Iterator(lang, true);
for (var key in it)
  print(key); // gibt jeden Schlüssel aus

Ein Vorteil bei der Benutzung der Iterator()-Funktion ist, dass die Inhalte von benutzerdefinierten Eigenschaften, die Object.prototype hinzugefügt wurden, in der Sequenz nicht enthalten sind.

Iterator() kann auch auf Arrays angewendet werden:

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (var pair in it)
  print(pair); // gibt jedes [index, language]-Paar aus

Genau wie bei Objekten kann man auch hier true als zweiten Parameter übergeben, um nur über die Schlüssel zu iteriert:

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs, true);
for (var i in it)
  print(i); // prints 0, then 1, then 2

Darüber hinaus ist es möglich, mit Hilfe des let-Schlüsselworts die Index-Positionen und Werte an blockbegrenzte Variablen innerhalb der for-Schleife zuzuweisen.

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (let [i, lang] in it)
 print(i + ': ' + lang); // gibt "0: JavaScript" aus, usw.

Iteratoren selbst definieren

Einige Ojekte repräsentieren Kollektionen von Elementen, über die auf spezielle Weise iteriert werden sollte.

  • Beim Iterieren über ein Bereichsobjekt sollten die Nummern in diesem Bereich eine nach der anderen ausgegeben werden.
  • Die Knoten eines Baums können mit Hilfe der Tiefensuche oder Breitensuche durchquert werden.
  • Beim Iterieren über ein Objekt, welches die Ergebnisse einer Datenbankabfrage enthält, sollten die Reihen eine nach der anderen zurückgegeben werden, auch wenn der ganze Satz nicht in ein einzelnes Array geladen wurde.
  • Ein Iterator für eine unenedliche mathematische Sequenz (z. B. die Fibonnacci-Sequenz) sollte in der Lage sein, ein Ergebnis nach dem anderen auszugeben, ohne dass eine Datenstruktur mit unendlicher Länge erstellt werden muss.

JavaScript ermöglicht das Schreiben von Code mit selbstdefinierter Iterationslogik und das verknüpfen dieser Logik mit einem Objekt.

Wir erstellen z. B. ein einfaches Range-Objekt, das einen unteren und oberen Wert zur Begrenzung entgegennimmt:

function Range(low, high){
  this.low = low;
  this.high = high;
}

Anschließend erstellen wir einen selbstdefinierten Iterator, der eine Sequenz von Ganzzahlen ausgeben kann, die zwischen den Begrenzungswerten liegen. Dem Iterator-Interface muss eine next()-Methode hinzugefügt werden, die entweder ein Element der Sequenz zurückgibt oder eine StopIteration Ausnahme auswirft.

function RangeIterator(range){
  this.range = range;
  this.current = this.range.low;
}
RangeIterator.prototype.next = function(){
  if (this.current > this.range.high)
    throw StopIteration;
  else
    return this.current++;
};

Unser RangeIterator wird mit einer Range-Instanz instanziert und besitzt eine eigene Eigenschaft current, um sich die aktuelle Position in der Sequenz zu merken.

Abschließend muss Range noch eine spezielle Methode __iterator__ hinzugefügt werden, um den RangeIterator mit dem Range-Objekt zu verknüpfen. Diese wird beim Versuch über eine Range-Instanz zu iterieren aufgerufen und sollte eine Instanz von RangeIterator zurückgeben, womit die Iterator-Logik implementiert wurde.

Range.prototype.__iterator__ = function(){
  return new RangeIterator(this);
};

Nachdem wir unseren selbstdefinierten Iterator angekoppelt haben, können wir wie folgt über eine range-Instanz interieren:

var range = new Range(3, 5);
for (var i in range)
  print(i); // prints 3, then 4, then 5 in sequence

Generatoren: ein besserer Weg zur Erstellung von Iteratoren

Während selbstdefiniert Iteratoren ein nützliches Werkzeug sind, muss bei ihrer Erstellung sehr auf sorgfältiges Programmieren geachtet werden, da der interne Zustand explizit instandgehalten werden muss. Generatoren stellen eine beachtenswerte Alternative dar: Sie erlauben die Definition eines iterativen Algorithmus über eine einzelne Funktion, die ihren Zustand behält.

Ein Generator ist eine spezielle Art von Funktion, die wie eine Fabrikanlage für Iteratoren arbeitet. Eine Funktion wird zu einem Generator, wenn sie eine oder mehrere yield-Ausdrücke enthält.

Hinweis: Das yield-Schlüsselwort ist bei Codeblöcke in HTML-Dokumenten nur verwendebar, wenn der Code innerhalb eines <script type="application/javascript;version=1.7"> Blocks (oder höhere Version) steht. XUL-Script-Tags haben ohne diese spezielle Angabe Zugriff auf dieses Feature.

Beim Aufruf einer Generatorfunktion wird der Code der Funktion nicht einfach ausgeführt, sondern ein Generator-Iterator-Objekt zurückgegeben. Bei jedem Aufruf der next()-Methode des Generator-Iterators wird dann der Funktionscode bis zum yield-Ausdruck ausgeführt und das Ergebnis zurückgegeben. Ist das Ende der Funktion oder eine return-Anweisung erreicht, wird eine StopIteration Ausnahme ausgeworfen.

Folgendes Beispiel veranschaulicht diesen Ablauf:

function simpleGenerator(){
  yield "first";
  yield "second";
  yield "third";
  for (var i = 0; i < 3; i++)
    yield i;
}

var g = simpleGenerator();
print(g.next()); // Ausgabe: "first"
print(g.next()); // Ausgabe: "second"
print(g.next()); // Ausgabe: "third"
print(g.next()); // Ausgabe: 0
print(g.next()); // Ausgabe: 1
print(g.next()); // Ausgabe: 2
print(g.next()); // StopIteration wird ausgeworfen

Eine Generatorfunktion kann direkt als __iterator__-Methode einer Klasse verwendet werden. Damit wird die Menge des Codes, der für die Erzeugung von selbstdefinierten Iteratoren nötig ist, stark reduziert.

Hier noch mal Range unter Einsatz eines Generators:

function Range(low, high){
  this.low = low;
  this.high = high;
}
Range.prototype.__iterator__ = function(){
  for (var i = this.low; i <= this.high; i++)
    yield i;
};
var range = new Range(3, 5);
for (var i in range)
  print(i); // gibt 3, dann 4, dann 5 in Reihe aus

Nicht alle Generatoren terminieren. Es kann auch ein Generator erstellt werden, der eine unendliche Folge repräsentiert. Mit folgendem Generator wird die Fibonacci-Folge implementiert: jedes Element ist die Summe der beiden vorherigen Elemente.

function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    yield current;
  }
}

var sequence = fibonacci();
print(sequence.next()); // 1
print(sequence.next()); // 1
print(sequence.next()); // 2
print(sequence.next()); // 3
print(sequence.next()); // 5
print(sequence.next()); // 8
print(sequence.next()); // 13

Generatorfunktionen können Argumente entgegennehmen, welche beim ersten Aufruf der Funktion eingebunden werden. Mit einer return-Anweisung können Generatoren abgebrochen werden (wodurch eine  StopIteration ausgelöst wird). Die folgende Abwandlung von fibonacci() nimmt eine optinale Begrenzungszahl als Argument entgegen und bricht ab, sobald diese Grenze erreicht ist.

function fibonacci(limit){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    if (limit && current > limit)
      return;
    yield current;
  }
}

Erweiterte Generatoren

Generatoren berechnen ihre Werte bei der Anforderung. Dies erlaubt die effiziente Erzeugung von Folgen, die aufwändig zu berechnen sind. Sogar unendliche Sequenzen können von Generatoren repräsentiert werden.

Zusätzlich zur Methode next() besitzen Generator-Iterator-Objekte eine send()-Methode, die zur Veränderung des internen Zustands benutzt werden kann. Ein Wert, der an send() übergeben wird, wird als Ergebnis des letzten Aufrufs des yield-Ausdrucks interpretiert. Zum Starten eines Generators muss die next()-Methode mindestens einmal aufgerufen werden, bevor über die send()-Methode ein bestimmter Wert gesetzt werden kann.

Hier noch mal der Fibonacci-Generator unter Einsatz der send()-Methode zum Zurücksetzen der Sequenz:

function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    var reset = yield current;
    if (reset){
        fn1 = 1;
        fn2 = 1;
    }
  }
}

var sequence = fibonacci();
print(sequence.next());     // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3
print(sequence.next());     // 5
print(sequence.next());     // 8
print(sequence.next());     // 13
print(sequence.send(true)); // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3
Achtung: Es ist interessant zu wissen, dass der Aufruf von send(undefined) äquivalent zum Aufruf von next() ist. Allerdings führt der Aufruf von send() zu Beginn nach Erstellung eines neu generierten Objekts mit einem anderen Wert als undefined zu einem TypeError Ausnahmefehler.

Man kann einen Generator mit dem Aufruf seiner throw()-Methode dazu zwingen, eine Ausnahme auszuwerfen. Dabei übergibt man den Wert, der ausgeworfen soll an die Methode. Diese Ausnahme wird im Kontext der aktuellen Unterbrechung des Generators ausgeworfen, als ob das yield, das an dieser Stelle unterbrochen wurde, eine throw Wert Anweisung gewesen wäre.

Wird ein yield bei der Ausführung der ausgeworfenen Ausnahme nicht erreicht, dann verbreitet sich die Ausnahme durch den Aufruf bis zu throw() nach oben und nachfolgende Aufrufe von next() resultieren in einem Auswurf einer StopIteration Ausnahme.

Generatoren besitzen außerdem eine close()-Methode, welche den Generator dazu zwngt, sich selbst zu schließen. Dies hat folgende Effekte:

  1. Alle finally-Abschnitte, die in der Generatorfunktion aktiv sind, werden ausgeführt.
  2. Wenn in einem finally-Abschnitt eine andere Ausnahme als StopIteration ausgeworfen wird, wird diese an den Aufrufer der close()-Methode übertragen.
  3. Der Generator terminiert.

Generator-Ausdrücke

Introduced in JavaScript 1.8

Ein großer Nachteil bei Array-Comprehensions ist, dass ein neues Array im Speicher erzeugt werden muss. Wenn die Eingabe der Comprehension nur ein kleines Array ist, spielt der hierdurch zusätzlich erzeugte Overhead keine Rolle. Ist die Eingabe allerdings ein großes Array oder ein aufwendiger (oder auch unendlicher) Generator, kann dieser Umstand zum Problem werden.

Generatoren ermöglichen die Erzeugung von Sequenzen on-demand; Elemente werden bei der Anforderung, dann wenn sie gebraucht werden, erstellt. Generator-Ausdrücke sind den Array-Comprehensions syntaktisch ähnlich, jedoch werden runde statt eckigen Klammern verwendet (und  for...in anstatt for each...in). Generator-Ausdrücke erzeugen keine Arrays sondern Generatoren, welche die "träge" Anfertigung von Sequenzen ermöglichen. Man kann sie sich als Kurzschreibweise für die Erzeugung von Generatoren vorstellen.

Angenommen man hat einen Iterator it, der über eine große Anzahl von Ganzzahlen iteriert und man will einen neuen Iterator erstellen, der über die doppelten Werte iteriert. Eine Array-Comprehension würde ein ganzes Array mit den verdoppelten Werten im Speicher erzeugen:

var doubles = [i * 2 for (i in it)];

Ein Generator-Ausdruck würde hingegen einen neuen Iterator erstellen, womit die doppelten Werte erst dann wenn Sie tatsächlich benötigt werden, erzeugt würden:

var it2 = (i * 2 for (i in it));
print(it2.next()); // The first value from it, doubled
print(it2.next()); // The second value from it, doubled

Wenn ein Generator-Ausdruck als Argument für eine Funktion eingesetzt wird, gelten die Klammern des Funktionsaufrufs auch für den Generator-Ausdruck und auf die äußeren Klammern kann verzichtet werden:

var result = doSomething(i * 2 for (i in it));

Schlagwörter des Dokuments und Mitwirkende

Mitwirkende an dieser Seite: eminor
Zuletzt aktualisiert von: eminor,