Was ist Schwachkopf Normalform?

290

Was bedeutet Weak Head Normal Form (WHNF)? Was bedeutet Leiter Normalform (HNF) und Normalform (NF) bedeuten?

In der realen Welt sagt Haskell :

Die bekannte seq-Funktion wertet einen Ausdruck in der sogenannten Kopfnormalform (abgekürzt HNF) aus. Es stoppt, sobald es den äußersten Konstruktor (den „Kopf“) erreicht. Dies unterscheidet sich von der Normalform (NF), bei der ein Ausdruck vollständig ausgewertet wird.

Sie werden auch hören, wie Haskell-Programmierer sich auf die Normalform des schwachen Kopfes (WHNF) beziehen. Bei normalen Daten entspricht die schwache Kopfnormalform der Kopfnormalform. Der Unterschied ergibt sich nur für Funktionen und ist zu abstrus, um uns hier zu beschäftigen.

Ich habe einige Ressourcen und Definitionen gelesen ( Haskell Wiki und Haskell Mail List und Free Dictionary ), aber ich verstehe es nicht. Kann jemand vielleicht ein Beispiel geben oder eine Laiendefinition liefern?

Ich vermute, es wäre ähnlich wie:

WHNF = thunk : thunk

HNF = 0 : thunk 

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

Wie macht seq und ($!)beziehen sich auf WHNF und HNF?

Aktualisieren

Ich bin immer noch verwirrt. Ich weiß, dass einige der Antworten besagen, HNF zu ignorieren. Aus dem Lesen der verschiedenen Definitionen geht hervor, dass es keinen Unterschied zwischen regulären Daten in WHNF und HNF gibt. Es scheint jedoch einen Unterschied zu geben, wenn es um eine Funktion geht. Wenn es keinen Unterschied gab, warum?seq notwendig für foldl'?

Ein weiterer Punkt der Verwirrung stammt aus dem Haskell-Wiki, das besagt, dass es seqsich auf WHNF reduziert und dem folgenden Beispiel nichts antut. Dann sagen sie, dass sie verwenden müssenseq , um die Bewertung zu erzwingen. Erzwingt das nicht HNF?

Häufiger Code für überlaufende Neulinge:

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

Menschen, die seq und schwache Kopfnormalform (whnf) verstehen, können sofort verstehen, was hier schief geht. (acc + x, len + 1) ist bereits in whnf, daher tut seq, das einen Wert auf whnf reduziert, nichts dagegen. Dieser Code baut Thunks auf, genau wie das ursprüngliche Foldl-Beispiel, sie befinden sich nur in einem Tupel. Die Lösung besteht nur darin, die Komponenten des Tupels zu erzwingen, z

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

- Haskell Wiki auf Stackoverflow

Micha Wiedenmann
quelle
1
Im Allgemeinen sprechen wir von WHNF und RNF. (RNF ist das, was Sie NF nennen)
Alternative
5
@monadic Wofür steht das R in RNF?
Dave4420
7
@ Dave4420: Reduziert
Marc

Antworten:

399

Ich werde versuchen, eine Erklärung in einfachen Worten zu geben. Wie andere bereits betont haben, gilt die normale Kopfform nicht für Haskell, daher werde ich sie hier nicht berücksichtigen.

Normalform

Ein Ausdruck in normaler Form wird vollständig ausgewertet, und es kann kein Unterausdruck weiter ausgewertet werden (dh er enthält keine nicht ausgewerteten Thunks).

Diese Ausdrücke sind alle in normaler Form:

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

Diese Ausdrücke sind nicht in normaler Form:

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

Normale Form des schwachen Kopfes

Ein Ausdruck in schwacher Kopfnormalform wurde für den äußersten Datenkonstruktor oder die Lambda-Abstraktion (den Kopf ) ausgewertet . Unterausdrücke können ausgewertet worden sein oder nicht . Daher liegt jeder Ausdruck in normaler Form auch in normaler Form mit schwachem Kopf vor, obwohl das Gegenteil im Allgemeinen nicht zutrifft.

Um festzustellen, ob ein Ausdruck eine schwache Kopfnormalform hat, müssen wir nur den äußersten Teil des Ausdrucks betrachten. Wenn es sich um einen Datenkonstruktor oder ein Lambda handelt, liegt die normale Kopfform vor. Wenn es sich um eine Funktionsanwendung handelt, ist dies nicht der Fall.

Diese Ausdrücke sind in schwacher Kopfnormalform:

(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 (:)

Wie bereits erwähnt, liegen alle oben aufgeführten Normalformausdrücke auch in schwacher Kopfnormalform vor.

Diese Ausdrücke haben keine schwache Kopfnormalform:

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 (++)

Stapel läuft über

Das Auswerten eines Ausdrucks in eine normale Form mit schwachem Kopf kann erfordern, dass andere Ausdrücke zuerst in WHNF ausgewertet werden. Um beispielsweise 1 + (2 + 3)WHNF zu bewerten , müssen wir zuerst bewerten2 + 3 . Wenn die Auswertung eines einzelnen Ausdrucks zu zu vielen dieser verschachtelten Auswertungen führt, ist das Ergebnis ein Stapelüberlauf.

Dies geschieht, wenn Sie einen großen Ausdruck erstellen, der keine Datenkonstruktoren oder Lambdas erzeugt, bis ein großer Teil davon ausgewertet wurde. Diese werden häufig durch diese Art der Verwendung von Folgendem verursacht 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

Beachten Sie, dass es ziemlich tief gehen muss, bevor es den Ausdruck in eine normale Form mit schwachem Kopf bringen kann.

Sie fragen sich vielleicht, warum Haskell die inneren Ausdrücke nicht im Voraus reduziert? Das liegt an Haskells Faulheit. Da generell nicht davon ausgegangen werden kann, dass jeder Unterausdruck benötigt wird, werden Ausdrücke von außen nach innen ausgewertet.

(GHC verfügt über einen Strenge-Analysator, der einige Situationen erkennt, in denen immer ein Unterausdruck erforderlich ist, und dieser dann vorab auswerten kann. Dies ist jedoch nur eine Optimierung, und Sie sollten sich nicht darauf verlassen, um Überläufe zu vermeiden.)

Diese Art des Ausdrucks ist dagegen völlig sicher:

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. 

Um zu vermeiden, dass diese großen Ausdrücke erstellt werden, wenn wir wissen, dass alle Unterausdrücke ausgewertet werden müssen, möchten wir die Auswertung der inneren Teile im Voraus erzwingen.

seq

seqist eine spezielle Funktion, mit der die Auswertung von Ausdrücken erzwungen wird. Seine Semantik seq x ybedeutet, dass jedes Mal, wenn yes als schwache Kopfnormalform bewertet wird, auch als schwache Kopfnormalform bewertet xwird.

Es wird unter anderem in der Definition von verwendet foldl' der strengen Variante von verwendet foldl.

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

Jede Iteration von foldl' zwingt den Akkumulator zu WHNF. Es wird daher vermieden, einen großen Ausdruck aufzubauen, und es wird daher ein Überlaufen des Stapels vermieden.

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.

Wie im Beispiel in HaskellWiki erwähnt, werden Sie dadurch nicht in allen Fällen gerettet, da der Akkumulator nur für WHNF ausgewertet wird. In diesem Beispiel ist der Akkumulator ein Tupel, sodass nur die Auswertung des Tupelkonstruktors erzwungen wird und nichtacc oder 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.

Um dies zu vermeiden, müssen wir dafür sorgen, dass die Auswertung des Tupelkonstruktors die Auswertung von accund erzwingt len. Wir tun dies mit 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.
Hammar
quelle
31
Die normale Kopfform erfordert, dass auch der Körper eines Lambda reduziert wird, während die schwache normale Kopfform diese Anforderung nicht erfüllt. So \x -> 1 + 1ist WHNF aber nicht HNF.
Hammar
Wikipedia gibt an, dass HNF "[a] Begriff ist in normaler Kopfform, wenn sich kein Beta-Redex in Kopfposition befindet". Ist Haskell "schwach", weil es keine Beta-Redex-Unterausdrücke gibt?
Wie kommen strenge Datenkonstruktoren ins Spiel? Sind sie nur so, als würden sie seqihre Argumente anrufen ?
Bergi
1
@CaptainObvious: 1 + 2 ist weder NF noch WHNF. Ausdrücke sind nicht immer in normaler Form.
Hammar
2
@Zorobay: Um das Ergebnis zu drucken, wertet GHCi den Ausdruck vollständig in NF aus, nicht nur in WHNF. Eine Möglichkeit, den Unterschied zwischen den beiden Varianten zu erkennen, besteht darin, Speicherstatistiken mit zu aktivieren :set +s. Sie können dann sehen, dass foldl' fam Ende mehr Thunks als zugewiesen werdenfoldl' f' .
Hammar
43

Der Abschnitt über Thunks und Schwachkopf-Normalform in der Beschreibung von Faulheit in Haskell Wikibooks enthält eine sehr gute Beschreibung von WHNF zusammen mit dieser hilfreichen Darstellung:

Schritt für Schritt den Wert (4, [1, 2]) auswerten.  Die erste Stufe ist völlig unbewertet;  Alle nachfolgenden Formen sind in WHNF und die letzte ist auch in normaler Form.

Schritt für Schritt den Wert (4, [1, 2]) auswerten. Die erste Stufe ist völlig unbewertet; Alle nachfolgenden Formen sind in WHNF und die letzte ist auch in normaler Form.

aculich
quelle
5
Ich weiß, dass Leute sagen, sie sollen die normale Kopfform ignorieren, aber können Sie in diesem Diagramm ein Beispiel geben, wie eine normale Kopfform aussieht?
CMCDragonkai
28

Haskell-Programme sind Ausdrücke und werden durch Ausführen einer Auswertung ausgeführt .

Um einen Ausdruck auszuwerten, ersetzen Sie alle Funktionsanwendungen durch ihre Definitionen. Die Reihenfolge, in der Sie dies tun, spielt keine große Rolle, ist aber dennoch wichtig: Beginnen Sie mit der äußersten Anwendung und fahren Sie von links nach rechts fort. Dies wird als verzögerte Bewertung bezeichnet .

Beispiel:

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

Die Auswertung wird beendet, wenn keine Funktionsanwendungen mehr zu ersetzen sind. Das Ergebnis ist in normaler Form (oder in reduzierter normaler Form) , RNF). Unabhängig davon, in welcher Reihenfolge Sie einen Ausdruck auswerten, erhalten Sie immer dieselbe normale Form (jedoch nur, wenn die Auswertung endet).

Es gibt eine etwas andere Beschreibung für die verzögerte Bewertung. Es heißt nämlich, dass Sie alles nur auf schwache Kopfnormalform bewerten sollten . Es gibt genau drei Fälle, in denen sich ein Ausdruck in WHNF befindet:

  • Ein Konstruktor: constructor expression_1 expression_2 ...
  • Eine eingebaute Funktion mit zu wenigen Argumenten wie (+) 2odersqrt
  • Ein Lambda-Ausdruck: \x -> expression

Mit anderen Worten, der Kopf des Ausdrucks (dh die äußerste Funktionsanwendung) kann nicht weiter ausgewertet werden, aber das Funktionsargument kann nicht bewertete Ausdrücke enthalten.

Beispiele für WHNF:

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

Anmerkungen

  1. Der "Kopf" in WHNF bezieht sich nicht auf den Kopf einer Liste, sondern auf die äußerste Funktionsanwendung.
  2. Manchmal nennen die Leute nicht bewertete Ausdrücke "Thunks", aber ich denke nicht, dass dies ein guter Weg ist, dies zu verstehen.
  3. Die Kopfnormalform (HNF) ist für Haskell irrelevant. Es unterscheidet sich von WHNF darin, dass die Körper von Lambda-Ausdrücken in gewissem Umfang auch bewertet werden.
Heinrich Apfelmus
quelle
Ist die Bewertung von WHNF zu HNF seqin foldl'Kraft?
1
@snmcdonald: Nein, Haskell nutzt HNF nicht. Durch Auswerten seq expr1 expr2wird der erste Ausdruck expr1für WHNF ausgewertet , bevor der zweite Ausdruck ausgewertet wird expr2.
Heinrich Apfelmus
26

Eine gute Erklärung mit Beispielen finden Sie unter http://foldoc.org/Weak+Head+Normal+Form. Die Kopfnormalform vereinfacht sogar die Bits eines Ausdrucks innerhalb einer Funktionsabstraktion, während die "schwache" Kopfnormalform bei Funktionsabstraktionen stoppt .

Aus der Quelle, wenn Sie haben:

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

das ist in schwacher Kopfnormalform, aber nicht in Kopfnormalform ... weil die mögliche Anwendung in einer Funktion steckt, die noch nicht ausgewertet werden kann.

Die tatsächliche Kopfnormalform wäre schwierig effizient umzusetzen. Es würde erfordern, innerhalb von Funktionen herumzustöbern. Der Vorteil einer normalen Form mit schwachem Kopf besteht also darin, dass Sie Funktionen weiterhin als undurchsichtigen Typ implementieren können und daher besser mit kompilierten Sprachen und Optimierungen kompatibel sind.

Chris Smith
quelle
12

Der WHNF möchte nicht, dass der Lambdas-Körper bewertet wird

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

seq will, dass sein erstes Argument in WHNF ist, also

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

bewertet zu

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

stattdessen, was würde HNF verwenden

\d e -> 2 + 5 + d + e + 2
marc
quelle
Oder ich verstehe das Beispiel falsch oder Sie mischen 1 und 2 in WHNF und HNF.
Zhen
5

Nehmen wir im Grunde an, Sie haben eine Art Thunk t.

Wenn wir tnun WHNF oder NHF bewerten möchten, die bis auf Funktionen gleich sind, würden wir feststellen, dass wir so etwas bekommen

t1 : t2wo t1und t2sind thunks. In diesem Fall t1wäre Ihr 0(oder besser gesagt ein Thunk, 0kein zusätzliches Unboxing zu geben)

seqund $!WHNF bewerten. Beachten Sie, dass

f $! x = seq x (f x)
Alternative
quelle
1
@snmcdonald HNF ignorieren. seq sagt, dass, wenn dies zu WHNF ausgewertet wird, das erste Argument zu WHNF ausgewertet wird.
Alternative