Fixed-Point Combinators

Question

Ich bin neu in der Welt von fixed-point combinators und ich schätze, dass sie verwendet werden, um anonyme Lambdas zu rekrutieren, aber ich habe sie nicht wirklich benutzen oder sie sogar komplett umschließen können.

Ich habe das Beispiel in Javascript für eine Y-combinator gesehen, aber konnte es nicht erfolgreich ausführen.

Die Frage ist hier, kann jemand, um eine intuitive Antwort geben:

• Was Festpunkt combinators ist, (nicht nur theoretisch, sondern in Zusammenhang mit einigem Beispiel, zu offenbaren, was genau festgelegt ist -Punkt in diesem Zusammenhang)?
• Was sind die anderen Arten von Festkomma-Kombinatoren, abgesehen vom Y-Kombinator?

Bonuspunkte: Wenn das Beispiel nicht nur in einer Sprache ist, vorzugsweise in Clojure auch.

UPDATE:

ich in der Lage gewesen, ein einfaches Beispiel in Clojure zu finden, aber finde es immer noch schwierig, den Y-Combinator selbst zu verstehen:

(defn Y [r] 
    ((fn [f] (f f)) 
    (fn [f] 
    (r (fn [x] ((f f) x)))))) 

Obwohl das Beispiel prägnant Ich finde es schwierig zu verstehen, was in der Funktion passiert. Jede Hilfe wäre nützlich.

Answer 1

Angenommen, Sie wollten die faktorielle Funktion schreiben. Normalerweise würden Sie es als so etwas wie

function fact(n) = if n=0 then 1 else n * fact(n-1) 

schreiben Aber das nutzt explizite Rekursion. Wenn Sie die Y-Combinator stattdessen verwenden möchten, können Sie erste abstrakte Tatsache als so etwas wie

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1) 

Dieses Argument übernimmt (myFact), die es nennt wurden die „wahre“ Tatsache selbst genannt hätte. Ich nenne diese Art von Funktion "Y-ready", was bedeutet, dass sie bereit ist, dem Y-Kombinator zugeführt zu werden.

Der Y-Kombinator verwendet factMaker, um etwas zu erstellen, das dem "wahren" Fakt entspricht.

newFact = Y(factMaker) 

Warum stören? Zwei Gründe. Die erste ist theoretisch: Wir brauchen Rekursion nicht wirklich, wenn wir sie mit dem Y-Kombinator "simulieren" können.

Die zweite ist pragmatischer. Manchmal möchten wir jeden Funktionsaufruf mit etwas zusätzlichem Code umhüllen, um Logging oder Profiling oder Memoization oder eine Menge anderer Dinge zu tun. Wenn wir versuchen, dies mit der "wahren" Tatsache zu tun, wird der zusätzliche Code nur für den ursprünglichen Aufruf zur Tatsache aufgerufen, nicht für alle rekursiven Aufrufe. Aber wenn wir dies für jeden Anruf machen wollen, alle rekursiven Aufruf einschließlich, können wir so etwas wie

loggingFact = LoggingY(factMaker) 

tun, wo LoggingY ist eine modifizierte Version des Y Combinator, die Protokollierung einführt. Beachten Sie, dass wir factMaker überhaupt nicht ändern mussten!

All dies ist mehr Motivation, warum der Y-Kombinator wichtiger ist als eine detaillierte Erklärung, wie diese spezielle Implementierung von Y funktioniert (weil es viele verschiedene Möglichkeiten gibt, Y zu implementieren).

Answer 2

Um Ihre zweite Frage zu Fix-Punkt combinators andere als Y. Es gibt abzählbar unendlich viele Standard-Fix-Punkt-Kombinatoren, zu beantworten das heißt, combinators fix, der die Gleichung

fix f = f (fix f) 

Es gibt auch viele contably erfüllen nicht-Standard-Fix-Punkt-Kombinatoren, die die Gleichung

fix f = f (f (fix f)) 

usw. Standard-Fix-Punkt combinators erfüllen, sind rekursiv aufzählbar, aber nicht-Standard nicht. Auf der folgenden Webseite finden Sie Beispiele, Referenzen und Diskussionen. http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes