Sollte ich die Tail-Rekursion in Prolog und generell vermeiden?

Question

Ich arbeite durch "Learn Prolog jetzt" Online-Buch zum Spaß.

Ich versuche, ein Prädikat zu schreiben, das durch jedes Mitglied einer Liste geht und eines hinzufügt, das Akkumulatoren verwendet. Ich habe es schon ohne Schwanzrekursion gemacht.

Aber ich habe gelesen, dass es besser ist, diese Art der Rekursion aus Leistungsgründen zu vermeiden. Ist das wahr? Wird es als "gute Praxis" angesehen, die Tail Recursion immer zu verwenden? Wird es sich lohnen, Akkus zu benutzen, um eine gute Angewohnheit zu bekommen?

Ich habe versucht, dieses Beispiel in die Verwendung von Akkumulatoren zu ändern, aber es kehrt die Liste um. Wie kann ich das vermeiden?

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result). 
accAddOne([],A,A). 
addone(List,Result) :- accAddOne(List,[],Result). 

Answer 1

Kurze Antwort: Schwanz Rekursion ist wünschenswert, aber nicht zu stark betonen.

Ihr ursprüngliches Programm ist als Tail rekursiv, wie Sie in Prolog bekommen können. Aber es gibt wichtigere Probleme: Korrektheit und Terminierung.

Tatsächlich sind viele Implementierungen mehr als bereit, Tail-Recursiveness für andere Eigenschaften zu opfern, die sie für wichtiger halten. Zum Beispiel steadfastness.

Aber Ihre versuchte Optimierung hat einen Punkt. Zumindest aus einer historischen Perspektive.

In den 1970er Jahren war die wichtigste KI-Sprache LISP. Und die entsprechende Definition würde

(defun addone (xs) 
    (cond ((null xs) nil) 
    (t (cons (+ 1 (car xs)) 
     (addone (cdr xs)))))) 

wird, die nicht direkt Schwanz-rekursiv ist: Der Grund ist die cons: In Implementierungen dieser Zeit ihre Argumente zuerst ausgewertet wurden, nur dann, die cons ausgeführt werden kann. Dies zu überschreiben, wie Sie angegeben haben (und die resultierende Liste umzukehren), war eine mögliche Optimierungstechnik.

In Prolog können Sie jedoch dank logischer Variablen die Nachteile erstellen, bevor Sie die tatsächlichen Werte kennen. So viele Programme, die in LISP nicht tail-rekursiv waren, wurden in tail-rekursive Programme in Prolog übersetzt.

Die Auswirkungen davon können noch in vielen Prolog-Lehrbüchern gefunden werden.

Answer 2

Ich glaube nicht, dass die erste Version von addone zu weniger effizienten Code führen soll. Es ist auch viel lesbarer, daher sehe ich keinen Grund, warum es ratsam sein sollte, es zu vermeiden.

In komplexeren Beispielen ist der Compiler möglicherweise nicht in der Lage, den Code automatisch zur Tail-Rekursion zu übertragen. Dann kann es sinnvoll sein, es als Optimierung neu zu schreiben, aber nur, wenn es wirklich notwendig ist.

Also, wie können Sie eine funktionierende Tail rekursive Version von addone implementieren? Es betrüge kann aber davon aus, dass reverse mit Schwanz-Rekursion durchgeführt wird (siehe beispielsweise here), dann kann es verwendet werden, um Ihr Problem zu beheben:

es extrem ungeschickt ist, though. :-)

Übrigens kann ich keine einfachere Lösung finden. Es kann aus dem gleichen Grund wie foldr in Haskell ist normalerweise nicht mit Schwanz Rekursion definiert.

Answer 3

Ihre addOne-Prozedur bereits ist Tail rekursiv.

Es gibt keine Auswahlpunkte zwischen dem Kopf und dem letzten rekursiven Aufruf, weil/2 deterministisch ist.

Akkumulatoren werden manchmal hinzugefügt, um Tail-Rekursion zu ermöglichen, das einfachere Beispiel, das ich mir vorstellen kann, ist reverse/2. Hier ist eine naive reverse (nreverse/2), nicht Schwanz rekursive

nreverse([], []). 
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R). 

wenn wir einen Akkumulator

reverse(L, R) :- reverse(L, [], R). 
reverse([], R, R). 
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R). 

hinzufügen jetzt umkehren/3 Schwanz rekursiv: der rekursive Aufruf ist die letzte, und kein Wahlpunkt ist übrig.

Answer 4

O. P. sagte:

Aber ich habe gelesen, dass es besser ist, [tail] Rekursion aus Leistungsgründen zu vermeiden. Ist das wahr? Wird es als "gute Praxis" angesehen, die Tail Recursion immer zu verwenden? Wird es wert sein, die Akkus zu benutzen, um eine gute Gewohnheit zu bekommen?

Es ist eine ziemlich einfache Optimierung, ein tail-rekursives Konstrukt in Iteration (eine Schleife) zu konvertieren. Da der tail (rekursive) Aufruf das letzte ist, was getan wird, kann der Stapelrahmen in dem rekursiven Aufruf wiederverwendet werden, was die Rekursion in jeder Hinsicht zu einer Schleife macht, indem einfach zum Anfang des Prädikats/function/method gesprungen wird /Subroutine. Daher wird ein tail-rekursives Prädikat den Stapel nicht überlaufen lassen. Tail-recursive Konstrukt, mit der Optimierung angewendet haben die folgenden Vorteile:

Etwas schnellere Ausführung, da neue Stack-Frames nicht zugewiesen/freigegeben werden müssen; Außerdem erhalten Sie eine bessere Fundstelle, also wohl weniger Paging.

Keine obere Grenze für die Rekursionstiefe.

Kein Stapel überläuft.

Die möglichen Nachteile?

• Verlust von nützlichen Stack-Trace. Kein Problem, wenn TRO nur in einem release/optimierten Build und nicht in einem Debug-Build angewendet wird, aber ...
• Entwickler schreiben Code, der von TRO abhängt, was bedeutet, dass der Code gut läuft, wenn TRO angewendet wird, ohne zu scheitern TRO wird angewendet. Das bedeutet, dass im obigen Fall (TRO nur in Release/optimierten Builds) eine funktionale Änderung zwischen Release- und Debug-Builds besteht, was bedeutet, dass die Wahl der Compiler-Optionen zwei unterschiedliche Programme aus identischem Quellcode erzeugt.

Dies ist natürlich nicht ein Problem, wenn der Sprachstandard Tail Recursion-Optimierung erfordert.

Wikipedia zitieren:

Endrekursion von Bedeutung ist, weil sie ohne Zugabe von ein neuer Stapelrahmen zu dem Call-Stack implementiert werden können. Der größte Teil des Rahmens der aktuellen Prozedur wird nicht mehr benötigt, und er kann durch den Rahmen des Tail Calls entsprechend geändert werden (ähnlich der Überlagerung für Prozesse, aber für die Funktion Aufrufe). Das Programm kann dann zum aufgerufenen Unterprogramm springen. Die Erzeugung eines solchen Codes anstelle einer Standard-Ruffolge wird als Tail Call Elimination oder Tail Rufoptimierung bezeichnet.

Siehe auch:

• What Is Tail Call Optimization?
• The Portland Pattern Repository on the matter
• und sogar Microsoft's MSDN

Ich habe nie verstanden, warum mehr Sprachen nicht Endrekursion Optimierung