Does "Anonymous recursion" work in .NET? He does in Mono

Question

I visited this site a few days ago in the "Anonymous Recursion in C #" section. The essence 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 rest of the article details the use of currying and Y-combinator to return to "Anonymous recursion" in C #. This is quite interesting, but it is a complex complex for my everyday encoding, I'm afraid. At the moment, at least ...

I like to see the material for myself, so I opened the Mono CSharp REPL and entered this line. No mistakes. So, I introduced fib(8); . To my great surprise, it worked! REPL answered with 21 !

I thought that maybe it was some kind of magic with REPL, so I activated "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)); } } 

He built and did a great job too!

I am running Mono 2.10 on a Mac. I do not have access to the Windows machine right now, so I can not check this on .NET in Windows.

Was it fixed on .NET, or is it a quiet Mono feature? The article is a couple of years.

If this is only Mono, I can’t wait for the next interview where they ask me to write the Fibinocci function in my language of choice (Mono C #), where I must provide a warning that .NET will not work. Well, actually I can wait, because I love my job. However, interesting ...

Update:

Mono does not perform anonymous recursion because it uses fib as a named delegate. To blame. The fact that the Mono C # compiler is null for fib before the assignment will be an error, as indicated below. I say “compiler” because the .NET CLR starts the resulting assembly just fine, even if the .NET C # compiler will not compile the code.

For the entire Nazi interview 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 C #. Some may suggest using memoization , but since it is still slower than the iterative method, they may just be wankers. :-)

At this point, it becomes more of an advertisement for functional programming than anything else (since the recursive version is much nicer). This really has nothing to do with my original question, but some answers thought this was important.

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 is definitely not assigned.

Answer 2

As I noted in the comment above, if Mono does this, then they have a mistake. The specification clearly states that this should be detected as an error. The error, of course, is basically harmless, and most of the time it does what you want. We considered changing the rules to make such recursion legal; basically, we would have to add a special case to the specification, which states that this narrowly defined case is legal. However, he was never a high enough priority.

For more on this issue, see my article on this topic:

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

And by the way, I would not hire those who gave me a direct recursive embodiment of the fib in an interview. It is extremely inefficient; its operating time is proportional to the size of its output, and the fiber grows exponentially. To use recursion efficiently with memoization or implement an obvious iterative solution.

Answer 3

try it...

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

... The problem is that fib is not detected when you try to use it in the above method, so the static analyzer reports a compiler error.

Answer 4

It seems that in my excitement I was fundamentally wrong. Neither .NET nor Mono provides anonymous recursion as intended in the original article. You cannot get around fib as a standalone object.

Check out the following sequence in 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 simply points to the current definition of fib (delegate), not itself. So Mono really just pre-assigns null to fib during the initial assignment so that the assignment is valid.

I prefer there is no need to declare null , so I like this behavior. However, this is not quite what the original article is talking about.

Answer 5

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

Otherwise, this will result in an error because fib used before it is assigned.
The monocompiler is smart enough to avoid this error (in other words, it violates the official specification).