Czy typy zależne dają ci wszystko, co robi podtyp?

Typy i języki programowania skupiają się dość mocno na subtypowaniu, ale o ile wiem, subtyping nie wydaje się szczególnie fundamentalny. Czy podtypowanie daje coś więcej niż typy zależne? Praca z typami zależnymi z pewnością będzie wymagała więcej pracy, więc rozumiem, dlaczego podtypy mogą być przydatne w praktyce. Jednak bardziej interesuje mnie teoria typów jako podstawa matematyki niż podstawa języków programowania, czy powinienem zwracać dużą uwagę na subtyfikację?

lo.logic pl.programming-languages type-theory

— John Salvatier
źródło

Odpowiedzi:

Podtypy i typy zależne są pojęciami ortogonalnymi.

Podtypowanie jest zazwyczaj wyposażone w pojęcie subsumcji, przy czym wyrażenie jednego typu może pojawić się w miejscu, w którym oczekiwany jest nadtyp.

Podpisywanie jest bardziej podatne na rozstrzygnięcie i jest łatwiejsze do zarządzania w trakcie wdrażania.

Zależne pisanie jest znacznie bardziej wyraziste. Ale jeśli kiedykolwiek zechcesz uznać grupę za monoidę, potrzebujesz pojęcia subsumpcji, aby zapomnieć o dodatkowej strukturze. Często, na przykład podczas korzystania z Coq, generowany jest trywialny obowiązek dowodu, aby poradzić sobie z tego rodzaju przymusem, więc w praktyce podtypowanie może niczego nie dodawać. Co ważniejsze, to sposoby pakowania różnych teorii, aby można je było ponownie wykorzystać, na przykład ponowne wykorzystanie teorii monoidów w rozmowach o grupach. Klasy typów w Coq to najnowsza innowacja do robienia takich rzeczy. Moduły są starszym podejściem.

Jeśli zrobisz szybkie wyszukiwanie w Google „podtypów zależnych”, znajdziesz mnóstwo pracy nad dodaniem podtypów do typów zależnych, głównie z około 2000 roku. Wyobrażam sobie, że meta-teoria jest naprawdę trudna, więc żadne podtypowanie typów zależnych nie pojawia się w asystenci dowodu.

— Dave Clarke
źródło

Dziękuję, właśnie tego szukałem. Zadałem teraz kilka pytań noob, które wydają się być dość dobrze przyjęte, mimo że cstheory.SE nie jest właściwym miejscem na takie pytania. Czy w skali od -5 do +5 zachęciłbyś lub zniechęciłbyś podobne pytania w przyszłości? Na marginesie, jak rozumiem (z czytania Roberta Harpera), klasy typów są podkategorią modułów, prawda?

— John Salvatier,

To pytanie znajduje się po prawej stronie granicy tego, co jest odpowiednie dla cstheory.SE. Klasy typów nie są tak naprawdę podkategorią modułów. Bardziej przypomina to, że klasy typów to moduły + wnioskowanie o typie + bezpłatna instalacja hydrauliczna.

— Dave Clarke

Wyobrażam sobie, że zawsze można dość łatwo modelować / symulować podtytuły z typami zależnymi. W Haskell, HList (która jest właśnie zbudowana na rozstrzygającej równości typów) daje ci podtypy, na przykład (por. „Overlooked Object System Haskella”). Jedyną trudną częścią subtyfikacji jest wnioskowanie o typach, a kiedy pracujesz z typami zależnymi, i tak rzuciłeś 90% tego.

— sclv

(zmieniono z komentarza na odpowiedź)

— Neel Krishnaswami

Teoria podzbiorów teorii typów Martina-Loefa jest w zasadzie tym, czego potrzebujesz do modelowania zapominania o strukturze, a pochodzi ona z lat 80. Myślę, że na tym właśnie polega @Neel w swojej odpowiedzi.

— Charles Stewart

Jednak bardziej interesuje mnie teoria typów jako podstawa matematyki niż podstawa języków programowania, czy powinienem zwracać uwagę na subtyfikację?

Jedną dodatkową rzeczą, jaką daje podtyp, jest to, że subsumcja oznacza, że zachowuje wiele właściwości koherencji. Teoria typów zależnych wymaga również pojęcia nieistotności dowodu do modelowania wszystkiego, co można zrobić z podtypami. Na przykład w teorii typów zależnych można w przybliżeniu utworzyć podzbiór z rekordem zależnym:

{x \in S. |; P. (x)} vs. Σ x : S. . P. (x)

$\{x \in S \;|; P(x)\} \mbox{ vs. } \Sigma x:S.\;P(x)$

$S$ $P(x)$ $x:$

$X <: Y$ $x:X$ $x:Y$ $P(x)$ $P(x)$

Gdy już to zrobisz, możesz systematycznie opracowywać podtypy w teorii typów zależnych. Zobacz tezę Williama Lovasa , aby zobaczyć przykład dodawania podtypów do teorii typów zależnych (w tym przypadku Twelfa).

— Neel Krishnaswami
źródło