93

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

Ruby 显然从函数式语言中“借用”了一些概念（lambda、map 等函数等），这让我很好奇：Ruby 是否执行尾调用优化？

4

5 回答 5

131

不，Ruby 不执行 TCO。但是，它也不执行 TCO。

Ruby 语言规范没有提及 TCO。它没有说你必须这样做，但也没有说你不能这样做。你不能依赖它。

这与 Scheme 不同，Scheme 中语言规范要求所有实现都必须执行 TCO。但它也与 Python 不同，Guido van Rossum 在 Python 中多次明确表示（上一次是几天前）Python 实现不应该执行 TCO。

Yukihiro Matsumoto 很同情 TCO，他只是不想强迫所有实现都支持它。不幸的是，这意味着您不能依赖 TCO，否则，您的代码将不再可移植到其他 Ruby 实现。

因此，一些 Ruby 实现执行 TCO，但大多数不执行。例如，YARV 支持 TCO，尽管（目前）您必须明确取消注释源代码中的一行并重新编译 VM，以激活 TCO——在未来的版本中，它将默认启用，在实现证明之后稳定的。Parrot 虚拟机本身支持 TCO，因此 Cardinal 也可以很容易地支持它。CLR 对 TCO 有一些支持，这意味着 IronRuby 和 Ruby.NET 可能会做到这一点。鲁比尼乌斯也可能做到这一点。

但是 JRuby 和 XRuby 不支持 TCO，而且它们可能不会，除非 JVM 本身获得对 TCO 的支持。问题是这样的：如果你想有一个快速的实现，和Java的快速无缝集成，那么你应该与Java堆栈兼容，并尽可能使用JVM的堆栈。您可以很容易地使用蹦床或显式延续传递样式实现 TCO，但是您不再使用 JVM 堆栈，这意味着每次您想调用 Java 或从 Java 调用 Ruby 时，都必须执行某种转换，很慢。因此，XRuby 和 JRuby 选择了速度和 Java 集成，而不是 TCO 和延续（基本上有相同的问题）。

这适用于希望与某些不支持原生 TCO 的主机平台紧密集成的所有 Ruby 实现。例如，我猜 MacRuby 也会遇到同样的问题。

于 2009-05-05T13:21:34.130 回答
43

更新：这里对 Ruby 中的 TCO 进行了很好的解释：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 中默认开启 TCO。它还解释了随之而来的一些问题：尾调用优化：默认启用？

链接的简短摘录：

通常，尾递归优化包括另一种优化技术——“调用”到“跳转”翻译。在我看来，很难应用这种优化，因为在 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
于 2012-11-12T19:46:40.507 回答
12

它可以具有但不保证：

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

于 2009-05-05T12:09:19.607 回答
4

TCO 也可以通过在编译前调整 vm_opts.h 中的几个变量来编译： 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
于 2014-03-12T20:26:14.560 回答
2

这建立在 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
于 2014-05-02T20:54:59.670 回答