为什么TCO需要VM的支持？ [英] Why does TCO require support from the VM?
问题描述
一些虚拟机，最着名的是JVM，据说不支持TCO。因此，像Clojure这样的语言需要用户改用 loop recur 。
Some VMs, most notably the JVM, are said to not support TCO. As a result, language like Clojure require the user to use loop recur instead.
但是，我可以重写自尾调用以使用循环。例如，这里是一个尾调用因子：
However, I can rewrite self-tail calls to use a loop. For example, here's a tail-call factorial:
def factorial(x, accum):
if x == 1:
return accum
else:
return factorial(x - 1, accum * x)
$ b b
这里是一个循环等价物：
Here's a loop equivalent:
def factorial(x, accum):
while True:
if x == 1:
return accum
else:
x = x - 1
accum = accum * x
这可以通过编译器完成（我已经写了宏）。对于相互递归，你可以简单地内联你调用的函数。
This could be done by a compiler (and I've written macros that do this). For mutual recursion, you could simply inline the function you're calling.
因此，鉴于你可以实现TCO而不需要任何VM，为什么不语言（例如Clojure，Armed Bear Common Lisp）这样做吗？我错过了什么？
So, given that you can implement TCO without requiring anything of the VM, why don't languages (e.g. Clojure, Armed Bear Common Lisp) do this? What have I missed?
推荐答案
由于多种原因，内联不是一般尾部调用消除问题的解决方案。下面的列表并不意味着详尽无遗。
Inlining is not a solution to the general tail call elimination problem for a number of reasons. The list below is not meant to be exhaustive. It is, however, sorted -- it starts with an inconvenience and ends with a complete showstopper.
-
在一个函数中调用的函数
A function called in a tail position may be a large one, in which case inlining it may not be advisable from a performance standpoint.
假设对<$ c有多个尾调用，则尾随尾数可能较大，因此从性能角度来看，内联可能不可取。 $ c> g 在 f 中。在内联的常规定义下，您必须在每个调用站点内联 g ，可能会使 f 巨大。如果你选择 goto 开头 g 然后跳回，那么你需要记住在哪里跳转并且突然之间你保持自己的调用堆栈片段（当与真实调用堆栈相比时，它几乎肯定会表现出较差的性能）。
Suppose there are multiple tail calls to g in f. Under the regular definition of inlining, you'd have to inline g at each call site, potentially making f huge. If instead you choose to goto the beginning of g and then jump back, then you need to remember where to jump to and all of a sudden you're maintaining your own call stack fragment (which will almost certainly exhibit poor performance when compared to the "real" call stack).
对于相互递归函数 f 和 g ，你必须内联 f 中 g 和 g 。显然，在内联的通常定义下这是不可能的。所以，你剩下的是什么是有效的自定义函数内调用约定（如上面的 goto 的方法）。
For mutually recursive functions f and g, you'd have to inline f in g and g in f. Clearly this is impossible under the usual definition of inlining. So, you're left with what's effectively a custom in-function calling convention (as in the goto-based approach to 2. above).
Real TCE适用于尾随位置中的任意调用，包括在高阶上下文中：
Real TCE works with arbitrary calls in tail position, including in higher-order contexts:
(defn say-foo-then-call [f]
(println "Foo!")
(f))
这在某些情况下可以有很好的效果，显然不能用内联模拟。
This can be used to great effect in certain scenarios and clearly cannot be emulated with inlining.
这篇关于为什么TCO需要VM的支持？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
