Mengapa fungsi "tidak melakukan apa-apa" Haskell, id, menghabiskan banyak memori?

112

Haskell memiliki fungsi identitas yang mengembalikan masukan tanpa perubahan. Definisinya sederhana:

id :: a -> a
id x = x

Jadi untuk bersenang-senang, ini harus menghasilkan 8:

f = id id id id id id id id id id id id id id id id id id id id id id id id id id id
main = print $ f 8

Setelah beberapa detik (dan sekitar 2 gb memori menurut Pengelola Tugas), kompilasi gagal dengan ghc: out of memory. Demikian kata penerjemah ghci: out of memory.

Karena idini adalah fungsi yang cukup sederhana, saya tidak akan mengharapkannya menjadi beban memori pada saat menjalankan atau waktu kompilasi. Untuk apa semua memori digunakan?

haskell ghc Ryan
sumber
11
Anda ingin membuat ids itu. Dalam VIM, dengan kursor pada definisi f, lakukan ini: :s/id id/id . id ./g.
Tobias Brandt

Jawaban:

135

Kami tahu jenisnya id,

id :: a -> a

Dan ketika kami mengkhususkan ini untuk id id, salinan kiriid memiliki tipe:

id :: (a -> a) -> (a -> a)

Dan kemudian ketika Anda mengkhususkan ini lagi untuk yang paling kiri iddi id id id, Anda mendapatkan:

id :: ((a -> a) -> (a -> a)) -> ((a -> a) -> (a -> a))

Jadi Anda melihat setiap yang idAnda tambahkan, tanda tangan tipe paling kiri iddua kali lebih besar.

Perhatikan bahwa tipe dihapus selama kompilasi, jadi ini hanya akan menggunakan memori di GHC. Ini tidak akan memakan memori di program Anda.

Dietrich Epp
sumber
Saya ingat Okasaki mengalami masalah serupa ketika dia menulis kalkulator RPN yang disematkan di Haskell.
dfeuer
3
Pertanyaannya, mungkin, apakah GHC harus menemukan cara untuk menangani hal semacam ini dengan lebih anggun. Secara khusus, jenisnya sangat besar ketika ditulis secara penuh, tetapi ada banyak duplikasi — dapatkah berbagi digunakan untuk memampatkan hal-hal seperti itu? Apakah ada cara yang efisien untuk memprosesnya?
dfeuer
5
@dfeuer Coba tanyakan jenis ghci. Anda akan melihat dari kecepatan tanggapan bahwa ia harus melakukan pembagian yang sesuai. Saya menduga pembagian ini hilang - karena alasan yang jelas - setelah Anda menerjemahkan ke beberapa representasi perantara lainnya (misalnya inti).
Daniel Wagner
4
Artinya jika iddiulang nkali, maka spasi jenisnya sebanding dengan 2^n. Tipe yang disimpulkan dalam kode Ryan akan membutuhkan 2^27referensi ke variabel tipe selain struktur lain yang diperlukan untuk merepresentasikan tipe, yang mungkin jauh lebih besar daripada yang Anda harapkan dari kebanyakan tipe.
David
58
Melakukan inferensi tipe secara naif adalah eksponensial ganda, dengan cerdik menggunakan berbagi dalam ekspresi tipe Anda dapat menurunkannya menjadi eksponensial saja. Tapi tidak peduli apa yang Anda lakukan, akan ada beberapa ekspresi yang agak sederhana yang akan membuat pemeriksa tipe meledak. Untungnya, ini tidak terjadi dalam pemrograman praktis.
augustss