Apakah ada bahasa pemrograman yang menggunakan fungsi rekursif umum sebagai dasarnya?

23

Ini adalah pertanyaan yang naif dan, karenanya, mungkin cacat, jadi minta maaf terlebih dahulu!

Pandangan saya adalah bahwa Mesin Turing dapat dilihat sebagai dasar komputasi untuk bahasa pemrograman prosedural / imperatif. Demikian pula, kalkulus lambda adalah dasar untuk bahasa pemrograman fungsional.

Baru-baru ini saya mengetahui bahwa Tesis Gereja-Turing juga menunjukkan kesetaraan timbal balik dengan model komputasi ketiga: fungsi rekursif umum . Apakah ada bahasa pemrograman yang menggunakan ini sebagai model komputasinya? Jika tidak, adakah alasan teknis mengapa; yaitu, selain "Belum ada yang mencoba"?

Xophmeister
sumber
1
Saya akan mengatakan bahwa mesin Turing atau mesin register universal adalah dasar dari prosesor PL (Majelis PL). Mereka tidak memiliki fungsi. -fungsi rekursif adalah dasar dari PL imperatif. Mereka tidak memiliki fungsi tingkat tinggi. μ
beroal
1
Saya juga merekomendasikan untuk melihat logika tingkat pertama dan Prolog.
Beroal
1
Sebelum C ++ 11, constexprAnda dapat (/ harus) menggunakan 'template' untuk melakukan perhitungan pada waktu kompilasi oleh kompiler. Pembatasan pada templat tidak memungkinkan loop, tetapi Anda dapat menggunakan rekursi untuk meniru loop apa pun, sehingga Anda berakhir dengan fasilitas Turing-complete (meta-programming) sebagai bagian dari standar bahasa C ++, lihat mis. Stackoverflow.com/questions / 189172 / c-templates-turing-complete
JimmyB

Jawaban:

45

Jawaban langsung atas pertanyaan: ya, ada PL yang esoteris dan sangat tidak praktis berdasarkan fungsi rekursif (pikirkan Whitespace), tetapi tidak ada bahasa pemrograman praktis yang didasarkan pada fungsi μ -kursif karena alasan yang sah.μμ

Fungsi rekursif umum (yaitu, rekursif ) secara signifikan kurang ekspresif daripada kalkulus lambda. Dengan demikian, mereka membuat fondasi yang buruk untuk bahasa pemrograman. Anda juga tidak benar bahwa TM adalah dasar dari PL imperatif: pada kenyataannya, bahasa pemrograman imperatif yang baik jauh lebih dekat dengan λ -kalkulus daripada pada mesin Turing.μλ

Dalam hal kemampuan komputasi, fungsi rekursif, mesin Turing, dan λ -kalkulus yang tidak diketik semuanya setara. Namun, LC yang tidak diketik memiliki sifat baik yang tidak dimiliki oleh dua lainnya. Ini sangat sederhana (hanya 3 bentuk sintaksis dan 2 aturan komputasi), sangat komposisional, dan dapat mengekspresikan konstruksi pemrograman yang relatif mudah. Selain itu, dilengkapi dengan sistem tipe sederhana (misalnya, Sistem F ω diperluas dengan f i x ), -calculus dapat menjadi sangat ekspresif karena dapat mengekspresikan banyak konstruksi pemrograman yang kompleks dengan mudah, benar dan komposisi. Anda juga dapat memperpanjangμλFωfixλλλ-kalkulus mudah untuk memasukkan konstruksi yang tidak lambda. Tidak ada model komputasi lain yang disebutkan di atas memberi Anda sifat-sifat yang bagus.

Mesin Turing bukan komposisi atau universal (Anda harus memiliki TM untuk setiap masalah). Tidak ada konsep "fungsi", "variabel" atau "komposisi". Juga tidak sepenuhnya benar bahwa TM adalah dasar dari PL imperatif - FWIW, PL imperatif jauh, jauh lebih dekat dengan kalkulus lambda dengan operator kontrol daripada mesin Turing. Lihat Peter J. Landin "Korespondensi Antara ALGOL 60 dan Notasi Lambda Gereja" untuk penjelasan terperinci. Jika Anda telah memprogram dalam Brainf ** k (yang sebenarnya mengimplementasikan mesin Turing yang agak sederhana), Anda akan tahu bahwa mesin Turing bukan ide yang baik untuk pemrograman.

μ μ Nμ fungsi rekursif mirip dengan TM dalam hal ini. Mereka komposisional, tetapi tidak hampir komposisional seperti LC. Anda juga tidak bisa menyandikan konstruksi pemrograman yang berguna dalam fungsi -recursive. Selain itu, fungsi rekursif hanya menghitung lebih dari , dan untuk menghitung apa pun yang lain, Anda harus menyandikan data Anda ke dalam bilangan asli menggunakan semacam penomoran Gödel, yang menyakitkan.μμN

Jadi, bukan kebetulan bahwa sebagian besar bahasa pemrograman didasarkan pada -calculus! The -calculus memiliki sifat yang baik: ekspresif, komposisionalitas dan ekstensibilitas, yang tidak dimiliki oleh sistem lain. Namun, mesin Turing yang baik untuk mempelajari kompleksitas komputasi, dan fungsi -recursive yang baik untuk mempelajari gagasan logis dari komputabilitas. Mereka berdua memiliki properti luar biasa yang kurang dari -calculus, tetapi di bidang pemrograman -calculus jelas menang.λ μ λ λλλμλλ

Faktanya, ada banyak, lebih banyak lagi sistem lengkap Turing di luar sana, tetapi mereka tidak memiliki properti yang menonjol sama sekali. Permainan Kehidupan Conway, makro LaTeX, dan bahkan (beberapa klaim) DNA semuanya Turing lengkap, tetapi tidak ada satu program (mis. Pemrograman yang serius) dengan Conway atau mempelajari kompleksitas komputasi menggunakan makro LaTeX. Mereka hanya kekurangan properti yang bagus. Turing lengkap per se hampir tidak ada artinya ketika datang ke pemrograman.

Selain itu, banyak sistem komputasi lengkap non-Turing sangat berguna dalam hal pemrograman. Ekspresi reguler dan yacc tidak lengkap, tetapi mereka sangat kuat dalam memecahkan kelas masalah tertentu. Coq juga bukan Turing lengkap, tetapi sangat kuat (sebenarnya dianggap jauh lebih ekspresif daripada sepupu lengkap Turing, OCaml). Ketika datang ke pemrograman, kelengkapan Turing bukanlah kuncinya, karena banyak (hampir) sistem yang tidak berguna Turing tidak lengkap. Anda tidak akan mengklaim bahwa Brainf ** k atau Whitespace adalah bahasa pemrograman yang lebih kuat daripada Coq, bukan? Sebuah ekspresif yayasan adalah kunci untuk bahasa pemrograman yang kuat, dan bahwa ini mengapa bahasa pemrograman modern hampir selalu didasarkan padaλ-kalkulus.

xuq01
sumber
7
"tidak ada program dengan Conway" ... ada yang membuat game Tetris yang berfungsi di Game of Life Conway ... juga memang sama praktisnya dengan spasi putih :)
Alexei Levenkov
Salah satu cara untuk melihat ini adalah bahwa fungsi -calculus yang mensimulasikan mesin Turing mungkin akan jauh lebih pendek daripada mesin Turing yang mensimulasikan -calculus (bukan yang pernah saya lihat juga). λλλ
Ejaan Nonkontekstual
@AlexeiLevenkov Itu sama sekali tidak benar. Whitespace pada dasarnya adalah bahasa imperatif (sederhana), meskipun dengan sintaks yang aneh. Ini memiliki fasilitas untuk aritmatika, aliran dasar kontrol, stack dan manipulasi tumpukan, dan I / O . Proyek QFT, di sisi lain, diperlukan merancang kompiler dari bahasa yang sangat sederhana hingga perakitan RISC yang dibuat untuk CPU yang dibangun dalam otomat seluler mirip Wireworld yang ditiru menggunakan OTCA Metapixels .
Ejaan Nonkontekstual
@AlexeiLevenkov Cogol utama → Kompilator CGoL membutuhkan pekerjaan banyak orang selama empat tahun, sementara ada proyek bernama HaPyLi , yang menyusun bahasa yang jauh lebih rumit untuk Whitespace, yang ditulis oleh satu orang di waktu luang mereka.
Ejaan Nonkontekstual
4

Mengetik µ-recursive function programming languagedi Google membawa saya ke repo GitHub ini , jadi jawaban untuk pertanyaan Anda adalah:

Ya, dan itu disebut miopia

Ngomong-ngomong, ini ditulis dalam Haskell.

Kapol
sumber
μ
2
Tentu saja. Saya hanya berasumsi bahwa OP ingin menemukan bahasa seperti itu untuk mempelajari teori atau sesuatu, bukan untuk benar-benar menaklukkan dunia dengan hal itu ;-)
Kapol