Konvertieren einer Funktion zur Verwendung der Tail-Rekursion - eine formale Studie

  

eine Methode um (automatisch) Funktionen zu rekursiv zu machen?

Es gibt also zwei Teile:

• Erkennen, dass eine gegebene rekursive Funktion in eine tail-rekursive Form umgewandelt werden kann und diese Umwandlung
macht
• die Implementierung von Tail-Calls auf effiziente Weise, so lohnt sich die Transformation.

Rekursion in Tail-Rekursion transformieren

Es erscheint relativ einfach, tail rekursive Definitionen syntaktisch zu erkennen. "Tail recursive" bedeutet nämlich nur, dass der Aufruf syntaktisch im Tail des Ausdrucks erscheint.

z. Die Scheme-Leute beschreiben:

  

Das Kompilieren geeigneter Selbstaufrufe als Sprünge reicht nicht aus   Erreiche volle Schwanz-Rekursion. Stattdessen teilen wir alle syntaktisch auf   Unterausdruck Positionen in der Ausgangssprache in zwei Klassen: Schwanz   (oder Reduktions-) Position und Unterproblemposition. Im einfachen   Ausdruck (wenn predicate konsequente Alternative), das predicate ist a   Teilproblemposition, während sowohl konsequent als auch alternativ sind   Reduktionspositionen. Dieser syntaktische Begriff kann leicht erweitert werden   beliebig verschachtelte Unterausdrücke.

• Kompilieren von Sprachen höherer Ordnung in vollständig tail-recursive Portable C

Transformieren von Funktionen in Tail-Aufrufe

Der knifflige Teil Ihrer Frage sind Optimierungen zum Identifizieren und Umwandeln rekursiver Kandidatenrechnungen in tailrekursive Berechnungen.

Eine Referenz ist in GHC, die Inlining und eine breite Palette von Vereinfachungsregeln verwendet, um rekursive Aufrufe wegzuspringen, bis ihre zugrunde liegende tailrekursive Struktur erhalten bleibt.

• Geheimnisse des GHC-Inliners

Tail Call Elimination

Sobald Sie Ihre Funktionen in einer tail-recursiven Form haben, möchten Sie dies effektiv implementiert haben. Wenn Sie eine Schleife erzeugen können, ist das ein guter Anfang. Wenn Ihr Zielcomputer dies nicht tut, dann wird die Beseitigung von Tail Calls "einige Tricks benötigen. Um Odersky und Schinz zu zitieren, unten zitiert,

  

Im Laufe der Jahre wurden verschiedene Techniken zur Beseitigung vorgeschlagen   allgemeine (und nicht nur rekursive) Tail-Aufrufe, meistens für Compiler   Targeting C.

     

... das ganze Programm in eine große Funktion bringen und simulieren   Funktionsaufrufe mit direkten Sprüngen oder Schalteranweisungen innerhalb dieser Funktion.

     

... Eine beliebte Technik ist ein Trampolin. Ein Trampolin ist ein Äußeres   Funktion, die wiederholt eine innere Funktion aufruft. Jedes Mal die innere Funktion   möchte eine andere Funktion aufrufen, sie nennt sie nicht direkt sondern einfach   gibt seine Identität (z. B. als eine Schließung) an das Trampolin zurück, das dann die   sich selbst anrufen. Unbegrenztes Stapelwachstum wird somit vermieden, aber etwas Leistung ist   unweigerlich verloren, vor allem, weil alle vom Trampolin getätigten Anrufe Anrufe sind   zu statisch unbekannten Funktionen.

     

Eine andere Technik ist Henry Bakers "Cheney on the M.T.A."   Mit seiner Technik muss das Programm zunächst in Fortsetzungsdurchgang umgewandelt werden   Stil (CPS), also alle Anrufe in Tail-Calls verwandeln, und kann dann sein   wie üblich zusammengestellt. Zur Laufzeit, wenn der Stapel überläuft, wird der   aktuelle Fortsetzung wird gebaut und zurückgegeben (oder longjmped) zum Trampolin   "Warten" am unteren Ende des Call Stack.

• Beseitigung von Tail-Calls auf Java Virtuelle Maschine , Michel Schinz Martin Odersky, 2001

• Henry G. Baker, Jr. CONS sollte seine Argumente nicht teilen, Teil II: Cheney auf der M. T. A. Entwurfsversion, Januar 1994.

Mercury enthält eine Reihe von Optimierungen, um Dinge automatisch tail-rekursiv zu machen. ( Mercury ist eine Logik-Programmiersprache mit erzwungener Reinheit. Es spricht also eher von Prädikaten als von Funktionen, aber viele davon Dieselben Ideen gelten für Mercury-Programme wie für Haskell-Programme.Ein viel größerer Unterschied als logisch zu sein ist, dass er eher streng als faul ist.

"Accumulator introduction" erzeugt spezielle Versionen von Prädikaten mit einem zusätzlichen Akkumulator-Parameter, um assoziative Operationen vor dem rekursiven Aufruf verschieben zu können. Offensichtlich führt diese Optimierung nicht notwendigerweise zu tail-rekursiven Prädikaten, sondern führt oft zu einer Form, die durch die zweite Optimierung optimiert werden kann:

"Last Call Modulo Constructors" ermöglicht im Wesentlichen einen rekursiven Aufruf, der nur von Konstruktor-Anwendungen gefolgt wird, um neu geschrieben zu werden, so dass der Wert zuerst aufgebaut wird, der ein "Loch" enthält und der rekursive Aufruf seine Ausgabe direkt in die Speicheradresse von zurückgibt das "Loch", anstatt die normale Rückgabewert-Konvention zu verwenden. Ich glaube, Haskell würde diese Optimierung kostenlos bekommen, einfach wegen Faulheit.

Diese beiden Optimierungen sind in der Veröffentlichung beschrieben, in der die Mercury-Programme rekursiv gemacht werden .