recur 的尾部位置到底是什么? [英] What exactly is tail position for recur?

问题描述

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

What's the precise definition of "tail position" for recur in Clojure? I would think that it would be the last item in a loop S-expression, but in the example below it seems to me that the S-Expression which starts with (if ...) is in tail position i.e. (loop [binding statements] [if statement]).

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

(代码取自 http://www.4clojure.com/problem/68)

密切相关的问题:我该怎么办在 Clojure 中以 if 条件调用 recur?

推荐答案

尾部位置是表达式将从中返回值的位置.评估尾部位置的表单后，不再评估其他表单.

考虑来自 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) 在一个尾部位置.

It takes a single parameter and names it x. If x is already a positive number, then x is returned; otherwise the opposite of x is returned. The if form is in the function’s tail position because whatever it returns, the whole function will return. The x in the "then" clause is also in a tail position of the function. But the x in the "else" clause is not in the function’s tail position because the value of x is passed to the - function, not returned directly. The else clause as a whole (- x) is in a tail position.

同样在表达式中

(if a
    b
    c)

b 和 c 都在尾部位置，因为它们中的任何一个都可以从 if 语句中返回.

both b and c are in tail positions, because either of them could be returned from the if statement.

现在在你的例子中

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

(if ...) 表单位于 (loop ...) 表单和 (recur ...) 表单和 result 表单位于 (if ...) 表单的尾部.

the (if ...) form is in the tail position of the (loop ...) form and both the (recur ...) form and the result form are in the tail position of the (if ...) form.

另一方面，在您链接的问题中

On the other hand in the question that you linked

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

recur not 位于尾部位置，因为 (+ 1 ...) 将在 (recur尾).因此 Clojure 编译器会报错.

the recur is not in tail position because the (+ 1 ...) will be evaluated after the (recur tail). Therefore the Clojure compiler gives an error.

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

Tail position is important because you can use the recur form from tail position. Functional programming languages usually use recursion for what procedural programming languages accomplish by loops. But recursion is problematic, because it consumes stack space and deep recursion can lead to stackoverflow problems (in addition to being slow). This problem is usually solved by tail call optimization (TCO), which does away with the caller when the recursive call happens in the tail position of a function / form.

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

Because Clojure is hosted on the JVM and the JVM does not support tail call optimization, it needs a trick to do recursion. The recur form is that trick, it allows the Clojure compiler to do something similar to tail call optimization. In addition, it verifies that recur is indeed in a tail position. The benefit is that you can make sure that the optimization actually does happen.

这篇关于recur 的尾部位置到底是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！