Использование рекурсии в Scala при запуске в JVM - PullRequest
Новая
       38

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

11 голосов
/ 18 апреля 2011

При поиске в других местах на этом сайте и в Интернете JVM не поддерживает оптимизацию хвостовых вызовов.Значит ли это, что хвостовой рекурсивный код Scala, такой как следующий, который может выполняться в очень больших входных списках, не должен быть написан, если он должен работать на JVM? 

// Get the nth element in a list    
def nth[T](n : Int, list : List[T]) : T = list match {
            case Nil => throw new IllegalArgumentException
            case _ if n == 0 => throw new IllegalArgumentException
            case _ :: tail if n == 1 => list.head
            case _ :: tail  => nth(n - 1, tail)
}

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

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

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

Спасибо!

Ответы [ 5 ]

22 голосов
/ 18 апреля 2011

Поскольку прямая хвостовая рекурсия эквивалентна циклу 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!)

19 голосов
/ 18 апреля 2011

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

Кто-нибудь может объяснить, что означают эти два средних предложения этого параграфа?

Хвостовая рекурсия является частным случаем хвостового вызова. Прямая рекурсия хвоста является частным случаем рекурсии хвоста. Только прямая хвостовая рекурсия гарантированно оптимизируется. Другие также могут быть оптимизированы , но это в основном просто оптимизация компилятора. Как языковая функция , Scala гарантирует только прямое устранение хвостовой рекурсии.

Так в чем же разница?

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

def a = {
  b
  c
}

В этом случае вызов на c является завершающим вызовом, вызов на b - нет.

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

def a = {
  b
}

def b = {
  a
}

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

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

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

def a = {
  b
  a
}

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

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

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

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

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

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

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

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

3 голосов
/ 18 апреля 2011

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

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

2 голосов
/ 18 апреля 2011

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

2 голосов
/ 18 апреля 2011

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

...