Was ist Tail Call Optimierung?

Ganz einfach, was ist Tail-Call-Optimierung? Genauer gesagt: Kann jemand kleine Code-Snippets anzeigen, auf die es angewendet werden kann, und wo nicht, mit einer Erklärung warum?

   

Mit der Tail-Call-Optimierung können Sie vermeiden, einen neuen Stack-Frame für eine function zuzuweisen, da die aufrufende function einfach den Wert zurückgibt, den sie von der aufgerufenen function erhält. Die häufigste Verwendung ist die Tail-Rekursion, wobei eine rekursive function, die geschrieben wurde, um die Tail-Call-Optimierung zu nutzen, einen konstanten Stapelspeicherplatz verwenden kann.

Schema ist eine der wenigen Programmiersprachen, die in der Spezifikation garantieren, dass jede Implementierung diese Optimierung bereitstellen muss (JavaScript funktioniert auch, beginnend mit ES6) . Hier sind zwei Beispiele für die faktorielle function in 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 function ist nicht tail-rekursiv, weil die function, wenn der rekursive Aufruf durchgeführt wird, die Multiplikation, die sie mit dem Ergebnis nach der Rückkehr des Aufrufs zu tun hat, verfolgen muss. Der Stack sieht folgendermaßen 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 der Stack-Trace für den tail rekursiven Faktor 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 können, müssen wir nur die gleiche Menge an Daten für jeden Aufruf zum Fact-Tail verfolgen, weil wir einfach den Wert, den wir erhalten, an die Spitze zurückgeben. Das heißt, selbst wenn ich anruft (Fakt 1000000), brauche ich nur den gleichen Platz wie (Fakt 3). Dies ist bei der nicht-tail-rekursiven Tatsache nicht der Fall, und als solche großen Werte können einen Stapelüberlauf verursachen.

Lassen Sie uns durch ein einfaches Beispiel gehen: die in C implementierte faktorielle function.

Wir beginnen mit der offensichtlichen rekursiven Definition

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

Eine function endet mit einem Tail-Call, wenn die letzte Operation vor der function ein anderer functionsaufruf ist. Wenn dieser Aufruf die gleiche function aufruft, ist er tail-rekursiv.

Auch wenn fac() auf den ersten Blick tail-rekursiv aussieht, ist es nicht so, wie es tatsächlich ist

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

Es ist jedoch möglich, fac() rekursiv zu schreiben, indem der akkumulierte Wert in der Aufrufkette als zusätzliches Argument übergeben wird und nur das Endergebnis als Rückgabewert zurückgegeben 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); } 

Nun, warum ist das nützlich? Da wir sofort nach dem Tail-Aufruf zurückkehren, können wir den vorherigen Stackframe vor dem Aufruf der function in der Tail-Position vercasting oder im Falle von rekursiven functionen den Stackframe unverändert übernehmen.

Die Tail-Call-Optimierung transformiert unseren rekursiven Code in

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

Dies kann in fac() eingezeichnet werden und wir kommen an

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

was entspricht

 unsigned fac(unsigned n) { unsigned acc = 1; for (; n > 1; --n) acc *= n; return acc; } 

Wie wir hier sehen können, kann ein ausreichend fortgeschrittener Optimierer die Tail-Rekursion durch Iteration ersetzen, was weitaus effizienter ist, da Sie den functionsaufruf-Overhead vermeiden und nur einen konstanten Stapelspeicherplatz verwenden.

TCO (Tail Call Optimization) ist der process, mit dem ein intelligenter Compiler einen Aufruf an eine function vornehmen und keinen zusätzlichen Stapelspeicherplatz einnehmen kann. Die einzige Situation, in der dies geschieht, ist, wenn der letzte in einer function f ausgeführte Befehl ein Aufruf einer function g ist (Anmerkung: g kann f sein ). Der Schlüssel hier ist, dass f keinen Stack-Speicherplatz mehr benötigt – es ruft einfach g auf und gibt dann zurück, was g zurückkommt. In diesem Fall kann die Optimierung vorgenommen werden, dass g nur läuft und den Wert zurückgibt, den es für die Sache hätte, die f genannt wird.

Diese Optimierung kann dazu führen, dass rekursive Aufrufe konstanten Stapelspeicherplatz einnehmen und nicht explodieren.

Beispiel: Diese Fakultät function ist nicht TCOptimizable:

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

Diese function ruft in ihrer return-statement außerdem eine andere function auf.

Diese untere function 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 functionen passiert, darin besteht, eine andere function aufzurufen.

Die wahrscheinlich beste Beschreibung für Tail Calls, rekursive Tail Calls und Tail Call Optimization ist der Blog Post

“Was zum Teufel ist: Ein Schwanz Anruf”

von Dan Sugalski. Bei der Tail Call Optimierung schreibt er:

Betrachten Sie für einen Moment diese einfache function:

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

Was können Sie, oder besser gesagt, Ihren Sprachcompiler tun? Nun, was es tun kann, ist Code des Formulars return somefunc(); in den Sequenz- pop stack frame; goto somefunc(); der unteren Ebene pop stack frame; goto somefunc(); pop stack frame; goto somefunc(); . In unserem Beispiel bedeutet das, bevor wir bar aufrufen, foo reinigt sich selbst und dann, anstatt bar als Unterroutine aufzurufen, führen wir eine Low-Level- goto Operation zum Anfang der bar . Foo ‘s hat sich schon aus dem Stack herausgeräumt, also wenn bar startet, sieht es so aus, als hätte der foo Namen bar , und wenn bar seinen Wert zurückgibt, gibt er es direkt an den foo , anstatt es an foo zu geben dann gib es an seinen Anrufer zurück.

Und auf Schwanz Rekursion:

Die Tail-Rekursion erfolgt, wenn eine function als letzte Operation das Ergebnis des Aufrufs selbst zurückgibt . Tail Rekursion ist leichter zu handhaben, denn anstatt irgendwo an den Anfang irgendeiner zufälligen function springen zu müssen, musst du nur zum Anfang von dir zurückgehen, 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 zu:

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

Was ich an dieser Beschreibung mag, ist, wie kurz und einfach es für diejenigen zu verstehen ist, die aus einem imperativen Sprachhintergrund kommen (C, C ++, Java)

Beachten Sie zunächst, dass nicht alle Sprachen dies unterstützen.

TCO gilt für einen speziellen Rekursionsfall. Der core davon ist, wenn das letzte, was du in einer function tust, sich selbst nennt (zB wenn es sich selbst von der “Tail” -Position aus aufruft), kann dies vom Compiler so optimiert werden, dass es wie eine Iteration anstatt einer Standardrekursion agiert.

Sie sehen, normalerweise während der Rekursion, muss die Laufzeit alle rekursiven Aufrufe verfolgen, so dass, wenn einer zurückkehrt, es bei dem vorherigen Aufruf fortgesetzt werden kann und so weiter. (Versuchen Sie, das Ergebnis eines rekursiven Aufrufs manuell auszugeben, um eine visuelle Vorstellung davon zu bekommen, wie dies funktioniert.) Das Verfolgen aller Aufrufe nimmt Platz in Anspruch, was signifikant wird, wenn sich die function selbst viel nennt. Aber mit TCO kann man einfach sagen “gehe zurück zum Anfang, nur diesmal ändere die Parameterwerte auf diese neuen Werte”. Es kann das tun, weil sich nichts nach dem rekursiven Aufruf auf diese Werte bezieht.

Schau hier:

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

Wie Sie wahrscheinlich wissen, können rekursive functionsaufrufe einen Stapel zerstören. Es ist einfach, den Stapelplatz schnell zu verlassen. Mit der Tail-Call-Optimierung können Sie einen rekursiven Stilalgorithmus erstellen, der konstanten Stack-Speicherplatz verwendet. Daher wird er nicht größer und wächst nicht und Sie erhalten Stack-Fehler.

  1. Wir sollten sicherstellen, dass es keine goto-statementen in der function selbst gibt. Vorsicht, da der functionsaufruf das letzte in der aufgerufenen function ist.

  2. Großskalige Rekursionen können dies für Optimierungen verwenden, aber in kleinem Maßstab verringert der statementsoverhead, um den functionsaufruf zu einem Tail-Aufruf zu machen, den eigentlichen Zweck.

  3. TCO kann zu einer für immer laufenden function führen:

     void eternity() { eternity(); } 

Der rekursive functionsansatz hat ein Problem. Es baut einen Aufruf-Stack der Größe O (n) auf, was unseren gesamten Speicher zu Kosten O (n) macht. Dies macht es anfällig für einen Stapelüberlauferrors, bei dem der Aufrufstapel zu groß wird und nicht mehr genügend Platz hat. Tail Cost Optimization (TCO) -Schema. Wo es rekursive functionen optimieren kann, um den Aufbau eines hohen Call-Stacks zu vermeiden und somit die Speicherkosten zu sparen.

Es gibt viele Sprachen, die TCO machen (Javascript, Ruby und wenige C), wo Python und Java nicht TCO machen.

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