Adventures in F#--Tail Recursion in Three Languages

Adventures in F#--Tail Recursion in Three Languages

  • Comments 12

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.

Leave a Comment
  • Please add 5 and 4 and type the answer here:
  • Post
  • Hi Jomo,

    I posted about this topic (C# -> CLI/IL) somewhere in the past, so I though it might be useful for your readers to check this link out as well:

    http://community.bartdesmet.net/blogs/bart/archive/2006/09/22/4463.aspx

    -Bart

  • Intresting post. I always thought that F# used something like "OpCodes.Tailcall" (see http://msdn2.microsoft.com/en-us/library/system.reflection.emit.opcodes.tailcall(VS.80).aspx) since that makes it possible to also optimize cases like:

    let f1 a

     do print a

     f2 a

    let f2 a

     do print a

     f1 a

    f1 1

  • Re: your last paragraph. Since C# is making the functional model available, will you be considering including this tail-call optimisation in future versions?

  • Samuel,

    There was some enthusiasm for this the last time I brought it up with Doctor T (http://blogs.msdn.com/madst/default.aspx).

    The optimization won't be in Orcas for sure. Beyond that, I can't say. If we did do it, I still think it makes sense to do it in the jitter.

  • Jomo Fisher--In a prior post I touched on recursion in F#. One of the comments was about mutually recursive

  • Hi Jomo,

    Like most of us, I followed a link from the official C# Visual page to your post. Discovered your "Adventures in F#" series. Very good. Is there a link between C# & F# ?

    The technical answer is threefold : generics, LINQ and lambda. The corporate answer is : both issued by microsoft. The networking answer is : people are supposed to know each other (Don Syme from F# has worked on generics ; the new feature of C#2 3 years ago).

    So my question is : as a member of C# team, you seem to depict your "adventures" as if it was in a foreign world. Are you this lonesome cowboy/pionneer visiting a desolated valley ?

    Please take your phone, call F# team for a meeting, set up a high return best-of-both-worlds project and be the main contributor of C#4.

    We, C# end users, are delighted by C#3 in beta 2 : LINQ, var, lambda. It simplifies the code (shorter/less verbose) and makes it more robust. We expect another simplification in delegates, interfaces, inheritance, polymorphism, virtuals,is/as. In short : level 2 concepts of Object/Classes programming. Ocaml team did not do too well with objects (it was 15 years ago). Will you do better ?

    Thanks for your fantastic work.

    Chris

  • Regardless of where it technically is done, the C# spec needs to explicitly say that tail calls will be optimized out, otherwise it's a nearly useless feature since we can't rely on it.

  • Jomo Fisher--Up until now, I've been avoiding using F# with the VS IDE. I've been using notepad.exe and

  • Immutability and tail recursion

  • In my previous post , I talked about some of the basics of recursion and why you might want to use it

  • In my previous post , I talked about some of the basics of recursion and why you might want to use it

  • In my previous post , I talked about some of the basics of recursion and why you might want to use it

Page 1 of 1 (12 items)