Wie berechnet Y-Kombinator den Fixpunkt programmatisch?

Question

Ich glaube, ich verstehe mathematisch die Idee des Y-Kombinator: Es gibt den Fixpunkt eines gegebenen funktionalen F, also f = Y(F) wo f erfüllt f == F(f).

Aber ich verstehe nicht, wie es das eigentliche Berechnungsprogramm klug macht?

Lassen Sie uns das Javascript Beispiel nehmen gegeben here (ich auch einen Coffeescript-Version in Kommentar enthalten, die zu lesen ist einfacher):

var Y = function (F) { 
    return (function(x) { 
    return F(function(y) { 
     return x(x)(y); 
    }); 
    })(function(x) { 
    return F(function(y) { 
     return x(x)(y); 
    }); 
    }); 
}; 


var Factorial = function (factorial) { 
    return function (n) { 
    if (n === 0) { 
     return 1; 
    } else { 
     return n * factorial(n - 1); 
    } 
    }  
}; 

/* Equivalent CoffeeScript: 
Y = (F) -> 
    ((x) -> F((y) -> x(x)(y)))((x) -> F((y) -> x(x)(y))) 

Factorial = (factorial) -> 
    if n == 0 then 1 else n * factorial(n-1) 
*/ 

Y(Factorial)(6) == 720 // => true 
computed_factorial = Y(Factorial) 

Der Teil verstehe ich nicht, wie die computed_factorial Funktion (der Fixpunkt) Wird tatsächlich berechnet? Durch die Verfolgung der Definition von Y, finden Sie es in eine unendlich Rekursion bei der x(x) Teil läuft, kann ich nicht sehen, Abschluss Fällen dort impliziert. Es kehrt jedoch komischerweise zurück. Kann mir jemand erklären?

Answer 1

Ich werde ES6 Pfeil Funktionssyntax verwenden. Da Sie CoffeeScript zu kennen scheinen, sollten Sie keine Probleme haben, es zu lesen.

Hier ist Ihr Y Combinator

var Y = F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y))) 

Ich werde eine verbesserte Version Ihrer factorial Funktion tho verwenden. Dieser verwendet stattdessen einen Akkumulator, der verhindert, dass sich die Auswertung in eine große Pyramide verwandelt. Der Prozess dieser Funktion wird linear iterative sein, während Ihr rekursiv wäre. Wenn ES6 endlich die Tail Call Elimination bekommt, macht dies einen noch größeren Unterschied.

Der Unterschied in der Syntax ist nominal. Es ist sowieso egal, da Sie nur sehen wollen, wie die Y ausgewertet wird.

Nun, dies wird bereits dazu führen, dass der Computer etwas Arbeit zu tun beginnt. Also lassen Sie uns diese bewerten, bevor wir weiter gehen ...

Ich hoffe, Sie haben eine wirklich gute Klammer Highlighter in Ihrem Texteditor ...

var factorial 
= Y (f=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1)                                        // sub Y 
= (F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))) (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1)                           // apply F=> to fact=> 
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (1)                // apply x=> to x=> 
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1) // apply fact=> to y=> 
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (1)    // apply acc=> to 1 
= n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1)        // return value 
= [Function] (n=> ...) 

So können Sie hier sehen, nach wir nennen:

var factorial = Y(fact=> acc=> n=> ...) (1); 
//=> [Function] (n=> ...) 

wir bekommen eine Funktion zurück, die für einen einzelnen Eingang wartet, n. Werfen wir nun einen faktorielles laufen

Bevor wir fortfahren, können Sie überprüfen (und sollten), dass hier jeder Linie korrekt ist durch Kopieren/Einfügen in ein Javascript-ers. Jede Zeile gibt 24 zurück (was die richtige Antwort für factorial(4) ist. Sorry, wenn ich das für Sie verdorben habe). Das ist wie wenn man Brüche vereinfacht, algebraische Gleichungen löst oder chemische Formeln ausgleicht; Jeder Schritt sollte eine korrekte Antwort sein.

Achten Sie darauf, den ganzen Weg nach rechts für meine Kommentare zu blättern. Ich sage dir, welche Operation ich in jeder Zeile abgeschlossen habe. Das Ergebnis der abgeschlossenen Operation befindet sich in der folgenden Zeile.

Und stellen Sie sicher, dass die Halterung Highlighter haben wieder handlich ...

factorial (4)                                                      // sub factorial 
= (n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1)) (4)         // apply n=> to 4 
= 4 < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1)           // 4 < 2 
= false ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1)           // ?: 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1)              // 1*4 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (4-1)               // 4-1 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3)               // apply y=> to 4 
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (4) (3)                  // apply x=> to x=> 
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3)  // apply fact=> to y=> 
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (4) (3)     // apply acc=> to 4 
= (n=> n < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*n) (n-1)) (3)         // apply n=> to 3 
= 3 < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1)           // 3 < 2 
= false ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1)           // ?: 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1)              // 4*2 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (3-1)              // 3-1 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2)               // apply y=> to 12 
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (12) (2)                 // apply x=> to y=> 
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2)  // apply fact=> to y=> 
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (12) (2)     // apply acc=> 12 
= (n=> n < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*n) (n-1)) (2)        // apply n=> 2 
= 2 < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1)           // 2 < 2 
= false ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1)           // ?: 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1)              // 12*2 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (2-1)              // 2-1 
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1)               // apply y=> to 24 
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (24) (1)                 // apply x=> to x=> 
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1)  // apply fact=> to y=> 
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (24) (1)     // apply acc=> to 24 
= (n=> n < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*n) (n-1)) (1)        // apply n=> to 1 
= 1 < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1)           // 1 < 2 
= true ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1)           // ?: 
= 24 

---

ich andere Implementierungen von Y auch gesehen haben. Hier ist ein einfacher Prozess zum Erstellen eines anderen (für die Verwendung in Javascript) von Grund auf neu.

// text book 
var Y = f=> f (Y (f)) 

// prevent immediate recursion (javascript is applicative order) 
var Y = f=> f (x=> Y (f) (x)) 

// remove recursion using U combinator 
var Y = U (h=> f=> f (x=> h (h) (f) (x))) 

// given: U = f=> f (f) 
var Y = (h=> f=> f (x=> h (h) (f) (x))) (h=> f=> f (x=> h (h) (f) (x))) 

Answer 2

In einer lazy evaluation Sprache kann der Y-Combinator wie folgt definiert werden:

Y = (f => 
    (x => f(x(x))) 
    (x => f(x(x)))) 

Aber da Javascript ist eine eifrige Auswertung Sprache, definiert Y auf diese Weise den x verursachen würde (x) Teil zu reccurse auf unbestimmte Zeit zu dem Zeitpunkt, wenn Sie versuchen, Y auf eine Funktion anzuwenden.

Um dieses Problem zu umgehen, kann eine anonyme "Wrapper" -Funktion eingeführt werden, um die Ausführung von x zu verzögern. Diese Wrapper-Funktion würde sich genauso verhalten wie x (x), wenn sie aufgerufen wird, würde aber sofort zurückkehren, da es nur eine Funktionsdefinition ist.

Zu wissen, dass x (x) würde die rekursive Funktion gebunden werden, im Fall des Beispiels:

Factorial = f => n => n==0 ? 1 : n*f(n-1) 

Wir können vor der Zeit sagen, dass nur ein einziges Argument würde an sie übergeben werden . Es ermöglicht uns, das folgende Muster zu verwenden, um eine anonyme Funktion zu erzeugen, die das gleiche wie jedes gegebene Funktion f (x) verhalten:

f => x => f(x) 

Wenn wir dieses Muster auf den x (x) Begriff gelten, Y würde Rekursion nicht mehr auf unbestimmte Zeit und wird:

Y = (f => 
    (x => f(y => x(x)(y))) 
    (x => f(y => x(x)(y)))) 

Answer 3

die Y Combinator eines der interessantesten Phänomene in dem Lambda-Kalkül ist. Ich bezweifle, dass man sofort eine Interpretation seiner Funktionalität entwickeln kann.

Y = f => (g => g(g))(g => n => f(g(g))(n)); 

Lassen Sie uns versuchen, die Ableitung Schritt für Schritt zu verstehen. Ich werde die Pfeilfunktionen verwenden. Wenn Sie sich nicht damit auskennen, folgen Sie bitte this link. Sie sind sehr einfach. x => x bedeutet function(x){return x;}. Das Schlüsselwort JS this hat eine andere Bedeutung innerhalb der Pfeile, aber das Thema ist nicht Thema.

Also werden wir immer mit der faktoriellen Funktion gehen, aber der Y-Kombinator, den wir ableiten werden, wird für alle rekursiven Funktionen gültig sein.

A Fakultäts-Funktion kann einfach ausgedrückt werden als

var fa = n => n === 0 ? 1 : n*fa(n-1); 
fact(5) // <- 120 

folgt aber sagen, dass wir nicht rekursiv auf die fa Funktion beziehen möchten; stattdessen möchten wir eine funktionierende faktorielle Funktion aus einer hypothetischen Version der faktoriellen Funktion ableiten. Was ist eine hypothetische faktorielle Funktion? Die hypothetische faktorielle Funktion nimmt eine korrekte faktorielle Funktion an und gibt uns eine funktionierende faktorielle Funktion zurück. Wie die folgenden

var fh = f => n => n === 0 ? 1 : n*f(n-1); 

Also, wenn ich pass fa Funktion fh als Argument wird es funktionieren. Mögen;

fh(fa)(5); // <- 120 

Aber wir wollen nicht wie fa auf eine andere Fakultätsfunktion beziehen, da wir bereits „Art“ definiert haben die Fakultät Logik innerhalb der fh Funktion. Dann denken wir. fh hält das f Argument in Schließung und gibt mir eine funktionierende faktorielle Funktion zurück (n => n === 0 ? 1 : n*f(n-1)), wenn ich eine richtige Fakultät Funktion wie fa übergeben. Was ist, wenn ich mich ihm hingebe? Ein kurzer Versuch fh(fh)(5) // <- NaN meh ..!

Also fangen wir an, mit der inneren Funktion zu spielen. Normalerweise würde ich diesen Schritt bestehen, aber es könnte hilfreich sein, die Transformationen zu sehen ... also lass uns fortfahren. Ich kann die fb Funktion definieren Sie mir eine Funktion zurück, die zwei Argumente übernimmt, sich und Fakultäts Zählung n

fb = (f,n) => n === 0 ? 1 : n* f(f,n-1), // fb(fb,5) <- 120 

So weit so gut, aber die zwei Argument Fakultäts-Funktion ist nicht in dem nahe, was ich suche. Ich kann sie trennen, indem ich einen weiteren funktionalen Schritt hinzufüge.

fc = f => n => n === 0 ? 1 : n* f(f)(n-1), // fc(fc)(5) <- 120 

Nun ist dies ganz in der Nähe unserer hypothetischen Funktion fh. Aber das Innere zeigt f(f)(n-1) Wir müssen dies korrigieren, um f (n-1) zu zeigen. Nun können wir eine JS Schönheit IIFE verwenden, um uns zu helfen ...

Können Sie die IIFE ..? ((g,n) => n === 0 ? 1 : n * g(n-1))(f(f),n) Obwohl dies in Ordnung scheint, muss ich das Doppelargument (g,n) IIFE loswerden, um das gewünschte Ergebnis zu erzielen. Dies wird eine andere Ebene der Funktionsfähigkeit nehmen.

fe => f => n => (g => n => n === 0 ? 1 : n * g(n-1))(f(f))(n) // fe(fe)(5) <- 120 

Jetzt haben wir innerhalb g => n => n === 0 ? 1 : n * g(n-1), die der Körper unserer hypothetischen Funktion fh ist. Was bedeutet, ich kann ersetzen (ich liebe diesen Teil .. genau wie Kalkül Substitution; in der Tat ist es ...) fh in der obigen Funktion zu lesen wie;

fe => f => n => fh(f(f))(n) // fe(fe)(5) <- 120 

Ok Zeit, um es zu wickeln. Was ich in erster Linie wollte ..? Ich möchte fh zu einer Funktion (Y-Kombinator) füttern und es ist Fixpunkt. Hier weiß ich, dass fe(fe)fh verwendet und mir die richtig funktionierende faktorielle Funktion zurückgibt. Lassen Sie uns also eine Funktion definieren, die unsere hypothetische rekursive Funktion als Argument annimmt und uns etwas funktioniert (behoben). IIFE, um wieder zu helfen.

Y = f => (g => g(g))(g => n => f(g(g))(n)); 

Also sollte dies für alles funktionieren. Versuchen wir unseren Y-Kombinator mit einer hypothetischen Fibonacci-Funktion.

var Y = f => (g => g(g))(g => n => f(g(g))(n)), 
 
fibH = f => n => n === 0 ? 0 
 
          : n === 1 ? 1 
 
            : f(n-2) + f(n-1), 
 
fibo = Y(fibH); 
 
console.log(fibo(10));

Ich hoffe, es ist klar, ...