Does "Anonymous Recursion" work in .NET? It does in Mono

Question

I surfed into this site a few days ago on "Anonymous Recursion in C#". The thrust of the article is that the following code will not work in C#:

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

The article then goes into some detail about how to use currying and the Y-combinator to get back to "Anonymous Recursion" in C#. This is pretty interesting but a tad complex for my everyday coding I am afraid. At this point at least...

I like to see stuff for myself so I opened the Mono CSharp REPL and entered that line. No errors. So, I entered fib(8);. Much to my great surprise, it worked! The REPL replied back with 21!

I thought maybe this was some magic with the REPL, so I fired-up 'vi', typed in the following program, and compiled it.

using System;

public class Program
{
    public static void Main(string[] args)
    {
        int x = int.Parse(args[0]);
        Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
        Console.WriteLine(fib(x));
    }
}

It built and ran perfectly too!

I am running Mono 2.10 on a Mac. I do not have access to a Windows machine right now so I cannot test this on .NET on Windows.

Has this been fixed on .NET as well or is this a silent feature of Mono? The article is a couple of years old.

If it is Mono only, I cannot wait for the next job interview where they ask me to write a Fibinocci function in the language of my choice (Mono C#) where I have to provide the caveat that .NET will not work. Well, actually I can wait since I love my job. Still, interesting...

Update:

Mono is not really doing "anonymous" recursion as it is using fib as a named delegate. My bad. The fact that the Mono C# compiler assumes a null value for fib before assignment is a bug as noted below. I say "compiler" because the .NET CLR would run the resulting assembly just fine even though the .NET C# compiler would not compile the code.

For all the interview Nazis out there:

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

can be replaced with an iterative version:

Func<int, int> fib = n => 
{
    int old = 1;
    int current = 1;
    int next;

    for (int i = 2; i < n; i++)
    {
        next = current + old;
        old = current;
        current = next;
    }
    return current;
};

You might want to do this because the recursive version is inefficient in a language like C#. Some might suggest using memoization but, since this is still slower than the iterative method, they may just be being wankers. :-)

At this point though, this becomes more of an ad for functional programming than anything else (since the recursive version is so much nicer). It really does not have anything to do with my original question, but some of the answers thought that it was important.

Drowsy

If any job interviewer asked me that I'd walk out. – Chowchow

Last I checked you still have to declare the Func on a separate line, I'd be happy to be incorrect! – Impale

Thanks Jonathon! I spell badly in the morning. :-) – Drowsy

As you can see from the answers, you don't want to do that in an interview. Besides this being the "stupid" implementation of the Fibonacci function, it is not even valid C# code. – Thundering

@Martinho. See my comment to Eric about the interview question. Thank you for the advice but I was not being serious. – Drowsy

Answer 1

This is a bug in the Mono compiler. It violates section §12.3.3 of the specification. The variable fib cannot be used in the variable initializer, because it isn't definitely assigned.

Thundering

Opened over 6 years ago... good to see that bugs get fixed in open source much "faster" than in closed source software ;) – Peafowl

@Matthew - There are probably bugs from day one in any software that last until the last user finally turns it off. I could not help but respond to your quip though...at least this bug has not been around 17 years: techchunks.com/technology/… – Drowsy

Discovered in 2010... that's 1 month – Peafowl

Answer 2

As I noted in a comment above, if Mono does that then they have a bug. The spec is clear that this is supposed to be detected as an error. The bug is of course mostly harmless, and most of the time does what you want. We've considered changing the rules to make this sort of recursion legal; basically we'd have to add a special case to the spec that says that this narrowly-defined case is legal. It's never been a high enough priority though.

For more thoughts on this issue see my article on the subject:

http://blogs.msdn.com/b/ericlippert/archive/2006/08/18/706398.aspx

And by the way, I would not hire anyone who gave me a straight-up recursive implementation of fib in an interview. It is extremely inefficient; its running time is proportional to the size of its output, and fib grows exponentially. To make it efficient use recursion with memoization, or implement the obvious iterative solution.

Resolutive

Clearly the interview crack was meant to be a joke though. I expected somebody to make the throwaway comment about efficiency but I am surprised to hear it from you here. After all, your comment on the blog I took it from was "Awesome Wes. This is one of the most clear explanations of the y combinator I've seen yet." Perhaps I should quip back that I would never hire a compiler dev that cannot implement tail call elimination. :-) Smile, it's early (for me at least). – Drowsy

@Justin: point taken. However, to be fair, Wes's article was not intended to give an efficient implementation of fib, it was intended to be a tutorial on the Y combinator. – Resolutive

agreed. Also to be fair, my implementation was a consequence of Wes's implementation. No? For further humor, Scott Hanselman calls this exact code snippet "a great use of C# 3.0". From my vantage, Scott seems to have been a pretty nice hire for Microsoft. Perhaps you need broaden your interviewing horizons. :-) By the way, despite my tone, I mean no disrespect. You are clearly leagues smarter than me and you contribute greatly to a product that I love. Keep up the good work. – Drowsy

I'm surprised you have such low standards. I thought for sure you'd require an interviewee to come up with an O(log n) solution (e.g via matrix exponentiation), if not the O(1) closed form solution! [:-)] – Acrolith

Answer 3

try this...

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; 

... The problem is that fib isn't defined when you try to use it in the above method so the static analyzer reports a compiler error.

Peafowl

Thanks Matthew. I get that. In fact, they give this example in the article. – Drowsy

This is almost certainly what REPL is turning your inline assignment into. Basically VS chokes on the evaluation of the lambda; "fib" technically doesn't exist yet when creating the lambda that will be assigned to fib. Your Mono compiler's just smart enough to take a step back and see the larger statement. – Beisel

@Beisel this isn't a "smart enough" thing in mono... it's a bug from the spec. See Eric Lippert's response (he should know... he's on the Microsoft C# team.) – Peafowl

Answer 4

It seems that, in my excitement, I was fundamentally mistaken. Neither .NET nor Mono provides "Anonymous Recursion" in the way that the original article means. You could not pass around fib as a self-contained entity.

Check out the following sequence in the Mono C# REPL:

csharp> Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; 
csharp> fibCopy = fib;
csharp> fib(6);
8
csharp> fibCopy(6);
8
csharp> fib = n => n * 2;
csharp> fib(6);
12
csharp> fibCopy(6);
18

This is because:

fib = n => n * 2;
fibCopy = n > 1 ? fib(n - 1) + fib(n - 2) : n;

In other words,

fibCopy = n > 1 ? (n - 1) * 2 + (n - 2) * 2 : n;    // at the moment

Clearly, fibCopy is just pointing at the current definition of fib (the delegate) and not at itself. So Mono is really just pre-assigning a value of null to fib during the initial assignment so that the assignment is valid.

I much prefer the convenience of not having to declare null so I do like this behavior. Still, it is not really what the original article is talking about.

Drowsy

You're right. It's not quite "anonymous recursion" because you're using the "named" fib function. – Thundering

Answer 5

In Microsoft's C# compiler, it will only work if you first set fib to null.

Otherwise, it will give an error because fib is used before it's assigned.
Mono's compiler is "smart" enough to avoid this error (in other words, it violates the official spec)

Pullulate

By smart enough, you mean smarter than the spec, right? Some might call that a bug. – Thundering

Which compiler is "smarter" is debatable. Different decisions were made in their designs. – Peafowl

For completeness, the violation of the spec regards section §12.3.3. The variable fib is not definitely assigned because it isn't before the statement, and it only becomes definitely assigned after the statement. – Thundering

@Martinho is correct; if Mono does that, technically they have a bug; the spec says that this should be illegal. A mostly harmless bug, of course. It would be interesting to see if the Mono compiler allows delegate D D(D d); /*...*/ D d = ((D)(c=>c(d))(e=>e); because there the value of d actually is used before it is initialized. If Mono allows that then the bug can actually be used to observe an uninitialized local variable. – Resolutive

Actually, this bug is already kind of reported: it's mentioned by Miguel in the comments of bug #317420. – Thundering

I actually don't like the wording @Pullulate used. It appears to favor mono, which I don't think is correct. -1. – Chowchow