Обеспечивает ли JVM оптимизацию хвостовых вызовов?

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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