Haskell · conceitos · avaliação

A avaliação lazy em Haskell, explicada

A maioria das linguagens é strict: uma expressão é avaliada assim que é ligada a um nome. O Haskell é diferente — é lazy (mais precisamente não strict) por defeito: uma expressão não é avaliada enquanto o seu resultado não for verdadeiramente necessário. Esta única decisão de design está por trás de alguns dos poderes mais distintivos do Haskell e da sua armadilha mais notória. Este guia explica o que é a avaliação lazy, como funcionam os thunks, o que ela lhe dá e como a desativar quando preciso.

A ideia numa frase

Sob a avaliação lazy, ligar um valor não o calcula — o Haskell guarda um cálculo diferido (um thunk) e só o força quando outro cálculo exige o resultado. Se o resultado nunca for exigido, o trabalho nunca é feito.

Thunks: o cálculo diferido

Quando escreve let x = expensive 42, o Haskell não executa expensive. Cria um thunk — uma promessa não avaliada de expensive 42. O thunk só é forçado quando algo precisa do valor real de x (por exemplo, imprimi-lo ou fazer pattern matching sobre ele). Force-o uma vez, e o resultado é colocado em cache para não ser recalculado.

let x = expensive 42   -- nothing runs yet; x is a thunk
let y = x + 1          -- still nothing; y is a thunk too
print y                -- NOW x and y are forced and evaluated

O que a lazyness lhe dá

• Estruturas de dados infinitas. [1..] é a lista infinita dos inteiros. take 5 [1..] devolve [1,2,3,4,5] porque apenas os primeiros cinco são alguma vez exigidos.
• Composição sem desperdício. Pode encadear filter e map sobre uma lista enorme e o Haskell funde o trabalho, produzindo apenas o que o consumidor puxa — sem listas intermédias completas se nunca forem inteiramente exigidas.
• Curto-circuito grátis. False && undefined devolve False sem nunca tocar em undefined, porque o segundo argumento nunca é forçado.
• Auto-referência. One-liners clássicos como fibs = 0 : 1 : zipWith (+) fibs (tail fibs) definem o fluxo infinito de Fibonacci — possível apenas porque a estrutura é construída de forma lazy.

A armadilha: as fugas de memória

A lazyness tem um custo. Os thunks não avaliados acumulam-se em memória, e uma longa cadeia de cálculos diferidos pode inflar silenciosamente o uso da heap — uma fuga de memória (space leak). O caso de manual é uma fold à esquerda lazy que constrói uma torre gigante de thunks (((0 + 1) + 2) + 3) ... em vez de somar à medida que avança:

foldl (+) 0 [1..1000000]    -- builds a million thunks, may blow the stack
foldl' (+) 0 [1..1000000]   -- strict fold: adds as it goes, constant space

A solução é forçar a avaliação onde importa. Recorra à fold à esquerda strict foldl' (de Data.List) para as acumulações.

Forçar a strictness: seq, $! e BangPatterns

O Haskell dá-lhe ferramentas precisas para exigir a avaliação:

• seq a b — força a para a forma normal fraca de cabeça antes de devolver b.
• ($!) — aplicação strict: f $! x força x antes de aplicar f.
• BangPatterns — a extensão {-# LANGUAGE BangPatterns #-} deixa-o escrever let !x = ... para forçar uma ligação.

Uma subtileza a conhecer: forçar atinge tipicamente a forma normal fraca de cabeça (o construtor mais externo), não a avaliação completa. Para forçar em profundidade, use force / deepseq do pacote deepseq.

FAQ

O Haskell é lazy ou não strict? Tecnicamente não strict (uma garantia semântica); o GHC implementa-o através da avaliação lazy com thunks e partilha. Na prática diz-se « lazy ».

Porque é que o meu programa Haskell usa tanta memória? Muitas vezes uma fuga de memória devido a thunks acumulados — habitualmente um foldl lazy. Mude para foldl' ou adicione strictness com seq/BangPatterns.

O que é um thunk? Um cálculo não avaliado e diferido guardado no lugar de um valor, forçado apenas quando o valor é exigido, e depois colocado em cache.

A lazyness torna o Haskell lento? Não intrinsecamente — pode evitar trabalho desnecessário e permitir a fusão. Mas uma lazyness descuidada causa fugas de memória; saber quando forçar faz parte de escrever bom Haskell.

A lazyness é o mesmo mecanismo que faz com que as outras abstrações do Haskell se componham de forma limpa — veja como funciona a sequenciação no nosso guia sobre as monads em Haskell, e configure a toolchain para experimentar estes exemplos em GHCi com o guia do compilador GHC.