Вопрос по java, jvm – Предотвращает ли JVM оптимизацию хвостовых вызовов?

97

Я видел эту цитату на вопрос:Какой хороший функциональный язык для создания веб-службы?

Scala in particular doesn't support tail-call elimination except in self-recursive functions, which limits the kinds of composition you can do (this is a fundamental limitation of the JVM).

Это правда? Если да, то что в JVM создает это фундаментальное ограничение?

Ваш Ответ

5   ответов
72

Рекурсия или итерация? может помочь.

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

Существует также больше дискуссий вОшибка солнца # 4726340где заканчивается оценка (с 2002 года):

I believe this could be done nonetheless, but it is not a small task.

В настоящее время вДа Винчи Машина проект. Состояние подпроекта хвостового вызова указано как «proto 80%»; вряд ли он попадет в Java 7, но я думаю, что у Java 8 есть очень хорошие шансы.

Вы знаете, если в java8 это включено?
@JustinSheehy: что не так? Вопрос был таков: «Предотвращает ли JVM оптимизацию хвостовых вызовов?» И ответ: «Нет, но это сложно».
Я не совсем следовал объяснениям. Я думал, что оптимизация хвостового вызова была осуществлена компилятором. Предполагая, что у вас есть функция, которую компилятор может оптимизировать с помощью хвостового вызова, вы также можете иметь эквивалентную нерекурсивную функцию, которая реализует ту же функциональность с использованием цикла, верно? Если это так, компилятор не может этого сделать. Я не в состоянии следить за зависимостью от JVM. Как это соотносится с компилятором Scheme, который генерировал собственный код i386?
Это распространенное заблуждение и часто повторяемое оправдание, но оно неверно. В течение ряда лет было установлено, что безопасность путем проверки стека (и предоставления полезных трассировок стека) не является несовместимой с правильными вызовами хвоста. Например, см. Эту статью от 2004 года.citeseerx.ist.psu.edu/viewdoc/… Понижение, так как ответ неверный.
@Gautham: Мое утверждение об отладке было связано с использованием батутов в качестве обходного пути для устранения исключения хвостовых вызовов в JVM. Устранение вызовов в хвосте может и было реализовано в JVM (Арнольд Шайгофер делал это в OpenJDK, а также в LLVM), поэтому нет никаких сомнений относительно того, можно ли это сделать. CLR от Microsoft, конечно же, поддерживает устранение хвостовых вызовов в течение 10 лет, и выпуск F # продемонстрировал, что это изменит правила игры. Я думаю, что ответ заключается в том, что JVM давно застоялась.
27

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

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

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

Hence there is a very strong argument that Scala is not a real functional programming language  - аргумент на самом деле довольно слабый. Конечно, естьtail calls [as] an essential featureИ хорошо, если базовое оборудование (или виртуальная машина) поддерживает его напрямую. Но это детали реализации.
тем не менее, просто потому, что JVM (к сожалению, без вопросов) не может выполнять хвостовые вызовы, это не означает, что устранение хвостовых вызовов невозможно. Это так, как если бы кто-то заявил, что вычисления с плавающей запятой возможны только на компьютерах с FPU.
Можно быть защитником, скажем, F #. Но я уже давно (даже годы назад в usenet) отмечал вашу враждебность ко всему, что не является F #, и все же ваши разработки показывают, что вы не знаете, о чем говорите. Как здесь: ваш аргумент выглядит так, что язык, на котором я могу написать программу, которая прерывает работу с переполнением стека, не является функциональным? Но нельзя ли привести такой же аргумент для языков, где я могу спровоцировать переполнение кучи? Следовательно, сам святой F # не будет считаться функциональным.
@ Инго: только если вы не считаете, что переполнение стека в вашей программе во время выполнения рассматривается пользователем как серьезная проблема. Согласно его трекеру ошибок, даже сам компилятор Scala страдает от переполнения стека. Так что даже самые опытные разработчики Scala все еще ошибаются ...
@Ingo: Некоторые идиомы в функциональном программировании, такие как взаимная рекурсия и стиль передачи продолжения, могут потребовать устранения хвостового вызова для работы. Без этого ваши программы будут переполнены стеком. Если язык не может надежно выполнять идиоматический функциональный код, является ли он функциональным? Ответ, как вы говорите, - это суждение, но важное различие на практике. Мартин Тройер только что опубликовал интересную запись в блоге об этом:martinsprogrammingblog.blogspot.com/2011/11/…
0

что JVM не может оптимизироваться в случае хвостовой рекурсии, но после чтенияНастройка производительности Java (2003, O 'reilly) Я обнаружил, что автор утверждает, что он может добиться большей производительности рекурсии путем реализации хвостовой рекурсии.

Вы можете найти его заявку на странице 212 (поиск «хвостовой рекурсии»; это должен быть второй результат). Что дает?

IBM поддерживает некоторую форму TCO в своей реализации JVM (в качестве оптимизации, поэтому никаких гарантий). Возможно, авторы настройки производительности Java думали, что эта функция будет в конечном итоге реализована всеми JVM.ibm.com/developerworks/java/library/j-diag8.html
8

опубликованной в Lambda The Ultimate (из ссылки, опубликованной выше), Джон Роуз из Sun может сказать еще кое-что об оптимизации хвостового вызова.

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

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

http://openjdk.java.net/projects/mlvm/

21

и (вызывающей себя функции) конечных методов и локальных функций.

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

Много информации о состоянии рекурсии Scala можно найти вБлог Rich Dougherty.

@ om-nom-nom AFAIK, ничего не изменилось, ни на стороне Scala, ни на стороне JVM.
Не могли бы вы обновить вопрос о текущем статусе scala?

Похожие вопросы