Teoria typów zależnych i funkcje typu „dowolne”
Moja pierwsza odpowiedź na to pytanie była pełna pojęć, mało szczegółów i zastanawiała się nad pytaniem: „co się dzieje?”; ta odpowiedź będzie taka sama, ale skoncentrowana na pytaniu „czy możemy uzyskać funkcje dowolnego typu?”.
Jednym rozszerzeniem algebraicznych operacji sumy i iloczynu są tak zwane „duże operatory”, które reprezentują sumę i iloczyn sekwencji (lub bardziej ogólnie, sumę i iloczyn funkcji w domenie), zwykle zapisywane Σi Πodpowiednio. Zobacz zapis Sigma .
Więc suma
a₀ + a₁X + a₂X² + ...
może być napisane
Σ[i ∈ ℕ]aᵢXⁱ
gdzie ajest na przykład sekwencja liczb rzeczywistych. Produkt byłby reprezentowany podobnie z Πzamiast Σ.
Kiedy patrzysz z dystansu, ten rodzaj wyrażenia przypomina bardzo „dowolną” funkcję X; jesteśmy oczywiście ograniczeni do wyrażalnych szeregów i związanych z nimi funkcji analitycznych. Czy jest to kandydat na reprezentację w teorii typów? Zdecydowanie!
Klasą teorii typów, które mają bezpośrednie przedstawienie tych wyrażeń, jest klasa teorii typów „zależnych”: teorie z typami zależnymi. Oczywiście mamy terminy zależne od terminów, w językach takich jak Haskell z funkcjami typu i kwantyfikacją typów, terminy i typy zależne od typów. W ustawieniu zależnym dodatkowo mamy typy zależne od warunków. Haskell nie jest językiem zależnym od typu, chociaż wiele funkcji typów zależnych można symulować przez nieco torturowanie tego języka .
Curry-Howard i typy zależne
„Izomorfizm Curry'ego-Howarda” rozpoczął życie jako spostrzeżenie, że terminy i reguły oceniania typów rachunku lambda po prostu wpisanego dokładnie odpowiadają naturalnej dedukcji (sformułowanej przez Gentzena) zastosowanej do intuicyjnej logiki zdań, a typy zajmują miejsce zdań oraz warunki zastępujące dowody, mimo że oba zostały niezależnie wynalezione / odkryte. Od tego czasu jest to ogromne źródło inspiracji dla teoretyków typów. Jedną z najbardziej oczywistych rzeczy do rozważenia jest to, czy i jak tę korespondencję dla logiki zdań można rozszerzyć na logikę predykatu lub wyższego rzędu. Teorie typu zależnego początkowo powstały z tej drogi eksploracji.
Aby zapoznać się z wprowadzeniem do izomorfizmu Curry'ego-Howarda dla rachunku zwykłego rachunku lambda, zobacz tutaj . Na przykład, jeśli chcemy udowodnić A ∧ B, musimy Audowodnić B; dowód łączony to po prostu para dowodów: po jednym dla każdego spójnika.
W odliczeniu naturalnym:
Γ ⊢ A Γ ⊢ B
Γ ⊢ A ∧ B
i w prostym typie rachunku lambda:
Γ ⊢ a : A Γ ⊢ b : B
Γ ⊢ (a, b) : A × B
Podobne zależności istnieją dla ∨typów sum i typów →oraz typów funkcji i różnych reguł eliminacji.
Twierdzenie nie do udowodnienia (intuicyjnie fałszywe) odpowiada typowi niezamieszkanemu.
Mając na uwadze analogię typów jako zdania logiczne, możemy zacząć zastanawiać się, jak modelować predykaty w świecie typów. Istnieje wiele sposobów sformalizowania tego (patrz wprowadzenie do Intuitionistycznej teorii typów Martina-Löfa dla powszechnie stosowanego standardu), ale abstrakcyjne podejście zwykle zauważa, że predykat jest jak zdanie z zmiennymi dowolnymi lub, alternatywnie, funkcja przyjmująca warunki do zdań. Jeśli pozwolimy, aby wyrażenia typu zawierały terminy, wówczas leczenie w stylu rachunku lambda natychmiast stanie się możliwe!
Biorąc pod uwagę tylko konstruktywne dowody, co stanowi dowód ∀x ∈ X.P(x)? Możemy myśleć o tym jako o funkcji dowodowej, przyjmując warunki ( x) do dowodów odpowiadających im zdań ( P(x)). Tak Członkowie (dowodów) typu (propozycja) ∀x : X.P(x)są zależne od funkcji „”, który dla każdego xw Xdają pojęcie typu P(x).
Co ∃x ∈ X.P(x)? Musimy każdy członek X, xwraz z dowodem P(x). Tak członków (dowodów) typu (propozycja) ∃x : X.P(x)są „pary utrzymaniu”: wybitnym określenie xsię X, wraz ze względu na ich rodzaj P(x).
Notacja: użyję
∀x ∈ X...
dla rzeczywistych wypowiedzi na temat członków klasy X, oraz
∀x : X...
dla wyrażeń typu odpowiadających uniwersalnej kwantyfikacji nad typem X. Podobnie dla ∃.
Uwagi kombinatoryczne: produkty i sumy
Oprócz korespondencji typów Curry'ego-Howarda z twierdzeniami, mamy kombinatoryczną zgodność typów algebraicznych z liczbami i funkcjami, co jest głównym punktem tego pytania. Na szczęście można to rozszerzyć na typy zależne przedstawione powyżej!
Użyję notacji modułu
|A|
reprezentowanie „rozmiaru” typu A, wyraźne powiązanie przedstawione w pytaniu między typami i liczbami. Zauważ, że jest to koncepcja poza teorią; Nie twierdzę, że w języku musi istnieć taki operator.
Policzmy możliwe (całkowicie zredukowane, kanoniczne) elementy typu
∀x : X.P(x)
który jest rodzajem funkcji zależnych uwzględniających warunki xtypu Xdo warunków typu P(x). Każda taka funkcja musi mieć dane wyjściowe dla każdego terminu X, a dane wyjściowe muszą być określonego typu. Dla każdego xIN X, to daje to |P(x)|„wybory” na wyjściu.
Punktem wyjścia jest
|∀x : X.P(x)| = Π[x : X]|P(x)|
co oczywiście nie czyni ogromne wiele sensu, jeśli Xjest IO (), ale ma zastosowanie do algebraicznych typów.
Podobnie termin typu
∃x : X.P(x)
Jest to typ par (x, p)z p : P(x), więc biorąc pod uwagę każdy xw Xmożemy skonstruować odpowiednią parę z jakiegokolwiek członka P(x), dając |P(x)|"wyborów.
W związku z tym,
|∃x : X.P(x)| = Σ[x : X]|P(x)|
z tymi samymi zastrzeżeniami.
Uzasadnia to powszechną notację typów zależnych w teoriach za pomocą symboli Πi Σ, i rzeczywiście, wiele teorii zaciera rozróżnienie między „dla wszystkich” i „produktem” oraz między „jest” i „sumą”, ze względu na wyżej wspomniane korespondencje.
Zbliżamy się!
Wektory: reprezentujące krotki zależne
Czy możemy teraz zakodować wyrażenia numeryczne takie jak
Σ[n ∈ ℕ]Xⁿ
jako wyrażenia typu?
Nie do końca. Chociaż możemy nieformalnie rozważyć znaczenie wyrażeń takich jak Xⁿw Haskell, gdzie Xjest typ i nliczba naturalna, jest to nadużycie zapisu; Jest to wyrażenie typu zawierający numer: wyraźnie nie poprawny wyraz.
Z drugiej strony, w przypadku typów zależnych na zdjęciu, typy zawierające liczby są właśnie tym celem; w rzeczywistości zależne krotki lub „wektory” są bardzo często cytowanym przykładem tego, w jaki sposób typy zależne mogą zapewnić pragmatyczne bezpieczeństwo na poziomie typu dla operacji takich jak dostęp do listy . Wektor jest tylko listą wraz z informacją na temat typu dotyczącą jego długości: dokładnie tym, czego szukamy dla wyrażeń typu Xⁿ.
Na czas trwania tej odpowiedzi pozwól
Vec X n
być typem nwektorów długości Xwartości -type.
Technicznie njest to, zamiast rzeczywistej liczby naturalnej, reprezentacja w systemie liczby naturalnej. Możemy reprezentować liczby naturalne ( Nat) w stylu Peano jako zero ( 0) lub następcę ( S) innej liczby naturalnej, i n ∈ ℕpiszę, ˻n˼aby oznaczać termin, w Natktórym reprezentuje n. Na przykład ˻3˼jest S (S (S 0)).
Następnie mamy
|Vec X ˻n˼| = |X|ⁿ
dla każdego n ∈ ℕ.
Typy nat: promowanie ℕ haseł do typów
Teraz możemy zakodować wyrażenia takie jak
Σ[n ∈ ℕ]Xⁿ
jako typy. To szczególne wyrażenie dałoby początek typowi, który jest oczywiście izomorficzny z typem list X, jak określono w pytaniu. (Nie tylko to, ale z teoretycznego punktu widzenia funkcja typu - która jest funktorem - biorąc Xpod uwagę powyższy typ jest naturalnie izomorficzna w stosunku do funktora List.)
Ostatnim elementem układanki dla „arbitralnych” funkcji jest sposób kodowania
f : ℕ → ℕ
wyrażenia jak
Σ[n ∈ ℕ]f(n)Xⁿ
abyśmy mogli zastosować dowolne współczynniki do szeregu mocy.
Rozumiemy już zgodność typów algebraicznych z liczbami, co pozwala nam mapować typy na liczby i funkcje typów na funkcje numeryczne. Możemy też iść w drugą stronę! - biorąc liczbę naturalną, istnieje oczywiście możliwy do zdefiniowania typ algebraiczny z tak wieloma członami terminowymi, niezależnie od tego, czy mamy typy zależne, czy nie. Możemy to łatwo udowodnić poza teorią typów przez indukcję. Potrzebujemy sposobu mapowania liczb naturalnych na typy wewnątrz systemu.
Przyjemną realizacją jest to, że gdy mamy typy zależne, dowody indukcyjne i konstrukcyjne rekurencyjne stają się bardzo podobne - w rzeczywistości są one takie same w wielu teoriach. Skoro możemy przez indukcję udowodnić, że istnieją typy, które spełniają nasze potrzeby, czy nie powinniśmy być w stanie je zbudować?
Istnieje kilka sposobów reprezentowania typów na poziomie terminu. Posłużę się tutaj wyimaginowaną notacją haskalijską *dla wszechświata typów, który zwykle uważany jest za typ w zależności od niego. 1
Podobnie, istnieje co najmniej tyle sposobów na zanotowanie „ ℕeliminacji”, ile jest zależnych teorii typów. Użyję notacji pasującej do wzoru Haskellisha.
Musimy mapowanie, αod Natcelu *, z właściwością
∀n ∈ ℕ.|α ˻n˼| = n.
Występuje następująca pseudodefinicja.
data Zero -- empty type
data Successor a = Z | Suc a -- Successor ≅ Maybe
α : Nat -> *
α 0 = Zero
α (S n) = Successor (α n)
Widzimy więc, że działanie αzwierciadła odzwierciedla zachowanie następcy S, czyniąc z niego rodzaj homomorfizmu. Successorjest funkcją typu, która „dodaje jedną” do liczby elementów typu; to znaczy |Successor a| = 1 + |a|dla każdego ao określonym rozmiarze.
Na przykład α ˻4˼(który jest α (S (S (S (S 0))))) jest
Successor (Successor (Successor (Successor Zero)))
a warunki tego typu to
Z
Suc Z
Suc (Suc Z)
Suc (Suc (Suc Z))
daje nam dokładnie cztery elementy: |α ˻4˼| = 4.
Podobnie dla każdego n ∈ ℕmamy
|α ˻n˼| = n
jako wymagane.
- Wiele teorii wymaga, aby członkowie
*byli zwykłymi przedstawicielami typów, a operacja jest zapewniona jako jawne odwzorowanie terminów typów *na powiązane z nimi typy. Inne teorie pozwalają, aby same dosłowne typy były jednostkami na poziomie terminowym.
Funkcje „arbitralne”?
Teraz mamy aparat do wyrażenia w pełni ogólnej serii mocy jako typu!
Serie
Σ[n ∈ ℕ]f(n)Xⁿ
staje się typem
∃n : Nat.α (˻f˼ n) × (Vec X n)
gdzie ˻f˼ : Nat → Natjest odpowiednia reprezentacja w języku funkcji f. Możemy to zobaczyć w następujący sposób.
|∃n : Nat.α (˻f˼ n) × (Vec X n)|
= Σ[n : Nat]|α (˻f˼ n) × (Vec X n)| (property of ∃ types)
= Σ[n ∈ ℕ]|α (˻f˼ ˻n˼) × (Vec X ˻n˼)| (switching Nat for ℕ)
= Σ[n ∈ ℕ]|α ˻f(n)˼ × (Vec X ˻n˼)| (applying ˻f˼ to ˻n˼)
= Σ[n ∈ ℕ]|α ˻f(n)˼||Vec X ˻n˼| (splitting product)
= Σ[n ∈ ℕ]f(n)|X|ⁿ (properties of α and Vec)
Jak to „arbitralne”? Metodą tą ograniczamy się nie tylko do współczynników całkowitych, ale także do liczb naturalnych. Poza tym, fmoże być cokolwiek, biorąc pod uwagę język Turing Complete z typami zależnymi, możemy reprezentować dowolną funkcję analityczną o współczynnikach liczb naturalnych.
Nie badałem interakcji tego z, na przykład, przypadkiem przedstawionym w pytaniu List X ≅ 1/(1 - X)lub jaki możliwy sens takie negatywne i niecałkowate „typy” mogą mieć w tym kontekście.
Mam nadzieję, że ta odpowiedź w jakiś sposób pozwoli zbadać, jak daleko możemy posunąć się z funkcjami dowolnego typu.