Optimiert Python die Schwanzrekursion?

204

Ich habe den folgenden Code, der mit dem folgenden Fehler fehlschlägt:

RuntimeError: Maximale Rekursionstiefe überschritten

Ich habe versucht, dies neu zu schreiben, um die Optimierung der Schwanzrekursion (TCO) zu ermöglichen. Ich glaube, dass dieser Code erfolgreich gewesen sein sollte, wenn eine TCO stattgefunden hätte.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Sollte ich zu dem Schluss kommen, dass Python keine TCO durchführt, oder muss ich es nur anders definieren?

Jordan Mack
quelle
11
@Wessie TCO ist eine einfache Betrachtung, wie dynamisch oder statisch die Sprache ist. Lua zum Beispiel macht es auch. Sie müssen lediglich Tail-Aufrufe erkennen (ziemlich einfach, sowohl auf AST-Ebene als auch auf Bytecode-Ebene) und dann den aktuellen Stack-Frame wiederverwenden, anstatt einen neuen zu erstellen (auch einfach, in Interpreten sogar noch einfacher als in nativem Code). .
11
Oh, ein nitpick: Sie sprechen ausschließlich über Endrekursion, sondern verwenden das Akronym „TCO“, den Schwanz bedeutet Anruf Optimierung und gilt für jede Instanz return func(...)(explizit oder implizit), ob es rekursiv ist oder nicht. TCO ist eine richtige Obermenge von TRE und nützlicher (z. B. macht es einen Weitergabestil möglich, was TRE nicht kann) und nicht viel schwieriger zu implementieren.
1
Hier ist ein hackiger Weg, um es zu implementieren - ein Dekorateur, der das Auslösen
jsbueno
2
Wenn Sie sich auf die Schwanzrekursion beschränken, halte ich einen richtigen Traceback nicht für sehr nützlich. Sie haben einen Anruf foovon innen zu einem Anruf foovon innen nach fooinnen von einem Anruf zu foo... Ich glaube nicht, dass nützliche Informationen durch den Verlust verloren gehen würden.
Kevin
1
Ich habe kürzlich etwas über Kokosnuss gelernt, es aber noch nicht ausprobiert. Ein Blick lohnt sich. Es wird behauptet, eine Optimierung der Schwanzrekursion zu haben.
Alexey

Antworten:

214

Nein, und das wird es auch nie, da Guido van Rossum es vorzieht, richtige Rückverfolgungen zu haben:

Eliminierung der Schwanzrekursion (2009-04-22)

Letzte Worte zu Tail Calls (27.04.2009)

Sie können die Rekursion mit einer Transformation wie folgt manuell entfernen:

>>> def trisum(n, csum):
...     while True:                     # Change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion

>>> trisum(1000,0)
500500
John La Rooy
quelle
12
Oder wenn Sie es so umwandeln wollen - nur : from operator import add; reduce(add, xrange(n + 1), csum)?
Jon Clements
38
@ JonClements, das funktioniert in diesem Beispiel. Die Umwandlung in eine while-Schleife funktioniert in allgemeinen Fällen für die Schwanzrekursion.
John La Rooy
25
+1 Um die richtige Antwort zu sein, aber dies scheint eine unglaublich knochige Designentscheidung zu sein. Die angegebenen Gründe scheinen sich darauf zu beschränken, "es ist schwer zu tun, wenn man bedenkt, wie Python interpretiert wird, und ich mag es sowieso nicht, also da!"
Basic
12
@jwg Also ... was? Sie müssen eine Sprache schreiben, bevor Sie schlechte Designentscheidungen kommentieren können? Kaum logisch oder praktisch. Ich gehe aus Ihrem Kommentar davon aus, dass Sie keine Meinung zu Funktionen (oder deren Fehlen) in einer Sprache haben, die jemals geschrieben wurde.
Basic
2
@Basic Nein, aber Sie müssen den Artikel lesen, den Sie kommentieren. Es scheint sehr stark zu sein, dass Sie es nicht wirklich gelesen haben, wenn man bedenkt, wie es auf Sie "herunterläuft". (Möglicherweise müssen Sie leider beide verknüpften Artikel lesen, da einige Argumente auf beide verteilt sind.) Es hat fast nichts mit der Implementierung der Sprache zu tun, sondern alles mit der beabsichtigten Semantik.
Veky
178

Ich habe ein Modul veröffentlicht, das die Tail-Call-Optimierung durchführt (sowohl die Tail-Rekursion als auch den Continuation-Passing-Stil): https://github.com/baruchel/tco

Optimierung der Schwanzrekursion in Python

Es wurde oft behauptet, dass die Schwanzrekursion nicht zur pythonischen Codierungsmethode passt und dass man sich nicht darum kümmern sollte, wie man sie in eine Schleife einbettet. Ich möchte mit diesem Standpunkt nicht streiten. Manchmal mag ich es jedoch aus verschiedenen Gründen, neue Ideen als schwanzrekursive Funktionen anstatt mit Schleifen zu versuchen oder zu implementieren (ich konzentriere mich eher auf die Idee als auf den Prozess, habe zwanzig kurze Funktionen gleichzeitig auf meinem Bildschirm und nicht nur drei "Pythonic"). Funktionen, die in einer interaktiven Sitzung arbeiten, anstatt meinen Code zu bearbeiten usw.).

Die Optimierung der Schwanzrekursion in Python ist in der Tat recht einfach. Es soll zwar unmöglich oder sehr knifflig sein, aber ich denke, es kann mit eleganten, kurzen und allgemeinen Lösungen erreicht werden. Ich denke sogar, dass die meisten dieser Lösungen Python-Funktionen nicht anders verwenden, als sie sollten. Saubere Lambda-Ausdrücke, die mit Standardschleifen zusammenarbeiten, führen zu schnellen, effizienten und vollständig verwendbaren Tools für die Implementierung der Optimierung der Schwanzrekursion.

Aus persönlichen Gründen habe ich ein kleines Modul geschrieben, das eine solche Optimierung auf zwei verschiedene Arten implementiert. Ich möchte hier über meine beiden Hauptfunktionen diskutieren.

Der saubere Weg: Modifizieren des Y-Kombinators

Der Y-Kombinator ist bekannt; Es erlaubt die rekursive Verwendung von Lambda-Funktionen, erlaubt es jedoch nicht, rekursive Aufrufe in eine Schleife einzubetten. Lambda-Kalkül allein kann so etwas nicht. Eine geringfügige Änderung des Y-Kombinators kann jedoch den rekursiven Aufruf schützen, der tatsächlich ausgewertet werden soll. Die Auswertung kann sich somit verzögern.

Hier ist der berühmte Ausdruck für den Y-Kombinator:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

Mit einer sehr kleinen Änderung konnte ich bekommen:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))

Anstatt sich selbst aufzurufen, gibt die Funktion f jetzt eine Funktion zurück, die denselben Aufruf ausführt. Da sie ihn jedoch zurückgibt, kann die Auswertung später von außen erfolgen.

Mein Code lautet:

def bet(func):
    b = (lambda f: (lambda x: x(x))(lambda y:
          f(lambda *args: lambda: y(y)(*args))))(func)
    def wrapper(*args):
        out = b(*args)
        while callable(out):
            out = out()
        return out
    return wrapper

Die Funktion kann folgendermaßen verwendet werden: Hier sind zwei Beispiele mit schwanzrekursiven Versionen von Fakultät und Fibonacci:

>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55

Offensichtlich ist die Rekursionstiefe kein Problem mehr:

>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42

Dies ist natürlich der einzige wirkliche Zweck der Funktion.

Mit dieser Optimierung kann nur eines nicht erreicht werden: Sie kann nicht mit einer rekursiven Endfunktion verwendet werden, die zu einer anderen Funktion ausgewertet wird (dies ergibt sich aus der Tatsache, dass aufrufbare zurückgegebene Objekte alle als weitere rekursive Aufrufe ohne Unterscheidung behandelt werden). Da ich normalerweise keine solche Funktion benötige, bin ich mit dem obigen Code sehr zufrieden. Um jedoch ein allgemeineres Modul bereitzustellen, habe ich etwas mehr darüber nachgedacht, um eine Problemumgehung für dieses Problem zu finden (siehe nächster Abschnitt).

In Bezug auf die Geschwindigkeit dieses Prozesses (was jedoch nicht das eigentliche Problem ist) ist er ziemlich gut. Schwanzrekursive Funktionen werden sogar viel schneller als mit dem folgenden Code mit einfacheren Ausdrücken ausgewertet:

def bet1(func):
    def wrapper(*args):
        out = func(lambda *x: lambda: x)(*args)
        while callable(out):
            out = func(lambda *x: lambda: x)(*out())
        return out
    return wrapper

Ich denke, dass die Bewertung eines Ausdrucks, auch wenn er kompliziert ist, viel schneller ist als die Bewertung mehrerer einfacher Ausdrücke, was in dieser zweiten Version der Fall ist. Ich habe diese neue Funktion nicht in meinem Modul behalten, und ich sehe keine Umstände, unter denen sie anstelle der "offiziellen" verwendet werden könnte.

Fortsetzung übergeben Stil mit Ausnahmen

Hier ist eine allgemeinere Funktion; Es ist in der Lage, alle rekursiven Funktionen zu verarbeiten, einschließlich derjenigen, die andere Funktionen zurückgeben. Rekursive Aufrufe werden mithilfe von Ausnahmen von anderen Rückgabewerten erkannt. Diese Lösung ist langsamer als die vorherige; Ein schnellerer Code könnte wahrscheinlich geschrieben werden, indem einige spezielle Werte als "Flags" verwendet werden, die in der Hauptschleife erkannt werden, aber ich mag die Idee, spezielle Werte oder interne Schlüsselwörter zu verwenden, nicht. Es gibt eine lustige Interpretation der Verwendung von Ausnahmen: Wenn Python keine rekursiven Aufrufe mag, sollte eine Ausnahme ausgelöst werden, wenn ein rekursiver Aufruf auftritt, und die pythonische Methode besteht darin, die Ausnahme abzufangen, um eine saubere zu finden Lösung, was eigentlich hier passiert ...

class _RecursiveCall(Exception):
  def __init__(self, *args):
    self.args = args
def _recursiveCallback(*args):
  raise _RecursiveCall(*args)
def bet0(func):
    def wrapper(*args):
        while True:
          try:
            return func(_recursiveCallback)(*args)
          except _RecursiveCall as e:
            args = e.args
    return wrapper

Jetzt können alle Funktionen verwendet werden. Im folgenden Beispiel f(n)wird die Identitätsfunktion für jeden positiven Wert von n ausgewertet:

>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42

Natürlich könnte argumentiert werden, dass Ausnahmen nicht dazu gedacht sind, den Interpreter absichtlich umzuleiten (als eine Art gotoAussage oder wahrscheinlich eher als eine Art Weitergabestil), was ich zugeben muss. Aber auch hier finde ich die Idee, tryeine einzelne Zeile als returnAnweisung zu verwenden , lustig : Wir versuchen, etwas zurückzugeben (normales Verhalten), können dies jedoch aufgrund eines rekursiven Aufrufs (Ausnahme) nicht tun.

Erste Antwort (29.08.2013).

Ich habe ein sehr kleines Plugin für die Behandlung der Schwanzrekursion geschrieben. Sie finden es möglicherweise mit meinen Erklärungen dort: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Es kann eine Lambda-Funktion, die mit einem Schwanzrekursionsstil geschrieben wurde, in eine andere Funktion einbetten, die sie als Schleife auswertet.

Das interessanteste Merkmal dieser kleinen Funktion ist meiner bescheidenen Meinung nach, dass die Funktion nicht auf einem schmutzigen Programmier-Hack beruht, sondern auf einem bloßen Lambda-Kalkül: Das Verhalten der Funktion wird beim Einfügen in eine andere Lambda-Funktion in ein anderes geändert sieht dem Y-Kombinator sehr ähnlich.

Thomas Baruchel
quelle
Könnten Sie bitte ein Beispiel für die Definition einer Funktion (vorzugsweise ähnlich einer normalen Definition) geben, die unter Verwendung Ihrer Methode eine von mehreren anderen Funktionen basierend auf einer bestimmten Bedingung aufruft? Kann Ihre Verpackungsfunktion bet0auch als Dekorateur für Klassenmethoden verwendet werden?
Alexey
@Alexey Ich bin nicht sicher, ob ich Code blockweise in einen Kommentar schreiben kann, aber Sie können natürlich die defSyntax für Ihre Funktionen verwenden, und tatsächlich basiert das letzte Beispiel oben auf einer Bedingung. In meinem Beitrag baruchel.github.io/python/2015/11/07/… sehen Sie einen Absatz, der mit "Natürlich können Sie einwenden, dass niemand einen solchen Code schreiben würde" beginnt, in dem ich ein Beispiel mit der üblichen Definitionssyntax gebe. Für den zweiten Teil Ihrer Frage muss ich etwas mehr darüber nachdenken, da ich eine Weile keine Zeit damit verbracht habe. Grüße.
Thomas Baruchel
Sie sollten sich darum kümmern, wo der rekursive Aufruf in Ihrer Funktion stattfindet, auch wenn Sie eine Implementierung ohne TCO-Sprache verwenden. Dies liegt daran, dass der Teil der Funktion, der nach dem rekursiven Aufruf auftritt, der Teil ist, der auf dem Stapel gespeichert werden muss. Wenn Sie Ihre Funktion endrekursiv machen, wird die Menge an Informationen, die Sie pro rekursivem Aufruf speichern müssen, minimiert, sodass Sie mehr Platz für große rekursive Aufrufstapel haben, wenn Sie diese benötigen.
Josiah
21

Das Wort von Guido ist unter http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Ich habe kürzlich in meinem Python-Verlaufsblog einen Eintrag über die Ursprünge der Funktionsfunktionen von Python veröffentlicht. Eine Nebenbemerkung über die Nichtunterstützung der Tail Recursion Elimination (TRE) löste sofort mehrere Kommentare darüber aus, wie schade, dass Python dies nicht tut, einschließlich Links zu aktuellen Blogeinträgen anderer, die versuchen, zu "beweisen", dass TRE zu Python hinzugefügt werden kann leicht. Lassen Sie mich also meine Position verteidigen (das heißt, ich möchte kein TRE in der Sprache). Wenn Sie eine kurze Antwort wünschen, ist sie einfach unpythonisch. Hier ist die lange Antwort:

Jon Clements
quelle
12
Und hier liegt das Problem mit dem sogenannten BDsFL.
Adam Donahue
6
@AdamDonahue Warst du mit jeder Entscheidung eines Komitees vollkommen zufrieden? Zumindest erhalten Sie eine begründete und maßgebliche Erklärung von der BDFL.
Mark Ransom
2
Nein, natürlich nicht, aber sie scheinen mir ausgeglichener zu sein. Dies von einem Preskriptivisten, nicht von einem Deskriptivisten. Die Ironie.
Adam Donahue
6

CPython unterstützt und wird wahrscheinlich niemals die Tail-Call-Optimierung unterstützen, die auf den Aussagen von Guido van Rossum zu diesem Thema basiert .

Ich habe Argumente gehört, die das Debuggen erschweren, weil es den Stack-Trace modifiziert.

rekursiv
quelle
18
@mux CPython ist die Referenzimplementierung der Programmiersprache Python. Es gibt andere Implementierungen (wie PyPy, IronPython und Jython), die dieselbe Sprache implementieren, sich jedoch in den Implementierungsdetails unterscheiden. Die Unterscheidung ist hier nützlich, da (theoretisch) eine alternative Python-Implementierung erstellt werden kann, die TCO ausführt. Mir ist jedoch nicht bekannt, dass jemand darüber nachdenkt, und die Nützlichkeit wäre begrenzt, da der darauf basierende Code bei allen anderen Python-Implementierungen nicht funktioniert.
3

Probieren Sie die experimentelle Makropy- TCO-Implementierung für die Größe aus.

Mark Lawrence
quelle
2

Neben der Optimierung der Schwanzrekursion können Sie die Rekursionstiefe manuell einstellen, indem Sie:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
zhenv5
quelle
5
Warum benutzt du nicht einfach jQuery?
Jeremy Hert
5
Weil es auch keine TCO bietet? :-D stackoverflow.com/questions/3660577/…
Veky