Jomo Fisher -- Sharp Things

Adventures in F#--Tail Recursion in Three Languages

Jomo Fisher—Here’s the F# I'm looking at today:

#light
let rec f n =
    do printf "%d\n" n
    f (n+1)

f 1

This defines a recursive function 'f' that takes a value 'n' as a parameter. This function prints the value of n to the console and then calls itself with n+1. So we've defined a function that will count up for a long time.

The question is, in what manner does this program end?

There are plenty of possibilities. The value of n must have a type and types always have physical limitations. A 32-bit number will overflow eventually, for example. If it overflows and arithmetic is checked, then it will throw an exception and that would end the program. If arithmetic isn't checked then the value will wrap around to the lowest value of the type, forming a never-ending loop. In this case, the program's ultimate fate is CTRL+C.

If the type of n is something with an arbitrary number of digits then perhaps the program could count up until memory on the machine is exhausted with holding information about the number. Though before this happened the machine would disintegrate along with the heat-death of the universe in a few trillion years. Probably way before that happened I would press CTRL+C.

Programmers accustomed to recursion may propose a more down-to-earth possibility. That the stack will overflow quickly and the subsequent exception will end the program.

Tail Recursion in C#

To see what I mean about stack overflow. Here's a hand-written transliteration of the F# above into C#:

    class Program {
        static void f(int n) {
            Console.WriteLine(n);
            f(n + 1);
        }

        static void Main(string[] args) {
            f(1);
        }
    }

On my 32-bit Vista machine, this counts up to 119922 and then throws a StackOverFlowException. On the other hand, if I run exactly the same executable on a 64-bit machine then it will run indefinitely, eventually looping back around to Int32.Min and continuing on from there until I press CTRL+C . There's a reason for this, and its not because there's more stack space on the 64-bit machine (though there is). I'll come back to this point later.

Tail Recursion in F#

If you run the F# I originally posed, it will run indefinitely on both 32-bit and 64-bit machines. To understand why, I'll disassemble that F# into C# using Lutz Roeder's reflector and render it into equivalent C#:

    public static T f<T>(int n) {
        while (true) {
            var fmt = new Format<FastFunc<int, Unit>, TextWriter, Unit, Unit>("%d\n");
            Printf.fprintf<FastFunc<int, Unit>>(Console.Out, fmt).Invoke(n);
            n++;
        }
    }

First, that Format business is just the printf in the loop. I'm a little surprised that the allocation of 'fmt' isn't lifted out of the loop. Note to self to investigate this later.

Setting that aside, the function which was written as recursive as been tranformed by the F# compiler into one with no recursion--its just a while loop. This is why there's no stack overflow in F#. This translation by the compiler is called the Tail Call Optimization.

Tail Recursion in C++\CLI

To get one more data point, let's look at the same function transliterated into C++\CLI:

    void f(int n) {
        printf("%d\n", n);
        f(n+1);
    }

    void main(){
        f(1);
    }

This will give you a nice warning:

warning C4717: 'f' : recursive on all control paths, function will cause runtime stack overflow

True to its word, if you execute the resulting code on either 32 or 64-bit machines you will get a stack overflow.

If you turn on full optmization in C++ (/Ox) you will still get the warning, but inspection under reflector shows that you will never actually get a stack overflow:

public private: static void __gc* modopt(CallConvCdecl __gc*) f(Int32 __gc* n)
{
    while (true)
    {
        <Module>::printf(&<Module>::?A0xdb2783a0.unnamed-global-0, n);
        n++;
    }
} 

As you can see, the C++ compiler has done the tail call optimization in this case.

Why the Difference Between 32 and 64 Bit?

There are some nagging questions left. Why does the C# version not overflow the stack under 64-bit when no tail recursion optimization is done by the compiler?

The missing piece is that, for managed code, there is a second chance to optimize. This is at JIT time or NGEN time. It turns out that the 64-bit jitter will do the tail call optimization on the raw IL and the 32-bit version doesn't (at least right now).

This raises a second question. Why did the unoptimized C++\CLI version overflow the stack on 64-bit machines? The reason is more mundane here: the C# project system targets AnyCPU by default while the C++ project system targets x86. If you run an x86-targetted .exe on a 64-bit machine it will still use the 32-bit jitter. If you change the C++ project to target 64-bit then you will get the tail optimized result.

Compiler Design Choices

So which compiler is doing it the right way? I think they all are. For C# applications tail recursion is relatively rare. Leaving the optimizing to the jitter to do or not makes sense--a better jitter benefits all managed languages. This tradeoff frees up the C# team to focus on things like LINQ. On the other hand, C++ already had a world-class optimizer available. It's a clear win to make as much of this optimizer work for C++\CLI as possible. Finally, tail recursion is very common when programming under the functional paradigm which is where you'd like to spend much of your time in F#. Without this optimization in the compiler itself, F# would be significantly crippled on 32-bit machines.

This posting is provided "AS IS" with no warranties, and confers no rights.