Apa artinya Weak Head Normal Form (WHNF)? Apa arti Head Normal form (HNF) dan Normal Form (NF)?

Negara Haskell Dunia Nyata :

Fungsi seq yang familier mengevaluasi ekspresi pada apa yang kita sebut head normal form (disingkat HNF). Ia berhenti begitu mencapai konstruktor terluar ("kepala"). Ini berbeda dari bentuk normal (NF), di mana ekspresi sepenuhnya dievaluasi.

Anda juga akan mendengar programmer Haskell merujuk pada bentuk kepala normal yang lemah (WHNF). Untuk data normal, bentuk normal kepala lemah sama dengan bentuk normal kepala. Perbedaannya hanya muncul untuk fungsi, dan terlalu sulit untuk diperhatikan di sini.

Saya telah membaca beberapa sumber dan definisi ( Haskell Wiki dan Haskell Mail List dan Kamus Gratis ) tetapi saya tidak mengerti. Bisakah seseorang memberi contoh atau memberikan definisi awam?

Saya kira ini akan mirip dengan:

WHNF = thunk : thunk

HNF = 0 : thunk 

NF = 0 : 1 : 2 : 3 : []

Bagaimana seqdan ($!)terkait dengan WHNF dan HNF?

Memperbarui

Saya masih bingung. Saya tahu beberapa jawaban mengatakan untuk mengabaikan HNF. Dari membaca berbagai definisi tampaknya tidak ada perbedaan antara data reguler di WHNF dan HNF. Namun, sepertinya ada perbedaan ketika datang ke suatu fungsi. Jika tidak ada perbedaan, mengapa seqperlu foldl'?

Titik kebingungan lainnya adalah dari Haskell Wiki, yang menyatakan bahwa seqmengurangi menjadi WHNF, dan tidak akan melakukan apa pun untuk contoh berikut. Kemudian mereka mengatakan bahwa mereka harus menggunakan sequntuk memaksa evaluasi. Apakah itu tidak memaksanya ke HNF?

Kode umum newbie stack meluap:

myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)

Orang-orang yang memahami bentuk kepala normal dan lemah kepala normal (whnf) dapat segera memahami apa yang salah di sini. (acc + x, len + 1) sudah ada di whnf, jadi seq, yang mengurangi nilai menjadi whnf, tidak melakukan apa-apa untuk ini. Kode ini akan membangun thunks seperti contoh foldl yang asli, mereka hanya akan berada di dalam tuple. Solusinya adalah dengan memaksa komponen tuple, misalnya

myAverage = uncurry (/) . foldl' 
          (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)

- Haskell Wiki di Stackoverflow

Saya akan mencoba memberikan penjelasan secara sederhana. Seperti yang telah ditunjukkan orang lain, bentuk normal kepala tidak berlaku untuk Haskell, jadi saya tidak akan mempertimbangkannya di sini.

Bentuk normal

Ekspresi dalam bentuk normal sepenuhnya dievaluasi, dan tidak ada sub-ekspresi yang dapat dievaluasi lebih lanjut (yaitu tidak mengandung thunks yang tidak dievaluasi).

Semua ungkapan ini dalam bentuk normal:

42
(2, "hello")
\x -> (x + 1)

Ungkapan-ungkapan ini tidak dalam bentuk normal:

1 + 2                 -- we could evaluate this to 3
(\x -> x + 1) 2       -- we could apply the function
"he" ++ "llo"         -- we could apply the (++)
(1 + 1, 2 + 2)        -- we could evaluate 1 + 1 and 2 + 2

Bentuk normal kepala lemah

Ekspresi dalam bentuk normal kepala lemah telah dievaluasi ke konstruktor data terluar atau abstraksi lambda ( kepala ). Sub-ekspresi mungkin atau mungkin belum dievaluasi . Oleh karena itu, setiap ekspresi bentuk normal juga dalam bentuk normal kepala lemah, meskipun sebaliknya tidak berlaku secara umum.

Untuk menentukan apakah suatu ekspresi dalam bentuk normal kepala lemah, kita hanya perlu melihat bagian terluar dari ekspresi itu. Jika itu adalah konstruktor data atau lambda, itu dalam bentuk normal kepala lemah. Jika itu adalah aplikasi fungsi, itu bukan.

Ekspresi ini dalam bentuk normal kepala lemah:

(1 + 1, 2 + 2)       -- the outermost part is the data constructor (,)
\x -> 2 + 2          -- the outermost part is a lambda abstraction
'h' : ("e" ++ "llo") -- the outermost part is the data constructor (:)

Seperti disebutkan, semua ekspresi bentuk normal yang tercantum di atas juga dalam bentuk normal kepala lemah.

Ungkapan-ungkapan ini tidak dalam bentuk normal kepala lemah:

1 + 2                -- the outermost part here is an application of (+)
(\x -> x + 1) 2      -- the outermost part is an application of (\x -> x + 1)
"he" ++ "llo"        -- the outermost part is an application of (++)

Stack overflow

Mengevaluasi ekspresi ke bentuk normal kepala lemah mungkin mengharuskan ekspresi lain dievaluasi ke WHNF terlebih dahulu. Misalnya, untuk mengevaluasi 1 + (2 + 3)ke WHNF, pertama-tama kita harus mengevaluasi 2 + 3. Jika mengevaluasi satu ekspresi mengarah ke terlalu banyak evaluasi bersarang ini, hasilnya adalah stack overflow.

Ini terjadi ketika Anda membangun ekspresi besar yang tidak menghasilkan konstruktor data atau lambdas sampai sebagian besar telah dievaluasi. Ini sering disebabkan oleh jenis penggunaan foldl:

foldl (+) 0 [1, 2, 3, 4, 5, 6]
 = foldl (+) (0 + 1) [2, 3, 4, 5, 6]
 = foldl (+) ((0 + 1) + 2) [3, 4, 5, 6]
 = foldl (+) (((0 + 1) + 2) + 3) [4, 5, 6]
 = foldl (+) ((((0 + 1) + 2) + 3) + 4) [5, 6]
 = foldl (+) (((((0 + 1) + 2) + 3) + 4) + 5) [6]
 = foldl (+) ((((((0 + 1) + 2) + 3) + 4) + 5) + 6) []
 = (((((0 + 1) + 2) + 3) + 4) + 5) + 6
 = ((((1 + 2) + 3) + 4) + 5) + 6
 = (((3 + 3) + 4) + 5) + 6
 = ((6 + 4) + 5) + 6
 = (10 + 5) + 6
 = 15 + 6
 = 21

Perhatikan bagaimana ia harus cukup dalam sebelum bisa membuat ekspresi menjadi bentuk normal kepala lemah.

Anda mungkin bertanya-tanya, mengapa Haskell tidak mengurangi ekspresi batin sebelumnya? Itu karena kemalasan Haskell. Karena tidak dapat diasumsikan secara umum bahwa setiap subekspresi akan diperlukan, ekspresi dievaluasi dari luar pada.

(GHC memiliki penganalisis ketelitian yang akan mendeteksi beberapa situasi di mana subekspresi selalu diperlukan dan kemudian dapat mengevaluasinya lebih awal. Namun ini hanya pengoptimalan, dan Anda tidak boleh bergantung padanya untuk menyelamatkan Anda dari luapan).

Ekspresi semacam ini, di sisi lain, benar-benar aman:

data List a = Cons a (List a) | Nil
foldr Cons Nil [1, 2, 3, 4, 5, 6]
 = Cons 1 (foldr Cons Nil [2, 3, 4, 5, 6])  -- Cons is a constructor, stop. 

Untuk menghindari pembangunan ekspresi besar ini ketika kita tahu semua subekspresi harus dievaluasi, kami ingin memaksa bagian dalam dievaluasi lebih dulu.

seq

seqadalah fungsi khusus yang digunakan untuk memaksa ekspresi dievaluasi. Semantiknya adalah bahwa seq x ysetiap kali ydievaluasi ke bentuk normal kepala lemah, xjuga dievaluasi untuk bentuk normal kepala lemah.

Ini adalah tempat lain yang digunakan dalam definisi foldl', varian ketat foldl.

foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

Setiap iterasi foldl'memaksa akumulator ke WHNF. Karena itu ia menghindari membangun ekspresi yang besar, dan karena itu menghindari tumpah tumpukan.

foldl' (+) 0 [1, 2, 3, 4, 5, 6]
 = foldl' (+) 1 [2, 3, 4, 5, 6]
 = foldl' (+) 3 [3, 4, 5, 6]
 = foldl' (+) 6 [4, 5, 6]
 = foldl' (+) 10 [5, 6]
 = foldl' (+) 15 [6]
 = foldl' (+) 21 []
 = 21                           -- 21 is a data constructor, stop.

Tetapi seperti contoh pada HaskellWiki menyebutkan, ini tidak menyelamatkan Anda dalam semua kasus, karena akumulator hanya dievaluasi ke WHNF. Dalam contoh tersebut, akumulator adalah tupel, sehingga hanya akan memaksa evaluasi konstruktor tupel, dan bukan accatau len.

f (acc, len) x = (acc + x, len + 1)

foldl' f (0, 0) [1, 2, 3]
 = foldl' f (0 + 1, 0 + 1) [2, 3]
 = foldl' f ((0 + 1) + 2, (0 + 1) + 1) [3]
 = foldl' f (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1) []
 = (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1)  -- tuple constructor, stop.

Untuk menghindari hal ini, kita harus membuatnya sehingga mengevaluasi kekuatan konstruktor tuple evaluasi accdan len. Kami melakukan ini dengan menggunakan seq.

f' (acc, len) x = let acc' = acc + x
                      len' = len + 1
                  in  acc' `seq` len' `seq` (acc', len')

foldl' f' (0, 0) [1, 2, 3]
 = foldl' f' (1, 1) [2, 3]
 = foldl' f' (3, 2) [3]
 = foldl' f' (6, 3) []
 = (6, 3)                    -- tuple constructor, stop.

Bagian tentang Bentuk Normal Thunks dan Weak Head dalam deskripsi haskell Wikibooks tentang kemalasan memberikan deskripsi WHNF yang sangat baik bersama dengan penggambaran yang bermanfaat ini:

Mengevaluasi nilai (4, [1, 2]) langkah demi langkah. Tahap pertama benar-benar tidak dievaluasi; semua bentuk selanjutnya dalam WHNF, dan yang terakhir juga dalam bentuk normal.

Program Haskell adalah ekspresi dan dijalankan dengan melakukan evaluasi .

Untuk mengevaluasi ekspresi, ganti semua aplikasi fungsi dengan definisinya. Urutan Anda melakukan ini tidak terlalu penting, tetapi tetap penting: mulai dengan aplikasi terluar dan lanjutkan dari kiri ke kanan; ini disebut evaluasi malas .

Contoh:

   take 1 (1:2:3:[])
=> { apply take }
   1 : take (1-1) (2:3:[])
=> { apply (-)  }
   1 : take 0 (2:3:[])
=> { apply take }
   1 : []

Evaluasi berhenti ketika tidak ada lagi aplikasi fungsi yang tersisa untuk diganti. Hasilnya dalam bentuk normal (atau bentuk normal tereduksi , RNF). Tidak masalah di mana urutan Anda mengevaluasi ekspresi, Anda akan selalu berakhir dengan bentuk normal yang sama (tetapi hanya jika evaluasi berakhir).

Ada deskripsi yang sedikit berbeda untuk evaluasi malas. Yaitu, ia mengatakan bahwa Anda harus mengevaluasi semuanya untuk bentuk normal kepala lemah saja. Ada tiga kasus untuk ekspresi di WHNF:

• Konstruktor: constructor expression_1 expression_2 ...
• Fungsi bawaan dengan terlalu sedikit argumen, seperti (+) 2atausqrt
• Ekspresi lambda: \x -> expression

Dengan kata lain, kepala ekspresi (yaitu aplikasi fungsi terluar) tidak dapat dievaluasi lebih lanjut, tetapi argumen fungsi dapat berisi ekspresi yang tidak dievaluasi.

Contoh WHNF:

3 : take 2 [2,3,4]   -- outermost function is a constructor (:)
(3+1) : [4..]        -- ditto
\x -> 4+5            -- lambda expression

Catatan

1. "Kepala" di WHNF tidak merujuk ke kepala daftar, tetapi ke aplikasi fungsi terluar.
2. Terkadang, orang menyebut ungkapan yang tidak dievaluasi sebagai "thunks", tapi saya rasa itu bukan cara yang baik untuk memahaminya.
3. Bentuk normal kepala (HNF) tidak relevan untuk Haskell. Ini berbeda dari WHNF di mana tubuh ekspresi lambda juga dievaluasi sampai batas tertentu.

Penjelasan yang baik dengan contoh diberikan di http://foldoc.org/Weak+Head+Normal+Form form normal menyederhanakan bahkan bit ekspresi di dalam abstraksi fungsi, sedangkan form normal head "lemah" berhenti pada abstraksi fungsi .

Dari sumbernya, jika Anda memiliki:

\ x -> ((\ y -> y+x) 2)

yang dalam bentuk normal kepala lemah, tetapi tidak dalam bentuk normal kepala ... karena aplikasi yang mungkin terjebak di dalam fungsi yang belum dapat dievaluasi.

Bentuk normal kepala aktual akan sulit diimplementasikan secara efisien. Itu akan membutuhkan menusuk di dalam fungsi. Jadi keuntungan dari bentuk normal kepala lemah adalah Anda masih dapat mengimplementasikan fungsi sebagai tipe buram, dan karenanya lebih kompatibel dengan bahasa yang dikompilasi dan optimisasi.

WHNF tidak ingin tubuh lambdas dievaluasi, jadi

WHNF = \a -> thunk
HNF = \a -> a + c

seq ingin argumen pertamanya berada di WHNF, jadi

let a = \b c d e -> (\f -> b + c + d + e + f) b
    b = a 2
in seq b (b 5)

mengevaluasi ke

\d e -> (\f -> 2 + 5 + d + e + f) 2

alih-alih, apa yang akan menggunakan HNF

\d e -> 2 + 5 + d + e + 2

Pada dasarnya, anggaplah Anda memiliki semacam pukulan t,.

Sekarang, jika kita ingin mengevaluasi tke WHNF atau NHF, yang sama kecuali untuk fungsi, kita akan menemukan bahwa kita mendapatkan sesuatu seperti

t1 : t2dimana t1dan t2adalah thunks. Dalam hal ini, t1akan menjadi Anda 0(atau lebih tepatnya, seorang thunk untuk 0tidak diberikan tambahan unboxing)

seqdan $!evaluasi WHNF. Catat itu

f $! x = seq x (f x)