Clojure 在尾调用优化失败时的警告/错误提示

Question

在Scala 2.8.x中，增加了一个新的注解（@tailrec），如果编译器无法对注释方法执行尾调用优化，则会产生编译时错误。

在Clojure中是否有类似于loop/recur的功能？

编辑：阅读了我的问题的第一个答案（感谢Bozhidar Batsov）并在Clojure文档中进一步搜索后，我发现了这个：

(recur exprs*)按顺序评估exprs，然后并行重新绑定递归点的绑定到exprs的值。如果递归点是fn方法，则重新绑定参数。如果递归点是循环，则重新绑定循环绑定。然后执行跳回递归点。recur表达式必须与递归点的arity完全匹配。特别地，如果递归点是变长fn方法的顶部，则不会收集rest args - 应传递单个seq（或null）。非尾位置的recur是错误的。

请注意，recur是Clojure中唯一不消耗堆栈的循环结构。没有尾调用优化，不鼓励使用自调用进行未知边界的循环。recur是功能性的，其在尾位置的使用由编译器验证。

(def factorial
  (fn [n]
    (loop [cnt n acc 1]
       (if (zero? cnt)
            acc
          (recur (dec cnt) (* acc cnt))))))

- Ralph

Answer 1

实际上，Scala在尾调用优化方面的情况与Clojure相同：在简单情况下（如自我递归）可以执行它，但在一般情况下（如在尾部位置调用任意函数）不行。这是由于JVM的工作方式 -- 要使TCO在JVM上工作，JVM本身必须支持它，但目前它还不支持（尽管在发布JDK7时可能会改变）。请参见例如此博客文章，了解Scala中TCO和trampolining的讨论。Clojure具有完全相同的功能，以促进非堆栈消耗（=尾调用优化）递归; 这包括当用户代码尝试在非尾位置调用recur时抛出编译时错误。

- Michał Marczyk

---

我认为这不正确。recur指示Clojure编译器调用是尾递归，而@tailrec询问Scala编译器调用是否为尾递归。因为Scala通常无法保证调用是尾递归（例如对于非最终方法），所以使用Clojure可以获得更多的尾递归优化，但需要显式声明。 - Peter Niederwieser

当然，有人可能会争辩说Scala也有一个显式的尾递归优化机制，例如通过引入嵌套方法。但这并不像Clojure那样明显/惯用。 - Peter Niederwieser

嗯，我以为@tailrec应该会在被注释的方法无法转换为循环时导致编译器出错。相关文档页面似乎证实了这一点（一个带有@tailrec注释的非尾递归阶乘方法的快速实验也是如此）。Clojure的recur也会导致相同的行为（非尾位置的recur是一个错误，并导致编译器抱怨）。虽然我不是Scala专家（远远不是！），但也许我在这里漏掉了一些重要的细节...？ - Michał Marczyk

正如我之前提到的，tailrec只是一个编译器提示（类似于Java中的Override）-它只是要求编译器检查这是否真的是一个可优化尾调用的方法。无论有没有注释，优化都会发生... - Bozhidar Batsov

这是关于Scala的一个有用的知识，但与手头的问题并不那么相关，该问题是关于确保Clojure中的尾调用编译成循环（如果不可能，则编译器会出错）。只有当尾调用实际上是自调用或被调用者在调用者中内联时，后者才是可能的--就我所知，这与Scala的情况相同。 - Michał Marczyk

我不认为我在没有指定@tailrec时如何工作的情况下发表了任何评论；尽管如此，为了完全公正地对待Scala，说明注释是不必要的可能会更好，所以感谢您的评论。 - Michał Marczyk

Answer 2

据我所知，在使用loop/recur时，Clojure没有尾调用优化。官方文档中有这样一句话：

在没有可变局部变量的情况下，循环和迭代必须采用不同于由状态改变控制的内置for或while结构的语言的形式。在函数式语言中，循环和迭代通过递归函数调用替换/实现。许多这样的语言保证在尾位置进行的函数调用不会消耗堆栈空间，因此递归循环利用常数空间。由于Clojure使用Java调用约定，它不能像其他语言那样提供相同的尾调用优化保证。相反，它提供了recur特殊运算符，通过重新绑定并跳转到最近的封闭循环或函数帧来实现常量空间递归循环。虽然不像尾调用优化那样通用，但它允许大多数相同的优雅结构，并提供了检查对recur的调用只能发生在尾部位置的优势。

- Bozhidar Batsov

---

我觉得这个答案有误导性。循环/递归的重点正是有限的尾调用优化(TCO) -- 即针对自我递归(在函数或循环形式中)的TCO。完全通用的TCO也会优化对其他函数的尾调用的堆栈使用。因此，虽然Clojure没有通用的TCO，但它可以从recur中进行TCO'd自调用。这就是“常量空间递归循环”所涉及到的内容。最终，recur确切地做了与Scala的@tailrec相同的事情，这也是这个问题所询问的。(希望这个问题随着JDK7而解决。) - Michał Marczyk

我猜你并没有太多使用Scala - 简单的尾递归优化即使在没有tailrec的情况下也会发生，但是如果你将一个不实际进行尾调用递归的方法标记为tailrec，那么你会得到一个错误。你的评论比我的回答更具误导性，但每个人都有权发表自己的意见... - Bozhidar Batsov

所以你的观点是，即使在你引用文档中指出使用recur进行循环不会消耗堆栈之后，当你使用loop/recur时没有尾调用优化？此外，这个问题并不是关于在未指定@tailrec时scalac的行为，而是关于在Clojure中获得与Scala中@tailrec给出的保证相同的可能性（完全可以，只需使用recur）。 - Michał Marczyk

我在我的回答下面回答了关于scalac的剩余问题，因为你也在那里提到了它。顺便说一句，我肯定有这样的印象，即Scala是一种很棒的语言，不想把它卖得太少——但据我所知，它遵循类似Java的调用约定，因此可以在与Clojure完全相同的情况下提供TCO。（Clojure做出需要一个recur的审美决定，而@tailrec是可选的，但这并不改变基本事实。） - Michał Marczyk

如果我在这方面有所错误（关于Scala 2.8在JDK <= 1.6上，这个问题是关于它的），请告诉我。此外，我希望在17个月前就进行这个讨论，当时这个问题实际上已经被提出了 - 很遗憾，自那以后我已经很长时间没有接触过Scala了。祝你有美好的一天。 - Michał Marczyk