Wo wird die relationale Parametrizität in Hyperdoktrin- oder Topos-Modellen untersucht?

Reynolds schlug ursprünglich eine relationale Semantik für den polymorphen Lambda-Kalkül zweiter Ordnung vor [1]. Später zeigte er jedoch [2], dass dieser Ansatz nicht mit der klassischen Mengenlehre vereinbar war. Pitts beschrieb den Rahmen von Hyperdoktrinmodellen und Topos-Modellen [3], die mit der konstruktiven Logik übereinstimmen.

Anschließend wurden vermutlich relationale Hyperdoktrin- und Topos-Modelle entwickelt. Wo kann ich darüber lesen?

• [1] Typen, Abstraktion und parametrischer Polymorphismus
• [2] Polymorphismus ist nicht satztheoretisch
• [3] Polymorphismus wird konstruktiv theoretisch festgelegt

• Aus technischen Gründen wurde nicht viel an parametrischen Topos-Modellen gearbeitet. Die interne Logik eines Topos ist eine Form der Mengenlehre, und die impredikative Indizierung im F-Stil und das Powerset-Axiom sind nicht kompatibel. Siehe Andy Pitts ' nicht triviale Krafttypen können keine Subtypen polymorpher Typen sein :

  Diese Arbeit stellt eine neue, begrenzende Beziehung zwischen dem polymorphen Lambda-Kalkül und der Art der Typentheorie höherer Ordnung her, die in der Logik der Toposen enthalten ist. Es wird gezeigt, dass jede Einbettung in ein Topos der kartesischen geschlossenen Kategorie von (geschlossenen) Typen eines Modells des polymorphen Lambda-Kalküls die polymorphen Typen in dem Sinne weit von den Powertypen P (X) der Topos entfernt platzieren muss dass P (X) nur dann ein Subtyp eines polymorphen Typs ist, wenn X leer ist (und daher P (X) terminal ist). Als Folgerungen erhalten wir Verstärkungen von Reynolds 'Ergebnis über das Nichtvorhandensein satztheoretischer Modelle des Polymorphismus.

  Obwohl Sie einem Universum die Möglichkeit geben können, Fs Typen in der Topos-Logik zu interpretieren, können Sie es daher nicht auf interessante Weise mit dem gesamten Universum von Mengen interagieren lassen. Es ist jedoch nicht alles verloren!

  1. $F_\omega$

  2. Eine andere Reaktion auf Pitts 'Ergebnis besteht darin, nicht mit einer Mengenlehre, sondern mit einer abhängigen Typentheorie zu arbeiten. Da es in der Theorie der abhängigen Typen keinen früheren Leistungstyp gibt, müssen Sie sich keine Gedanken über das Zusammenspiel von Leistungstypen und Polymorphismus machen. Siehe Atkey, Ghani und Johanns Ein relational parametrisches Modell der abhängigen Typentheorie .

• Es gibt jedoch keine derartigen Hindernisse für die Erstellung hyperdoktriner Modelle, bei denen Begriffe von System F Objekte der Logik sind. Forschungen in dieser Richtung wurden wahrscheinlich von Abadi und Plotkin in ihrer wegweisenden Arbeit A Logic for Parametric Polymorphism initiiert . Lars Birkedal und seine Mitarbeiter haben intensiv an der Formulierung kategorialer Modelle für diese und ähnliche Logiken gearbeitet - siehe insbesondere Birkedal, Møgelberg und Petersens kategorietheoretische Modelle der linearen Abadi und Plotkin-Logik , die eine Logik für die Argumentation über das lineare System F liefern sowie einen Beweis dafür, dass es in Bezug auf eine bestimmte Klasse von kategorialen Modellen solide und vollständig ist.