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)?Co to jest adnotacja Scala, aby upewnić się, że funkcja rekursywna ogona jest zoptymalizowana?
Odpowiedz
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 = {
^
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.
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:
- rekurencyjne połączenie nie znajduje się w położeniu tylnego
- sposób może być nadpisane
- 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.
Rozszerzając powyższe słowa, Scala może optymalizować tylko wywołania ogona dla jednej metody. Wzajemnie rekurencyjne połączenia nie zostaną zoptymalizowane. –
Nienawidzę być głupim wybrednym, ale w twoim przykładzie w przypadku Nil powinieneś wrócić do poprawnej funkcji długości listy, w przeciwnym razie zawsze otrzymasz 0 jako wartość zwrotną, gdy rekursja się zakończy. –
Przypuszczam, że jest to trochę jak adnotacja 'override' w Javie - kod działa bez niego, ale jeśli ją umieścisz, to powie Ci, czy popełniłeś błąd. –