Apa poin keketatan Haskell?

Kita semua tahu (atau seharusnya tahu) bahwa Haskell malas secara default. Tidak ada yang dievaluasi sampai harus dievaluasi. Jadi, kapan sesuatu harus dievaluasi? Ada beberapa poin di mana Haskell harus tegas. Saya menyebutnya "titik-titik ketelitian", meskipun istilah khusus ini tidak seluas yang saya kira. Menurut saya:

Pengurangan (atau evaluasi) di Haskell hanya terjadi pada poin-poin yang ketat.

Jadi pertanyaannya adalah: apa, tepatnya , poin-poin keketatan Haskell? Intuisi saya mengatakan bahwa main, seq/ pola ledakan, pencocokan pola, dan IOtindakan apa pun yang dilakukan melalui mainadalah poin keketatan utama, tetapi saya tidak benar-benar tahu mengapa saya mengetahuinya.

(Juga, jika mereka tidak disebut "kekerasan poin", apa yang mereka sebut?)

Saya membayangkan jawaban yang bagus akan mencakup beberapa diskusi tentang WHNF dan seterusnya. Saya juga membayangkan itu mungkin menyentuh kalkulus lambda.

Edit: pemikiran tambahan tentang pertanyaan ini.

Saat saya merenungkan pertanyaan ini, saya pikir akan lebih jelas untuk menambahkan sesuatu pada definisi titik keketatan. Titik keketatan dapat memiliki konteks yang berbeda-beda dan kedalaman (atau keketatan) yang berbeda -beda . Kembali ke definisi saya bahwa "pengurangan Haskell hanya terjadi pada titik-titik pengetatan", mari kita tambahkan ke definisi tersebut klausul ini: "titik pengetatan hanya dipicu ketika konteks sekitarnya dievaluasi atau dikurangi."

Jadi, izinkan saya mencoba membantu Anda memulai dengan jenis jawaban yang saya inginkan. mainadalah poin yang ketat. Ini secara khusus ditetapkan sebagai titik ketelitian utama dari konteksnya: program. Ketika program ( mainkonteks) dievaluasi, titik keketatan main diaktifkan. Kedalaman induk maksimal: harus dievaluasi sepenuhnya. Utama biasanya terdiri dari tindakan IO, yang juga merupakan poin keketatan, yang konteksnya adalah main.

Sekarang Anda mencoba: mendiskusikan seqdan mencocokkan pola dalam istilah-istilah ini. Jelaskan nuansa aplikasi fungsi: bagaimana itu ketat? Bagaimana tidak Tentang apa deepseq? letdan casepernyataan? unsafePerformIO? Debug.Trace? Definisi tingkat atas? Tipe data yang ketat? Pola bang? Dll. Berapa banyak dari item ini yang dapat dijelaskan hanya dalam istilah pencocokan pola atau urutan?

Tempat yang baik untuk memulai adalah dengan memahami makalah ini: Semantik Alami untuk Evaluasi Malas (Launchbury). Itu akan memberi tahu Anda saat ekspresi dievaluasi untuk bahasa kecil yang mirip dengan Inti GHC. Kemudian pertanyaan yang tersisa adalah bagaimana memetakan Haskell ke Core, dan sebagian besar terjemahan itu diberikan oleh laporan Haskell itu sendiri. Dalam GHC kami menyebut proses ini "desugaring", karena menghilangkan gula sintaksis.

Nah, itu bukan keseluruhan cerita, karena GHC mencakup keseluruhan optimisasi antara desugaring dan pembuatan kode, dan banyak dari transformasi ini akan mengatur ulang Inti sehingga hal-hal dievaluasi pada waktu yang berbeda (analisis keketatan khususnya akan menyebabkan hal-hal dievaluasi. sebelumnya). Jadi untuk benar-benar memahami bagaimana program Anda akan dievaluasi, Anda perlu melihat Core yang dihasilkan oleh GHC.

Mungkin jawaban ini tampak agak abstrak bagi Anda (saya tidak secara khusus menyebutkan pola atau urutan ledakan), tetapi Anda meminta sesuatu yang tepat , dan inilah hal terbaik yang dapat kami lakukan.

Saya mungkin akan menyusun ulang pertanyaan ini sebagai, Dalam keadaan apa Haskell akan mengevaluasi ekspresi? (Mungkin menggunakan "bentuk normal kepala lemah".)

Untuk perkiraan pertama, kita dapat menentukannya sebagai berikut:

• Mengeksekusi tindakan IO akan mengevaluasi ekspresi apa pun yang "dibutuhkan". (Jadi Anda perlu tahu apakah aksi IO dijalankan, misalnya namanya main, atau dipanggil dari main DAN Anda perlu tahu apa yang dibutuhkan aksi.)
• Ekspresi yang sedang dievaluasi (hei, itu definisi rekursif!) Akan mengevaluasi ekspresi apa pun yang dibutuhkannya.

Dari daftar intuitif Anda, tindakan utama dan IO termasuk dalam kategori pertama, dan pencocokan urutan dan pola termasuk dalam kategori kedua. Tapi menurut saya kategori pertama lebih sejalan dengan gagasan Anda tentang "titik ketelitian", karena itulah sebenarnya cara kami menyebabkan evaluasi di Haskell menjadi efek yang dapat diamati bagi pengguna.

Memberikan semua detail secara spesifik adalah tugas yang besar, karena Haskell adalah bahasa yang besar. Ini juga cukup halus, karena Concurrent Haskell dapat mengevaluasi berbagai hal secara spekulatif, meskipun pada akhirnya kami tidak menggunakan hasilnya: ini adalah jenis ketiga dari hal-hal yang menyebabkan evaluasi. Kategori kedua dipelajari dengan cukup baik: Anda ingin melihat ketegasan fungsi yang terlibat. Kategori pertama juga dapat dianggap sebagai semacam "ketegasan", meskipun ini agak cerdik karena evaluate xdan seq x $ return ()sebenarnya adalah hal yang berbeda! Anda dapat memperlakukannya dengan benar jika Anda memberikan semacam semantik ke IO monad (secara eksplisit meneruskan RealWorld#token berfungsi untuk kasus sederhana), tetapi saya tidak tahu apakah ada nama untuk jenis analisis keketatan berlapis ini secara umum.

C memiliki konsep titik urutan , yang menjamin untuk operasi tertentu bahwa satu operan akan dievaluasi sebelum operan lainnya. Saya pikir itu adalah konsep terdekat yang ada, tetapi istilah keketatan istilah yang pada dasarnya setara (atau mungkin titik kekuatan ) lebih sejalan dengan pemikiran Haskell.

Dalam praktiknya, Haskell bukanlah bahasa yang murni malas: misalnya pencocokan pola biasanya ketat (Jadi, mencoba pola pencocokan akan memaksa evaluasi terjadi setidaknya cukup jauh untuk menerima atau menolak kecocokan.

…

Pemrogram juga dapat menggunakan seqprimitif untuk memaksa ekspresi dievaluasi terlepas dari apakah hasilnya akan digunakan.

$!didefinisikan dalam istilah seq.

- Malas vs. tidak ketat .

Jadi pemikiran Anda tentang !/ $!dan seqpada dasarnya benar, tetapi pencocokan pola tunduk pada aturan yang lebih halus. Anda selalu bisa menggunakan ~untuk memaksa pencocokan pola malas, tentu saja. Hal menarik dari artikel yang sama itu:

Penganalisis keketatan juga mencari kasus di mana sub-ekspresi selalu dibutuhkan oleh ekspresi luar, dan mengubahnya menjadi evaluasi yang bersemangat. Hal ini dapat dilakukan karena semantik (dalam istilah "bawah") tidak berubah.

Mari lanjutkan ke lubang kelinci dan lihat dokumen untuk pengoptimalan yang dilakukan oleh GHC:

Analisis keketatan adalah proses dimana GHC mencoba untuk menentukan, pada waktu kompilasi, data mana yang pasti akan 'selalu dibutuhkan'. GHC kemudian dapat membuat kode untuk hanya menghitung data tersebut, daripada proses normal (overhead yang lebih tinggi) untuk menyimpan penghitungan dan menjalankannya nanti.

- Optimasi GHC: Analisis Ketat .

Dengan kata lain, kode ketat dapat dibuat di mana saja sebagai pengoptimalan, karena pembuatan thunk tidak perlu mahal ketika data akan selalu dibutuhkan (dan / atau hanya dapat digunakan sekali).

… Tidak ada lagi evaluasi yang dapat dilakukan terhadap nilai; itu dikatakan dalam bentuk normal . Jika kita berada di salah satu langkah perantara sehingga kita telah melakukan setidaknya beberapa evaluasi pada suatu nilai, itu dalam bentuk normal kepala lemah (WHNF). (Ada juga 'head normal form', tapi tidak digunakan di Haskell.) Mengevaluasi sepenuhnya sesuatu di WHNF akan menguranginya menjadi sesuatu dalam bentuk normal…

- Wikibooks Haskell: Kemalasan

(Sebuah istilah dalam bentuk normal head jika tidak ada beta-redex di posisi head ^1. Sebuah redex adalah head redex jika hanya didahului oleh lambda abstractors dari non-redexes ^2. ) Jadi, saat Anda mulai memaksa thunk, Anda bekerja di WHNF; ketika tidak ada lagi halangan yang tersisa untuk dipaksakan, Anda berada dalam kondisi normal. Hal menarik lainnya:

… Jika pada titik tertentu kami perlu, katakanlah, mencetak z ke pengguna, kami perlu mengevaluasinya sepenuhnya…

Yang secara alami menyiratkan bahwa, memang, setiap IOtindakan yang dilakukan dari main melakukan evaluasi paksa, yang seharusnya jelas mengingat bahwa program Haskell memang melakukan sesuatu. Apa pun yang perlu melalui urutan yang ditentukan mainharus dalam bentuk normal dan oleh karena itu tunduk pada evaluasi yang ketat.

CA McCann benar dalam komentarnya, meskipun: satu-satunya hal yang istimewa mainadalah yang maindidefinisikan sebagai khusus; pencocokan pola pada konstruktor cukup untuk memastikan urutan yang ditentukan oleh IOmonad. Dalam hal itu saja seqdan pencocokan pola adalah hal yang mendasar.

Haskell adalah AFAIK bukan bahasa malas murni, melainkan bahasa yang tidak ketat. Ini berarti bahwa ia tidak selalu mengevaluasi istilah-istilah pada saat-saat terakhir yang memungkinkan.

Sumber yang baik untuk model haskell tentang "kemalasan" dapat ditemukan di sini: http://en.wikibooks.org/wiki/Haskell/Laziness

Pada dasarnya, penting untuk memahami perbedaan antara bentuk normal WHNF thunk dan header lemah.

Pemahaman saya adalah bahwa haskell menarik komputasi melalui mundur dibandingkan dengan bahasa imperatif. Artinya adalah bahwa dengan tidak adanya "seq" dan pola bang, pada akhirnya akan menjadi semacam efek samping yang memaksa evaluasi dari sebuah thunk, yang dapat menyebabkan evaluasi sebelumnya pada gilirannya (benar-benar malas).

Karena hal ini akan menyebabkan kebocoran ruang yang mengerikan, penyusun kemudian mencari tahu bagaimana dan kapan harus mengevaluasi potongan sebelumnya untuk menghemat ruang. Programmer kemudian dapat mendukung proses ini dengan memberikan anotasi keketatan (en.wikibooks.org/wiki/Haskell/Strictness, www.haskell.org/haskellwiki/Performance/Strictness) untuk lebih mengurangi penggunaan ruang dalam bentuk tumpukan bertingkat.

Saya bukan ahli dalam semantik operasional haskell, jadi saya akan meninggalkan tautan sebagai sumber daya.

Beberapa sumber daya lainnya:

http://www.haskell.org/haskellwiki/Performance/Laziness

http://www.haskell.org/haskellwiki/Haskell/Lazy_Evaluation

Malas bukan berarti tidak melakukan apa-apa. Kapanpun pola program Anda cocok dengan caseekspresi, itu mengevaluasi sesuatu - toh cukup. Jika tidak, RHS tidak dapat digunakan. Tidak melihat ekspresi kasus apa pun dalam kode Anda? Jangan khawatir, kompiler sedang menerjemahkan kode Anda ke bentuk Haskell yang dipreteli di mana mereka sulit untuk menghindari penggunaannya.

Untuk pemula, aturan dasarnya letadalah malas, casekurang malas.

Ini bukanlah jawaban lengkap yang bertujuan untuk karma, tetapi hanya sepotong teka-teki - sejauh ini tentang semantik, ingatlah bahwa ada beberapa strategi evaluasi yang memberikan semantik yang sama . Salah satu contoh bagus di sini - dan proyek juga menunjukkan bagaimana kita biasanya memikirkan semantik Haskell - adalah proyek Eager Haskell, yang secara radikal mengubah strategi evaluasi sambil mempertahankan semantik yang sama: http://csg.csail.mit.edu/ pubs / haskell.html

Kompiler Glasgow Haskell menerjemahkan kode Anda ke dalam bahasa mirip kalkulus Lambda yang disebut inti . Dalam bahasa ini, sesuatu akan dievaluasi, setiap kali Anda mencocokkannya dengan pola case-statement. Jadi jika suatu fungsi dipanggil, konstruktor terluar dan hanya itu (jika tidak ada bidang paksa) yang akan dievaluasi. Ada lagi yang dikalengkan dalam sekejap. (Thunks diperkenalkan oleh letbinding).

Tentu saja ini tidak persis seperti yang terjadi dalam bahasa aslinya. Kompiler mengubah Haskell menjadi Core dengan cara yang sangat canggih, membuat sebanyak mungkin hal menjadi malas dan apapun yang selalu dibutuhkan menjadi malas. Selain itu, ada nilai tanpa kotak dan tupel yang selalu ketat.

Jika Anda mencoba mengevaluasi suatu fungsi dengan tangan, pada dasarnya Anda dapat berpikir:

• Cobalah untuk mengevaluasi konstruktor terluar dari pengembalian.
• Jika ada hal lain yang diperlukan untuk mendapatkan hasil (tetapi hanya jika itu benar-benar dibutuhkan) juga akan dievaluasi. Urutan tidak penting.
• Dalam kasus IO, Anda harus mengevaluasi hasil dari semua pernyataan dari yang pertama hingga yang terakhir. Ini sedikit lebih rumit, karena IO monad melakukan beberapa trik untuk memaksa evaluasi dalam urutan tertentu.