Mungkinkah memiliki bahasa pemrograman 'berguna' yang belum selesai Turing?

Di mana diterima bahwa suatu bahasa harus Turing lengkap untuk menjadi baik, apakah mungkin untuk memiliki bahasa pemrograman 'berguna' yang Turing tidak lengkap?

Saya harus mengklarifikasi bahwa ini cukup khusus tentang bahasa 'pemrograman' dalam pengertian tradisional, dan bukan bahasa markup atau query.

Coq , Agda , HOL dan ACL2 adalah bahasa yang sangat berguna dan sangat kuat, meskipun mereka tidak lengkap Turing.

Fitur umum yang menjadikannya non-Turing-complete adalah fakta bahwa selalu mungkin untuk membuktikan pemutusan hubungan kerja. Batasan yang sangat sederhana sudah cukup: panggilan rekursif hanya diperbolehkan dengan ketentuan yang secara struktural lebih kecil terbukti. Oleh karena itu, walaupun tidak mungkin untuk mengimplementasikan juru bahasa untuk bahasa lengkap Turing atau bahkan untuk bahasa itu sendiri, banyak hal berguna lainnya masih mungkin, seperti kompiler C bersertifikat .

Saya akan berpikir istilah "mini-bahasa" Yegge mengacu pada fakta bahwa sering berguna untuk menggunakan bahasa untuk masalah khusus di mana bahasa tidak memerlukan turing-kelengkapan untuk menyelesaikan tugas, dan ini masuk ke jantung bagaimana non -Turing bahasa lengkap dapat bermanfaat. https://sites.google.com/site/steveyegge2/language-grubbing

Wikipedia menjawab ini dengan sangat baik, sesuai dengan apa yang dikatakan oleh usus saya. Pertama saya berpikir matematika murni, lalu saya ingat regexp, dan Wikipedia mencantumkan Epigram yang saya yakin akan berada di jalur 'matematika murni'.

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

Bahasa non-Turing-lengkap

Banyak bahasa komputasi ada yang tidak lengkap Turing. Salah satu contohnya adalah seperangkat bahasa reguler, yang paling umum adalah ekspresi reguler, yang dihasilkan oleh automata terbatas. Perpanjangan yang lebih kuat tetapi masih belum Turing-complete automata terbatas adalah kategori pushdown automata dan tata bahasa bebas konteks, yang umumnya digunakan untuk menghasilkan pohon parse pada tahap awal penyusunan program. Contoh lebih lanjut termasuk beberapa versi awal bahasa pixel shader yang tertanam dalam Direct3D dan ekstensi OpenGL, atau serangkaian rumus matematika dalam spreadsheet tanpa siklus. [Rujukan?] Dalam bahasa pemrograman fungsional total, semua fungsi adalah total, dan harus berakhir, seperti Charity dan Epigram. Amal menggunakan sistem tipe dan kontrol konstruksi berdasarkan teori kategori,

Bahasa data

Gagasan Turing-kelengkapan tidak berlaku untuk bahasa seperti XML, JSON, YAML dan ekspresi-S, karena mereka biasanya digunakan untuk mewakili data terstruktur, tidak menggambarkan perhitungan. Ini kadang-kadang disebut sebagai bahasa markup, atau lebih tepatnya sebagai "bahasa deskripsi data".

Itu juga menyebutkan representasi struktur data bukan bahasa, tapi saya akan berpikir XSLT harus dihitung sebagai representasi komputasi, XPath mungkin tidak didasarkan pada apa yang dikatakan Yannis di atas tentang SQL sebagai bahasa query dan bukan bahasa komputasi. Mungkin T-SQL atau PL / SQL dianggap sebagai bahasa komputasi karena Anda dapat melakukan banyak perhitungan menggunakan agregat mereka, di mana bentuk umum dari SQL mungkin tidak menentukan agregat.

Saya mengerti SQL cukup populer di kalangan tipe bisnis

Turing kelengkapan diperlukan agar suatu bahasa cocok untuk digunakan sebagai bahasa tujuan umum. Tapi itu tidak cukup , yaitu hanya karena Turing lengkap, tidak cocok untuk setiap domain masalah:

• Whitespace terbukti Turing lengkap tetapi jelas tidak cocok untuk masalah domain di luar hiburan programmer.
• Templat C ++ telah terbukti Turing lengkap, tetap saja Anda tidak akan pernah menulis seluruh program bersama mereka.

Sebaliknya, DSL cocok untuk domain masalah yang dirancang untuknya (dengan asumsi itu memang dirancang dengan baik), bahkan tanpa kelengkapan Turing:

• HTML ^* menyediakan cara ringkas untuk menggambarkan pohon DOM. Sementara JavaScript adalah Turing lengkap dan dapat digunakan untuk melakukan hal yang sama, itu jauh lebih berisik dan tidak jelas
• XPath dan bahasa permintaan lainnya, PCRE tanpa kode yang disematkan dan semacamnya adalah alat yang ampuh untuk pekerjaan tunggal yang dirancang untuk mereka

^* IIRC telah terbukti bahwa HTML dengan animasi CSS sudah Turing lengkap dengan menggunakannya untuk mengimplementasikan Game of Life Conway pada larik kotak centang. Tetapi kegunaan HTML bertahan bahkan di browser yang tidak mendukung animasi CSS.

Sebenarnya ada bahasa pemrograman yang ada, di mana Anda hanya dapat menulis program "efisien". Efisien dalam arti ini berarti bahwa setiap program yang ditulis dalam bahasa seperti itu mewakili bahasa dalam bahasa P. Bellantoni, Niggl dan Schwichtenberg menjelaskan bahasa seperti itu di sini .

C preprocessor tidak Turing-lengkap (dengan desain), namun masih bisa menerapkan juru untuk bahasa yang adalah Turing lengkap (Order-the-bahasa, seperti yang dijelaskan dalam dokumentasi, pada dasarnya hanya run-of-the- pabrik murni hal ML / Skema jenis hal, dan akan relatif biasa-biasa saja - mungkin cukup baik untuk digunakan - jika bukan karena implementasi yang tidak biasa).

Trik di baliknya mirip dengan argumen di atas tentang menerapkan mesin Turing apa pun di alam semesta fisik yang terbatas: preprosesor C tidak dapat memberikan jumlah langkah yang tak terbatas , atau sel data, ke bahasa, tetapi dapat:

1. memberikan angka dinamis yang tidak masuk akal (2 ^ 64 atau lebih secara default), cukup besar untuk memecahkan masalah yang paling realistis menggunakan proses ekspansi eksponensial ( bergumam seumur hidup bergumam dari dunia bergumam ).

2. menggunakan tutup statis acak untuk angka di atas, yaitu sementara jumlah langkah harus beberapa angka terbatas, Anda dapat mengubah apa cap spesifik pada "kompilasi" -waktu dengan mengubah pengaturan statis mesin interpreter. Karena tidak ada batasan (teoritis) pada nilai aktual dari tutup ini, maka (secara teoritis) dapat diperluas agar sesuai dengan persyaratan ruang untuk program penghentian apa pun .

Bukan untuk membantah bahwa Order harus "berguna" dalam dirinya sendiri, atau bahwa mesin yang diimplementasikan CPP akan, tetapi itu adalah bukti konsep yang menarik. Itu juga seharusnya diketik secara dinamis , yang tidak biasa untuk area ini.

Ya, memang mungkin untuk memiliki bahasa yang bermanfaat yang Turing tidak lengkap. Lihat di sini: http://tkatchev.bitbucket.org/tab/examples.html

Contoh lain dari bahasa Turing yang berguna tidak lengkap adalah SQL. (Dan yang lainnya adalah spreadsheet seperti Gnumeric atau Excel, meskipun sebenarnya bukan bahasa pemrograman.)

Tentang mengapa Anda ingin bahasa yang Turing tidak lengkap: karena itu memungkinkan Anda untuk membuat beberapa jaminan kuat tentang perilaku runtime.

Turing kelengkapan, jelasnya, berarti memiliki kapasitas untuk rekursi. Memiliki rekursi berarti memiliki struktur yang berpotensi tidak terbatas dalam memori. Karena di dunia nyata memori tidak terbatas, kelengkapan Turing membutuhkan manajemen memori dan / atau pengumpulan sampah.

Melarang rekursi adalah cara yang bagus untuk menghindari masalah manajemen sumber daya yang sangat, sangat sulit.

Nota bene! Menjadi Turing tidak lengkap tidak selalu berarti bahwa program apa pun akan berakhir. Bahasa Turing yang tidak lengkap dapat memungkinkan mengevaluasi daftar malas yang tak terbatas.

Satu "bahasa pemrograman sub-Turing" yang menarik tidak disebutkan sampai sekarang jadi saya akan menambahkannya.

Ini disebut "Crema" . Ini menggambarkan dirinya sebagai:

Crema adalah front-end LLVM yang bertujuan untuk secara khusus dieksekusi di ruang Sub-Turing Lengkap. Dirancang agar mudah dipelajari, dan praktis untuk sebagian besar tugas pemrograman yang diperlukan, Crema dapat membatasi kompleksitas komputasi program hingga minimum yang diperlukan untuk meningkatkan keamanan.

Levelnya cukup minimalis dan agak rendah.

Seharusnya terlihat akrab bagi pengembang C.

Awalnya didanai oleh Badan Penelitian Proyek Pertahanan (DARPA), tetapi terlihat tidak terawat pada saat penulisan. Tapi mungkin seseorang tertarik.