Endlosschleife in Python oder dynamische Sprachen

Question

Kürzlich Detecting habe ich versucht, die Erstellung Programm so etwas wie dies mit GCC:

int f(int i){ 
    if(i<0){ return 0;} 
    return f(i-1); 
f(100000); 

und es lief ganz gut. Als ich die Stack-Frames inspizierte, optimierte der Compiler das Programm so, dass nur ein Frame verwendet wurde, indem einfach zum Anfang der Funktion gesprungen wurde und nur die Argumente zu f ersetzt wurden. Und - der Compiler lief nicht einmal im optimierten Modus.

Jetzt, wenn ich das gleiche in Python versuche - ich habe maximale Rekursion Wand (oder wahrscheinlich Stapelüberlauf, wenn ich Rekursionstiefe zu hoch gesetzt).

Gibt es eine Möglichkeit, dass eine dynamische Sprache wie Python diese netten Optimierungen nutzen kann? Vielleicht ist es möglich, einen Compiler anstelle eines Interpreters zu verwenden, damit dies funktioniert?

Nur neugierig!

Answer 1

Die Optimierung, von der Sie sprechen, ist als Tail Call Elimination bekannt - ein rekursiver Aufruf wird in eine iterative Schleife aufgefächert.

Es gab einige Diskussion darüber, aber die aktuelle Situation ist, dass dies nicht hinzugefügt wird, zumindest zu cpython richtig. Eine Diskussion finden Sie unter Guido's blog entry.

Es gibt jedoch somedecorators, die die Funktion manipulieren, um diese Optimierung durchzuführen. Sie erhalten im Allgemeinen nur den Platz sparen, aber nicht die Zeit (in der Tat sind sie in der Regel langsamer)

Answer 2

Es hat nichts damit zu tun, dass es sich um eine dynamische Sprache handelt oder dass sie interpretiert wird. CPython implementiert einfach Tail Recursion Optimierung nicht. Sie können finden, dass JPython usw. tut.

Answer 3

Als ich die Stapelframes inspizierte, optimierte der Compiler das Programm so, dass nur ein Frame verwendet wurde, indem einfach zum Anfang der Funktion gesprungen wurde und nur die Argumente zu f ersetzt wurden.

Was Sie beschreiben, heißt "Tail-Rekursion". Einige Compiler/Interpreter unterstützen es, andere nicht. Die meisten nicht. Wie Sie bemerkt haben, macht gcc. Und tatsächlich ist die Tail-Rekursion ein Teil der Spezifikation für die Programmiersprache Scheme, so dass alle Scheme-Compiler/Interpreter Tail-Rekursion unterstützen müssen. Auf der anderen Seite machen die Compiler für Sprachen wie Java und Python (sowie die meisten anderen Sprachen, die ich wetten möchte) keine Tail-Rekursion.

Gibt es eine Möglichkeit, dass eine dynamische Sprache wie Python diese netten Optimierungen nutzen kann?

Meinen Sie, jetzt, oder fragen Sie in abstraktere Begriffe? Abstrakt gesprochen, ja! Es wäre durchaus möglich, dass dynamische Sprachen die Tail-Rekursion ausnutzen (Scheme zum Beispiel). Aber konkret gesagt, nein, CPython (der kanonische Python-Interpreter) hat kein Flag oder einen anderen Parameter, um die Tail-Rekursion zu aktivieren.