Iterables, Iterators und Generators

Vorwort

Bei meiner Arbeit bei esveo verwenden wir in vielen Projekten die Programmiersprache JavaScript bzw. TypeScript. Aufgrund der vielfältigen Anwendungsmöglichkeiten und der extremen Stärke des Ökosystems dieser Sprachen, war das bisher nie eine schlechte Entscheidung. Im Vergleich zur Entwicklung mit anderen Sprachen und Umgebungen ist die Komplexität der Anwendungen erst in den letzten Jahre so angestiegen (wie in einem anderen Artikel erläutert wurde), sodass man die Unterstützung von Frameworks und Design Patterns sucht, die in anderen Communities schon längst verbreitet sind. Eines dieser Patterns ist der Iterator, bzw. Iterables: Ein vereinheitlichtes Muster, mit denen ein Strom an Datenblöcken abgebildet werden kann.

Auch wenn die Code-Beispiele in diesem Artikel in TypeScript geschrieben sind, möchte ich an dieser Stelle betonen, dass es sich bei Iterables um ein JavaScript feature handelt, was dadurch natürlich auch in TypeScript verwendet werden kann.

Wieso keine Arrays?

const data = [1, 2, 3]; // Einfach, bequem und gut lesbar.

data.push(4);

Muss man eine Vielzahl von Werten in einer Variable ablegen, greift man üblicherweise zu einem Array bzw. zu einer Liste. Wieso sollte man jetzt also weg vom bewährten Vorgehen? Der große Nachteil bei Arrays ist, dass alle Werte gleichzeitig im Speicher existieren und gehalten werden müssen. Muss bei der serverseitigen Programmierung zum Beispiel eine Datei eingelesen und verarbeitet werden, sollte man die Zeilen der Datei nicht gleichzeitig laden und in einem Array ablegen, um sie anschließend zu verarbeiten, da der Arbeitsspeicher des Servers so nur unnötig befüllt wird. Stattdessen verarbeitet man jede Zeile einzeln und kann so eine hohe Spitze im Ressourcenverbrauch vermeiden. Natürlich kann man hier auch auf die Node.js typischen Streams zurückgreifen, mit den Iterables existiert seit 2015 jedoch ein Sprachfeature, das uns bei solchen Anwendungsfällen hilft.

Iterables & Iterator

Der grundlegende Baustein für die Verwendung von Iterables ist der Iterator. Ein Objekt, auf welchem man die next() Methode aufrufen kann, um den nächsten Wert zu erhalten. Als Resultat erhält man hierbei ein Objekt mit den Schlüsseln value und done, die den aktuellen Wert und die Information über den Zustand des Iterators beinhalten.

In TypeScript sieht das Interface des Iterators und des IteratorResults ungefähr (für die Erklärung wurden 2 Methoden wegglassen, die hier nicht benötigt werden, die richtigen Typen findet Ihr in lib.es2015.iterable.d.ts) so aus:

interface IteratorResult<ValueType> {
  done: boolean;
  value: ValueType;
}

interface Iterator<ValueType> {
  next: (value?: any) => IteratorResult<ValueType>;
}

Eine Beispielimplementierung, die eine Reihe aufsteigender Zahlen erzeugt, könnte dann so aussehen:

let n = 0;
const numberIterator = {
  next: () => {
    const nextResult = { value: n, done: false };
    n++;
    return nextResult;
  },
};

numberIterator.next(); // { value: 0, done: false }
numberIterator.next(); // { value: 1, done: false }
numberIterator.next(); // { value: 2, done: false }

Für eine einfache Zahlenfolge ist das dann doch erstaunlich viel Aufwand. Noch dazu kommt, dass ein einzelner zustandsbehafteter Iterator wenig Mehrwert bietet. Stattdessen möchte man eher seine eigenen Klassen als "iterierbar" markieren. Dafür wird das Interface des Iterables verwendet. Per Definition ist ein Objekt ein Iterable, wenn es im Schlüssel Symbol.iterator eine Methode enthält, die einen Iterator als Resultat liefert:

interface Iterable<ValueType> {
  [Symbol.iterator](): Iterator<ValueType>;
}

Eine Implementierung der Zahlenfolge könnte dann so aussehen:

const numbers = {
  [Symbol.iterator]: () => {
    let n = 0;
    return {
      next: () => {
        const nextResult = { value: n, done: false };
        n++;
        return nextResult;
      },
    };
  },
};

So ist der Schreibaufwand sogar noch größer, um etwas simples wie eine Zahlenfolge zu implementieren.

Eine Besonderheit dieser Lösungen soll hier jedoch hervorgehoben werden: Die Zahlenfolge ist unendlich. Das ließe sich in einem Array nicht abbilden, da es immer eine endliche Länge haben muss, da alle Elemente des Arrays gleichzeitig im Speicher gehalten werden müssen.

Da das Iterable eine einheitlich definierte Schnittstelle ist, können Sprachfeatures darauf aufgebaut werden:

// Implementierung des iterable ausgelassen
const iterableWithNumbersFromOneToThree = {
  /* ... */
};
for (const number of iterableWithNumbersFromOneToThree) {
  console.log(number); // 1, 2, 3
}

const arrayFromIterable = [...iterableWithNumbersFromOneToThree]; // [1, 2, 3]

// Gleich wie console.log(1, 2, 3)
console.log(...iterableWithNumbersFromOneToThree);

Von den Sprachkonstrukten for ... of und dem Spread operator ... werden also iterables konsumiert. Praktischerweise sind die eingebauten Arrays auch "iterable". Das bedeutet, dass der Code ab Zeile 5 flexibel ist: Er kann mit Arrays, Sets, NodeLists und anderen Iterables ausgeführt werden.

Da die Verwendung von Iterables verbreitet werden soll, wurde zudem eine neue Art Funktion zu JavaScript hinzugefügt, die die Erzeugung von Iterables erheblich erleichtert: Der Generator. Ein Generator ist eine Funktion, die als Rückgabewert einen Iterable Iterator liefert. Also einen Iterator (mit next-Methode) der gleichzeitig ein Iterable ist (mit Symbol.iterator Methode). Die Schreibweise sieht wie folgt aus:

function* numberGenerator() {
  let n = 0;
  while (true) {
    yield n;
    n++;
  }
}

Hier muss auf zwei Besonderheiten geachtet werden: Der * vor dem Funktionsnamen zeigt an, dass es sich bei dieser Funktion um einen Generator handelt. Das yield n im Funktionsblock, erzeugt den nächsten Wert im Iterable. Nach der yield Anweisung pausiert der Funktionscode in der Funktion und läuft erst weiter, wenn von außen die .next() Methode aufgerufen wird. Aus diesem Grund friert das while (true) den Browser auch nicht ein.

Der Code erzeugt also die gleiche unendliche Sequenz an Zahlen wie oben, lässt sich jedoch viel einfacher lesen.

Iterable Hilfsfunktionen

Jeder der in JavaScript schon öfter mit Listen von Daten gearbeitet hat, wird Hilfsfunktionen wie .map oder .filter kennen. Diese müssen für die Iterables aktuell einmalig selbst implementiert werden (wenn man keine externe Bibliothek hinzuziehen möchte). Es gibt hierfür jedoch schon ein Proposal im TC39 Prozess, welches Abhilfe schaffen soll. Bis dahin muss eine einfache Implementierung herhalten:

// Transformiere jeden Wert im iterable mit einer gegebenen Funktion:
function* map(iterable, transform) {
  for (let item of iterable) {
    yield transform(item);
  }
}

// Prüfe für jeden Wert im Iterable den Rückgabewert einer Funktion.
// Nur bei `true` wird der Wert behalten.
function* filter(iterable, condition) {
  for (let item of iterable) {
    if (condition(item)) yield item;
  }
}

Als kleines Beispiel, soll jetzt noch eine simple Transformation umgesetzt werden:

function transform(numbers: Iterable<number>) {
  const squared = map(numbers, (n) => n * n);
  const even = filter(numbers, (n) => n % 2 === 0);
  const multiplied = map(numbers, (n) => n * 100);

  return multiplied;
}

Diese Funktion quadriert alle Zahlen in einem Iterable, entfernt alle ungeraden und multipliziert die restlichen Zahlen jeweils mit 100.

Hier muss wieder betont werden: Iterables sind "lazy"! Das heißt, es werden nur die Werte berechnet, die wirklich benötigt werden:

const infinite = numberGenerator();
const transformed = transform(infinite);

// Bis hier hin wurde noch keine Berechnung durchgeführt.

let i = 0;
for (const n of transformed) {
  if (i > 10) break;
  i++;
  console.log(n);
}
// Hier werden die ersten 10 Ergebnisse des Iterators
// "gezogen" und auf die Konsole geschrieben.

Sowohl die Filter, als auch die Transformationen werden nur so oft durchgeführt, wie für die ersten 10 Ergebnisse benötigt wird. Mit den Array Methoden wäre dieses Vorgehen nicht möglich. Wir müssten uns erst selbst überlegen, wie viele Zahlen wir initial brauchen, um nach der Filterung genau 10 Ergebnisse zu haben. Zudem würde mit jedem Verarbeitungsschritt mit .map() oder .filter() ein komplett neues Array erzeugt werden, was den Garbage Collector zusätzlich belastet.

Wofür das alles?

Der größte Vorteil in der Verwendung des Iterable Interfaces versteckt sich in den SOLID-Prinzipien, genauer gesagt im Dependency Inversion Prinzip. Dieses besagt, dass Code immer nur von Interfaces und nicht von konkreten Implementierungen abhängen sollte. Würde die transform Funktion direkt mit den Array-Methoden arbeiten, könnte die Funktion auch nur mit Arrays aufgerufen werden und wir wären in der Verwendung unnötig eingeschränkt.

Hier kommt jetzt der größte Vorteil in der Verwendung von Iterables: Die eingebauten Sprach- und Browserfunktionen verwenden bereits Iterables: Arrays, Sets, Maps, NodeLists und viele weitere implementieren bereits das Iterable Interface. Das bedeutet, dass unsere transform-Funktion auch mit diesen Datenstrukturen aufgerufen werden kann und trotzdem funktioniert. So bleiben die Funktionen flexibel und können für viele Anwendungsfälle benutzt werden.

Gerade in der Backend-Entwicklung ist es einfach manchmal nötig, eigene Datenstrukturen, wie eine Queue oder eine LinkedList zu implementieren um optimale Performanz zu gewährleisten. Wenn diese auch Iterables sind, können viele Hilfsfunktionen trotzdem weiterverwendet werden.

Wenn Du also das nächste mal eine Funktion implementierst, die eine Liste von Elementen erhalten soll, hoffe ich, dass du zunächst an Iterables denkst, um diese Liste zu verarbeiten.