26

可能重复：
为什么 .net/C# 不消除尾递归？

采用以下 C# 代码：

using System;

namespace TailTest
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Counter(0);
        }

        static void Counter(int i)
        {
            Console.WriteLine(i);
            if (i < int.MaxValue) Counter(++i);
        }
    }
}

C# 编译器（无论如何都是我的）会将 Counter 方法编译为以下 CIL：

.method private static hidebysig default void Counter (int32 i) cil managed 
{
.maxstack 8
IL_0000:  ldarg.0 
IL_0001:  call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006:  ldarg.0 
IL_0007:  ldc.i4 2147483647
IL_000c:  bge IL_0019
IL_0011:  ldarg.0 
IL_0012:  ldc.i4.1 
IL_0013:  add 
IL_0014:  call void class TailTest.MainClass::Counter(int32)
IL_0019:  ret 
}

上面代码的问题是它会导致堆栈溢出（在我的硬件上大约 i=262000）。为了解决这个问题，一些语言执行所谓的尾调用消除或尾调用优化 (TCO)。本质上，它们将递归调用变成了循环。

我的理解是 .NET 4 JIT 的 64 位实现现在执行 TCO 并避免像上面的 CIL 这样的代码溢出。但是，32 位 JIT 没有。Mono 似乎也没有。有趣的是，JIT（在时间和资源压力下）实现了 TCO，而 C# 编译器却没有。我的问题是为什么 C# 编译器本身没有更多的 TCO 意识？

有一条 CIL 指令告诉 JIT 执行 TCO。例如，C# 编译器可以生成以下 CIL：

.method private static hidebysig default void Counter (int32 i) cil managed 
{
.maxstack 8
IL_0000:  ldarg.0 
IL_0001:  call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006:  ldarg.0 
IL_0007:  ldc.i4 2147483647
IL_000c:  bge IL_001c
IL_0011:  ldarg.0 
IL_0012:  ldc.i4.1 
IL_0013:  add 
IL_0014:  tail.
IL_0017:  call void class TailTest.MainClass::Counter(int32)
IL_001c:  ret 
}

与原始代码不同的是，即使在 32 位 JIT（.NET 和 Mono）上，此代码也不会溢出并且会运行完成。神奇之处在于tail.CIL 指令。像 F# 这样的编译器会自动生成包含该指令的 CIL。

所以我的问题是，C# 编译器不这样做是否有技术原因？

我知道它在历史上可能只是不值得。类似的代码Counter()在惯用的 C# 和/或 .NET 框架中并不常见。您可以轻松地将 C# 的 TCO 视为不必要的或过早的优化。

随着 LINQ 和其他东西的引入，似乎 C# 和 C# 开发人员都在朝着更多功能的方向发展。因此，如果使用递归不是一件不安全的事情，那就太好了。但我的问题确实是一个更具技术性的问题。

我错过了一些使 TCO 这样的 C# 的坏主意（或冒险的主意）的东西。还是有什么东西让正确的事情变得特别棘手？这确实是我希望理解的。有什么见解吗？

编辑：感谢您提供的重要信息。我只是想明确一点，我并不是在批评缺乏甚至要求这个功能。我对围绕优先级的合理性不是很感兴趣。我的好奇心是我可能无法察觉或理解的哪些障碍使这成为一件困难、危险或不受欢迎的事情。

也许不同的上下文将有助于集中对话......

假设我要在 CLR 上实现我自己的类 C# 语言。为什么我不（除了机会成本）包括“尾巴”的自动和透明发射。指令在哪里合适？在非常像 C# 的语言中支持此功能时，我会遇到哪些挑战或会引入哪些限制。

再次（并提前）感谢您的回复。

4

2 回答 2

12

检查以下链接

为什么 .NET/C# 不针对尾调用递归进行优化？ /491463#491463
http://social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/67b6d908-8811-430f-bc84-0081f4393336?StatusCode=1
https://connect.microsoft.com/VisualStudio /feedback/ViewFeedback.aspx?FeedbackID=166013&wa=wsignin1.0

以下语句是 MS 官方（Luke Hoban Visual C# Compiler Program Manager）并从上一个链接复制

谢谢你的建议。在 C# 编译器的开发过程中，我们考虑过在多个点发出尾调用指令。然而，到目前为止，有一些微妙的问题促使我们避免这种情况：1) 在 CLR 中使用 .tail 指令实际上存在不小的开销成本（它不仅仅是一个跳转指令，因为尾调用最终会变成在许多不太严格的环境中，例如对尾调用进行了高度优化的函数式语言运行时环境）。2) 很少有真正的 C# 方法发出尾调用是合法的（其他语言鼓励具有更多尾递归的编码模式，许多严重依赖尾调用优化的人实际上会进行全局重写（例如继续传递转换）以增加尾递归的数量）。3) 部分由于 2)，C# 方法由于本应成功的深度递归而堆栈溢出的情况相当罕见。

综上所述，我们继续关注这一点，我们可能会在编译器的未来版本中找到一些发出 .tail 指令有意义的模式。

于 2011-08-17T16:24:57.347 回答
7

好问题。我没有具体的答案，但我有一些你可能会觉得有趣的想法。（之前有人告诉我，我不应该发布诸如答案之类的东西，但是嘿......）Yahia 的答案看起来是你可能得到的最明确的答案，尽管我也会联系 Eric Lippert 看看是否他想插话。

汉斯在评论中链接到的博客文章的一部分可能会涵盖他的一些想法，但我相信还有更多：

我被问到“为什么 C# 不实现功能 X？” 每时每刻。答案总是一样的：因为从来没有人设计、指定、实施、测试、记录和发布该功能。所有这六件事都是使功能发生所必需的。所有这些都花费了大量的时间、精力和金钱。功能并不便宜，鉴于我们有限的时间、精力和金钱预算，我们非常努力地确保我们只发布那些为我们的用户带来最大利益的功能。

现在回到我自己的想法：

我怀疑它从来都不是优先事项，但有一个很好的理由不要对此过于狂热：如果开发人员要依赖它，它需要得到保证。你写了：

因此，如果使用递归不是一件不安全的事情，那就太好了。但我的问题确实是一个更具技术性的问题。

现在，查看解释何时应用尾调用优化的博客文章。那是在 2007 年，它明确指出：

请注意，这些语句适用于 JIT，就像 Grant 和 Fei 查看代码库时一样，并且很容易随心所欲地更改。您不得依赖此行为。仅将这些信息用于您自己的个人娱乐。

然后，在应用尾调用之前需要一长串条件。从编码人员的角度来看，其中很多都是非平凡的猜测。

如果在某些情况下使用递归是安全的，那你是绝对正确的——但我相信只有在可以保证安全的情况下才会出现这种情况。如果它在 95% 的情况下是安全的，但 5% 的情况很难预测，那么我们就会遇到一大堆“在我的机器上工作”的错误。

我想要的是 C# 语言允许我陈述尾调用优化的要求。然后编译器可以验证它是否正确，并且理想情况下提供的不仅仅是提示JIT 需要此行为。基本上，如果我要以某种不受控制的方式递归，我最好知道它会起作用。你能想象垃圾收集是否只在某些配置中启用？哎呀！

所以 +1 尾递归是一个有用的概念，但我认为我们需要语言、JIT和编译器的更多支持才能真正被认为是“安全的”。

于 2011-08-17T16:31:03.250 回答