¿Implementé Y-combinator usando C# dynamic, y si no lo hice, qué es?

Question

Mi cerebro parece estar en modo masoquista, por lo que después de haber sido ahogado en this, this y this, quería perder el tiempo con un poco de bricolaje en C#.

me ocurrió lo siguiente, que yo no creo es el Y-Combinator, pero qué parecen llegar a hacer una función recursiva no recursivo, sin referirse a sí mismo:

Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>> Y = x => x(x); 

Así dadas estas:

Func<dynamic, Func<dynamic, dynamic>> fact = 
        self => n => n == 0 ? 1 : n * self(self)(n - 1); 
Func<dynamic, Func<dynamic, dynamic>> fib = 
        self => n => n < 2 ? n : self(self)(n-1) + self(self)(n-2); 

podemos generar los siguientes:

Func<dynamic, dynamic> Fact = Y(fact); 
Func<dynamic, dynamic> Fib = Y(fib); 

Enumerable.Range(0, 10) 
      .ToList() 
      .ForEach(i => Console.WriteLine("Fact({0})={1}", i, Fact(i))); 

Enumerable.Range(0, 10) 
      .ToList() 
      .ForEach(i => Console.WriteLine("Fib({0})={1}", i, Fib(i))); 

Answer 1

No, ese no es el combinador Y; solo estás a mitad de camino allí. Aún necesita factorizar la autoaplicación dentro de las funciones de "semilla" a las que lo está aplicando. Es decir, en lugar de esto:

Func<dynamic, Func<dynamic, dynamic>> fact = 
        self => n => n == 0 ? 1 : n * self(self)(n - 1); 

usted debe tener presente:

Func<dynamic, Func<dynamic, dynamic>> fact = 
        self => n => n == 0 ? 1 : n * self(n - 1); 

Nota la sola aparición de self en la segunda definición a diferencia de las dos apariciones en la primera definición.

(editado para agregar :) Por cierto, ya que el uso de C# simula el cálculo lambda con la evaluación de llamada por valor, el combinador de punto fijo que desea utilizar es the one often called Z, not Y

(editado de nuevo para elaborar :) El ecuación que describe Y es esto (ver the wikipedia page para la derivación):

Y g = g (Y g) 

Pero en los lenguajes de programación más prácticas, a evaluar el argumento de una función antes de llamar a la función. En la comunidad de lenguajes de programación, esto se llama evaluación llamada por valor (que no debe confundirse con la forma en que los programadores C/C++/Fortran/etc distinguen "llamada por valor" versus "llamada por referencia" versus "llamada por copia-restauración" , etc.)

Pero si lo hicimos, que tendríamos

Y g = g (Y g) = g (g (Y g)) = g (g (g (Y g))) = ... 

Es decir, que teníamos que pasar todo nuestro tiempo construcción de la función recursiva y nunca moverse a la aplicación de ella.

En la evaluación de llamada por nombre, por el contrario, aplica una función, aquí g, a la expresión de argumento no evaluado, aquí (Y g). Pero si g es como fact, está esperando otro argumento antes de que haga algo. Así que esperaríamos el segundo argumento al g antes de tratar de evaluar (Y g) más --- y dependiendo de lo que haga la función (es decir, si tiene un caso base), es posible que no necesitemos evaluar (Y g) en absoluto. Es por eso que Y funciona para la evaluación llamada por nombre.

La solución para llamar por valor es cambiar la ecuación.En lugar de Y g = g (Y g), queremos algo parecido a la siguiente ecuación en su lugar:.

Z g = g (λx. (Z g) x) 

(creo que tengo la ecuación de la derecha, o cerca de la derecha se puede calcular hacia fuera y ver si se ajusta a la definición de Z.)

Una forma de pensar en esto es que en lugar de calcular "toda la función recursiva" y entregándola a g, le asignamos una función que calculará la función recursiva un poco a la vez --- y solo cuando en realidad necesitamos un poco más para poder aplicarlo a un argumento (x).