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: .NET Framework v2.0, C# 2.0