Apakah tipe dependen memberi Anda segala yang subtyping lakukan?

Jenis dan Pemrograman Bahasa berfokus sedikit pada subtyping, tetapi sejauh yang saya tahu, subtyping tampaknya tidak terlalu mendasar. Apakah subtyping memberi Anda lebih dari sekadar tipe dependen? Bekerja dengan tipe dependen pasti lebih banyak pekerjaan, jadi saya bisa mengerti mengapa subtipe mungkin berguna dalam praktik. Namun, saya lebih tertarik pada teori tipe sebagai dasar untuk matematika daripada sebagai dasar untuk bahasa pemrograman, haruskah saya memperhatikan subtyping?

lo.logic pl.programming-languages type-theory John Salvatier
sumber

Jawaban:

Tipe subtipe dan dependen adalah konsep ortogonal.

Subtyping biasanya dilengkapi dengan gagasan subsumption, di mana ekspresi satu jenis dapat muncul di tempat di mana supertype diharapkan.

Subtyping lebih cenderung decidable dan lebih mudah dikelola dalam implementasi.

Pengetikan dependen jauh lebih ekspresif. Tetapi jika Anda pernah ingin menganggap suatu kelompok juga sebagai monoid, maka Anda memerlukan gagasan subsumption untuk melupakan struktur tambahan. Seringkali, seperti saat menggunakan Coq, kewajiban bukti sepele dihasilkan untuk menangani paksaan semacam ini, sehingga dalam praktiknya subtyping mungkin tidak menambah apa pun. Yang lebih penting adalah memiliki cara mengemas berbagai teori untuk membuatnya dapat digunakan kembali, seperti menggunakan kembali teori monoids ketika berbicara tentang kelompok. Jenis kelas dalam Coq adalah inovasi terbaru untuk melakukan hal-hal seperti itu. Modul adalah pendekatan yang lebih tua.

Jika Anda melakukan google cepat "subtipe tipe dependen" Anda menemukan banyak pekerjaan menambahkan subtipe ke tipe dependen, sebagian besar dari sekitar tahun 2000. Saya membayangkan bahwa teori-meta benar-benar menantang, sehingga tidak ada subtipe jenis dependen muncul di asisten bukti.

Dave Clarke
sumber

Terima kasih, inilah tepatnya yang saya cari. Saya telah mengajukan beberapa pertanyaan noob sekarang yang tampaknya agak diterima dengan baik meskipun cstheory.SE bukan Tempat yang Tepat untuk pertanyaan seperti itu. Pada skala -5 hingga +5 akankah Anda mendorong atau mengecilkan pertanyaan serupa di masa mendatang? Sebagai catatan tambahan, seperti yang saya pahami (dari membaca Robert Harper), kelas tipe adalah subkategori modul, benarkah itu?

John Salvatier

Pertanyaan ini ada di sisi kanan perbatasan yang cocok untuk cstheory.SE. Kelas tipe sebenarnya bukan subkategori modul. Ini lebih seperti kelas tipe adalah modul + inferensi tipe + free_plumbing.

Dave Clarke

Saya membayangkan bahwa Anda selalu dapat memodelkan / mensimulasikan subtying dengan tipe dependen dengan cukup mudah. Dalam Haskell, HList (yang hanya dibangun di atas kesetaraan tipe yang dapat didekati) memberi Anda subtyping, misalnya (lihat "Haskell's Overlooked Object System"). Satu-satunya bagian yang sulit tentang subtying adalah inferensi tipe, dan begitu Anda bekerja dengan tipe dependen, Anda tetap membuang 90% dari itu.

sclv

(diubah dari komentar menjadi jawaban)

Neel Krishnaswami

Teori subset dari teori tipe Martin-Loef pada dasarnya adalah apa yang Anda butuhkan untuk memodelkan struktur lupa, dan itu sudah ada sejak tahun 1980-an. Saya pikir ini semacam apa yang @Neel maksudkan dalam jawabannya.

Charles Stewart

Namun, saya lebih tertarik pada teori tipe sebagai dasar untuk matematika daripada sebagai dasar untuk bahasa pemrograman, haruskah saya memperhatikan subtyping?

Satu hal tambahan yang subtyping berikan kepada Anda adalah bahwa subsumsi menyiratkan bahwa banyak sifat koherensi bertahan. Teori tipe dependen juga membutuhkan gagasan bukti tidak relevan untuk memodelkan semua yang dapat Anda lakukan dengan subtipe. Misalnya, dalam teori tipe dependen Anda dapat memperkirakan membentuk subset dengan catatan dependen:

{x \in S |; P (x)} vs. Σ x : S . P (x)

$\{x \in S \;|; P(x)\} \mbox{ vs. } \Sigma x:S.\;P(x)$

Namun, perhatikan bahwa kardinalitas himpunan bagian akan lebih kecil dari , sedangkan catatan dependen dapat memiliki kardinalitas yang lebih besar (karena mungkin ada banyak kemungkinan bukti untuk setiap . $S$ $P(x)$ $x:$

Untuk mewakili subtyping (yang mengatakan bahwa jika , dan maka ), Anda perlu menjadi tidak relevan - yaitu, agar ada paling banyak satu penghuni ketik . $X <: Y$ $x:X$ $x:Y$ $P(x)$ $P(x)$

Setelah Anda memilikinya, Anda dapat menguraikan subtyping secara sistematis menjadi teori tipe dependen. Lihat tesis William Lovas untuk contoh menambahkan subtyping ke teori tipe dependen (dalam hal ini, Twelf).

Neel Krishnaswami
sumber