Ruby是否执行尾部呼叫优化？ [英] Does Ruby perform Tail Call Optimization?

问题描述

功能性语言导致使用递归来解决很多问题，因此其中很多都执行尾部呼叫优化（TCO）。作为该功能的最后一步，TCO会导致从另一个函数（或其本身，在这种情况下，此功能也称为尾递归消除，这是TCO的子集）对函数的调用，因为不需要新的堆栈帧，这可以减少开销和内存使用。Ruby显然已经从功能语言（lambdas，函数如map等等）中借用了一些概念，这些概念来自于函数式语言让我好奇：Ruby是否执行tail调用优化？

解决方案

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

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

这不像Scheme，Language Specification 需要 all 实现必须执行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的堆栈。你可以很容易地用蹦床或明确的继续传递方式实现TCO，但是你不再使用JVM栈，这意味着每次你想调用Java或者从Java调用到Ruby时，都必须执行某种转换，这是缓慢的。所以，XRuby和JRuby选择在TCO和延续（基本上都有相同的问题）上进行速度和Java集成。

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

Functional languages lead to use of recursion to solve a lot of problems, and therefore many of them perform Tail Call Optimization (TCO). TCO causes calls to a function from another function (or itself, in which case this feature is also known as Tail Recursion Elimination, which is a subset of TCO), as the last step of that function, to not need a new stack frame, which decreases overhead and memory usage.

Ruby obviously has "borrowed" a number of concepts from functional languages (lambdas, functions like map and so forth, etc.), which makes me curious: Does Ruby perform tail call optimization?

解决方案

No, Ruby doesn't perform TCO. However, it also doesn't not perform TCO.

The Ruby Language Specification doesn't say anything about TCO. It doesn't say you have to do it, but it also doesn't say you can't do it. You just can't rely on it.

This is unlike Scheme, where the Language Specification requires that all Implementations must perform TCO. But it is also unlike Python, where Guido van Rossum has made it very clear on multiple occasions (the last time just a couple of days ago) that Python Implementations should not perform TCO.

Yukihiro Matsumoto is sympathetic to TCO, he just doesn't want to force all Implementations to support it. Unfortunately, this means that you cannot rely on TCO, or if you do, your code will no longer be portable to other Ruby Implementations.

So, some Ruby Implementations perform TCO, but most don't. YARV, for example, supports TCO, although (for the moment) you have to explicitly uncomment a line in the source code and recompile the VM, to activate TCO – in future versions it is going to be on by default, after the implementation proves stable. The Parrot Virtual Machine supports TCO natively, therefore Cardinal could quite easily support it, too. The CLR has some support for TCO, which means that IronRuby and Ruby.NET could probably do it. Rubinius could probably do it, too.

But JRuby and XRuby don't support TCO, and they probably won't, unless the JVM itself gains support for TCO. The problem is this: if you want to have a fast implementation, and fast and seamless integration with Java, then you should be stack-compatible with Java and use the JVM's stack as much as possible. You can quite easily implement TCO with trampolines or explicit continuation-passing style, but then you are no longer using the JVM stack, which means that everytime you want to call into Java or call from Java into Ruby, you have to perform some kind of conversion, which is slow. So, XRuby and JRuby chose to go with speed and Java integration over TCO and continuations (which basically have the same problem).

This applies to all implementations of Ruby that want to tightly integrate with some host platform that doesn't support TCO natively. For example, I guess MacRuby is going to have the same problem.

这篇关于Ruby是否执行尾部呼叫优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！