F # hat Tail Call Elimination?

Das Problem mit den richtigen Tail Calls in Scala ist eine der technischen Kompromisse. Es wäre leicht möglich, PTCs zu Scala hinzuzufügen: Fügen Sie einfach einen Satz zum SLS hinzu. Voilà: PTCs in Scala. Aus der Sicht des Sprachdesigns sind wir fertig.

Nun müssen die armen Compiler-Schreiber diese Spezifikation implementieren . Nun, das Kompilieren von in eine Sprache mit PTCs ist einfach ... aber leider ist der JVM-Bytecode keine solche Sprache. Okay, was ist mit GOTO ? Nee. Fortsetzungen? Nee. Ausnahmen (von denen bekannt ist, dass sie Continuations gleichwertig sind)? Ah, jetzt kommen wir irgendwohin! Also konnten wir Ausnahmen verwenden, um PTCs zu implementieren. Alternativ könnten wir den JVM-Call-Stack einfach nicht verwenden und unseren eigenen Stack implementieren.

Immerhin gibt es auf der JVM mehrere Scheme-Implementierungen, die alle PTCs gut unterstützen. Es ist ein Mythos, dass Sie keine PTCs auf der JVM haben können, nur weil die JVM sie nicht unterstützt. Schließlich hat x86 auch keine, aber dennoch gibt es Sprachen, die auf x86 laufen, die sie haben.

Wenn also PTCs auf der JVM implementiert werden können, warum hat Scala sie dann nicht? Wie ich oben sagte, könnten Sie Ausnahmen oder Ihren eigenen Stack verwenden, um sie zu implementieren. Aber das Verwenden von Ausnahmen für den Kontrollfluss oder das Implementieren eines eigenen Stapels bedeutet, dass alles, was erwartet, dass der JVM-Aufrufstapel auf eine bestimmte Weise aussieht, nicht mehr funktioniert.

Insbesondere würden Sie praktisch die gesamte Interoperabilität mit dem Java Tooling-Ökosystem verlieren (Debugger, Visualizer, statische Analysatoren). Sie müssten auch Brücken bauen, um mit Java-Bibliotheken zu interagieren, was langsam wäre, so dass Sie auch die Interoperabilität mit dem Java-Bibliotheksökosystem verlieren.

Aber das ist ein wichtiges Designziel von Scala! Und deshalb hat Scala keine PTCs.

Ich nenne das "Hickey's Theorem", nach Rich Hickey, dem Designer von Clojure, der einmal in einem Vortrag "Tail Calls, Interop, Performance - Pick Two" gesagt hat.

Sie würden auch den JIT-Compiler mit einigen sehr ungewöhnlichen Byte-Code-Mustern präsentieren, von denen sie nicht wissen, wie sie gut zu optimieren sind.

Wenn Sie F # an die JVM portieren würden, müssten Sie im Grunde genau diese Wahl treffen: Geben Sie Tail Calls auf (können nicht, weil sie von der Language Spec benötigt werden), geben Sie Interop auf oder gibst du die Performance auf? Unter .NET können Sie alle drei haben, da Tail Calls in F # einfach in Tail Calls in MSIL kompiliert werden können. (Obwohl die eigentliche Übersetzung komplexer ist und die Implementierung von Tail Calls in MSIL in einigen Fällen fehlerhaft ist.)

Das wirft die Frage auf: Warum nicht Tail Calls zur JVM hinzufügen? Nun, das ist sehr schwer, aufgrund eines Entwurfsfehlers im JVM-Byte-Code. Die Entwickler wollten, dass der JVM-Bytecode bestimmte Sicherheitseigenschaften aufweist. Aber anstatt die JVM-Byte-Code-Sprache so zu gestalten, dass man überhaupt kein unsicheres Programm schreiben kann (wie zB in Java, wo man kein Programm schreiben kann, das die Pointer-Sicherheit verletzt, weil die Sprache einfach ist bietet Ihnen keinen Zugang zu Zeigern an erster Stelle), JVM-Byte-Code an sich ist unsicher und benötigt einen separaten Byte-Code-Verifier, um es sicher zu machen.

Dieser Byte-Code-Verifizierer basiert auf einer Stapelprüfung und Tail-Aufrufe ändern den Stapel. Also sind die beiden sehr schwer zu vereinbaren, aber die JVM funktioniert einfach nicht ohne den Byte-Code-Verifier. Es dauerte eine lange Zeit und einige sehr kluge Leute, um endlich herauszufinden, wie Tail Calls auf der JVM implementiert werden können, ohne den Bytecode-Verifier zu verlieren (siehe Eine tail-rekursive Maschine mit Stack-Inspektion von Clements und Felleisen und Tail ruft in der VM von John Rose (JVM Lead Designer) ), so sind wir nun von der Bühne, wo es ein offenes Forschungsproblem war, zur Bühne gerückt ist "nur" ein offenes Engineering-Problem.

Beachten Sie, dass Scala und einige andere Sprachen tun direkte Intra-Methode Tail-Rekursion haben. Das ist jedoch ziemlich langweilig, was die Implementierung angeht: Es ist nur eine while -Schleife. Die meisten Ziele haben while Schleifen oder etwas Ähnliches, z. Die JVM hat die Intra-Methode GOTO . Scala hat auch das scala.util.control.TailCalls -Objekt , was irgendwie so ist ein verbessertes Trampolin. (Siehe Stapellose Scala mit freien Monaden von Rúnar Óli Bjarnason für eine allgemeine Darstellung Version dieser Idee, die alle Verwendung des Stapels beseitigen kann, nicht nur in Tail-Calls.) Dies kann verwendet werden, um einen Tail-Calling-Algorithmus in Scala zu implementieren, aber damit ist es nicht kompatibel der JVM-Stack, dh es sieht nicht wie ein rekursiver Methodenaufruf zu anderen Sprachen oder zu einem Debugger aus:

Clojure hat die recur spezielle Form , die auch ein explizites Trampolin ist.

F # hat kein Problem mit Tail-Aufrufen. Hier ist was es tut:

• Wenn Sie eine einzelne tailrekursive Funktion haben, generiert der Compiler eine Schleife mit Mutation, da dies schneller ist als das Erzeugen der Anweisung .tail

• In anderen Tail-Call-Positionen (z. B. bei Verwendung von Fortsetzungen oder zwei gegenseitig rekursiven Funktionen) generiert es die .tail -Anweisung und so wird der Tail-Aufruf von der CLR

behandelt

• Standardmäßig ist die Endanrufoptimierung im Debug-Modus in Visual Studio deaktiviert , da dies das Debugging vereinfacht (Sie können den Stack überprüfen), aber Sie können es aktivieren Projekteigenschaften, falls erforderlich.

Früher gab es Probleme mit der Anweisung .tail in einigen Laufzeiten (CLR x64 und Mono), aber alle wurden behoben und alles funktioniert gut.