B# .NET Blog

Introduction

You might have hear about the concept of a tail call already. It's already quite some time ago I found myself browsing through the entire ECMA 335 spec of the CLI (to be precise, from mid July this summer for some Rotor 2.0 experiments). A few days ago however, I was playing around with F# (Wikipedia) again, triggered by two Channel 9 videos of Mike Hall interviewing Don Syme (blog) (Don has been involved in .NET generics in the FX 2.0 timeframe). Basically, F# is a modern variant of ML languages running on the CLR, created by the Microsoft Research folks. Watch the Channel 9 videos here and there. Back to the original subject: tail calls.

Tail calls are - how can you guess? - calls at the tail of a method. Let's start by taking a look at the concept of a call. Normally a call instruction (call, calli, callvirt) grows the stack. That is, the current method's state is kept and a new activation frame is pushed on the call stack which is used by the called method. Just try this one:

class So
{
   public static void Main()
   {
      Main();
   }
}

No wonder it will crash with a "Process is terminated due to StackOverflowException" message (on my machine after approx. 80,000 calls). (Quiz: Is there any way to catch this exception? Why? Why not? Tip: The answer is very close.)

This code emits a simple call instruction:

A tail call on the other hand releases the current stack frame before making the call, therefore keeping the stack low. This is a common 'requirement' in dynamic languages (which C# isn't but F# has chacteristics of this). This means that after a tail call nothing else than the ret instruction should appear in the current method ("Call Terminates Current Method", ECMA 335 - Partition III - 2.1).

Ildasm the executable compiled out of the previous piece of code and patch it as follows (red = drop; green = add):

.class private auto ansi beforefieldinit So
       extends [mscorlib]System.Object
{
  .method public hidebysig static void  Main() cil managed
  {
    .entrypoint
    // Code size       8 (0x8)
    .maxstack  8
    IL_0000:  nop
    IL_0001:  tail. call       void So::Main()
    IL_0006:  nop
    IL_0007:  ret
  } // end of method So::Main

Then ilasm again. Now the app will run till the end of times.

I agree that this sample isn't particularly useful (not to say it's worth just nothing :-)) but I thought it might be useful to some of you to know a) what a tail call is; b) that it is supported by the CLI/CLR; c) how cool dynamic languages should be...

Tip: for a more useful (or better: less useless) example, take a look at Partition V of ECMA 335 which contains an example of tail calls. It's basically the equivalent of this piece of C# (but which doesn't run out of stack space):

class EvenOdd
{
   static bool IsEven(int n)
   {
      if (n == 0)
         return true;
      else
         return IsOdd(n-1);
   }

   static bool IsOdd(int n)
   {
      if (n == 0)
         return false;
      else
         return IsEven(n-1);
   }

   static void Main()
   {
      Console.WriteLine(IsEven(1000000));
   }
}

It might be a good exercise for anyone who has time left to try to patch the IL of this program to use tail calls (== not straightforward).

C ya in the F# universe soon?