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 может быть лень, но это другая проблема).
tailcall
инструкция для JVM уже была предложена еще в 2007 году: блог на sun.com через механизм обратного хода . После поглощения Oracle, эта ссылка 404-х годов. Я предполагаю, что это не попало в список приоритетов JVM 7.tailcall
Инструкция будет означать только хвост вызов , как хвост вызов. Вопрос: действительно ли JVM оптимизировала этот хвостовой вызов - это совершенно другой вопрос. CLI CIL имеет.tail
префикс инструкции, но 64-битный CLR Microsoft долгое время не оптимизировал его. Ото, то IBM J9 JVM делает обнаружение хвостовых вызовов и оптимизирует их, без необходимости специальной инструкции , чтобы указать, какие вызовы хвостовых вызовов. Аннотирование оконечных вызовов и оптимизация оконечных вызовов действительно ортогональны. (Помимо того факта, что статическое определение того, какой вызов является хвостовым, может быть или не быть неразрешимым. Не знаю.)call something; oreturn
. Основная работа JVM SPEC обновления будет не вводить явное указание хвостового вызова но мандат , что такое распоряжение оптимизировано. Такая инструкция только облегчает работу авторов компилятора: автору JVM не нужно обязательно распознавать эту последовательность команд, прежде чем она искажена до неузнаваемости, а компилятор байт-кода X-> может быть уверен, что их байт-код либо недействителен, либо на самом деле оптимизированный, никогда не корректный, но переполняющий стек.call something; return;
будет эквивалентна только хвостовому вызову, если вызываемая вещь никогда не запрашивает трассировку стека; если рассматриваемый метод является виртуальным или вызывает виртуальный метод, JVM не будет иметь возможности узнать, может ли он запросить информацию о стеке.Clojure может выполнять автоматическую оптимизацию хвостовой рекурсии в циклы: это, безусловно, возможно сделать на JVM, как доказывает Scala.
Это было на самом деле дизайнерское решение не делать этого - вы должны явно использовать
recur
специальную форму, если вы хотите эту функцию. Смотрите почтовую ветку Re: Почему нет оптимизации хвостового вызова в группе Google Clojure.На текущей JVM единственное, что невозможно сделать, - это оптимизация хвостового вызова между различными функциями (взаимная рекурсия). Это не особенно сложно реализовать (другие языки, такие как Scheme, имели эту функцию с самого начала), но для этого потребуются изменения в спецификации JVM. Например, вам нужно изменить правила сохранения полного стека вызовов функций.
В будущем итерация JVM, скорее всего, получит эту возможность, хотя, возможно, в качестве опции, чтобы обеспечить обратную совместимость поведения для старого кода. Скажем, в « Предварительном просмотре возможностей» в Geeknizer это указано для Java 9:
Конечно, будущие дорожные карты всегда подвержены изменениям.
Оказывается, это не так уж и важно. За более чем 2 года программирования Clojure я никогда не сталкивался с ситуацией, когда нехватка TCO была проблемой. Основными причинами этого являются:
recur
или цикла. Случай взаимной рекурсии довольно редок в нормальном кодеисточник
Дело не в том, чтобы быть умнее, а в том, чтобы быть другим. До недавнего времени JVM была разработана и оптимизирована исключительно для одного языка (очевидно, Java), который имеет очень строгую память и модели вызова.
Не только не было никаких
goto
указателей, но и не было никакого способа вызвать «голую» функцию (такую, которая не была определена в классе).Концептуально, при нацеливании на JVM, автор компилятора должен спросить: «Как я могу выразить эту концепцию в терминах Java?». И, очевидно, нет способа выразить TCO в Java.
Обратите внимание, что это не рассматривается как сбой JVM, потому что они не нужны для Java. Как только Java понадобится такая функция, она добавляется в JVM.
Только недавно власти Java начали серьезно относиться к JVM как к платформе для не-Java языков, поэтому он уже получил некоторую поддержку функций, которые не имеют эквивалента Java. Самым известным является динамическая типизация, которая уже есть в JVM, но не в Java.
источник
Вы заметили, что адрес метода начинается с 0? Что все методы ofsets начинаются с 0? JVM не позволяет прыгать вне метода.
Я понятия не имею, что произойдет с веткой со смещением вне метода, который был загружен Java - возможно, он будет перехвачен верификатором байт-кода, может быть, он сгенерирует исключение, и, возможно, он действительно выйдет за пределы метода.
Проблема, конечно, заключается в том, что вы не можете гарантировать, где будут находиться другие методы того же класса, а тем более методы других классов. Я сомневаюсь, что JVM дает какие-либо гарантии относительно того, куда он будет загружать методы, хотя я был бы рад исправить это.
источник