Apakah Haskell membutuhkan pengumpul sampah?

Saya ingin tahu mengapa implementasi Haskell menggunakan GC.

Saya tidak dapat memikirkan kasus di mana GC akan diperlukan dalam bahasa yang murni. Apakah ini hanya pengoptimalan untuk mengurangi penyalinan, atau memang perlu?

Saya mencari contoh kode yang akan bocor jika GC tidak ada.

Seperti orang lain telah menunjukkan, Haskell membutuhkan otomatis , dinamis manajemen memori: manajemen memori otomatis diperlukan karena manajemen memori manual tidak aman; manajemen memori dinamis diperlukan karena untuk beberapa program, masa pakai suatu objek hanya dapat ditentukan saat runtime.

Misalnya, pertimbangkan program berikut:

main = loop (Just [1..1000]) where
  loop :: Maybe [Int] -> IO ()
  loop obj = do
    print obj
    resp <- getLine
    if resp == "clear"
     then loop Nothing
     else loop obj

Dalam program ini, daftar [1..1000]harus disimpan dalam memori sampai pengguna mengetik "jelas"; jadi masa hidup ini harus ditentukan secara dinamis, dan inilah mengapa manajemen memori dinamis diperlukan.

Jadi dalam pengertian ini, alokasi memori dinamis otomatis diperlukan, dan dalam praktiknya ini berarti: ya , Haskell memerlukan pengumpul sampah, karena pengumpulan sampah adalah pengelola memori dinamis otomatis berkinerja tertinggi.

Namun...

Meskipun pengumpul sampah diperlukan, kita mungkin mencoba menemukan beberapa kasus khusus di mana kompilator dapat menggunakan skema pengelolaan memori yang lebih murah daripada pengumpulan sampah. Misalnya, diberikan

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

kita mungkin berharap compiler untuk mendeteksi bahwa x2dapat dengan aman dibatalkan alokasinya ketika fkembali (daripada menunggu pengumpul sampah untuk membatalkan alokasi x2). Pada dasarnya, kami meminta compiler melakukan analisis escape untuk mengonversi alokasi menjadi heap yang dikumpulkan sampah menjadi alokasi pada stack jika memungkinkan.

Ini tidak terlalu tidak beralasan untuk ditanyakan: kompilator haskell jhc melakukan ini, meskipun GHC tidak melakukannya. Kata Simon Marlow bahwa pengumpul sampah generasi GHC membuat analisis pelarian sebagian besar tidak diperlukan.

jhc sebenarnya menggunakan bentuk analisis melarikan diri yang canggih yang dikenal sebagai inferensi wilayah . Mempertimbangkan

f :: Integer -> (Integer, Integer)
f x = let x2 = x * x in (x2, x2+1)

g :: Integer -> Integer
g x = case f x of (y, z) -> y + z

Dalam kasus ini, analisis pelolosan sederhana akan menyimpulkan bahwa x2pelarian dari f(karena dikembalikan dalam tupel), dan karenanya x2harus dialokasikan pada heap yang dikumpulkan sampah. Wilayah inferensi, di sisi lain, mampu mendeteksi yang x2dapat dibatalkan alokasinya ketika gkembali; idenya di sini adalah bahwa x2harus dialokasikan di gdaerah daripada fdi daerah.

Di luar Haskell

Meskipun inferensi wilayah berguna dalam kasus tertentu seperti yang didiskusikan di atas, tampaknya sulit untuk menyesuaikan secara efektif dengan evaluasi malas (lihat komentar Edward Kmett dan Simon Peyton Jones ). Misalnya, pertimbangkan

f :: Integer -> Integer
f n = product [1..n]

Seseorang mungkin tergoda untuk mengalokasikan daftar [1..n]di stack dan membatalkan alokasinya setelah fdikembalikan, tetapi ini akan menjadi bencana besar: ini akan berubah fdari menggunakan memori O (1) (di bawah pengumpulan sampah) ke memori O (n).

Pekerjaan ekstensif dilakukan pada 1990-an dan awal 2000-an pada inferensi wilayah untuk ML bahasa fungsional yang ketat . Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg telah menulis retrospektif yang cukup dapat dibaca tentang pekerjaan mereka pada inferensi wilayah, yang sebagian besar diintegrasikan ke dalam kompiler MLKit . Mereka bereksperimen dengan manajemen memori berbasis wilayah murni (yaitu tanpa pengumpul sampah) serta manajemen memori berbasis wilayah hybrid / pengumpulan sampah, dan melaporkan bahwa program pengujian mereka berjalan "antara 10 kali lebih cepat dan 4 kali lebih lambat" daripada sampah murni- versi yang dikumpulkan.

Mari kita ambil contoh yang sepele. Mengingat ini

f (x, y)

Anda perlu mengalokasikan pasangan di (x, y)suatu tempat sebelum menelepon f. Kapan Anda dapat membatalkan alokasi pasangan itu? Anda tidak tahu. Itu tidak dapat dialokasikan ketika fkembali, karena fmungkin telah menempatkan pasangan dalam struktur data (misalnya, f p = [p]), sehingga masa pakai pasangan mungkin harus lebih lama daripada saat kembali dari f. Sekarang, katakanlah pasangan itu dimasukkan ke dalam daftar, dapatkah siapa pun yang mengambil daftar itu secara terpisah membatalkan alokasi pasangan? Tidak, karena pasangan mungkin dibagi (misalnya let p = (x, y) in (f p, p)). Jadi sangat sulit untuk mengetahui kapan pasangan dapat dibatalkan alokasinya.

Hal yang sama berlaku untuk hampir semua alokasi di Haskell. Meskipun demikian, mungkin ada analisis (analisis wilayah) yang memberikan batas atas masa pakai. Ini berfungsi cukup baik dalam bahasa yang ketat, tetapi tidak terlalu baik dalam bahasa lazy (bahasa lazy cenderung melakukan lebih banyak mutasi daripada bahasa ketat dalam implementasinya).

Jadi saya ingin membalik pertanyaan itu. Menurut Anda mengapa Haskell tidak membutuhkan GC. Bagaimana Anda menyarankan alokasi memori dilakukan?

Intuisi Anda bahwa ini ada hubungannya dengan kemurnian ada benarnya.

Haskell dianggap murni sebagian karena efek samping fungsi diperhitungkan dalam tanda tangan tipe. Jadi jika suatu fungsi memiliki efek samping mencetak sesuatu, harus adaIO tempat dalam tipe kembaliannya.

Tapi ada fungsi yang digunakan secara implisit di mana-mana di Haskell dan yang jenis tanda tangannya tidak diperhitungkan, dalam arti tertentu, efek samping. Yaitu fungsi yang menyalin beberapa data dan memberi Anda dua versi kembali. Di bawah tenda, ini dapat bekerja baik secara harfiah, dengan menduplikasi data dalam memori, atau 'secara virtual' dengan meningkatkan hutang yang harus dibayar kembali nanti.

Anda dapat merancang bahasa dengan sistem jenis yang lebih ketat (murni "linier") yang melarang fungsi salin. Dari sudut pandang seorang programmer dalam bahasa seperti itu, Haskell terlihat sedikit tidak murni.

Faktanya, Clean , kerabat Haskell, memiliki tipe linier (lebih tepatnya: unik), dan itu dapat memberi gambaran tentang bagaimana rasanya melarang penyalinan. Namun, Bersihkan tetap memungkinkan penyalinan untuk jenis "tidak unik".

Ada banyak penelitian di bidang ini dan jika Anda cukup Google, Anda akan menemukan contoh kode linier murni yang tidak memerlukan pengumpulan sampah. Anda akan menemukan semua jenis sistem tipe yang dapat memberi sinyal kepada kompilator memori apa yang mungkin digunakan yang memungkinkan kompilator untuk menghilangkan beberapa GC.

Ada perasaan di mana algoritma kuantum juga murni linier. Setiap operasi dapat dibalik sehingga tidak ada data yang dapat dibuat, disalin , atau dihancurkan. (Mereka juga linier dalam pengertian matematika biasa.)

Menarik juga untuk membandingkan dengan Forth (atau bahasa berbasis stack lainnya) yang memiliki operasi DUP eksplisit yang memperjelas saat duplikasi terjadi.

Cara berpikir lain (yang lebih abstrak) tentang hal ini adalah dengan mencatat bahwa Haskell dibangun dari kalkulus lambda yang diketik sederhana yang didasarkan pada teori kategori tertutup kartesian dan bahwa kategori tersebut dilengkapi dengan fungsi diagonal diag :: X -> (X, X). Bahasa berdasarkan kelas kategori lain mungkin tidak memiliki hal seperti itu.

Tetapi secara umum, pemrograman linier murni terlalu sulit untuk digunakan, jadi kami menerima GC.

Teknik implementasi standar yang diterapkan pada Haskell sebenarnya membutuhkan GC lebih banyak daripada kebanyakan bahasa lain, karena mereka tidak pernah mengubah nilai sebelumnya, sebagai gantinya membuat nilai baru yang dimodifikasi berdasarkan yang sebelumnya. Karena ini berarti program terus mengalokasikan dan menggunakan lebih banyak memori, sejumlah besar nilai akan dibuang seiring berjalannya waktu.

Inilah sebabnya mengapa program GHC cenderung memiliki angka alokasi total yang tinggi (dari gigabyte hingga terabyte): mereka terus-menerus mengalokasikan memori, dan hanya berkat GC yang efisien mereka mendapatkannya kembali sebelum kehabisan.

Jika suatu bahasa (bahasa apa pun) memungkinkan Anda untuk mengalokasikan objek secara dinamis, maka ada tiga cara praktis untuk menangani manajemen memori:

1. Bahasa ini hanya memungkinkan Anda mengalokasikan memori pada stack, atau saat startup. Tetapi pembatasan ini sangat membatasi jenis komputasi yang dapat dilakukan oleh program. (Dalam praktiknya. Dalam teori, Anda dapat meniru struktur data dinamis di (katakanlah) Fortran dengan merepresentasikannya dalam array besar. HORRIBLE ... dan tidak relevan dengan diskusi ini.)

2. Bahasa dapat memberikan mekanisme freeatau eksplisit dispose. Tapi ini bergantung pada programmer untuk melakukannya dengan benar. Setiap kesalahan dalam manajemen penyimpanan dapat mengakibatkan kebocoran memori ... atau lebih buruk lagi.

3. Bahasa (atau lebih tepatnya, implementasi bahasa) dapat menyediakan pengelola penyimpanan otomatis untuk penyimpanan yang dialokasikan secara dinamis; yaitu beberapa bentuk pengumpul sampah.

Satu-satunya pilihan lain adalah jangan pernah mengklaim kembali penyimpanan yang dialokasikan secara dinamis. Ini bukan solusi praktis, kecuali untuk program kecil yang melakukan komputasi kecil.

Menerapkan ini ke Haskell, bahasanya tidak memiliki batasan 1., dan tidak ada operasi pembatalan alokasi manual sesuai 2. Oleh karena itu, agar dapat digunakan untuk hal-hal yang tidak sepele, implementasi Haskell perlu menyertakan pengumpul sampah .

Saya tidak dapat memikirkan kasus di mana GC akan diperlukan dalam bahasa yang murni.

Mungkin yang Anda maksud adalah bahasa fungsional murni.

Jawabannya adalah bahwa GC diperlukan di balik terpal untuk mendapatkan kembali objek heap yang HARUS dibuat oleh bahasa. Sebagai contoh.

• Fungsi murni perlu membuat objek heap karena dalam beberapa kasus ia harus mengembalikannya. Itu berarti mereka tidak dapat dialokasikan di tumpukan.

• Fakta bahwa bisa ada siklus (dihasilkan dari let recmisalnya) berarti bahwa pendekatan penghitungan referensi tidak akan berfungsi untuk objek heap.

• Lalu ada penutupan fungsi ... yang juga tidak dapat dialokasikan pada tumpukan karena mereka memiliki masa hidup yang (biasanya) tidak tergantung pada bingkai tumpukan tempat mereka dibuat.

Saya mencari contoh kode yang akan bocor jika GC tidak ada.

Hampir semua contoh yang melibatkan penutupan atau struktur data berbentuk grafik akan bocor dalam kondisi tersebut.

Pengumpul sampah tidak pernah diperlukan, asalkan Anda memiliki memori yang cukup. Namun pada kenyataannya, kita tidak memiliki memori yang tidak terbatas, sehingga diperlukan beberapa metode untuk mendapatkan kembali memori yang tidak lagi diperlukan. Dalam bahasa tidak murni seperti C, Anda dapat secara eksplisit menyatakan Anda telah selesai dengan beberapa memori untuk membebaskannya - tetapi ini adalah operasi mutasi (memori yang baru saja Anda bebaskan tidak lagi aman untuk dibaca), jadi Anda tidak dapat menggunakan pendekatan ini dalam bahasa yang murni. Jadi entah bagaimana menganalisis secara statis di mana Anda dapat membebaskan memori (mungkin tidak mungkin dalam kasus umum), membocorkan memori seperti saringan (berfungsi dengan baik sampai Anda habis), atau menggunakan GC.

GC adalah "harus memiliki" dalam bahasa FP murni. Mengapa? Alokasi operasi dan gratis tidak murni! Dan alasan kedua adalah, bahwa struktur data rekursif yang tidak dapat diubah membutuhkan GC untuk keberadaannya karena tautan balik menciptakan struktur yang muskil dan tidak dapat dipertahankan untuk pikiran manusia. Tentu saja, backlinking adalah berkah, karena menyalin struktur yang menggunakannya sangat murah.

Bagaimanapun, Jika Anda tidak mempercayai saya, coba terapkan bahasa FP dan Anda akan melihat bahwa saya benar.

EDIT: Saya lupa. Kemalasan adalah NERAKA tanpa GC. Tidak percaya padaku Coba saja tanpa GC di, misalnya, C ++. Anda akan melihat ... banyak hal

Haskell adalah bahasa pemrograman yang tidak ketat, tetapi sebagian besar implementasi menggunakan panggilan sesuai kebutuhan (kemalasan) untuk mengimplementasikan non-ketat. Dalam call-by-need, Anda hanya mengevaluasi barang ketika tercapai selama runtime menggunakan mesin "thunks" (ekspresi yang menunggu untuk dievaluasi dan kemudian menimpa dirinya sendiri, tetap terlihat agar nilainya dapat digunakan kembali saat diperlukan).

Jadi, jika Anda mengimplementasikan bahasa Anda secara malas menggunakan thunks, Anda telah menangguhkan semua alasan tentang masa pakai objek hingga saat terakhir, yaitu waktu proses. Karena Anda sekarang tidak tahu apa-apa tentang masa hidup, satu-satunya hal yang dapat Anda lakukan adalah mengumpulkan sampah ...