Co zyskujemy, mając „typy zależne”?

Myślałem, że dobrze rozumiem pisanie zależne (DT), ale odpowiedź na to pytanie: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% Teoria typu B6f do tworzenia-intuicyjnego typu kazała mi myśleć inaczej.

Po przeczytaniu DT i próbie zrozumienia, czym one są, zastanawiam się, co zyskujemy dzięki temu pojęciu DT? Wydają się być bardziej elastyczne i wydajne niż zwykły rachunek lambda (STLC), chociaż nie mogę dokładnie zrozumieć „jak / dlaczego”.

Co możemy zrobić z ID, czego nie można zrobić z STLC? Wydaje się, że dodanie ID komplikuje teorię, ale jaka jest z tego korzyść?

Od odpowiedzi na powyższe pytanie:

Typy zależne zostały zaproponowane przez de Bruijna i Howarda, którzy chcieli rozszerzyć korespondencję Curry-Howarda z propozycji na logikę pierwszego rzędu.

To wydaje się mieć sens na pewnym poziomie, ale wciąż nie jestem w stanie zrozumieć dużego obrazu „jak / dlaczego”? Być może przykład wyraźnie pokazuje, że to rozszerzenie korespondencji CH do logiki FO może pomóc w osiągnięciu celu w zrozumieniu, o co chodzi z ID? Nie jestem pewien, czy też to rozumiem.

logic type-theory intuition

— Doktorat
źródło

Czy przeglądałeś je? Czy słyszałeś o Coq, twierdzeniu opartym na typach zależnych? Czy wiesz, że twierdzenie o 4 kolorach udowodniło użycie Coq?

— Dave Clarke

Faktycznie zrobiłem. Co jest trudne dla Google, czym jest ta dodatkowa „moc” (z braku lepszego słowa), którą DT nadają typowi teorii, mówiąc intuicyjnie?

— Dr

Dlaczego? Zależne typy pozwalają pisać więcej programów, zachowując jednocześnie bezpieczeństwo typów. W jaki sposób? Poprzez parametryzację typów za pomocą programów.

— Martin Berger,

@MartinBerger - Czy możesz opracować „więcej programów”? Co „więcej” mogę zrobić lub potrzebować z teoretycznego punktu widzenia?

— Dr

@DaveClarke That Coq, ze swoimi fantazyjnymi typami, był używany do robienia fantazyjnych rzeczy, nie oznacza to, że te fantazyjne rzeczy wymagają tych fantazyjnych typów. Na przykład Twelf odniósł duże sukcesy (takie jak dowód poprawności SML) i jest to tylko drugi rząd, a nie wyższy. Widziałem kilka całkiem dużych systemów sprawdzonych tylko z logiką pierwszego rzędu.

— Gilles „SO- przestań być zły”

Odpowiedzi:

Rozszerzanie mojego komentarza: typy zależne mogą pisać więcej programów. „Więcej” oznacza po prostu, że zestaw programów, które można pisać za pomocą typów zależnych, jest właściwym nadzbiorem programów, które można pisać za pomocą prostego kalkulatora (STLC). Przykładem może być , listy długości , zawierające elementy typu . Wyrażenie jest jednocześnie programem i częścią typu. Nie możesz tego zrobić w STLC. $\lambda$ $List_{2*3+4}(\alpha)$ $10$ $\alpha$ $2*3+4$

Kluczową zasadą, która odróżnia typy zależne od typów niezależnych, jest zastosowanie:

\frac{Γ ⊢ M : A \to B Γ ⊢ N : A}{Γ ⊢ M N : B} \frac{Γ ⊢ M : Π x^{A} . B Γ ⊢ N : A}{Γ ⊢ M N : B {N / x}}

$\newcommand{\TYPES}[3]{#1 \vdash #2 : #3} \newcommand{\SUBST}[2]{\{#1/#2\}} \frac{ \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{\color{red}{MN}}{B} } \qquad \frac{ \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}} }$

Po lewej stronie znajduje się STLC, w którym programy w lokalu „przepływają” tylko do programu zakończenia. W przeciwieństwie do reguły zależnej aplikacji po prawej, program z właściwej przesłanki „wpada” do typu we wniosku . $N$ $^1$

Aby móc parametryzować typy według programów, składnia typów zależnych musi być bogatsza, a dla zapewnienia, że typy są dobrze uformowane, używamy drugiego „systemu typowania” zwanego rodzajami, który ogranicza typy. Ten system sortowania to zasadniczo STLC, ale „jeden poziom wyżej”.

Istnieje wiele wyjaśnień typów zależnych. Kilka przykładów.

Zależne typy w pracy , autor: Bove i Dybjer.
Typy zależne, autorstwa Aspinall i Hofmann.
Programowanie zależne w Agdzie , autorstwa Norella i Chapmana.
Lambda Calculi with Types , autor: Barendregt.

$^1$ ^{Pod względem kolorów: w przypadku typów niezależnych, czarne wyrażenia w konkluzji są konstruowane z czarnych wyrażeń w lokalu, podczas gdy czerwone wyrażenia w konkluzji są konstruowane z czerwonych wyrażeń w lokalu. W przypadku typów zależnych kolory można mieszać, tworząc czarne części wniosku zbudowane z czerwonej i czarnej części lokalu.}

— Martin Berger
źródło

To ma wiele sensu. Być może było to oczywiste, ale z jakiegoś powodu nie mogłem położyć na tym palca. Doceń przejście od komentarza do odpowiedzi. Niestety pytanie zostało głosowane za zamknięciem, ale cieszę się z odpowiedzi :)

— dr

Nie szaleję za twoim przykładem, ponieważ długość listy jest po prostu czymś, co można usunąć w typach i sprawić, że programy mówią o zwykłych (nieindeksowanych) listach. Warto zauważyć, że istnieją typy, które po takim skasowaniu nie są dobrze wpisane, np. Program typu , gdzie i .

A r r n

$\mathrm{Arr}\ n$

A r r 0 = n a t

$\mathrm{Arr}\ 0 = \mathrm{nat}$

A r r (n + 1) = n a t \to A r r n

$\mathrm{Arr}\ (n+1) = \mathrm{nat}\rightarrow\mathrm{Arr}\ n$

— cody

@cody Nie jestem pewien, co masz na myśli. Typy zależne mają (lub można je ustawić tak, aby były) usuwanie typu w następującym znaczeniu: dla wszystkich P: iff , gdzie to relacja redukcji czasu pracy . (Jest to uproszczony opis, w którym funkcja wymazywania mapuje programy z adnotacją typu do „tych samych” programów bez adnotacji.) Może masz na myśli coś innego?

P ⇓ V

$P\Downarrow V$

e r a s e (P) ⇓ e r a s e (V)

$erase(P)\Downarrow erase(V)$

⇓

$\Downarrow$

— Martin Berger

@MartinBerger: tak w tym przypadku mówię o usuwaniu zależności w typach zależnych, aby uzyskać proste typy. Jedynym przykładem, na który mogę teraz wskazać, jest dowód, że normalizuje iff normalizuje (np. W książce Barendregta ).

F_{ω}

$F_\omega$

C o C

$\mathrm{CoC}$

— cody

@cody Myślę, że nazywanie tego typu wymazaniem jest niezwykłe. Jakie jest lepsze imię? Może wpisz uproszczenie?

— Martin Berger

Pomyśl o deklaracjach typu jako o niczym więcej niż twierdzeniach. Obecnie wszystko, co możesz powiedzieć, to rzeczy takie jak isInt32 (), isCharPtr () itp. Te różne twierdzenia są wybierane do sprawdzenia w czasie kompilacji. Ale tę koncepcję można rozszerzyć na rzeczy takie jak: isCharPtr () i& isNotNull (). Wskaźniki zerowalne są ogromnym problemem. Wskaźniki nie powinny być zerowalne jako postawa domyślna, a zerowalne wskaźniki są typem, który nie jest dereferencyjny bez wiedzy, czy jest zerowy, czy nie. Podobne problemy to: isPositiveInteger () lub isEvenNaturalNumber ().

— Obrabować
źródło