Предотвращает ли JVM оптимизацию хвостовых вызовов? - PullRequest
98 голосов
/ 20 сентября 2008

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

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

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

Ответы [ 5 ]

74 голосов
/ 20 сентября 2008

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

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

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

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

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

27 голосов
/ 06 ноября 2008

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

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

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

21 голосов
/ 19 июня 2009

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

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

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

8 голосов
/ 20 сентября 2008

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

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

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

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

0 голосов
/ 01 декабря 2010

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

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

...