为什么TCO需要VM的支持？

Question

据说一些虚拟机,尤其是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)呢？我错过了什么？

Answer 1

由于许多原因,内联不是一般尾部呼叫消除问题的解决方案.以下列表并非详尽无遗.然而,它是排序的 - 它开始带来不便,并以完整的showstopper结束.

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

2. 假设有多个尾调用,以g在f.在内联的常规定义下,您必须g在每个呼叫站点内联,可能会产生f巨大的影响.相反,如果您选择goto开始g然后再跳回,那么您需要记住跳转到哪里,突然之间您将维护自己的调用堆栈片段(与"真实"相比,这几乎肯定会表现出较差的性能"调用堆栈".

3. 对于相互递归函数f和g,你必须内嵌f在g和g中f.显然,根据通常的内联定义,这是不可能的.所以,你留下的是一个有效的自定义函数调用约定(如goto上面的基于2.的方法).

4. Real TCE在尾部位置使用任意调用,包括在高阶上下文中:

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

   这可以在某些情况下用于很好的效果,显然不能用内联模拟.