Kombinator stałopunktowy - Fixed-point combinator

W matematyce i ogólnie informatyce stały punkt funkcji to wartość, która jest przypisywana sobie przez funkcję.

W rachunek kombinatorów na informatyce , a operator paradoksalny (lub operator paradoksalny ) jest funkcja wyższego rzędu , która wraca kilka stałym punktem jego argumentów funkcji, jeśli taka istnieje.

Formalnie, jeśli funkcja f ma jeden lub więcej punktów stałych, to

a co za tym idzie, poprzez wielokrotne stosowanie,

Kombinator Y

W klasycznym beztypowym rachunku lambda każda funkcja ma ustalony punkt.

Szczególną implementacją poprawki jest paradoksalny kombinator Y Curry'ego , reprezentowany przez

W programowaniu funkcjonalnym kombinator Y może służyć do formalnego definiowania funkcji rekurencyjnych w języku programowania, który nie obsługuje rekurencji.

Ten kombinator może być użyty w implementacji paradoksu Curry'ego . Sednem paradoksu Curry'ego jest to, że beztypowy rachunek lambda jest niesłuszny jako system dedukcyjny, a kombinator Y demonstruje to, pozwalając anonimowemu wyrażeniu reprezentować zero, a nawet wiele wartości. Jest to niespójne w logice matematycznej.

Stosowany do funkcji z jedną zmienną kombinator Y zwykle nie kończy się. Bardziej interesujące wyniki uzyskuje się, stosując kombinator Y do funkcji dwóch lub więcej zmiennych. Druga zmienna może służyć jako licznik lub indeks. Wynikowa funkcja zachowuje się jak while lub pętla for w języku imperatywnym.

Zastosowany w ten sposób kombinator Y realizuje prostą rekurencję. W rachunku lambda nie można odwoływać się do definicji funkcji w ciele funkcji. Rekurencję można osiągnąć tylko przez przekazanie funkcji jako parametru. Y combinator dowodzi tego stylu programowania.

Kombinator stałopunktowy

Y syntezatora jest realizacja operator paradoksalny w lambda rachunku. Kombinatory stałopozycyjne można również łatwo zdefiniować w innych językach funkcjonalnych i imperatywnych. Implementacja w rachunku lambda jest trudniejsza ze względu na ograniczenia w rachunku lambda. Kombinator stałopunktowy może być używany w wielu różnych obszarach:

Kombinatory stałoprzecinkowe mogą być stosowane do szeregu różnych funkcji, ale zwykle nie kończą się, chyba że istnieje dodatkowy parametr. Gdy funkcja, która ma zostać naprawiona, odwołuje się do swojego parametru, wywoływane jest kolejne wywołanie funkcji, więc obliczenia nigdy się nie rozpoczynają. Zamiast tego, dodatkowy parametr jest używany do uruchomienia obliczenia.

Typ punktu stałego jest typem zwracanym funkcji, która jest ustalana. Może to być wartość rzeczywista, funkcja lub dowolny inny typ.

W nieopisanym rachunku lambda funkcja, do której ma zostać zastosowany kombinator stałoprzecinkowy, może być wyrażona za pomocą kodowania, takiego jak Church Encoding . W tym przypadku poszczególne terminy lambda (które definiują funkcje) są traktowane jako wartości. „Uruchamianie” (redukcja beta) kombinator stałoprzecinkowy w kodowaniu daje wyrażenie lambda dla wyniku, który może być następnie interpretowany jako wartość stałoprzecinkowa.

Alternatywnie funkcję można uznać za termin lambda zdefiniowany wyłącznie w rachunku lambda.

Te różne podejścia wpływają na to, jak matematyk i programista mogą traktować kombinator stałoprzecinkowy. Matematyk zajmujący się rachunkiem lambda może widzieć kombinator Y zastosowany do funkcji jako wyrażenie spełniające równanie stałoprzecinkowe, a zatem rozwiązanie.

W przeciwieństwie do tego, osoba, która chce zastosować kombinator stałoprzecinkowy tylko do jakiegoś ogólnego zadania programistycznego, może go postrzegać tylko jako sposób implementacji rekurencji.

Wartości i domeny

Każde wyrażenie ma jedną wartość. Jest to prawdą w matematyce ogólnej i musi być prawdą w rachunku lambda. Oznacza to, że w rachunku lambda zastosowanie kombinatora stałoprzecinkowego do funkcji daje wyrażenie, którego wartością jest stały punkt funkcji.

Jest to jednak wartość w domenie rachunku lambda , może nie odpowiadać żadnej wartości w domenie funkcji, więc w sensie praktycznym niekoniecznie jest to punkt stały funkcji, a tylko w domenie rachunku lambda jest to stały punkt równania.

Rozważmy na przykład

Podział na zawartych numery mogą być realizowane w kodowaniu Church, tak M , mogą być reprezentowane przez okres lambda. To równanie nie ma rozwiązania w liczbach rzeczywistych. Ale w dziedzinie liczb zespolonych i oraz -i są rozwiązaniami. To pokazuje, że mogą istnieć rozwiązania równania w innej dziedzinie. Jednak człon lambda dla rozwiązania powyższego równania jest dziwniejszy. Termin lambda reprezentuje stan, w którym x może być i lub -i , jako jedna wartość. Informacje rozróżniające te dwie wartości zostały utracone przy zmianie domeny.

Dla matematyka zajmującego się rachunkiem lambda jest to konsekwencja definicji rachunku lambda. Dla programisty oznacza to, że redukcja beta wyrażenia lambda będzie zapętlać się w nieskończoność, nigdy nie osiągając normalnej postaci.

Funkcja a implementacja

Kombinator stałoprzecinkowy może być zdefiniowany w matematyce, a następnie zaimplementowany w innych językach. Matematyka ogólna definiuje funkcję na podstawie jej własności ekstensjonalnych . Oznacza to, że dwie funkcje są równe, jeśli wykonują to samo mapowanie. Rachunek lambda i języki programowania traktują tożsamość funkcji jako własność intensjonalną . Tożsamość funkcji opiera się na jej implementacji.

Funkcja rachunku lambda (lub termin) jest implementacją funkcji matematycznej. W rachunku lambda istnieje szereg kombinatorów (implementacji), które spełniają matematyczną definicję kombinatora stałoprzecinkowego.

Co to jest „kombinator”?

Logika kombinatoryczna jest teorią funkcji wyższego rzędu . Syntezatora jest zamknięty wyrażenie lambda, co oznacza, że nie ma wolnych zmiennych. Kombinatory można łączyć, aby kierować wartości do ich właściwych miejsc w wyrażeniu bez nazywania ich zmiennymi.

Wykorzystanie w programowaniu

Kombinatory stałoprzecinkowe mogą być używane do implementacji rekurencyjnej definicji funkcji. Jednak rzadko są używane w praktycznym programowaniu. Silnie normalizujące systemy typów, takie jak po prostu typowany rachunek lambda uniemożliwiają brak zakończenia, a zatem kombinatory stałoprzecinkowe często nie mogą być przypisane do typu lub wymagają złożonych cech systemu typów. Ponadto kombinatory stałoprzecinkowe są często nieefektywne w porównaniu z innymi strategiami implementacji rekurencji, ponieważ wymagają większej redukcji funkcji oraz konstruują i rozdzielają krotkę dla każdej grupy wzajemnie rekurencyjnych definicji.

Funkcja silnia

Funkcja silni stanowi dobry przykład zastosowania kombinatora stałoprzecinkowego. Wynik demonstruje prostą rekurencję, jaka zostałaby zaimplementowana w pojedynczej pętli w języku imperatywnym. Definicja użytych liczb jest wyjaśniona w kodowaniu Church .

Funkcja przyjmująca siebie jako parametr to

Daje to YF n jako

Ustawienie daje

Ta definicja stawia F w roli ciała pętli, która ma być iterowana i jest równoważna matematycznej definicji silni:

Kombinatory stałopozycyjne w rachunku lambda

Y syntezatora odkryte przez Haskell B. Curry , jest zdefiniowany jako

Redukcja beta tego daje:

(z definicji Y )
(przez β-redukcję λf: przyłożone Y do g)
(przez β-redukcję λx: zastosowana funkcja lewa do funkcji prawej)
(przez drugą równość)

Wielokrotne stosowanie tej równości daje:

(Powyższą równość należy traktować jako sekwencję wieloetapowych β-redukcji od lewej do prawej. Termin lambda nie może, ogólnie rzecz biorąc, β-redukować do terminu . Zamiast tego można interpretować znaki równości jako β-równoważności wielostopniowych β-redukcji, aby umożliwić jazdę w obu kierunkach.)

Równoważna definicja kombinatora stałoprzecinkowego

Ten kombinator stałoprzecinkowy można zdefiniować jako y , jako in

Wyrażenie na y można wyprowadzić przy użyciu reguł z definicji wyrażenia let . Po pierwsze, korzystając z reguły

daje

Również, używając

daje

A następnie stosując zasadę redukcji eta ,

daje

Wyprowadzenie kombinatora Y

Kombinator Y Curry'ego można łatwo uzyskać z definicji y .

Począwszy od,

Abstrakcja lambda nie obsługuje odwołań do nazwy zmiennej w zastosowanym wyrażeniu, więc x musi być przekazany jako parametr do x . Możemy myśleć o tym jako o zastąpieniu x przez xx , ale formalnie nie jest to poprawne. Zamiast definiować y przez daje

Wyrażenie let można traktować jako definicję funkcji y , gdzie z jest parametrem. Instancja z jak y w wywołaniu daje

A ponieważ parametr z zawsze przekazuje funkcję y ,

Stosując zasadę redukcji eta ,

daje

Ekspresji Let może być wyrażona jako abstrakcji lambda ; za pomocą

daje

Jest to prawdopodobnie najprostsza implementacja kombinatora stałoprzecinkowego w rachunku lambda. Jednak jedna redukcja beta daje bardziej symetryczną formę kombinatora Y Curry'ego:

Zobacz także Tłumaczenie między wyrażeniami let i lambda .

Inne kombinatory stałopunktowe

W nieopisanym rachunku lambda kombinatory stałoprzecinkowe nie są szczególnie rzadkie. W rzeczywistości jest ich nieskończenie wiele. W 2005 roku Mayer Goldberg wykazał, że zbiór kombinatorów stałoprzecinkowych nietypowego rachunku lambda jest rekurencyjnie przeliczalny .

Y syntezatora może być wyrażona w SKI nazębnego co

Najprostszym kombinatorem stałoprzecinkowym w rachunku SK, znalezionym przez Johna Trompa , jest

chociaż zauważ, że nie jest w normalnej formie, która jest dłuższa. Ten kombinator odpowiada wyrażeniu lambda

Następujący kombinator stałoprzecinkowy jest prostszy niż kombinator Y, a β-redukuje do kombinatora Y; jest czasami cytowany jako sam kombinator Y:

Innym popularnym kombinatorem stałoprzecinkowym jest kombinator stałoprzecinkowy Turinga (nazwany na cześć jego odkrywcy, Alana Turinga ):

Jego zaletą jest to, że beta redukuje do , podczas gdy i tylko beta redukuje do wspólnego terminu.

ma również prosty formularz call-by-value:

Analogiem rekurencji wzajemnej jest wielowariantowy kombinator stałoprzecinkowy , który może być oznaczony jako Y*.

Ścisły kombinator stałopunktowy

W ścisłym języku programowania kombinator Y będzie się rozszerzał aż do przepełnienia stosu lub nigdy się nie zatrzyma w przypadku optymalizacji funkcji ogona. Z syntezatora będzie działać w ścisłym językach (zwanych również językach chętny, gdzie kolejność aplikacyjnych ocena jest stosowana). Z syntezatora ma następny argument określony jednoznacznie, zapobieganie ekspansji Z g w prawej strony definicji:

aw rachunku lambda jest to rozszerzenie eta kombinatora Y :

Niestandardowe kombinatory stałopunktowe

W nieopisanym rachunku lambda istnieją terminy, które mają to samo drzewo Böhma co kombinator stałoprzecinkowy, czyli mają to samo nieskończone rozszerzenie λx.x (x (x ... )). Są to tak zwane niestandardowe kombinatory stałoprzecinkowe . Każdy kombinator stałoprzecinkowy jest również niestandardowy, ale nie wszystkie niestandardowe kombinatory stałoprzecinkowe są kombinatorami stałoprzecinkowymi, ponieważ niektóre z nich nie spełniają równania, które definiuje „standardowe”. Te dziwne kombinatory nazywane są ściśle niestandardowymi kombinatorami stałoprzecinkowymi ; przykładem jest następujący kombinator:

gdzie

Zbiór niestandardowych kombinatorów stałoprzecinkowych nie jest rekurencyjnie przeliczalny.

Implementacja w innych językach

(Kombinator Y jest szczególną implementacją kombinatora stałoprzecinkowego w rachunku lambda. Jego struktura jest określona przez ograniczenia rachunku lambda. Nie jest konieczne ani pomocne używanie tej struktury w implementacji kombinatora stałoprzecinkowego w innych językach. )

Poniżej podano proste przykłady kombinatorów stałoprzecinkowych zaimplementowanych w niektórych paradygmatach programowania .

Leniwe wdrożenie funkcjonalne

W języku obsługującym leniwą ocenę , jak w Haskell , możliwe jest zdefiniowanie kombinatora stałoprzecinkowego za pomocą równania definiującego kombinatora stałoprzecinkowego, który umownie nazywa się fix. Ponieważ Haskell ma leniwe typy danych, ten kombinator może być również używany do definiowania stałych punktów konstruktorów danych (a nie tylko do implementowania funkcji rekurencyjnych). Poniżej podano definicję, a następnie kilka przykładów użycia. W Hackage oryginalna próbka to:

fix, fix' :: (a -> a) -> a
fix f = let x = f x in x         -- Lambda dropped. Sharing.
                                 -- Original definition in Data.Function.
-- alternative:
fix' f = f (fix' f)              -- Lambda lifted. Non-sharing.

fix (\x -> 9)                    -- this evaluates to 9

fix (\x -> 3:x)                  -- evaluates to the lazy infinite list [3,3,3,...]

fact = fix fac                   -- evaluates to the factorial function
  where fac f 0 = 1
        fac f x = x * f (x-1)

fact 5                           -- evaluates to 120

Ścisła implementacja funkcjonalna

W ściśle funkcjonalnym języku argument f jest wcześniej rozszerzany, dając nieskończoną sekwencję wywołań,

.

Można to rozwiązać, definiując fix z dodatkowym parametrem.

let rec fix f x = f (fix f) x (* note the extra x; here fix f = \x-> f (fix f) x *)

let factabs fact = function   (* factabs has extra level of lambda abstraction *)
   0 -> 1
 | x -> x * fact (x-1)

let _ = (fix factabs) 5       (* evaluates to "120" *)

Implementacja języka imperatywnego

Ten przykład jest nieco interpretacyjną implementacją kombinatora stałoprzecinkowego. Klasa służy do przechowywania funkcji fix , zwanej fixer . Funkcja do naprawienia jest zawarta w klasie, która dziedziczy po fixer. Funkcja fix uzyskuje dostęp do funkcji, która ma zostać naprawiona, jako funkcja wirtualna. Jeśli chodzi o ścisłą definicję funkcjonalną, fix otrzymuje wyraźnie dodatkowy parametr x , co oznacza, że ​​leniwa ocena nie jest potrzebna.

template <typename R, typename D>
class fixer
{
public:
    R fix(D x)
    {
        return f(x);
    }
private:
    virtual R f(D) = 0;
};

class fact : public fixer<long, long>
{
    virtual long f(long x)
    {
        if (x == 0)
        {
            return 1;
        }
        return x * fix(x-1);
    }
};

long result = fact().fix(5);

W języku imperatywno-funkcjonalnym, takim jak Lisp , Scheme lub Racket , Landin (1963) sugeruje użycie przypisania zmiennej do stworzenia kombinatora stałoprzecinkowego:

(define Y!
  (lambda (f-maker)
    ((lambda (f)
       (set! f (f-maker (lambda (x) (f x)))) ;; assignment statement
       f)
     'NONE)))

Używając rachunku lambda z aksjomatami dla instrukcji przypisania, można pokazać, że Y! spełnia to samo prawo stałoprzecinkowe, co kombinator Y call-by-value:

Pisanie na maszynie

W Systemie F (polimorficzny rachunek lambda) polimorficzny kombinator stałoprzecinkowy ma typ;

∀a.(a → a) → a

gdzie a jest zmienną typu . Oznacza to, że fix przyjmuje funkcję, która odwzorowuje a → a i używa jej do zwrócenia wartości typu a.

W prostym typowanym rachunku lambda rozszerzonym o rekurencyjne typy danych można pisać operatory stałoprzecinkowe, ale typ "użytecznego" operatora stałoprzecinkowego (takiego, którego aplikacja zawsze zwraca) może być ograniczony.

W prostym typowanym rachunku lambda , kombinator stałoprzecinkowy Y nie może być przypisany do typu, ponieważ w pewnym momencie poradzi sobie z podkategorią samostosowania zgodnie z regułą aplikacji:

gdzie ma nieskończony typ . W rzeczywistości nie można wpisać żadnego kombinatora stałoprzecinkowego; w tych systemach wszelkie wsparcie dla rekurencji musi być wyraźnie dodane do języka.

Wpisz kombinator Y

W językach programowania obsługujących rekurencyjne typy danych możliwe jest wpisanie kombinatora Y poprzez odpowiednie uwzględnienie rekurencji na poziomie typu. Konieczność samodzielnego zastosowania zmiennej x może być zarządzana za pomocą typu (Rec a), który jest zdefiniowany jako izomorficzny z (Rec a -> a).

Na przykład w poniższym kodzie Haskella mamy Ini outjesteśmy nazwami dwóch kierunków izomorfizmu, z typami:

In :: (Rec a -> a) -> Rec a
out :: Rec a -> (Rec a -> a)

co pozwala nam napisać:

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

Lub równoważnie w OCaml:

type 'a recc = In of ('a recc -> 'a)
let out (In x) = x

let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a))

Alternatywnie:

let y f = (fun x -> f (fun z -> out x x z)) (In (fun x -> f (fun z -> out x x z)))

Informacje ogólne

Ponieważ kombinatory stałoprzecinkowe mogą być wykorzystywane do implementacji rekurencji, możliwe jest wykorzystanie ich do opisu określonych typów obliczeń rekurencyjnych, takich jak te w iteracji stałoprzecinkowej , metody iteracyjne , łączenie rekurencyjne w relacyjnych bazach danych , analiza przepływu danych , FIRST i FOLLOW zestawy nieterminali w gramatyce bezkontekstowej , domknięciu przechodnim i innych typach operacji domknięcia .

Funkcja, dla której każde wejście jest punktem stałym, nazywana jest funkcją tożsamości . Formalnie:

W przeciwieństwie do uniwersalnej kwantyfikacji przez wszystkie , kombinator stałoprzecinkowy konstruuje jedną wartość, która jest punktem stałym . Niezwykłą właściwością kombinatora stałoprzecinkowego jest to, że konstruuje on punkt stały dla dowolnej danej funkcji .

Inne funkcje mają tę specjalną właściwość, że po jednokrotnym zastosowaniu kolejne aplikacje nie przynoszą żadnego efektu. Bardziej formalnie:

Takie funkcje nazywane są idempotentnymi (zobacz także Projekcja (matematyka) ). Przykładem takiej funkcji jest funkcja, która zwraca 0 dla wszystkich parzystych liczb całkowitych i 1 dla wszystkich nieparzystych liczb całkowitych.

W rachunku lambda , z obliczeniowego punktu widzenia, zastosowanie kombinatora stałoprzecinkowego do funkcji tożsamości lub funkcji idempotentnej zwykle skutkuje obliczeniami niekończącymi. Na przykład otrzymujemy

gdzie wynikowy termin może zredukować się tylko do siebie i reprezentuje nieskończoną pętlę.

Kombinatory stałoprzecinkowe niekoniecznie istnieją w bardziej restrykcyjnych modelach obliczeń. Na przykład nie istnieją w prostym rachunku lambda .

Kombinator Y umożliwia zdefiniowanie rekursji jako zestawu reguł przepisywania bez konieczności obsługi natywnej rekursji w języku.

W językach programowania obsługujących funkcje anonimowe kombinatory stałoprzecinkowe umożliwiają definiowanie i używanie anonimowych funkcji rekurencyjnych , tj. bez konieczności wiązania takich funkcji z identyfikatorami . W tym ustawieniu użycie kombinatorów stałoprzecinkowych jest czasami nazywane anonimową rekurencją .

Zobacz też

Uwagi

Bibliografia

Zewnętrzne linki