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.
źródło
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ć L i s t 2 ∗ 3 + 4 ( α ) , listy długości 10 , zawierające elementy typu α . Wyrażenie 2 ∗ 3 + 4 jest jednocześnie programem i częścią typu. Nie możesz tego zrobić w STLC.λ List2∗3+4(α) 10 α 2∗3+4
Kluczową zasadą, która odróżnia typy zależne od typów niezależnych, jest zastosowanie:
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 .1N 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.
źródło
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 ().
źródło