Tail-Recursion in Python

[bwbg]

Gibt es gewichtige Gründe, warum Python keine Tail-Recursion unterstützt? Mit fiele jetzt auf Anhieb ein undurchsichtiger Stack-Trace ein. Aus Interpretersicht kann ich leider nicht viel sagen. Syntaktisch könnte man das continue-Schlüsselwort überladen, welche dem Interpreter klar macht, dass der aktuelle Stack-Frame recycelt wird:

Code: Alles auswählen

def fac(n, acc=1):
    if n == 1: return acc
    continue(n - 1, acc * n)

Hier muss der Anwender jedoch selbst sicherstellen, dass der derzeitige Stack-Frame nicht mehr benötigt wird.

[cofi]

GvR zum Thema: http://neopythonic.blogspot.de/2009/04/ ... ation.html

Dass Stack-Traces nicht nur undurchsichtig, sondern unbrauchbar werden, finde ich einen sehr gewichtigen Grund. Dass TCO nur unter sehr engen Schranken nuetzlich ist, macht es nicht besser.

Code: Alles auswählen

def factorial(n):
    if n == 1:
        return 1
    else:
        return n + factorial(n - 1)

Und schon ist Schluss mit TCO ..

[BlackJack]

Ein weiterer Grund: Nicht trivial zu implementieren, bzw. nicht überall wie in CPython. Müsste dann ja auch in Jython und IronPython umgesetzt werden.

Gibt es denn gewichtige Gründe warum Python TCO unterstützen sollte?

[pillmuncher]

@cofi: Dass man seinen Code anpassen muss, damit er mit TCO funtioniert, ist nichts was gegen TCO spricht. Genauso könnte man gegen Generatorfunktionen sein, weil sie nicht so funktionieren, wie normale Funktionen, oder gegen Multithreading, weil man da mit Locks hantieren muss.

Ich wünsche mir ebenfalls TCO, aber ich hätte gerne eine Keyword-Lösung, zB:

Code: Alles auswählen

def factorial(n):
    if n == 1:
        return 1
    else:
        return from n * factorial(n - 1)  # FictionalSyntaxError, see below
        ^^^^^^ ^^^^

Der Vorteil dabei wäre, dass man die Syntax so festlegen könnte, dass nach einem return from ausschließlich ein dotted_name + geklammerte parameter_list stehen darf, wodurch man sicher sein kann, dass tatächlich eine TCO-Transformation möglich ist und auch stattfindet. Damit wäre der o.s. Code ungültig. Erlaubt wäre aber:

Code: Alles auswählen

def factorial(n):
    def fact(n, acc):
        if n == 1:
            return acc
        else:
            return from fact(n - 1, n * acc)
    return from fact(n, 1)

Ich wünsche es mir übrigens nicht, weil ich Rekursion so super finde, sondern weil ich Continuation Passing Style mag.

But you can always roll your own.

Oder man baut Continuations ohne CTO, aber dafür monadisch.

[cofi]

@pillmuncher, Nein so meinte ich das nicht. Mein Argument ist eher, dass man sehr schnell Code schreibt, der keinen TC hat und damit aus der Optimierung herausfaellt ... man sich im Gegenzug aber meist darauf verlaesst, dass eine TCO stattfindet.

Wenn man dann sowas wie Scalas `@tailrec` Annotation hat oder ein Sprachkonstrukt hat, dass den TC explizit macht, wie du es vorstellst sieht die Sache natuerlich anders aus.

Ich bin nur etwas angefressen bei dem Thema, weil Leute die das fordern oft keine Ahnung haben und dass als wuenschenswert per se darstellen .. is ja schliesslich ne Optimierung.

[bwbg]

Ich habe überhaupt nichts gefordert (zumindest nicht willentlich). Und ja, ich habe keine Ahnung. Wenn dem so wäre, dann hätte ich kein Thema dazu aufmachen müssen.

Einen impliziten TC habe ich von vorneherein ausgeschlossen. Deswegen dachte ich über das continue(...) nach. Ein expliziter TC setzt voraus, dass man sich im Vorfeld bereits darüber Gedanken gemacht hat.

[pillmuncher]

@bwbg: Ich denke nicht, dass cofi dich persönlich gemeint hat. Er schrieb ja bereits, dass die Art seines Postings auch seiner generellen Angefressenheit angesichts des Themas geschuldet ist.

continue(...), so wie du es vorschlägst, würde nur direkte Rekursion ermöglichen. Continuation Passing Style ginge damit nicht, auch nicht wechselweise Rekursion zweier Funktionen.

Eine andere Frage stellt sich außerdem: wünschen wir uns, dass der aktuelle Call Frame wiederverwendet wird, oder soll ein neuer erzeugt und der alte dem Garbage Collector überlassen werden? Im ersten Fall wäre es vermutlich wirklich eine Optimierung, im zweiten Fall wäre der einzige Vorteil, dass der Stack Frame nicht wächst. Mir würde das genügen.

[cofi]

@bwbg: Nein ich habe nicht dich persoenlich gemeint. Ich will dich auch nicht vom Posten abbringen, im Gegenteil

Es ist nur so, dass man in Python sehr einfach Funktionen konstruieren kann, die nach TR aussehen, aber keine sind. Z.B. wenn Context Manager im Spiel sind. Ich bin mir nicht sicher, ob es gut waere Stackmanagement in die Sprache mit aufzunehmen (es gibt schliesslich Stackless Python), aber pragmatisch waere es ganz nett um Rekursion praktisch anwendbar zu machen.

[pillmuncher]

[...] dass man in Python sehr einfach Funktionen konstruieren kann, die nach TR aussehen, aber keine sind. Z.B. wenn Context Manager im Spiel sind. [...]

Meh! Spielverderber! Ich glaube, Context Manager wurden nur eingeführt, weil Guido kein TCO will und es mit diesen praktisch verunmöglicht wurde.

[BlackJack]

Was ist denn an Kontextmanagern mehr ein Problem als am traditionellen ``try``/``finally``?

[cofi]

Technisch nichts, aber es ist vielleicht schwieriger zu sehen, dass

Code: Alles auswählen

with open(path) as f:
    ... 
    return foo(data)

genau das gleiche Problem wie

Code: Alles auswählen

try:
    f = open(path)
    ...
    return foo(data)
finally:
    f.close()

darstellt, weil bei CM der Methodenaufruf tatsaechlich die letzte Zeile im konkreten Code ist, aber halt nicht mehr nach dem desugaring.

[Sirius3]

noch mehr Zuckerguss gibt es bei Dekoratoren und Metaprogrammierung, obwohl es da auch genügen Fälle gäbe, in denen ein "return from" sinnvoll ist.