Saya menemukan masalah aneh ketika menulis seorang juru bahasa yang (harus) menghubungkan ke program / fungsi eksternal: Fungsi dalam 'C' dan 'C ++' tidak dapat mengaitkan fungsi variadik , misalnya saya tidak dapat membuat fungsi yang memanggil 'printf' dengan argumen yang sama persis yang didapatnya, dan sebagai gantinya harus memanggil versi alternatif yang mengambil objek variadic. Ini sangat bermasalah karena saya ingin dapat membuat objek yang memegang kait anonim.

Jadi, saya pikir ini aneh karena Forth , JavaScript , dan mungkin kebanyakan bahasa lain dapat melakukan ini dengan sangat mudah tanpa harus menggunakan kode bahasa assembly / mesin. Karena bahasa lain dapat melakukan ini dengan mudah, apakah itu berarti bahwa kelas masalah yang dapat dipecahkan oleh masing-masing bahasa pemrograman sebenarnya berbeda-beda berdasarkan bahasa, meskipun semua bahasa ini lengkap Turing ?

Turing bahasa lengkap dapat menghitung set fungsi yang sama , yang merupakan himpunan fungsi parsial rekursif umum. Itu dia.$\mathbb{N}^k \rightarrow \mathbb{N}$

Ini tidak mengatakan apa-apa tentang fitur bahasa. Mesin Turing memiliki fitur komposisi yang sangat terbatas. The untyped kalkulus jauh lebih komposisi, tetapi tidak memiliki banyak fitur yang umum ditemukan dalam bahasa modern.$\lambda$

Kelengkapan Turing tidak memberi tahu apa pun tentang memiliki tipe, built in array / integer / kamus, kemampuan input / output, akses jaringan, multithreading, alokasi dinamis, ...

Hanya karena Java tidak memiliki fitur X (katakanlah, makro, tipe peringkat lebih tinggi, atau tipe dependen), itu tidak tiba-tiba berhenti menjadi Turing lengkap.

Kelengkapan Turing dan ekspresi bahasa adalah dua konsep yang berbeda.

Kelengkapan Turing adalah konsep abstrak dari kemampuan komputasi. Jika suatu bahasa Turing lengkap, maka ia mampu melakukan perhitungan apa pun yang bisa dilakukan oleh bahasa lengkap Turing lainnya.

Namun, ini tidak mengatakan betapa nyamannya melakukannya. Beberapa fitur yang mudah dalam beberapa bahasa mungkin sangat sulit di yang lain, karena pilihan desain. Kelengkapan Turing hanya mengatakan bahwa Anda dapat melakukan perhitungan. Sebagai contoh ekstrem, mungkin sulit untuk menghubungkan fungsi varadic di C ++, tetapi dimungkinkan untuk menulis penerjemah JavaScript dalam C ++ yang dapat mengaitkan fungsi variadic.

Desain bahasa adalah seni yang cukup menarik. Salah satu langkah utama yang harus dilakukan adalah mengidentifikasi perilaku mana yang Anda inginkan untuk membentuk tulang punggung bahasa Anda. Perilaku ini adalah hal-hal yang mudah dilakukan dalam bahasa Anda karena mereka dibangun di lantai dasar. Kami membuat keputusan desain tentang fitur mana yang akan disertakan dalam setiap bahasa.

Mengenai contoh khusus Anda, ketika C dikembangkan, ia dirancang untuk beroperasi sangat dekat dengan cara bahasa assembly saat itu beroperasi. Fungsi variadic hanya mendorong argumen ke stack, dengan sangat sedikit typesafety. Implementasi fungsi-fungsi variadik ini diserahkan kepada kompiler, untuk memastikan portabilitas maksimum. Dengan demikian, sangat sedikit asumsi yang dibuat tentang kemampuan perangkat keras. Pada saat JavaScript muncul, adegan telah berubah. Itu sudah beroperasi di mesin virtual sebagai bahasa yang ditafsirkan, sehingga keseimbangan bergeser ke arah kenyamanan. Mengizinkan mengaitkan fungsi variad menjadi wajar. Bahkan dalam kasus JavaScript yang Just In Time Compiled, kompiler kami bersedia untuk menyimpan lebih banyak informasi tambahan tentang argumen daripada yang ingin disimpan oleh kompiler C dahulu.

Pikirkan bahasa pemrograman sebagai kendaraan darat yang berbeda: sepeda, mobil, hovercars, kereta api.

Turing Completeness mengatakan, "kendaraan ini bisa pergi ke mana saja kendaraan lain bisa pergi." Artinya, Anda dapat menghitung semua fungsi yang sama. Input ke output, mulai dari akhir.

Tapi, pernyataan itu tidak mengatakan apa - apa tentang bagaimana Anda sampai di sana. Mungkin di rel, mungkin di jalan, mungkin di udara. Dengan cara yang sama, Turing Completeness tidak mengatakan apa-apa tentang bagaimana Anda menghitung suatu fungsi. Anda dapat menggunakan rekursi, atau iterasi, atau automata seluler yang aneh. Anda mungkin menggunakan tipe atau tidak, Anda mungkin menggunakan teknik dinamis atau statis. Tetapi, jika semua yang Anda anggap fungsi (atau set / bahasa formal) Anda dapat menghitung, selama Anda Turing Lengkap, fitur-fitur ini memberi Anda kekuatan yang sama.

Apa yang Anda tanyakan pada dasarnya adalah perbedaan antara kekuatan komputasi dan apa yang biasa disebut kekuatan ekspresif (atau hanya ekspresif ) dari suatu bahasa (atau sistem perhitungan).

Kekuatan Komputasi

Kekuatan komputasi mengacu pada jenis masalah apa yang dapat dikomputasi oleh bahasa. Kelas daya komputasi yang paling terkenal adalah yang setara dengan Universal Turing Machine . Ada banyak sistem komputasi lain, seperti Random Access Machines , λ-calculus , SK combinator calculus , fungsi μ-rekursif , WHILEprogram, dan banyak lainnya. Dan ternyata, semua ini dapat mensimulasikan satu sama lain, yang berarti bahwa mereka semua memiliki kekuatan komputasi yang sama.

Ini memunculkan Tesis Gereja-Turing (dinamai Gereja Alonzo yang menciptakan λ-kalkulus dan Alan Turing yang menciptakan Mesin Universal Turing). Church-Turing-Thesis adalah hipotesis tentang kemampuan komputasi dengan dua aspek:

1. semua sistem komputasi yang mampu melakukan komputasi umum sama kuatnya, dan
2. seorang manusia yang mengikuti suatu algoritma dapat menghitung dengan tepat fungsi-fungsi yang dapat dikomputasi oleh Mesin Turing (dan karenanya sistem lain mana pun).

Yang kedua lebih penting dalam bidang filsafat pikiran daripada ilmu komputer.

Namun, ada dua hal yang tidak dikatakan oleh Turing-Gereja , yang sangat relevan dengan pertanyaan Anda:

1. seberapa efisien berbagai simulasi dan
2. seberapa mudah penyandian masalah.

Contoh sederhana untuk (1): pada Mesin Akses Acak, menyalin array membutuhkan waktu sebanding dengan panjang array. Pada Mesin Turing, bagaimanapun, dibutuhkan waktu sebanding dengan kuadrat dari panjang array, karena Mesin Turing tidak memiliki akses memori acak, itu hanya dapat bergerak melintasi pita satu sel pada suatu waktu. Oleh karena itu, perlu bergerak melintasi n elemen dari array n kali untuk menyalinnya. Jadi, model komputasi yang berbeda mungkin memiliki karakteristik kinerja yang berbeda, bahkan dalam kasus asimptotik, di mana kami mencoba untuk abstrak dari detail implementasi.

Contoh untuk (2) berlimpah: λ-kalkulus dan Python adalah Turing-complete. Tetapi apakah Anda lebih suka menulis program dengan Python atau dalam λ-calculus?

Ada juga kerutan ketiga yang saya alami sampai sekarang: semua sistem asli dirancang oleh ahli logika, filsuf, atau ahli matematika, bukan oleh ilmuwan komputer ... hanya karena komputer dan dengan demikian ilmu komputer tidak ada. Ini semua pergi kembali ke awal 1930-an, bahkan sebelum Konrad Zuse 's sangat eksperimen pertama (yang tidak diprogram dan / atau pula Turing-lengkap). Mereka hanya berbicara tentang "fungsi yang dapat dihitung pada bilangan asli".

Sekarang, ternyata, ada banyak hal yang dapat Anda ekspresikan sebagai fungsi pada bilangan asli - setelah semua, komputer modern kita bahkan bertahan dengan lebih sedikit dari itu (pada dasarnya 3-4 fungsi pada angka 0 dan 1, dan hanya itu ), tetapi, misalnya, fungsi apa yang dihitung oleh sistem operasi?

Gagasan I / O ini, efek samping, berinteraksi dengan lingkungan, tidak ditangkap oleh gagasan "fungsi atas bilangan alami". Namun, ini agak penting, karena, seperti yang pernah dikatakan Simon Peyton Jones "Semua fungsi murni tanpa efek samping, membuat CPU Anda panas" , yang dijawab oleh anggota audiens "sebenarnya, itu adalah sisi -Efek juga! "

Edwin Brady , perancang Idris , (hanya setengah) dengan bercanda menggunakan (saya tidak tahu apakah dia yang menciptakannya) istilah "Tetris-complete" untuk menyatakan perbedaan antara "dapat menghitung fungsi yang dapat dihitung pada bilangan asli" dan "dapat digunakan untuk menulis program non-sepele yang berinteraksi dengan lingkungan ". Yang lebih ironis lagi, ia mendemonstrasikan hal ini dengan mengimplementasikan klon Space Invaders di Idris , tetapi ia mengatakan bahwa ia yakin Tetris berkurang menjadi Space Invaders.

Hal lain untuk menunjukkan adalah bahwa tidak hanya Turing-kesetaraan belum tentu cukup untuk berbicara tentang benar-benar menulis "berguna" program, mungkin Otoh juga bahkan tidak necesssary . Misalnya SQL hanya menjadi setara Turing dengan ANSI SQL: 1999 , tetapi masih berguna sebelum itu. Bahkan, beberapa orang mungkin berpendapat bahwa membuatnya setara dengan Turing tidak menambah manfaatnya sama sekali. Ada banyak Bahasa Khusus Domain yang tidak setara dengan Turing. Deskripsi Data Bahasa biasanya tidak (dan tidak seharusnya). Total Bahasa jelas tidak bisa setara dengan Turing, namun Anda masih bisa menulis loop acara, server web, atau sistem operasi di dalamnya. Ada juga bahasa yang setara dengan Turing tetapi di mana ini sebenarnya dianggap sebagai kesalahan.

Jadi, secara keseluruhan, Turing-equivalence tidak terlalu menarik, kecuali jika Anda ingin menganalisis program secara statis.

Ekspresi

Dengan asumsi bahwa sistem komputasi kita cukup kuat secara komputasi untuk menyelesaikan masalah kita sama sekali, apa yang harus kita lakukan selanjutnya, adalah mengekspresikan algoritma kami untuk memecahkan masalah itu dalam semacam notasi formal untuk sistem itu. Dengan kata lain: kita perlu menulis sebuah program dalam beberapa bahasa komputer. Di situlah gagasan ekspresif muncul.

Ini merujuk pada, pada dasarnya, betapa "mudah" atau "menyenangkan" menulis program kami dalam bahasa pemrograman khusus kami. Seperti yang Anda lihat, gagasan ini cukup kabur, subyektif, dan lebih psikologis daripada teknis.

Namun, ada upaya definisi yang lebih tepat. Yang paling terkenal (dan yang paling keras yang saya tahu) adalah oleh Matthias Felleisen di makalahnya Pada Kekuatan Ekspresif Bahasa Pemrograman (dua halaman pertama berisi perkenalan yang lembut, sisa kertasnya lebih tebal).

Intuisi utamanya adalah ini: ketika menerjemahkan suatu program dari bahasa ke bahasa lain, beberapa perubahan yang perlu Anda lakukan terkandung secara lokal (seperti misalnya mengubah FORloop menjadi WHILEloop atau loop ke conditional GOTOs), dan beberapa memerlukan perubahan ke global struktur program.

Ketika Anda dapat mengganti satu fitur dari satu bahasa dengan fitur yang berbeda dari bahasa yang berbeda hanya dengan transformasi lokal, maka fitur-fitur ini dikatakan tidak berpengaruh pada kekuatan ekspresif. Ini disebut gula sintaksis .

Di sisi lain, jika memerlukan perubahan struktur global program, maka bahasa yang Anda terjemahkan dikatakan tidak dapat mengekspresikan fitur. Dan bahasa tempat Anda menerjemahkan dikatakan lebih ekspresif (berkenaan dengan fitur ini).

Perhatikan bahwa ini memberikan definisi ekspresif yang terukur secara obyektif. Perhatikan juga bahwa gagasan tergantung pada konteks pada fitur, dan itu komparatif. Jadi, jika setiap program dalam bahasa A dapat diterjemahkan ke bahasa B dengan hanya perubahan lokal, dan setidaknya ada satu program dalam bahasa B yang tidak dapat diterjemahkan ke A dengan hanya perubahan lokal, maka bahasa B secara ketat lebih ekspresif daripada bahasa SEBUAH. Namun, skenario yang lebih mungkin adalah bahwa banyak program dalam kedua bahasa dapat diterjemahkan bolak-balik, tetapi ada beberapa program dalam kedua bahasa yang tidak dapat diterjemahkan ke yang lain. Ini berarti bahwa tidak ada bahasa yang lebih ekspresif daripada yang lain, mereka hanya memiliki fitur yang berbeda yang memungkinkan program yang berbeda untuk diekspresikan dengan cara yang berbeda.

Ini memberikan definisi formal tentang apa artinya "lebih ekspresif", tetapi masih tidak menangkap gagasan psikologis di balik fenomena tersebut. Misalnya, gula sintaksis, menurut model ini, tidak meningkatkan kekuatan ekspresif suatu bahasa, karena itu dapat diterjemahkan hanya dengan menggunakan perubahan lokal. Namun, kita tahu dari pengalaman bahwa memiliki FOR, WHILEdan IFtersedia, bahkan jika itu hanya gula sintaksis untuk bersyarat GOTOmembuat mengekspresikan maksud kita lebih mudah .

Faktanya adalah, bahasa yang berbeda memiliki fitur yang berbeda yang membuat mengekspresikan cara berpikir yang berbeda tentang masalah lebih mudah atau lebih sulit. Dan beberapa orang mungkin menemukan satu cara untuk mengekspresikan niat mereka dengan lebih mudah dan yang lain dengan cara yang berbeda.

Sebuah contoh yang saya temukan di tag Ruby pada StackOverflow: banyak pengguna yang mengikuti klaim tag Ruby bahwa loop lebih mudah dipahami daripada rekursi dan rekursi hanya untuk programmer fungsional lanjutan dan loop lebih intuitif untuk pendatang baru, tetapi saya telah melihat beberapa kasus pendatang baru yang secara intuitif menulis kode seperti ini:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Yang biasanya menyebabkan beberapa orang berkomentar bahwa "ini tidak berhasil" dan "mereka melakukan kesalahan" dan "cara yang benar" adalah ini:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Jadi, jelas, ada beberapa orang yang rekursi ekornya merupakan cara yang lebih alami untuk mengekspresikan konsep "perulangan" daripada konstruksi perulangan.

Ringkasan

Fakta bahwa dua bahasa setara Turing mengatakan satu dan tepat satu hal: bahwa mereka dapat menghitung set fungsi yang sama pada bilangan asli seperti yang dapat dilakukan oleh Mesin Turing. Itu dia.

Itu tidak mengatakan apa-apa tentang seberapa cepat mereka menghitung fungsi-fungsi itu. Itu tidak mengatakan apa-apa tentang kemudahan mengekspresikan fungsi-fungsi itu. Dan itu tidak mengatakan apa-apa tentang apa lagi yang bisa mereka lakukan selain menghitung fungsi pada bilangan asli (misalnya menautkan ke pustaka C, membaca input dari pengguna, menulis output ke layar).

apakah itu berarti bahwa kelas masalah yang dapat dipecahkan oleh setiap bahasa pemrograman berbeda-beda berdasarkan bahasa, meskipun semua bahasa ini sudah lengkap?

Iya nih.

1. Ada masalah yang tidak tercakup oleh istilah "Turing-complete" (yang hanya menyangkut dirinya sendiri dengan fungsi komputasi pada bilangan asli) seperti mencetak ke layar. Dua bahasa dapat menyelesaikan Turing tetapi satu dapat memungkinkan pencetakan ke layar dan yang lainnya tidak.
2. Bahkan jika kedua bahasa dapat memecahkan masalah yang sama, itu tidak mengatakan apa-apa tentang betapa rumitnya pengkodean, dan betapa mudahnya mengekspresikan pengodean ini. Misalnya C dapat menyelesaikan setiap masalah yang Haskell bisa, cukup dengan menulis juru bahasa Haskell di C ... tetapi Anda harus menulis juru bahasa Haskell terlebih dahulu untuk menyelesaikan masalah dengan cara ini!

Semua bahasa pemrograman lengkap Turing dapat menerapkan serangkaian algoritma yang sama. Jadi, jika Anda melihat bahwa beberapa algoritma sangat sulit diimplementasikan dalam bahasa tertentu, itu tidak berarti tidak mungkin.

Ingat bahwa suatu bahasa terdiri dari sintaks dan semantik. Terkadang, himpunan kata-kata milik beberapa bahasa tidak minimum untuk dianggap Turing lengkap, ada fitur yang membuat segalanya lebih mudah (itu sebabnya mereka disebut fitur ). Jika Anda mengeluarkan fitur-fitur itu, bahasa Turing masih lengkap.

Beberapa di antaranya mungkin menarik:

• Kompiler sumber-ke-sumber di Wikipedia

• Tentang pentingnya kelengkapan Turing pada Lambda the Ultimate

Semua bahasa Turing-lengkap dapat menghitung hal yang sama.

Jika Anda mencoba menerapkan bahasa modern, Anda akan melihat bahwa sebagian besar fiturnya tidak menambah kemampuan komputasi apa pun. Banyak dari fitur tersebut dapat diturunkan ke yang lebih sederhana yang sudah ada dalam bahasa yang sama.

Berikut ini beberapa contohnya:

• Jika Anda tidak memiliki enum, Anda dapat menggunakan bilangan bulat.
• Jika Anda tidak memiliki buffer yang mengetahui ukurannya, Anda bisa membuat tipe yang berisi ukuran dan buffer yang tidak tahu ukurannya.
• Jika Anda tidak memiliki batas memeriksa buffer, Anda bisa memeriksa indeks setiap kali Anda menggunakannya.
• Jika Anda tidak memiliki fungsi variadic, Anda dapat membuat fungsi yang mengambil buffer yang mengetahui ukurannya dan membaca dari buffer itu informasi yang sama yang Anda dapatkan dari argumen formal.
• Jika Anda tidak memiliki operator, Anda dapat menggunakan berbagai fungsi.
• Jika Anda tidak memiliki tipe yang dapat mewarisi satu sama lain, Anda dapat membuat tipe yang berisi satu sama lain dan mengaksesnya melalui tingkat tipuan ekstra, dengan subtyping menjadi sekadar transformasi dari tipe handle-to-the-whole ke sebuah handle-to-the-contained-type.
• Jika Anda tidak memiliki delegasi tetapi Anda memiliki pointer fungsi, Anda bisa membuat tipe yang berisi objek referensi dan pointer fungsi.
• Jika Anda tidak memiliki delegasi tetapi Anda memiliki antarmuka, Anda dapat mendeklarasikan antarmuka yang berisi metode tunggal dengan tanda tangan yang Anda inginkan.
• Jika Anda tidak memiliki tipe generik, Anda dapat menggunakan tipe non-generik yang hanya mengasumsikan batas atas atau bawah yang Anda minati (dan mungkin melakukan gips yang sesuai di tempat penggunaan, untuk membuat kompiler senang).
• Jika Anda tidak memiliki sistem tipe linear / affine, Anda bisa menghindari menggunakan variabel apa pun lebih dari sekali.
• ...dan seterusnya.

Desain bahasa arus utama berfokus pada fitur yang membuatnya lebih mudah dan lebih nyaman bagi kita untuk menghitung hal-hal lebih cepat, mengenali kesalahan kita sebelumnya, memprogram terhadap komponen yang tidak dikenal, membuat paralelisme lebih aman, dan sebagainya.

Hal-hal yang murni komputasi telah dipakukan sejak lama.

Jawaban yang ada dengan tepat menunjukkan bahwa kelengkapan Turing bukan cara yang baik untuk membandingkan bahasa. Memang, hampir semua bahasa Turing lengkap. ("Jika semua orang istimewa, maka tidak ada yang istimewa," seperti yang biasa dikatakan The Incredibles.)

Namun, adalah mungkin untuk membandingkan ekspresi bahasa dengan presisi matematis. Lihatlah Felleisen's On the Expressive Power dari Bahasa Pemrograman . Secara kasar, idenya adalah untuk mengajukan pertanyaan berikut: Dapatkah saya mengubah program apa pun dalam bahasa A menjadi program dalam bahasa B dengan hanya membuat perubahan lokal ? Dengan kata lain, Felleisen memberikan bentuk matematis yang tepat untuk intuisi Anda.

Di atas jawaban semua orang, inilah analogi lain.

Untuk mencuci pakaian, Anda memerlukan tiga hal: beberapa reservoir yang menampung air, deterjen dari beberapa jenis, dan mekanisme agitasi. Ini bisa diwujudkan dengan banyak cara. Waduk air adalah apa saja yang menampung cukup air (misalnya bak, danau, sungai). Mekanisme agitasi bisa berupa alat mekanis, papan cuci, atau bahkan batu tempat pakaian dipukuli. Dan deterjen datang dalam berbagai bentuk juga.

Jadi apa perbedaan antara mesin cuci modern terkomputerisasi, dan batu di sebelah sungai?

Itu bermuara pada tiga hal: efisiensi, keamanan, dan kenyamanan. Beberapa metode pencucian menggunakan lebih sedikit energi, lebih sedikit mencemari lingkungan, menggunakan lebih sedikit air, dan sebagainya. Beberapa metode pencucian membutuhkan aktivitas manual yang kurang berulang (yang mengakibatkan cedera) atau berada di luar dalam cuaca buruk. Dan beberapa metode mencuci tidak memerlukan manusia untuk mengasuh prosesnya.

Bahasa pemrograman Turing-complete adalah tujuan umum, sehingga mereka digunakan untuk lebih dari satu tugas. Meskipun demikian, untuk tugas yang diberikan, beberapa bahasa pemrograman lebih efisien, lebih mudah, dan lebih aman (dalam arti bahwa lebih sedikit kesalahan bisa terjadi ketika program tersebut benar-benar digunakan) daripada yang lain.

Yang lain telah memberikan banyak jawaban yang baik, tetapi mereka tidak secara eksplisit menyebutkan satu peringatan yang pernah sangat membingungkan saya: Turing kelengkapan tidak menyiratkan bahwa suatu bahasa dapat mengekspresikan fungsi yang dapat dihitung secara sewenang-wenang dari inputnya ke outputnya. Itu lebih lemah: harus ada beberapa cara untuk mewakili domain dan rentang himpunan fungsi yang dapat dihitung sebagai input dan output sehingga masing-masing fungsi ini memetakan ke program yang membawa representasi inputnya ke output yang sesuai.

Ambil, misalnya, bahasa yang mengekspresikan mesin Turing. Setiap program dalam bahasa adalah mesin Turing.

Sekarang pertimbangkan subbahasa semua mesin Turing yang membaca dan menulis hanya karakter a, b, dan kosong. Itu Turing lengkap, tetapi tidak dapat mengekspresikan program apa pun yang, misalnya, menghasilkan c pada semua input, karena tidak dapat menulis cs apa pun. Itu hanya dapat mengekspresikan semua fungsi yang dapat dihitung pada input dan output yang dikodekan sebagai string as dan bs.

Jadi tidak benar bahwa semua bahasa Turing-lengkap dapat menghitung hal-hal yang sama, bahkan ketika kita membatasi hal-hal ini menjadi fungsi yang dapat dihitung dari input potensial mereka ke output potensial mereka. Bahasa mungkin memerlukan input dan output untuk dikodekan dengan cara tertentu.