Bagaimana bahasa imperatif lebih berbeda satu sama lain daripada bahasa fungsional?

Saya membaca buku Simon Peyton Jones, Implementasi Bahasa Pemrograman Fungsional dan ada satu pernyataan yang sedikit mengejutkan saya (di halaman 39):

Untuk tingkat yang jauh lebih besar daripada kasus untuk bahasa imperatif, bahasa fungsional sebagian besar variasi sintaksis satu sama lain, dengan perbedaan semantik yang relatif sedikit.

Sekarang, ini ditulis pada tahun 1987 dan pemikiran saya tentang hal ini mungkin dipengaruhi oleh bahasa pemrograman yang lebih modern yang tidak ada atau populer saat itu. Namun, saya menemukan ini agak sulit dipercaya. Sebagai contoh, saya berpikir bahwa bahasa pemrograman Miranda yang dijelaskan (pendahulu awal Haskell) memiliki semantik yang jauh lebih berbeda dibandingkan dengan bahasa yang ketat seperti ML daripada mengatakan C harus Pascal atau bahkan mungkin C harus smalltalk (walaupun saya akan memberikan itu C ++ memberikan beberapa validasi atas poinnya :-).

Tetapi sekali lagi, saya mendasarkan ini pada pemahaman intuitif saya. Apakah Simon Peyton Jones sebagian besar benar dalam mengatakan ini, atau apakah ini poin yang kontroversial?

Simon pada dasarnya benar, dari sudut pandang ekstensional. Kita tahu betul apa semantik bahasa fungsional modern, dan mereka benar-benar merupakan variasi yang relatif kecil satu sama lain - masing-masing mewakili terjemahan yang sedikit berbeda ke dalam bahasa logam monadik. Bahkan bahasa seperti Skema (bahasa imperatif tingkat tinggi yang diketik secara dinamis dengan kontrol kelas satu) memiliki semantik yang cukup dekat dengan ML dan Haskell.

$V$

Tetapi untuk sampai ke kategori yang cocok untuk menafsirkan bahasa fungsional yang diketik modern, segalanya menjadi cukup menakutkan. Pada dasarnya, Anda akhirnya membangun kategori hubungan ekuivalensi parsial yang diperkaya ultrametrik atas domain ini. (Sebagai contoh, lihat Birkedal, Stovring, dan Thamsborg "Semantis Realisasi Polimorfisme Parametrik, Referensi Umum, dan Jenis Rekursif".) Orang yang lebih suka semantik operasional mengetahui hal ini sebagai hubungan logis langkah-diindeks. (Misalnya, lihat Ahmed, Dreyer dan Rossberg "Kemandirian Representasi Ketergantungan Negara"). Bagaimanapun, teknik yang digunakan relatif baru.

a -> b$\left<a\right> \to T\left<b\right>$$\left<a\right> \to \left<b\right>$$T(A)$$\left<a\right>$a$\to$

Sejauh teori persamaan berjalan, karena bahasa-bahasa ini dapat keduanya dijelaskan oleh terjemahan ke dalam himpunan bagian yang sedikit berbeda dari bahasa yang sama, sepenuhnya adil untuk menyebut mereka variasi sintaksis satu sama lain.

Perbedaan rasa antara ML dan Haskell sebenarnya muncul dari sifat intensional dari dua bahasa - yaitu, waktu eksekusi dan konsumsi memori. ML memiliki model kinerja komposisional (yaitu, biaya waktu / ruang dari suatu program dapat dihitung dari biaya waktu / ruang dari subtermsnya), seperti halnya bahasa panggilan-dengan-nama yang sebenarnya. Haskell yang sebenarnya diimplementasikan dengan panggilan-oleh-kebutuhan, semacam memoisasi, dan akibatnya kinerjanya tidak komposisional - berapa lama ekspresi yang terikat pada variabel diperlukan untuk mengevaluasi tergantung pada apakah ia telah digunakan sebelumnya atau tidak. Ini tidak dimodelkan dalam semantik yang saya singgung di atas.

Jika Anda ingin mengambil sifat intensional lebih serius, maka ML dan Haskell mulai menunjukkan perbedaan yang lebih serius. Mungkin masih mungkin untuk merancang bahasa logam yang umum untuk mereka, tetapi interpretasi jenis akan berbeda dalam cara yang jauh lebih sistematis, terkait dengan ide bukti-teori tentang fokus . Satu tempat yang baik untuk belajar tentang ini adalah tesis PhD Noam Zeilberger.

Perasaan saya adalah bahwa SPJ mengacu pada bahasa yang murni fungsional - yaitu bahasa yang secara transparan transparan. Ini termasuk, misalnya, Haskell, Miranda, Clean, tetapi tidak ML. Setelah Anda memiliki bahasa yang murni fungsional, secara umum, Anda dapat memberikannya semantik denotasional yang cukup bersih dan terdefinisi dengan baik. Semantik ini akan, secara umum, terlihat seperti satu untuk kalkulus lambda, dengan beberapa tweak di sana-sini. Secara umum, Anda akan memiliki sistem tipe yang menginginkan sesuatu yang menyerupai varian Sistem F - mungkin lebih kuat dalam beberapa hal, lebih terbatas pada yang lain. Inilah sebabnya mengapa ekstraksi kode ke / kompilasi ke Haskell, O'Caml, dll. Relatif mudah dari asisten bukti canggih yang diketik secara dependen seperti Agda.

Dalam kerangka itu, ada banyak ruang untuk bermain. Tentu saja, masih ada perbedaan antara bahasa yang tidak ketat dan yang ketat. Namun, dengan tidak adanya efek samping, satu-satunya perbedaan adalah bahwa bahasa yang tidak ketat mengandung lebih banyak ekspresi yang tidak menunjukkan bottom - sejauh kedua strategi evaluasi tidak menghasilkan bottom, mereka setuju.

Pernyataan Simon juga cocok dengan konteks sejarah yang sangat penting. Pada saat kelahiran Haskell (1987), ada persenjataan lengkap dari bahasa fungsional yang tidak ketat - tidak hanya Miranda, tetapi Lazy ML, Orwell, Clean, dan banyak lainnya. Selain variasi sintaksis tertentu, semuanya sangat mirip. Yang justru menjadi motivasi untuk membentuk Komite Haskell. Untuk lebih lanjut tentang ini, lihat "Sejarah Haskell: malas dengan kelas": http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/ .

Saya pikir SPJ benar dalam mengatakan ini untuk semantik inti.

Walaupun ada banyak seluk-beluk tingkat lanjut yang bisa ditunjukkan, seperti default ke evaluasi yang ketat atau malas, seperti yang Anda sebutkan, perincian sistem tipe atau bagaimana unit kode yang lebih besar diatur (modul, struktur), model mental dari suatu program adalah sangat mirip di seluruh bahasa fungsional.

Pilih beberapa fungsi tertentu dan tulis dalam semua bahasa yang Anda bandingkan, dan Anda mungkin akan menemukan bahwa struktur dan semantik dari implementasi yang berbeda akan sangat mirip untuk mereka semua, termasuk tingkat abstraksi, struktur data yang dipilih, mereka semua akan memikul pengumpulan sampah, dll.

Sebaliknya, katakanlah implementasi C vs implementasi Smalltalk dari fungsi yang sama kemungkinan akan memiliki struktur yang berbeda (fungsi dan struktur data tingkat rendah vs objek), fokus pada berbagai tingkat detail (misalnya, manajemen memori manual vs pengumpulan sampah ), dan beroperasi pada berbagai tingkat abstraksi.

Pandangan dunia dari ruang desain bahasa fungsional hanya lebih spesifik dan koheren daripada ruang "pemrograman imperatif" yang menyatukan perakitan, C, Smalltalk, Forth, dan lusinan bahasa lain yang secara radikal berbeda ke dalam satu kategori catchall.

Saya pikir kutipan Simon PJ adalah sedikit komentar yang salah.

Kesamaan antara bahasa ditentukan oleh konsensus apa yang telah dihasilkan dalam komunitas peneliti dan perancang bahasa. Tidak ada pertanyaan bahwa ada tingkat konsensus yang lebih tinggi di komunitas pemrograman fungsional daripada di komunitas pemrograman imperatif. Tetapi juga kasus bahwa bahasa pemrograman fungsional sebagian besar dirancang oleh para peneliti daripada praktisi. Jadi, wajar jika konsensus semacam itu muncul.

Hampir semua bahasa fungsional menggunakan manajemen memori sampah yang dikumpulkan dan struktur data rekursif (berasal dari Lisp), kebanyakan dari mereka menggunakan tipe data "aljabar" dan pencocokan pola (berasal dari Hope), banyak dari mereka menggunakan fungsi orde tinggi dan fungsi polimorfik ( berasal dari ML). Di luar itu, konsensus menghilang. Mereka berbeda dalam sistem modul yang digunakan, bagaimana operasi pergantian negara dan efek komputasi lainnya harus ditangani, dan urutan evaluasi (panggilan-dengan-nama vs nilai-panggilan), dll.

Bahasa pemrograman imperatif umumnya menggunakan struktur kontrol bersarang (berasal dari Algol 60), dan sistem tipe (berasal dari Algol 60, tetapi dikonsolidasikan oleh Algol 68). Mereka umumnya memiliki sintaks permukaan yang rumit (sekali lagi kembali ke Algol 60), melakukan upaya setengah hati untuk menangani fungsi tingkat tinggi dan tipe polimorfik, dan berbeda dalam dukungan mereka untuk struktur blok dan sistem modul. Mungkin ada lebih banyak keseragaman dalam urutan evaluasi karena, setelah 60-an, panggilan-dengan-nama pada dasarnya telah menghilang dari bahasa-bahasa penting.

Jadi, tidak jelas bagi saya bahwa perbedaan antara dua kelas bahasa dalam keseragaman mereka semua hebat.

Akan sangat bermanfaat untuk membawa notasi pemrograman fungsional yang lebih bersih dan seragam ke dalam bahasa pemrograman imperatif. Saya melihat bahwa Scala telah membuat awal ke arah itu. Masih harus dilihat apakah tren akan berlanjut.