Clojure：什么是尾部位置复发？ [英] Clojure: What exactly is tail position for recur?

问题描述

tail position的精确定义是什么在clojure中重现。我认为这将是循环S表达式中的最后一个项目，但在下面的示例中，我认为以（if ...开头）的S表达式在尾位置ie（[LOOP KEYWORD] [BINDING STATMENTS] [IF STATEMENT]）。

Whats 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 KEYWORD] [BINDING STATMENTS] [IF STATEMENT]).

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

代码来自 http：// www.4clojure.com/problem/68

关系密切的问题：

Closely related question: How can I call recur in an if conditional in Clojure?

推荐答案

尾部位置是一个表达式将返回值的位置。

The tail position is a postion which an expression would return a value from. There are no more forms evaluated after the form in the tail position is evaluated.

请考虑 Clojure的欢乐

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

它需要一个参数并将其命名为x。如果x已经是一个正数，那么x是
返回的;否则返回x的相反值。
if表单在函数的尾部位置，因为无论返回什么，整个
函数将返回。 then子句中的x也在函数的尾部位置。
但是else子句中的x不在函数的尾部位置，因为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 ...） c $ c> 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 在尾部位置是不，因为 1 ...）将在（recur tail）之后计算。因此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 表单。函数式编程语言通常使用递归来表示过程式编程语言通过循环完成。但递归是有问题的，因为它消耗堆栈空间和深度递归可能导致stackoverflow问题（除了慢）。这个问题通常通过尾调用优化（TCO）来解决，当递归调用发生在函数/表单的尾部位置时，它会抛弃调用者。

Tail position is important because you can use the recur form from tail position. Functional programming languages usually use recursion for what procedual 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.

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