Friday, September 22, 2006 11:35 PM bart

Some notes on the CLI tail call support (and some F# links)

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

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:

call void So::Main()

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?

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# re: Some notes on the CLI tail call support (and some F# links)

Saturday, September 23, 2006 12:29 AM by Can Erten

I really liked that post. Thank you for informing about Tail in CLR. Dynamic languages are just great.
By the way how to call CLR tail function (or whatever in CLR) from C#? Is it possible to use it by using Reflection.Emit namespace.
Thank you.

# re: Some notes on the CLI tail call support (and some F# links)

Saturday, September 23, 2006 6:50 PM by Jonathan de Halleux

# The Case of The Failed Demo – StackOverflowException on x64

Wednesday, July 07, 2010 2:35 AM by B# .NET Blog

Introduction A while ago I was explaining runtime mechanisms like the stack and the heap to some folks