Apa yang membuat inferensi tipe untuk tipe dependen tidak dapat diputuskan?

42

Saya telah melihatnya menyebutkan bahwa sistem tipe dependen tidak dapat disimpulkan, tetapi dapat diperiksa. Saya bertanya-tanya apakah ada penjelasan sederhana mengapa demikian, dan apakah ada atau tidak ada batas "ketergantungan" di mana jenis dapat diindeks oleh nilai-nilai, di bawah ini jenis inferensi yang mungkin dan di atas yang tidak?

Pemenang
sumber
Tidak yakin, tetapi dugaan saya adalah Anda dapat menggunakan inferensi untuk menentukan apakah perhitungan dihentikan atau tidak.
jmite
Apakah ini terkait dengan konversi tipe dalam bahasa pemrograman? ini merupakan masalah terbuka di sana— ketik konversi dalam bahasa pemrograman yang tidak dapat
dipastikan
Alasan lain adalah bahwa tipe dependen tidak mengakui tipe utama. Apa jenis ? λa.a
jmite

Jawaban:

36

Untuk versi yang agak sederhana dari teori tipe dependen, Gilles Dowek memberikan bukti ketakpastian kemampuan mengetik dalam konteks yang tidak kosong:

Gilles Dowek, Ketidakpastian kemampuan mengetik di -kalkulusλΠ

Yang bisa ditemukan di sini .

λ

Idenya adalah untuk menyandikan masalah korespondensi Post sebagai masalah konversi jenis, dan kemudian dengan hati-hati membangun istilah yang dapat diketik jika dua jenis spesifik dapat dikonversi. Ini menggunakan pengetahuan tentang bentuk bentuk normal, yang selalu ada dalam kalkulus ini. Artikel ini pendek dan ditulis dengan baik, jadi saya tidak akan membahas lebih detail di sini.

λ

JB Wells, Kemampuan Mengenal dan memeriksa tipe dalam Sistem F adalah setara dan tidak dapat diputuskan .

Ini dapat ditemukan di sini . Yang saya tahu tentang hal itu adalah bahwa itu mengurangi masalah semi-unifikasi (yang merupakan instantiasi modulo unifikasi kuantifiers universal, dan tidak dapat dipastikan) untuk mengetikkan pengecekan pada Sistem F.

Akhirnya cukup mudah untuk menunjukkan bahwa penghuni keluarga yang tergantung tidak dapat diputuskan: cukup menyandikan masalah Post ke dalam indeks konstruktor. Berikut ini beberapa slide karya Nicolas Oury yang menggambarkan sketsa itu.

Seperti apakah ada "batas", itu sangat tergantung pada apa yang Anda coba lakukan dengan tipe dependen Anda, dan ada banyak perkiraan yang mencoba menjadi decidable, atau setidaknya cukup dekat untuk dapat digunakan. Pertanyaan-pertanyaan ini masih merupakan bagian dari penelitian aktif.

Salah satu jalan yang mungkin adalah bidang "tipe penyempurnaan" di mana bahasa ekspresi dependensi tipe dibatasi untuk memungkinkan pemeriksaan lihat yang dapat ditentukan, misalnya Jenis Cairan . Jarang bahwa inferensi tipe penuh dapat ditentukan bahkan dalam sistem ini sekalipun.

cody
sumber
Tautan jenis cairan terputus
michaelsnowden
@michaelsnowden sudah diperbaiki!
cody