Jak definiuje się dualność typów?

W Wadler's Recursive Types za darmo! [1], zademonstrował dwa typy, i i twierdził, że są podwójne . W szczególności wskazał, że typ nie jest dualistą poprzedniej. Wydaje się, że dualność, o której tu mowa, różni się logicznie od dualności De Morgana. Zastanawiam się, w jaki sposób definiuje się dualność typów, szczególnie dla wymienionych trzech typów, dlaczego drugi jest podwójny z pierwszym, a trzeci nie. Dzięki.∃ X . ( X → F ( X ) ) × $\forall X . (F(X) \rightarrow X) \rightarrow X$$\exists X . (X \rightarrow F(X)) \times X$$\exists X . X \rightarrow (X \rightarrow F(X))$

[1] http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt

W tym kontekście dualność odnosi się do zajęcia najmniej stałego punktu w jednym przypadku i największego stałego punktu w drugim. Powinniśmy starać się zrozumieć, w jakim sensie i G = ∃ X . ( X → F ( X ) ) x X są "najmniej" i "największe" roztwory rekurencyjnych równania F ( x ) ≅ X .$L = \forall X . (F(X) \to X) \to X$$G = \exists X . (X \to F(X)) \times X$$F(X) \cong X$

Po pierwsze, i G są rzeczywiście stałymi punktami (przy pewnych założeniach technicznych, które ograniczają naturę F ), ponieważ mapy porównawcze v : F ( L ) → L i w : G → F ( G ) podane przez $L$$G$$F$$v : F(L) \to L$$w : G \to F(G)$ i W ( X , ( F , x ) ) = K ( λ Y :

$$v \, x \, X \, g = g \, (F (\lambda h : L \,.\, h \,X\, g)\, x)$$ to izomorfizmy. Zauważ, że użyliśmy faktu, że F jest funktorem, tj. Jest monotoniczny, kiedy zastosowaliśmy go do funkcji. $$w (X, (f, x)) = F (\lambda y : X \,.\, (X, (f, y))) \, (f x)$$ $F$

Załóżmy, że jest rozwiązanie kwestii F ( Y ) ≅ Y z pośredniczącym izomorfizmie U : F ( Y ) → Y . Mamy zatem mapy kanoniczne α : L → Y  i  β : Y → G zdefiniowane przez $Y$$F(Y) \cong Y$$u : F(Y) \to Y$

$$\alpha : L \to Y \text{ and } \beta : Y\to G$$ i $$\alpha \, f = f\, Y\, u$$ Dlatego L jestnajmniejsze,ponieważ możemy zmapować z niego do dowolnego innego rozwiązania, a G jestnajwiększe,ponieważ możemy zmapować z dowolnego innego rozwiązania. Możemy to wszystko uściślić, mówiąc o początkowych algebrach i końcowych węgielach, ale chcę, aby moja odpowiedź była krótka i słodka, a cody i tak wyjaśnił algebry. $$\beta \, y = (Y, (u^{-1}, y)).$$ $L$$G$

W praktyce najmniejszymi rozwiązaniami są chętne typy danych, a największymi rozwiązaniami są leniwe typy danych. Na przykład, jeśli czym w pierwszym przypadku mamy skończonych listy „S i w drugim skończony i nieskończony listy ” S.$F(X) = 1 + A \times X$$A$$A$

Odpowiedź można zrozumieć kategorycznie przez soczewki F-algebry . Kategoryczny reprezentacją rekurencyjnego typu w kategorii C, można z grubsza określić za pomocą funktor F : C → C . Jeden następnie pracuje w kategorii F- algebry z$I$$\cal C$$F:{\cal C}\rightarrow{\cal C}$$F$

• jako obiekty: obiekty z C wraz z morfizmem α : F ( A ) → $A$$\cal C$ $$\alpha:F(A)\rightarrow A$$

• jako strzałki: kwadraty

  

Teraz aby stać się typem rekurencyjnym reprezentowanym przez F , muszę być początkowy w tej kategorii: potrzebujemy$I$$F$$I$

1. Morfizmem $in:F(I) \rightarrow I$
2. Dla każdego -algebrze ( A , α ) morfizmem f O l d : I → sprawia, że odpowiedni kwadratowy dojazdy.$F$$(A,\alpha)$$fold: I\rightarrow A$

Teraz zdefiniować . Jest całkiem jasne, jak zbudować f o, l D : wystarczy wziąć f o, l D = λ I : I . I α : I → budynku i n jest nieco bardziej skomplikowane, Wadler wyjaśnia, więc nie będę próbować. Zauważ jednak, że wymaga to faktu, że F jest funktorem$I=\forall X.(F(X)\rightarrow X)\rightarrow X$$fold$

$$fold=\lambda i:I. i\ A\ \alpha : I\rightarrow A$$ $in$$F$, co można uznać za wymóg dodatni.

Teraz w teorii kategorii często chcemy wziąć pod uwagę sytuację, w której wszystkie strzałki są odwrócone. W tym przypadku, biorąc pod uwagę , możemy rozważyć kategorię F- węglowy z$F$$F$

• Jako obiektów: obiekty o C wraz z morfizmem Ohm : Z → K ( Z $Z$$\cal C$ $$\omega: Z\rightarrow F(Z)$$
• Jako strzałki kwadraty jak w przypadku algebry (ale z odwróconym α i β ).$F$$\alpha$$\beta$

Teraz chcemy zbadać obiekt końcowy tej kategorii. Wymagania są teraz odwrócone:$T$

1. Morfizmem $out:T\rightarrow F(T)$
2. Dla każdego -coalgebra Z , morfizmem c O M O L d : Z → T .$F$$Z$$cofold: Z\rightarrow T$

Jak to robimy? A także określa Wadler bierzemy . W podobny sposób, niż wcześniej, mają c o, f O l d = X Ż : Z . ( Z , ω , oo ) : Z → T Ta konstrukcja nie będzie pracował, gdybyśmy zamiast podjąć T = ∃ X . X → ( $T=\exists X.(X\rightarrow F(X))\times X$

$$cofold = \lambda z:Z.(Z,\omega,z) : Z\rightarrow T$$ .$T=\exists X.X\rightarrow (X\rightarrow F(X))$

Z mojego doświadczenia wynika , że dobrym i operacyjnym sposobem na zrozumienie dualności typów dla calculi jest przejście przez π- calculus.$\lambda$$\pi$

Kiedy tłumaczysz (rozkładasz) typy na rachunek procesowy, dualność staje się prosta: dane wejściowe są podwójne do danych wyjściowych i odwrotnie . W dualności nie ma (dużo) więcej.

$\pi$$\alpha = (Bool, Int)^{\uparrow}$$\alpha$$\alpha$$x$$\overline{x}\langle false,7\rangle$$\overline{\alpha}$$(v, w)$$v$$w$$\overline{\alpha}$$(bool,int)^{\downarrow}$$\overline{\alpha}$$x$$c(v,w).0$

$\beta = (int, (int)^{\uparrow})^{\downarrow}$$(v, w)$$v$$w$$\overline{\beta} =(int, (int)^{\downarrow})^{\uparrow}$$\alpha$$\overline{\alpha}$$P$$\alpha$$x$$Q$$\overline{\alpha}$$x$$P$$Q$$\beta$$\overline{\beta}$

$\forall X.(X,(X)^{\uparrow})^{\downarrow}$$(v, w)$$v$$X$$w$$X$$x$

$$x(vw).\overline{w}v$$ $\forall X.(X,(X)^{\uparrow})^{\downarrow}$

Co oznacza uniwersalna kwantyfikacja na poziomie procesu? Istnieje prosta interpretacja: jeśli dane są wpisywane przez zmienną typu, nie mogą być użyte jako przedmiot wyniku, tylko obiekt. Nie możemy więc sprawdzać tych danych, możemy je tylko przekazać lub zapomnieć.

$\forall X.(X,(X)^{\uparrow})^{\downarrow}$$\exists X.(X,(X)^{\downarrow})^{\uparrow}$

Teorię tę opracowano bardziej szczegółowo w [1, 2, 3] i niektórych innych, trudniej dostępnych pracach, i bardzo precyzyjnie dotyczyły spolaryzowanej logiki liniowej i jej pojęcia dualności w 4 .

$\lambda$$\lambda$$\pi$$\lambda$$\pi$$\lambda$

$\pi$

$\pi$

$\pi$

4 K. Honda i in., Dokładna zgodność między typowanym pi-rachunek a spolaryzowanymi siatkami próbnymi .

5 R. Milner, Funkcje jako procesy .