¿Cómo utilizar TailCalls?

Question

Si entiendo correctamente, scala.util.control.TailCalls se puede usar para evitar desbordamientos de pila para funciones no recursivas de cola mediante el uso de un trampolín. El ejemplo dado en la API es sencillo:

import scala.util.control.TailCalls._ 

def isEven(xs: List[Int]): TailRec[Boolean] = 
    if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail)) 

def isOdd(xs: List[Int]): TailRec[Boolean] = 
    if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail)) 

isEven((1 to 100000).toList).result 

Sin embargo, el caso más interesante es que si quieres hacer algunas operaciones después de la llamada recursve. Tengo una aplicación factorial "ingenua" de alguna manera corriendo por

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result) 

pero esto se ve horrible y dudo que esto es el uso previsto. Entonces mi pregunta es cómo escribir correctamente una función factorial o fibonacci usando TailCalls (sí, sé cómo usar los acumuladores para obtener recursivas de cola). ¿O TailCalls no es adecuado para este tipo de problema?

Answer 1

Sí, su ingenuo factorial no será recursivo de cola, y utilizará el espacio de pila lineal en el valor del argumento. El propósito de scala.util.control.TailCalls no es convertir mágicamente los algoritmos recursivos no cola en recursivos de cola. Su propósito es permitir ciclos de funciones mutuamente llamadas para ejecutar en un espacio de pila constante.

El compilador de Scala implementa la optimización de recursión de cola para los métodos que se llaman a sí mismos en la posición de cola, permitiendo que el marco de pila del método de llamada sea utilizado por la persona que llama. Lo hace esencialmente al convertir una llamada probadamente recursiva en la cola en un ciclo while, bajo las cubiertas. Sin embargo, debido a las restricciones de JVM no hay forma de que implemente la optimización de la llamada de cola, lo que permitiría que cualquier llamada de método en la posición de cola reutilice el marco de pila de la persona que llama. Esto significa que si tiene dos o más métodos que se llaman entre sí en posición de cola, no se realizará ninguna optimización y se correrá el riesgo de que se desborde la pila. scala.util.control.TailCalls es un truco que le permite evitar este problema.

Por cierto, vale la pena mirar la fuente a scala.util.control.TailCalls. La llamada de "resultado" es donde se realiza todo el trabajo interesante, y es básicamente un ciclo de tiempo dentro.

Answer 2

Esta pregunta es más de 6 años de edad, pero no parece la respuesta aceptada para responder a la pregunta: ¿

Así que mi pregunta es cómo escribir una función factorial o de Fibonacci usando correctamente TailCalls (sí, Sé cómo usar los acumuladores para que sean recursivos por la cola).

Por lo tanto, aquí está:

object Factorial { 

    /** 
    * Returns the nth factorial 
    */ 
    def apply(n: Long): BigInt = { 
    if (n < 0) 
     throw new IllegalArgumentException("Can't factorial to an index less than 0") 
    else { 
     import scala.util.control.TailCalls._ 
     def step(current: Long): TailRec[BigInt] = { 
     if (current <= 0) 
      done(1) 
     else 
      tailcall { 
      for { 
       next <- step(current - 1) 
      } yield current * next 
      } 
     } 
     step(n).result 
    } 
    } 

} 

assert(Factorial(0) == 1) 
assert(Factorial(7) == 5040) 
assert(Factorial(10) == 3628800) 

Uno de los grandes casos de uso para el uso de TailCalls es hacer algo que sea haga doble-similares.