Mengapa bahasa pemrograman fungsional memerlukan pengumpulan sampah?

14

Apa yang menghentikan ghc dari menerjemahkan Haskell ke dalam bahasa pemrograman concatenative seperti logika kombinasi dan kemudian hanya menggunakan alokasi stack untuk semuanya? Menurut Wikipedia, terjemahan dari lambda kalkulus ke logika kombinasi adalah sepele, dan juga, bahasa pemrograman concatenative hanya dapat mengandalkan tumpukan untuk alokasi memori. Apakah layak untuk melakukan terjemahan ini dan dengan demikian menghilangkan pengumpulan sampah untuk bahasa seperti Haskell dan ocaml? Apakah ada kerugian untuk melakukan ini?

EDIT: pindah ke sini /programming/39440412/why-do-functional-programming-languages-require-garbage-collection

functional-programming haskell Nicholas Grasevski
sumber
The Cat Bahasa Pemrograman terlihat seperti contoh fungsi, bahasa berbasis stack.
Petr Pudlák
1
Ini bukan pertanyaan tingkat penelitian, karena pengumpulan sampah tercakup dalam kursus sarjana tentang bahasa pemrograman (serta kebutuhan untuk itu). Silakan pindah ke cs.stackexchange.com
Andrej Bauer
Kesalahanku. Apakah Anda tahu jawaban untuk pertanyaan saya?
Nicholas Grasevski
5
Saya pikir ada beberapa respon tingkat penelitian yang diberikan untuk pertanyaan ini, karena saya ingat berjuang dengan itu selama tahun-tahun pascasarjana saya juga: segala sesuatu dalam bahasa seperti Haskell terlihat seperti aplikasi fungsi, yang hidup di tumpukan. Saya pikir menjelaskan mengapa penutupan diperlukan, mengapa mereka hidup di heap, dan mungkin apa "data yang keluar dari lingkup fungsi" harus dilakukan dengan itu akan membuat jawaban yang sangat informatif (yang saya tidak yakin saya memenuhi syarat untuk memberi, sayangnya).
cody
2
λ

Jawaban:

16

Semua komentar berikut didasarkan pada pilihan strategi implementasi standar menggunakan penutupan untuk mewakili nilai fungsi dan urutan evaluasi panggilan-oleh-nilai:

  1. Untuk kalkulus lambda murni, pengumpulan sampah tidak perlu. Ini karena tidak mungkin untuk membentuk siklus di heap: setiap nilai yang baru dialokasikan hanya dapat berisi referensi ke nilai yang sebelumnya dialokasikan, dan grafik memori membentuk DAG - jadi penghitungan referensi cukup untuk mengelola memori.

  2. Sebagian besar implementasi tidak menggunakan penghitungan referensi karena dua alasan.

    1. Mereka mendukung bentuk tipe pointer (misalnya, refkonstruktor tipe dalam ML), dan siklus yang benar dalam tumpukan dapat dibentuk.
    2. Penghitungan referensi jauh lebih efisien daripada pengumpulan sampah, karena
      • itu membutuhkan banyak ruang tambahan untuk menjaga jumlah referensi, dan
      • memperbarui hitungan biasanya sia-sia, dan
      • pembaruan untuk penghitungan membuat banyak pertikaian penulisan yang membunuh kinerja paralel.

  3. Bahasa yang diketik secara linier dapat menghilangkan jumlah referensi (pada dasarnya karena jumlah adalah 0-1: nilai memiliki referensi tunggal atau mati dan dapat dibebaskan).

  4. Namun, alokasi tumpukan masih tidak cukup. Ini karena dimungkinkan untuk membentuk nilai fungsi yang merujuk ke variabel bebas (yaitu, kita perlu menerapkan penutupan fungsi), jika Anda mengalokasikan hal-hal pada stack, maka nilai langsung dapat disisipkan dengan nilai mati, dan ini akan menyebabkan asimptotik yang salah penggunaan ruang.

  5. Anda bisa mendapatkan asimptotik yang tepat dengan mengganti tumpukan dengan "tumpukan spageti" (yaitu, menerapkan tumpukan sebagai daftar tertaut di tumpukan, sehingga Anda dapat memotong kerangka mati sesuai kebutuhan).

  6. Jika Anda ingin disiplin stack nyata, Anda dapat menggunakan sistem tipe berdasarkan "logika yang dipesan" (dasarnya tipe linear minus pertukaran).

Neel Krishnaswami
sumber
2
Bukankah alasan yang lebih mendasar untuk (2) bahwa - bahkan tanpa efek samping yang dapat diamati - implementasi ingin memiliki operator yang efisien untuk rekursi (mutual), yaitu, yang benar-benar membentuk siklus di heap?
Andreas Rossberg
@ andreasrossberg: Saya berpikir tentang menyebutkan itu, tetapi tinggalkan karena Anda dapat menggunakan kombinator y untuk rekursi.
Neel Krishnaswami