Qu'est-ce que la Faiblesse de la Tête Forme Normale?

Je vais essayer de donner une explication en termes simples. Comme d'autres l'ont souligné, la tête forme normale ne s'applique pas à Haskell, je ne vais pas examiner ici.

Forme normale

Une expression de la forme normale est pleinement évalués, et pas de sous-expression pourrait être évaluées plus en détail (c'est à dire qu'il ne contient aucune des nations unies-évalué thunks).

Ces expressions sont toutes de la forme normale:

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

Ces expressions ne sont pas en forme normale:

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

La faiblesse de la tête à la forme normale de

Une expression de la faiblesse de la tête à la forme normale a été évalué à l'ultrapériphériques données constructeur ou lambda abstraction (la tête). Les sous-expressions peut ou peut ne pas avoir été évalué. Par conséquent, chaque forme normale d'expression est aussi dans la faiblesse de la tête à la forme normale, bien que l'inverse ne tient pas en général.

Pour déterminer si une expression est dans la faiblesse de la tête à la forme normale, nous n'avons qu'à regarder la partie la plus extérieure de l'expression. Si c'est une des données du constructeur ou d'un lambda, c'est dans la faiblesse de la tête à la forme normale. Si c'est une fonction de l'application, il n'est pas.

Ces expressions sont dans la faiblesse de la tête forme normale:

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

Comme mentionné précédemment, toutes de la forme normale des expressions ci-dessus sont aussi dans la faiblesse de la tête à la forme normale.

Ces expressions ne sont pas dans la faiblesse de la tête forme normale:

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

Débordements de pile

L'évaluation d'une expression à la faiblesse de la tête forme normale peut exiger que d'autres expressions être évalué à WHNF premier. Par exemple, pour évaluer 1 + (2 + 3) à WHNF, nous devons d'abord évaluer 2 + 3. Si l'évaluation d'une expression unique conduit à un trop grand nombre de ces imbriqués les évaluations, le résultat est un débordement de pile.

Ce qui se passe quand vous construire une grande expression qui ne produisent pas de toutes les données constructeurs ou des lambdas jusqu'à ce qu'une grande partie de cela a été évaluée. Ce sont souvent causés par ce genre d'utilisation de 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

Remarquez comment il doit aller assez profond avant de pouvoir obtenir l'expression dans la faiblesse de la tête à la forme normale.

Vous pouvez vous demander, pourquoi ne pas Haskell réduire l'intérieur des expressions à l'avance? C'est à cause de Haskell paresse. Puisqu'il ne peut être supposé que, en général, chaque sous-expression sera nécessaire, les expressions sont évaluées à partir de l'extérieur.

(GHC a une rigueur de l'analyseur qui permet de détecter certaines situations où une sous-expression est toujours nécessaire, et il peut alors évaluer à l'avance. Ce n'est qu'une optimisation, cependant, et vous ne devriez pas compter sur elle pour vous sauver de débordements).

Ce genre d'expression, d'autre part, est tout à fait sûr:

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. 

Pour éviter la construction de ces expressions de grande taille quand on sait toutes les sous-expressions devront être évalués, nous voulons forcer les parties intérieures être évalué à l'avance.

seq

seq est une fonction spéciale qui est utilisée pour forcer les expressions à évaluer. Sa sémantique est que seq x y signifie que chaque fois que y est évaluée à la faiblesse de la tête à la forme normale, x est également évaluée à la faiblesse de la tête à la forme normale.

Il est entre autres utilisé dans la définition de foldl', la stricte variante de foldl.

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

Chaque itération de foldl' les forces de l'accumulateur à WHNF. Il permet donc d'éviter la constitution d'une importante expression, et il permet donc d'éviter les débordement de la pile.

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.

Mais comme l'exemple sur HaskellWiki mentionne, il ne vous fait pas gagner dans tous les cas, que l'accumulateur est seulement évaluée à WHNF. Dans l'exemple, l'accumulateur est un n-uplet, donc il ne force l'évaluation de la n-uplet constructeur, et pas acc ou 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.

Pour éviter cela, nous devons faire en sorte que l'évaluation de la n-uplet constructeur forces de l'évaluation de acc et len. Nous faisons cela en utilisant 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.

Haskell programmes sont expressions et ils sont gérés par l'exécution évaluation.

Pour évaluer une expression, remplacer toutes les applications de fonctions par leurs définitions. L'ordre dans lequel vous faites cela n'importe pas beaucoup, mais il est toujours important: commencez avec la plus externe de l'application et de procéder de gauche à droite; cela s'appelle évaluation différée.

Exemple:

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

L'évaluation s'arrête lorsqu'il n'y a plus de fonction des applications de gauche à remplacer. Le résultat est dans forme normale (ou réduit à la forme normale de, FRR). Peu importe l'ordre dans lequel vous évaluer une expression, vous vous retrouvez toujours avec la même forme normale (mais seulement si l'évaluation se termine).

Est légèrement différente de la description de l'évaluation différée. À savoir, il est dit que vous devez évaluer tout à la faiblesse de la tête à la forme normale de seulement. Il y a précisément trois cas pour une expression dans WHNF:

• Constructeur: constructor expression_1 expression_2 ...
• Une fonction intégrée avec trop peu d'arguments, comme (+) 2 ou sqrt
• Une lambda-expression: \x -> expression

En d'autres termes, le chef de l'expression (c'est à dire de l'extérieur de la fonction de demande) ne peut pas être évaluées plus en détail, mais l'argument de fonction peut contenir des expressions non évaluées.

Exemples de WHNF:

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

---

Notes

1. La "tête" dans WHNF ne se réfère pas à la tête d'une liste, mais pour l'extérieur de la fonction de demande.
2. Parfois, les gens l'appellent non évaluée expressions "bits", mais je ne pense pas que c'est une bonne façon de le comprendre.
3. Tête à la forme normale de (HNF) n'est pas pertinente pour Haskell. Il diffère de WHNF en ce que le corps de la lambda expressions sont également évalués dans une certaine mesure.

La WHNF ne voulez pas que le corps de la lambda pour être évaluées,

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

seq veut que son premier argument en WHNF, donc

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

évalue à

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

au lieu de, ce serait en utilisant HNF

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