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

Question

在Scala 2.8.x中,添加了一个新的注释(@tailrec),如果编译器无法对带注释的方法执行尾调用优化,则会产生编译时错误.

在Clojure中是否有类似的设施loop/recur？

编辑: 在阅读我的问题的第一个答案(谢谢,Bozhidar Batsov)并进一步搜索Clojure文档后,我发现了这个问题:

(recur exprs*)
按顺序计算exprs,然后并行地将递归点的绑定重新绑定到exprs的值.如果递归点是fn方法,那么它会重新引导params.如果递归点是一个循环,那么它会重新绑定循环绑定.执行然后跳回到递归点.recur表达式必须与递归点的arity完全匹配.特别是,如果递归点是可变参数fn方法的顶部,则不会收集休息参数 - 应该传递单个seq(或null).在尾部位置以外重复是一个错误.

请注意,recur是Clojure中唯一不占用堆栈的循环结构.没有尾调用优化,并且不鼓励使用自调用来循环未知边界.recur是功能性的,它在尾部位置的使用由编译器验证 [强调是我的].

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

Answer 1

实际上,Scala中的尾部调用优化的情况与Clojure中的情况相同:可以在简单的情况下执行它,例如自递归,但在一般情况下,例如在尾部位置调用任意函数.

这是由于JVM的工作方式 - 为了让TCO在JVM上工作,JVM本身必须支持它,而目前它不支持它(尽管这可能会在JDK7发布时发生变化).

有关TCO和Scala中的蹦床的讨论,请参阅此博客条目.Clojure具有完全相同的功能,以促进非堆栈消耗(=尾部调用优化)递归; 这包括在用户代码尝试以recur非尾部位置调用时抛出编译时错误.

Answer 2

AFAIK 使用循环/递归时没有尾部调用优化。引用官方文档：

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