Jakiej najbardziej intuicyjnej teorii typów zależnych mógłbym się nauczyć?

46

Jestem zainteresowany uzyskaniem naprawdę solidnego zrozumienia zależnego pisania. Przeczytałem większość TaPL i przeczytałem (jeśli nie w pełni zaabsorbowane) „Typy zależne” w ATTaPL . Przeczytałem również i przejrzałem kilka artykułów na temat pisania zależnego.

Wiele dyskusji na temat teorii typów wydaje się koncentrować na dodawaniu funkcji przyrostowych do poprzednich systemów typów, a nie „jakie jest następne duże uogólnienie od systemu typów X?”. Typy zależne wydają się być kolejnym dużym uogólnieniem z Systemu F, ale nie znalazłem jeszcze intuicyjnego, kanonicznego języka zależnego. Wiele odniesień do rachunku (indukcyjnych) konstrukcji powoduje, że myślę, że CoC jest tym językiem, ale wyjaśnienia języka, który widziałem, nie wydają mi się zbyt jasne ani intuicyjne.

Spodziewam się / zgaduję, że taki język miałby takie cechy jak: (i daj mi znać, jeśli coś konkretnego wyskoczy jako zdezorientowane lub nierealne)

  • Uogólniona abstrakcja (może mieć funkcje z dowolnej domeny w hierarchii typów na inne, rodzaj -> termin, termin-> typ '' itp.)
  • Ma nieskończoną hierarchię pisania (terminy: typy: typy ': typy' ': ...)
  • Minimalna liczba podstawowych elementów. Wyobrażam sobie, że język zapewnia tylko jeden element dla każdego poziomu. Na przykład może twierdzić, że ((): Unit: Type: Type ': ...). Inne elementy są zbudowane z tych elementów.
  • Suma i typy produktów są pochodnymi.

Szukam również wyjaśnienia tego języka, który najlepiej omawia:

  • Związek między abstrakcją a kwantyfikacją w tym języku. Jeśli nie są zjednoczone, wyjaśnij, dlaczego nie są zjednoczone.
  • Hierarchia typów nieskończonych jawnie

Zadaję to pytanie, ponieważ chcę nauczyć się teorii typów zależnych, ale także dlatego, że chcę przygotować przewodnik, który przy założeniu, że ma małe doświadczenie w CS, uczy obsługi i sposobu rozumienia asystentów dowodzenia oraz języków zależnie wpisywanych.

(Krzyż wysłany do Reddit)

John Salvatier
źródło

Odpowiedzi:

35

Istnieje kilka różnych sposobów podejścia do tego:

  1. Teoria typów zależnych . Nie jest to prawdopodobnie najłatwiejszy sposób uczenia się o typach zależnych, ale można na przykład spojrzeć na dokumenty Calculus of Constructions i ich warianty, Pure Type Systems oraz artykuł Martina Hofmanna na temat składni i semantyki typów zależnych.

  2. Dowodzenie twierdzeń . Po pierwsze, spójrz na moją odpowiedź na powiązane pytanie: Jak mógłbym zacząć uczyć się podstawowej teorii asystenta dowodu Coq? .

  3. ΠΣ, pośród innych. I oczywiście jest książka Adama Chlipali, podana w odpowiedzi Marca Hamanna.

Byłbym skłonny zacząć od programowania, zanim przejdę do użycia dowodzenia twierdzeń, a następnie zacznę zgłębiać bardziej teoretyczne problemy.

Dave Clarke
źródło
Mogę znaleźć dokumenty do Epigram, ale nie mogę znaleźć faktycznego pobrania dla Epigram, tylko niedokończony Epigram 2. Jakieś pomysły?
John Salvatier
1
Czy znalazłeś: e-pig.org/darcs/Pig09/web ? Epigram jest dostępny na dole strony.
Dave Clarke
3
Epigram 1 jest zasadniczo nieobsługiwany od dłuższego czasu AFAIK - autor obecnie używa Agdy (pracując nad Epigramem 2 na boku).
Blaisorblade
W 2019 roku nie sądzę, aby Epigram 2 kiedykolwiek miał miejsce - ale teraz jest Idris (i Idris 2!).
xrq
14

λπ

Twelf to dobry system dowodzenia twierdzeń oparty na LF. Przegląd zaawansowanych notatek kursowych oferowanych przez Franka Pfenninga stanowi dobre wprowadzenie do teorii i praktyki LF.

To powiedziawszy, być może nie jest to najlepszy pierwszy system, aby dowiedzieć się, czy interesuje Cię matematyka konstruktywna, a nie podstawy teorii typów: LF oznacza ramy logiczne i jest systemem służącym do aksjatyzacji teorii i nie jest tak często stosowany system docelowy bezpośrednio. Korzystanie z systemu opartego na teorii typów Martina-Loefa jest prawdopodobnie najlepszym wprowadzeniem - między innymi Dave wspomina o Agdzie - jest być może lepszym punktem wyjścia, jeśli jest to twój cel, ponieważ w takim przypadku możesz szybciej zacząć z typami arytmetycznymi i indukcyjnymi struktura.

Charles Stewart
źródło
10

CoC jest najprawdopodobniej właściwą drogą. Po prostu zanurz się w Coq i przeprowadź fajny samouczek, taki jak Software Foundations (w który zaangażowany jest Pierce z TaPL i ATTaPL).

Po zapoznaniu się z praktycznymi aspektami pisania zależnego powróć do źródeł teoretycznych: będą one miały o wiele więcej sensu.

Twoja lista funkcji brzmi właściwie poprawnie, ale sprawdzenie, jak działają w praktyce, jest warte tysiąca punktów funkcji.

(Kolejnym, nieco bardziej zaawansowanym samouczkiem jest Certyfikowane programowanie Adama Chlipali z typami zależnymi )

Marc Hamann
źródło
„intuicyjny” jest być może kwestią kluczową: w CoC / CIC latają o wiele więcej intuicji niż tylko pisanie zależne. To dobry cel końcowy - moim zdaniem wybór jest naprawdę pomiędzy Coq i Twelfem - ale może nie jest to najlepszy pierwszy krok w kierunku „uzyskania naprawdę solidnego zrozumienia zależnego pisania”.
Charles Stewart,
@Charles: Twój punkt jest zajęty. Nadal uważam, że z praktycznego punktu widzenia jest to dobry zakład. Chociaż pełne zrozumienie CoC / CIC może być bardziej złożonym przedsięwzięciem, Coq (plus istnienie dobrych samouczków na poziomie podstawowym) ułatwia skoncentrowanie się na nauce tylko aspektów programowania lub podstawowych aspektów asystenta dowodu (jako twoje zainteresowania dyktują) nawet zanim zrozumiesz wszystkie zawiłości. Myślę, że to kwalifikuje się jako „intuicyjne” dla kogoś, kto nie pochodzi z podstaw teoretycznych.
Marc Hamann,