Java-Tail-Call-Optimierung

1. Was ist die Tail-Call-Optimierung?
2. Gründe dafür, keine Tail-Call-Optimierung in Java zu haben
3. Gibt es eine Möglichkeit, die Tail-Call-Optimierung in Java zu simulieren?

Dieses Tutorial spricht über Tail-Call-Optimierung (auch als TCO bezeichnet) und die Gründe dafür, dass es in Java nicht existiert. Wir werden auch einige andere Möglichkeiten sehen, die wir verwenden können, um TCO in Java zu simulieren.

Was ist die Tail-Call-Optimierung?

Die Tail-Call-Optimierung ist ein Prozess, bei dem wir vermeiden können, einer Funktion einen neuen Stack-Frame zuzuweisen, da die aufrufende Funktion einen Wert zurückgibt, den sie von der aufgerufenen Funktion erhält.

Eine der häufigsten Anwendungen ist die Tail-Rekursion (eine rekursive Funktion, bei der sich eine Funktion am Ende/Ende selbst aufruft), bei der die rekursive Methode geschrieben wird, um die Tail-Call-Optimierung zu nutzen und konstanten Stapelspeicherplatz zu verwenden.

Das Scheme ist eine jener Programmiersprachen, die in der Spezifikation garantieren, dass jede Implementierung dieser Optimierung dienen muss. Das Folgende sind also zwei Beispiele für die faktorielle Methode in der Programmiersprache Scheme.

Beispiel Code Eins (ohne Tail-Rekursiv):

(define (factorial n)
  (if (= n 0) 1
      (* n (factorial (- n 1)))))

Beispiel Code Zwei (mit Tail-Rekursiv):

(define (factorial n)
  (define (factorial-tail n accum)
    (if (= n 0) accum
        (factorial-tail (- n 1) (* n accum))))
  (factorial-tail n 1))

In Beispielcode eins ist die Funktion nicht endrekursiv. Dies liegt daran, dass die Methode bei jedem rekursiven Aufruf (unter Berücksichtigung eines faktoriellen Beispiels) die Multiplikation nachverfolgen muss, die sie mit den Ergebnissen nach der Rückgabe des Aufrufs durchführen muss.

Als solches sieht ein Stack wie folgt aus.

(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Im Gegensatz dazu würde der Stack-Trace für eine schwanzrekursive Fakultät wie unten angegeben aussehen.

(factorial 3)
(factorial-tail 3 1)
(factorial-tail 2 3)
(factorial-tail 1 6)
(factorial-tail 0 6)
6

Wir müssen lediglich bei jedem Aufruf von factorial-tail dieselben Daten nachverfolgen.

Der Grund dafür ist, dass wir einen Wert zurückgeben, den wir bis zu einem top durchbekommen, d.h. selbst wenn wir (Fakultät 1000000) aufrufen würden, brauchen wir nur so viel Platz wie für ( Fakultät 3).

Dies ist nicht der Fall, wenn wir Non-Tail-Rekursive als faktoriell betrachten, und die großen Werte können zu einem Stapelüberlauf führen.

Gründe dafür, keine Tail-Call-Optimierung in Java zu haben

Derzeit wird auf Compiler-Ebene die Java-Tail-Call-Optimierung in einfachem Java nicht unterstützt. Aufgrund des Vorhandenseins der Vererbung ist es möglicherweise nicht einfach, eine aufgerufene Methode herauszufinden.

Außerdem erlaubt der gegenwärtige Stack-Zählmechanismus nicht, dass diese Art von Optimierung bald implementiert wird. Es könnte einen Grund geben, die drastische Änderung der Funktionsweise der Sprache jedes Jahr zu vermeiden.

Der erste Grund ist, dass die Tail-Call-Optimierung teuer ist. Zweitens erhalten wir gemäß einer Regel in Java den Stack-Trace, wenn wir auf einen Fehler stoßen.

Und die Stack-Traces sind wohldefinierte Konzepte, die kaum einen Stack-Frame für jeden logischen Aufruf verfolgen können. Dies ist nicht möglich, wenn eine Tail-Call-Optimierung in Java vorhanden ist.

Drittens ist Tail-Call-Optimierung als Modell die Vorgehensweise, aber nicht die einzige Möglichkeit. Im Allgemeinen ist es nicht so schwierig, alles, was als TCO-rekursive App geschrieben werden kann, in einen schleifenbasierten, nicht rekursiven Algorithmus umzugestalten.

Also, was sollten wir tun? Wir können stattdessen die while- oder for-Schleife verwenden.

Gibt es eine Möglichkeit, die Tail-Call-Optimierung in Java zu simulieren?

Obwohl Java, die virtuelle Maschine, über neue Funktionen verfügt, die anderen die Arbeit erleichtern können, werden Nicht-Java-Programmiersprachen in die Klassendateien kompiliert, um sie auf einer Java-Laufzeitumgebung auszuführen, um die Tail-Call-Optimierung zu unterstützen.

Wir empfehlen Ihnen, sich die folgenden zwei Videos anzusehen, um die Dinge im Großen und Ganzen zu verstehen, da nicht jedes Feature immer gerechtfertigt ist, insbesondere wenn die Sprache eine der beliebtesten Sprachen ist.

1. Video 1: Brian Goetz – Stewardship: die ernüchternden Teile
2. Video 2: Java-Sprache und Plattform-Futures

Wir sind uns also nicht sicher, welcher Ansatz für die Verwendung von TCO in Java verwendet werden sollte. es ist im Vorschlag von Project Loom gut erklärt.

Wir glauben jedoch, dass es noch einige andere Möglichkeiten gibt, die wir verwenden können, um die Tail-Call-Optimierung in Java zu simulieren. Die erste besteht darin, eine andere JVM-Sprache zu verwenden, beispielsweise Scala.

Die zweite Lösung kann die Verwendung des lambda-Ausdrucks sein. Oder, wenn Sie sich trauen, können Sie etwas Gefährliches wie dieses ausprobieren.