Предупреждение / ошибка Clojure при сбое оптимизации хвостового вызова

В Scala 2.8.x была добавлена ​​новая аннотация (@tailrec), которая выдает ошибку времени компиляции, если компилятор не может выполнить оптимизацию хвостового вызова для аннотированного метода.

Есть ли в Clojure аналогичные возможности по отношению к loop/recur?

РЕДАКТИРОВАТЬ: Прочитав первый ответ на мой вопрос (спасибо, Божидар Бацов) и продолжив поиск в документации Clojure, я наткнулся на следующее:

(recur exprs *)
Оценивает выражения по порядку, затем, параллельно, повторно привязывает привязки точки рекурсии к значениям выражений. Если точкой рекурсии был метод fn, он повторно связывает параметры. Если точкой рекурсии был цикл, он повторно связывает привязки цикла. Затем выполнение возвращается к точке рекурсии. Повторяющееся выражение должно точно соответствовать арности точки рекурсии. В частности, если точка рекурсии была вершиной метода переменной fn, сбор аргументов отдыха не происходит - должен быть передан один seq (или null). повторение в позиции, отличной от хвостовой, является ошибкой.

Обратите внимание, что recur - единственная конструкция цикла в Clojure, не использующая стек. Оптимизация хвостового вызова отсутствует, и использование самовызовов для зацикливания неизвестных границ не рекомендуется. recur функционально, и его использование в хвостовой позиции проверяется компилятором [курсив мой].

(def factorial
  (fn [n]
    (loop [cnt n acc 1]
       (if (zero? cnt)
            acc
          (recur (dec cnt) (* acc cnt))))))

clojure tail-recursion
person Ralph    schedule 26.04.2010    source источник

Ответы (2)


arrow_upward
4
arrow_downward

При использовании цикла / повторения AFAIK нет оптимизации хвостового вызова. Цитата из официальных документов:

В отсутствие изменяемых локальных переменных цикл и итерация должны принимать другую форму, чем в языках со встроенными конструкциями for или while, которые управляются изменением состояния. В функциональных языках циклы и итерации заменяются / реализуются с помощью рекурсивных вызовов функций. Многие такие языки гарантируют, что вызовы функций, выполняемые в хвостовой позиции, не занимают пространство стека, и, таким образом, рекурсивные циклы используют постоянное пространство. Поскольку Clojure использует соглашения о вызовах Java, он не может и не дает тех же гарантий оптимизации хвостового вызова. Вместо этого он предоставляет специальный оператор recur, который выполняет рекурсивный цикл в постоянном пространстве путем повторной привязки и перехода к ближайшему охватывающему циклу или функциональному кадру. Хотя он не такой общий, как оптимизация хвостового вызова, он позволяет использовать большинство тех же элегантных конструкций и предлагает преимущество проверки того, что повторные вызовы могут происходить только в хвостовой позиции.

person Bozhidar Batsov    schedule 26.04.2010
comment
Этот ответ мне кажется вводящим в заблуждение. Точка цикла / повторения - это как раз ограниченная форма TCO, а именно TCO для саморекурсии (в форме функции или цикла). Полностью общая совокупная стоимость владения также оптимизирует использование стека для хвостовых вызовов других функций. Таким образом, хотя у Clojure нет TCO (общая форма), у него есть самовызовы TCO из повторения. Вот в чем суть рекурсивного цикла с постоянным пространством. В конечном счете, recur делает то же самое, что и @tailrec в Scala, вот о чем и идет речь. (Мы надеемся, что эта проблема исчезнет с JDK7.) - person Michał Marczyk; 26.04.2010
comment
Думаю, вы не так уж много использовали Scala - простая хвостовая оптимизация там происходит даже без tailrec, но вы получите ошибку, если пометите метод как tailrec, который на самом деле не является рекурсивным хвостовым вызовом. Ваш комментарий вводит в заблуждение больше, чем мой ответ, но каждый имеет право на свое мнение ... - person Bozhidar Batsov; 30.09.2011
comment
Итак, ваше мнение таково, что [t] здесь нет оптимизации хвостового вызова, когда вы используете цикл / повтор, хотя сразу после этого вы цитируете отрывок из документации (как вы говорите), в котором говорится, что цикл через recur не использует стек ? Кроме того, этот вопрос не о поведении scalac, когда @tailrec не указан, а о возможности получения в Clojure тех же гарантий, которые @tailrec дает вам в Scala (вполне возможно, просто используйте recur). - person Michał Marczyk; 30.09.2011
comment
Я отвечаю на оставшийся вопрос о scalac ниже моего ответа, так как вы тоже подняли его там. Кстати, у меня определенно сложилось впечатление, что Scala - отличный язык, и я бы не хотел его продавать, но, насколько мне известно, он следует соглашению о вызовах, подобному Java, и поэтому может обеспечить совокупную стоимость владения в точно таких же обстоятельствах Clojure может. (Тот факт, что Clojure принял эстетическое решение, требуя recur, в то время как @tailrec является необязательным, не меняет этого фундаментального факта.) - person Michał Marczyk; 30.09.2011
comment
Если я в чем-то ошибаюсь (в отношении Scala 2.8 на JDK ‹= 1.6, о чем идет речь в этом вопросе), пожалуйста, дайте мне знать. Кроме того, я хотел бы провести это обсуждение 17 месяцев назад, когда этот вопрос был задан - я с сожалением должен сказать, что прошло довольно много времени с тех пор, как я имел дело со Scala сейчас. Хорошего дня. - person Michał Marczyk; 30.09.2011

arrow_upward
6
arrow_downward

Собственно ситуация в Scala w.r.t. Оптимизация хвостового вызова такая же, как в Clojure: ее можно выполнять в простых ситуациях, таких как саморекурсия, но не в общих ситуациях, таких как вызов произвольной функции в хвостовой позиции.

Это связано с тем, как работает JVM - для того, чтобы TCO работала с JVM, сама JVM должна поддерживать ее, чего в настоящее время нет (хотя это может измениться после выпуска JDK7. ).

См., Например, эту запись в блоге для обсуждения совокупной стоимости владения и прыжки на батуте в Scala. Clojure имеет точно такие же функции для облегчения рекурсии без использования стека (= оптимизированной для хвостового вызова); сюда входит выдача ошибки времени компиляции, когда пользовательский код пытается вызвать recur не в хвостовой позиции.

person Michał Marczyk    schedule 26.04.2010
comment
Я не думаю, что это правильно. recur указывает компилятору Clojure, что вызов является хвосторекурсивным, тогда как @tailrec спрашивает компилятор Scala, является ли вызов хвостовым рекурсивным вызовом. Поскольку Scala часто не может гарантировать, что вызов является хвостовой рекурсией (например, для неокончательных методов), с Clojure можно получить гораздо больше оптимизации с хвостовой рекурсией, чем с помощью Scala, за счет необходимости быть явным. - person Peter Niederwieser; 26.03.2011
comment
Конечно, можно утверждать, что Scala также имеет явный механизм для оптимизации хвостовой рекурсии, например, путем введения вложенного метода. Но это не так очевидно / идиоматично, как в Clojure. - person Peter Niederwieser; 26.03.2011
comment
Хм. Я думал, что @tailrec должен был вызвать ошибку компилятора, когда аннотированный метод нельзя было превратить в цикл. Соответствующая страница документации, похоже, подтверждает это (поскольку проводит быстрый эксперимент с @tailrec аннотированным нерекурсивным факториальным методом). Clojure recur вызывает такое же поведение (recur в позиции, отличной от хвоста, является ошибкой и вызывает жалобу компилятора). Однако я не эксперт по Scala (далеко не всегда!), Так что, возможно, я упускаю здесь какую-то важную тонкость ...? - person Michał Marczyk; 29.03.2011
comment
Как я уже упоминал ранее, tailrec - это просто подсказка компилятора (похожая на Override в Java) - она ​​просто просит компилятор проверить, действительно ли это оптимизируемый метод хвостового вызова. Оптимизация будет происходить с аннотацией или без нее ... - person Bozhidar Batsov; 30.09.2011
comment
Это полезная вещь, которую нужно знать о Scala, но не все, что имеет отношение к рассматриваемому вопросу, который касается обеспечения того, чтобы хвостовой вызов был скомпилирован в цикл в Clojure (и что компилятор выдает ошибки, если это невозможно). Последнее возможно тогда и только тогда, когда хвостовой вызов на самом деле является самостоятельным вызовом или если вызываемый объект встроен в вызывающий объект - та же история, что и в Scala, насколько я могу судить. - person Michał Marczyk; 30.09.2011
comment
Не думаю, что я сделал какие-либо замечания о том, как scalac работает, когда @tailrec не указан; тем не менее, я полагаю, чтобы быть полностью справедливым по отношению к Scala, было бы хорошо заявить, что аннотация не нужна, поэтому спасибо за ваш комментарий. - person Michał Marczyk; 30.09.2011