Parametrik dan eliminasi proyektif untuk catatan dependen

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$

Ini tidak terlalu mengejutkan, meskipun pembacaan alami dari tipe F adalah pasangan dengan eliminasi gaya , karena dua jenis pasangan dapat ditafsirkan dalam logika intuitionistic. $\mathsf{let}\;(x,y) = p \;\mathsf{in}\; e$

Sekarang, dalam teori tipe dependen dengan kuantifikasi impredikatif, Anda dapat mengikuti pola yang sama untuk menyandikan tipe rekaman dependen $\Sigma x:A.\; B[x]$ sebagai

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

$\Sigma x:A.\;B[x] \triangleq \forall\alpha.\; (\Pi x:A.\; B[x] \to \alpha) \to \alpha$ Tetapi dalam kasus ini, tidak ada cara sederhana untuk mendefinisikan eliminator proyektif

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

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

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

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

Namun, jika teori jenisnya adalah parametrik, Anda bisa menggunakan parametrik untuk menunjukkan bahwa $\pi_2$ dapat didefinisikan. Ini tampaknya diketahui --- lihat, misalnya, pengembangan Agda ini oleh Dan Doel di mana ia memperolehnya tanpa komentar --- tapi sepertinya saya tidak dapat menemukan referensi untuk fakta ini.

Adakah yang tahu referensi untuk fakta bahwa parametricity memungkinkan mendefinisikan eliminasi proyektif untuk tipe dependen?

EDIT: Hal terdekat yang saya temukan sejauh ini adalah makalah tahun 2001 ini oleh Herman Geuvers, Induksi tidak dapat diturunkan dalam teori tipe dependen urutan kedua , di mana ia membuktikan bahwa Anda tidak dapat melakukannya tanpa parametrik.

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

Saya tidak tahu dari pos ini apa pertanyaannya. (Saya tidak tahu apa-apa tentang daerah itu dan tidak akan tahu, tetapi saya ingin dapat mengartikulasikan pertanyaan)

Vijay D

Saya menambahkan baris pertanyaan eksplisit di atas hasil edit. Apakah ini membantu?

Neel Krishnaswami

Iya. Awalnya saya tidak yakin apakah itu hanya permintaan referensi atau permintaan bukti. Saya akan bertanya-tanya.

Vijay D

Saya berdiskusi beberapa bulan yang lalu di sini: queuea9.wordpress.com/2012/03/28/why-not-lambda-encode-data dan saya percaya bahwa prinsip eliminasi parametrik-> adalah cerita rakyat / karya asli dari Dan. Diskusi ini dekat dengan yang lain tentang parametrik oleh J.-P. Bernardi. Anda mungkin ingin melihat perkembangan pustaka standar Coq seputar jumlah dependen: coq.inria.fr/stdlib/Coq.Init.Specif.html dan mungkin coq.inria.fr/stdlib/Coq.Logic.EqdepFacts.html#

cody

@ kvb: Saya kira belum ada jawaban positif. Dalam konsep saya baru-baru ini (dengan Derek Dreyer) tentang parametrikitas dalam Calculus of Constructions ( mpi-sws.org/~neelk/internalizing-parametricity.pdf ), kami menunjukkan bahwa parametrikitas membuatnya terdengar untuk menambahkan aksioma yang memungkinkan Anda mengeluarkan elim yang kuat. pengkodean Gereja. Namun, kami belum memiliki cerita yang bagus tentang cara menginternalisasi parametrik dengan cara yang menghitung dengan baik (kemungkinan besar kita perlu mengintegrasikan metode JP Bernardy ke dalam teori tipe kita). Ini sepertinya tidak mungkin, tetapi kita belum tahu bagaimana.

Neel Krishnaswami

Parametrik dan eliminasi proyektif untuk catatan dependen

Jawaban: