Чем должен пожертвовать jvm для реализации оптимизации хвостового вызова?

Question

Люди говорят, что реализация clojure превосходна, за исключением ограничения отсутствия оптимизации хвостового вызова - ограничения jvm, а не реализации clojure.

http://lambda -the-ultimate.org / узел / 2547

Было сказано, что внедрение TCO в Python принесло бы в жертву

• дампов трассировки стека и
• регулярность отладки.

Объясните мне, в чем заключается сложность оптимизации хвостового вызова и зачем это нужно Python

Должны ли те же жертвы быть принесены для реализации TCO на jvm? Нужно ли жертвовать чем-то еще?

Answer 1

Хотя по-другому (в том смысле, что инструкции il уже существовали), стоит отметить дополнительные усилия, которые пришлось приложить команде .Net 64-битной JIT для соблюдения всех оконечных вызовов.

Я, в частности, взываю:

Недостатком, конечно, является то, что если вам нужно отладить или профилировать оптимизированный код, будьте готовы работать со стеками вызовов, которые выглядят так, как будто в них пропущено несколько кадров.

Я думаю, очень маловероятно, что JVM сможет этого избежать.

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

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

Answer 2

Работа ведется сейчас для добавления оконечных вызовов в JVM. Есть вики-страница , в которой говорится о некоторых деталях.

Answer 3

Да, как правило, реализация TCO не позволит вам получить трассировки полного стека. Это неизбежно, поскольку весь смысл TCO состоит в том, чтобы избегать создания дополнительных кадров стека.

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

Пример:

(defn triangle [n accumulator] 
  (if 
    (<= n 0)  
      accumulator
      (recur (dec n) (+ n accumulator))))

(triangle 1000000 0)

=> 500000500000     (note stack does not explode here!)