Что аннотация Scala должна гарантировать, что рекурсивная функция хвоста оптимизирована?
Я думаю, что существует @tailrec аннотация для обеспечения компилятора оптимизирует рекурсивную функцию хвоста. Вы просто помещаете его перед объявлением? Это также работает, если Scala используется в сценариях режима (например, использующий :load <file> под REPL)?
3 ответа
Из сообщения блога « 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 = {
^
Компилятор Scala автоматически оптимизирует любой действительно хвосторекурсивный метод. Если вы аннотируете метод, который, по вашему мнению, является хвосторекурсивным, с помощью аннотации @tailrec , то компилятор предупредит вас, если метод на самом деле не хвосторекурсивный. Это делает аннотацию @tailrec хорошей идеей, как для обеспечения возможности оптимизации метода в данный момент, так и для его сохранения при изменении.
Обратите внимание, что Scala не считает метод хвостовым рекурсивным, если его можно переопределить. Таким образом, метод должен быть закрытым, окончательным, для объекта (в отличие от класса или признака) или внутри другого метода, который нужно оптимизировать.
Аннотация 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 {
^
Ой! Последний вызов - 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 автоматически является закрытым, потому что он определен в области действия другого метода.