Cha*_*ers 90 ruby functional-programming tail-recursion
功能语言导致使用递归来解决许多问题,因此许多函数执行尾调用优化(TCO).TCO导致从另一个函数调用函数(或者本身,在这种情况下,这个特性也称为Tail Recursion Elimination,它是TCO的一个子集),作为该函数的最后一步,不需要新的堆栈帧,这减少了开销和内存使用.
Ruby显然已经从函数式语言(lambdas,map等函数等)中"借用"了许多概念,这让我很好奇:Ruby是否执行尾调用优化？
Jör*_*tag 125
不,Ruby不执行TCO.然而,它也不会不执行TCO.
Ruby语言规范没有说明TCO.它并没有说你必须这样做,但它也没有说你不能这样做.你不能依赖它.
这与计划,其中语言规范要求的是所有的实现必须进行TCO.但它也与Python不同,Guido van Rossum在多个场合(最近一次仅仅是几天前)已经非常清楚Python实现不应该执行TCO.
Yukihiro Matsumoto对TCO表示同情,他只是不想强迫所有的实施支持它.不幸的是,这意味着您不能依赖TCO,或者如果您这样做,您的代码将不再可移植到其他Ruby实现.
因此,一些Ruby实现执行TCO,但大多数不执行.例如,YARV支持TCO,尽管(目前)你必须在源代码中明确取消注释一行并重新编译VM,以激活TCO - 在未来版本中,默认情况下,它将在实现证明之后启用稳定.Parrot虚拟机本身支持TCO,因此Cardinal也可以非常轻松地支持它.CLR对TCO有一些支持,这意味着IronRuby和Ruby.NET可能会这样做.Rubinius也可能会这样做.
但JRuby和XRuby不支持TCO,他们可能不会,除非JVM本身获得对TCO的支持.问题在于:如果您希望快速实现,并与Java快速无缝集成,那么您应该与Java堆栈兼容并尽可能使用JVM的堆栈.您可以使用trampolines或显式的continuation-passing方式轻松实现TCO,但是您不再使用JVM堆栈,这意味着每次要调用Java或从Java调用Ruby时,都必须执行某种类型的转换,这很慢.因此,XRuby和JRuby选择了速度和Java集成而不是TCO和延续(基本上有相同的问题).
这适用于想要与某些本身不支持TCO的主机平台紧密集成的Ruby的所有实现.例如,我猜MacRuby会遇到同样的问题.
Ern*_*est 42
更新:以下是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