¿Frege realiza la optimización de la cola de llamada?

Question

Se optimizan las llamadas finales en Frege. Sé que no hay TCO ni en Java ni en lenguajes que compilan códigos de byte JVM como Clojure y Scala. ¿Qué hay de Frege?

Answer 1

Frege does Tail Recursion Optimization simplemente generando while loops.

Las llamadas de cola generales se manejan "por cierto" a través de la pereza. Si el compilador ve una llamada final a una función sospechosa que se sabe que es (indirectamente) recursiva, se devuelve un resultado diferido (un thunk). Por lo tanto, la carga real de llamar a esa función recae en la persona que llama. De esta forma, se evitan las pilas cuya profundidad depende de los datos.

Dicho esto, ya la profundidad de la pila estática es por naturaleza más profunda en un lenguaje funcional que en Java. Por lo tanto, algunos programas necesitarán tener una pila más grande (es decir, con -Xss1m).

Existen casos patológicos, en los que se generan grandes thunks y cuando se evalúan, se produce un desbordamiento de la pila. Un ejemplo notorio es la función foldl (el mismo problema que en Haskell). Por lo tanto, el plegado a la izquierda estándar en Frege es plegado, que es recursivo de cola y estricto en el acumulador y, por lo tanto, trabaja en un espacio de pila constante (como Haskells foldl ').

El siguiente programa debe no desbordamiento de pila, pero la impresión "falsa" después de 2 ó 3 años:

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) 

Esto funciona de la siguiente manera: println debe tener un valor de imprimir, por lo que trata de evaluar (incluso n) Pero todo lo que obtiene es un golpe a (impar (pred n)). Por lo tanto, trata de evaluar este procesador, que recibe otro procesador (even (pred (pred n))). incluso debe evaluar (pred (pred n)) para ver si el argumento fue 0 o 1, antes de devolver otro procesador (impar (pred (n-2)) donde n-2 ya está evaluado. De esta manera, todas las llamadas (en el nivel JVM) se hace desde println. En ningún momento incluso se invoca impar, o viceversa.

Si uno descomenta la directiva en línea, uno obtiene una versión recursiva de cola, y el resultado se obtiene diez veces . rápido

hace falta decir que este algoritmo torpe es sólo para demostración -. normalmente uno se compruebe si-dad incluso con una operación de bit

Aquí es otra versión, que es patológico y se apilarán overflo w:

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

El problema aquí es que not es la llamada de cola y es estricta en su argumento (es decir, para negar algo, primero debe tener ese algo). Por lo tanto, cuando se calcula even n, entonces not debe evaluar completamente odd n que, a su vez, debe evaluar completamente even (pred n) y por lo tanto tomará 2 * n marcos de pila.

Lamentablemente, esto no va a cambiar, incluso si la JVM debe tener la cola adecuada un día. La razón es la recursión en el argumento de una función estricta.

Answer 2

@Landei TCO no se admite por completo en Scala ... prueba este.

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

Nota, no tengo suficiente reputación para comentar directamente. Encontrar comentario Estoy respondiendo en los comentarios de la pregunta original.