Ruby是否执行尾调用优化？

Question

函数式语言通常使用递归解决许多问题，因此其中许多语言都执行尾调用优化（TCO）。尾调用优化使得从另一个函数（或者是自身，在这种情况下该特性也被称为尾递归消除，它是TCO的一个子集）调用一个函数在该函数的最后一步不需要新的堆栈帧，从而减少开销和内存使用。

Ruby 显然从函数式语言中“借鉴”了许多概念（例如 lambda 表达式、像 map 等的函数等），这使我很好奇：Ruby 是否执行尾调用优化？

- Charlie Flowers

Answer 1

不，Ruby 没有支持TCO。然而，它也没有不支持 TCO。

Ruby 语言规范并没有关于TCO的说明。规范没有要求你必须支持它，但也没有说你不能支持它。只是你不能依赖TCO。

这与 Scheme 不同，Scheme 语言规范要求所有实现必须支持TCO。但这也与 Python 不同，Guido van Rossum 多次明确表示（最近几天刚刚提到），Python 实现不应该支持TCO。

Yukihiro Matsumoto 对 TCO 是持支持态度的，他只是不想强制 所有 实现都支持它。不幸的是，这意味着你不能依赖 TCO，或者如果你依赖它，你的代码将无法在其他 Ruby 实现中移植。

因此，一些 Ruby 实现支持TCO，但大多数不支持。例如，YARV 支持TCO，虽然（目前）你需要在源代码中显式取消注释一行，并重新编译VM才能启用TCO - 在未来版本中，TCO将默认开启，待实现证明稳定性。Parrot 虚拟机本身支持TCO，因此 Cardinal 也可以很容易地支持它。CLR 对 TCO 有一些支持，这意味着 IronRuby 和 Ruby.NET 也可能支持它。Rubinius 也可能支持 TCO。

但 JRuby 和 XRuby 不支持 TCO，而且除非 JVM 本身支持 TCO，否则它们可能不会支持。问题在于：如果你想要一个快速的实现，并且与 Java 的集成也快速又无缝，则应该与 Java 兼容并尽可能地使用 JVM 的堆栈。你可以通过跳板或显式传递 continuation 方式很容易地实现 TCO，但那样就不能再使用 JVM 堆栈了，这意味着每次你想要从 Ruby 调用 Java 或者从 Java 调用 Ruby 时，都需要执行某种转换，这会导致速度变慢。因此，XRuby 和 JRuby 选择了速度和 Java 集成而不是 TCO 和 continuation（基本上有相同的问题）。

这适用于所有想要紧密集成到某些不原生支持 TCO 的主机平台中的 Ruby 实现。例如，我猜 MacRuby 也将面临同样的问题。

- Jörg W Mittag

---

我可能错了（如果是这样，请启发我），但我怀疑在真正的面向对象语言中，尾调用优化并没有任何意义，因为尾调用必须能够重用调用者的堆栈帧。由于在运行时不知道哪个方法将被消息发送调用，因此似乎很难确保（也许通过类型反馈JIT，或强制所有消息的实现者使用相同大小的堆栈帧，或将TCO限制为相同消息的自我发送...）。 - Damien Pollet

这是一个很好的回应。那些信息在谷歌上不容易找到。有趣的是yarv支持它。 - Charlie Flowers

Damien，原来真正的面向对象语言需要TCO支持。请见http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion。不用太担心堆栈框架的问题：可以合理设计堆栈框架，使其与TCO协同工作。 - Tony Garnock-Jones

tonyg将GLS的引用帖子从消失中保存下来，并在此处进行了镜像：http://www.eighty-twenty.org/index.cgi/tech/oo-tail-calls-20111001.html - Frank Shearar

我似乎找不到TCO的任何缺点，为什么Python强制执行“不要”实现它？ - karatedog

Answer 2

更新：这里有一篇关于Ruby中尾调用优化的很好的解释：http://nithinbekal.com/posts/ruby-tco/

更新：你可能还想看看tco_method gem：http://blog.tdg5.com/introducing-the-tco_method-gem/

在 Ruby MRI（1.9、2.0和2.1）中，你可以通过以下方式开启TCO:

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

有一个提议在Ruby 2.0中默认启用尾调用优化。它还解释了一些相关的问题：Tail call optimization: enable by default?.

以下是链接中的简短摘录：

通常，尾递归优化包括另一种优化技术 - "调用"到"跳转"的转换。在我看来， 在Ruby的世界中识别“递归”很困难，因此应用该优化也会比较困难。

接下来是一个示例。else子句中的fact()方法调用不是“尾调用”。

def fact(n) 
  if n < 2
    1 
 else
   n * fact(n-1) 
 end 
end

如果你想在fact()方法中使用尾调用优化，你需要按照以下方式更改fact()方法（采用传递续体的样式）。

def fact(n, r) 
  if n < 2 
    r
  else
    fact(n-1, n*r)
  end
end

- Ernest

Answer 3

它可能具有以下特性，但不能保证：

https://bugs.ruby-lang.org/issues/1256

- Steve Jessop

---

目前该链接已失效。 - karatedog

@karatedog：谢谢，已更新。不过说实话，这个参考文献可能已经过时了，因为该错误已经存在五年了，而且同一主题上已经有了新的活动。 - Steve Jessop

是的 :-) 我刚刚阅读了关于这个主题的内容，并且我看到在 Ruby 2.0 中可以从源代码中启用它（不再需要C源代码修改和重新编译）。 - karatedog

Answer 4

在编译之前，可以通过调整vm_opts.h中的几个变量来编译TCO: https://github.com/ruby/ruby/blob/trunk/vm_opts.h#L21

// vm_opts.h
#define OPT_TRACE_INSTRUCTION        0    // default 1
#define OPT_TAILCALL_OPTIMIZATION    1    // default 0

- Christopher Kuttruff

Answer 5

这基于Jörg和Ernest的回答。基本上这取决于实现方式。

我无法让Ernest的答案在MRI上运行，但是它是可行的。 我发现这个例子适用于MRI 1.9到2.1。这应该会打印一个非常大的数字。如果您不将TCO选项设置为true，则应该会收到“堆栈太深”的错误。

source = <<-SOURCE
def fact n, acc = 1
  if n.zero?
    acc
  else
    fact n - 1, acc * n
  end
end

fact 10000
SOURCE

i_seq = RubyVM::InstructionSequence.new source, nil, nil, nil,
  tailcall_optimization: true, trace_instruction: false

#puts i_seq.disasm

begin
  value = i_seq.eval

  p value
rescue SystemStackError => e
  p e
end

- Kelvin