5

有些虚拟机，尤其是 JVM，据说不支持 TCO。因此，像 Clojure 这样的语言需要用户使用loop recur。

但是，我可以重写自尾调用以使用循环。例如，这是一个尾调用阶乘：

def factorial(x, accum):
    if x == 1:
        return accum
    else:
        return factorial(x - 1, accum * x)

这是一个等效的循环：

def factorial(x, accum):
    while True:
        if x == 1:
            return accum
        else:
            x = x - 1
            accum = accum * x

这可以由编译器完成（我已经编写了执行此操作的宏）。对于相互递归，您可以简单地内联您正在调用的函数。

那么，既然您可以在不需要任何 VM 的情况下实现 TCO，为什么语言（例如 Clojure、Armed Bear Common Lisp）不这样做呢？我错过了什么？

4

3 回答 3

11

由于多种原因，内联不是解决一般尾调用消除问题的方法。下面的列表并不详尽。然而，它是经过分类的——它从不便开始，以一个完整的表演结束。

  1. 在尾部位置调用的函数可能很大，在这种情况下，从性能的角度来看，内联它可能是不可取的。

  2. 假设有多个对gin的尾调用f。根据内联的常规定义，您必须g在每个调用站点内联，这可能会产生f巨大的影响。相反，如果您选择goto开始g然后跳回，那么您需要记住跳转到的位置，并且突然之间您正在维护自己的调用堆栈片段（与“真正的“调用堆栈）。

  3. 对于相互递归函数fand g，您必须内联fing和gin f。显然，在通常的内联定义下这是不可能的。因此，您只剩下一个有效的自定义函数内调用约定（如goto上面 2. 的基于 - 的方法）。

  4. Real TCE 适用于尾部位置的任意调用，包括在高阶上下文中：

    (defn say-foo-then-call [f]
  (println "Foo!")
  (f))

    这在某些场景中可以发挥很大的作用，显然不能用内联来模拟。

于 2014-04-19T21:33:09.527 回答
1

  1. 这可能会令人惊讶，并且可能会使调试更加困难，因为您看不到调用堆栈。

  2. 它仅适用于非常特殊的情况，而不是 VM 支持 TCO 时处理的一般情况。

  3. 程序员通常不会用尾递归的方式编写代码，除非语言激励他们这样做。例如，递归阶乘通常用递归步骤写成n * fact(n-1)，它不是尾递归的。

于 2014-04-19T21:03:50.930 回答
1

TCO本身不需要 VM 支持。也就是说，不是针对局部函数。跨越外部函数的尾调用需要 VM 支持。理想情况下，尾递归的完整实现允许单独编译的程序单元中的函数在常量空间中相互递归，不仅是一个父函数本地的函数，或者编译器一次都可以看到的函数。

在没有尾调用支持的 VM 中，函数调用被封装，并在退出时分配一个新帧。尾调用需要一个特殊的入口点来绕过它。函数可以参与尾调用和非尾调用，因此它们需要两个入口点。

可以使用非本地返回和调度在没有 VM 支持的情况下模拟尾调用消除。也就是说，当尾部调用在语法上发生时，它被转换为非本地返回，该返回通过动态控制转移放弃当前函数，将参数（可能打包为对象）传递给隐藏的调度循环，它将控制权转移到目标函数，将这些参数传递给它。这将实现递归发生在恒定空间中的要求，并且会像尾调用一样“看起来和感觉”。但是，它很慢，而且可能并不完全透明。

于 2016-08-10T18:53:56.503 回答