循环的尾部位置到底是什么？

Question

Clojure 中 recur 的“尾部位置”的准确定义是什么？我认为这将是循环 S 表达式中的最后一项，但在下面的示例中，在我看来，以 (if ...) 开头的 S 表达式位于尾部位置即（循环[绑定语句][if 语句]）。

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

（代码取自http://www.4clojure.com/problem/68）

密切相关问题： 如何调用 recur在 Clojure 的 if 条件中？

Answer 1

尾部位置是表达式返回值的位置。评估尾部位置的表单后，不再评估任何表单。

请考虑 Clojure 的乐趣

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

它采用单个参数并将其命名为 x。如果 x 已经是正数，则 x 是
返回；否则返回 x 的相反数。
if 形式位于函数的尾部位置，因为无论它返回什么，整个
函数将返回。 “then”子句中的 x 也位于函数的尾部位置。
但是“else”子句中的 x 不在函数的尾部位置，因为 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 not 位于尾部位置，因为 (+ 1 ...) 将被评估在（recur tail）之后。因此 Clojure 编译器会给出错误。

尾部位置很重要，因为您可以从尾部位置使用 recur 形式。函数式编程语言通常使用递归来实现过程式编程语言通过循环完成的任务。但递归是有问题的，因为它消耗堆栈空间，并且深度递归可能导致堆栈溢出问题（除了速度慢之外）。这个问题通常通过尾部调用优化（TCO）来解决，当递归调用发生在函数/表单的尾部位置时，它会消除调用者。

因为 Clojure 托管在 JVM 上，而 JVM 不支持尾调用优化，所以它需要一个技巧来进行递归。 recur 形式就是这个技巧，它允许 Clojure 编译器执行类似于尾部调用优化的操作。此外，它还验证 recur 确实位于尾部位置。好处是您可以确保优化确实发生。

Answer 2

只是为了补充上面 Paul 的精彩答案，The Joy of Clojure (ed1) 提供了一个表格（表 7.1），它准确地显示了各种形式/表达式中尾部位置的位置，我在下面复制了该表格。查找“tail”一词在每种形式/表达中出现的位置：

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