Использование рекурсии в Scala при запуске в JVM

Ответ 1

Поскольку прямая хвостовая рекурсия эквивалентна циклу while, ваш пример будет эффективно работать на JVM, потому что компилятор Scala может скомпилировать это в цикле под капотом, просто используя прыжок. Однако общая поддержка TCO не поддерживается JVM, хотя имеется метод tailcall(), который поддерживает хвостовые вызовы с использованием батутов, созданных компилятором.

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

import scala.annotation.tailrec

@tailrec def nth[T](n : Int, list : List[T]) : Option[T] = list match {
            case Nil => None
            case _ if n == 0 => None
            case _ :: tail if n == 1 => list.headOption
            case _ :: tail  => nth(n - 1, tail)
}

(винт IllegalArgmentException!)

Ответ 2

В принципе, хвостовые вызовы всегда могут повторно использовать фрейм стека вызова   функция. Однако некоторые среды выполнения (например, виртуальная машина Java) не имеют   примитивы, чтобы сделать повторное использование фреймов стека для эффективного использования хвостовых вызовов. Качество продукции   Таким образом, реализация Scala необходима только для повторного использования кадра стека di   прямая хвосто-рекурсивная функция, последним действием которой является вызов самому себе. Другие хвостовые звонки могут   также оптимизироваться, но не следует полагаться на это во всех реализациях.

Может ли кто-нибудь объяснить, что означают эти средние два предложения этого абзаца?

Рекурсия хвоста является частным случаем хвостового вызова. Прямая хвостовая рекурсия - это особый случай рекурсии хвоста. Гарантируется оптимизация только прямой хвостовой рекурсии. Другие могут быть оптимизированы, но это в основном просто оптимизация компилятора. В качестве языковой функции Scala гарантирует только исключение прямой хвостовой рекурсии.

Итак, какая разница?

Ну, хвостовой вызов - это просто последний вызов в подпрограмме:

def a = {
  b
  c
}

В этом случае вызов c является хвостовым вызовом, вызов b не является.

Рекурсия хвоста - это когда хвостовой вызов вызывает подпрограмму, которая уже была вызвана раньше:

def a = {
  b
}

def b = {
  a
}

Это хвостовая рекурсия: a вызывает b (хвостовой вызов), который в свою очередь вызывает a снова. (В отличие от прямой хвостовой рекурсии, описанной ниже, это иногда называют косвенной хвостовой рекурсией.)

Однако ни один из этих двух примеров не будет оптимизирован Scala. Или, точнее: реализация Scala позволяет оптимизировать их, но это не требуется. Это в отличие от, например, Схема, где спецификация языка гарантирует, что все перечисленные выше случаи будут занимать пространство O(1).

Спецификация языка Scala гарантирует только оптимизацию прямой хвостовой рекурсии, т.е. когда подпрограмма напрямую вызывает себя без других вызовов между ними:

def a = {
  b
  a
}

В этом случае вызов a является хвостовым вызовом (поскольку он является последним вызовом в подпрограмме), это хвостовая рекурсия (потому что она снова вызывает себя) и, самое главное, это прямая хвостовая рекурсия, потому что a напрямую вызывает себя, не пропуская другого вызова.

Обратите внимание, что есть много тонких вещей, которые могут привести к тому, что метод не будет иметь прямую рекурсивность. Например, если a перегружен, то рекурсия может фактически проходить различные перегрузки и, следовательно, больше не будет прямой.

На практике это означает две вещи:

• вы не можете выполнить рефакторинг метода извлечения по хвостовому рекурсивному методу, по крайней мере, не включая хвостовой вызов, потому что это превратит прямой хвосто-рекурсивный метод (который будет оптимизирован) в косвенно-хвосторекурсивный метод (который не будет оптимизирован).
• Вы можете использовать только прямую рекурсию хвоста. Вывод хвостового рекурсивного парсера спуска или конечный автомат, который может быть очень элегантно выражен с помощью косвенной хвостовой рекурсии.

Основная причина этого заключается в том, что, когда ваш основной механизм выполнения не обладает мощными функциями управления потоком управления, такими как GOTO, продолжениями, первоклассным изменяемым стеком или правильными хвостовыми вызовами, тогда вам нужно либо реализовать свой собственный стек сверху из этого, использовать батуты, сделать глобальное преобразование CPS или что-то подобное противное, чтобы обеспечить обобщенные правильные хвостовые звонки. Все они оказывают либо серьезное влияние на производительность, либо совместимость с другим кодом на той же платформе.

Или, как сказал Рик Хикки, создатель Clojure, когда он столкнулся с одной и той же проблемой: "Производительность, Java-взаимодействие, хвостовые вызовы. Выберите два". Оба Clojure и Scala решили скомпрометировать хвостовые вызовы и предоставить только хвостовую рекурсию, а не полные хвостовые вызовы.

Короче говоря: да, конкретный пример, который вы опубликовали, будет оптимизирован, так как это прямая рекурсия хвоста. Вы можете проверить это, добавив аннотацию @tailrec к методу. Аннотации не изменяют, будет ли оптимизирован метод, однако он гарантирует, что вы получите ошибку компиляции, если метод не может быть оптимизирован.

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

Ответ 3

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

Конечно, ваш код должен быть оптимизирован для этого. Однако, если вы используете аннотацию @tailrec перед вашим методом (scala.annotation.tailrec), компилятор будет ЗАПРОСИТЬ, что метод может быть оптимизирован или не скомпилирован.

Ответ 4

В замечании Мартина говорится, что только прямые саморекурсивные вызовы являются кандидатами (другие критерии выполнены) для оптимизации TCO. Непрямые, взаимно рекурсивные пары методов (или более крупные наборы рекурсивных методов) не могут быть оптимизированы.

Ответ 5

Обратите внимание, что существуют JVM, которые поддерживают оптимизацию хвостовых вызовов (IIRC, IBM J9), это просто не требование в JLS, а реализация Oracle не делает этого.