Wenn es keine Gesamtbetriebskosten gibt, wann müssen Sie sich Sorgen machen, den Stapel zu sprengen?

14

Jedes Mal, wenn über eine neue Programmiersprache diskutiert wird, die auf die JVM abzielt, werden unvermeidlich Dinge gesagt wie:

"Die JVM unterstützt keine Tail-Call-Optimierung, daher sage ich viele explodierende Stacks voraus."

Es gibt Tausende von Variationen zu diesem Thema.

Jetzt weiß ich, dass einige Sprachen, wie zum Beispiel Clojure, ein spezielles wiederkehrendes Konstrukt haben, das Sie verwenden können.

Was ich nicht verstehe, ist: Wie ernst ist der Mangel an Tail-Call-Optimierung? Wann sollte ich mir darüber Sorgen machen?

Meine Hauptverwirrung rührt wahrscheinlich von der Tatsache her, dass Java eine der erfolgreichsten Sprachen aller Zeiten ist und einige der JVM-Sprachen ziemlich gut abschneiden. Wie ist das möglich , wenn der Mangel an TCO ist wirklich von jeder Sorge?

Cedric Martin
quelle
4
Wenn Sie eine Rekursion haben, die tief genug ist, um den Stapel ohne TCO zu sprengen, haben Sie auch mit TCO
Ratschenfreak
18
@ratchet_freak Das ist Quatsch. Das Schema hat nicht einmal Schleifen, aber da die Spezifikation die TCO-Unterstützung vorschreibt, ist eine rekursive Iteration über einen großen Satz von Daten nicht teurer als eine imperative Schleife (mit dem Vorteil, dass das Schema-Konstrukt einen Wert zurückgibt).
itsbruce
6
@ratchetfreak TCO ist ein Mechanismus, mit dem rekursive Funktionen, die auf eine bestimmte Weise (dh rekursiv am Ende) geschrieben wurden, nicht in der Lage sind, den Stapel zu sprengen, selbst wenn sie dies wollten. Ihre Aussage ist nur für eine nicht rekursiv geschriebene Rekursion sinnvoll. In diesem Fall sind Sie korrekt und die Gesamtbetriebskosten helfen Ihnen nicht.
Evicatos
2
Zuletzt habe ich mir angesehen, dass der 80x86 auch keine (native) Tail-Call-Optimierung durchführt. Aber das hat Sprachentwickler nicht davon abgehalten, Sprachen zu portieren, die es verwenden. Der Compiler erkennt, wann er einen Sprung gegen einen jsr ausführen kann, und alle sind glücklich. Auf einer JVM können Sie dasselbe tun.
kdgregory
3
@kdgregory: Aber das x86 hat GOTOdie JVM nicht. Und x86 wird nicht als Interop-Plattform verwendet. Die JVM hat keine GOTOund einer der Hauptgründe für die Wahl der Java-Plattform ist Interop. Wenn Sie auf der JVM TCO implementieren möchten, müssen Sie tun etwas in den Stapel. Verwalten Sie es selbst (dh verwenden Sie den JVM-Aufrufstapel überhaupt nicht), verwenden Sie Trampoline, verwenden Sie Ausnahmen als GOTO, so etwas. In all diesen Fällen werden Sie mit dem JVM-Aufrufstapel inkompatibel. Es ist unmöglich, mit Java Stack-kompatibel zu sein, TCO und hohe Leistung zu haben. Du musst einen dieser drei opfern.
Jörg W Mittag

Antworten:

16

Nehmen wir an, wir haben alle Schleifen in Java beseitigt (die Compiler-Autoren streiken oder so). Jetzt wollen wir Fakultät schreiben, also können wir so etwas korrigieren

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

Jetzt fühlen wir uns ziemlich schlau, wir haben es geschafft, unsere Fakultät auch ohne Schleifen zu schreiben! Beim Testen stellen wir jedoch fest, dass bei einer angemessenen Anzahl Stapelüberlauffehler auftreten, da keine Gesamtbetriebskosten anfallen.

In echtem Java ist dies kein Problem. Wenn wir jemals einen rekursiven Algorithmus für den Schwanz haben, können wir ihn in eine Schleife umwandeln und alles in Ordnung sein. Was ist jedoch mit Sprachen ohne Schleifen? Dann bist du einfach abgespritzt. Das ist der Grund, warum Clojure diese recurForm hat, ohne sie ist sie nicht einmal vollständig (keine Möglichkeit, Endlosschleifen durchzuführen).

Die Klasse der funktionalen Sprachen, die auf JVM, Frege, Kawa (Schema) und Clojure abzielen, versucht immer, mit dem Fehlen von Tail Calls umzugehen, da TC in diesen Sprachen die idiomatische Art ist, Schleifen zu erstellen! Wenn in Schema übersetzt, wäre diese Fakultät eine gute Fakultät. Es wäre furchtbar unpraktisch, wenn Ihr Programm durch eine 5000-fache Schleife abstürzen würde. Dies kann jedoch durch recurspezielle Formulare, Anmerkungen, die darauf hindeuten, dass Selbstanrufe optimiert werden, und Trampolinspringen, umgangen werden. Sie alle erzwingen entweder Leistungseinbußen oder unnötige Arbeit für den Programmierer.

Jetzt kommt Java auch nicht frei davon, da es bei TCO mehr gibt als nur Rekursion. Was ist mit gegenseitig rekursiven Funktionen? Sie können nicht einfach in Schleifen übersetzt werden, werden jedoch von der JVM immer noch nicht optimiert. Dies macht es auf spektakuläre Weise unangenehm zu versuchen, Algorithmen mithilfe gegenseitiger Rekursion unter Verwendung von Java zu schreiben, da Sie, wenn Sie eine anständige Leistung / Reichweite wünschen, dunkle Magie anwenden müssen, damit sie in Schleifen passt.

Zusammenfassend ist dies für viele Fälle keine große Sache. Die meisten Tail-Aufrufe gehen entweder nur einen Stackframe tief, mit Dingen wie

return foo(bar, baz); // foo is just a simple method

oder sind Rekursion. Für die TC-Klasse, die nicht dazu passt, ist jedoch jede JVM-Sprache mit Schmerzen konfrontiert.

Es gibt jedoch einen guten Grund, warum wir noch keine Gesamtbetriebskosten haben. Die JVM gibt uns Stapelspuren. Mit TCO eliminieren wir systematisch Stackframes, von denen wir wissen, dass sie "zum Scheitern verurteilt" sind, aber die JVM möchte diese möglicherweise später für ein Stacktrace! Nehmen wir an, wir implementieren eine solche FSM, bei der jeder Staat den nächsten abruft. Wir würden alle Aufzeichnungen früherer Zustände löschen, damit ein Traceback uns zeigt, welcher Zustand vorliegt, aber nichts darüber, wie wir dorthin gekommen sind.

Darüber hinaus basiert ein Großteil der Bytecode-Verifizierung auf Stapeln, wodurch die Möglichkeit, Bytecode zu verifizieren, nicht unbedingt in Frage kommt. Abgesehen von der Tatsache, dass Java Schleifen aufweist, scheint die TCO für die JVM-Ingenieure etwas schwieriger zu sein, als sie es wert ist.

Daniel Gratzer
quelle
2
Das größte Problem ist der Bytecode-Verifizierer, der vollständig auf der Stapelprüfung basiert. Das ist ein großer Fehler in der JVM-Spezifikation. Vor 25 Jahren, als die JVM entworfen wurde, sagten die Leute bereits, dass es besser wäre, die JVM-Bytecodesprache an erster Stelle sicher zu haben, als diese Sprache unsicher zu machen, und sich danach auf die Bytecodeüberprüfung zu verlassen. Matthias Felleisen (einer der Hauptakteure in der Scheme-Community) hat jedoch in einem Artikel demonstriert, wie Tail Calls zur JVM hinzugefügt werden können, während der Bytecode-Verifizierer erhalten bleibt.
Jörg W Mittag
2
Interessanterweise ist die J9 JVM von IBM nicht TCO zuführen.
Jörg W Mittag
1
@jozefg Interessanterweise kümmert sich niemand um Stacktrace-Einträge für Schleifen, daher enthält das Stacktrace-Argument zumindest für rekursive Tail-Funktionen kein Wasser.
Ingo
2
@ MasonWheeler Das ist genau mein Punkt: Die Stapelverfolgung sagt Ihnen nicht, in welcher Iteration es passiert ist. Sie können dies nur indirekt sehen, indem Sie Schleifenvariablen usw. untersuchen. Warum sollten Sie also mehrere hundert Stack-Trace-Einträge einer rekursiven Tail-Funktion wünschen? Nur der letzte ist interessant! Und wie bei Schleifen können Sie feststellen, um welche Rekursion es sich handelt, indem Sie lokale Variablen, Argumentwerte usw. untersuchen.
Ingo
3
@Ingo: Wenn eine Funktion nur für sich selbst wiederkehrt, zeigt der Stack-Trace möglicherweise nicht viel. Wenn jedoch eine Gruppe von Funktionen wechselseitig rekursiv ist, kann ein Stack-Trace manchmal sehr viel anzeigen.
Supercat
7

Die Optimierung von Schwanzaufrufen ist hauptsächlich wegen der Schwanzrekursion wichtig. Es gibt jedoch ein Argument, warum es eigentlich gut ist, dass die JVM keine Tail-Aufrufe optimiert: Da die TCO einen Teil des Stacks wiederverwendet, ist ein Stack-Trace einer Ausnahme unvollständig, wodurch das Debuggen etwas schwieriger wird.

Es gibt verschiedene Möglichkeiten, um die Einschränkungen der JVM zu umgehen:

  1. Die einfache Schwanzrekursion kann vom Compiler auf eine Schleife optimiert werden.
  2. Wenn das Programm im Continuation-Passing-Stil ist, ist es trivial, „Trampolin“ zu verwenden. Hier gibt eine Funktion nicht das Endergebnis zurück, sondern eine Fortsetzung, die dann von außen ausgeführt wird. Diese Technik ermöglicht es einem Compiler-Schreiber, einen beliebig komplexen Steuerfluss zu modellieren.

Dies erfordert möglicherweise ein größeres Beispiel. Betrachten Sie eine Sprache mit Abschlüssen (z. B. JavaScript oder ähnliches). Wir können die Fakultät schreiben als

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Jetzt können wir stattdessen einen Rückruf anfordern:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

Dies funktioniert jetzt in einem konstanten Stapelbereich, was irgendwie albern ist, weil es sowieso rekursiv ist. Diese Technik ist jedoch in der Lage, alle Tail-Aufrufe in einen konstanten Stapelraum zu reduzieren. Befindet sich das Programm in CPS, bedeutet dies, dass der Callstack insgesamt konstant ist (in CPS ist jeder Aufruf ein Tail Call).

Ein großer Nachteil dieser Technik ist, dass es viel schwieriger zu debuggen, etwas schwieriger zu implementieren und weniger performant ist - sehen Sie alle Abschlüsse und Indirektionen, die ich verwende.

Aus diesen Gründen wäre es sehr zu bevorzugen, wenn die VM eine Tail-Call-Operation implementieren würde - Sprachen wie Java, die aus guten Gründen keine Tail-Calls unterstützen, müssten diese nicht verwenden.

amon
quelle
1
"Da TCO einen Teil des Stapels wiederverwendet, ist eine Stapelverfolgung von einer Ausnahme unvollständig." - Ja, aber eine Stapelverfolgung aus einer Schleife ist auch unvollständig. Es wird nicht aufgezeichnet, wie oft die Schleife ausgeführt wurde. - Auch wenn die JVM ordnungsgemäße Tail-Aufrufe unterstützen würde, könnte man sich dennoch beispielsweise während des Debuggens abmelden. Aktivieren Sie dann für die Produktion TCO, um sicherzustellen, dass der Code mit 100.000 oder 100.000.000 Tail Calls ausgeführt wird.
Ingo
1
@Ingo No. (1) Wenn Schleifen nicht als Rekursion implementiert sind, gibt es keinen Grund dafür, dass sie auf dem Stack angezeigt werden (Tail Call, Jump, Call). (2) Die TCO ist allgemeiner als die Schwanzrekursionsoptimierung. Meine Antwort verwendet die Rekursion als Beispiel . (3) Wenn Sie in einem Stil programmieren, der sich auf die Gesamtbetriebskosten stützt , ist das Ausschalten dieser Optimierung keine Option - vollständige Gesamtbetriebskosten oder vollständige Stapelverfolgungen sind entweder eine Sprachfunktion oder nicht. Beispiel: Scheme schafft es, die Nachteile der Gesamtbetriebskosten durch ein erweitertes Ausnahmesystem auszugleichen.
amon
1
(1) stimme voll zu. Aber aus der gleichen Überlegung gibt es natürlich keinen Grund, Hunderte und Tausende von Stack-Trace-Einträgen beizubehalten, auf die alle return foo(....);in Methode foo(2) verweisen . Wir akzeptieren jedoch unvollständige Ablaufverfolgungen von Schleifen, Zuweisungen (!) Und Anweisungsfolgen. Wenn Sie zum Beispiel einen unerwarteten Wert in einer Variablen finden, möchten Sie sicher wissen, wie er dort ankommt. Aber Sie beklagen sich nicht über fehlende Spuren in diesem Fall. Weil es irgendwie in unser Gehirn eingraviert ist, dass a) es nur bei Anrufen passiert, b) es bei allen Anrufen passiert. Beides ergibt keinen Sinn, IMHO.
Ingo
(3) Stimme nicht zu. Ich kann keinen Grund sehen, warum es unmöglich sein sollte, meinen Code mit einem Problem der Größe N zu debuggen, für einige N, die klein genug sind, um mit dem normalen Stapel davonzukommen. Schalten Sie dann den Schalter und die Gesamtbetriebskosten ein, um die Einschränkung der Probemgröße effektiv aufzuheben.
Ingo
@Ingo “Stimme nicht zu. Ich kann keinen Grund erkennen, warum es unmöglich sein sollte, meinen Code mit einem Problem der Größe N zu debuggen, wenn einige N klein genug sind, um mit dem normalen Stack davonzukommen off überläuft den Stack und stürzt das Programm ab, so dass kein Debugging möglich ist. Google lehnte es ab, TCO in V8 JS zu implementieren, da dieses Problem zufällig auftrat . Sie würden eine spezielle Syntax wünschen, damit der Programmierer erklären kann, dass er die Gesamtbetriebskosten und den Verlust des Stack-Trace wirklich will. Weiß jemand, ob Ausnahmen auch von TCO geschraubt werden?
Shelby Moore III
6

Ein wesentlicher Teil der Aufrufe in einem Programm sind Tail Calls. Jedes Unterprogramm hat einen letzten Aufruf, daher hat jedes Unterprogramm mindestens einen Endaufruf. Tail Calls haben die Leistungsmerkmale GOTOaber die Sicherheit eines Unterprogrammaufrufs.

Mit Proper Tail Calls können Sie Programme schreiben, die Sie sonst nicht schreiben können. Nehmen Sie zum Beispiel eine Zustandsmaschine. Eine Zustandsmaschine kann sehr direkt implementiert werden, indem jeder Zustand ein Unterprogramm und jeder Zustandsübergang ein Unterprogrammaufruf ist. In diesem Fall wechseln Sie von Staat zu Staat, indem Sie Anruf nach Anruf nach Anruf tätigen, und Sie kehren tatsächlich nie zurück! Ohne die richtigen Tail Calls würden Sie den Stack sofort sprengen.

Ohne PTC, müssen Sie Verwendung GOTOoder Trampoline oder Ausnahmen als Kontrollfluss oder so ähnlich. Es ist viel hässlicher und nicht so sehr eine direkte 1: 1-Darstellung der Zustandsmaschine.

(Beachten Sie, wie ich es geschickt vermieden habe, das langweilige "Schleifen" -Beispiel zu verwenden. Dies ist ein Beispiel, in dem PTCs auch in einer Sprache mit Schleifen nützlich sind .)

Ich habe hier bewusst den Begriff "Proper Tail Calls" anstelle von TCO verwendet. TCO ist eine Compileroptimierung. PTC ist eine Sprachfunktion, bei der jeder Compiler die TCO durchführen muss.

Jörg W. Mittag
quelle
The vast majority of calls in a program are tail calls. Nicht, wenn "die überwiegende Mehrheit" der aufgerufenen Methoden mehr als einen eigenen Aufruf ausführt. Every subroutine has a last call, so every subroutine has at least one tail call. Dies ist trivialerweise nachweisbar als falsch: return a + b. (Es sei denn, Sie sprechen eine verrückte Sprache, in der Grundrechenarten als Funktionsaufrufe definiert sind.)
Mason Wheeler,
1
"Das Hinzufügen von zwei Zahlen bedeutet das Hinzufügen von zwei Zahlen." Mit Ausnahme von Sprachen, in denen dies nicht der Fall ist. Was ist mit der + -Operation in Lisp / Scheme, bei der ein einzelner arithmetischer Operator eine beliebige Anzahl von Argumenten verwenden kann? (+ 1 2 3) Der einzig vernünftige Weg, dies umzusetzen, ist eine Funktion.
Evicatos
1
@ Mason Wheeler: Was meinst du mit Abstraktionsinversion?
Giorgio
1
@MasonWheeler Das ist ohne Zweifel der meistgewellte Wikipedia-Eintrag zu einem technischen Thema, den ich je gesehen habe. Ich habe einige zweifelhafte Einträge gesehen, aber das ist nur ... wow.
Evicatos
1
@ MasonWheeler: Sprechen Sie über die Listenlängenfunktionen auf den Seiten 22 und 23 von On Lisp? Die Tail-Call-Version ist etwa 1,2-fach so kompliziert, bei weitem nicht 3-fach. Mir ist auch nicht klar, was Sie unter Abstraktionsinversion verstehen.
Michael Shaw
4

"Die JVM unterstützt keine Tail-Call-Optimierung, daher sage ich viele explodierende Stacks voraus."

Jeder, der dies sagt, versteht entweder (1) die Tail-Call-Optimierung nicht oder (2) die JVM nicht oder (3) beides.

Ich beginne mit der Definition von Tail-Calls aus Wikipedia (wenn Sie Wikipedia nicht mögen, finden Sie hier eine Alternative ):

In der Informatik ist ein Tail-Aufruf ein Unterprogrammaufruf, der in einer anderen Prozedur als letzte Aktion ausgeführt wird. es kann einen Rückgabewert erzeugen, der dann sofort von der aufrufenden Prozedur zurückgegeben wird

Im folgenden Code ist der Anruf an bar()der Rückruf von foo():

private void foo() {
    // do something
    bar()
}

Die Optimierung von Tail-Aufrufen geschieht, wenn die Sprachimplementierung, die einen Tail-Aufruf sieht, keinen normalen Methodenaufruf verwendet (wodurch ein Stack-Frame erstellt wird), sondern stattdessen eine Verzweigung erstellt. Dies ist eine Optimierung, da ein Stack-Frame Speicher benötigt und CPU-Zyklen erforderlich sind, um Informationen (wie z. B. die Rücksprungadresse) auf den Frame zu übertragen, und da angenommen wird, dass das Aufruf / Rücksprung-Paar mehr CPU-Zyklen benötigt als ein unbedingter Sprung.

TCO wird oft auf Rekursion angewendet, aber das ist nicht seine einzige Verwendung. Es gilt auch nicht für alle Rekursionen. Der einfache rekursive Code zum Berechnen einer Fakultät kann beispielsweise nicht nachträglich optimiert werden, da das Letzte, was in der Funktion passiert, eine Multiplikationsoperation ist.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

Um die Tail-Call-Optimierung zu implementieren, benötigen Sie zwei Dinge:

  • Eine Plattform, die Verzweigungen zusätzlich zu Subtroutinenaufrufen unterstützt.
  • Ein statischer Analysator, mit dem festgestellt werden kann, ob eine Tail Call-Optimierung möglich ist.

Das ist es. Wie ich bereits an anderer Stelle bemerkt habe, hat die JVM (wie jede andere Turing-complete-Architektur) ein Goto. Es ist ein bedingungsloses goto-Objekt vorhanden , aber die Funktionalität kann leicht mithilfe eines bedingten Zweigs implementiert werden.

Die statische Analyse ist schwierig. Innerhalb einer einzelnen Funktion ist das kein Problem. Hier ist zum Beispiel eine rekursive Scala-Funktion, um die Werte in a zu summieren List:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

Diese Funktion wird in den folgenden Bytecode umgewandelt:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Beachten Sie die goto 0am Ende. Im Vergleich dazu wird eine äquivalente Java-Funktion (die ein verwenden muss Iterator, um das Verhalten des Aufteilens einer Scala-Liste in Kopf und Schwanz zu imitieren) in den folgenden Bytecode umgewandelt. Beachten Sie, dass die letzten beiden Operationen jetzt ein Aufruf sind , gefolgt von einer expliziten Rückgabe des durch diesen rekursiven Aufruf erzeugten Werts.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

Die Optimierung von Tail-Aufrufen für eine einzelne Funktion ist trivial: Der Compiler kann feststellen, dass es keinen Code gibt, der das Ergebnis des Aufrufs verwendet, sodass er den Aufruf durch einen ersetzen kann goto.

Wo das Leben schwierig wird, ist, wenn Sie mehrere Methoden haben. Die Verzweigungsanweisungen der JVM sind im Gegensatz zu denen eines Universalprozessors wie dem 80x86 auf eine einzige Methode beschränkt. Es ist immer noch relativ einfach, wenn Sie über private Methoden verfügen: Der Compiler kann diese Methoden nach Bedarf einbinden, um Endaufrufe zu optimierenswitch , um das Verhalten zu steuern). Sie können diese Technik sogar auf mehrere öffentliche Methoden in derselben Klasse ausweiten: Der Compiler fügt die Methodentexte ein, stellt öffentliche Bridge-Methoden bereit und interne Aufrufe werden zu Sprüngen.

Dieses Modell bricht jedoch zusammen, wenn Sie öffentliche Methoden in verschiedenen Klassen berücksichtigen, insbesondere im Hinblick auf Schnittstellen und Klassenladeprogramme. Der Compiler auf Quellenebene verfügt einfach nicht über das erforderliche Wissen, um die Tail-Call-Optimierung zu implementieren. Im Gegensatz zu "Bare-Metal" -Implementierungen verfügt die JVM über die entsprechenden Informationen in Form des Hotspot-Compilers (zumindest der frühere Sun-Compiler). Ich weiß nicht, ob sie tatsächlich funktioniert Tail-Call-Optimierungen und vermuten nicht, aber es könnte .

Womit ich zum zweiten Teil Ihrer Frage komme, den ich als "sollten wir uns darum kümmern?" Umformulieren werde.

Wenn Ihre Sprache die Rekursion als einziges Grundelement für die Iteration verwendet, ist Ihnen das natürlich wichtig. Sprachen, die diese Funktion benötigen, können sie jedoch implementieren. Die einzige Frage ist, ob ein Compiler für diese Sprache eine Klasse erzeugen kann, die von einer beliebigen Java-Klasse aufgerufen und aufgerufen werden kann.

Außerhalb dieses Falles werde ich Ablehnungen einladen, indem ich sage, dass dies irrelevant ist. Der meiste rekursive Code, den ich gesehen habe (und mit vielen Grafikprojekten gearbeitet habe), ist nicht für Tail-Calls optimierbar . Wie die einfache Fakultät verwendet sie die Rekursion, um den Status zu erstellen, und die Tail-Operation ist eine Kombination.

Für Code, der per Tail-Call optimiert werden kann, ist es häufig unkompliziert, diesen Code in eine iterierbare Form zu übersetzen. Zum Beispiel kann diese sum()Funktion, die ich zuvor gezeigt habe, verallgemeinert werden als foldLeft(). Wenn Sie sich die Quelle ansehen , werden Sie feststellen, dass sie tatsächlich als iterative Operation implementiert ist. Jörg W. Mittag ließ ein Beispiel einer Zustandsmaschine über Funktionsaufrufe implementieren; Es gibt viele effiziente (und wartbare) Zustandsmaschinenimplementierungen, die nicht darauf angewiesen sind, dass Funktionsaufrufe in Sprünge übersetzt werden.

Ich werde mit etwas völlig anderem abschließen. Wenn Sie Ihren Weg von Fußnoten in der SICP googeln, könnten Sie hier landen . Ich persönlich finde das viel interessanter, als wenn mein Compiler durch ersetzt JSRwird JUMP.

kdgregory
quelle
Wenn ein Tail-Call-Opcode vorhanden wäre, warum sollte die Tail-Call-Optimierung etwas anderes erfordern, als an jedem Aufrufort zu beobachten, ob die aufrufende Methode danach Code ausführen müsste? Es kann sein, dass in einigen Fällen eine Anweisung wie return foo(123);diese besser durch Inlining ausgeführt werden kann, fooals durch Generieren von Code, um den Stack zu manipulieren und einen Sprung auszuführen, aber ich verstehe nicht, warum sich der Tail-Call von einem normalen Call-In unterscheidet diesbezüglich.
Supercat
@supercat - Ich bin mir nicht sicher, was deine Frage ist. Der erste Punkt in diesem Beitrag ist, dass der Compiler nicht wissen kann, wie der Stack-Frame aller potenziellen Callees aussehen könnte (denken Sie daran, dass der Stack-Frame nicht nur die Funktionsargumente, sondern auch die lokalen Variablen enthält). Ich nehme an, Sie könnten einen Opcode hinzufügen, der eine Laufzeitprüfung für kompatible Frames durchführt, aber das bringt mich zum zweiten Teil des Beitrags: Was ist der wahre Wert?
kdgregory