Perché Java non ha l'ottimizzazione per la ricorsione della coda?

Question

Perché Java non ha l'ottimizzazione per la ricorsione della coda?

#1 da (121 voti)
#2 da (22 voti)
#3 da (5 voti)
#4 da (4 voti)
#5 da (1 voti)

84

Da quello che ho letto: il motivo è perché non è facile determinare quale metodo verrà effettivamente chiamato come abbiamo ereditato.

Tuttavia, perché Java non dispone almeno dell'ottimizzazione della ricorsione in coda per i metodi statici e impone il modo corretto di richiamare metodi statici con il compilatore?

Perché Java non ha alcun supporto per la ricorsione in coda?

Non sono sicuro che ci sia qualche difficoltà qui.

Riguardo al suggerito duplicato , come spiegato da Jörg W Mittag ¹:

The other question asks about TCO, this one about TRE. TRE is much simpler than TCO.

Also, the other question asks about what limitations the JVM imposes on language implementations that wish to compile to the JVM, this question asks about Java, which is the one language that is not restricted by the JVM, since the JVM spec can be changed by the same people who design Java.

And lastly, there isn't even a restriction in the JVM about TRE, because the JVM does have intra-method GOTO, which is all that's needed for TRE

¹ _{Formattazione aggiunta per richiamare i punti fatti.}

recursion java compiler

posta InformedA 04.02.2015 - 09:40

fonte

5 risposte

Leggi altre domande sui tag recursion java compiler

Perché Java non è più utilizzato per lo sviluppo di giochi? [chiuso] Cosa c'è di sbagliato in Unlicense?

score 121 · Answer 1

Come spiegato da Brian Goetz (Java Language Architect presso Oracle) in questo video :

in jdk classes [...] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who's calling them.

Qualunque cosa che ha cambiato il numero di frame nello stack si romperebbe e causerebbe un errore. Ammette che questa è stata una ragione stupida, e quindi gli sviluppatori JDK hanno sostituito questo meccanismo.

Inoltre afferma che non è una priorità, ma quella ricorsione di coda

will eventually get done.

NB. Questo vale per HotSpot e OpenJDK, le altre macchine virtuali possono variare.

score 22 · Answer 2

Java non ha ottimizzazione delle chiamate tail per lo stesso motivo per cui la maggior parte delle lingue imperative non ce l'ha. I loop imperativi sono lo stile preferito della lingua e il programmatore può sostituire la ricorsione della coda con loop imperativi. La complessità non vale la pena per una funzionalità il cui utilizzo è scoraggiato come una questione di stile.

Questa cosa in cui i programmatori vogliono scrivere a volte in uno stile FP in lingue altrimenti imperative è venuta in voga solo negli ultimi 10 anni circa, dopo che i computer hanno iniziato a ridimensionare i core anziché i GHz. Anche ora, non è così popolare. Se suggerissi di sostituire un ciclo imperativo con la ricorsione della coda al lavoro, metà dei revisori del codice riderebbe e l'altra metà darebbe un aspetto confuso. Anche nella programmazione funzionale, generalmente si evita la ricorsione della coda a meno che altri costrutti come le funzioni di ordine superiore non si adattino in modo pulito.

score 5 · Answer 3

Java non ha un'ottimizzazione delle chiamate alta perché la JVM non ha un bytecode per le chiamate tail (a qualche puntatore di funzione staticamente sconosciuto , ad esempio un metodo in alcuni vtable).

Sembra che per ragioni sociali (e forse tecniche), l'aggiunta di una nuova operazione bytecode nella JVM (che renderebbe incompatibile con le versioni precedenti di quella JVM) è terribilmente difficile per il proprietario delle specifiche JVM.

^{Le ragioni tecniche per non aggiungere un nuovo codice bytecode nelle specifiche JVM includono il fatto che le realizzazioni JVM realistiche sono pezzi di software estremamente complessi (ad esempio a causa delle numerose ottimizzazioni JIT che sta facendo).}

Le chiamate di coda ad alcune funzioni sconosciute richiedono la sostituzione dello stack frame corrente con una nuova, e tale operazione dovrebbe essere presente nella JVM (non si tratta solo di modificare il compilatore generando bytecode).

score 4 · Answer 4

A meno che una lingua abbia una sintassi speciale per effettuare una chiamata di coda (ricorsiva o meno) e un compilatore squittisci quando viene richiesta una coda, ma non può essere generata, l'ottimizzazione "facoltativa" di coda o di ricorsione di coda produrrà situazioni dove un pezzo di codice può richiedere meno di 100 byte di stack su una macchina, ma più di 100.000.000 di byte di stack su un'altra. Tale diverso dovrebbe essere considerato qualitativo piuttosto che meramente quantitativo.

Si presume che le macchine possano avere diverse dimensioni di stack, e quindi è sempre possibile che il codice funzioni su una macchina ma fa saltare la pila su un'altra. Generalmente, tuttavia, il codice che funzionerà su una macchina anche quando lo stack è costretto artificialmente, probabilmente funzionerà su tutte le macchine con dimensioni di stack "normali". Se, tuttavia, un metodo che ricorre fino a 1.000.000 di profondità è ottimizzato in coda su una macchina ma non un'altra, l'esecuzione sulla prima macchina funzionerà probabilmente anche se il suo stack è insolitamente piccolo, e fallirà su quest'ultima anche se il suo stack è insolitamente grande .

score 1 · Answer 5

Penso che la ricorsione chiamata coda non venga utilizzata in Java principalmente perché così facendo si alterano le tracce dello stack e quindi si rende più difficile il debug di un programma. Penso che uno degli obiettivi principali di Java sia quello di consentire ai programmatori di eseguire facilmente il debug del loro codice, e lo stack tracing è essenziale per farlo soprattutto in un ambiente di programmazione altamente orientato agli oggetti. Dato che l'iterazione potrebbe essere utilizzata, il comitato linguistico deve aver capito che non vale la pena aggiungere la ricorsione alla coda.