Предотвращает ли JVM оптимизацию хвостового вызова?

99

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

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

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

java jvm scala tail-recursion Джейсон Дагит
источник

Ответы:

74

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

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

Также более подробно обсуждается ошибка Sun # 4726340 , где оценка (от 2002 г.) заканчивается:

Я считаю, что это все-таки можно сделать, но это непростая задача.

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

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

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

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

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

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

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

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

Много информации о состоянии рекурсии Scala можно найти в блоге Рича Догерти .

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

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

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

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

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

фаран
источник
0

Все источники указывают на то, что JVM не может оптимизировать в случае хвостовой рекурсии, но после прочтения настройки производительности Java (2003, Орейли) я обнаружил, что автор утверждает, что он может достичь большей производительности рекурсии, реализовав хвостовую рекурсию.

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

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