¿Por qué el compilador Scala no aplica la optimización de llamadas de cola a menos que un método sea definitivo?

tail-recursion tail-call-optimization

Question

¿Por qué el compilador Scala no aplica la optimización de llamadas de cola a menos que un método sea definitivo?

Por ejemplo, esto:

class C {
    @tailrec def fact(n: Int, result: Int): Int =
        if(n == 0)
            result
        else
            fact(n - 1, n * result)
}

resultados en

error: no se pudo optimizar el método anotado @tailrec: no es privado ni definitivo, por lo que se puede anular

¿Qué sería exactamente incorrecto si el compilador aplicara el TCO en un caso como este?

Answer 1

¿Qué sería exactamente incorrecto si el compilador aplicara el TCO en un caso como este?

Nada saldría mal. Cualquier idioma con la eliminación adecuada de la llamada de cola hará esto (SML, OCaml, F #, Haskell, etc.). La única razón por la que Scala no lo hace es que la JVM no admite la recursión de la cola y el truco habitual de Scala de reemplazar las llamadas auto-recursivas en la posición de la cola con goto no funciona en este caso. Scala en el CLR podría hacer esto como lo hace F #.

Answer 2

Considere la siguiente interacción con el REPL. Primero definimos una clase con un método factorial:

scala> class C {
         def fact(n: Int, result: Int): Int =
           if(n == 0) result
           else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

Ahora vamos a anularlo en una subclase para duplicar la respuesta de la superclase:

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

¿Qué resultado esperas para esta última convocatoria? Usted podría estar esperando 240. Pero no:

scala> (new C2).fact(5, 1)
res13: Int = 7680

Esto se debe a que cuando el método de la superclase hace una llamada recursiva, la llamada recursiva pasa por la subclase.

Si la anulación funcionó de modo que 240 fuera la respuesta correcta, entonces sería seguro que la optimización de la llamada de cola se realice en la superclase aquí. Pero no es así como funciona Scala (o Java).

A menos que un método esté marcado como final, es posible que no se llame a sí mismo cuando realiza una llamada recursiva.

Y es por eso que @tailrec no funciona a menos que un método sea definitivo (o privado).

ACTUALIZACIÓN: Recomiendo leer las otras dos respuestas (de John y Rex) también.

Answer 3

Deja que foo::fact(n, res) denote tu rutina. Deje que baz::fact(n, res) denote la anulación de su rutina por parte de otra persona.

El compilador le está diciendo que la semántica permite que baz::fact() sea ​​una envoltura, que PUEDE hacer una llamada ascendente (?) foo::fact() si así lo desea. Bajo tal escenario, la regla es que foo::fact() , cuando se repite, debe activar baz::fact() lugar de foo::fact() , y, mientras que foo::fact() es de tipo recursivo. , baz::fact() no puede ser. En ese punto, en lugar de hacer un bucle en la llamada recursiva de la cola, foo::fact() debe volver a baz::fact() , para que pueda desenrollarse.

Answer 4

Las llamadas recursivas pueden ser a una subclase en lugar de a una superclase; final lo impedirá. Pero, ¿por qué podrías querer ese comportamiento? La serie de Fibonacci no proporciona ninguna pista. Pero esto hace:

class Pretty {
  def recursivePrinter(a: Any): String = { a match {
    case xs: List[_] => xs.map(recursivePrinter).mkString("L[",",","]")
    case xs: Array[_] => xs.map(recursivePrinter).mkString("A[",",","]")
    case _ => a.toString
  }}
}
class Prettier extends Pretty {
  override def recursivePrinter(a: Any): String = { a match {
    case s: Set[_] => s.map(recursivePrinter).mkString("{",",","}")
    case _ => super.recursivePrinter(a)
  }}
}

scala> (new Prettier).recursivePrinter(Set(Set(0,1),1))
res8: String = {{0,1},1}

Si la llamada Bonita fuera de la cola recursiva, imprimiríamos {Set(0, 1),1} lugar, ya que la extensión no se aplicaría.

Dado que este tipo de recursión es plausiblemente útil, y se destruiría si se permitieran las llamadas de cola en métodos no finales, el compilador inserta una llamada real en su lugar.