¿Funciona la "Recursividad anónima" en .NET? Lo hace en Mono

Question

He navegado en el sitio this hace unos días en "Recursividad anónima en C#". La idea central del artículo es que el siguiente código no funcionará en C#:

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

El artículo entonces entra en algunos detalles acerca de cómo usar currying y la Y-combinator para volver a "Anónimo recursividad" en C#. Esto es bastante interesante, pero un poco complejo para mi codificación diaria, me temo. En este punto al menos ...

Me gusta ver cosas para mí, así que abrí el Mono CSharp REPL y entré en esa línea. Sin errores. Entonces, ingresé fib(8);. ¡Para mi gran sorpresa, funcionó! ¡El REPL respondió de nuevo con 21!

Pensé que tal vez esto era algo mágico con el REPL, así que encendí 'vi', escribí el siguiente programa y lo compilé.

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)); 
    } 
} 

¡Construyó y funcionó perfectamente también!

Estoy ejecutando Mono 2.10 en una Mac. No tengo acceso a una máquina con Windows ahora mismo, así que no puedo probar esto en .NET en Windows.

¿Se ha corregido esto también en .NET o esta es una función silenciosa de Mono? El artículo tiene un par de años.

Si solo es Mono, no puedo esperar para la próxima entrevista de trabajo en la que me piden que escriba una función de Fibinocci en el idioma de mi elección (Mono C#) donde tengo que advertir que .NET no funcionará . Bueno, en realidad puedo esperar ya que amo mi trabajo. Aún así, interesante ...

Actualización:

Mono no está haciendo realmente recursividad "anónimo", como se usa fib como delegado nombrado. Mi error. El hecho de que el compilador Mono C# asuma un valor null para fib antes de la asignación es un error como se indica a continuación. Digo "compilador" porque .NET CLR ejecutará el ensamblaje resultante muy bien, aunque el compilador .NET C# no compile el código.

Para todos los nazis de la entrevista por ahí:

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

se pueden sustituir por una versión iterativa:

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; 
}; 

Es posible que desee hacer esto debido a que la versión recursiva es ineficiente en un lenguaje como DO#. Algunos pueden sugerir el uso de memoization, pero, dado que esto es aún más lento que el método iterativo, pueden estar siendo más tontos. :-)

En este punto, sin embargo, esto se convierte más en un anuncio para programación funcional que en cualquier otra cosa (ya que la versión recursiva es mucho más agradable). Realmente no tiene nada que ver con mi pregunta original, pero algunas de las respuestas pensaron que era importante.

Answer 1

Esto es bug en el compilador Mono. Viola la sección §12.3.3 del specification. La variable fib no se puede utilizar en el inicializador variable, porque no está asignada definitivamente.

Answer 2

probar este ...

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

...El problema es que fib no está definido cuando intenta usarlo en el método anterior para que el analizador estático informe un error de compilación.

Answer 3

En compilador de C# de Microsoft, que sólo funcionará si primer conjunto fib a null.

De lo contrario, dará un error porque fib se usa antes de asignarlo.
compilador de Mono es suficientemente "inteligentes" para evitar este error (en otras palabras, que viola la especificación oficial)

Answer 4

Como señalé en un comentario anterior, si Mono hace que entonces tienen un error. La especificación es clara de que se supone que debe detectarse como un error. El error es, por supuesto, inofensivo, y la mayoría de las veces hace lo que quiere. Hemos considerado cambiar las reglas para legalizar este tipo de recursividad; Básicamente, tendríamos que agregar un caso especial a la especificación que diga que este caso definido de forma estricta es legal. Sin embargo, nunca ha sido una prioridad lo suficientemente alta.

Para más ideas sobre este tema, véase mi artículo sobre el tema:

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

Y, por cierto, no me contratar a nadie que me dio una implementación recursiva recta en marcha de fib en una entrevista . Es extremadamente ineficaz; su tiempo de ejecución es proporcional al tamaño de su salida, y fib crece exponencialmente. Para que sea eficiente use la recursión con la memoria, o implemente la solución iterativa obvia.

Answer 5

Parece que, en mi entusiasmo, estaba fundamentalmente equivocado. Ni .NET ni Mono proporcionan "Recursividad anónima" en la forma en que lo hace el artículo original. No se pudo pasar alrededor de fib como una entidad autónoma.

Mira la siguiente secuencia en el 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 

Esto es debido a que:

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

En otras palabras,

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

Claramente, fibCopy se acaba apuntando en la definición actual de fib (el delegado) y no en sí mismo. Entonces, Mono simplemente está asignando previamente un valor de null a fib durante la asignación inicial para que la asignación sea válida.

Prefiero la conveniencia de no tener que declarar null así que me gusta este comportamiento. Aún así, no es realmente de lo que está hablando el artículo original.