La JVM impedisce l'ottimizzazione delle chiamate in coda?

Question

Ho visto questa citazione sulla domanda: Qual è un buon linguaggio funzionale su cui costruire un servizio web?

  

Scala in particolare non supporta l'eliminazione della coda, tranne che nelle funzioni auto-ricorsive, che limitano il tipo di composizione che puoi fare (questa è una limitazione fondamentale della JVM).

È vero? In tal caso, che cos'è la JVM che crea questa limitazione fondamentale?

Answer 1

Questo post: Ricorsione o iterazione? potrebbe essere utile.

In breve, l'ottimizzazione delle chiamate di coda è difficile da eseguire nella JVM a causa del modello di sicurezza e della necessità di avere sempre una traccia dello stack disponibile. Questi requisiti potrebbero in teoria essere supportati, ma probabilmente richiederebbero un nuovo bytecode (vedi La proposta informale di John Rose ).

C'è anche più discussione in Sun bug # 4726340 , dove termina la valutazione (dal 2002):

  

Credo che ciò possa essere fatto comunque, ma non è un compito piccolo.

Attualmente, ci sono lavori in corso nella Da Vinci Machine progetto. Lo stato del sottoprogetto di coda chiamata è elencato come "proto 80%"; è improbabile che arrivi a Java 7, ma penso che abbia ottime possibilità con Java 8.

Answer 2

La limitazione fondamentale è semplicemente che la JVM non fornisce chiamate di coda nel suo codice byte e, di conseguenza, non esiste un modo diretto per un linguaggio costruito sulla JVM di fornire chiamate di coda stesse. Esistono soluzioni alternative che possono ottenere un effetto simile (ad esempio il trampolino), ma hanno il grave costo di prestazioni orribili e offuscano il codice intermedio generato che rende inutile un debugger.

Quindi la JVM non può supportare alcun linguaggio di programmazione funzionale di qualità di produzione fino a quando Sun non implementa le chiamate di coda nella JVM stessa. Ne hanno discusso per anni, ma dubito che implementeranno mai le chiamate di coda: sarà molto difficile perché hanno prematuramente ottimizzato la loro VM prima di implementare tali funzionalità di base e lo sforzo di Sun è fortemente focalizzato su linguaggi dinamici piuttosto che linguaggi funzionali.

Quindi c'è una forte argomentazione secondo cui Scala non è un vero linguaggio di programmazione funzionale: questi linguaggi hanno considerato le chiamate di coda come una caratteristica essenziale da quando Scheme è stato introdotto per la prima volta oltre 30 anni fa.

Answer 3

Scala 2.7.x supporta l'ottimizzazione della coda per l'auto-ricorsione (una funzione che si chiama) dei metodi finali e delle funzioni locali.

Scala 2.8 potrebbe venire con il supporto libreria anche per il trampolino, che è una tecnica per ottimizzare le funzioni reciprocamente ricorsive.

Una buona quantità di informazioni sulla ricorsione dello stato di Scala è disponibile in il blog di Rich Dougherty .

Answer 4

Oltre al documento collegato in Lambda The Ultimate (dal link mmyer pubblicato sopra), John Rose di Sun ha altro da dire sull'ottimizzazione delle chiamate di coda.

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

Ho sentito che un giorno potrebbe essere implementato sulla JVM. Il supporto per le chiamate di coda, tra le altre cose, viene esaminato sulla Da Vinci Machine.

http://openjdk.java.net/projects/mlvm/

Answer 5

Tutte le fonti indicano che la JVM non è in grado di ottimizzare in caso di ricorsione della coda, ma leggendo L'autore di Java è in grado di ottenere l'ottenimento di Java, è possibile trovare il 2003 maggiori prestazioni di ricorsione implementando la ricorsione di coda.

Puoi trovare il suo reclamo a pagina 212 (cerca 'ricorsione della coda' dovrebbe essere il secondo risultato). Cosa dà?