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

Question

Каково точное определение «положения хвоста» для повторения в уловке.Я бы подумал, что это будет последний элемент в S-выражении цикла, но в приведенном ниже примере мне кажется, что S-выражение, начинающееся с (если ...), находится в хвостовой позиции, т. Е. ([LOOP KEYWORD][ЗАЯВЛЕНИЯ О СВЯЗИ] [ЕСЛИ ЗАЯВЛЕНИЕ]).

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

код взят из http://www.4clojure.com/problem/68

Тесно связанный вопрос: Как я могу вызвать recur в условии if в Clojure?

Answer 1

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

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

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

Он принимает один параметр и называет его 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 из положения хвоста. Функциональные языки программирования обычно используют рекурсию для того, что процедурные языки программирования выполняют с помощью циклов. Но рекурсия проблематична, потому что она потребляет пространство стека, и глубокая рекурсия может привести к проблемам переполнения стека (в дополнение к замедлению). Эта проблема обычно решается с помощью оптимизации хвостового вызова (TCO) , которая устраняет вызывающего, когда рекурсивный вызов происходит в хвостовой позиции функции / формы.

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

Answer 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            |
|---------------------+-------------------------------------------+---------------|