Wprowadzenie do teorii typów Martina-Löfa

36

Jakie byłoby najlepsze wprowadzenie do pomysłów Per Martina-Löfsa na temat teorii typów? Obejrzałem niektóre wykłady ze szkoły letniej w Oregon PL, ale nadal jestem zdziwiony następującym pytaniem:

Jaki jest typ

Wiem, co to jest zestaw, ponieważ można je zdefiniować za pomocą zwykłych aksjomatów ZF i mają one bardzo intuicyjny konkretny model; pomyśl tylko o koszyku pełnym rzeczy. Jednak nie spotkałem się jeszcze z rozsądną definicją typu i zastanawiałem się, czy istnieje jakieś źródło, które mogłoby wypaczyć ten pomysł na manekina.

logic type-theory

— dst
źródło

4

Książka HoTT zawiera wprowadzenie, które porównuje typy i zestawy, być może to pomoże, patrz sekcja 1.1 homotopytypetheory.org/book . Ale co ważniejsze, chcesz, abyśmy wszczepili w twoją głowę prawidłową ideę typów, podczas gdy dla zestawów jesteś szczęśliwy, że opisujesz je aksjomatami, bez nalegania, aby wiedzieć, „czym one naprawdę są”. Cóż, typy są opisane przez reguły wnioskowania dla typów. I mają bardzo intuicyjny konkretny model, wiecie, wygrzany wypełniony klockami Lego. Cokolwiek możesz z nich zbudować, jest tego rodzaju.

— Andrej Bauer,

Myślę, że największym problemem jest oderwanie mojego mózgu od teorii mnogości. Nie jestem jednak pewien, jak dobra jest analogia Lego. Jakie są bloki? Jeśli x: A i y: A zazwyczaj nie mogę nic z nich zbudować, chyba że A jest jakimś rekurencyjnym typem strzałki. Oczywiście często mogę miksować różne rodzaje, aby zbudować coś trzeciego typu ...

— dst

4

Klocki Lego są konstruktorami typów. Na przykład z i możesz zbudować i i , i i . Możesz także budować nowe typy, na przykład i i tak dalej. Ludzie mają różne intuicje dotyczące typów. Zestawy to jeden z nich, ale surowy. Typy są również jak przestrzenie topologiczne. Są również jak ustrukturyzowane dane w programowaniu. Są również podobne do -groupoids. To jest jego piękno, bogactwo możliwości. Wybierz jedną możliwość i biegnij z nią.

x : A

$x : A$

y : A

$y : A$

(x, y)

$(x,y)$

(x, x)

$(x,x)$

i n l (x)

$\mathsf{inl}(x)$

{r e l f}_{x}

$\mathsf{relf}_x$

λ z : A . x

$\lambda z : A . x$

I d (x, y)

$\mathsf{Id}(x,y)$

\sum_{z : A} I d (x, z)

$\sum_{z : A} \mathsf{Id}(x,z)$

ω

$\omega$

— Andrej Bauer,

31

Typ jest właściwością obliczeń. To, co piszesz po prawej stronie jelita grubego.

Pozwól mi rozwinąć tę kwestię. Zauważ, że terminologia nie jest całkowicie standardowa: niektóre artykuły lub książki mogą używać różnych słów dla niektórych pojęć.

Termin jest elementem składni abstrakcyjnej, która jest przeznaczona do reprezentowania obliczeń. Intuicyjnie jest to parsowane drzewo. Formalnie jest to skończone drzewo, w którym węzły należą do jakiegoś alfabetu. Rachunek bez typu definiuje składnię terminów. Na przykład (nietypowy) rachunek lambda zawiera terminy (zapisane , itd.) Zbudowane z trzech typów węzłów: $M$ $N$

zmienne, arity 0 (ich niezliczona kolekcja), zapisane , itd .; $x$ $y$
zastosowanie zmiennej arity 1 (jej niezliczona kolekcja, z bijectmem do zmiennych), zapisany itp .; $\lambda x. M$
aplikacji z Arity 2, napisany . $M \, N$

Termin jest konstrukcją składniową. A semantyka dotyczy warunków do obliczeń. Istnieje wiele rodzajów semantyki, z których najczęstszą jest operacyjna (opisująca, w jaki sposób terminy mogą zostać przekształcone w inne terminy) lub denotacyjna (opisująca warunki poprzez transformację w inną przestrzeń, zwykle zbudowaną z teorii mnogości).

Typ jest własnością warunkach. System typów dla rachunku bez typów opisuje, które terminy mają jakie typy. Z matematycznego punktu widzenia system typów jest relacją między terminami i typami. Dokładniej, system typów jest rodziną takich relacji, indeksowaną przez konteksty - zazwyczaj kontekst zapewnia co najmniej typy zmiennych (tzn. Kontekst jest funkcją częściową od zmiennych do typów), tak że termin może mieć tylko typ w kontekstach, które zapewniają typ dla wszystkich wolnych zmiennych. Rodzaj obiektu matematycznego zależy od systemu typów.

Niektóre systemy typów są opisywane typami jako zbiory, używając pojęć teorii zbiorów, takich jak przecięcie, połączenie i zrozumienie. Ma to tę zaletę, że opiera się na znanych podstawach matematycznych. Ograniczeniem tego podejścia jest to, że nie pozwala na rozumowanie na temat równoważnych typów.

Wiele systemów typów opisuje same typy jako terminy w rachunku typów. W zależności od systemu typów mogą to być te same warunki lub różne warunki. Użyję wyrażenia bazowego, aby odnieść się do rachunku różniczkowego opisującego obliczenia. Na przykład, prosty typ rachunku lambda wykorzystuje następujący rachunek typów (zapisany itp.): $\tau$

typy podstawowe, o rodzaju 0 (ich skończony lub dający się zliczyć zbiór), zapisane , itd .; $A$ $B$
funkcja, arity 2, zapisana . $\tau_0 \rightarrow \tau_1$

Relacja między terminami i typami, która definiuje prosty typ rachunku lambda, jest zwykle definiowana przez reguły pisania . Reguły pisania nie są jedynym sposobem definiowania systemu typów, ale są wspólne. Działają dobrze w systemach typu kompozycyjnego, tj. Systemach typu, w których typ (-y) terminu jest zbudowany z typów podtermów. Reguły typowania definiują system typów indukcyjnie: każda reguła typowania jest aksjomatem, który stwierdza, że dla dowolnej instancji formuł powyżej reguły poziomej obowiązuje również wzór pod regułą. Zobacz Jak czytać zasady pisania? po więcej szczegółów. Czy istnieje pełny rachunek lambda na maszynie Turinga? może również być interesujące.

W przypadku prostego rachunku lambda, wynik pisania oznacza, że ma typ w kontekście . Pominąłem formalną definicję kontekstów. $\Gamma \vdash M : \tau$ $M$ $\tau$ $\Gamma$

\frac{x : τ \in Γ}{Γ ⊢ x : τ} (Γ) \frac{Γ, x : τ_{0} ⊢ M. : τ_{1}}{Γ ⊢ λ x . M. : τ_{0} \to τ_{1}} (\to ja) \frac{Γ ⊢ M. : τ_{0} \to τ_{1} Γ ⊢ N. : τ_{0}}{Γ ⊢ M. N. : τ_{1}} (\to mi)

$\dfrac{x:\tau \in \Gamma}{\Gamma \vdash x : \tau}(\Gamma) \qquad \dfrac{\Gamma, x:\tau_0 \vdash M : \tau_1}{\Gamma \vdash \lambda x.M : \tau_0 \rightarrow \tau_1}(\mathord{\rightarrow}I) \qquad \dfrac{\Gamma \vdash M : \tau_0 \rightarrow \tau_1 \quad \Gamma \vdash N : \tau_0}{\Gamma \vdash M\,N : \tau_1}(\mathord{\rightarrow}E)$

Na przykład, jeśli i są typami bazowymi, to ma typ w dowolnym kontekście (od dołu do góry, zastosuj dwa razy, a następnie i wreszcie na każdym oddziale). $A$ $B$ $\lambda x. \lambda y. x\,y$ $(A \rightarrow B) \rightarrow A \rightarrow B$ $(\mathord{\rightarrow}I)$ $(\mathord{\rightarrow}E)$ $(\Gamma)$

Możliwe jest interpretowanie typów prostych rachunków lambda jako zbiorów. Sprowadza się to do podania denotacyjnej semantyki dla typów. Dobra semantyka denotacyjna dla terminów podstawowych przypisuje każdemu terminowi podstawowemu element denotacji wszystkich jego typów.

Intuicyjna teoria typów (znana również jako teoria typu Martina-Löfa) jest bardziej złożona niż zwykły rachunek lambda, ponieważ zawiera znacznie więcej elementów w rachunku typów (a także dodaje kilka stałych do warunków podstawowych). Ale podstawowe zasady są takie same. Ważną cechą teorii typów Martina-Löfa jest to, że typy mogą zawierać terminy podstawowe (są to typy zależne ): wszechświat terminów podstawowych i wszechświat typów są takie same, chociaż można je odróżnić za pomocą prostych reguł składniowych (zwykle znanych jako sortowanie, tj. przypisywanie rodzajów do terminów w teorii przepisywania).

Istnieją systemy typów, które idą dalej i całkowicie mieszają typy i warunki podstawowe, dzięki czemu nie ma rozróżnienia między nimi. Mówi się, że takie systemy typu są wyższego rzędu . W takich kamieni, typy mają typy - typ może pojawić się na lewej stronie z . Rachunek budowy jest paradygmat wyższego rzędu typu zależnych. Kostki lambda (znany również jako sześcian Barendregt'a) systemy klasyfikuje typu pod względem tego, czy pozwalają one na warunkach, które zależą od rodzaju ( polimorfizm - niektóre terminy bazowe zawierają typy jak subterms) rodzaje zależy od warunków (typ zależnego) lub typu zależy na typach ( operatory typów - rachunek typów ma pojęcie obliczeń). $:$

Większość systemów typów ma semantykę teoretyczną, aby powiązać je ze zwykłymi podstawami matematyki. W jaki sposób powiązane są języki programowania i podstawy matematyki? a jaka jest różnica między widokami semantycznymi i syntaktycznymi typów funkcji? może być tutaj interesujące. Trwają również prace nad wykorzystaniem teorii typów jako podstawy matematyki - teoria zbiorów jest historycznym fundamentem, ale nie jest to jedyny możliwy wybór. Teoria typów homotopii jest ważnym kamieniem milowym w tym kierunku: opisuje semantykę umyślnej intuicyjnej teorii typów w kategoriach teorii homotopii i konstruuje teorię zbiorów w tych ramach.

Polecam książki Benjamina Pierce'a Rodzaje i języki programowania oraz postępy Tematy w typach i językach programowania . Są one dostępne dla każdego studenta bez żadnych innych wymagań poza podstawową znajomością formalnego rozumowania matematycznego. TAPL opisuje wiele systemów typów; typy zależne są przedmiotem rozdziału 2 ATTAPL.

— Gilles „SO- przestań być zły”
źródło

+1 dla TAPL. Mogłem nauczyć się sporo o typach z czytania tej książki.

— Guy Coder

Nie jestem pewien, czy ATTAPL jest dobrym punktem wyjścia do poznania typów zależnych.

— Martin Berger

15

Być może lepszym pytaniem dla kogoś, kto wywodzi się z teorii zbiorów i boryka się z różnicami między teorią zbiorów a teorią typu Martina-Löfa, jest zastanowienie się, czym są zbiory. Twoje intuicje dotyczące teorii mnogości i podstaw matematyki zostaną zainfekowane niekwestionowanymi założeniami teoretycznymi, które przyjmujesz za pewnik. Niestety teoria typów Martina-Löfa nie podziela tych założeń.

W przeciwieństwie do konwencjonalnego zrozumienia, teoria zbiorów jest teorią dwóch relacji: równości i ustalonego członkostwa , a nie tylko ustalonego członkostwa. I te dwie relacje zbudowane są w zasadniczo odrębnych fazach.

Budujemy logikę pierwszego rzędu jako teorię równości arbitralnych rzeczy (nie tylko zbiorów). Logika pierwszego rzędu wykorzystuje nieformalne pojęcie dowodu. Samo potwierdzenie koncepcji nie jest formalnie możliwe do wyrażenia wyłącznie w logice pierwszego rzędu.
Następnie budujemy teorię zbiorów na podstawie logiki pierwszego rzędu jako teorii zbiorów i przynależności do zestawu.
Przynależność do zbioru i równość są następnie powiązane z aksjomatem ekstensywności, który mówi, że dwa zbiory są równe dokładnie wtedy, gdy mają te same elementy.
Wreszcie, nieformalna koncepcja dowodu z (1) podlega racjonalizacji ex post jako pewne zestawy (drzewa dowodu).

Należy pamiętać, że pojęcie dowodu jest zatem obywatelem drugiej kategorii w teorii mnogości.

Ta konfiguracja działa dobrze w przypadku konwencjonalnej matematyki małej / średniej, ale ponieważ zajmujemy się teraz dowodami na dużą skalę, takimi jak klasyfikacja wszystkich skończonych prostych grup lub weryfikacja nietrywialnych programów komputerowych, rozpada się, ponieważ nie prowadzi to do łatwej mechanizacji.

$T$ $T$

$\lambda$

— Martin Berger
źródło

To było bardzo przydatne. Myślę, że jednym z głównych problemów każdego, kto zajmuje się konstruktywną matematyką, jest oduczenie się wielu rzeczy.

— dst

Zgadzam się. Odswojenie się od niepotwierdzonych założeń teoretycznych zajmuje trochę czasu. Dużo programowania Agda pomogło mi, a może i dla ciebie pracować, jeśli pochodzisz z informatyki.

— Martin Berger

10

Nie znam łatwych ścieżek do teorii typu Martina-Löfa. Sądzę, że poniższe informacje mogą służyć jako wprowadzenie.

B. Nordström, K. Petersson, JM Smith, Martin-Löf's Theory Theory .
B. Nordström, K. Petersson, JM Smith, Programowanie w teorii typów Martina-Löfa .

Jeśli jednak zastanawia Cię pytanie „co to jest typ”, sugeruję najpierw zająć się znacznie prostszymi teoriami typów. Zda się każdy wpisany język programowania, ale np. Ocaml, F # i Haskell byłyby szczególnie przydatne. Upraszczając nieco, można powiedzieć, że teoria typów Martina-Löfa rozszerza typy wyżej wymienionych języków na dwa sposoby:

Z typami zależnymi . Znajdziesz je w formie pogromcy w różnych językach programowania.
Z typami tożsamości. Jest to główna innowacja Martina-Löfa w stosunku do poprzednich teorii typów zależnych.

Kluczowa idea stojąca za typami zależnymi jest prosta: typy mogą być parametryzowane przez programy. Nie jest to możliwe (nieco upraszczając) w bardziej konwencjonalnych systemach pisania, takich jak te wspomniane powyżej. Choć proste, konsekwencje są głębokie: typy zależne podnoszą zgodność Curry'ego-Howarda z konstruktywną logiką pierwszego rzędu. Rodzaje tożsamości są nieco niezwykłe. Jeśli lubisz język taki jak Haskell, możesz nauczyć się Agdy , czyli Haskell z teorią typów Martina-Löfa. Uważam, że dla programisty Agda jest znacznie łatwiejsza do nauczenia się niż czytanie wyżej wymienionych książek.

— Martin Berger
źródło

Właściwie to znam Haskella. Mój problem polega na tym, że jakikolwiek samouczek po prostu powie ci, jak definiować typy, ale nigdy tym, czym one właściwie nie są. Wydaje się, że jest to jakiś magiczny znacznik dołączony do wszystkich danych, dzięki czemu moduł sprawdzania typu może wybrać odpowiednią wersję funkcji polimorficznej i sprawdzić, czy rzeczy nie są pomieszane w sposób, który nie ma sensu. Nadal pozostawiają otwarte pytanie, co to za typ. Jestem tym szczególnie zaskoczony, ponieważ Voevodsky & co próbuje na tym oprzeć całą matematykę, ale nigdy nie widziałem dokładnej definicji.

— dst

2

Γ ⊢ M : α

$\Gamma \vdash M : \alpha$

M

$M$

α

$\alpha$

M

$M$

M

$M$

Γ

$\Gamma$

Typy są bardzo precyzyjnie zdefiniowane w Haskell, w teorii typów Martina-Löfa oraz w teorii typów homotopii Voevodsky'ego. Nie ma w tym żadnej dwuznaczności. Na przykład załącznik A.2 zawiera system sprawdzający dla wszystkich terminów i typów teorii typów homotopii. Jeśli chcesz jeszcze bardziej rygorystycznego, możesz spojrzeć na formalizacje Coq lub Agda .

— Martin Berger,

2

Być może musisz przełknąć, że typy nie mają innej istoty niż sposób ich zdefiniowania. Nie jest inaczej w przypadku np. Zbiorów, są one podane przez aksjomaty teorii zbiorów. (To nie do końca prawda, ale ważne jest, aby zrozumieć.)

— Martin Berger,