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

Question

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

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

743 3

scala tail-call-optimization

3 ответов:

Comments

Ничего не найдено.

VonC · Accepted Answer · 2010-06-25 01:06:08

от "хвост звонки, @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 = {
                    ^

Dave Griffith · Accepted Answer · 2012-01-09 15:43:11

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

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

retronym · Accepted Answer · 2017-01-31 15:34:31

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

рекурсивный вызов не находится в хвостовой позиции

метод может быть overriden

метод не является окончательным (частный случай предыдущего)

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