为什么TCO需要VM的支持？

Question

一些VM，特别是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，武装)不这样做呢？我错过了什么？

Answer 1

内衬不是解决一般尾呼消除问题的办法，原因有几个。以下清单并不是详尽无遗的。然而，它是被分类的--它以一个不方便开始，以一个完整的显示停止结束。

1. 在尾位置调用的函数可能是大型函数，在这种情况下，从性能角度来看，内联可能不可取。
2. 假设在g中有多个f尾调用。根据内联的常规定义，您必须在每个调用站点内联g，这可能会使f变得巨大。如果您选择goto开始g，然后跳回来，那么您需要记住跳转到哪里，突然之间，您将维护自己的调用堆栈片段(与“真正的”调用堆栈相比，这几乎肯定会显示出较差的性能)。
3. 对于相互递归的函数f和g，您必须在g中内联f，在f中嵌入g。显然，根据通常的内衬定义，这是不可能的。因此，您将得到实际上是自定义的函数内调用约定(如上文2.的goto-based方法中的那样)。
4. 真正的TCE工作在尾位置的任意调用，包括在高阶上下文中： (defn say-foo-then call Foo! (f)) 在某些情况下，这可以产生很大的效果，显然不能用内衬来模仿。

Answer 2

1. 这可能令人惊讶，而且可能会使调试更加困难，因为您看不到调用堆栈。
2. 它只在非常特殊的情况下工作，而不是在VM支持TCO时处理的一般情况。
3. 程序员通常不会递归地编写代码尾，除非语言给了他们这样做的动机。例如，递归阶乘通常用递归步骤编写为n * fact(n-1)，而不是尾递归。

Answer 3

TCO本身不需要VM支持。也就是说，不是为了当地的活动。跨越外部函数的尾调用需要VM支持。理想情况下，完全实现尾递归允许单独编译的程序单元中的函数在常量空间中相互递归，不仅是父函数的本地函数，或者编译器同时可见的函数。

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

无需VM支持，可以使用非本地返回和调度来模拟尾呼叫消除。也就是说，当一个尾调用在语法上发生时，它被转换成一个非本地返回，该返回通过动态控制传输放弃当前函数，将参数(可能打包为一个对象)传递到一个隐藏的调度循环，该循环将控制传递给目标函数，并将这些参数传递给它。这将实现递归在恒定空间中发生的要求，并将“外观和感觉”类似于尾调用。然而，这是缓慢的，也许不是完全透明的。