Ho implementato Y-combinator usando C# dynamic, e se non l'ho, che cos'è?

Question

Il mio cervello sembra essere in modalità masochista, quindi dopo essere annegato in this, e this, voleva fare un po 'di fai-da-te in C#.

mi si avvicinò con la seguente, che io non credo che è la Y-Combinator, ma fa sembrano riuscire a fare una funzione ricorsiva non ricorsiva, senza fare riferimento a se stessa:

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

Quindi, dato questi:

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

possiamo generare questi:

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, non è il combinatore Y; sei solo a metà strada. Hai ancora bisogno di calcolare l'auto-applicazione all'interno delle funzioni "seme" a cui stai applicando. Cioè, invece di questo:

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

si dovrebbe avere questo:

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

Annotare la singola occorrenza di self nella seconda definizione in contrasto con le due ricorrenze nella prima definizione.

(a cura di aggiungere :) BTW, dal momento che l'utilizzo di C# simula il lambda calcolo con la valutazione delle chiamate per valore, il punto fisso-Combinator che vuoi è the one often called Z, not Y

(a cura di nuovo di elaborare :) Il equazione che descrive Y è questo (vedi the wikipedia page per la derivazione):

Y g = g (Y g) 

Ma nei linguaggi di programmazione più pratici, si valuta l'argomento di una funzione prima di chiamare la funzione. Nella comunità dei linguaggi di programmazione, si chiama valutazione call-by-value (da non confondere con il modo in cui i programmatori C/C++/Fortran/etc distinguono "call by value" vs "call by reference" vs "call by copy-restore" , eccetera).

Ma se lo facessimo, ci saremmo

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

Cioè, ci piacerebbe trascorrere tutto il nostro tempo costruendo la funzione ricorsiva e mai andare in giro a applicare esso.

Nella valutazione della chiamata per nome, d'altra parte, si applica una funzione, qui g, all'espressione di argomento non valutato, qui (Y g). Ma se g è come fact, è in attesa di un altro argomento prima che faccia qualcosa. Quindi dovremmo aspettare il secondo argomento a g prima di provare a valutare (Y g) e, a seconda di cosa funzioni la funzione (cioè, se ha un caso base), potremmo non aver bisogno di valutare (Y g). Ecco perché lo Y funziona per la valutazione del nome per nome.

La correzione per la chiamata per valore consiste nel modificare l'equazione.Invece di Y g = g (Y g), vogliamo qualcosa di simile al seguente equazione invece:.

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

(Penso che ho avuto l'equazione giusta, o vicino al giusto grado di calcolare fuori e vedere se si adatta con la definizione di Z.

Un modo per pensare a questo è invece di calcolare "l'intera funzione ricorsiva" e passandogli a g, gli passiamo una funzione che calcolerà la funzione ricorsiva un po 'alla volta --- e solo quando abbiamo bisogno di un po 'di più per applicarlo a un argomento (x).