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

98

Я думаю, что есть @tailrecаннотация, чтобы компилятор оптимизировал хвостовую рекурсивную функцию. Вы просто ставите это перед декларацией? Работает ли он также, если Scala используется в режиме сценариев (например, с использованием :load <file>REPL)?

Huynhjl
источник

Ответы:

119

Из записи блога « Звонки хвоста, @tailrec и батуты »:

  • В 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 = {
                    ^
VonC
источник
44

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

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

Дэйв Гриффит
источник
8
Я полагаю, что это что-то вроде overrideаннотации в Java - код работает и без нее, но если вы поместите его туда, он сообщит вам, если вы сделали ошибку.
Zoltán
23

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

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

Он помещается непосредственно перед 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 { 
                    ^

Ой! Последний призыв - 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это автоматически закрытый, потому что он определен в области действия другого метода.

ретроним
источник
2
Расширяя сказанное выше, Scala может оптимизировать хвостовые вызовы только для одного метода. Взаимно рекурсивные вызовы не будут оптимизированы.
Rich Dougherty
Я ненавижу быть придирчивым, но в вашем примере в случае Nil вы должны вернуть tally для функции правильной длины списка, иначе вы всегда получите 0 в качестве возвращаемого значения, когда рекурсия завершится.
Lucian Enache