Parametricidade e eliminações projetivas para registros dependentes

É sabido que no Sistema F, você pode codificar produtos binários com o tipo Pode, em seguida, definir projecção funções e .

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

Isso não é tão surpreendente, embora a leitura natural do tipo F seja de um par com uma eliminação no estilo let $\mathsf{let}\;(x,y) = p \;\mathsf{in}\; e$ , porque os dois tipos de pares são interderiváveis na lógica intuicionista.

Agora, em uma teoria de tipos dependentes com quantificação impredicativa, você pode seguir o mesmo padrão para codificar um tipo de registro dependente $\Sigma x:A.\; B[x]$ como

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

$\Sigma x:A.\;B[x] \triangleq \forall\alpha.\; (\Pi x:A.\; B[x] \to \alpha) \to \alpha$ Mas neste caso, não existe uma maneira simples de definir os eliminadores projetivos

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

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

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

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

No entanto, se a teoria dos tipos for paramétrica, você poderá usar a parametridade para mostrar que $\pi_2$ é definível. Isso parece ser conhecido - veja, por exemplo, este desenvolvimento da Agda por Dan Doel, no qual ele deriva sem comentários -, mas não consigo encontrar uma referência para esse fato.

Alguém conhece uma referência pelo fato de a parametridade permitir definir eliminações projetivas para tipos dependentes?

Edição: A coisa mais próxima que eu encontrei até agora é este artigo de Herman Geuvers, de 2001. A indução não é derivável na teoria do tipo dependente de segunda ordem , na qual ele prova que você não pode fazê-lo sem parametridade.

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

Não posso dizer neste post qual é a questão. (Eu não sei nada da área e não saberia de qualquer maneira, mas eu gostaria de ser capaz de articular a questão)

Vijay D

Eu adicionei uma linha de perguntas explícita acima da edição. Isso ajuda?

Neel Krishnaswami

Sim. Inicialmente, eu não tinha certeza se era apenas um pedido de referência ou um pedido de prova. Eu vou perguntar por aí.

Vijay D

Eu tive uma discussão há alguns meses aqui: queuea9.wordpress.com/2012/03/28/why-not-lambda-encode-data e acredito que o princípio da parametridade-> eliminação é folclore / trabalho original de Dan. Essas discussões estão próximas de outras relacionadas à parametridade por J.‑P. Bernardi. Você pode dar uma olhada nos desenvolvimentos da biblioteca padrão da Coq em torno de somas dependentes: coq.inria.fr/stdlib/Coq.Init.Specif.html e talvez coq.inria.fr/stdlib/Coq.Logic.EqdepFacts.html#

Cody

@kvb: Acho que ainda não há uma resposta positiva. No meu rascunho recente (com Derek Dreyer) sobre a parametridade no Cálculo de Construções ( mpi-sws.org/~neelk/internalizing-parametricity.pdf ), mostramos que a parametridade faz parecer interessante para adicionar axiomas que permitem obter fortes eliminações. da codificação da Igreja. No entanto, ainda não temos uma boa história de como internalizar a parametridade de uma maneira que calcule bem (provavelmente precisamos integrar os métodos de JP Bernardy em nossa teoria de tipos). Isso não parece impossível, mas ainda não sabemos como.

Neel Krishnaswami

Parametricidade e eliminações projetivas para registros dependentes

Respostas: