Clojure: Что такое хвостовое положение для повторения?

Ответ 1

Позиция хвоста - это позиция, из которой выражение возвращает значение. Нет оценки больше форм после оценки формы в позиции хвоста.

Рассмотрим этот пример из Радость Clojure

(defn absolute-value [x]
  (if (pos? x)
      x        ; "then" clause 
      (- x)))  ; "else" clause

Он принимает один параметр и называет его x. Если x уже положительное число, то x равно вернулся; в противном случае возвращается противоположное x. Форма if находится в позиции хвоста функций, потому что все, что она возвращает, функция вернется. X в предложении "then" также находится в хвостовой позиции функции. Но x в предложении "else" не находится в позиции хвоста функций, потому что значение x передается в функцию - не возвращается напрямую. Предложение else в целом (- x) находится в положение хвоста.

Аналогично в выражении

(if a
    b
    c)

оба b и c находятся в хвостовых позициях, потому что любой из них может быть возвращен из оператора if.

Теперь в вашем примере

(loop [x 5
       result []]
  (if (> x 0)
    (recur (dec x) (conj result (+ 2 x)))
    result)))

форма (if ...) находится в хвостовом положении формы (loop ...), и форма (recur ...) и форма result находятся в хвостовом положении формы (if ...).

С другой стороны, в вопросе, который вы связали

(fn [coll] (let [tail (rest coll)]
             (if (empty tail)
                 1
                 (+ 1 (recur tail)))))

recur не в хвостовом положении, потому что (+ 1 ...) будет оцениваться после (recur tail). Поэтому компилятор Clojure дает ошибку.

Положение хвоста важно, потому что вы можете использовать форму recur из положения хвоста. Функциональные языки программирования обычно используют рекурсию для выполнения процедурными языками программирования с помощью циклов. Но рекурсия проблематична, потому что она потребляет пространство стека, а глубокая рекурсия может привести к проблемам stackoverflow (в дополнение к медленному). Эта проблема обычно решается с помощью оптимизации хвостового вызова (TCO), которая устраняет вызывающий объект, когда рекурсивный вызов происходит в позиции хвоста функции/формы.

Поскольку Clojure размещается на JVM, а JVM не поддерживает оптимизацию хвостового вызова, ему нужен трюк, чтобы сделать рекурсию. Форма recur - это трюк, она позволяет компилятору Clojure делать что-то подобное оптимизации хвостового вызова. Кроме того, он проверяет, что recur действительно находится в положении хвоста. Преимущество в том, что вы можете убедиться, что оптимизация действительно происходит.

Ответ 2

Чтобы дополнить отличный ответ от вышеизложенного, "Радость" Clojure (ed1) содержит таблицу (Таблица 7.1), которая точно показывает, где позиция хвоста находится в разных формах/выражениях, которые я воспроизвел ниже. Ищите, где слово "хвост" встречается в каждой форме/выражении:

|---------------------+-------------------------------------------+---------------|
| Form                | Tail Position                             | recur target? |
|---------------------+-------------------------------------------+---------------|
| fn, defn            | (fn [args] expressions tail)              | Yes           |
| loop                | (loop [bindings] expressions tail)        | Yes           |
| let, letfn, binding | (let [bindings] expressions tail)         | No            |
| do                  | (do expressions tail)                     | No            |
| if, if-not          | (if test then tail else tail)             | No            |
| when, when-not      | (when test expressions tail)              | No            |
| cond                | (cond test test tail ... :else else tail) | No            |
| or, and             | (or test test ... tail)                   | No            |
| case                | (case const const tail ... default tail)  | No            |
|---------------------+-------------------------------------------+---------------|