¿Funciona la “recursión anónima” en .NET?lo hace en mono

Question

navegué hacia este sitio hace unos días sobre "Recursión 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;

Luego, el artículo entra en algunos detalles sobre cómo utilizar zurra y el combinador en Y para volver a "Recursión anónima" en C#.Esto es bastante interesante, pero me temo que es un poco complejo para mi codificación diaria.Al menos a estas alturas...

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

Pensé que tal vez esto era algo mágico con 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));
    }
}

¡Se construyó y funcionó perfectamente también!

Estoy ejecutando Mono 2.10 en una Mac.No tengo acceso a una máquina con Windows en este momento, por lo que no puedo probar esto en .NET en Windows.

¿Esto también se ha solucionado en .NET o es una característica silenciosa de Mono?El artículo tiene un par de años.

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

Actualizar:

Mono realmente no está haciendo recursividad "anónima", ya que está usando fib como delegado designado.Culpa mía.El hecho de que el compilador Mono C# asuma una null valor por fib antes de la asignación hay un error como se indica a continuación.Digo "compilador" porque .NET CLR ejecutaría bien el ensamblado resultante aunque el compilador .NET C# no compilaría el código.

Para todas las entrevistas a nazis que existen:

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

se puede reemplazar con 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;
};

Quizás quieras hacer esto porque la versión recursiva es ineficiente en un lenguaje como C#.Algunos podrían sugerir el uso memorización pero, dado que esto sigue siendo más lento que el método iterativo, es posible que simplemente estén siendo unos idiotas.:-)

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

Answer 1

Esto es un bicho en el compilador Mono.Viola la sección §12.3.3 de la especificación.La variable mentira no se puede utilizar en el inicializador de variables porque no está asignado definitivamente.

Answer 2

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

Para obtener más ideas sobre este tema, consulte mi artículo sobre el tema:

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

Y, por cierto, no contrataría a nadie que me diera una implementación recursiva directa de mentira en una entrevista.Es extremadamente ineficiente;su tiempo de ejecución es proporcional al tamaño de su producción y fib crece exponencialmente.Para hacerlo eficiente, use la recursividad. con memorización, o implementar la solución iterativa obvia.

Answer 3

prueba esto...

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 intentas usarlo en el método anterior, por lo que el analizador estático informa un error del compilador.

Answer 4

Parece que, en mi excitación, estaba fundamentalmente equivocado.Ni .NET ni Mono proporcionan "recursión anónima" en la forma en que lo indica el artículo original.No podías pasar fib como una entidad autónoma.

Consulte la siguiente secuencia en 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 porque:

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 simplemente está señalando la definición actual de fib (el delegado) y no a sí mismo.Entonces Mono en realidad solo está preasignando un valor de null a fib durante la asignación inicial para que la asignación sea válida.

Prefiero la comodidad de no tener que declarar null Entonces me gusta este comportamiento.Aún así, no es realmente de lo que habla el artículo original.

Answer 5

En el compilador C# de Microsoft, sólo funcionará si configura primero fib a null.

De lo contrario, dará un error porque fib se utiliza antes de ser asignado.
El compilador de Mono es lo suficientemente "inteligente" como para evitar este error (en otras palabras, viola la especificación oficial)