Haskell requer um coletor de lixo?

118

Estou curioso para saber por que as implementações de Haskell usam um GC.

Não consigo pensar em um caso em que o GC seria necessário em uma linguagem pura. É apenas uma otimização para reduzir as cópias ou é realmente necessário?

Estou procurando por exemplo de código que vazaria se um GC não estivesse presente.

Pubby
fonte
14
Você pode achar esta série esclarecedora; abrange como o lixo é gerado (e subsequentemente coletado): blog.ezyang.com/2011/04/the-haskell-heap
Tom Crockett
5
existem referências por toda parte em línguas puras! apenas referências não mutáveis .
Tom Crockett
1
@pelotom Referências a dados imutáveis ​​ou referências imutáveis?
Pubby
3
Ambos. O fato de os dados referidos serem imutáveis ​​decorre do fato de que todas as referências são imutáveis, até o fim.
Tom Crockett,
4
Você certamente se interessará pelo problema da parada , pois a aplicação desse raciocínio à alocação de memória ajuda a entender por que a desalocação não pode ser prevista estaticamente no caso geral . No entanto, existem alguns programas para os quais a desalocação pode ser prevista, assim como alguns programas que podem ser encerrados sem realmente executá-los.
Paul R

Respostas:

218

Como outros já observaram, Haskell requer automático , dinâmico gerenciamento memória: o gerenciamento automático de memória é necessário porque o gerenciamento manual de memória não é seguro; o gerenciamento de memória dinâmica é necessário porque, para alguns programas, o tempo de vida de um objeto só pode ser determinado em tempo de execução.

Por exemplo, considere o seguinte programa:

main = loop (Just [1..1000]) where
  loop :: Maybe [Int] -> IO ()
  loop obj = do
    print obj
    resp <- getLine
    if resp == "clear"
     then loop Nothing
     else loop obj

Neste programa, a lista [1..1000]deve ser mantida na memória até que o usuário digite "limpar"; portanto, o tempo de vida disso deve ser determinado dinamicamente e é por isso que o gerenciamento de memória dinâmico é necessário.

Portanto, nesse sentido, a alocação de memória dinâmica automatizada é necessária e, na prática, isso significa: sim , Haskell requer um coletor de lixo, já que a coleta de lixo é o gerenciador automático de memória dinâmica de mais alto desempenho.

Contudo...

Embora um coletor de lixo seja necessário, podemos tentar encontrar alguns casos especiais em que o compilador pode usar um esquema de gerenciamento de memória mais barato do que a coleta de lixo. Por exemplo, dado

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

podemos esperar que o compilador detecte o que x2pode ser desalocado com segurança quando fretornar (em vez de esperar que o coletor de lixo seja desalocado x2). Essencialmente, estamos pedindo que o compilador execute uma análise de escape para converter as alocações em heap coletado pelo lixo para alocações na pilha sempre que possível.

Não é muito razoável perguntar: o compilador haskell jhc faz isso, embora o GHC não. Simon Marlow diz que o coletor de lixo geracional do GHC torna a análise de fuga quase desnecessária.

A jhc realmente usa uma forma sofisticada de análise de escape conhecida como inferência de região . Considerar

f :: Integer -> (Integer, Integer)
f x = let x2 = x * x in (x2, x2+1)

g :: Integer -> Integer
g x = case f x of (y, z) -> y + z

Nesse caso, uma análise de escape simplista concluiria que x2escapa de f(porque é retornado na tupla) e, portanto, x2deve ser alocado no heap coletado pelo lixo. A inferência de região, por outro lado, é capaz de detectar que x2pode ser desalocada quando gretorna; a ideia aqui é que x2deva ser alocado na gregião de e não fna região de.

Além de Haskell

Embora a inferência de região seja útil em certos casos, conforme discutido acima, parece ser difícil conciliar efetivamente com a avaliação preguiçosa (veja os comentários de Edward Kmett e Simon Peyton Jones ). Por exemplo, considere

f :: Integer -> Integer
f n = product [1..n]

Alguém pode ficar tentado a alocar a lista [1..n]na pilha e desalocá-la após o fretorno, mas isso seria catastrófico: mudariaf de usar memória O (1) (sob coleta de lixo) para memória O (n).

Um extenso trabalho foi feito na década de 1990 e no início de 2000 na inferência de região para a linguagem funcional estrita ML. Mads Tofte, Lars Birkedal, Martin Elsman e Niels Hallenberg escreveram uma retrospectiva bastante legível sobre seu trabalho em inferência de região, grande parte da qual eles integraram ao compilador MLKit . Eles experimentaram com gerenciamento de memória puramente baseado em região (ou seja, sem coletor de lixo), bem como gerenciamento de memória híbrido baseado em região / coletado por lixo, e relataram que seus programas de teste rodaram "entre 10 vezes mais rápido e 4 vezes mais lento" do que o lixo puro- versões coletadas.

reinerp
fonte
2
Haskell requer compartilhamento? Se não, em seu primeiro exemplo, você pode passar uma cópia da lista (resp. Nothing) Para a chamada recursiva loope desalocar a antiga - sem tempo de vida desconhecido. Claro que ninguém quer uma implementação sem compartilhamento de Haskell, porque é terrivelmente lento para grandes estruturas de dados.
nimi
3
Gosto muito dessa resposta, embora minha única confusão seja com o primeiro exemplo. Obviamente, se o usuário nunca digitou "limpar", ele poderia usar memória infinita (sem um GC), mas isso não é exatamente um vazamento, pois a memória ainda está sendo rastreada.
Pubby
3
C ++ 11 tem uma implementação maravilhosa de ponteiros inteligentes. Basicamente, ele emprega contagem de referência. Acho que Haskell poderia abandonar a coleta de lixo em favor de algo semelhante e, portanto, tornar-se determinista.
intrepidis
3
@ChrisNash - Não funciona. Os ponteiros inteligentes usam a contagem de referência sob o capô. A contagem de referência não pode lidar com estruturas de dados com ciclos. Haskell pode gerar estruturas de dados com ciclos.
Stephen C
3
Não tenho certeza se concordo com a parte de alocação dinâmica de memória desta resposta. Só porque o programa não sabe quando um usuário vai parar de fazer o loop temporariamente não deve torná-lo dinâmico. Isso é determinado pelo fato de o compilador saber se algo sairá do contexto. No caso de Haskell, onde isso é formalmente definido pela própria gramática da linguagem, o contexto de vida é conhecido. No entanto, a memória ainda pode ser dinâmica porque as expressões e tipos de lista são gerados dinamicamente na linguagem.
Timothy Swan
27

Vamos dar um exemplo trivial. Dado isso

f (x, y)

você precisa alocar o par em (x, y)algum lugar antes de chamar f. Quando você pode desalocar esse par? Você não tem ideia. Ele não pode ser desalocado quando fretorna, porque fpode ter colocado o par em uma estrutura de dados (por exemplo, f p = [p]), então a vida útil do par pode ter que ser mais longa do que o retorno de f. Agora, digamos que o par tenha sido colocado em uma lista, quem desmonta a lista pode desalocar o par? Não, porque o par pode ser compartilhado (por exemplo, let p = (x, y) in (f p, p)). Portanto, é realmente difícil dizer quando o par pode ser desalocado.

O mesmo é válido para quase todas as alocações em Haskell. Dito isso, é possível ter uma análise (análise de região) que fornece um limite superior para o tempo de vida. Isso funciona razoavelmente bem em linguagens restritas, mas nem tanto em linguagens preguiçosas (linguagens preguiçosas tendem a fazer muito mais mutações do que linguagens estritas na implementação).

Então, eu gostaria de inverter a questão. Por que você acha que Haskell não precisa de GC. Como você sugere que a alocação de memória seja feita?

agosto
fonte
18

Sua intuição de que isso tem algo a ver com pureza tem alguma verdade.

Haskell é considerado puro em parte porque os efeitos colaterais das funções são contabilizados na assinatura do tipo. Portanto, se uma função tem o efeito colateral de imprimir algo, deve haver um IOalgum lugar em seu tipo de retorno.

Mas há uma função que é usada implicitamente em todos os lugares em Haskell e cuja assinatura de tipo não é responsável, o que é, em certo sentido, um efeito colateral. Ou seja, a função que copia alguns dados e lhe dá duas versões de volta. Nos bastidores, isso pode funcionar literalmente, duplicando os dados na memória, ou 'virtualmente', aumentando uma dívida que precisa ser paga mais tarde.

É possível projetar linguagens com sistemas de tipos ainda mais restritivos (puramente "lineares") que não permitem a função de cópia. Do ponto de vista de um programador em tal linguagem, Haskell parece um pouco impuro.

Na verdade, Clean , um parente de Haskell, tem tipos lineares (mais estritamente: únicos) e isso pode dar uma ideia de como seria não permitir a cópia. Mas o Clean ainda permite a cópia de tipos "não exclusivos".

Há muitas pesquisas nesta área e, se você pesquisar no Google, encontrará exemplos de código linear puro que não requer coleta de lixo. Você encontrará todos os tipos de sistemas de tipo que podem sinalizar para o compilador qual memória pode ser usada, permitindo que o compilador elimine parte do GC.

Em certo sentido, os algoritmos quânticos também são puramente lineares. Cada operação é reversível e, portanto, nenhum dado pode ser criado, copiado ou destruído. (Eles também são lineares no sentido matemático usual.)

Também é interessante comparar com Forth (ou outras linguagens baseadas em pilha), que têm operações DUP explícitas que deixam claro quando a duplicação está acontecendo.

Outra maneira (mais abstrata) de pensar sobre isso é observar que Haskell é construído a partir do cálculo lambda simplesmente digitado, que se baseia na teoria das categorias fechadas cartesianas e que tais categorias vêm equipadas com uma função diagonal diag :: X -> (X, X). Uma linguagem baseada em outra classe de categoria pode não ter tal coisa.

Mas, em geral, a programação puramente linear é muito difícil para ser útil, então optamos pelo GC.

Sigfpe
fonte
3
Desde que escrevi esta resposta, a linguagem de programação Rust cresceu bastante em popularidade. Portanto, vale a pena mencionar que Rust usa um sistema do tipo linear para controlar o acesso à memória e vale a pena dar uma olhada se você quiser ver as idéias que mencionei usadas na prática.
sigfpe
14

As técnicas de implementação padrão aplicadas a Haskell realmente requerem um GC mais do que a maioria das outras linguagens, uma vez que eles nunca alteram valores anteriores, em vez de criar novos valores modificados com base nos anteriores. Como isso significa que o programa está constantemente alocando e usando mais memória, um grande número de valores será descartado com o passar do tempo.

É por isso que os programas GHC tendem a ter números totais de alocação tão altos (de gigabytes a terabytes): eles estão constantemente alocando memória, e é apenas graças ao GC eficiente que eles a recuperam antes de acabar.

terceiro
fonte
2
"eles nunca alteram os valores anteriores": você pode verificar haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011/Takano , trata-se de uma extensão experimental GHC que reutiliza a memória.
gfour
11

Se uma linguagem (qualquer linguagem) permite que você aloque objetos dinamicamente, então existem três maneiras práticas de lidar com o gerenciamento de memória:

  1. O idioma só pode permitir que você aloque memória na pilha ou na inicialização. Mas essas restrições limitam severamente os tipos de cálculos que um programa pode realizar. (Na prática. Em teoria, você pode emular estruturas de dados dinâmicas em (digamos) Fortran, representando-as em um grande array. É HORRÍVEL ... e não relevante para esta discussão.)

  2. A linguagem pode fornecer um mecanismo freeou explícito dispose. Mas isso depende do programador para acertar. Qualquer erro no gerenciamento de armazenamento pode resultar em vazamento de memória ... ou pior.

  3. A linguagem (ou mais estritamente, a implementação da linguagem) pode fornecer um gerenciador de armazenamento automático para o armazenamento alocado dinamicamente; ou seja, alguma forma de coletor de lixo.

A única outra opção é nunca recuperar o armazenamento alocado dinamicamente. Esta não é uma solução prática, exceto para pequenos programas que executam pequenos cálculos.

Aplicando isso a Haskell, a linguagem não tem a limitação de 1. e não há operação de desalocação manual de acordo com 2. Portanto, para ser utilizável para coisas não triviais, uma implementação de Haskell precisa incluir um coletor de lixo .

Não consigo pensar em um caso em que o GC seria necessário em uma linguagem pura.

Presumivelmente, você se refere a uma linguagem funcional pura.

A resposta é que um GC é necessário sob o capô para recuperar os objetos heap que a linguagem DEVE criar. Por exemplo.

  • Uma função pura precisa criar objetos heap porque, em alguns casos, ela precisa retorná-los. Isso significa que eles não podem ser alocados na pilha.

  • O fato de que pode haver ciclos (resultante de um, let recpor exemplo) significa que uma abordagem de contagem de referência não funcionará para objetos de heap.

  • Depois, há encerramentos de função ... que também não podem ser alocados na pilha porque têm um tempo de vida que é (normalmente) independente do quadro de pilha em que foram criados.

Estou procurando por exemplo de código que vazaria se um GC não estivesse presente.

Praticamente qualquer exemplo que envolvesse fechamentos ou estruturas de dados em forma de gráfico vazaria nessas condições.

Stephen C
fonte
2
Por que você acha que sua lista de opções é exaustiva? ARC em Objective C, inferência de região em MLKit e DDC, coleta de lixo em tempo de compilação em Mercury - todos eles não se encaixam nesta lista.
Dee Seg
@DeeMon - todos eles se encaixam em uma dessas categorias. Se você acha que não é porque está traçando os limites da categoria com muita força. Quando digo "alguma forma de coleta de lixo", quero dizer qualquer mecanismo no qual o armazenamento é recuperado automaticamente.
Stephen C
1
C ++ 11 usa ponteiros inteligentes. Basicamente, ele emprega contagem de referência. É determinístico e automático. Eu adoraria ver uma implementação de Haskell usando esse método.
intrepidis
2
@ChrisNash - 1) Não funcionaria. A recuperação de base de contagem de referência vaza dados se houver ciclos ... a menos que você possa contar com o código do aplicativo para interromper os ciclos. 2) É bem conhecido (para as pessoas que estudam essas coisas) que a contagem de referência tem um desempenho ruim quando comparada com um coletor de lixo (real) moderno.
Stephen C
@DeeMon - além disso, veja a resposta de Reinerp sobre por que a inferência de região não seria prática com Haskell.
Stephen C
8

Um coletor de lixo nunca é necessário, desde que você tenha memória suficiente. No entanto, na realidade, não temos memória infinita e, portanto, precisamos de algum método para recuperar a memória que não é mais necessária. Em linguagens impuras como C, você pode declarar explicitamente que acabou com alguma memória para liberá-la - mas esta é uma operação de mutação (a memória que você acabou de liberar não é mais segura para ler), então você não pode usar essa abordagem em uma linguagem pura. Portanto, é de alguma forma analisar estaticamente onde você pode liberar a memória (provavelmente impossível no caso geral), vazar memória como uma peneira (funciona muito bem até acabar) ou usar um GC.

bdonlan
fonte
Isso responde por que um GC é desnecessário em geral, mas estou mais interessado em Haskell em particular.
Pubby
10
Se um GC é teoricamente desnecessário em geral, então trivialmente segue que é teoricamente desnecessário para Haskell também.
terceiro dia
@ehird eu quis dizer necessário , acho que meu corretor ortográfico mudou o significado.
Pubby
1
O terceiro comentário ainda se mantém :-)
Paul R
2

GC é "obrigatório" em linguagens FP puras. Por quê? Operações alocadas e gratuitas são impuras! E a segunda razão é que estruturas de dados recursivas imutáveis ​​precisam de GC para existir porque backlinking cria estruturas abstrusas e impossíveis de manutenção para a mente humana. Claro, backlinking é uma bênção, porque copiar estruturas que o utilizam é ​​muito barato.

De qualquer forma, se você não acredita em mim, tente implementar a linguagem FP e verá que estou certo.

EDIT: Eu esqueci. Preguiça é INFERNO sem GC. Não acredita em mim? Experimente sem GC em, por exemplo, C ++. Você vai ver ... coisas

dev1223
fonte
1

Haskell é uma linguagem de programação não rígida, mas a maioria das implementações usa chamada por necessidade (preguiça) para implementar a não rigidez. No call-by-need você só avalia as coisas quando elas são alcançadas durante o tempo de execução usando a maquinaria de "thunks" (expressões que esperam para serem avaliadas e então se sobrescrevem, ficando visíveis para que seu valor seja reutilizado quando necessário).

Portanto, se você implementar sua linguagem preguiçosamente usando thunks, terá adiado todo o raciocínio sobre a vida útil dos objetos até o último momento, que é o tempo de execução. Já que agora você não sabe nada sobre vidas, a única coisa que você pode fazer razoavelmente é coletar o lixo ...

gfour
fonte
1
Em alguns casos, a análise estática pode inserir no código de conversão, o que libera alguns dados depois que a conversão é avaliada. A desalocação acontecerá em tempo de execução, mas não é GC. Isso é semelhante à ideia de ponteiros inteligentes de contagem de referência em C ++. Raciocinar sobre a vida útil do objeto acontece no tempo de execução, mas nenhum GC é usado.
Dee Seg