Vor kurzem habe ich versucht, Programm so etwas mit GCC zu kompilieren:
%Vor%und es lief gut. Als ich die Stack-Frames inspizierte, optimierte der Compiler das Programm so, dass nur ein Frame verwendet wurde, indem einfach an den Anfang der Funktion gesprungen wurde und nur die Argumente für f ersetzt wurden. Und - der Compiler lief nicht einmal im optimierten Modus.
Wenn ich nun dasselbe in Python versuche - habe ich die maximale Rekursionsmauer erreicht (oder wahrscheinlich einen Stapelüberlauf, wenn ich die Rekursionstiefe zu hoch setze).
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!
Die Optimierung, von der Sie sprechen, wird als Tail Call Elimination bezeichnet - ein rekursiver Aufruf wird in eine iterative Schleife aufgefächert.
Es gibt einige Diskussionen darüber, aber die aktuelle Situation ist, dass dies nicht hinzugefügt wird, zumindest nicht für cpython. Weitere Informationen finden Sie in Guidos Blogeintrag .
Allerdings gibt es einige decorators , die die Funktion manipulieren, um diese Optimierung durchzuführen. Im Allgemeinen erhalten sie jedoch nur die Platzersparnis, nicht die Zeit (tatsächlich sind sie in der Regel langsamer)
Als ich die Stack-Frames inspizierte, optimierte der Compiler das Programm so, dass nur ein Frame verwendet wurde, indem einfach an den Anfang der Funktion gesprungen wurde und nur die Argumente durch f ersetzt wurden.
Was Sie beschreiben, heißt "Tail Recursion". Einige Compiler / Interpreter unterstützen es, andere nicht. Die meisten nicht. Wie Sie bemerkt haben, macht gcc. Tatsächlich ist die Tail-Rekursion ein Teil der Spezifikation für die Programmiersprache Scheme, so dass alle Scheme-Compiler / Interpreter die Tail-Rekursion unterstützen müssen. Auf der anderen Seite, die Compiler für Sprachen wie Java und Python (sowie die meisten anderen Sprachen, würde ich wetten) nicht Schwanz Rekursion.
Gibt es eine Möglichkeit, dass eine dynamische Sprache wie Python diese netten Optimierungen nutzen kann?
Meinst du, gerade jetzt , oder fragst du etwas abstrakter? 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.
Es hat nichts damit zu tun, dass es sich um eine dynamische Sprache handelt oder dass sie interpretiert wird. CPython implementiert einfach nicht Tail Recursion Optimierung. Sie können finden, dass JPython usw. tut.
Tags und Links python gcc compiler-construction