Какие ограничения накладывает JVM на оптимизацию хвостового вызова

36

Clojure не выполняет оптимизацию хвостового вызова самостоятельно: если у вас есть хвостовая рекурсивная функция и вы хотите оптимизировать ее, вы должны использовать специальную форму recur. Точно так же, если у вас есть две взаимно рекурсивные функции, вы можете оптимизировать их только с помощью trampoline.

Компилятор Scala может выполнять TCO для рекурсивной функции, но не для двух взаимно рекурсивных функций.

Всякий раз, когда я читал об этих ограничениях, они всегда приписывались некоторым ограничениям, свойственным модели JVM. Я почти ничего не знаю о компиляторах, но это меня немного озадачивает. Позвольте мне взять пример с Programming Scala. Здесь функция

def approximate(guess: Double): Double =
  if (isGoodEnough(guess)) guess
  else approximate(improve(guess))

переводится на

0: aload_0
1: astore_3
2: aload_0
3: dload_1
4: invokevirtual #24; //Method isGoodEnough:(D)Z
7: ifeq
10: dload_1
11: dreturn
12: aload_0
13: dload_1
14: invokevirtual #27; //Method improve:(D)D
17: dstore_1
18: goto 2

Итак, на уровне байт-кода нужно просто goto. В этом случае, фактически, тяжелая работа выполняется компилятором.

Какие средства базовой виртуальной машины позволят компилятору легче обрабатывать TCO?

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

Andrea
источник

Ответы:

25

Я мало что знаю о Clojure и немного о Scala, но я попробую.

Прежде всего, мы должны различать tail-CALLS и tail-RECURSION. Хвостовая рекурсия действительно довольно легко преобразовать в цикл. С хвостовыми вызовами в общем случае гораздо сложнее или даже невозможнее. Вам нужно знать, что вызывается, но с полиморфизмом и / или первоклассными функциями вы редко это знаете, поэтому компилятор не может знать, как заменить вызов. Только во время выполнения вы знаете целевой код и можете переходить туда без выделения другого кадра стека. Например, следующий фрагмент имеет хвостовой вызов и не требует никакого стекового пространства при правильной оптимизации (включая TCO), но его нельзя устранить при компиляции для JVM:

function forward(obj: Callable<int, int>, arg: int) =
    let arg1 <- arg + 1 in obj.call(arg1)

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

Какие средства базовой виртуальной машины позволят компилятору легче обрабатывать TCO?

Инструкция хвостового вызова, такая как в Lua 5.1 VM. Ваш пример не становится намного проще. Мой становится примерно таким:

push arg
push 1
add
load obj
tailcall Callable.call
// implicit return; stack frame was recycled

Как примечание, я не ожидал бы, что реальные машины будут намного умнее, чем JVM.

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


источник
Понимаю. Я не осознавал, что, будучи менее умным, можно допустить оптимизацию, которая иначе была бы запрещена.
Андреа
7
+1, tailcallинструкция для JVM уже была предложена еще в 2007 году: блог на sun.com через механизм обратного хода . После поглощения Oracle, эта ссылка 404-х годов. Я предполагаю, что это не попало в список приоритетов JVM 7.
К.Стефф
1
tailcallИнструкция будет означать только хвост вызов , как хвост вызов. Вопрос: действительно ли JVM оптимизировала этот хвостовой вызов - это совершенно другой вопрос. CLI CIL имеет .tailпрефикс инструкции, но 64-битный CLR Microsoft долгое время не оптимизировал его. Ото, то IBM J9 JVM делает обнаружение хвостовых вызовов и оптимизирует их, без необходимости специальной инструкции , чтобы указать, какие вызовы хвостовых вызовов. Аннотирование оконечных вызовов и оптимизация оконечных вызовов действительно ортогональны. (Помимо того факта, что статическое определение того, какой вызов является хвостовым, может быть или не быть неразрешимым. Не знаю.)
Йорг W Mittag
@ JörgWMittag Вы можете сказать, что JVM может легко обнаружить шаблон call something; oreturn. Основная работа JVM SPEC обновления будет не вводить явное указание хвостового вызова но мандат , что такое распоряжение оптимизировано. Такая инструкция только облегчает работу авторов компилятора: автору JVM не нужно обязательно распознавать эту последовательность команд, прежде чем она искажена до неузнаваемости, а компилятор байт-кода X-> может быть уверен, что их байт-код либо недействителен, либо на самом деле оптимизированный, никогда не корректный, но переполняющий стек.
@delnan: последовательность call something; return;будет эквивалентна только хвостовому вызову, если вызываемая вещь никогда не запрашивает трассировку стека; если рассматриваемый метод является виртуальным или вызывает виртуальный метод, JVM не будет иметь возможности узнать, может ли он запросить информацию о стеке.
Суперкат
12

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

Это было на самом деле дизайнерское решение не делать этого - вы должны явно использовать recurспециальную форму, если вы хотите эту функцию. Смотрите почтовую ветку Re: Почему нет оптимизации хвостового вызова в группе Google Clojure.

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

В будущем итерация JVM, скорее всего, получит эту возможность, хотя, возможно, в качестве опции, чтобы обеспечить обратную совместимость поведения для старого кода. Скажем, в « Предварительном просмотре возможностей» в Geeknizer это указано для Java 9:

Добавление хвостовых вызовов и продолжений ...

Конечно, будущие дорожные карты всегда подвержены изменениям.

Оказывается, это не так уж и важно. За более чем 2 года программирования Clojure я никогда не сталкивался с ситуацией, когда нехватка TCO была проблемой. Основными причинами этого являются:

  • Вы уже можете получить быструю хвостовую рекурсию для 99% общих случаев с помощью recurили цикла. Случай взаимной рекурсии довольно редок в нормальном коде
  • Даже когда вам нужна взаимная рекурсия, часто глубина рекурсии достаточно мала, чтобы вы могли в любом случае сделать это в стеке без TCO. ТШО - это всего лишь «оптимизация»…
  • В очень редких случаях, когда вам нужна некоторая форма не требующей стека взаимной рекурсии, существует множество других альтернатив, которые могут достичь той же цели: ленивые последовательности, батуты и т. Д.
mikera
источник
«будущая итерация» - Предварительный просмотр функций в Geeknizer говорит о Java 9: добавление хвостовых вызовов и продолжений - так ли это?
комнат
1
Да, вот и все. Конечно, будущие дорожные карты всегда могут быть изменены ....
Микера
5

Как примечание, я не ожидал бы, что реальные машины будут намного умнее, чем JVM.

Дело не в том, чтобы быть умнее, а в том, чтобы быть другим. До недавнего времени JVM была разработана и оптимизирована исключительно для одного языка (очевидно, Java), который имеет очень строгую память и модели вызова.

Не только не было никаких gotoуказателей, но и не было никакого способа вызвать «голую» функцию (такую, которая не была определена в классе).

Концептуально, при нацеливании на JVM, автор компилятора должен спросить: «Как я могу выразить эту концепцию в терминах Java?». И, очевидно, нет способа выразить TCO в Java.

Обратите внимание, что это не рассматривается как сбой JVM, потому что они не нужны для Java. Как только Java понадобится такая функция, она добавляется в JVM.

Только недавно власти Java начали серьезно относиться к JVM как к платформе для не-Java языков, поэтому он уже получил некоторую поддержку функций, которые не имеют эквивалента Java. Самым известным является динамическая типизация, которая уже есть в JVM, но не в Java.

Хавьер
источник
3

Итак, на уровне байт-кода нужно просто перейти. В этом случае, фактически, тяжелая работа выполняется компилятором.

Вы заметили, что адрес метода начинается с 0? Что все методы ofsets начинаются с 0? JVM не позволяет прыгать вне метода.

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

Проблема, конечно, заключается в том, что вы не можете гарантировать, где будут находиться другие методы того же класса, а тем более методы других классов. Я сомневаюсь, что JVM дает какие-либо гарантии относительно того, куда он будет загружать методы, хотя я был бы рад исправить это.

Даниэль С. Собрал
источник
Хорошая точка зрения. Но для того, чтобы оптимизировать саморекурсивную функцию с помощью хвостового вызова, все, что вам нужно, это GOTO в рамках того же метода . Таким образом, это ограничение не исключает совокупную стоимость саморекурсивных методов.
Алекс Д