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

Question

¿Por qué el compilador de Scala no aplica 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: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden

¿Qué es exactamente saldría mal si el compilador aplica TCO en un caso como éste?

Answer 1

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 de 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 se puede esperar de esta última llamada? Usted podría estar esperando 240. Pero no:

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

Eso es porque cuando el método de la superclase hace una llamada recursiva, la llamada recursiva pasa a través de la subclase.

Si la anulación funcionaba de forma tal que 240 era la respuesta correcta, entonces sería seguro realizar una 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.

Answer 2

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

El compilador le está diciendo que la semántica permiten baz::fact() para ser una envoltura, que MAYO llamada ascendente (?) foo::fact() si quiere. En tal escenario, la regla es que foo::fact(), cuando se repita, debe activar baz::fact() en lugar de foo::fact() y, aunque foo::fact() es recursivo de cola, baz::fact() puede no serlo. 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.

Answer 3

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. Sin embargo, 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 era recursiva de cola, le imprima {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 finales en métodos no finales, el compilador inserta una llamada real en su lugar.

Answer 4

What exactly would go wrong if the compiler applied TCO in a case such as this?

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 #.