programar - scala introduccion

¿Qué es la anotación de Scala para garantizar que se optimice la función recursiva de la cola?

Question

Creo que hay @tailrec anotación @tailrec para asegurar que el compilador optimice una función recursiva de cola. ¿Lo pones frente a la declaración? ¿Funciona también si se usa Scala en el modo de scripting (por ejemplo, usando :load <file> en REPL)?

Answer 1

De la publicación del blog " Tail calls, @tailrec and trampolines ":

• En Scala 2.8, también podrá usar la nueva anotación @tailrec para obtener información sobre qué métodos están optimizados.
  Esta anotación le permite marcar métodos específicos que espera que el compilador optimice.
  Luego recibirá una advertencia si el compilador no lo optimiza.
• En Scala 2.7 o anterior, deberá confiar en las pruebas manuales o la inspección del bytecode para determinar si un método se ha optimizado.

Ejemplo:

podría agregar una anotación @tailrec para que pueda estar seguro de que sus cambios han funcionado.

import scala.annotation.tailrec

class Factorial2 {
  def factorial(n: Int): Int = {
    @tailrec def factorialAcc(acc: Int, n: Int): Int = {
      if (n <= 1) acc
      else factorialAcc(n * acc, n - 1)
    }
    factorialAcc(1, n)
  }
}

Y funciona desde REPL (ejemplo de los consejos y trucos de Scala REPL ):

C:/Prog/Scala/tests>scala
Welcome to Scala version 2.8.0.RC5 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_18).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import scala.annotation.tailrec
import scala.annotation.tailrec

scala> class Tails {
     | @tailrec def boom(x: Int): Int = {
     | if (x == 0) throw new Exception("boom!")
     | else boom(x-1)+ 1
     | }
     | @tailrec def bang(x: Int): Int = {
     | if (x == 0) throw new Exception("bang!")
     | else bang(x-1)
     | }
     | }
<console>:9: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
       @tailrec def boom(x: Int): Int = {
                    ^
<console>:13: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden
       @tailrec def bang(x: Int): Int = {
                    ^

Answer 2

El compilador de Scala optimizará automáticamente cualquier método verdaderamente recursivo. Si anota un método que cree que es recursivo de cola con la anotación @tailrec , entonces el compilador le advertirá si el método realmente no es recursivo de cola. Esto hace que la anotación @tailrec una buena idea, tanto para garantizar que un método sea actualmente optimizable y que siga siendo optimizable a medida que se modifique.

Tenga en cuenta que Scala no considera que un método sea recursivo de cola si se puede anular. Por lo tanto, el método debe ser privado, final, en un objeto (a diferencia de una clase o rasgo), o dentro de otro método para ser optimizado.

Answer 3

La anotación es scala.annotation.tailrec . Desencadena un error de compilación si el método no puede ser optimizado, lo que ocurre si:

1. La llamada recursiva no está en la posición de cola
2. El método podría ser anulado
3. El método no es final (caso especial del anterior)

Se coloca justo antes de la def en una definición de método. Funciona en REPL.

Aquí importamos la anotación e intentamos marcar un método como @tailrec .

scala> import annotation.tailrec
import annotation.tailrec

scala> @tailrec def length(as: List[_]): Int = as match {  
     |   case Nil => 0
     |   case head :: tail => 1 + length(tail)
     | }
<console>:7: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
       @tailrec def length(as: List[_]): Int = as match { 
                    ^

Oops! La última invocación es 1.+() , No length() ! Vamos a reformular el método:

scala> def length(as: List[_]): Int = {                                
     |   @tailrec def length0(as: List[_], tally: Int = 0): Int = as match {
     |     case Nil          => tally                                       
     |     case head :: tail => length0(tail, tally + 1)                    
     |   }                                                                  
     |   length0(as)
     | }
length: (as: List[_])Int

Tenga en cuenta que length0 es automáticamente privado porque está definido en el alcance de otro método.