Kombinator stałoprzecinkowy FIX (znany również jako kombinator Y) w (niepoprawnym) rachunku lambda ( ) jest zdefiniowany jako:
FIX
Rozumiem jego cel i doskonale mogę śledzić wykonanie jego aplikacji; Chciałbym zrozumieć, jak wyprowadzić FIX z pierwszych zasad .
Oto, o ile mi się podoba, gdy próbuję to uzyskać:
- FIX to funkcja: FIX
- FIX przyjmuje inną funkcję, , aby była rekurencyjna: FIX
- Pierwszym argumentem funkcji jest „nazwa” funkcji, używana tam, gdzie przewidziana jest aplikacja rekurencyjna. Dlatego wszystkie wyglądy pierwszego argumentu na powinny być zastąpione przez funkcję, a ta funkcja powinna oczekiwać reszty argumentów (załóżmy, że przyjmuje jeden argument): FIX
W tym miejscu nie wiem, jak „zrobić krok” w moim rozumowaniu. Małe elipsy wskazują, gdzie brakuje mojego FIXa (chociaż mogę to wiedzieć tylko przez porównanie z „prawdziwym” FIXem).
Przeczytałem już Typy i języki programowania , które nie próbują wyprowadzić ich bezpośrednio, a zamiast tego odsyłają czytelnika do The Little Schemer w celu uzyskania pochodnej. Też to przeczytałem, a jego „wyprowadzenie” nie było tak pomocne. Co więcej, jest to w mniejszym stopniu bezpośrednie wyprowadzenie, a bardziej wykorzystanie bardzo specyficznego przykładu i próba ad-hoc napisania odpowiedniej funkcji rekurencyjnej w .
Odpowiedzi:
Nigdzie tego nie czytałem, ale wierzę, że można było wyprowadzić:Y
Niech będzie funkcja rekurencyjna , być może silnia lub coś podobnego. Nieformalnie definiujemy jako termin pseudo-lambda, gdzie występuje w jego własnej definicji:f f f
Po pierwsze, zdajemy sobie sprawę, że wywołanie rekurencyjne może zostać uwzględnione jako parametr:
Teraz moglibyśmy zdefiniować , gdybyśmy tylko mieli sposób, aby przekazać to jako argument sam w sobie. Nie jest to oczywiście możliwe, ponieważ nie mamy pod rękąCo mamy pod ręką jest . Ponieważ zawiera wszystko, co potrzebne do zdefiniowania , możemy spróbować przekazać jako argument zamiast i spróbować zrekonstruować z niego później w środku. Nasza pierwsza próba wygląda następująco:f f M M f M f f
Nie jest to jednak do końca poprawne. Wcześniej, , ale podstawiony przez w środku . Ale teraz zamiast tego mijamyMusimy jakoś naprawić wszystkie miejsca, w których używamy tak, aby zrekonstruować od . W rzeczywistości nie jest to wcale trudne: teraz, gdy wiemy, że , wszędzie, gdzie używamy , po prostu zastępujemy go przez .f r M M r f M f=MM r (rr)
To rozwiązanie jest dobre, ale musieliśmy zmienić wewnątrz. To nie jest zbyt wygodne. Możemy to zrobić bardziej elegancko bez konieczności modyfikowania , wprowadzając inny który wysyła do jego argument dotyczy samego siebie: Wyrażając jako otrzymujemyM M λ M M′ λx.M(xx)
W ten sposób, gdy jest podstawione na , jest podstawione na , co z definicji jest równe . To daje nam nierekurencyjną definicję , wyrażoną jako prawidłowy termin lambda!M x MM r f f
Przejście do jest teraz łatwe. Możemy wziąć dowolny termin lambda zamiast i wykonać na nim tę procedurę. Możemy więc wyliczyć i zdefiniowaćY M M
Rzeczywiście, zmniejsza się do jak to zdefiniowaliśmy.YM f
Uwaga: Wyprowadziłem zgodnie z definicją w literaturze. Syntezatora już opisany jest wariant dla call-by-value językach, czasami nazywany też . Zobacz ten artykuł w Wikipedii .Y Y Z
źródło
Jak zauważył Yuval, nie ma tylko jednego operatora punktu stałego. Dużo ich. Innymi słowy, równanie dla twierdzenia o punkcie stałym nie ma jednej odpowiedzi. Nie można więc uzyskać od nich operatora.
To tak, jakby zapytać, jak ludzie wyprowadzają jako rozwiązanie dla . Oni nie! Równanie nie ma unikalnego rozwiązania.(x,y)=(0,0) x=y
Na wypadek, gdybyście chcieli dowiedzieć się, jak odkryto pierwsze twierdzenie o punkcie stałym. Powiem, że zastanawiałem się także, w jaki sposób wymyślili twierdzenia o punkcie stałym / rekurencji, kiedy je zobaczyłem. To wydaje się takie genialne. Szczególnie w formie teorii obliczalności. W przeciwieństwie do tego, co mówi Yuval, ludzie nie bawili się, dopóki czegoś nie znaleźli. Oto, co znalazłem:
O ile pamiętam, twierdzenie to pierwotnie wynika z SC Kleene. Kleene wymyślił pierwotne twierdzenie o stałym punkcie, ocalając dowód niespójności pierwotnego rachunku lambda Kościoła. Oryginalny rachunek lambda Kościoła cierpiał na paradoks typu Russel. Zmodyfikowany rachunek lambda uniknął problemu. Kleene przestudiował dowód niespójności, aby prawdopodobnie sprawdzić, czy zmodyfikowany rachunek lambda cierpiałby na podobny problem i przekształcił dowód niespójności w przydatne twierdzenie o zmodyfikowanym rachunku lambda. Poprzez swoją pracę dotyczącą równoważności rachunku lambada z innymi modelami obliczeń (maszyny Turinga, funkcje rekurencyjne itp.) Przeniósł go na inne modele obliczeń.
Jak uzyskać operatora, o który możesz zapytać? Oto jak o tym pamiętam. Twierdzenie o punkcie stałym dotyczy usuwania odniesienia do siebie.
Każdy zna kłamliwy paradoks:
Lub w bardziej lingwistycznej formie:
Teraz większość ludzi uważa, że problem z tym zdaniem dotyczy samego odniesienia. Nie jest! Odniesienia do siebie można wyeliminować (problem dotyczy prawdy, język nie może mówić ogólnie o prawdziwości własnych zdań, patrz twierdzenie Tarskiego o nieokreśloności prawdy ). Formularz, w którym usunięto odniesienie, jest następujący:
Bez odniesienia do siebie, mamy instrukcje, jak skonstruować zdanie, a następnie coś z nim zrobić. A zdanie, które się konstruuje, jest równe instrukcjom. Zauważ, że w -calculus nie potrzebujemy cudzysłowów, ponieważ nie ma rozróżnienia między danymi a instrukcjami.λ
Teraz, jeśli to przeanalizujemy, mamy gdzie jest instrukcją, aby skonstruować i coś z tym zrobić.MM Mx xx
Więc to i mamyM λx.f(xx)
To jest dla ustalonego . Jeśli chcesz uczynić go operatorem, po prostu dodajemy i otrzymujemy :f λf Y
Więc po prostu pamiętać paradoksu bez samo-odniesienia i że pomaga mi zrozumieć, co jest.Y
źródło
Musisz więc zdefiniować kombinator punktów stałych
ale bez wyraźnej rekurencji. Zacznijmy od najprostszego nieredukowalnego kombinatora
x
W pierwszym lambda wielokrotnie podstawiony przez drugi lambda. Prosta konwersja alfa czyni ten proces jaśniejszym:Tzn. Zmienna w pierwszej lambdzie zawsze znika. Więc jeśli dodamy
f
do pierwszej lambdaf
wola bob góręMamy swoje
omega
plecy. Teraz powinno być jasne, że jeśli dodamyf
do drugiej lambda, tof
pojawi się w pierwszej lambdzie, a potem się podskoczy:Od
możemy przepisać wyrażenie jako
co jest sprawiedliwe
i mamy nasze równanie
Y f = f (Y f)
. Tak więcY
kombinator jest zasadniczof
f
poruszało się w góręźródło
Być może widziałeś klasyczny przykład równania bez normalnej postaci:
Podobne równanie sugeruje równanie ogólne:
(A) jest sposobem na pisanie ogólnych równań rekurencyjnych w rachunku lambda (poza prymitywnym rekurencyjnym). Jak więc rozwiązać równanie ? Podłącz dla w powyższym równaniu, aby uzyskać:Yf=f(Yf) f R
źródło