Teknik bukti untuk menunjukkan bahwa pemeriksaan tipe dependen dapat dipilih

10

Saya berada dalam situasi di mana saya harus menunjukkan bahwa pemeriksaan ketik dapat dipilih untuk kalkulus yang diketik secara dependen yang sedang saya kerjakan. Sejauh ini, saya dapat membuktikan bahwa sistem ini sangat normal, dan dengan demikian kesetaraan definisi dapat ditentukan.

Dalam banyak referensi yang saya baca, decidability dari typechecking terdaftar sebagai akibat wajar dari normalisasi yang kuat, dan saya percaya pada kasus-kasus itu, tapi saya bertanya-tanya bagaimana orang bisa menunjukkan ini.

Secara khusus, saya terjebak pada hal berikut:

  • Hanya karena istilah yang diketik dengan baik sangat normal, tidak berarti bahwa algoritme tidak akan berulang selamanya pada input yang tidak diketik dengan baik
  • Karena hubungan logis biasanya digunakan untuk menunjukkan normalisasi yang kuat, tidak ada metrik penurunan yang nyaman saat kami mengembangkan istilah pengetikan. Jadi, bahkan jika aturan jenis saya diarahkan sintaks, tidak ada jaminan bahwa penerapan aturan pada akhirnya akan berakhir.

Saya bertanya-tanya, apakah ada yang punya referensi yang baik untuk bukti kepastian pengetikan untuk bahasa yang diketik secara dependen? Jika itu adalah kalkulus inti kecil, itu bagus. Apa pun yang membahas teknik bukti untuk menunjukkan kepatutan akan bagus.

Ya ampun
sumber
7
Algoritma pengecekan tipe dua arah yang biasa tidak pernah mencoba untuk menormalkan suatu istilah (atau tipe) tanpa terlebih dahulu memeriksa apakah itu diketik dengan baik (atau dibentuk dengan baik). Anda tidak perlu khawatir tentang menormalkan istilah yang tidak diketik.
Andrej Bauer
7
Mengenai penerapan aturan: semua aturan istilah dan tipe mengurangi sasaran, kecuali konversi tipe. Jadi kita perlu mengontrol konversi tipe, yang kita lakukan dengan menggunakan pendekatan dua arah.
Andrej Bauer

Jawaban:

9

Memang ada kehalusan di sini, meskipun hal-hal bekerja dengan baik dalam hal pemeriksaan tipe. Saya akan menuliskan masalahnya di sini, karena tampaknya muncul di banyak utas terkait, dan mencoba menjelaskan mengapa semuanya beres ketika mengetikkan teori tipe ketergantungan "standar" (saya akan sengaja tidak jelas, karena masalah ini cenderung muncul terlepas):

Fakta 1: Jika adalah derivasi dari , maka ada derivasi dari untuk beberapa jenis , dan untuk setiap subterm , ada beberapa jenis , konteks dan derivasi dari .DΓt:ADΓA:ssutBΔDΔu:B

Fakta yang baik ini agak sulit untuk dibuktikan, dan diimbangi dengan fakta yang cukup buruk:

Fakta 2: Secara umum, dan bukan merupakan turunan dari !DD D

Ini sedikit tergantung pada formulasi yang tepat dari sistem tipe Anda, tetapi sebagian besar sistem "operasional" yang diterapkan dalam praktik memuaskan Fakta 2.

Ini berarti bahwa Anda tidak dapat "beralih ke sub-istilah" ketika bernalar dengan induksi pada derivasi, atau menyimpulkan bahwa pernyataan induktif benar tentang jenis istilah yang Anda coba buktikan.

Fakta ini menggigit Anda dengan keras ketika mencoba untuk membuktikan pernyataan yang tampaknya tidak bersalah, misalnya bahwa sistem dengan konversi yang diketik sama dengan yang memiliki konversi yang tidak diketik.

Namun , dalam kasus inferensi tipe, Anda dapat memberikan algoritme inferensi tipe dan sortir (tipe tipe) secara simultan dengan menginduksi pada struktur istilah, yang mungkin melibatkan algoritma tipe-terarah seperti yang disarankan Andrej. Untuk istilah tertentu (dan konteks , Anda gagal atau menemukan sehingga dan . Anda tidak perlu menggunakan hipotesis induktif untuk menemukan yang terakhir derivasi, dan khususnya Anda menghindari masalah yang dijelaskan di atas.tΓA,sΓt:AΓA:s

Kasus penting (dan satu-satunya kasus yang benar-benar membutuhkan konversi) adalah aplikasi:

infer(t u):
   type_t, sort_t <- infer(t)
   type_t' <- normalize(type_t)
   type_u, sort_u <- infer(u)
   type_u' <- normalize(type_u)
   if (type_t' = Pi(A, B) and type_u' = A' and alpha_equal(A, A') then
      return B, sort_t (or the appropriate sort)
   else fail

Setiap panggilan untuk menormalkan dilakukan pada istilah yang diketik dengan baik, karena ini adalah invarian untuk inferkesuksesan.


Omong-omong, seperti yang diterapkan, Coq tidak memiliki pengecekan tipe yang dapat didekati, karena akan menormalkan isi fixpernyataan sebelum mencoba mengetikkan memeriksanya.

Bagaimanapun, batas-batas pada bentuk normal dari istilah-istilah yang diketik dengan baik begitu astronomis, sehingga teorema desidabilitas kebanyakan bersifat akademis pada titik ini. Dalam praktiknya, Anda menjalankan algoritme pengecekan tipe selama Anda memiliki kesabaran, dan mencoba rute yang berbeda jika belum selesai saat itu.

cody
sumber
Saya menemukan jawaban Anda sangat berguna, terima kasih. Saya punya dua pertanyaan: 1. Apa artinya "sistem operasional"? Apa alternatifnya? 2. Bisakah Anda lebih eksplisit dengan contoh: apa artinya (fakta apa yang kami coba buktikan?) "Sistem dengan konversi yang diketik setara dengan yang memiliki konversi yang tidak diketik."? Terima kasih!
Łukasz Lew
1
@ ŁukaszLew Alternatif untuk sistem operasional (yang diterapkan dalam praktiknya misalnya perangkat lunak Coq atau Agda) akan menjadi sistem teoretis, yang berguna untuk membuktikan sifat meta-teoretik, tetapi tidak efisien atau tidak nyaman untuk digunakan dalam praktik. Membuktikan kesetaraan sistem operasional dan teori seringkali merupakan bagian penting dari desain sistem. Saya berbicara lebih banyak tentang ini di sini: cstheory.stackexchange.com/a/41457/3984
cody
Saya pikir itu layak menyebutkan Lennart Augustsson's Simpler, Easier! . Ini adalah implementasi Haskell minimal pengecekan tipe dan beberapa kesimpulan untuk kalkulus lambda yang diketik secara dependen. Ada kode yang berhubungan erat dengan cody infer(t u):; untuk menemukannya, cari " tCheck r (App f a) =". Untuk implementasi yang lebih lengkap tetapi masih sederhana, Anda dapat memeriksa Morte'stypeWith .
Łukasz Lew
1
@ ŁukaszLew Masalah konversi yang diketik vs yang tidak diketik adalah pertanyaan terbuka yang terkenal yang berkaitan dengan 2 formulasi teori tipe, dan diselesaikan lebih baru: pauillac.inria.fr/ ~herbelin
cody
Apa artinya ? ut
Jonaprieto