Was ist Tail Call-Optimierung?

818

Was ist Tail-Call-Optimierung?

Genauer gesagt, was sind einige kleine Codefragmente, wo sie angewendet werden könnten und wo nicht, mit einer Erklärung, warum?

Majelbstoat
quelle
10
TCO verwandelt einen Funktionsaufruf in der Endposition in einen goto, einen Sprung.
Will Ness
8
Diese Frage wurde 8 Jahre zuvor vollständig gestellt;)
Majelbstoat

Antworten:

755

Bei der Tail-Call-Optimierung können Sie vermeiden, einer Funktion einen neuen Stapelrahmen zuzuweisen, da die aufrufende Funktion einfach den Wert zurückgibt, den sie von der aufgerufenen Funktion erhält. Die häufigste Verwendung ist die Tail-Rekursion, bei der eine rekursive Funktion, die zur Nutzung der Tail-Call-Optimierung geschrieben wurde, konstanten Stapelspeicher verwenden kann.

Das Schema ist eine der wenigen Programmiersprachen, die in der Spezifikation garantieren, dass jede Implementierung diese Optimierung bereitstellen muss (JavaScript auch, beginnend mit ES6) . Hier sind zwei Beispiele für die Fakultätsfunktion im Schema:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

Die erste Funktion ist nicht rekursiv, da die Funktion bei einem rekursiven Aufruf die Multiplikation verfolgen muss, die sie mit dem Ergebnis nach der Rückkehr des Aufrufs durchführen muss. Als solches sieht der Stapel wie folgt aus:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Im Gegensatz dazu sieht die Stapelverfolgung für die rekursive Fakultät des Schwanzes wie folgt aus:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Wie Sie sehen, müssen wir bei jedem Aufruf von fact-tail nur die gleiche Datenmenge nachverfolgen, da wir einfach den Wert, den wir erhalten, ganz nach oben zurückgeben. Dies bedeutet, dass ich selbst bei einem Anruf (Fakt 1000000) nur den gleichen Speicherplatz benötige wie (Fakt 3). Dies ist bei der nicht rekursiven Tatsache nicht der Fall, und als solche können große Werte einen Stapelüberlauf verursachen.

Kyle Cronin
quelle
99
Wenn Sie mehr darüber erfahren möchten, empfehle ich Ihnen, das erste Kapitel über Struktur und Interpretation von Computerprogrammen zu lesen.
Kyle Cronin
3
Tolle Antwort, perfekt erklärt.
Jonah
15
Genau genommen ersetzt die Tail-Call-Optimierung nicht unbedingt den Stack-Frame des Anrufers durch die Callees, sondern stellt vielmehr sicher, dass eine unbegrenzte Anzahl von Anrufen in der Tail-Position nur einen begrenzten Speicherplatz benötigt. Siehe Will Clingers Artikel
Jon Harrop
3
Ist dies nur eine Möglichkeit, rekursive Funktionen im konstanten Raum zu schreiben? Weil Sie mit einem iterativen Ansatz nicht dieselben Ergebnisse erzielen konnten?
dclowd9901
5
@ dclowd9901, TCO ermöglicht es Ihnen, einen funktionalen Stil anstelle einer iterativen Schleife zu bevorzugen. Sie können imperativen Stil bevorzugen. Viele Sprachen (Java, Python) bieten keine TCO. Dann müssen Sie wissen, dass ein funktionaler Aufruf Speicher kostet ... und der imperative Stil bevorzugt wird.
mcoolive
552

Lassen Sie uns ein einfaches Beispiel durchgehen: die in C implementierte Fakultätsfunktion.

Wir beginnen mit der offensichtlichen rekursiven Definition

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

Eine Funktion endet mit einem Tail-Aufruf, wenn die letzte Operation vor der Rückkehr der Funktion ein anderer Funktionsaufruf ist. Wenn dieser Aufruf dieselbe Funktion aufruft, ist er schwanzrekursiv.

Obwohl es fac()auf den ersten Blick schwanzrekursiv aussieht, ist es nicht so, wie es tatsächlich passiert

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

dh die letzte Operation ist die Multiplikation und nicht der Funktionsaufruf.

Es ist jedoch möglich, fac()eine rekursive Umschreibung vorzunehmen, indem der akkumulierte Wert als zusätzliches Argument an die Aufrufkette übergeben und nur das Endergebnis erneut als Rückgabewert übergeben wird:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Warum ist das nützlich? Da wir sofort nach dem Tail-Aufruf zurückkehren, können wir den vorherigen Stackframe verwerfen, bevor wir die Funktion in Tail-Position aufrufen, oder bei rekursiven Funktionen den Stackframe unverändert wiederverwenden.

Die Tail-Call-Optimierung wandelt unseren rekursiven Code in um

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Dies kann eingefügt werden fac()und wir kommen zu

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

das ist äquivalent zu

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

Wie wir hier sehen können, kann ein ausreichend fortschrittlicher Optimierer die Endrekursion durch Iteration ersetzen. Dies ist weitaus effizienter, da Sie den Aufwand für Funktionsaufrufe vermeiden und nur eine konstante Menge an Stapelspeicher verwenden.

Christoph
quelle
Können Sie genau erklären, was ein Stackframe bedeutet? Gibt es einen Unterschied zwischen dem Aufrufstapel und dem Stapelrahmen?
Shasak
10
@Kasahs: Ein Stapelrahmen ist der Teil des Aufrufstapels, der zu einer bestimmten (aktiven) Funktion gehört. cf en.wikipedia.org/wiki/Call_stack#Structure
Christoph
1
Ich hatte gerade eine ziemlich intensive Offenbarung, nachdem ich diesen Beitrag gelesen hatte, nachdem ich 2ality.com/2015/06/tail-call-optimization.html
agm1984
198

TCO (Tail Call Optimization) ist der Prozess, mit dem ein Smart Compiler eine Funktion aufrufen und keinen zusätzlichen Stapelspeicherplatz beanspruchen kann. Die einzige Situation, in der dies geschieht, ist, wenn der letzte in einer Funktion f ausgeführte Befehl ein Aufruf einer Funktion g ist (Hinweis: g kann f sein ). Der Schlüssel hier ist, dass f keinen Stapelspeicher mehr benötigt - es ruft einfach g auf und gibt dann zurück, was auch immer g zurückgeben würde. In diesem Fall kann die Optimierung vorgenommen werden, dass g nur ausgeführt wird und den Wert, den es für das Objekt mit dem Namen f haben würde, zurückgibt.

Diese Optimierung kann dazu führen, dass rekursive Aufrufe einen konstanten Stapelspeicher beanspruchen und nicht explodieren.

Beispiel: Diese Fakultätsfunktion ist nicht TCOptimierbar:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Diese Funktion ruft nicht nur eine andere Funktion in ihrer return-Anweisung auf.

Diese Funktion ist TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

Dies liegt daran, dass das Letzte, was in einer dieser Funktionen passiert, darin besteht, eine andere Funktion aufzurufen.

Claudiu
quelle
3
Die ganze Sache 'Funktion g kann f sein' war ein wenig verwirrend, aber ich verstehe, was Sie meinen, und die Beispiele haben die Dinge wirklich klargestellt. Vielen Dank!
Majelbstoat
10
Hervorragendes Beispiel, das das Konzept veranschaulicht. Berücksichtigen Sie einfach, dass die von Ihnen ausgewählte Sprache die Eliminierung von Tail Calls oder die Optimierung von Tail Calls implementieren muss. In dem in Python geschriebenen Beispiel wird bei Eingabe eines Werts von 1000 der Wert "RuntimeError: Maximale Rekursionstiefe überschritten" angezeigt, da die Standard-Python-Implementierung die Eliminierung der Schwanzrekursion nicht unterstützt. In einem Beitrag von Guido selbst wird erklärt, warum dies so ist: neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html .
rmcc
"Die einzige Situation" ist etwas zu absolut; Zumindest theoretisch gibt es auch TRMC , die auf die gleiche Weise optimieren (cons a (foo b))oder die Heckposition einnehmen würden (+ c (bar d)).
Will Ness
Ich mochte Ihren F- und G-Ansatz besser als die akzeptierte Antwort, vielleicht weil ich eine mathematische Person bin.
Nithin
Ich denke du meinst TCOptimized. Zu sagen, dass es nicht TCOptimizable ist, lässt darauf schließen, dass es niemals optimiert werden kann (wenn es tatsächlich möglich ist)
Jacques Mathieu
65

Die wahrscheinlich beste Beschreibung auf hoher Ebene, die ich für Tail Calls, rekursive Tail Calls und Tail Call-Optimierung gefunden habe, ist der Blog-Beitrag

"Was zum Teufel ist: Ein Schwanzruf"

von Dan Sugalski. Zur Tail-Call-Optimierung schreibt er:

Betrachten Sie für einen Moment diese einfache Funktion:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Was können Sie oder vielmehr Ihr Sprachcompiler tun? Nun, was es tun kann, ist, den Code des Formulars return somefunc();in die Low-Level-Sequenz umzuwandeln pop stack frame; goto somefunc();. In unserem Beispiel, das heißt , bevor wir rufen bar, fooreinigt sich selbst und dann, anstatt Aufruf barals ein Unterprogramm, machen wir eine Low-Level - gotoBetrieb zu Beginn des bar. Foo's hat sich bereits aus dem Stapel entfernt. Wenn bares also startet, sieht es so aus, als hätte derjenige, der angerufen foohat, wirklich aufgerufen bar, und wenn er barseinen Wert zurückgibt, gibt er ihn direkt an denjenigen zurück, der angerufen hat foo, anstatt ihn zurückzugeben, fooder ihn dann an seinen Aufrufer zurückgeben würde.

Und auf Schwanzrekursion:

Die Schwanzrekursion tritt auf, wenn eine Funktion als letzte Operation das Ergebnis des Aufrufs selbst zurückgibt . Die Schwanzrekursion ist einfacher zu handhaben, da Sie nicht irgendwo zum Anfang einer zufälligen Funktion springen müssen, sondern nur zum Anfang Ihrer selbst zurückkehren müssen, was eine verdammt einfache Sache ist.

Damit das:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

wird leise verwandelt in:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

Was mir an dieser Beschreibung gefällt, ist, wie prägnant und einfach es für diejenigen ist, die einen imperativen Sprachhintergrund haben (C, C ++, Java).

Übrigens
quelle
4
404 Fehler. Es ist jedoch weiterhin auf archive.org verfügbar: web.archive.org/web/20111030134120/http://www.sidhe.org/~dan/…
Tommy
Ich habe es nicht verstanden, ist der anfängliche fooFunktionsendaufruf nicht optimiert? Es ruft nur eine Funktion als letzten Schritt auf und gibt einfach diesen Wert zurück, oder?
SexyBeast
1
@ TryinHard vielleicht nicht das, was Sie vorhatten, aber ich habe es aktualisiert, um einen Überblick darüber zu geben, worum es geht. Entschuldigung, ich werde nicht den ganzen Artikel wiederholen!
btiernay
2
Vielen Dank, dies ist einfacher und verständlicher als das am besten
gewählte
2
Als jemand, der selten in funktionale Sprachen eintaucht, ist es erfreulich, eine Erklärung in "meinem Dialekt" zu sehen. Es gibt eine (verständliche) Tendenz für funktionale Programmierer, in der Sprache ihrer Wahl zu evangelisieren, aber aus der imperativen Welt kommend finde ich es so viel einfacher, mich mit einer Antwort wie dieser zu beschäftigen.
James Beninger
15

Beachten Sie zunächst, dass dies nicht in allen Sprachen unterstützt wird.

TCO gilt für einen Sonderfall der Rekursion. Der Kern davon ist, dass, wenn das letzte, was Sie in einer Funktion tun, der Aufruf selbst ist (z. B. der Aufruf von der "End" -Position), dies vom Compiler so optimiert werden kann, dass er sich wie eine Iteration anstelle einer Standardrekursion verhält.

Normalerweise muss die Laufzeit während der Rekursion alle rekursiven Aufrufe verfolgen, damit sie bei der Rückkehr beim vorherigen Aufruf fortgesetzt werden kann und so weiter. (Versuchen Sie, das Ergebnis eines rekursiven Aufrufs manuell aufzuschreiben, um eine visuelle Vorstellung davon zu erhalten, wie dies funktioniert.) Das Verfolgen aller Aufrufe nimmt Speicherplatz in Anspruch, der erheblich wird, wenn sich die Funktion häufig selbst aufruft. Aber mit TCO kann es einfach sagen: "Gehen Sie zurück zum Anfang, nur dieses Mal ändern Sie die Parameterwerte in diese neuen." Dies ist möglich, da sich nach dem rekursiven Aufruf nichts auf diese Werte bezieht.

J Cooper
quelle
3
Endaufrufe können auch für nicht rekursive Funktionen gelten. Jede Funktion, deren letzte Berechnung vor der Rückkehr ein Aufruf einer anderen Funktion ist, kann einen Endaufruf verwenden.
Brian
Nicht unbedingt sprachweise - der 64-Bit-C # -Compiler fügt möglicherweise Tail-Opcodes ein, während die 32-Bit-Version dies nicht tut. und F # Release Build wird, aber F # Debug wird nicht standardmäßig.
Steve Gilham
3
"TCO gilt für einen Sonderfall der Rekursion". Ich fürchte, das ist völlig falsch. Tail Calls gelten für jeden Call in Tail Position. Wird häufig im Zusammenhang mit der Rekursion diskutiert, hat aber eigentlich nichts spezielles mit Rekursion zu tun.
Jon Harrop
@Brian, schau dir den oben angegebenen Link @btiernay an. Ist der anfängliche fooMethoden-Tail-Aufruf nicht optimiert?
SexyBeast
13

Beispiel für ein minimal lauffähiges GCC mit x86-Demontageanalyse

Lassen Sie uns anhand der generierten Assembly sehen, wie GCC automatisch Tail-Call-Optimierungen für uns durchführen kann.

Dies ist ein äußerst konkretes Beispiel dafür, was in anderen Antworten wie https://stackoverflow.com/a/9814654/895245 erwähnt wurde, dass die Optimierung rekursive Funktionsaufrufe in eine Schleife konvertieren kann.

Dies spart wiederum Speicher und verbessert die Leistung, da Speicherzugriffe heutzutage häufig die Hauptsache sind, die Programme verlangsamt .

Als Eingabe geben wir GCC eine nicht optimierte naive stapelbasierte Fakultät:

tail_call.c

#include <stdio.h>
#include <stdlib.h>

unsigned factorial(unsigned n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(int argc, char **argv) {
    int input;
    if (argc > 1) {
        input = strtoul(argv[1], NULL, 0);
    } else {
        input = 5;
    }
    printf("%u\n", factorial(input));
    return EXIT_SUCCESS;
}

GitHub stromaufwärts .

Kompilieren und disassemblieren:

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
  -o tail_call.out tail_call.c
objdump -d tail_call.out

Wo -foptimize-sibling-callsist der Name der Verallgemeinerung von Tail Calls nach man gcc:

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

wie unter: Wie überprüfe ich, ob gcc eine Tail-Rekursionsoptimierung durchführt?

Ich wähle -O1weil:

  • Die Optimierung erfolgt nicht mit -O0. Ich vermute, dass dies daran liegt, dass erforderliche Zwischentransformationen fehlen.
  • -O3 erzeugt gottlos effizienten Code, der nicht sehr lehrreich wäre, obwohl er auch für Tail Call optimiert ist.

Demontage mit -fno-optimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       89 f8                   mov    %edi,%eax
    1147:       83 ff 01                cmp    $0x1,%edi
    114a:       74 10                   je     115c <factorial+0x17>
    114c:       53                      push   %rbx
    114d:       89 fb                   mov    %edi,%ebx
    114f:       8d 7f ff                lea    -0x1(%rdi),%edi
    1152:       e8 ee ff ff ff          callq  1145 <factorial>
    1157:       0f af c3                imul   %ebx,%eax
    115a:       5b                      pop    %rbx
    115b:       c3                      retq
    115c:       c3                      retq

Mit -foptimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       b8 01 00 00 00          mov    $0x1,%eax
    114a:       83 ff 01                cmp    $0x1,%edi
    114d:       74 0e                   je     115d <factorial+0x18>
    114f:       8d 57 ff                lea    -0x1(%rdi),%edx
    1152:       0f af c7                imul   %edi,%eax
    1155:       89 d7                   mov    %edx,%edi
    1157:       83 fa 01                cmp    $0x1,%edx
    115a:       75 f3                   jne    114f <factorial+0xa>
    115c:       c3                      retq
    115d:       89 f8                   mov    %edi,%eax
    115f:       c3                      retq

Der Hauptunterschied zwischen den beiden ist:

  • die -fno-optimize-sibling-callsVerwendungen callq, die der typische nicht optimierte Funktionsaufruf ist.

    Dieser Befehl verschiebt die Rücksprungadresse an den Stapel und erhöht sie daher.

    Darüber hinaus tut dies auch diese Version push %rbx, die auf den Stapel schiebt%rbx .

    GCC tut dies, weil es speichert edi, was das erste Funktionsargument ( n) ist ebx, und dann aufruft factorial.

    GCC muss dies tun, da es sich auf einen weiteren Anruf bei vorbereitet factorial, bei dem das neue verwendet wird edi == n-1.

    Es wird ausgewählt, ebxweil dieses Register als Angerufene gespeichert ist: Welche Register werden durch einen Linux x86-64-Funktionsaufruf beibehalten, damit der Unteraufruf factoriales nicht ändert und verliert n.

  • Das -foptimize-sibling-callsverwendet keine Anweisungen, die auf den Stapel verschoben werden: Es gotospringt nur factorialmit den Anweisungen jeund jne.

    Daher entspricht diese Version einer while-Schleife ohne Funktionsaufrufe. Die Stapelnutzung ist konstant.

Getestet in Ubuntu 18.10, GCC 8.2.

Ciro Santilli 冠状 病毒 审查 六四 事件 法轮功
quelle
6

Schau hier:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

Wie Sie wahrscheinlich wissen, können rekursive Funktionsaufrufe einen Stapel zerstören. Es ist leicht, schnell keinen Stapelplatz mehr zu haben. Die Tail-Call-Optimierung ist eine Methode, mit der Sie einen rekursiven Stilalgorithmus erstellen können, der konstanten Stapelspeicher verwendet. Daher wächst er nicht und wächst und es treten Stapelfehler auf.

BobbyShaftoe
quelle
3
  1. Wir sollten sicherstellen, dass die Funktion selbst keine goto-Anweisungen enthält. Der Funktionsaufruf ist das Letzte in der Angerufenenfunktion.

  2. Rekursionen in großem Maßstab können dies für Optimierungen verwenden, aber in kleinem Maßstab verringert der Anweisungsaufwand, um den Funktionsaufruf zu einem Endaufruf zu machen, den tatsächlichen Zweck.

  3. TCO kann eine für immer laufende Funktion verursachen:

    void eternity()
    {
        eternity();
    }
    
GrillSandwich
quelle
3 wurde noch nicht optimiert. Dies ist die nicht optimierte Darstellung, die der Compiler in iterativen Code umwandelt, der anstelle von rekursivem Code konstanten Stapelspeicher verwendet. TCO ist nicht die Ursache für die Verwendung des falschen Rekursionsschemas für eine Datenstruktur.
Nomen
"TCO ist nicht die Ursache für die Verwendung des falschen Rekursionsschemas für eine Datenstruktur." Bitte erläutern Sie, wie dies für den jeweiligen Fall relevant ist. Das obige Beispiel zeigt nur ein Beispiel für die Frames, die auf dem Aufrufstapel mit und ohne TCO zugewiesen sind.
GrillSandwich
Sie haben die unbegründete Rekursion für traverse () verwendet. Das hatte nichts mit TCO zu tun. Ewigkeit ist zufällig eine Tail-Call-Position, aber eine Tail-Call-Position ist nicht erforderlich: void eternity () {eternity (); Ausfahrt(); }
Nomen
Was ist eine "groß angelegte Rekursion", wenn wir schon dabei sind? Warum sollten wir Goto in der Funktion vermeiden? Dies ist weder notwendig noch ausreichend, um TCO zuzulassen. Und welcher Unterrichtsaufwand? Der springende Punkt bei TCO ist, dass der Compiler den Funktionsaufruf in der Endposition durch ein goto ersetzt.
Nomen
Bei TCO geht es darum, den auf dem Aufrufstapel verwendeten Speicherplatz zu optimieren. Mit großflächiger Rekursion beziehe ich mich auf die Größe des Rahmens. Jedes Mal, wenn eine Rekursion auftritt und ich einen großen Frame auf dem Aufrufstapel über der Anruffunktion zuweisen muss, ist die Gesamtbetriebskosten hilfreich und ermöglicht mir mehr Rekursionsstufen. Wenn meine Frame-Größe jedoch geringer ist, kann ich auf TCO verzichten und mein Programm trotzdem gut ausführen (ich spreche hier nicht von unendlicher Rekursion). Wenn Sie in der Funktion mit goto belassen werden, ist "tail" -Aufruf kein Tail-Aufruf und TCO ist nicht anwendbar.
Grill Sandwich
3

Der Ansatz der rekursiven Funktion hat ein Problem. Es baut einen Aufrufstapel der Größe O (n) auf, wodurch unser Gesamtspeicher O (n) kostet. Dies macht es anfällig für einen Stapelüberlauffehler, bei dem der Aufrufstapel zu groß wird und nicht mehr genügend Speicherplatz zur Verfügung steht.

TCO-Schema (Tail Call Optimization). Wo es rekursive Funktionen optimieren kann, um den Aufbau eines hohen Aufrufstapels zu vermeiden und somit die Speicherkosten zu sparen.

Es gibt viele Sprachen, die TCO-ähnliche Aufgaben ausführen (JavaScript, Ruby und wenige C), während Python und Java keine TCO-Vorgänge ausführen.

Die JavaScript-Sprache wurde mit :) http://2ality.com/2015/06/tail-call-optimization.html bestätigt

Rupesh Kumar Tiwari
quelle
0

In einer funktionalen Sprache ist die Endaufrufoptimierung so, als ob ein Funktionsaufruf als Ergebnis einen teilweise ausgewerteten Ausdruck zurückgeben könnte, der dann vom Aufrufer ausgewertet würde.

f x = g x

f 6 reduziert sich auf g 6. Wenn die Implementierung also g 6 als Ergebnis zurückgeben und diesen Ausdruck dann aufrufen könnte, würde ein Stapelrahmen gespeichert.

Ebenfalls

f x = if c x then g x else h x.

Reduziert sich auf f 6 auf entweder g 6 oder h 6. Wenn die Implementierung also c 6 auswertet und feststellt, dass es wahr ist, kann sie reduzieren,

if true then g x else h x ---> g x

f x ---> h x

Ein einfacher Nicht-Tail-Call-Optimierungsinterpreter könnte folgendermaßen aussehen:

class simple_expresion
{
    ...
public:
    virtual ximple_value *DoEvaluate() const = 0;
};

class simple_value
{
    ...
};

class simple_function : public simple_expresion
{
    ...
private:
    simple_expresion *m_Function;
    simple_expresion *m_Parameter;

public:
    virtual simple_value *DoEvaluate() const
    {
        vector<simple_expresion *> parameterList;
        parameterList->push_back(m_Parameter);
        return m_Function->Call(parameterList);
    }
};

class simple_if : public simple_function
{
private:
    simple_expresion *m_Condition;
    simple_expresion *m_Positive;
    simple_expresion *m_Negative;

public:
    simple_value *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive.DoEvaluate();
        }
        else
        {
            return m_Negative.DoEvaluate();
        }
    }
}

Ein Interpreter für die Tail-Call-Optimierung könnte folgendermaßen aussehen:

class tco_expresion
{
    ...
public:
    virtual tco_expresion *DoEvaluate() const = 0;
    virtual bool IsValue()
    {
        return false;
    }
};

class tco_value
{
    ...
public:
    virtual bool IsValue()
    {
        return true;
    }
};

class tco_function : public tco_expresion
{
    ...
private:
    tco_expresion *m_Function;
    tco_expresion *m_Parameter;

public:
    virtual tco_expression *DoEvaluate() const
    {
        vector< tco_expression *> parameterList;
        tco_expression *function = const_cast<SNI_Function *>(this);
        while (!function->IsValue())
        {
            function = function->DoCall(parameterList);
        }
        return function;
    }

    tco_expresion *DoCall(vector<tco_expresion *> &p_ParameterList)
    {
        p_ParameterList.push_back(m_Parameter);
        return m_Function;
    }
};

class tco_if : public tco_function
{
private:
    tco_expresion *m_Condition;
    tco_expresion *m_Positive;
    tco_expresion *m_Negative;

    tco_expresion *DoEvaluate() const
    {
        if (m_Condition.DoEvaluate()->IsTrue())
        {
            return m_Positive;
        }
        else
        {
            return m_Negative;
        }
    }
}
Peter Driscoll
quelle