Mengapa menulis kompiler dalam bahasa fungsional lebih mudah? [Tutup]

89

Saya telah memikirkan pertanyaan ini sangat lama, tetapi benar-benar tidak dapat menemukan jawabannya di Google serta pertanyaan serupa di Stackoverflow. Jika ada duplikatnya, saya minta maaf untuk itu.

Banyak orang tampaknya mengatakan bahwa menulis kompiler dan alat bahasa lain dalam bahasa fungsional seperti OCaml dan Haskell jauh lebih efisien dan lebih mudah daripada menulisnya dalam bahasa imperatif.

Apakah ini benar? Dan jika demikian - mengapa begitu efisien dan mudah untuk menulisnya dalam bahasa fungsional daripada dalam bahasa imperatif, seperti C? Juga - bukankah alat bahasa dalam bahasa fungsional lebih lambat dari pada beberapa bahasa tingkat rendah seperti C?

compiler-construction haskell ocaml functional-programming wvd
sumber
5
Saya tidak akan mengatakan itu lebih mudah. Tetapi sifat fungsional dari tugas-tugas kompilasi seperti parsing mungkin cocok secara alami untuk pemrograman fungsional. Bahasa fungsional seperti OCaml bisa sangat cepat, menyaingi kecepatan C.
Robert Harvey
17
Teman-teman, apakah ini benar-benar argumentatif? Tentunya seseorang memiliki wawasan. Saya ingin tahu diri saya sendiri.
Robert Harvey
Saya pikir setidaknya harus ada beberapa alasan bagus mengapa menggunakan bahasa fungsional daripada bahasa imperatif. Saya telah menemukan beberapa artikel yang pada dasarnya menyatakan bahwa bahasa fungsional tidak memiliki efek samping dan semacamnya. Tapi itu sama sekali tidak jelas. Namun, jika ini argumentatif, maka mungkin lebih baik untuk menutupnya atau merumuskan kembali pertanyaannya.
wvd
12
Apakah benar-benar argumentatif untuk mengakui bahwa beberapa ceruk lebih cocok untuk gaya bahasa tertentu? "Mengapa C lebih baik daripada Javascript untuk menulis driver perangkat" tidak akan kontroversial, menurut saya ...
CA McCann
1
Saya pikir itu akan menjadi sebaliknya. Saya membaca "kompiler super kecil" dan menggunakan mutasi variabel di semua tempat.
Rolf

Jawaban:

102

Seringkali kompiler banyak bekerja dengan pohon. Kode sumber diurai menjadi pohon sintaks. Pohon itu kemudian dapat diubah menjadi pohon lain dengan anotasi tipe untuk melakukan pemeriksaan tipe. Sekarang Anda dapat mengubah pohon itu menjadi pohon yang hanya berisi elemen bahasa inti (mengubah notasi sintaksis seperti gula ke dalam bentuk yang tidak berbatu). Sekarang Anda dapat melakukan berbagai pengoptimalan yang pada dasarnya adalah transformasi di pohon. Setelah itu Anda mungkin akan membuat pohon dalam beberapa bentuk normal dan kemudian mengulangi pohon itu untuk membuat kode target (perakitan).

Bahasa fungsional memiliki fitur seperti pencocokan pola dan dukungan yang baik untuk rekursi yang efisien, yang membuatnya mudah untuk bekerja dengan pohon, jadi itulah mengapa mereka umumnya dianggap sebagai bahasa yang baik untuk menulis kompiler.

sepp2k.dll
sumber
Jawaban paling lengkap sejauh ini, saya akan tandai sebagai jawaban yang diterima, namun menurut saya jawaban Pete Kirkham juga bagus.
wvd
1
Bagaimana dengan "pembuktian kebenaran", karena ketepatan kompilator adalah atribut penting, saya sering mendengar bahwa penggemar bahasa fungsional memasukkan "bukti" ketepatan ke dalam alur kerja mereka. Saya tidak tahu apa artinya secara praktis, tetapi karena keandalan kompiler itu penting, ini tampaknya bermanfaat.
Warren P
3
@WarrenP: Konsep "kode pembawa bukti" berasal dari bahasa fungsional yang diketik secara statis. Idenya adalah Anda menggunakan sistem tipe sedemikian rupa sehingga suatu fungsi hanya dapat mengetik memeriksa apakah benar, jadi fakta yang dikompilasi kode adalah bukti kebenaran. Tentu saja ini tidak sepenuhnya mungkin sambil menjaga bahasa turing-complete dan typechecking decidable. Tapi semakin kuat sistem tipe, semakin dekat Anda bisa mencapai tujuan itu.
sepp2k
3
Alasan mengapa konsep ini sangat populer di komunitas fungsional adalah karena dalam bahasa dengan status bisa berubah, Anda juga harus menyandikan informasi tentang kapan dan di mana perubahan status terjadi pada jenis. Dalam bahasa yang Anda tahu bahwa hasil dari suatu fungsi hanya bergantung pada argumennya, jauh lebih mudah untuk mengenkode bukti dalam tipe (juga jauh lebih mudah untuk membuktikan kebenaran kode secara manual karena Anda tidak perlu mempertimbangkan status global yang mana mungkin dan bagaimana hal itu akan mempengaruhi perilaku fungsi). Namun tidak satupun dari ini secara khusus terkait dengan kompiler.
sepp2k
3
Satu-satunya fitur terpenting adalah pencocokan pola menurut saya. Mengoptimalkan pohon sintaksis abstrak dengan pencocokan pola sangatlah mudah. Melakukannya tanpa pencocokan pola sering kali sangat sulit dilakukan.
Bob Aman
38

Banyak tugas kompilator yang mencocokkan pola pada struktur pohon.

Baik OCaml dan Haskell memiliki kemampuan pencocokan pola yang kuat dan ringkas.

Lebih sulit menambahkan pencocokan pola ke bahasa imperatif karena nilai apa pun yang sedang dievaluasi atau diekstraksi untuk mencocokkan pola harus bebas efek samping.

Pete Kirkham
sumber
Kedengarannya seperti jawaban yang masuk akal, tetapi apakah ini satu-satunya? misalnya apakah hal-hal seperti rekursi ekor juga berperan?
wvd
Itu sepertinya menunjukkan bahwa ini lebih merupakan masalah sistem tipe daripada model eksekusi yang sebenarnya. Sesuatu yang didasarkan pada pemrograman imperatif dengan nilai yang tidak dapat diubah atas tipe struktural mungkin baik-baik saja.
Donal Fellows
@wvd: Pengoptimalan rekursi tail adalah detail implementasi, bukan fitur bahasa seperti itu, yang membuat fungsi rekursif linier setara dengan loop iteratif. Fungsi rekursif untuk menjalankan daftar tertaut di C akan mendapat manfaat darinya sama seperti pengulangan pada daftar di Skema.
CA McCann
@wvd gcc C memiliki penghapusan panggilan ekor, seperti halnya bahasa negara bagian yang dapat berubah lainnya
Pete Kirkham
3
@camccann: Jika standar bahasa menjamin tco (atau setidaknya menjamin bahwa fungsi rekursif dari bentuk tertentu tidak akan pernah menyebabkan stack overflow atau pertumbuhan linier dari konsumsi memori), saya akan mempertimbangkan itu sebagai fitur bahasa. Jika standar tidak menjaminnya, tetapi kompilator tetap melakukannya, itu adalah fitur kompilator.
sepp2k
15

Salah satu faktor penting untuk dipertimbangkan adalah bahwa sebagian besar proyek kompilator adalah ketika Anda dapat menghosting kompiler sendiri dan "memakan makanan anjing Anda sendiri". Untuk alasan ini ketika Anda melihat bahasa seperti OCaml di mana mereka dirancang untuk penelitian bahasa, mereka cenderung memiliki fitur yang bagus untuk masalah tipe kompilator.

Dalam pekerjaan compiler-esque terakhir saya, kami menggunakan OCaml untuk alasan ini persis saat memanipulasi kode C, itu hanya alat terbaik untuk tugas itu. Jika orang-orang di INRIA telah membangun OCaml dengan prioritas yang berbeda, itu mungkin tidak cocok.

Meskipun demikian, bahasa fungsional adalah alat terbaik untuk memecahkan masalah apa pun, jadi secara logis dapat dikatakan bahwa bahasa fungsional adalah alat terbaik untuk memecahkan masalah khusus ini. QED.

/ me: merangkak kembali ke tugas Java saya sedikit kurang menyenangkan ...

Ukko
sumber
4
-1 untuk "bahasa fungsional adalah alat terbaik untuk memecahkan masalah apa pun." Jika ini benar, kita semua akan menggunakannya di mana-mana. ;)
Andrei Krotkov
15
@Andrei Krotkov: Kata hari ini adalah fa · ce · tious Pengucapan: \ fə-ˈsē-shəs \ Fungsi: kata sifat Etimologi: facetieux Perancis Tengah, dari lelucon facetie, dari facetia Latin Tanggal: 1599 1: bercanda atau sering bercanda dengan tidak tepat : waggish <just being jenaka> 2: dimaksudkan untuk menjadi jenaka atau lucu: tidak serius <a komentar jenaka> sinonim lihat jenaka Selain melewatkan lelucon, logika Anda masih cacat. Anda berasumsi bahwa semua orang adalah aktor rasional, dan saya khawatir, ini bukanlah asumsi yang adil.
Ukko
5
Saya rasa saya merindukan lelucon itu, karena saya tahu orang-orang dalam kehidupan nyata yang akan mengatakan hal yang persis sama, kecuali sepenuhnya serius. Hukum Poe, kurasa. tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw
Andrei Krotkov
13
@Andrei: Menggunakan argumentum ad populum Anda : "Jika alasan lebih baik daripada ketidaktahuan emosional, kita semua akan menggunakannya di mana-mana."
Tim Schaeffer
9

Pada dasarnya, kompiler adalah transformasi dari satu set kode ke kode lainnya - dari sumber ke IR, dari IR ke IR yang dioptimalkan, dari IR ke assembly, dll. Inilah tepatnya bahasa fungsional yang dirancang untuk - fungsi murni adalah hanya sebuah transformasi dari satu hal ke hal lainnya. Fungsi imperatif tidak memiliki kualitas ini. Meskipun Anda dapat menulis kode semacam ini dalam bahasa imperatif, bahasa fungsional dikhususkan untuk itu.

Membuang
sumber
6

Lihat juga

F # pola desain

FP mengelompokkan berbagai hal 'berdasarkan operasi', sedangkan OO mengelompokkan hal-hal 'menurut jenis', dan 'menurut operasi' lebih alami untuk kompiler / juru bahasa.

Brian
sumber
3
Ini berkaitan dengan apa yang disebut, di beberapa lingkungan Teori Bahasa Pemrograman, "masalah ekspresi". Misalnya, lihat pertanyaan ini , di mana saya mendemonstrasikan beberapa kode Haskell yang benar-benar mengerikan yang melakukan berbagai hal dengan cara "tipe yang dapat diperluas". Sebaliknya, memaksa bahasa OOP ke dalam gaya "operasi yang dapat diperluas" cenderung memotivasi Pola Pengunjung.
CA McCann
6

Salah satu kemungkinannya adalah kompilator cenderung harus menangani dengan sangat hati-hati sejumlah kasus sudut. Mendapatkan kode yang benar sering kali menjadi lebih mudah dengan menggunakan pola desain yang menyusun implementasi dengan cara yang paralel dengan aturan yang diimplementasikannya. Seringkali yang berakhir menjadi deklaratif (pencocokan pola, "di mana") daripada desain imperatif (pengurutan, "ketika") dan dengan demikian lebih mudah untuk diterapkan dalam bahasa deklaratif (dan sebagian besar berfungsi).

BCS
sumber
4

Sepertinya semua orang melewatkan alasan penting lainnya. Sangat mudah untuk menulis bahasa khusus domain tertanam (EDSL) untuk parser yang sangat mirip (E) BNF dalam kode normal. Kombinator pengurai seperti Parsec cukup mudah untuk menulis dalam bahasa fungsional menggunakan fungsi tingkat tinggi dan komposisi fungsi. Tidak hanya lebih mudah tetapi juga sangat elegan.

Pada dasarnya Anda mewakili parser generik paling sederhana hanya sebagai fungsi dan Anda memiliki operasi khusus (biasanya fungsi orde tinggi) yang memungkinkan Anda menyusun parser primitif ini menjadi parser yang lebih rumit dan lebih spesifik untuk tata bahasa Anda.

Ini bukan satu-satunya cara untuk melakukan kerangka kerja pengupas tentunya.

snk_kid
sumber