C# 不发出“尾部”是否存在技术原因？ CIL指令？

Question

可能的重复：
为什么.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# 的语言支持此功能时，我会遇到哪些挑战或会引入哪些限制。

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

Answer 1

检查以下链接

为什么 .NET/C# 不针对 tail 进行优化-调用递归？
/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# 编译器程序管理器）并从上一个链接复制

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

尽管如此，我们仍会继续关注这一点，并且可能会在未来的版本中
编译器找到一些有意义的模式来发出 .tail 指令。

Answer 2

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

博客文章 Hans 链接评论中的 to 可能会涵盖他的一些想法，但我确信还有更多：

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

---

现在回到我自己的想法：

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

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

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

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

在应用尾部调用之前需要满足一长串条件。从编码员的角度来看，其中很多都不是简单的猜测。

如果在某些情况下使用递归是安全的，那就太好了，这是绝对正确的 - 但我相信只有在可以保证安全的情况下才是这种情况。如果 95% 的情况下是安全的，但 5% 的情况很难预测，那么我们就会遇到大量“在我的机器上运行”的错误。

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

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