Co to jest adnotacja Scala, aby upewnić się, że funkcja rekursywna ogona jest zoptymalizowana?

Question

Myślę, że istnieje adnotacja @tailrec, aby kompilator optymalizował funkcję rekursywną ogona. Czy stawiasz to przed deklaracją? Czy działa również, jeśli Scala jest używana w trybie skryptowym (na przykład przy użyciu wersji :load <file> pod REPL)?

Answer 1

Z „Tail calls, @tailrec and trampolines” blogu:

• W Scala 2.8, to będą mogli korzystać z nowego @tailrec adnotacji, aby uzyskać informacje na temat metod, które są zoptymalizowane.
  Ta adnotacja umożliwia oznaczenie określonych metod, które mają nadzieję, że kompilator będzie optymalizowany.
  Otrzymasz ostrzeżenie, jeśli nie zostaną zoptymalizowane przez kompilator.
• W Scala 2.7 lub wcześniejszym, aby sprawdzić, czy metoda została zoptymalizowana, należy polegać na ręcznym testowaniu lub sprawdzaniu kodu bajtowego.

Przykład:

można dodać @tailrec adnotacji, dzięki czemu można mieć pewność, że zmiany zostały przepracowane.

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) 
    } 
} 

---

I działa z REPL (przykład z Scala REPL tips and tricks):

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

Kompilator Scala automatycznie zoptymalizuje każdą prawdziwie rekurencyjną metodę ogonowania. Jeśli dodasz adnotację do metody, która Twoim zdaniem jest rekursywna, z adnotacją @tailrec, kompilator ostrzeże Cię, jeśli ta metoda nie jest rekursywna. To sprawia, że ​​adnotacja @tailrec jest dobrym pomysłem, zarówno w celu zapewnienia, że ​​metoda jest obecnie optymalizowana i że pozostaje optymalizowana w miarę jej modyfikacji.

Należy zauważyć, że Scala nie uważa metody rekurencyjnej za ogon, jeśli można ją przesłonić. Zatem metoda musi być albo prywatna, końcowa, na obiekcie (w przeciwieństwie do klasy lub cechy), albo wewnątrz innej optymalizowanej metody.

Answer 3

Adnotacja jest scala.annotation.tailrec. To powoduje błąd kompilatora, jeśli sposób nie może być optymalne połączenie ogona, co dzieje się, gdy:

1. rekurencyjne połączenie nie znajduje się w położeniu tylnego
2. sposób może być nadpisane
3. Metoda nie jest końcowy (specjalny przypadek poprzedzający)

Znajduje się tuż przed def w definicji metody. Działa w REPL.

Tutaj importujemy adnotację i staramy się oznaczyć metodę jako @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 { 
        ^

Ups!Ostatnia inwokacja to 1.+(), a nie length()! Załóżmy przeformułować metody:

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 

Zauważ, że length0 jest automatycznie prywatny, ponieważ jest zdefiniowana w ramach innej metody.