Geben abhängige Typen Ihnen alles, was Subtyping macht?

24

Typen und Programmiersprachen konzentrieren sich ziemlich stark auf Subtypisierung, aber soweit ich das beurteilen kann, scheint die Subtypisierung nicht besonders grundlegend zu sein. Gibt es bei der Subtypisierung mehr als bei abhängigen Typen? Das Arbeiten mit abhängigen Typen ist sicherlich aufwändiger, sodass ich verstehen kann, warum Untertypen in der Praxis nützlich sein können. Ich interessiere mich jedoch mehr für die Typentheorie als Grundlage für Mathematik als für die Grundlage für Programmiersprachen. Sollte ich der Untertypisierung viel Aufmerksamkeit schenken?

John Salvatier
quelle

Antworten:

22

Subtypisierung und abhängige Typen sind orthogonale Konzepte.

Die Untertypisierung ist in der Regel mit einem Subsumtionsbegriff ausgestattet, bei dem ein Ausdruck eines Typs an der Stelle erscheinen kann, an der ein Supertyp erwartet wird.

Subtypisierung ist mit größerer Wahrscheinlichkeit entscheidbar und in der Implementierung einfacher zu handhaben.

Abhängiges Tippen ist weitaus aussagekräftiger. Aber wenn Sie eine Gruppe jemals als Monoid betrachten wollen, dann brauchen Sie einen Subsumtionsbegriff, um die zusätzliche Struktur zu vergessen. Oft wird, wie bei der Verwendung von Coq, eine triviale Beweispflicht für die Bewältigung dieser Art von Zwang generiert, sodass in der Praxis durch die Subtypisierung möglicherweise nichts hinzugefügt wird. Was wichtiger ist, ist die Möglichkeit, verschiedene Theorien so zusammenzufassen, dass sie wiederverwendbar sind, z. B. die Wiederverwendung der Theorie der Monoide, wenn über Gruppen gesprochen wird. Typenklassen in Coq sind eine neue Innovation, um solche Dinge zu tun. Module sind ein älterer Ansatz.

Wenn Sie einen kurzen Blick auf "Subtypisierung abhängiger Typen" werfen, finden Sie eine Menge Arbeit, die abhängigen Typen Subtypisierung hinzufügt, hauptsächlich aus der Zeit um das Jahr 2000. Ich stelle mir vor, dass die Metatheorie wirklich herausfordernd ist, sodass in keine Subtypisierung abhängiger Typen vorkommt Beweisassistenten.

Dave Clarke
quelle
3
Danke, genau das habe ich gesucht. Ich habe jetzt ein paar Noob-Fragen gestellt, die anscheinend einigermaßen gut aufgenommen wurden, obwohl cstheory.SE nicht der richtige Ort für solche Fragen ist. Würden Sie in Zukunft ähnliche Fragen auf einer Skala von -5 bis +5 anregen oder entmutigen? Als Randnotiz, so wie ich es verstehe (nach dem Lesen von Robert Harper), sind Typklassen eine Unterkategorie von Modulen, oder?
John Salvatier
3
Diese Frage befindet sich genau rechts am Rand dessen, was für cstheory.SE geeignet ist. Typklassen sind eigentlich keine Unterkategorie von Modulen. Es ist eher so, als wären Typklassen Module + Typinferenz + free_plumbing.
Dave Clarke
2
Ich würde mir vorstellen, dass Sie Subtying mit abhängigen Typen immer ziemlich einfach modellieren / simulieren können. In Haskell gibt Ihnen HList (das nur auf entscheidbarer Typgleichheit basiert) beispielsweise Untertypen (siehe "Haskells System für übersehene Objekte"). Der einzige schwierige Teil beim Untertiteln ist die Typinferenz, und wenn Sie mit abhängigen Typen arbeiten, haben Sie sowieso 90% davon weggeworfen.
sclv
(geändert von einem Kommentar zu einer Antwort)
Neel Krishnaswami
Die Untergruppentheorie der Martin-Loef-Typentheorie ist im Grunde das, was Sie brauchen, um das Strukturvergessen zu modellieren. Sie stammt aus den 1980er Jahren. Ich denke, das ist eine Art, worauf @Neel in seiner Antwort kommt.
Charles Stewart
22

Ich interessiere mich jedoch mehr für die Typentheorie als Grundlage für Mathematik als für die Grundlage für Programmiersprachen. Sollte ich der Untertypisierung viel Aufmerksamkeit schenken?

Eine zusätzliche Sache, die Subtypisierung gibt, ist, dass Subsumtion impliziert, dass viele Kohärenzeigenschaften gelten. Eine abhängige Typentheorie benötigt auch den Begriff der Beweisrelevanz, um alles zu modellieren, was Sie mit Subtypen tun können. In der Theorie abhängiger Typen können Sie beispielsweise eine Teilmenge mit einem abhängigen Datensatz approximieren:

{xS|;P(x)} gegen Σx:S.P(x)

SP(x)x:

X<:Y.x:Xx:Y.P(x)P(x)

Sobald Sie das haben, können Sie systematisch die Untertypisierung in die Theorie der abhängigen Typen ausarbeiten. Sehen These von William Lovas finden Sie ein Beispiel für das Hinzufügen von Untertypen zu einer Theorie abhängiger Typen (in diesem Fall Twelf).

Neel Krishnaswami
quelle