技术原因是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#不能优化尾调用递归？ / 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看看是否他想要加入.

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

我被问到"为什么C#不实现功能X？" 每时每刻.答案总是一样的:因为没有人设计,指定,实施,测试,记录和发送该功能.所有这六件事都是实现这一功能所必需的.所有这些都耗费了大量的时间,精力和金钱.功能并不便宜,我们非常努力地确保我们只提供那些能够为我们的用户提供最佳利益的功能,因为我们的时间,精力和预算都有限.

现在回到我自己的想法:

我怀疑它从来都不是优先事项,但是有充分的理由不对它过于苛刻:如果开发人员要依赖它,它需要得到保证.你写了:

因此,如果使用递归并不是一件不安全的事情,那就太好了.但我的问题实际上更具技术性.

现在,看看解释何时应用尾调优化的博客文章.那是在2007年,它明确指出:

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

然后在应用尾调用之前需要很长的条件列表.从编码人员的角度来看,很多都是非常重要的.

如果在某些情况下使用递归是安全的,那么你是绝对正确的 - 但我相信只有这样才能保证安全.如果它在95%的情况下是安全的,但是5%很难预测,我们会有一大堆"在我的机器上工作"的错误.

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

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