Verhindert die JVM Tail-Call-Optimierungen?

99

Ich habe dieses Zitat auf der Frage gesehen: Was ist eine gute funktionale Sprache, auf der ein Webdienst aufgebaut werden kann?

Insbesondere Scala unterstützt die Eliminierung von Tail-Calls nur in selbstrekursiven Funktionen, wodurch die Art der Komposition eingeschränkt wird (dies ist eine grundlegende Einschränkung der JVM).

Ist das wahr? Wenn ja, was ist mit der JVM, die diese grundlegende Einschränkung schafft?

java jvm scala tail-recursion Jason Dagit
quelle

Antworten:

74

Dieser Beitrag: Rekursion oder Iteration? könnte helfen.

Kurz gesagt, die Tail-Call-Optimierung ist in der JVM aufgrund des Sicherheitsmodells und der Notwendigkeit, immer einen Stack-Trace verfügbar zu haben, schwierig durchzuführen. Diese Anforderungen könnten theoretisch unterstützt werden, erfordern jedoch wahrscheinlich einen neuen Bytecode (siehe den informellen Vorschlag von John Rose ).

Es gibt auch mehr Diskussionen in Sun Bug # 4726340 , wo die Evaluierung (ab 2002) endet:

Ich glaube, dass dies trotzdem getan werden könnte, aber es ist keine kleine Aufgabe.

Derzeit wird am Da Vinci Machine- Projekt gearbeitet. Der Status des Unterprojekts "Tail Call" wird als "Proto 80%" aufgeführt. Es ist unwahrscheinlich, dass es in Java 7 gelingt, aber ich denke, es hat eine sehr gute Chance auf Java 8.

Michael Myers
quelle
Ich bin der Erklärung nicht ganz gefolgt. Ich dachte, die Tail-Call-Optimierung wurde vom Compiler implementiert. Angenommen, Sie haben eine Funktion, die vom Compiler optimiert werden könnte, dann könnten Sie auch eine äquivalente nicht rekursive Funktion haben, die dieselbe Funktionalität mithilfe einer Schleife implementiert, richtig? Wenn ja, könnte dies nicht vom Compiler durchgeführt werden. Ich kann der Abhängigkeit von der JVM nicht folgen. Wie ist dies mit einem Scheme-Compiler zu vergleichen, der nativen i386-Code generiert hat?
Gautham Ganapathy
4
@ Gautham: Meine Aussage zum Debuggen bezog sich auf die Verwendung von Trampolinen als Problemumgehung für die fehlende Eliminierung von Tail Calls in der JVM. Die Beseitigung von Tail Calls kann und wurde in der JVM implementiert (Arnold Schaighofer in OpenJDK und auch in LLVM), sodass keine Frage besteht, ob dies möglich ist oder nicht. Die CLR von Microsoft unterstützt natürlich seit 10 Jahren die Beseitigung von Tail Calls, und die Veröffentlichung von F # hat gezeigt, dass es sich um einen Game Changer handelt. Ich denke, die Antwort ist, dass die JVM längst stagniert hat.
JD
3
Dies ist ein weit verbreitetes Missverständnis und eine oft wiederholte Entschuldigung, aber falsch. Es ist seit einigen Jahren bekannt, dass die Sicherheit durch Stapelinspektion (und Bereitstellung nützlicher Stapelspuren) nicht mit ordnungsgemäßen Tail-Aufrufen unvereinbar ist. Siehe zum Beispiel dieses Papier aus dem Jahr 2004. citeseerx.ist.psu.edu/viewdoc/… Downvoting, da die Antwort falsch ist.
Justin Sheehy
5
@ JustinSheehy: Was ist falsch? Die Frage war: "Verhindert die JVM Tail-Call-Optimierungen?" Und die Antwort lautet: "Nein, aber es ist schwer."
Michael Myers
5
Weißt du, ob dies in Java8 enthalten ist?
Nachokk
27

Die grundlegende Einschränkung besteht einfach darin, dass die JVM in ihrem Bytecode keine Tail-Aufrufe bereitstellt und folglich keine direkte Möglichkeit für eine auf der JVM aufgebaute Sprache besteht, Tail-Aufrufe selbst bereitzustellen. Es gibt Problemumgehungen, die einen ähnlichen Effekt erzielen können (z. B. Trampolin), aber sie gehen zu Lasten einer schrecklichen Leistung und einer Verschleierung des generierten Zwischencodes, wodurch ein Debugger unbrauchbar wird.

Daher kann die JVM keine funktionalen Programmiersprachen in Produktionsqualität unterstützen, bis Sun Tail Calls in der JVM selbst implementiert. Sie haben jahrelang darüber diskutiert, aber ich bezweifle, dass sie jemals Tail Calls implementieren werden: Es wird sehr schwierig sein, weil sie ihre VM vor der Implementierung solcher grundlegenden Funktionen vorzeitig optimiert haben, und Suns Bemühungen konzentrieren sich stark auf dynamische Sprachen anstatt auf funktionale Sprachen.

Daher gibt es ein sehr starkes Argument dafür, dass Scala keine echte funktionale Programmiersprache ist: Diese Sprachen haben Tail Calls seit der Einführung von Scheme vor über 30 Jahren als wesentliches Merkmal angesehen.

JD
quelle
5
Hence there is a very strong argument that Scala is not a real functional programming language - Das Argument ist eigentlich ziemlich schwach. Sicher sind tail calls [as] an essential feature, und schön, wenn die zugrunde liegende Hardware (oder virtuelle Maschine) es direkt unterstützt. Aber es sind Implementierungsdetails.
Ingo
8
@Ingo: Nur wenn Sie Stapelüberläufe in Ihrem Programm zur Laufzeit nicht als ein erhebliches Problem betrachten, das vom Benutzer gesehen wird. Laut seinem Bug-Tracker war sogar der Scala-Compiler selbst von Stapelüberläufen geplagt. Selbst die erfahrensten Scala-Entwickler verstehen das immer noch falsch ...
JD
7
Es ist in Ordnung, ein Anwalt von F # zu sein. Aber ich habe Sie schon lange (sogar Jahre zuvor im Usenet) dafür bemerkt, dass Sie allem feindlich gegenüberstehen, was nicht F # ist, und dennoch zeigen Ihre Ausführungen, dass Sie nicht wissen, wovon Sie sprechen. Wie hier: Ihr Argument scheint zu sein, dass eine Sprache, in der ich ein Programm schreiben kann, das mit Stapelüberlauf abgebrochen wird, keine funktionierende ist? Aber könnte nicht das gleiche Argument für Sprachen vorgebracht werden, in denen ich einen Heap-Überlauf provozieren kann? Daher würde das heilige F # selbst nicht als funktional gelten.
Ingo
7
@Ingo: Mehrere Redewendungen in der funktionalen Programmierung, wie die gegenseitige Rekursion und die Weitergabe, können die Beseitigung von Tail Calls erfordern, um zu funktionieren. Ohne sie stapeln Ihre Programme Überlauf. Wenn eine Sprache idiomatischen Funktionscode nicht zuverlässig ausführen kann, ist sie dann funktionsfähig? Die Antwort ist, wie Sie sagen, ein Urteilsspruch, aber eine wichtige Unterscheidung in der Praxis. Martin Trojer hat gerade einen interessanten Blog-Beitrag darüber veröffentlicht: martinsprogrammingblog.blogspot.com/2011/11/…
JD
2
Nur weil die JVM (leider keine Frage) keine Tail Calls ausführen kann, bedeutet dies nicht, dass die Eliminierung von Tail Calls unmöglich ist. Dies ist so, als ob man angibt, dass Gleitkommaberechnungen nur auf Computern mit FPUs möglich sind.
Ingo
22

Scala 2.7.x unterstützt die Tail-Call-Optimierung für die Selbstrekursion (eine Funktion, die sich selbst aufruft) der endgültigen Methoden und lokalen Funktionen.

Scala 2.8 bietet möglicherweise auch Bibliotheksunterstützung für Trampolin, eine Technik zur Optimierung gegenseitig rekursiver Funktionen.

Viele Informationen über den Zustand der Scala-Rekursion finden Sie in Rich Doughertys Blog .

Daniel C. Sobral
quelle
Können Sie bitte die Frage zum aktuellen Scala-Status aktualisieren?
om-nom-nom
@ om-nom-nom AFAIK, nichts hat sich geändert, weder auf der Scala-Seite noch auf der JVM-Seite.
Daniel C. Sobral
8

Zusätzlich zu dem in Lambda The Ultimate verlinkten Artikel (aus dem oben veröffentlichten Link mmyers) hat John Rose von Sun noch etwas mehr über die Optimierung von Tail Calls zu sagen.

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

Ich habe gehört, dass es eines Tages auf der JVM implementiert werden könnte. Auf der Da Vinci-Maschine wird unter anderem die Unterstützung für Rückrufe geprüft.

http://openjdk.java.net/projects/mlvm/

Faran
quelle
0

Alle Quellen weisen darauf hin, dass die JVM im Fall einer Schwanzrekursion nicht optimieren kann, aber beim Lesen der Java-Leistungsoptimierung (2003, O'reilly) stellte der Autor fest, dass er durch die Implementierung einer Schwanzrekursion eine höhere Rekursionsleistung erzielen kann.

Sie finden seinen Anspruch auf Seite 212 (Suche nach 'Schwanzrekursion' sollte das zweite Ergebnis sein). Was gibt?

Denker
quelle
IBM hat irgendeine Form von TCO in seiner JVM-Implementierung unterstützt (als Optimierung, also keine Garantien). Vielleicht dachten die Autoren von Java Performance Tuning, dass diese Funktion irgendwann von allen JVMs implementiert werden würde. ibm.com/developerworks/java/library/j-diag8.html
llemieng