Поддерживает ли Scala оптимизацию хвостовой рекурсии?
Поддерживает ли Scala оптимизацию хвостовой рекурсии?
4 ответа
Scala выполняет оптимизацию хвостовой рекурсии во время компиляции, как говорили другие авторы. То есть хвостовая рекурсивная функция преобразуется компилятором в цикл (вызов метода преобразуется в переход), как видно из трассировки стека при запуске хвостовой рекурсивной функции.
Попробуйте следующий фрагмент:
def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)
и осмотрите трассировку стека. Он покажет только один вызов функции boom - поэтому скомпилированный байт-код не является рекурсивным.
Существует предложение реализовать хвостовые вызовы на уровне JVM - что, на мой взгляд, было бы замечательно, так как тогда JVM могла бы выполнять оптимизацию во время выполнения, а не просто оптимизацию времени компиляции кода - и, возможно, означать больше гибкая хвостовая рекурсия. В основном tailcall invoke будет вести себя точно так же, как обычный метод invoke но удалит стек вызывающей стороны, когда это будет безопасно - спецификация JVM гласит, что кадры стека должны быть сохранены, поэтому JIT должен выполнить некоторый статический анализ кода, чтобы выяснить, будут ли кадры стека никогда не быть используемый.
Текущий статус этого прото 80%. Я не думаю, что это будет сделано вовремя для Java 7 (invokedynamic имеет больший приоритет, и реализация почти завершена), но Java 8 может увидеть его реализованным.
В Scala 2.8 вы можете использовать @tailrec чтобы отметить конкретный метод, который вы ожидаете, компилятор оптимизирует:
import scala.annotation.tailrec
@tailrec def factorialAcc(acc: Int, n: Int): Int = {
if (n <= 1) acc
else factorialAcc(n * acc, n - 1)
}
Если метод не может быть оптимизирован, вы получаете ошибку во время компиляции.
Scala 2.7.x поддерживает оптимизацию хвостового вызова для саморекурсии (вызывающей себя функции) конечных методов и локальных функций.
Scala 2.8 может также поставляться с библиотечной поддержкой батута, который является техникой для оптимизации взаимно рекурсивных функций.
Много информации о состоянии рекурсии Scala можно найти в блоге Рича Догерти.
Только в очень простых случаях, когда функция является саморекурсивной.
Доказательство способности рекурсии хвоста.
Похоже, что Scala 2.8 может улучшить распознавание хвостовой рекурсии.