scala - ¿Cómo usar TailCalls?

tail-recursion trampolines

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 si desea realizar algunas operaciones después de la llamada recursiva. Tengo una implementació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 este sea el uso previsto. Entonces, mi pregunta es ¿cómo escribir una función factorial o de fibonacci usando TailCalls (sí, sé cómo usar acumuladores para hacerlos recursivos)? ¿O es que TailCalls no es adecuado para este tipo de problema?

Answer 1

Esta pregunta tiene más de 6 años, pero la respuesta aceptada no parece responderla:

Entonces, mi pregunta es ¿cómo escribir una función factorial o de fibonacci usando TailCalls (sí, sé cómo usar acumuladores para hacerlos recursivos)?

Asi que aqui esta:

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 usar TailCalls es hacer algo que sea correcto.

Answer 2

Sí, su ingenuo factorial no será recursivo, y usará 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 no recursivos de la cola en los recursivos de la cola. Su propósito es permitir que los ciclos de funciones mutuamente llamadas cola se ejecuten 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, lo que permite que la persona que llama utilice el cuadro de pila del método de llamada. Lo hace esencialmente mediante la conversión de una llamada recursiva de forma demostrable a un bucle while, debajo de las coberturas. 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 del llamante. Esto significa que si tiene dos o más métodos que se llaman entre sí en la posición de cola, no se realizará ninguna optimización y se correrá el riesgo de desbordamiento de la pila. scala.util.control.TailCalls es un truco que le permite solucionar este problema.

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