Quali limitazioni impone la JVM all'ottimizzazione di coda

Ora, non so molto di Clojure e poco di Scala, ma lo farò.

Per prima cosa, dobbiamo distinguere tra CALL in coda e RECURSION in coda. La ricorsione della coda è infatti piuttosto facile da trasformare in un loop. Con le chiamate di coda, è molto più difficile da realizzare nel caso generale. Hai bisogno di sapere cosa viene chiamato, ma con il polimorfismo e / o le funzioni di prima classe, raramente lo sai, quindi il compilatore non può sapere come sostituire la chiamata. Solo in fase di esecuzione si conosce il codice di destinazione e si può saltare lì senza allocare un altro frame dello stack. Ad esempio, il seguente frammento ha una coda e non ha bisogno di alcuno spazio nello stack se correttamente ottimizzato (incluso il TCO), ma non può essere eliminato durante la compilazione per la JVM:

function forward(obj: Callable<int, int>, arg: int) =
    let arg1 <- arg + 1 in obj.call(arg1)

Anche se è un po 'inefficiente, ci sono interi stili di programmazione (come Continuation Passing Style o CPS) che hanno tonnellate di chiamate tail e raramente ritornano. In questo modo, senza un TCO completo, puoi eseguire solo piccoli bit di codice prima di esaurire lo spazio di stack.

What facility of the underlying virtual machine would allow the compiler to handle TCO more easily?

Un'istruzione di coda, come nella VM Lua 5.1. Il tuo esempio non diventa molto più semplice. Il mio diventa qualcosa del genere:

push arg
push 1
add
load obj
tailcall Callable.call
// implicit return; stack frame was recycled

As a sidenote, I would not expect actual machines to be much smarter than the JVM.

Hai ragione, non lo sono. In effetti, sono meno intelligenti e quindi non conoscono (molto) cose come gli stack frames. Questo è esattamente il motivo per cui si possono trucchi come riutilizzare lo spazio dello stack e saltare al codice senza premere un indirizzo di ritorno.

Clojure potrebbe eseguire l'ottimizzazione automatica della ricorsione della coda in loop: è certamente possibile farlo sulla JVM come dimostra la Scala.

In realtà era una decisione progettuale di non eseguire questa operazione: devi utilizzare esplicitamente il modulo speciale recur se desideri questa funzione. Consulta la discussione della posta Re: perché non ottimizza le chiamate tail sul gruppo google Clojure.

Sull'attuale JVM, l'unica cosa che è impossibile da fare è l'ottimizzazione delle chiamate tail tra diverse funzioni (ricorsione reciproca). Questo non è particolarmente complesso da implementare (altri linguaggi come Scheme hanno avuto questa caratteristica fin dall'inizio) ma richiederebbero modifiche alle specifiche JVM. Ad esempio, dovresti modificare le regole relative alla conservazione dello stack di chiamata della funzione completa.

È probabile che una futura iterazione della JVM ottenga questa capacità, anche se probabilmente come opzione, in modo da mantenere il comportamento compatibile all'indietro per il vecchio codice. Dì, Anteprima caratteristiche su Geeknizer elenca questo per Java 9:

Adding tail calls and continuations...

^{Naturalmente, le future roadmap sono sempre soggette a modifiche.}

A quanto pare, comunque non è un grosso problema. In oltre 2 anni di programmazione di Clojure, ho mai imbattersi in una situazione in cui la mancanza di TCO era un problema. I motivi principali sono:

• Puoi già ottenere una rapida ricorsione della coda per il 99% dei casi comuni con recur o un ciclo. Il caso di ricorsione della coda reciproca è piuttosto raro nel codice normale
• Anche quando hai bisogno di una ricorsione reciproca, spesso la profondità della ricorsione è abbastanza bassa da poterla semplicemente mettere in pila in ogni caso senza TCO. Il TCO è solo un "ottimizzazione" dopo tutto ....
• Nei casi molto rari in cui hai bisogno di una qualche forma di ricorsione reciproca che non consumi lo stack ci sono molte altre alternative che possono raggiungere lo stesso obiettivo: sequenze pigre, trampolini ecc.

As a sidenote, I would not expect actual machines to be much smarter than the JVM.

Non si tratta di essere più intelligenti, ma di essere diversi. Fino a poco tempo fa, la JVM è stata progettata e ottimizzata esclusivamente per una singola lingua (Java, ovviamente), che ha modelli di memoria e chiamata molto rigidi.

Non solo non c'era nessun goto o puntatori, non c'era nemmeno un modo per chiamare una funzione 'nuda' (una che non era un metodo definito all'interno di una classe).

Concettualmente, quando si targetizza JVM, uno scrittore di compilatori deve chiedere "come posso esprimere questo concetto in termini Java?". E ovviamente, non c'è modo di esprimere il TCO in Java.

Si noti che questi non sono visti come errori di JVM, perché non sono necessari per Java. Non appena Java ha bisogno di alcune funzionalità come queste, viene aggiunto a JVM.

Solo di recente le autorità Java hanno iniziato a prendere sul serio JVM come piattaforma per i linguaggi non-Java, quindi ha già ottenuto il supporto per le funzionalità che non hanno equivalente Java. Il più noto è la digitazione dinamica, che è già in JVM ma non in Java.

So, at the bytecode level, one just needs goto. In this case, in fact, the hard work is done by the compiler.

Hai notato che l'indirizzo del metodo inizia con 0? Che i tutti i metodi di set iniziano con 0? JVM non consente di saltare all'esterno di un metodo.

Non ho idea di cosa succederebbe con un ramo con offset al di fuori del metodo caricato da java - forse verrebbe catturato dal verificatore bytecode, forse genererebbe un'eccezione e forse salterà fuori dal metodo .

Il problema, naturalmente, è che non puoi davvero garantire dove saranno gli altri metodi della stessa classe, molto meno i metodi di altre classi. Dubito che JVM abbia qualche garanzia su dove caricherà i metodi, anche se sarei felice di essere corretto.