Почему нельзя хвостовые вызовы оптимизировать в Lisp на основе JVM?
Основной вопрос: я рассматриваю наиболее значительное применение оптимизации хвостового вызова (TCO) как преобразование рекурсивного вызова в цикл (в случаях, когда рекурсивный вызов имеет определенную форму). Точнее говоря, при переводе на машинный язык это обычно будет перевод в какую-то серию прыжков. Некоторые компиляторы Common Lisp и Scheme, которые компилируются в собственный код (например, SBCL), могут идентифицировать хвостово-рекурсивный код и выполнять этот перевод. Лиспы, основанные на JVM, такие как Clojure и ABCL, не могут это сделать. Что такого в JVM как машине, которая предотвращает или затрудняет это? Я не понимаю У JVM, очевидно, нет проблем с циклами. Компилятор должен выяснить, как использовать TCO, а не компьютер, на который он компилируется.
Смежный вопрос: Clojure может преобразовать, казалось бы, рекурсивный код в цикл: он действует так, как будто он выполняет TCO, если программист заменяет хвостовой вызов функции ключевым словом recur, Но если возможно заставить компилятор идентифицировать хвостовые вызовы - как, например, SBCL и CCL - тогда почему компилятор Clojure не может понять, что он должен обрабатывать хвостовой вызов так, как он обрабатывает recur?
(Извините - это, несомненно, часто задаваемые вопросы, и я уверен, что приведенные выше замечания показывают мое невежество, но мне не удалось найти более ранние вопросы.)
3 ответа
Реальная совокупная стоимость владения работает для произвольных вызовов в конечной позиции, а не только для собственных вызовов, поэтому код, подобный следующему, не вызывает переполнение стека:
(letfn [(e? [x] (or (zero? x) (o? (dec x))))
(o? [x] (e? (dec x)))]
(e? 10))
Очевидно, что для этого вам понадобится поддержка JVM, так как программы, работающие на JVM, не могут манипулировать стеком вызовов. (Если только вы не захотели установить свое собственное соглашение о вызовах и наложить соответствующие накладные расходы на вызовы функций; Clojure стремится использовать обычные вызовы методов JVM.)
Что касается устранения собственных вызовов в хвостовой позиции, это более простая проблема, которая может быть решена до тех пор, пока все тело функции будет скомпилировано в один метод JVM. Однако это ограничивающее обещание. Кроме того, recur довольно хорошо понравился за его явность.
Существует причина, по которой JVM не поддерживает TCO: почему JVM все еще не поддерживает оптимизацию хвостового вызова?
Однако есть способ обойти это путем злоупотребления памятью кучи и некоторыми хитростями, описанными в документе "Преобразование CPS первого прохода за один проход"; это реализовано в Clojure Крисом Фрисом и Дэниелом П. Фридманом (см. clojure-tco).
Теперь Rich Hickey мог бы сделать такую оптимизацию по умолчанию, в некоторых случаях это делает Scala. Вместо этого он решил положиться на конечного пользователя, чтобы указать случаи, когда они могут быть оптимизированы с помощью Clojure с trampoline или же loop-recur строит. Решение было объяснено здесь: https://groups.google.com/d/msg/clojure/4bSdsbperNE/tXdcmbiv4g0J
В заключительной презентации ClojureConj 2014 Брайан Гетц отметил, что в JVM есть функция безопасности, которая предотвращает коллапс стекового фрейма (так как это будет вектор атаки для людей, желающих заставить функцию пойти куда-нибудь по возвращении).
https://www.youtube.com/watch?v=2y5Pv4yN0b0&index=21&list=PLZdCLR02grLoc322bYirANEso3mmzvCiI