Почему в Java вообще нет оптимизации для хвостовой рекурсии?

92

Из того, что я прочитал: причина в том, что нелегко определить, какой метод на самом деле будет вызываться, поскольку у нас есть наследование.

Однако почему в Java, по крайней мере, нет оптимизации хвостовой рекурсии для статических методов и не реализован надлежащий способ вызова статических методов с помощью компилятора?

Почему Java вообще не поддерживает хвостовую рекурсию?

Я не уверен, есть ли здесь какие-либо трудности.

Что касается предложенного дубликата , как объяснил Йорг Миттаг 1 :

  • Другой вопрос спрашивает о TCO, этот о TRE. TRE намного проще, чем TCO.
  • Кроме того, другой вопрос задает вопрос о том, какие ограничения накладывает JVM на языковые реализации, которые хотят компилировать в JVM, этот вопрос задается о Java, который является единственным языком, который не ограничен JVM, поскольку спецификация JVM может быть изменена с помощью те же люди, которые проектируют Java.
  • И, наконец, в JVM нет даже ограничений на TRE, потому что у JVM есть GOTO внутри метода, и это все, что нужно для TRE.

1 Добавлено форматирование, чтобы вызвать сделанные пункты.

java compiler recursion InformedA
источник
26
Цитируя Эрика Липперта : «Функции недешевы; они чрезвычайно дороги, и они должны не только оправдывать свои собственные затраты, они должны оправдывать альтернативные издержки, связанные с отсутствием сотен других функций, которые мы могли бы сделать с этим бюджетом». Java была отчасти разработана для привлечения разработчиков на C / C ++, и оптимизация хвостовой рекурсии не гарантируется на этих языках.
Доваль
5
Поправьте меня, если я ошибаюсь, но является ли Эрик Липперт разработчиком C # с оптимизацией хвостовой рекурсии?
InformedA
1
Он в команде компилятора C #, да.
Доваль
10
Из того, что я понимаю, JIT может сделать это , если , возможно , будут выполнены определенные условия . Таким образом, на практике вы не можете положиться на это. Но то, имеет ли это C # или нет, не имеет значения для Эрика.
Доваль
4
@InstructedA Если вы покопаетесь немного глубже, вы увидите, что это никогда не делается в 32-битном JIT-компиляторе. 64-битный JIT новее и умнее во многих отношениях. Еще более новый экспериментальный компилятор (как для 32-разрядных, так и для 64-разрядных) еще умнее и будет поддерживать оптимизацию хвостовой рекурсии в IL, которая явно не запрашивает его. Есть еще один момент, который вы должны принять во внимание - у JIT-компиляторов не так много времени. Они сильно оптимизированы для скорости - приложение, для компиляции которого в C ++ может потребоваться несколько часов, все равно должно будет перейти от IL к нативному в течение максимум пары сотен мс (по крайней мере, частично).
Luaan

Ответы:

132

Как объясняет Брайан Гетц (Java Language Architect в Oracle) в этом видео :

в классах jdk [...] есть ряд чувствительных к безопасности методов, которые полагаются на подсчет кадров стека между кодом библиотеки jdk и кодом вызова, чтобы выяснить, кто их вызывает.

Все, что изменило количество кадров в стеке, сломало бы это и вызвало бы ошибку. Он признает, что это глупая причина, и поэтому разработчики JDK заменили этот механизм.

Затем он упоминает, что это не приоритет, а хвостовая рекурсия.

в конечном итоге будет сделано.

NB Это относится к HotSpot и OpenJDK, другие виртуальные машины могут отличаться.

ggovan
источник
7
Я поражен, что есть такой довольно резкий ответ, как этот! Но это действительно кажется ответом - это возможно сейчас, по устаревшим техническим причинам это еще не было сделано, и поэтому сейчас мы просто ждем, пока кто-то решит, что это достаточно важно для реализации.
BrianH
1
Почему бы не реализовать обходной путь? Как скрытый ярлык-goto, который просто переходит на вершину вызова метода с новыми значениями для аргументов? Это будет оптимизация во время компиляции и не потребует смещения кадров стека или нарушения безопасности.
Джеймс Уоткинс
2
Для нас будет намного лучше, если вы или кто-то еще здесь сможете глубже вникнуть и конкретно указать, что это за «чувствительные к безопасности методы». Спасибо!
InformedA
3
@InstructedA - см securingjava.com/chapter-three/chapter-three-6.html , который содержит подробное описание того , как система менеджер Java Security работал около выхода Java 2.
Жюль
3
Один из способов - использовать другой язык JVM. Например, Scala делает это в компиляторе, а не во время выполнения.
Джеймс Мур
24

В Java нет оптимизации хвостового вызова по той же причине, что и в большинстве императивных языков ее нет. Императивные циклы являются предпочтительным стилем языка, и программист может заменить хвостовую рекурсию императивными циклами. Сложность не стоит того, чтобы использовать функцию, которая не рекомендуется из-за стиля.

Эта вещь, когда программисты хотят иногда писать в стиле FP на других императивных языках, вошла в моду только в последние 10 лет или около того, после того, как компьютеры начали масштабировать ядра вместо ГГц. Даже сейчас это не так популярно. Если бы я предложил заменить императивный цикл на хвостовую рекурсию на работе, половина обозревателей кода рассмеялась бы, а другая половина смутно посмотрела бы. Даже в функциональном программировании вы обычно избегаете хвостовой рекурсии, если другие конструкции, такие как функции высшего порядка, не подходят точно.

Карл Билефельдт
источник
36
Этот ответ не кажется правильным. Тот факт, что рекурсия хвоста не является строго необходимой, не означает, что она не будет полезна. Рекурсивные решения часто легче понять, чем итерацию, но отсутствие хвостовых вызовов означает, что рекурсивные алгоритмы становятся некорректными для больших размеров задач, которые могут разрушить стек. Речь идет о правильности, а не производительности (скорость торговли для простоты часто того стоит). Как отмечается в правильном ответе, отсутствие хвостовых вызовов происходит из-за странной модели безопасности, основанной на следах стека, а не из-за императивного фанатизма.
Амон
4
@amon Джеймс Гослинг однажды сказал, что не добавит функцию в Java, если ее не попросят несколько человек , и только тогда он рассмотрит ее. Поэтому я не удивлюсь, если часть ответа на самом деле будет «вы всегда можете использовать forцикл» (и аналогично для первоклассных функций против объектов). Я бы не стал так называть это «императивным фанатизмом», но я не думаю, что он был бы очень востребован еще в 1995 году, когда главной заботой, вероятно, была скорость Java и отсутствие обобщений.
Доваль
7
@amon, модель безопасности кажется мне законной причиной не добавлять TCO к ранее существовавшему языку, но плохой причиной, чтобы вообще не переводить ее в язык. Вы не выбрасываете главную видимую программисту функцию, чтобы включить небольшую закулисную функцию. «Почему в Java 8 нет TCO» - это совсем другой вопрос, чем «Почему в Java 1.0 нет TCO?» Я отвечал на последнее.
Карл Билефельдт
3
@ rwong, вы можете преобразовать любую рекурсивную функцию в итеративную. (Если можно, я написал пример здесь )
Алена
3
@ZanLynx это зависит от типа проблемы. Например, шаблон посетителя может извлечь выгоду из TCO (в зависимости от особенностей структуры и посетителя), не имея ничего общего с FP. Прохождение конечных автоматов аналогично, хотя трансформация с использованием батутов кажется немного более естественной (в зависимости от проблемы). Кроме того, хотя технически вы можете реализовать деревья с помощью циклов, я считаю, что единодушным является то, что рекурсия гораздо более естественна (аналогично для DFS, хотя в этом случае вы можете избежать рекурсии из-за ограничений стека даже при использовании TCO).
Мацей Пехотка
5

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

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

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

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

Василий Старынкевич
источник
17
Вопрос не в хвостовых рекурсиях, а в хвостовой рекурсии. И вопрос не в языке байт-кода JVM, а в языке программирования Java, который является совершенно другим языком. Scala компилируется в байт-код JVM (среди прочего) и устраняет хвостовую рекурсию. Реализации схемы на JVM имеют полные правильные Tail-Calls. Java 7 (JVM Spec, 3-е изд.) Добавило новый байт-код. IBM J9 JVM выполняет TCO, даже не требуя специального байт-кода.
Йорг Миттаг
1
@ JörgWMittag: Это правда, но потом, мне интересно, правда ли, что язык программирования Java не имеет правильных хвостовых вызовов. Возможно, было бы точнее заявить, что язык программирования Java не должен иметь надлежащих вызовов tail, поскольку в спецификации ничего этого не требуется. (То есть: я не уверен, что что-то в спецификации на самом деле запрещает реализации устранять хвостовые вызовы. Это просто не упоминается.)
ruakh
4

Если язык не имеет специального синтаксиса для выполнения хвостового вызова (рекурсивного или иного) и компилятор будет кричать, когда хвостовой вызов запрашивается, но не может быть сгенерирован, «дополнительная» хвостовая вызов или оптимизация хвостовой рекурсии приведут к ситуациям, когда кусок кода может потребовать менее 100 байт стека на одном компьютере, но более 100 000 000 байт стека на другом. Такое различение следует считать качественным, а не просто количественным.

Ожидается, что машины могут иметь разные размеры стеков, и поэтому всегда возможно, чтобы код работал на одной машине, но перебил стек на другой. Как правило, однако, код, который будет работать на одной машине, даже когда стек искусственно сужен, вероятно, будет работать на всех машинах с «нормальными» размерами стека. Однако, если метод, который рекурсивно использует глубину 1 000 000, оптимизирован с помощью хвостового вызова на одной машине, но не на другой, выполнение на первой машине, вероятно, будет работать, даже если его стек необычно мал, и завершится неудачей на последней, даже если его стек необычно большой ,

Supercat
источник
2

Я думаю, что рекурсия хвостового вызова не используется в Java в основном потому, что это может изменить трассировку стека и, следовательно, значительно усложнит отладку программы. Я думаю, что одна из основных целей Java - дать возможность программистам легко отлаживать свой код, и для этого требуется трассировка стека, особенно в среде объектно-ориентированного программирования. Поскольку вместо этого можно было использовать итерацию, языковой комитет решил, что не стоит добавлять хвостовую рекурсию.

annoying_squid
источник