Frege esegue l'ottimizzazione delle chiamate tail?

Question

Le chiamate di coda sono ottimizzate in Frege. So che c'è il TCO nè in Java nè nelle lingue che compilano in codice bytecode JVM come Clojure e Scala. Che mi dici di Frege?

Answer 1

Frege do Tail Ottimizzazione della ricorsione semplicemente generando cicli while.

Le chiamate di coda generali sono gestite "a proposito" attraverso la pigrizia. Se il compilatore vede una chiamata di coda a una funzione sospetta che è nota per essere (indirettamente) ricorsiva, viene restituito un risultato pigro (un thunk). Quindi, il vero onere di chiamare quella funzione risiede nel chiamante. In questo modo, gli stack la cui profondità dipende dai dati vengono evitati.

Detto questo, già la profondità dello stack statico è per sua natura più profonda in un linguaggio funzionale rispetto a Java. Quindi, alcuni programmi dovranno ricevere uno stack più grande (cioè con -Xss1m).

Esistono casi patologici, in cui vengono generati i thunk grandi e quando vengono valutati, si verificherà un overflow dello stack. Un esempio famoso è la funzione foldl (stesso problema di Haskell). Quindi, la piega di sinistra standard in Frege è fold, che è ricorsiva e rigida nell'accumulatore e quindi funziona nello spazio di stack costante (come Haskells foldl ').

Il seguente programma dovrebbe non overflow dello stack, ma stampa "false" dopo 2 o 3 secondi:

module Test 
    -- inline (odd) 
    where 

even 0 = true 
even 1 = false 
even n = odd (pred n) 

odd n = even (pred n) 

main args = println (even 123_456_789) 

Questo funziona come segue: println deve avere un valore per la stampa, quindi cerca di valutare (anche n). Ma tutto ciò che ottiene è un thunk a (dispari (pred n)). Quindi cerca di valutare questo thunk, che ottiene un altro thunk (anche (pred (pred n))). anche deve valutare (pred (pred n)) per vedere se l'argomento era 0 o 1, prima di restituire un altro thunk (dispari (pred (n-2)) dove n-2 è già valutato. In questo modo, tutte le chiamate (a livello JVM) viene eseguito da println. In ogni istante nemmeno invoca lo odd, o viceversa.

Se si disimpegna la direttiva inline, si ottiene una versione ricorsiva della coda pari, e il risultato viene ottenuto dieci volte . più veloce

Inutile dire che questo algoritmo goffo è solo per dimostrazione -. normalmente si potrebbe verificare la presenza di even-ness con un'operazione po

Ecco un'altra versione, che è patologico e si impilare overflo w:

even 0 = true 
even 1 = false 
even n = not . odd $ n 
odd = even . pred 

Il problema è qui che not è la chiamata coda ed è severo nel suo argomento (vale a dire, per negare qualcosa, è necessario innanzitutto avere quel qualcosa). Quindi, quando viene calcolato even n, l'not deve valutare completamente odd n che, a sua volta, deve valutare completamente even (pred n) e quindi richiederà 2 * n frame di stack.

Sfortunatamente, questo non cambierà, anche se la JVM dovrebbe avere una coda adeguata una volta. La ragione è la ricorsione nell'argomento di una funzione rigorosa.

Answer 2

@Landei TCO non è completamente supportato in Scala ... prova questo.

def foo() { def bar() { println("bar"); foo() }; println("foo"); bar() } 

Nota, non ho abbastanza reputazione per commentare direttamente. Trova un commento a cui sto rispondendo nei commenti della domanda originale.