Clojure:尾部位置究竟是什么？

Question

什么是"尾部位置"的精确定义,以便在clojure中重复出现.我认为这将是循环S表达式中的最后一项,但在下面的例子中,在我看来,以(if ...)开头的S-Expression处于尾部位置即([LOOP KEYWORD] [BINDING STATMENTS] [IF声明]).

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

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

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

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是不在尾部位置,因为(+ 1 ...)将后进行评估(recur tail).因此Clojure编译器会出错.

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

因为Clojure托管在JVM上并且JVM不支持尾调用优化,所以需要一个技巧来进行递归.该recur形式是把戏,它允许Clojure的编译器做类似的尾调用优化的东西.此外,它验证recur确实处于尾部位置.好处是您可以确保优化确实发生.

Answer 2

为了补充保罗上面的优秀答案,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            |
|---------------------+-------------------------------------------+---------------|