Warum hat Java überhaupt keine Optimierung für die Schwanzrekursion?

92

Aus dem, was ich gelesen habe: Der Grund ist, dass es nicht einfach ist zu bestimmen, welche Methode tatsächlich aufgerufen wird, wenn wir eine Vererbung haben.

Warum verfügt Java jedoch nicht mindestens über eine Schwanzrekursionsoptimierung für statische Methoden und erzwingt eine ordnungsgemäße Methode zum Aufrufen statischer Methoden mit dem Compiler?

Warum unterstützt Java die Schwanzrekursion überhaupt nicht?

Ich bin mir nicht sicher, ob es hier überhaupt Schwierigkeiten gibt.

In Bezug auf das vorgeschlagene Duplikat , wie von Jörg W Mittag 1 erklärt :

  • Bei der anderen Frage geht es um TCO, bei der anderen um TRE. TRE ist viel einfacher als TCO.
  • Bei der anderen Frage geht es auch darum, welche Einschränkungen die JVM für Sprachimplementierungen auferlegt, die in die JVM kompiliert werden sollen. Bei dieser Frage geht es um Java, die eine Sprache ist, die von der JVM nicht eingeschränkt wird, da die JVM-Spezifikation von geändert werden kann die gleichen Leute, die Java entwerfen.
  • Und schließlich gibt es in der JVM nicht einmal eine Einschränkung in Bezug auf TRE, da die JVM über die Intra-Methode GOTO verfügt, die alles ist, was für TRE benötigt wird

1 Formatierung hinzugefügt, um gemachte Punkte hervorzuheben.

java compiler recursion InformedA
quelle
26
Um Eric Lippert zu zitieren : "Features sind nicht billig; sie sind extrem teuer und müssen nicht nur ihre eigenen Kosten, sondern auch die Opportunitätskosten rechtfertigen, die entstehen, wenn wir nicht die hundert anderen Features verwenden, die wir mit diesem Budget hätten erzielen können." Java wurde teilweise entwickelt, um C / C ++ - Entwickler anzusprechen, und die Optimierung der Schwanzrekursion wird in diesen Sprachen nicht garantiert.
Doval
5
Korrigieren Sie mich, wenn ich mich irre, aber ist Eric Lippert der Designer für C #, der die Optimierung der Schwanzrekursion hat?
InformedA
1
Er ist im C # -Compiler-Team, ja.
Doval
10
Von dem, was ich verstehe, könnte die JIT es tun , wenn bestimmte Bedingungen erfüllt sind , vielleicht. In der Praxis kann man sich also nicht darauf verlassen. Aber ob C # es hat oder nicht, spielt für Eric keine Rolle.
Doval
4
@InstructedA Wenn Sie etwas tiefer graben, können Sie feststellen, dass dies im 32-Bit-JIT-Compiler nie erfolgt ist. Das 64-Bit-JIT ist in vielerlei Hinsicht neuer und intelligenter. Der noch neuere experimentelle Compiler (sowohl für 32- als auch für 64-Bit-Versionen) ist noch intelligenter und unterstützt die Schwanzrekursionsoptimierung in IL, die nicht explizit danach fragt. Es gibt noch einen weiteren Punkt, den Sie berücksichtigen müssen: JIT-Compiler haben nicht viel Zeit. Sie sind stark auf Geschwindigkeit optimiert - Anwendungen, deren Kompilierung in C ++ Stunden in Anspruch nehmen kann, müssen in höchstens ein paar hundert ms (zumindest teilweise) von IL auf native umgestellt werden.
Luaan,

Antworten:

132

Wie von Brian Goetz (Java Language Architect bei Oracle) in diesem Video erklärt :

in jdk-klassen gibt es eine reihe von sicherheitsrelevanten methoden, bei denen stapelrahmen zwischen jdk-bibliothekscode und aufrufendem code gezählt werden, um herauszufinden, wer sie aufruft.

Alles, was die Anzahl der Frames auf dem Stack verändert, würde dies unterbrechen und einen Fehler verursachen. Er gibt zu, dass dies ein dummer Grund war, und so haben die JDK-Entwickler diesen Mechanismus inzwischen ersetzt.

Er erwähnt dann weiter, dass es keine Priorität ist, sondern diese Schwanzrekursion

wird irgendwann erledigt.

Hinweis: Dies gilt für HotSpot und das OpenJDK. Andere VMs können davon abweichen.

ggovan
quelle
7
Ich bin erstaunt, dass es so eine eher geschnittene und trockene Antwort gibt! Aber es scheint wirklich wie die Antwort - es ist jetzt möglich, aus veralteten technischen Gründen wurde es noch nicht getan, und jetzt warten wir nur darauf, dass jemand entscheidet, dass es wichtig genug ist, um es zu implementieren.
BrianH
1
Warum nicht eine Problemumgehung implementieren? Wie ein Undercover-Label, das nur mit neuen Werten für Argumente an die Spitze des Methodenaufrufs springt? Dies wäre eine Optimierung zur Kompilierungszeit und müsste nicht die Stack-Frames verschieben oder Sicherheitsverletzungen verursachen.
James Watkins
2
Es wird für uns viel besser sein, wenn Sie oder jemand anderes hier tiefer in diese "sicherheitsrelevanten Methoden" eindringen und sie genauer beschreiben kann. Danke!
InformedA
3
@InstructedA - siehe securingjava.com/chapter-three/chapter-three-6.html , die enthält eine detaillierte Beschreibung, wie die Java Security Manager - System arbeitete circa der Veröffentlichung von Java 2.
Jules
3
Eine Problemumgehung besteht darin, eine andere JVM-Sprache zu verwenden. Scala tut dies zum Beispiel im Compiler, nicht zur Laufzeit.
James Moore
24

Java hat keine Tail-Call-Optimierung aus dem gleichen Grund, aus dem es in den meisten imperativen Sprachen nicht verfügbar ist. Imperative Schleifen sind der bevorzugte Stil der Sprache, und der Programmierer kann die Endrekursion durch imperative Schleifen ersetzen. Die Komplexität lohnt sich nicht für ein Feature, dessen Verwendung aus Gründen des Stils nicht empfohlen wird.

Dieses Thema, bei dem Programmierer manchmal in einem FP-Stil in ansonsten zwingenden Sprachen schreiben möchten, ist erst in den letzten 10 Jahren oder so in Mode gekommen, nachdem Computer mit der Skalierung in Kernen anstelle von GHz begonnen hatten. Auch jetzt ist es nicht so beliebt. Wenn ich vorschlagen würde, eine imperative Schleife durch eine Endpunktrekursion bei der Arbeit zu ersetzen, würde die Hälfte der Codeüberprüfer lachen und die andere Hälfte würde verwirrt aussehen. Selbst in der funktionalen Programmierung vermeiden Sie im Allgemeinen die Schwanzrekursion, es sei denn, andere Konstrukte wie Funktionen höherer Ordnung passen nicht sauber zusammen.

Karl Bielefeldt
quelle
36
Diese Antwort scheint nicht richtig zu sein. Nur weil die Schwanzrekursion nicht unbedingt erforderlich ist, heißt das nicht, dass sie nicht nützlich wäre. Rekursive Lösungen sind häufig einfacher zu verstehen als Iterationen. Das Fehlen von Tail-Aufrufen führt jedoch dazu, dass rekursive Algorithmen bei großen Problemen, die den Stapel sprengen würden, nicht mehr korrekt sind. Hier geht es um Korrektheit, nicht um Leistung (Handelsgeschwindigkeit zur Vereinfachung lohnt sich oft). Wie die richtige Antwort vermerkt, ist das Fehlen von Tail Calls auf ein seltsames Sicherheitsmodell zurückzuführen, das sich auf Stack-Traces stützt, nicht auf eine zwingende Bigotterie.
amon
4
@amon James Gosling hat einmal gesagt , dass er nicht eine Funktion Java hinzufügen würde , es sei denn mehrere Leute sie angefordert , und erst dann würde er betrachtet es. Es würde mich also nicht wundern, wenn ein Teil der Antwort wirklich "Sie könnten immer eine forSchleife verwenden" wäre (und auch für erstklassige Funktionen gegen Objekte). Ich würde nicht so weit gehen, es "imperative Bigotterie" zu nennen, aber ich glaube nicht, dass es 1995 sehr gefragt gewesen wäre, als die Hauptsorge wahrscheinlich Javas Geschwindigkeit und der Mangel an Generika war.
Doval
7
@amon, ein Sicherheitsmodell scheint mir ein legitimer Grund zu sein, TCO nicht zu einer bereits vorhandenen Sprache hinzuzufügen, aber ein schlechter Grund, es überhaupt nicht in die Sprache zu integrieren. Sie verzichten auf eine vom Programmierer sichtbare Hauptfunktion, um eine kleine Funktion hinter den Kulissen einzuschließen. "Warum hat Java 8 keine TCO?" Ist eine ganz andere Frage als "Warum hatte Java 1.0 keine TCO?" Ich antwortete letzterem.
Karl Bielefeldt
3
@rwong, Sie können jede rekursive Funktion in eine iterative umwandeln . (Wenn ich kann, ich habe ein Beispiel geschrieben hier )
alain
3
@ZanLynx es hängt von der Art des Problems ab. Beispielsweise kann das Besuchermuster von den Gesamtbetriebskosten profitieren (abhängig von Struktur- und Besucherspezifikationen), ohne dass dies mit FP zu tun hat. Das Durchlaufen von Zustandsautomaten ist ähnlich, obwohl die Transformation mit Trampolinen etwas natürlicher erscheint (je nach Problem). Auch wenn Sie Bäume technisch mit Schleifen implementieren können, ist die Rekursion meines Erachtens viel natürlicher (ähnlich wie bei DFS, obwohl Sie in diesem Fall die Rekursion aufgrund von Stapelbeschränkungen auch bei TCO vermeiden können).
Maciej Piechotka
5

Java bietet keine Optimierung für große Aufrufe, da die JVM keinen Bytecode für Endaufrufe enthält (zu einem statisch unbekannten Funktionszeiger, z. B. einer Methode in einer vtable).

Aus sozialen (und möglicherweise technischen) Gründen ist das Hinzufügen einer neuen Bytecode-Operation in der JVM (die sie mit früheren Versionen dieser JVM inkompatibel machen würde) für den Eigentümer der JVM-Spezifikation furchtbar schwierig.

Zu den technischen Gründen, warum in der JVM-Spezifikation kein neuer Bytecode hinzugefügt wurde, gehört die Tatsache, dass echte JVM-Implementierungen äußerst komplexe Softwareteile sind (z. B. aufgrund der vielen JIT-Optimierungen, die durchgeführt werden).

Bei Endaufrufen einer unbekannten Funktion muss der aktuelle Stack-Frame durch einen neuen ersetzt werden. Diese Operation sollte in der JVM stattfinden (es geht nicht nur darum, den Compiler für die Bytecode-Generierung zu ändern).

Basile Starynkevitch
quelle
17
Die Frage betrifft nicht die Schwanzaufrufe, sondern die Schwanzrekursion. Dabei geht es nicht um die JVM-Bytecodesprache, sondern um die Java-Programmiersprache, eine völlig andere Sprache. Scala kompiliert unter anderem nach JVM-Bytecode und eliminiert Schwanzrekursionen. Schemaimplementierungen auf der JVM haben vollständige Proper Tail-Calls. Java 7 (JVM Spec, 3rd Ed.) Hat einen neuen Bytecode hinzugefügt. Die IBM J9 JVM führt die Gesamtbetriebskosten auch ohne einen speziellen Bytecode aus.
Jörg W Mittag
1
@ JörgWMittag: Das stimmt, aber dann frage ich mich, ob es wirklich stimmt, dass die Java-Programmiersprache keine richtigen Tail-Aufrufe hat. Es könnte genauer sein , zu erklären , dass die Java - Programmiersprache nicht funktioniert hat richtige Endaufruf haben, dass nichts in den spec Mandaten es. (Das heißt: Ich bin mir nicht sicher, ob irgendetwas in der Spezifikation einer Implementierung das Eliminieren von Tail Calls verbietet . Es wird einfach nicht erwähnt.)
ruakh
4

Sofern eine Sprache keine spezielle Syntax zum Ausführen eines Tail-Aufrufs (rekursiv oder auf andere Weise) hat und ein Compiler quietscht, wenn ein Tail-Aufruf angefordert wird, aber nicht generiert werden kann, führt die "optionale" Tail-Aufruf- oder Tail-Rekursionsoptimierung zu Situationen, in denen ein Teil ausgegeben wird Code erfordert möglicherweise weniger als 100 Byte Stapel auf einem Computer, aber mehr als 100.000.000 Byte Stapel auf einem anderen Computer. Solch ein Unterschied sollte eher als qualitativ als nur als quantitativ angesehen werden.

Es wird erwartet, dass Maschinen unterschiedliche Stapelgrößen haben, und daher ist es immer möglich, dass Code auf einer Maschine funktioniert, aber den Stapel auf einer anderen sprengt. Im Allgemeinen funktioniert Code, der auf einem Computer ausgeführt wird, auch wenn der Stapel künstlich eingeschränkt ist, wahrscheinlich auf allen Computern mit "normalen" Stapelgrößen. Wenn jedoch eine Methode, die 1.000.000 tief rekursiv ist, auf einer Maschine, aber nicht auf einer anderen, tail-call-optimiert ist, funktioniert die Ausführung auf der ersten Maschine wahrscheinlich auch dann, wenn ihr Stapel ungewöhnlich klein ist und auf der zweiten Maschine selbst dann fehlschlägt, wenn ihr Stapel ungewöhnlich groß ist .

Superkatze
quelle
2

Ich denke, die Tail-Call-Rekursion wird in Java hauptsächlich deshalb nicht verwendet, weil dadurch die Stack-Traces geändert und das Debuggen eines Programms erheblich erschwert würden. Ich denke, eines der Hauptziele von Java ist es, Programmierern ein einfaches Debuggen ihres Codes zu ermöglichen, und die Stapelverfolgung ist dafür besonders in einer stark objektorientierten Programmierumgebung von entscheidender Bedeutung. Da stattdessen eine Iteration verwendet werden könnte, muss das Sprachkomitee angenommen haben, dass es sich nicht lohnt, eine Schwanzrekursion hinzuzufügen.

ärgerlich_squid
quelle