Предупреждение/ошибка Clojure при отказе оптимизации последнего вызова
В Scala 2.8.x, новая аннотация (@tailrec) был добавлен, который дает ошибку времени компиляции, если компилятор не может выполнить оптимизацию последнего вызова на аннотируемом методе.
Есть ли некоторое подобное средство в Clojure относительно loop/recur?
Править: После чтения первого ответа на мой вопрос (спасибо, Bozhidar Batsov) и дальнейший поиск в документах Clojure, я столкнулся с этим:
(повторитесь exprs*),
Оценивает exprs в порядке, затем, параллельно, снова переплетает привязку точки рекурсии к значениям exprs. Если точка рекурсии была fn методом, то она снова переплетает параметрические усилители. Если точка рекурсии была циклом, то она снова переплетает привязку цикла. Выполнение затем переходит назад к точке рекурсии. Повториться выражение должно соответствовать арности точки рекурсии точно. В частности, если точка рекурсии была вершиной variadic fn метод, нет никакого сбора отдыха args - должен быть передан единственный seq (или пустой указатель). повторитесь в кроме положения хвоста, ошибка.
Обратите внимание, что повторяются, единственная non-stack-consuming конструкция цикличного выполнения в Clojure. Нет никакой оптимизации последнего вызова, и использованию самопризывов к цикличному выполнению неизвестных границ препятствуют. повторитесь функционально, и его использование в позиционном хвостом проверяется компилятором [акцент - мое].
(def factorial
(fn [n]
(loop [cnt n acc 1]
(if (zero? cnt)
acc
(recur (dec cnt) (* acc cnt))))))
2 ответа
При использовании loop/recur AFAIK не существует оптимизации хвостовых вызовов. Цитата из официальной документации:
В отсутствие изменяемых локальных переменных, цикл и итерация должны принимать другую форму, чем в языках со встроенными for или while которые управляются изменением состояния. В функциональных языках зацикливание и итерация заменяются/реализуются через рекурсивные вызовы функций. Многие такие языки гарантируют, что вызовы функций, сделанные в хвостовой позиции, не занимают место в стеке пространство, и, таким образом, рекурсивные циклы используют постоянное пространство. Поскольку Clojure использует соглашения о вызовах Java, он не может и не делает таких же гарантии оптимизации хвостовых вызовов. Вместо этого он предоставляет специальный оператор recur оператор, который выполняет константное пространство рекурсивный цикл путем перепривязки и переходом к ближайшему охватывающему циклу или фрейм функции. Хотя это не так общим, как оптимизация хвостового вызова, он она позволяет использовать большинство тех же элегантных конструкций, и предлагает преимущество проверки того, что вызовы рекурсии могут происходить только в хвостовой позиции.
Собственно ситуация в Scala w.r.t. Оптимизация хвостового вызова такая же, как и в Clojure : ее можно выполнять в простых ситуациях, таких как саморекурсия, но не в общих ситуациях, таких как вызов произвольной функции в хвостовой позиции.
Это связано с тем, как работает JVM - для того, чтобы TCO работала с JVM, сама JVM должна поддерживать его, чего в настоящее время нет (хотя это может измениться после выпуска JDK7) .
См., Например, эта запись в блоге для обсуждения совокупной стоимости владения и прыжков на батуте в Scala. Clojure имеет точно такие же функции для облегчения рекурсии, не потребляющей стек (= оптимизированной для хвостового вызова); сюда входит выдача ошибки времени компиляции, когда пользовательский код пытается вызвать recur в не хвостовой позиции .