Kombinatory z punktami stałymi

Question

Jestem nowy w świecie fixed-point combinators i domyślam się, że są one używane do powtarzania się na anonimowych lambdach, ale tak naprawdę nie musiałem ich używać, a nawet byłem w stanie całkowicie owinąć się wokół nich.

Widziałem przykład w JavaScript dla Y-combinator, ale nie udało się go pomyślnie uruchomić.

Chodzi o to, może ktoś podać intuicyjne odpowiedzi:

• Co stałoprzecinkowych kombinatorów, (nie tylko teoretycznie, ale w kontekście jakiegoś przykładu, aby odsłonić to, co dokładnie jest stały punkt w tym kontekście)?
• Jakie są inne rodzaje kombinatorów o ustalonym punkcie, poza kombinatorem Y?

Bonusowe Punkty: Jeżeli przykład nie jest tylko w jednym języku, najlepiej w Clojure, jak również.

UPDATE:

udało mi się znaleźć prosty przykład w Clojure, ale wciąż trudno zrozumieć Y Combinator sam:

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

Choć przykładem jest zwięzły , Trudno mi zrozumieć, co dzieje się w funkcji. Pomocna będzie każda pomoc.

Answer 1

Załóżmy, że chcesz napisać funkcję silni. Zwykle można go zapisać jako coś podobnego do tego, co na przykład:

Ale używa to jawnej rekursji. Jeśli chcesz użyć zamiast Y Combinator, można najpierw streszczenie fakt jako coś

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

Ten przyjmuje argument (myFact), który wywołuje były „prawdziwe” Fakt nazwałby siebie. Nazywam ten styl funkcją "Y-ready", co oznacza, że ​​jest gotowy do podania Y-combinatorowi.

Y-combinator używa factMaker do zbudowania czegoś podobnego do "prawdziwego" faktu.

newFact = Y(factMaker) 

Po co? Dwa powody. Pierwsza z nich jest teoretyczna: nie potrzebujemy rekursji, jeśli możemy "zasymulować" ją za pomocą kombinatora Y.

Drugi jest bardziej pragmatyczny. Czasami chcemy zawinąć każde wywołanie funkcji za pomocą dodatkowego kodu, aby wykonać rejestrowanie lub profilowanie lub zapamiętywanie lub wiele innych rzeczy. Jeśli spróbujemy zrobić to z faktem "prawdziwym", dodatkowy kod będzie wywoływany tylko dla pierwotnego wywołania faktów, a nie dla wszystkich wywołań rekursywnych. Ale jeśli chcemy to zrobić dla każdego połączenia, w tym wszystkie wywołanie rekurencyjne, możemy zrobić coś

loggingFact = LoggingY(factMaker) 

gdzie LoggingY jest zmodyfikowaną wersją combinator Y, który wprowadza rejestrowanie. Zauważ, że wcale nie musieliśmy zmieniać programu factMaker!

Wszystko to jest bardziej motywacją, dlaczego kombinator Y ma znaczenie niż szczegółowe wyjaśnienie, jak działa ta konkretna implementacja Y (ponieważ istnieje wiele różnych sposobów wdrożenia Y).

Answer 2

Aby odpowiedzieć na drugie pytanie o kombinatorów fix-punktowych innych niż Y. Są przeliczalnie nieskończenie wiele standardowych kombinatorów fix-point, czyli kombinatorów fix które spełniają równanie

fix f = f (fix f) 

Istnieje również wiele contably nietypowe złożone jest poprawka punktowe, które spełniają równanie

fix f = f (f (fix f)) 

itp standardowe kombinatorów fIX-punktowe są rekurencyjnie wyliczalnych, ale nie standardowe nie. Poniższa strona internetowa zawiera przykłady, odniesienia i dyskusje. http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes