Is there a technical reason that C# does not issue the "tail." CIL instruction?

Question

Possible Duplicate:
Why doesn't .net/C# eliminate tail recursion?

Take the following C# code:

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);
        }
    }
}

The C# compiler (mine anyway) will compile the Counter method into the following 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 
}

The problem with the above code is that it will cause a stack overflow (at about i=262000 on my hardware). To get around this problem, some languages do what is called tail-call elimination or tail-call optimization (TCO). Essentially, they turn the recursive call into a loop.

My understanding is the the 64-bit implementation of the .NET 4 JIT now performs TCO and avoids the overflow on code like the above CIL. However, the 32-bit JIT does not. Mono does not seem to either. It is interesting that the JIT (which is under time and resource pressure) does TCO while the C# compiler does not. My question is why isn't the C# compiler itself more TCO aware?

There is a CIL instruction that tells the JIT to perform TCO. For example, the C# compiler could instead generate the following 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 
}

Unlike the original, this code will not overflow and will run to completion even on the 32-bit JIT (both .NET and Mono). The magic is in the tail. CIL instruction. Compilers like F# will generate CIL that includes this instruction automatically.

So my question is, is there a technical reason that the C# compiler does not do this?

I get that it has historically maybe just not been worth it. Code like Counter() has not been common in idiomatic C# and/or the .NET framework. You could easily view TCO for C# as an unnecessary or premature optimization.

With the introduction of LINQ and other things, it seems like both C# and C# developers are moving in more functional directions. So, it would be nice if using recursion was not such an unsafe thing to do. But my question is really a more technical one.

Am missing something that makes TCO like this a bad idea (or a risky one) for C#. Or is there something that makes it particularly tricky to get right? That is really what I am hoping to understand. Any insight?

EDIT: Thanks for the great information. I just wanted to be clear that I am not criticizing the lack of or even demanding this feature. I am not super interested in the rational around prioritization. My curiosity is what obstacles might I not perceive or understand that make this a difficult, dangerous, or undesirable thing to do.

Perhaps a different context will help focus the conversation...

Let's say I was going to implement my own C#-like language on the CLR. Why would I not (other than opportunity cost) include automatic and transparent emission of the 'tail.' instruction where appropriate? What challenges would I encounter or what constraints would I introduce in supporting this feature in a language very much like C#.

Thank you again (and in advance) for the responses.

Answer 1

check the following links

Why doesn't .NET/C# optimize for tail-call recursion? /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

The following statement is MS official (Luke Hoban Visual C# Compiler Program Manager) and copied from last link

Thanks for the suggestion. We've considered emiting tail call instructions at a number of points in the development of the C# compiler. However, there are some subtle issues which have pushed us to avoid this so far: 1) There is actually a non-trivial overhead cost to using the .tail instruction in the CLR (it is not just a jump instruction as tail calls ultimately become in many less strict environments such as functional language runtime environments where tail calls are heavily optimized). 2) There are few real C# methods where it would be legal to emit tail calls (other languages encourage coding patterns which have more tail recursion, and many that rely heavily on tail call optimization actually do global re-writing (such as Continuation Passing transformations) to increase the amount of tail recursion). 3) Partly because of 2), cases where C# methods stack overflow due to deep recursion that should have succeeded are fairly rare.

All that said, we continue to look at this, and we may in a future release of the compiler find some patterns where it makes sense to emit .tail instructions.

Answer 2

Good question. I don't have a concrete answer, but I have some thoughts you might find interesting. (I've been told before that I shouldn't post such things as answers, but hey...) Yahia's answer looks like the most definitive one you're likely to get, although I'll also ping Eric Lippert to see if he wants to chime in.

Part of the blog post Hans linked to in the comments will probably cover some of his thoughts, but I'm sure there are more:

I am asked "why doesn't C# implement feature X?" all the time. The answer is always the same: because no one ever designed, specified, implemented, tested, documented and shipped that feature. All six of those things are necessary to make a feature happen. All of them cost huge amounts of time, effort and money. Features are not cheap, and we try very hard to make sure that we are only shipping those features which give the best possible benefits to our users given our constrained time, effort and money budgets.

---

Now back to my own thoughts:

I suspect it's just never been a priority, but there's a good reason not to be too gung-ho about it: if developers are going to rely on it, it needs to be guaranteed. You wrote:

So, it would be nice if using recursion was not such an unsafe thing to do. But my question is really a more technical one.

Now, look at the blog post explaining when tail call optimizations are applied. That was back in 2007, and it explicitly states:

Note that these statements apply to the JITs as they were when Grant and Fei looked through the code base, and are prone to change at whim. You must not take dependencies on this behavior. Use this information for your own personal entertainment only.

There's then a long list of conditions which are required before tail calls will be applied. Plenty of those are non-trivial to guess from a coder's point of view.

You're absolutely right that it would be nice if using recursion was safe in certain circumstances - but I believe that's only the case if it could be guaranteed to be safe. If it were safe in 95% of cases but the 5% were hard to predict, we'd have a whole slew of "works on my machine" bugs.

What I would like is for the C# language to allow me to state a requirement of tail call optimization. The compiler could then verify that it's correct, and ideally provide more than just a hint to the JIT that this behaviour is required. Basically, if I'm going to recurse in a somewhat-uncontrolled manner, I'd better know it's going to work. Can you imagine if garbage collection were only enabled in some configurations? Eek!

So +1 to the idea of tail recursion being a useful concept, but I think we need more support from the language, the JIT and the compiler before it could truly be considered "safe".