Endrekursions-Nachlese


Wie ich bei meinem ersten Beitrag über Endrekursion gelernt habe, kann man zwar im Byte-Code Endrekursion nachbauen (wie es Scala tut), aber automatisch kann das die JVM von Sun nicht, und auch Sun’s Java-Compiler liefert keine nachgebaute Version.

Eigentlich ziemlich unverständlich, denn das einzige halbwegs stichhaltige Gegenargument ist, dass die rekursiven Aufrufe bei Endrekursion natürlich nicht (ohne weiteres) im Stacktrace zu finden sind. Aber ganz ehrlich: Ist ein Programm, das viele Fälle von Stack-Überlaufen vermeidet und zudem schneller läuft nicht wichtiger als ein „ordentlicher“ Stacktrace?

Bei Sun scheint sich nun – nach jahrelangem Dornröschenschlaf – langsam vorsichtiges Umdenken einzustellen, wie der Blog-Eintrag. Tail Calls in the JVM (John Rose @ Sun) zeigt.

Warum ich das „JVM von Sun“ so betone? Ganz einfach: Einige andere JVMs, wie z.B. das in Eclipse verwendete J9 von IBM, besitzen Endrekursion, und das teilweise recht lange (IBM’s Implementierung beispielsweise seit Java 1.3). Vor diesem Hintergrund erscheint Sun’s Zurückhaltung einigermaßen peinlich.

Endrekursion lässt sich übrigens auch mit anderen Mitteln simulieren, z.B. mit sogenannten „Trampolines“:

Used in some LISP implementations, a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style). A single trampoline is sufficient to express all control transfers of a program; a program so expressed is trampolined, or in trampolined style; converting a program to trampolined style is trampolining. Trampolined functions can be used to implement tail recursive function calls in stack-oriented languages.

(Wikipedia)
Hier beißt sich die Katze in den Schwanz, denn Java verfügt bekanntlich nicht über Funktionen höherer Ordnung, was die Implementierung bestimmt nicht einfacher macht (es gibt eine Klasse sun.reflect.misc.Trampoline, aber nichts genaues weiß ich nicht …)

Wer ganz genau wissen will, wie Scala die JVM zur Endrekursion „überredet“, sei auf das Whitepaper Tail call elimination on the Java Virtual Machine (M. Schinz, M. Odersky) verwiesen.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s