¿Por qué el comstackdor de Scala no aplicará la optimización de la cola de cola a menos que un método sea definitivo?

¿Por qué el comstackdor de Scala no aplicará la optimización de la cola 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 ni privado ni definitivo, por lo que se puede anular

¿Qué podría salir mal si el comstackdor aplicara el TCO en un caso como este?

Considere la siguiente interacción con 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 espera para esta última llamada? Es posible que esté 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 realiza una llamada recursiva, la llamada recursiva pasa por la subclase.

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

A menos que un método se marque 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 final (o privado).

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

Las llamadas recursivas pueden ser a una subclase en lugar de a una superclase; final evitará eso. Pero, ¿por qué querrías 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 Pretty fue recursiva de la cola, imprimiríamos {Set(0, 1),1} lugar, ya que la extensión no se aplicaría.

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

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

El comstackdor te dice que la semántica permite que baz::fact() sea ​​un contenedor, que PUEDE llamar al alza (?) foo::fact() si así lo desea. Bajo tal escenario, la regla es que foo::fact() , cuando se repita, debe activar baz::fact() lugar de foo::fact() , y, mientras que foo::fact() es recursivo de cola , baz::fact() no puede ser. En ese punto, en lugar de hacer un bucle en la llamada recursiva de cola, foo::fact() debe regresar a baz::fact() , para que pueda desenrollarse.

¿Qué podría salir mal si el comstackdor aplicara el TCO en un caso como este?

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