27. Tail Call Optimierung

ECMAScript 6 bietet die Tail Call Optimierung, bei der einige Funktionsaufrufe vorgenommen werden können, ohne den Call-Stack zu vergrößern. Dieses Kapitel erklärt, wie das funktioniert und welche Vorteile es bringt.

Warnung: Obwohl die Tail Call Optimierung Teil der Sprachspezifikation ist, wird sie von vielen Engines nicht unterstützt und das wird sich möglicherweise nie ändern.

27.1. Was ist Tail Call Optimierung?
- 27.1.1. Normale Ausführung
- 27.1.2. Tail Call Optimierung
27.2. Prüfen, ob ein Funktionsaufruf in einer Tail-Position ist
- 27.2.1. Tail Calls in Ausdrücken
- 27.2.2. Tail Calls in Anweisungen
- 27.2.3. Tail Call Optimierung kann nur im Strict Mode erfolgen
- 27.2.4. Fallstrick: Alleinstehende Funktionsaufrufe sind nie in Tail-Position
27.3. Tail-rekursive Funktionen
- 27.3.1. Tail-rekursive Schleifen

27.1 Was ist Tail Call Optimierung?

Im Grunde genommen, wenn das Letzte, was eine Funktion tut, der Aufruf einer anderen Funktion ist, muss die letztere nicht zu ihrem Aufrufer zurückkehren. Infolgedessen müssen keine Informationen auf dem Call-Stack gespeichert werden und der Funktionsaufruf ist eher ein goto (ein Sprung). Diese Art von Aufruf wird als Tail Call bezeichnet; das Nicht-Vergrößern des Stacks wird als Tail Call Optimierung (TCO) bezeichnet.

Betrachten wir ein Beispiel, um TCO besser zu verstehen. Ich werde zuerst erklären, wie es ohne TCO und dann mit TCO ausgeführt wird.

function id(x) {
    return x; // (A)
}
function f(a) {
    const b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

27.1.1 Normale Ausführung

Nehmen wir an, es gibt eine JavaScript-Engine, die Funktionsaufrufe verwaltet, indem sie lokale Variablen und Rücksprungadressen auf einem Stack speichert. Wie würde eine solche Engine den Code ausführen?

Schritt 1. Anfangs befinden sich nur die globalen Variablen id und f auf dem Stack.

Der Block von Stack-Einträgen kodiert den Zustand (lokale Variablen, einschließlich Parameter) des aktuellen Gültigkeitsbereichs und wird als Stack Frame bezeichnet.

Schritt 2. In Zeile C wird f() aufgerufen: Zuerst wird die Rücksprungadresse auf dem Stack gespeichert. Dann werden fs Parameter zugewiesen und die Ausführung springt zu seinem Körper. Der Stack sieht nun wie folgt aus.

Es befinden sich nun zwei Frames auf dem Stack: Einer für den globalen Gültigkeitsbereich (unten) und einer für f() (oben). fs Stack Frame enthält die Rücksprungadresse, Zeile C.

Schritt 3. id() wird in Zeile B aufgerufen. Wieder wird ein Stack Frame erstellt, der die Rücksprungadresse und ids Parameter enthält.

Schritt 4. In Zeile A wird das Ergebnis x zurückgegeben. ids Stack Frame wird entfernt und die Ausführung springt zur Rücksprungadresse, Zeile B. (Es gibt mehrere Möglichkeiten, wie die Rückgabe eines Werts gehandhabt werden könnte. Zwei gängige Lösungen sind, das Ergebnis auf einem Stack zu belassen oder es in einem Register zu übergeben. Diesen Teil der Ausführung ignoriere ich hier.)

Der Stack sieht nun wie folgt aus

Schritt 5. In Zeile B wird der von id zurückgegebene Wert an den Aufrufer von f zurückgegeben. Wieder wird der oberste Stack Frame entfernt und die Ausführung springt zur Rücksprungadresse, Zeile C.

Schritt 6. Zeile C empfängt den Wert 3 und gibt ihn aus.

27.1.2 Tail Call Optimierung

function id(x) {
    return x; // (A)
}
function f(a) {
    const b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

Wenn Sie sich den vorherigen Abschnitt ansehen, gibt es einen unnötigen Schritt – Schritt 5. Alles, was in Zeile B passiert, ist, dass der von id() zurückgegebene Wert an Zeile C weitergegeben wird. Idealerweise könnte id() das selbst tun und der Zwischenschritt könnte übersprungen werden.

Wir können dies erreichen, indem wir den Funktionsaufruf in Zeile B anders implementieren. Bevor der Aufruf stattfindet, sieht der Stack wie folgt aus.

Wenn wir den Aufruf untersuchen, sehen wir, dass dies die letzte Aktion in f() ist. Sobald id() fertig ist, ist die einzige verbleibende Aktion, die f() ausführt, die Weitergabe des Ergebnisses von id an den Aufrufer von f. Daher werden fs Variablen nicht mehr benötigt und sein Stack Frame kann vor dem Aufruf entfernt werden. Die an id() übergebene Rücksprungadresse ist die Rücksprungadresse von f, Zeile C. Während der Ausführung von id() sieht der Stack so aus

Dann gibt id() den Wert 3 zurück. Man könnte sagen, dass es diesen Wert für f() zurückgibt, weil es ihn an den Aufrufer von f, Zeile C, transportiert.

Fassen wir zusammen: Der Funktionsaufruf in Zeile B ist ein Tail Call. Ein solcher Aufruf kann mit null Stack-Wachstum ausgeführt werden. Um herauszufinden, ob ein Funktionsaufruf ein Tail Call ist, müssen wir prüfen, ob er sich in einer Tail-Position befindet (d.h. die letzte Aktion in einer Funktion). Wie das geschieht, wird im nächsten Abschnitt erklärt.

27.2 Prüfen, ob ein Funktionsaufruf in einer Tail-Position ist

Wir haben gerade gelernt, dass Tail Calls Funktionsaufrufe sind, die effizienter ausgeführt werden können. Aber was zählt als Tail Call?

Zuerst spielt die Art und Weise, wie Sie eine Funktion aufrufen, keine Rolle. Die folgenden Aufrufe können optimiert werden, wenn sie sich in einer Tail-Position befinden

Funktionsaufruf: func(···)
Dispatchter Methodenaufruf: obj.method(···)
Direkter Methodenaufruf über call(): func.call(···)
Direkter Methodenaufruf über apply(): func.apply(···)

27.2.1 Tail Calls in Ausdrücken

Pfeilfunktionen können Ausdrücke als Körper haben. Für die Tail Call Optimierung müssen wir daher herausfinden, wo sich Funktionsaufrufe in Ausdrücken in Tail-Position befinden. Nur die folgenden Ausdrücke können Tail Calls enthalten

Der Bedingungsoperator (? :)
Der logische ODER-Operator (||)
Der logische UND-Operator (&&)
Der Komma-Operator (,)

Sehen wir uns ein Beispiel für jeden an.

27.2.1.1 Der Bedingungsoperator (`? :`)

const a = x => x ? f() : g();

Sowohl f() als auch g() befinden sich in Tail-Position.

27.2.1.2 Der logische ODER-Operator (`||`)

const a = () => f() || g();

f() befindet sich nicht in einer Tail-Position, aber g() befindet sich in einer Tail-Position. Um zu verstehen, warum, sehen Sie sich den folgenden Code an, der dem vorherigen Code entspricht

const a = () => {
    const fResult = f(); // not a tail call
    if (fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

Das Ergebnis des logischen ODER-Operators hängt vom Ergebnis von f() ab, weshalb dieser Funktionsaufruf nicht in einer Tail-Position ist (der Aufrufer tut etwas damit, außer es zurückzugeben). g() befindet sich jedoch in einer Tail-Position.

27.2.1.3 Der logische UND-Operator

const a = () => f() && g();

f() befindet sich nicht in einer Tail-Position, aber g() befindet sich in einer Tail-Position. Um zu verstehen, warum, sehen Sie sich den folgenden Code an, der dem vorherigen Code entspricht

const a = () => {
    const fResult = f(); // not a tail call
    if (!fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

Das Ergebnis des logischen UND-Operators hängt vom Ergebnis von f() ab, weshalb dieser Funktionsaufruf nicht in einer Tail-Position ist (der Aufrufer tut etwas damit, außer es zurückzugeben). g() befindet sich jedoch in einer Tail-Position.

27.2.1.4 Der Komma-Operator (`,`)

const a = () => (f() , g());

f() befindet sich nicht in einer Tail-Position, aber g() befindet sich in einer Tail-Position. Um zu verstehen, warum, sehen Sie sich den folgenden Code an, der dem vorherigen Code entspricht

const a = () => {
    f();
    return g();
}

27.2.2 Tail Calls in Anweisungen

Für Anweisungen gelten die folgenden Regeln.

Nur diese zusammengesetzten Anweisungen können Tail Calls enthalten

Blöcke (begrenzt durch {}, mit oder ohne Label)
if: entweder im „then“-Teil oder im „else“-Teil.
do-while, while, for: in ihren Körpern.
switch: in seinem Körper.
try-catch: nur im catch-Teil. Der try-Teil hat den catch-Teil als Kontext, der nicht wegoptimiert werden kann.
try-finally, try-catch-finally: nur im finally-Teil, der ein Kontext der anderen Teile ist, der nicht wegoptimiert werden kann.

Von allen atomaren (nicht zusammengesetzten) Anweisungen kann nur return einen Tail Call enthalten. Alle anderen Anweisungen haben einen Kontext, der nicht wegoptimiert werden kann. Die folgende Anweisung enthält einen Tail Call, wenn expr einen Tail Call enthält.

return «expr»;

27.2.3 Tail Call Optimierung kann nur im Strict Mode erfolgen

Im Non-Strict Mode verfügen die meisten Engines über die folgenden beiden Eigenschaften, mit denen Sie den Call-Stack untersuchen können

func.arguments: enthält die Argumente der zuletzt ausgeführten Instanz von func.
func.caller: verweist auf die Funktion, die func zuletzt aufgerufen hat.

Mit Tail Call Optimierung funktionieren diese Eigenschaften nicht, da die Informationen, auf denen sie basieren, möglicherweise entfernt wurden. Daher verbietet der Strict Mode diese Eigenschaften (wie in der Sprachspezifikation beschrieben) und die Tail Call Optimierung funktioniert nur im Strict Mode.

27.2.4 Fallstrick: Alleinstehende Funktionsaufrufe sind nie in Tail-Position

Der Funktionsaufruf bar() im folgenden Code befindet sich nicht in einer Tail-Position

function foo() {
    bar(); // this is not a tail call in JS
}

Der Grund dafür ist, dass die letzte Aktion von foo() nicht der Funktionsaufruf bar() ist, sondern (implizit) das Zurückgeben von undefined. Mit anderen Worten, foo() verhält sich wie folgt

function foo() {
    bar();
    return undefined;
}

Aufrufer können sich darauf verlassen, dass foo() immer undefined zurückgibt. Wenn bar() ein Ergebnis für foo() zurückgeben würde, würde sich aufgrund der Tail Call Optimierung das Verhalten von foo ändern.

Daher müssen wir foo() wie folgt ändern, wenn bar() ein Tail Call sein soll.

function foo() {
    return bar(); // tail call
}

27.3 Tail-rekursive Funktionen

Eine Funktion ist tail-rekursiv, wenn die wichtigsten rekursiven Aufrufe, die sie macht, in Tail-Positionen erfolgen.

Zum Beispiel ist die folgende Funktion nicht tail-rekursiv, da der wichtigste rekursive Aufruf in Zeile A nicht in einer Tail-Position ist

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

factorial() kann über eine tail-rekursive Hilfsfunktion facRec() implementiert werden. Der wichtigste rekursive Aufruf in Zeile A befindet sich in einer Tail-Position.

function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

Das heißt, einige nicht-tail-rekursive Funktionen können in tail-rekursive Funktionen umgewandelt werden.

27.3.1 Tail-rekursive Schleifen

Tail Call Optimierung ermöglicht es, Schleifen über Rekursion zu implementieren, ohne den Stack zu vergrößern. Die folgenden sind zwei Beispiele.

27.3.1.1 `forEach()`

function forEach(arr, callback, start = 0) {
    if (0 <= start && start < arr.length) {
        callback(arr[start], start, arr);
        return forEach(arr, callback, start+1); // tail call
    }
}
forEach(['a', 'b'], (elem, i) => console.log(`${i}. ${elem}`));

// Output:
// 0. a
// 1. b

27.3.1.2 `findIndex()`

function findIndex(arr, predicate, start = 0) {
    if (0 <= start && start < arr.length) {
        if (predicate(arr[start])) {
            return start;
        }
        return findIndex(arr, predicate, start+1); // tail call
    }
}
findIndex(['a', 'b'], x => x === 'b'); // 1

Weiter: 28. Metaprogrammierung mit Proxies