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

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

88 голосов
/ 25 июня 2010

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

Ответы [ 3 ]

109 голосов
/ 25 июня 2010

Из сообщения блога " Tail, @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 = {
                    ^
36 голосов
/ 25 июня 2010

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

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

21 голосов
/ 25 июня 2010

Аннотация: 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 автоматически является частным, поскольку оно определено в области действия другого метода.

...