Каждый раз, когда обсуждается новый язык программирования для JVM, неизбежно появляются люди, которые говорят что-то вроде:
«JVM не поддерживает оптимизацию хвостового вызова, поэтому я предсказываю множество взрывающихся стеков»
Есть тысячи вариаций на эту тему.
Теперь я знаю, что некоторые языки, такие как Clojure, например, имеют специальную конструкцию recur, которую вы можете использовать.
Что я не понимаю, так это: насколько серьезным является отсутствие оптимизации хвостового вызова? Когда я должен беспокоиться об этом?
Мой основной источник путаницы, вероятно, связан с тем фактом, что Java является одним из самых успешных языков за всю историю, и довольно много языков JVM работают довольно хорошо. Как это возможно , если отсутствие TCO действительно из любой озабоченности?
источник
GOTO
, а у JVM нет. И x86 не используется в качестве платформы взаимодействия. У JVM нет,GOTO
и одной из основных причин выбора платформы Java является взаимодействие. Если вы хотите реализовать TCO на JVM, вы должны что- то сделать со стеком. Управляй им сам (т.е. вообще не используй стек вызовов JVM), используй батуты, используй исключения какGOTO
, что-то вроде этого. Во всех этих случаях вы становитесь несовместимыми со стеком вызовов JVM. Невозможно быть совместимым со стеком с Java, иметь TCO и высокую производительность. Вы должны пожертвовать одним из этих трех.Ответы:
Подумайте об этом, скажем, мы избавились от всех циклов в Java (авторы компиляторов бастуют или что-то в этом роде). Теперь мы хотим написать факториал, чтобы мы могли исправить что-то вроде этого
Теперь мы чувствуем себя довольно умно, нам удалось написать наш факториал даже без циклов! Но когда мы тестируем, мы замечаем, что при любом значении разумного размера мы получаем ошибки переполнения стека, поскольку TCO отсутствует.
В реальной Java это не проблема. Если у нас когда-либо есть хвостовой рекурсивный алгоритм, мы можем преобразовать его в цикл и все будет в порядке. Однако как насчет языков без петель? Тогда ты просто накрылся. Вот почему у clojure есть такая
recur
форма, без нее она даже не завершается (не существует бесконечных циклов).Класс функциональных языков, нацеленных на JVM, Frege, Kawa (Scheme), Clojure, всегда старается справиться с отсутствием хвостовых вызовов, потому что в этих языках TC является идиоматическим способом создания циклов! Если перевести на Схему, этот факториал выше будет хорошим факториалом. Было бы ужасно неудобно, если зацикливание 5000 раз приводило к краху вашей программы. Однако это можно обойти, используя
recur
специальные формы, аннотации, намекающие на оптимизацию собственных вызовов, прыжки на батуте, что угодно. Но все они вызывают либо снижение производительности, либо ненужную работу программиста.Теперь Java тоже не становится бесплатной, поскольку для TCO есть нечто большее, чем просто рекурсия, как насчет взаимно рекурсивных функций? Они не могут быть прямо переведены в циклы, но все еще не оптимизированы JVM. Это делает невероятно неприятным пытаться писать алгоритмы с использованием взаимной рекурсии с использованием Java, поскольку, если вы хотите приличную производительность / диапазон, вы должны делать темную магию, чтобы она вписывалась в циклы.
Итак, в целом, это не так уж важно для многих случаев. Большинство хвостовых вызовов либо выполняются только на один стек, с такими вещами, как
или рекурсия. Однако для класса TC, который не вписывается в это, каждый язык JVM чувствует боль.
Однако есть веская причина, по которой у нас пока нет TCO. JVM дает нам трассировки стека. С TCO мы систематически исключаем стековые фреймы, которые, как мы знаем, «обречены», но JVM может на самом деле захотеть их позже для трассировки стека! Скажем, мы реализуем FSM, как это, где каждое состояние вызывает следующий. Мы удалили бы все записи о предыдущих состояниях, чтобы обратная связь показывала нам, в каком состоянии, но не о том, как мы туда попали.
Кроме того, и что еще более актуально, большая часть проверки байт-кода основывается на стеке, что исключает то, что позволяет нам проверять байт-код, не является приятной перспективой. Между этим и тем, что в Java есть циклы, TCO выглядит немного сложнее, чем это стоит инженерам JVM.
источник
Оптимизация вызовов хвоста в основном важна из-за рекурсии хвоста. Однако есть аргумент, почему на самом деле хорошо, что JVM не оптимизирует хвостовые вызовы: поскольку TCO повторно использует часть стека, трассировка стека из исключения будет неполной, что усложнит отладку.
Есть способы обойти ограничения JVM:
Это может потребовать большего примера. Рассмотрим язык с замыканиями (например, JavaScript или аналогичный). Мы можем написать факториал как
Теперь мы можем сделать так, чтобы он возвращал обратный вызов:
Теперь это работает в пространстве с постоянным стеком, что довольно глупо, потому что в любом случае это хвостовая рекурсия. Тем не менее, этот метод может сгладить все хвостовые вызовы в пространстве постоянного стека. И если программа находится в CPS, то это означает, что callstack в целом является постоянным (в CPS каждый вызов является хвостовым вызовом).
Основным недостатком этого метода является то, что его намного сложнее отладить, немного сложнее реализовать и менее производительно - увидеть все замыкания и косвенные указания, которые я использую.
По этим причинам было бы гораздо предпочтительнее, чтобы виртуальная машина реализовала операторы хвостового вызова, такие как Java, у которых есть веские причины не поддерживать хвостовые вызовы, которые бы не использовали его.
источник
return foo(....);
в методеfoo
(2), конечно, полностью согласуются. Тем не менее, мы принимаем неполное отслеживание из циклов, присваиваний (!), Последовательностей операторов. Например, если вы найдете неожиданное значение в переменной, вы наверняка захотите узнать, как оно туда попало. Но вы не жалуетесь на отсутствие следов в этом случае. Поскольку в нашем мозгу как-то выгравировано, что а) это происходит только на вызовах, б) это происходит на всех вызовах. И то и другое не имеет смысла, ИМХО.Значительную часть вызовов в программе составляют хвостовые вызовы. У каждой подпрограммы есть последний вызов, поэтому у каждой подпрограммы есть хотя бы один хвостовой вызов. Хвостовые вызовы имеют характеристики производительности,
GOTO
но безопасность вызова подпрограммы.Наличие правильных вызовов в хвосте позволяет вам писать программы, которые вы не можете написать иначе. Взять, к примеру, конечный автомат. Конечный автомат может быть реализован очень напрямую, если каждое состояние будет подпрограммой, а каждый переход состояния - вызовом подпрограммы. В этом случае вы переходите из состояния в состояние, делая вызов после вызова после вызова, и вы фактически никогда не возвращаетесь! Без правильных коллировок вы бы сразу взорвали стек.
Без PTC вы должны использовать
GOTO
или батуты или исключения как поток управления или что-то в этом роде. Это намного уродливее, и не столько прямое представление конечного автомата 1: 1.(Обратите внимание, как я ловко избегал использовать скучный пример «цикла». Это пример, когда PTC полезны даже в языке с циклами.)
Я намеренно использовал здесь термин «правильные вызовы», а не ТШО. TCO - это оптимизация компилятора. PTC - это языковая функция, которая требует от каждого компилятора выполнения TCO.
источник
The vast majority of calls in a program are tail calls.
Нет, если «подавляющее большинство» вызываемых методов выполняют более одного собственного вызова.Every subroutine has a last call, so every subroutine has at least one tail call.
Это легко продемонстрировать как ложноеreturn a + b
. (Если, конечно, вы не на каком-то безумном языке, где базовые арифметические операции определены как вызовы функций.)Любой, кто говорит это, либо (1) не понимает оптимизацию хвостового вызова, либо (2) не понимает JVM, либо (3) оба.
Я начну с определения хвостовых вызовов из Википедии (если вам не нравится Википедия, вот альтернатива ):
В приведенном ниже коде вызов
bar()
является хвостовым вызовомfoo()
:Оптимизация хвостового вызова происходит, когда языковая реализация, видя хвостовой вызов, не использует нормальный вызов метода (который создает фрейм стека), а вместо этого создает ветвь. Это оптимизация, потому что для стекового фрейма требуется память, и для этого требуется, чтобы циклы ЦП выдвигали информацию (например, адрес возврата) в фрейм, а также потому, что для пары вызов / возврат предполагается больше циклов ЦП, чем для безусловного перехода.
TCO часто применяется к рекурсии, но это не единственное ее использование. Это не относится ко всем рекурсиям. Например, простой рекурсивный код для вычисления факториала не может быть оптимизирован хвостовым вызовом, потому что последнее, что происходит в функции - это операция умножения.
Для реализации оптимизации хвостового вызова вам понадобятся две вещи:
Вот и все. Как я уже отмечал в другом месте, у JVM (как и у любой другой полной по Тьюрингу архитектуры) есть начало. Это имеет безусловный переход , но функциональность может быть легко реализована с использованием условного перехода.
Часть статического анализа - вот что сложно. В пределах одной функции это не проблема. Например, вот хвостовая рекурсивная функция Scala для суммирования значений в
List
:Эта функция превращается в следующий байт-код:
Обратите внимание
goto 0
на в конце. Для сравнения, эквивалентная Java-функция (которая должна использовать функциюIterator
имитации поведения разбиения списка Scala на голову и хвост) превращается в следующий байт-код. Обратите внимание, что последние две операции теперь являются вызовом , за которым следует явный возврат значения, созданного этим рекурсивным вызовом.Хвост оптимизации вызова одной функции тривиальна: компилятор может видеть , что не существует кода , который использует результат вызова, так что он может заменить Invoke с
goto
.Жизнь становится сложнее, если у вас есть несколько методов. Инструкции по ветвлению JVM, в отличие от процессора общего назначения, такого как 80x86, ограничены одним методом. Это все еще относительно просто, если у вас есть закрытые методы: компилятор может встраивать эти методы соответствующим образом, поэтому он может оптимизировать хвостовые вызовы (если вам интересно, как это может работать, рассмотрите общий метод, который использует a
switch
для управления поведением). Вы даже можете распространить эту технику на несколько открытых методов в одном классе: компилятор вставляет тела методов, предоставляет методы открытого моста, а внутренние вызовы превращаются в переходы.Но эта модель ломается, когда вы рассматриваете публичные методы в разных классах, особенно в свете интерфейсов и загрузчиков классов. Компилятору исходного уровня просто не хватает знаний для реализации оптимизации хвостовых вызовов. Однако, в отличие от "голых" реализаций, * JVM (имеет информацию для этого в виде компилятора Hotspot (по крайней мере, это делает компилятор ex-Sun). Я не знаю, выполняет ли он на самом деле Оптимизация хвостового вызова, и подозреваю, что нет, но это возможно .
Что подводит меня ко второй части вашего вопроса, которую я перефразирую как «нам все равно?»
Понятно, что если ваш язык использует рекурсию в качестве единственного примитива для итерации, вам все равно. Но языки, которым нужна эта функция, могут ее реализовать; единственная проблема заключается в том, может ли компилятор для указанного языка создать класс, который может вызываться и вызываться произвольным классом Java.
Вне этого случая я собираюсь пригласить отрицательные голоса, говоря, что это не имеет значения. Большая часть рекурсивного кода, который я видел (и я работал со многими графическими проектами) , не оптимизирована с помощью хвостового вызова . Как и простой факториал, он использует рекурсию для построения состояния, а хвостовая операция является комбинацией.
Для кода, оптимизируемого с помощью хвостового вызова, часто просто перевести этот код в итеративную форму. Например, ту
sum()
функцию, которую я показал ранее, можно обобщить какfoldLeft()
. Если вы посмотрите на источник , вы увидите, что он фактически реализован как итерационная операция. У Jörg W Mittag был пример конечного автомата, реализованного посредством вызовов функций; Есть много эффективных (и поддерживаемых) реализаций конечного автомата, которые не полагаются на вызовы функций, переводимые в переходы.Я закончу с чем-то совершенно другим. Если вы выберете Google из сносок в SICP, вы можете оказаться здесь . Я лично считаю, что это гораздо более интересное место, чем замена моего компилятора
JSR
наJUMP
.источник
return foo(123);
может быть лучше выполнен с помощью встраивания,foo
чем путем генерации кода для управления стеком и выполнения перехода, но я не понимаю, почему tail-call будет отличаться от обычного вызова в что касается