Что такое аннотация Scala для обеспечения оптимизации рекурсивной функции хвоста?

Ответ 1

Из Tail calls, @tailrec и trampolines" сообщение в блоге:

• В Scala 2.8 вы также сможете использовать новую аннотацию @tailrec, чтобы получить информацию о том, какие методы оптимизированы.
  Эта аннотация позволяет отмечать определенные методы, которые, как вы надеетесь, оптимизируют компилятор.
  Затем вы получите предупреждение, если они не будут оптимизированы компилятором.
• В Scala 2.7 или более ранней версии вам нужно будет полагаться на ручное тестирование или проверку байт-кода, чтобы определить, был ли оптимизирован метод.

Пример:

вы можете добавить аннотацию @tailrec, чтобы вы могли быть уверены, что ваши изменения сработали.

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

И он работает с REPL (пример из 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 = {
                    ^

Ответ 2

Компилятор Scala автоматически оптимизирует любой по-настоящему хвостовой рекурсивный метод. Если вы комментируете метод, который, по вашему мнению, является хвост-рекурсивным с аннотацией @tailrec, тогда компилятор предупредит вас, если метод на самом деле не является хвостовым рекурсивным. Это делает примечание @tailrec хорошей идеей, как для обеспечения того, что метод в настоящее время оптимизируется, так и для того, чтобы он был оптимизирован по мере его изменения.

Обратите внимание, что Scala не считает метод хвостовым рекурсивным, если он может быть переопределен. Таким образом, этот метод должен быть либо частным, и конечным, на объекте (в отличие от класса или признака), либо внутри другого метода, который должен быть оптимизирован.

Ответ 3

Аннотация scala.annotation.tailrec. Он вызывает ошибку компилятора, если метод не может быть оптимизирован хвостовым вызовом, что происходит, если:

• Рекурсивный вызов не находится в положении хвоста
• Метод можно переопределить
• Метод не является окончательным (особый случай предыдущего)

Он помещается непосредственно перед def в определении метода. Он работает в REPL.

Здесь мы импортируем аннотацию и попытаемся отметить метод как @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! Последний вызов 1.+(), а не length()! Переформулируем метод:

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

Обратите внимание, что length0 является автоматически приватным, потому что он определен в области другого метода.