Apakah kompiler untuk tipe dependen jauh lebih sulit daripada intepreter?

11

Saya telah belajar sesuatu tentang menerapkan tipe dependen, seperti tutorial ini , tetapi kebanyakan dari mereka menerapkan juru bahasa. Pertanyaan saya adalah, tampaknya menerapkan kompiler untuk tipe dependen jauh lebih sulit daripada kompiler, karena Anda benar-benar dapat mengevaluasi argumen tipe dependen untuk pengecekan tipe.

Begitu

  • Apakah kesan naif saya benar?
  • Jika benar, ada contoh / sumber daya tentang penerapan bahasa yang diperiksa secara statis yang mendukung tipe dependen?
type-systems compilers dependent-type molikto
sumber
Tidak, karena Anda dapat mengurangi masalah kompilasi tipe dependen menjadi masalah yang diketahui: (1) ketik periksa program menggunakan juru bahasa; (2) mengekstrak program ke OCaml / Haskell / apa pun; (3) kompilasi menggunakan ocamloptatau GHC :-) (
Omong

Jawaban:

12

Ini pertanyaan yang menarik! Seperti jawaban Anthony menyarankan, seseorang dapat menggunakan pendekatan biasa untuk menyusun bahasa fungsional yang tidak tergantung, asalkan Anda sudah memiliki juru bahasa untuk mengevaluasi persyaratan untuk pengecekan tipe .

Ini adalah pendekatan yang diambil oleh Edwin Brady. Sekarang ini secara konsep lebih sederhana, tetapi tidak kehilangan keunggulan kecepatan kompilasi ketika melakukan pengecekan tipe. Ini telah dibahas dalam beberapa perilaku.

Pertama, seseorang dapat mengimplementasikan mesin virtual yang mengkompilasi istilah-istilah untuk byte-code on the fly untuk melakukan pemeriksaan konversi. Ini adalah ide di balik vm_computediterapkan dalam Coq oleh Benjamin Gregoire . Rupanya ada juga tesis ini oleh Dirk Kleeblatt pada subjek yang tepat ini, tetapi menurunkan kode mesin yang sebenarnya daripada mesin virtual.

Kedua, seseorang dapat menghasilkan kode dalam bahasa yang lebih konvensional yang, setelah dieksekusi, memeriksa semua konversi yang diperlukan untuk mengetik-periksa program yang diketik secara dependen. Ini berarti kita dapat menggunakan Haskell, misalnya, untuk mengetik-periksa modul Agda. Kode dapat dikompilasi dan dijalankan, dan jika diterima, maka kode dalam bahasa tipe dependen dapat diasumsikan diketik dengan baik (pembatasan implementasi dan kesalahan kompiler). Saya pertama kali mendengar pendekatan ini yang disarankan oleh Mathieu Boesflug .

∗

cody
sumber
1
Agak di-cheeck: mengapa Anda repot-repot menulis kompiler jika Anda memiliki penerjemah melakukan pengecekan tipe? Lagi pula, sebagian besar (semua?) Pengguna serius dari bahasa pemrograman yang diketik secara dependen hanya peduli pada pemeriksa tipe, menggunakan bahasa sebagai asisten bukti. Saya tentu saja tidak pernah benar-benar menjalankan program Agda atau Coq saya. Jadi, jika Anda peduli tentang kecepatan, bukankah Anda ingin mengkompilasi konversi tipe?
Martin Berger
2
Solusi 2 dan 3 mengatasi masalah ini: Anda mengkompilasi kode yang memeriksa ketikan yang baik (dan khususnya melakukan konversi jenis). Komentar kedua saya adalah bahwa Anda sebenarnya ingin menjalankan kode yang diketik secara dependen dalam beberapa situasi (lihat Idris, Ur / Web).
cody
1
Juga: sampai batas tertentu, solusi 1 mengatasinya juga, dengan mengaburkan garis antara interpreter dan kompiler.
cody
1
Saya ingin tahu apakah teknik proyeksi futurama dapat digunakan untuk mempercepat penerjemah, secara efektif berakhir dengan kompiler?
Steven Shaw
1
Satu-satunya hal yang saya lihat adalah Unison unisonweb.org/2017-10-13/scala-world.html
Steven Shaw
10

Tesis PhD Edwin Brady menguraikan bagaimana membangun kompiler untuk bahasa pemrograman yang diketik secara dependen. Saya bukan seorang ahli, tetapi saya akan mengatakan itu tidak terlalu sulit daripada mengimplementasikan kompiler seperti Sistem F. Banyak prinsip yang sangat mirip dan ada yang sama (misalnya kompilasi supercombinator.) Tesis ini mencakup banyak masalah lain.

Anthony
sumber