Apa yang tidak bisa dilakukan Idris dengan meninggalkan Turing?

35

Saya tahu bahwa Idris memiliki tipe dependen tetapi belum selesai. Apa yang tidak bisa dilakukan dengan melepaskan kelengkapan Turing, dan apakah ini terkait dengan memiliki tipe dependen?

Saya kira ini adalah pertanyaan yang cukup spesifik, tetapi saya tidak tahu banyak tentang tipe dependen dan sistem tipe terkait.

Squidly
sumber
2
Saya kira Anda sedang mencari contoh konkret? Saya tidak terbiasa dengan Idris, tetapi di Isabelle / HOL Anda tidak dapat menulis (atau lebih tepatnya, mengkompilasi) fungsi yang tidak selalu berakhir (lebih buruk, Anda harus memberikan bukti terminasi ).
Raphael
Sesuatu di sepanjang garis ini ya - Saya tidak sepenuhnya yakin apakah akan ada sesuatu yang cukup ceruk seperti Anda tidak dapat menyandikan bahasa dengan properti tertentu dalam sistem tipe, atau apakah itu akan menjadi sedikit lebih umum (misalnya seperti yang Anda katakan , semua fungsi harus terbukti berakhir)
Squidly
1
Tebak anggapan salah ini datang dari Edwin Brady yang mengatakan bahwa Idris adalah "Pacman complete". Saya pikir poin utamanya dengan mengatakan "Pacman complete" daripada "Turing complete", adalah bahwa ia ingin menggarisbawahi pentingnya bahasa yang mudah dikompilasi oleh otak manusia dan bukan hanya mesin! .. bahasa konyol seperti BrainFuck sudah pasti Turing lengkap, tetapi perlu waktu cukup lama bagi otak manusia untuk memahami kode yang ditulis dalam BrainFuck, sehingga pengembangan, dan bahkan pemeliharaan yang lebih penting , program Pacman di BrainFuck membutuhkan upaya yang cukup besar ..
Michelrandahl
@Mitzh Tidak juga. Saya pikir itu karena saya salah mengerti sesuatu yang saya dengar dia katakan dalam sebuah pembicaraan.
Squidly

Jawaban:

50

Idris Turing Lengkap! Itu memeriksa totalitas (penghentian saat pemrograman dengan data, produktivitas saat pemrograman dengan codata) tetapi tidak mengharuskan semuanya total.

Menariknya, memiliki data dan kodata cukup untuk model Kelengkapan Turing karena Anda dapat menulis monad untuk fungsi parsial. Saya melakukan ini, tahun lalu, di Coq - mungkin sudah bitrotted sekarang tapi ini dia: http://eb.host.cs.st-andrews.ac.uk/Partial/partial.v .

Anda memang perlu satu pelarian untuk benar-benar menjalankan hal-hal seperti itu, tetapi Idris memungkinkan Anda untuk melakukan itu.

Idris tidak akan mengurangi fungsi parsial pada tingkat tipe, agar pemeriksaan jenis dapat dimenangkan. Juga, hanya total program yang dapat dipercaya sebagai bukti.

Edwin Brady
sumber
4
Pria itu sendiri. Apa produktivitas dalam konteks ini?
Squidly
5
Dapat ganda untuk pengakhiran: sementara definisi induktif harus diakhiri (dengan menggunakan semua datanya) definisi koinduktif harus produktif - dalam praktiknya ini berarti, singkatnya, bahwa setiap panggilan rekursif harus dijaga oleh konstruktor. Saya menemukan penjelasan ini sebagai yang paling jelas (ymmv): adam.chlipala.net/cpdt/html/Coinductive.html
Edwin Brady
14

Pertama, saya menganggap Anda sudah pernah mendengar tentang tesis Gereja-Turing , yang menyatakan bahwa apa pun yang kita sebut "perhitungan" adalah sesuatu yang dapat dilakukan dengan mesin Turing (atau salah satu dari banyak model lain yang setara). Jadi bahasa Turing-complete adalah bahasa di mana perhitungan apa pun dapat diekspresikan. Sebaliknya, bahasa Turing-tidak lengkap adalah bahasa di mana ada beberapa perhitungan yang tidak dapat diungkapkan.

Oke, itu tidak terlalu informatif. Izinkan saya memberi contoh. Ada satu hal yang tidak dapat Anda lakukan dalam bahasa Turing-tidak lengkap: Anda tidak dapat menulis simulator mesin Turing (jika tidak, Anda dapat menyandikan perhitungan apa pun pada mesin Turing yang disimulasikan).

Ok, masih tidak terlalu informatif. pertanyaan sebenarnya adalah, apa yang berguna program yang tidak dapat ditulis dalam bahasa Turing-tidak lengkap? Yah, tidak ada yang datang dengan definisi "program yang berguna" yang mencakup semua program yang ditulis seseorang di suatu tempat untuk tujuan yang bermanfaat, dan itu tidak termasuk semua perhitungan mesin Turing. Jadi merancang bahasa Turing-tidak lengkap di mana Anda dapat menulis semua program yang bermanfaat masih merupakan tujuan penelitian jangka panjang.

Sekarang ada beberapa jenis bahasa Turing yang tidak lengkap di luar sana, dan mereka berbeda dalam hal apa yang tidak dapat mereka lakukan. Namun ada tema umum: Bahasa Turing-complete harus menyertakan beberapa cara untuk mengakhiri secara kondisional atau tetap berjalan untuk waktu yang tidak dibatasi oleh ukuran program, dan cara bagi program untuk menggunakan jumlah memori yang tergantung pada input . Konkretnya, sebagian besar bahasa pemrograman imperatif menyediakan kemampuan ini melalui loop sementara dan alokasi memori dinamis masing-masing. Sebagian besar bahasa pemrograman fungsional menyediakan kemampuan ini melalui rekursi dan struktur data bersarang.

Idris sangat terinspirasi oleh Agda . Agda adalah bahasa yang dirancang untuk membuktikan teorema . Sekarang membuktikan teorema dan menjalankan program-program yang sangat erat terkait , sehingga Anda dapat menulis program di Agda seperti Anda membuktikan teorema. Secara intuitif, bukti teorema "A menyiratkan B" adalah fungsi yang mengambil bukti teorema A sebagai argumen dan mengembalikan bukti teorema B.

Karena tujuan dari sistem ini adalah untuk membuktikan teorema, Anda tidak dapat membiarkan programmer menulis fungsi yang sewenang-wenang. Bayangkan bahasa yang memungkinkan Anda untuk menulis fungsi rekursif konyol yang hanya menyebut dirinya:

oops : A -> B
oops x = oops x

Anda tidak dapat membiarkan keberadaan fungsi seperti itu meyakinkan Anda bahwa A menyiratkan B, atau Anda akan dapat membuktikan apa pun dan bukan hanya teorema yang benar! Jadi Agda (dan pembalik teorema serupa) melarang rekursi sewenang-wenang. Ketika Anda menulis fungsi rekursif, Anda harus membuktikan bahwa itu selalu berakhir , sehingga setiap kali Anda menjalankannya pada bukti teorema A Anda tahu bahwa itu akan membangun bukti teorema B.

Keterbatasan praktis langsung dari Agda adalah bahwa Anda tidak dapat menulis fungsi rekursif sewenang-wenang. Karena sistem harus dapat menolak semua fungsi non-terminasi, ketidakpastian masalah penghentian (atau lebih umum teorema Rice ) memastikan bahwa ada fungsi terminasi yang ditolak juga. Kesulitan praktis tambahan adalah bahwa Anda harus membantu sistem untuk membuktikan bahwa fungsi Anda berakhir.

Ada banyak penelitian yang sedang berlangsung untuk membuat sistem bukti lebih seperti bahasa pemrograman tanpa mengurangi jaminannya bahwa jika Anda memiliki fungsi dari A ke B, sama baiknya dengan bukti matematis yang disiratkan oleh A. Memperluas sistem untuk menerima lebih banyak mengakhiri fungsi adalah salah satu topik penelitian. Arah ekstensi lainnya termasuk mengatasi masalah "dunia nyata" seperti input / output dan konkurensi. Tantangan lain adalah membuat sistem ini dapat diakses oleh manusia biasa (atau mungkin meyakinkan manusia biasa bahwa mereka sebenarnya dapat diakses).

Saya tidak terbiasa dengan Idris. Ini adalah tantangan yang baru saja saya sebutkan. Sejauh yang saya mengerti dari pandangan sekilas pada 2013 preprint , Idris adalah Turing-lengkap, tetapi mencakup checker totalitas. Pemeriksa totalitas memverifikasi bahwa setiap fungsi yang dijelaskan dengan kata kunci totalberakhir. Fragmen bahasa yang hanya berisi program Idris di mana setiap fungsi total sama dalam kekuatan ekspresif dengan Arda (mungkin bukan pencocokan persis karena perbedaan dalam teori jenis, tetapi cukup dekat sehingga Anda tidak akan melihat kecuali Anda sengaja mencoba).

Untuk contoh bahasa lain yang tidak menyelesaikan Turing dengan cara yang berbeda, lihat Apa batasan praktis dari bahasa lengkap yang tidak menggunakan turing seperti Coq? (jawaban ini untuk sebagian besar diambil dari).

Gilles 'SANGAT berhenti menjadi jahat'
sumber
3
" program bermanfaat apa yang tidak bisa ditulis dalam bahasa Turing-tidak lengkap?" Mesin virtual Java.
David Richerby
@ DavidRicherby, kan? Apakah JVM benar-benar Turing-lengkap? Ada batasan ukuran objek individual, dapatkah Anda mengatur untuk mengalokasikan dan mengakses sejumlah objek tanpa batas? Misalnya, dalam C, jawabannya tampaknya tidak karena hanya ada banyak nilai pointer.
Gilles 'SO- berhenti bersikap jahat'
Untuk pembaca yang tertarik pada bagian itu, kami memiliki posting lain tentang mengapa tidak ada bahasa pemrograman untuk bahasa yang selalu berakhir.
Raphael
3
@Gilles, saya mengerti maksud Anda, tetapi bukankah ini kurang lebih sama dengan mengatakan bahwa tidak ada bahasa pemrograman aktual yang menyelesaikan Turing? Bagaimanapun, implementasi apa pun akan mengalami hambatan seperti yang Anda sebutkan. Sepertinya ada cukup banyak gajah di dalam ruangan sambil mempertimbangkan apa yang dirugikan oleh Idris dengan tidak menjadi Turing-lengkap. Apakah itu kehilangan lebih dari bahasa lain, misalnya? Jika Anda melarang penyimpanan eksternal tanpa batas (misalnya, program berhenti untuk mengatakan "silakan masukkan disk berikutnya / sebelumnya") maka bahasa apa pun sepele tidak Turing-selesai sehingga setiap pertanyaan tentang kasus itu kosong.
David Richerby
3
@ DavidRicherby Komentar saya (tapi bukan jawaban saya) dalam mode teori bahasa pemrograman geek. Jika Anda mengambil spesifikasi formal SML (misalnya), dimungkinkan untuk merancang (tetapi tentu saja tidak diterapkan di dunia fisik) suatu implementasi bahasa yang dapat mensimulasikan semua program yang dapat dihitung. Ini tidak begitu dalam C, karena kehalusan memori dibangun ke dalam bahasa ( sizeof(void*)). Dalam jawaban saya, saya memperlakukan bahasa dengan cara yang ideal, sehingga SML atau C akan dianggap Turing-lengkap.
Gilles 'SO- stop being evil'