Parametrizität und projektive Eliminierungen für abhängige Datensätze

A \times B ≜ \forall α . (A \to B \to α) \to α

$A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha$

π_{1} : A \times B \to A

$\pi_1 : A \times B \to A$

π_{2} : A \times B \to B

$\pi_2 : A \times B \to B$

Dies ist nicht so überraschend, obwohl die natürliche Lesart des F-Typs ein Paar mit einer Eliminierung im Let-Stil ist. , weil die beiden Arten von Paaren in der intuitionistischen Logik interderierbar sind. $\mathsf{let}\;(x,y) = p \;\mathsf{in}\; e$

Nun können Sie in einer Theorie abhängiger Typen mit improvisierter Quantifizierung dem gleichen Muster folgen, um einen abhängigen Datensatztyp zu codieren als Aber in diesem Fall gibt es keinen einfachen Weg, um die projektiven Eliminatoren zu definieren und . $\Sigma x:A.\; B[x]$

Σ x : EIN . B [x] ≜ \forall α . (Π x : EIN . B [x] \to α) \to α

$\Sigma x:A.\;B[x] \triangleq \forall\alpha.\; (\Pi x:A.\; B[x] \to \alpha) \to \alpha$

π_{1} : Σ x : A . B [x] \to A

$\pi_1 : \Sigma x:A.\;B[x] \to A$

π_{2} : Π p : (Σ x : A . B [x]) . B [π_{1} p]

$\pi_2 : \Pi p:(\Sigma x:A.\;B[x]).\; B[\pi_1\,p]$

Wenn die Typentheorie jedoch parametrisch ist, können Sie die Parametrizität verwenden, um zu zeigen, dass $\pi_2$ definierbar ist. Dies scheint bekannt zu sein - siehe zum Beispiel diese Agda-Entwicklung von Dan Doel, in der er sie kommentarlos herleitet -, aber ich kann keinen Hinweis auf diese Tatsache finden.

Kennt jemand eine Referenz für die Tatsache, dass die Parametrizität die Definition projektiver Eliminierungen für abhängige Typen ermöglicht?

EDIT: Das Naheliegendste, was ich bisher gefunden habe, ist der Artikel von Herman Geuvers aus dem Jahr 2001. Induktion ist in der Theorie des abhängigen Typs zweiter Ordnung nicht ableitbar , in der er beweist, dass man es nicht ohne Parametrizität schaffen kann.

reference-request pl.programming-languages dependent-type parametricity Neel Krishnaswami
quelle

Ich kann in diesem Beitrag nicht sagen, was die Frage ist. (Ich weiß nichts von der Gegend und würde es sowieso nicht wissen, aber ich möchte in der Lage sein, die Frage zu artikulieren)

Vijay D

Ich habe eine explizite Fragezeile über der Bearbeitung hinzugefügt. Hilft das?

Neel Krishnaswami

Ja. Ich war mir anfangs einfach nicht sicher, ob es sich nur um eine Referenzanfrage oder eine Beweisanfrage handelte. Ich werde herumfragen.

Vijay D

Ich hatte vor ein paar Monaten eine Diskussion hier: queuea9.wordpress.com/2012/03/28/why-not-lambda-encode-data und ich glaube, dass das Parametricity-> Elimination-Prinzip Folklore / Originalarbeit von Dan ist. Diese Diskussionen sind in Bezug auf die Parametrizität von J.-P. Bernardi. Vielleicht möchten Sie einen Blick auf die Entwicklungen der Coq-Standardbibliothek in Bezug auf abhängige Summen werfen : coq.inria.fr/stdlib/Coq.Init.Specif.html und möglicherweise coq.inria.fr/stdlib/Coq.Logic.EqdepFacts.html#

Cody

@kvb: Ich denke, es gibt noch keine positive Antwort. In meinem letzten Entwurf (mit Derek Dreyer) auf Parametrizität in der Calculus of Constructions ( mpi-sws.org/~neelk/internalizing-parametricity.pdf ) zeigen wir , dass Parametrizität macht es klingen Axiome hinzuzufügen , die Sie stark eLIMS erhalten rauslassen der kirchlichen Kodierung. Wir haben jedoch noch keine gute Geschichte, wie man Parametrizität auf eine Art und Weise internalisiert, die gut berechnet werden kann (höchstwahrscheinlich müssen wir die Methoden von JP Bernardy in unsere Typentheorie integrieren). Dies scheint nicht unmöglich, aber wir wissen noch nicht wie.

Neel Krishnaswami

Parametrizität und projektive Eliminierungen für abhängige Datensätze

Antworten: