Jaka jest adnotacja Scala, aby zapewnić optymalizację funkcji rekurencyjnej ogona?

98

Myślę, że istnieje @tailrecadnotacja zapewniająca, że ​​kompilator zoptymalizuje funkcję rekurencyjną ogona. Czy po prostu umieszczasz to przed deklaracją? Czy działa również, jeśli Scala jest używana w trybie skryptowym (na przykład przy użyciu :load <file>REPL)?

huynhjl
źródło

Odpowiedzi:

119

Z posta na blogu „ Tail wzywa, @tailrec i trampoliny ”:

  • W Scali 2.8 będzie można również skorzystać z nowej @tailrecadnotacji, aby uzyskać informacje o zoptymalizowanych metodach.
    Ta adnotacja pozwala oznaczyć określone metody, które, jak masz nadzieję, zoptymalizuje kompilator.
    Otrzymasz ostrzeżenie, jeśli nie zostaną zoptymalizowane przez kompilator.
  • W Scali 2.7 lub starszej będziesz musiał polegać na ręcznym testowaniu lub sprawdzeniu kodu bajtowego, aby sprawdzić, czy metoda została zoptymalizowana.

Przykład:

możesz dodać @tailrecadnotację, aby mieć pewność, że zmiany zadziałały.

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 ze wskazówek i trików 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 = {
                    ^
VonC
źródło
44

Kompilator Scala automatycznie zoptymalizuje każdą prawdziwie rekurencyjną metodę. Jeśli dodasz adnotację do metody, która Twoim zdaniem jest rekurencyjna z ogonem @tailrec, kompilator ostrzeże Cię, jeśli metoda faktycznie nie jest rekurencyjna. To sprawia, że @tailrecadnotacja jest dobrym pomysłem, zarówno po to, aby upewnić się, że metoda jest obecnie optymalizowana, jak i że pozostaje optymalna po zmodyfikowaniu.

Zauważ, że Scala nie uważa metody za rekurencyjną ogonową, jeśli można ją przesłonić. Dlatego metoda musi być albo prywatna, ostateczna, na obiekcie (w przeciwieństwie do klasy lub cechy), albo wewnątrz innej metody, która ma być zoptymalizowana.

Dave Griffith
źródło
8
Przypuszczam, że jest to trochę jak overrideadnotacja w Javie - kod działa bez niej, ale jeśli go tam umieścisz, powie ci, czy popełniłeś błąd.
Zoltán
23

Adnotacja jest scala.annotation.tailrec. Wywołuje błąd kompilatora, jeśli metoda nie może zostać zoptymalizowana pod kątem wywołań tail, co dzieje się, gdy:

  1. Wywołanie rekurencyjne nie znajduje się w końcowej pozycji
  2. Metoda może zostać zastąpiona
  3. Metoda nie jest ostateczna (szczególny przypadek poprzedniego)

Jest umieszczany tuż przed defdefinicją metody. Działa w REPL.

Tutaj importujemy adnotację i próbujemy 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! Ostatnie wezwanie brzmi 1.+(): nie length()! Sformułujmy ponownie metodę:

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 length0jest to automatycznie prywatne, ponieważ jest zdefiniowane w zakresie innej metody.

retronim
źródło
2
Rozszerzając to, co powiedziałeś powyżej, Scala może zoptymalizować wywołania końcowe tylko dla jednej metody. Wzajemnie rekurencyjne wywołania nie będą optymalizowane.
Rich Dougherty
Nienawidzę bycia najbardziej wybrednym, ale w twoim przykładzie w przypadku zerowym powinieneś zwrócić tally dla prawidłowej funkcji długości listy, w przeciwnym razie zawsze otrzymasz 0 jako wartość zwracaną po zakończeniu rekursji.
Lucian Enache