O que significa o formulário normal de cabeça fraca (WHNF)? O que significa Forma Normal da Cabeça (HNF) e Forma Normal (NF)?

O mundo real Haskell afirma:

A função seq familiar avalia uma expressão para o que chamamos de forma normal da cabeça (HNF abreviado). Ele para quando atinge o construtor mais externo (a “cabeça”). Isso é diferente da forma normal (NF), na qual uma expressão é completamente avaliada.

Você também ouvirá os programadores Haskell se referirem à forma normal da cabeça fraca (WHNF). Para dados normais, a forma normal da cabeça fraca é igual à forma normal da cabeça. A diferença surge apenas para funções e é muito obscura para nos interessar aqui.

Eu li alguns recursos e definições ( Haskell Wiki e Haskell lista de correio e livre do dicionário ), mas eu não consegui-lo. Alguém pode dar um exemplo ou fornecer uma definição de leigo?

Eu estou supondo que seria semelhante a:

WHNF = thunk : thunk

HNF = 0 : thunk 

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

Como seqe se ($!)relacionam com WHNF e HNF?

Atualizar

Eu ainda estou confuso. Eu sei que algumas das respostas dizem para ignorar HNF. Ao ler as várias definições, parece que não há diferença entre os dados regulares no WHNF e no HNF. No entanto, parece que há uma diferença quando se trata de uma função. Se não houve diferença, por que é seqnecessário foldl'?

Outro ponto de confusão é o da Haskell Wiki, que afirma que se seqreduz ao WHNF e não fará nada no exemplo a seguir. Então eles dizem que precisam usar seqpara forçar a avaliação. Isso não está forçando o HNF?

Código transbordante de pilha de novato comum:

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

Pessoas que entendem seq e cabeça normal (whnf) podem entender imediatamente o que está errado aqui. (acc + x, len + 1) já está em whnf, portanto, seq, que reduz um valor a whnf, não faz nada para isso. Esse código criará thunks exatamente como no exemplo dobrável original, eles estarão dentro de uma tupla. A solução é apenas forçar os componentes da tupla, por exemplo,

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

- Wiki de Haskell no Stackoverflow

Vou tentar dar uma explicação em termos simples. Como outros já apontaram, a forma normal da cabeça não se aplica a Haskell, então não a considerarei aqui.

Forma normal

Uma expressão na forma normal é totalmente avaliada e nenhuma subexpressão pode ser avaliada mais (ou seja, não contém thunks não avaliados).

Essas expressões estão todas na forma normal:

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

Essas expressões não estão na forma 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

Forma normal de cabeça fraca

Uma expressão na forma normal de cabeça fraca foi avaliada para o construtor de dados mais externo ou a abstração lambda (a cabeça ). As subexpressões podem ou não ter sido avaliadas . Portanto, toda expressão de forma normal também está na forma normal de cabeça fraca, embora o oposto não seja válido em geral.

Para determinar se uma expressão está na forma normal de cabeça fraca, precisamos apenas observar a parte mais externa da expressão. Se é um construtor de dados ou um lambda, está na forma normal de cabeça fraca. Se é um aplicativo de função, não é.

Essas expressões estão na forma normal de cabeça fraca:

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

Como mencionado, todas as expressões de forma normal listadas acima também estão na forma normal de cabeça fraca.

Essas expressões não estão na forma normal de cabeça fraca:

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

Estouros de pilha

A avaliação de uma expressão para a forma normal de cabeça fraca pode exigir que outras expressões sejam avaliadas primeiro pelo WHNF. Por exemplo, para avaliar o 1 + (2 + 3)WHNF, primeiro precisamos avaliar 2 + 3. Se a avaliação de uma única expressão levar a muitas dessas avaliações aninhadas, o resultado será um estouro de pilha.

Isso acontece quando você constrói uma expressão grande que não produz nenhum construtor de dados ou lambdas até que uma grande parte dela tenha sido avaliada. Isso geralmente é causado por esse tipo de uso 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

Observe como ele precisa se aprofundar bastante antes de conseguir expressar a expressão na forma normal da cabeça fraca.

Você pode se perguntar: por que Haskell não reduz as expressões internas antes do tempo? Isso é por causa da preguiça de Haskell. Como não se pode presumir em geral que toda subexpressão será necessária, as expressões são avaliadas de fora para dentro.

(O GHC possui um analisador de rigidez que detecta algumas situações em que uma subexpressão é sempre necessária e pode avaliá-la antes do tempo. Entretanto, isso é apenas uma otimização e você não deve contar com isso para evitar transbordamentos).

Este tipo de expressão, por outro lado, é completamente seguro:

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. 

Para evitar a construção dessas grandes expressões quando sabemos que todas as subexpressões terão que ser avaliadas, queremos forçar as partes internas a serem avaliadas com antecedência.

seq

seqé uma função especial usada para forçar expressões a serem avaliadas. Sua semântica é que seq x ysignifica que sempre que yé avaliada para a forma normal da cabeça fraca, xtambém é avaliada para a forma normal da cabeça fraca.

Está entre outros lugares usados ​​na definição de foldl', a variante estrita de foldl.

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

Cada iteração foldl'força o acumulador ao WHNF. Portanto, evita construir uma expressão grande e, portanto, evita o transbordamento da pilha.

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.

Porém, como o exemplo do HaskellWiki menciona, isso não salva você em todos os casos, pois o acumulador é avaliado apenas como WHNF. No exemplo, o acumulador é uma tupla, portanto, forçará apenas a avaliação do construtor da tupla, e não accou 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.

Para evitar isso, devemos fazer com que a avaliação do construtor da tupla force a avaliação de acce len. Fazemos isso usando 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.

A seção sobre a forma normal de Thunks e Weak Head na descrição de preguiça de Haskell Wikibooks fornece uma descrição muito boa do WHNF junto com esta descrição útil:

Avaliando o valor (4, [1, 2]) passo a passo. O primeiro estágio é completamente não avaliado; todos os formulários subseqüentes estão no WHNF e o último também está no formato normal.

Os programas Haskell são expressões e são executados através da avaliação .

Para avaliar uma expressão, substitua todos os aplicativos de função por suas definições. A ordem em que você faz isso não importa muito, mas ainda é importante: comece com o aplicativo mais externo e prossiga da esquerda para a direita; isso é chamado de avaliação preguiçosa .

Exemplo:

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

A avaliação é interrompida quando não há mais aplicativos de funções a serem substituídos. O resultado está na forma normal (ou na forma normal reduzida , RNF). Não importa em que ordem você avalie uma expressão, você sempre terminará com a mesma forma normal (mas somente se a avaliação terminar).

Há uma descrição ligeiramente diferente para avaliação lenta. Ou seja, ele diz que você deve avaliar tudo apenas para a forma normal da cabeça fraca . Existem precisamente três casos para uma expressão estar no WHNF:

• Um construtor: constructor expression_1 expression_2 ...
• Uma função interna com muito poucos argumentos, como (+) 2ousqrt
• Uma expressão lambda: \x -> expression

Em outras palavras, o cabeçalho da expressão (ou seja, o aplicativo da função mais externa) não pode mais ser avaliado, mas o argumento da função pode conter expressões não avaliadas.

Exemplos de WHNF:

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

Notas

1. O "cabeçalho" no WHNF não se refere ao cabeçalho de uma lista, mas ao aplicativo de função mais externo.
2. Às vezes, as pessoas chamam expressões não avaliadas de "thunks", mas não acho que seja uma boa maneira de entender isso.
3. A forma normal da cabeça (HNF) é irrelevante para Haskell. Difere do WHNF pelo fato de os corpos das expressões lambda também serem avaliados até certo ponto.

Uma boa explicação com exemplos é dada em http://foldoc.org/Weak+Head+Normal+Form A forma normal do cabeçalho simplifica até os bits de uma expressão dentro de uma abstração de função, enquanto a forma normal do cabeçote "fraco" para nas abstrações de funções .

Da fonte, se você tiver:

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

que está na forma normal da cabeça fraca, mas não na forma normal da cabeça ... porque a possível aplicação está presa dentro de uma função que ainda não pode ser avaliada.

A forma normal da cabeça real seria difícil de implementar com eficiência. Seria necessário bisbilhotar dentro das funções. Portanto, a vantagem da forma normal de cabeça fraca é que você ainda pode implementar funções como um tipo opaco e, portanto, é mais compatível com linguagens compiladas e otimização.

O WHNF não deseja que o corpo de lambdas seja avaliado, portanto

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

seq quer que seu primeiro argumento esteja no WHNF, então

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

avalia como

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

em vez de, o que estaria usando HNF

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

Basicamente, suponha que você tenha algum tipo de thunk t,.

Agora, se quisermos avaliar tpara WHNF ou NHF, que são os mesmos, exceto para funções, descobriríamos que obtemos algo como

t1 : t2onde t1e t2são thunks. Nesse caso, t1seria o seu 0(ou melhor, um thunk para 0não receber unboxing extra)

seqe $!avaliar WHNF. Observe que

f $! x = seq x (f x)