Paramétricité et éliminations projectives pour les enregistrements dépendants

Il est bien connu que dans le système F, vous pouvez coder des produits binaires avec le type Vous pouvez alors définir des fonctions de projection et .

UNE \times B ≜ \forall α . (UNE \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$

Ce n'est pas si surprenant, même si la lecture naturelle du type F est d'une paire avec une élimination de style let $\mathsf{let}\;(x,y) = p \;\mathsf{in}\; e$ , parce que les deux types de paires sont interconnectables dans la logique intuitionniste.

Maintenant, dans une théorie de type dépendante avec une quantification imprédicative, vous pouvez suivre le même modèle pour coder un type d'enregistrement dépendant $\Sigma x:A.\; B[x]$ as

Σ X : UNE . B [X] ≜ \forall α . (Π X : UNE . B [X] \to α) \to α

$\Sigma x:A.\;B[x] \triangleq \forall\alpha.\; (\Pi x:A.\; B[x] \to \alpha) \to \alpha$ Mais dans ce cas, il n'y a pas de moyen simple de définir les éliminateurs projectifs

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

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

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

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

Cependant, si la théorie des types est paramétrique, vous pouvez utiliser la paramétrie pour montrer que $\pi_2$ est définissable. Cela semble être connu --- voir, par exemple, ce développement Agda par Dan Doel dans lequel il le dérive sans commentaire --- mais je n'arrive pas à trouver une référence pour ce fait.

Quelqu'un connaît-il une référence au fait que la paramétricité permet de définir des éliminations projectives pour les types dépendants?

EDIT: La chose la plus proche que j'ai trouvée jusqu'à présent est cet article de 2001 de Herman Geuvers, Induction n'est pas dérivable dans la théorie des types dépendants du second ordre , dans laquelle il prouve que vous ne pouvez pas le faire sans paramétrie.

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

Je ne peux pas dire à partir de ce post quelle est la question. (Je ne connais rien de la région et je ne le saurais pas de toute façon, mais j'aimerais pouvoir articuler la question)

Vijay D

J'ai ajouté une ligne de question explicite au-dessus de la modification. est-ce que cela aide?

Neel Krishnaswami

Oui. Je n'étais tout simplement pas sûr au départ s'il s'agissait uniquement d'une demande de référence ou d'une demande de preuve. Je vais demander autour.

Vijay D

J'ai eu une discussion il y a quelques mois ici: queuea9.wordpress.com/2012/03/28/why-not-lambda-encode-data et je crois que le principe d'élimination de la paramétricité-> est le folklore / œuvre originale de Dan. Ces discussions sont proches de celles concernant la paramétricité par J.-P. Bernardi. Vous voudrez peut-être jeter un œil aux développements de la bibliothèque standard Coq autour des sommes dépendantes: coq.inria.fr/stdlib/Coq.Init.Specif.html et peut-être coq.inria.fr/stdlib/Coq.Logic.EqdepFacts.html#

cody

@kvb: Je ne pense pas qu'il y ait encore de réponse positive. Dans mon récent projet (avec Derek Dreyer) sur paramétricité dans le calcul des constructions ( mpi-sws.org/~neelk/internalizing-parametricity.pdf ), nous montrons que paramétricité rend le son d'ajouter axiomes qui vous permettent d' obtenir elims fortes sur de l'encodage de l'Église. Cependant, nous n'avons pas encore une bonne histoire sur la façon d'intérioriser la paramétricité d'une manière qui calcule bien (nous avons probablement besoin d'intégrer les méthodes de JP Bernardy dans notre théorie des types). Cela ne semble pas impossible, mais nous ne savons pas encore comment.

Neel Krishnaswami

Paramétricité et éliminations projectives pour les enregistrements dépendants

Réponses: