Scala supporta l'ottimizzazione della ricorsione in coda?

Question

Scala supporta l'ottimizzazione della ricorsione in coda?

Answer 1

Scala fa l'ottimizzazione della ricorsione di coda in fase di compilazione, come hanno detto altri utenti. Cioè, una funzione ricorsiva di coda viene trasformata in un ciclo dal compilatore (un metodo invocato viene trasformato in un salto), come si può vedere dalla traccia di stack quando si esegue una funzione ricorsiva di coda.

provare il seguente frammento:

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1) 
boom(10) 

e controllare la traccia dello stack. Mostrerà solo una chiamata al boom delle funzioni, quindi il bytecode compilato non è ricorsivo.

c'è una proposta galleggianti intorno a implement tail calls at the JVM level - che a mio parere sarebbe una grande cosa da fare, come allora la JVM potrebbe fare ottimizzazioni runtime, piuttosto che compilare ottimizzazioni di tempo del codice - e potrebbe significare la coda più flessibile ricorsione. Fondamentalmente un tailcall invoke si comporterebbe esattamente come un normale metodo invoke ma lascerà cadere lo stack del chiamante quando è sicuro farlo - la specifica degli stati JVM che i frame dello stack devono essere preservati, quindi il JIT deve fare qualche analisi del codice statico per scoprire se i frame dello stack non saranno mai utilizzati.

Lo stato corrente è proto 80%. Non credo che sarà fatto in tempo per Java 7 (invokedynamic ha una priorità maggiore, e l'implementazione è quasi terminata) ma Java 8 potrebbe vederla implementata.

Answer 2

Solo in casi molto semplici in cui la funzione è auto-ricorsiva.

Proof of tail recursion ability.

Sembra Scala 2.8 potrebbe essere migliorare il riconoscimento coda ricorsione, però.

Answer 3

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

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

Una buona quantità di informazioni sullo stato della ricorsione Scala può essere trovata in Rich Dougherty's blog.

Answer 4

In Scala 2.8 è possibile utilizzare @tailrec per contrassegnare metodo specifico che si spera il compilatore di ottimizzare:

import scala.annotation.tailrec 

@tailrec def factorialAcc(acc: Int, n: Int): Int = { 
    if (n <= 1) acc 
    else factorialAcc(n * acc, n - 1) 
} 

Se un metodo non può essere ottimizzato si ottiene un messaggio di avviso.