Por que linguagens de programação funcionais requerem coleta de lixo?

14

O que impede o ghc de traduzir o Haskell em uma linguagem de programação concatenativa, como lógica combinatória, e simplesmente usar a alocação de pilha para tudo? Segundo a Wikipedia, a tradução do cálculo lambda para a lógica combinatória é trivial e também as linguagens de programação concatenativas podem contar apenas com uma pilha para alocação de memória. É possível fazer essa tradução e, assim, eliminar a coleta de lixo para idiomas como Haskell e ocaml? Existem desvantagens em fazer isso?

Edição: movido para aqui /programming/39440412/why-do-functional-programming-languages-require-garbage-collection

Nicholas Grasevski
fonte
A Linguagem de Programação Cat se parece com um exemplo de função, linguagem baseada em pilha.
Petr Pudlák
1
Esta não é uma questão de nível de pesquisa, pois a coleta de lixo é abordada nos cursos de graduação em linguagens de programação (assim como a necessidade). Por favor, vá para cs.stackexchange.com
Andrej Bauer
Meu erro. Você sabe a resposta para minha pergunta?
Nicholas Grasevski 11/11/16
5
Eu acho que há alguma resposta no nível de pesquisa a ser dada a essa pergunta, pois eu lembro de ter lutado com ela também durante meus anos de pós-graduação: tudo em uma linguagem como Haskell parece um aplicativo de função, que vive na pilha. Penso que explicar por que os fechamentos são necessários, por que eles vivem na pilha e, talvez, que "dados que escapam ao escopo da função" tenham uma resposta muito informativa (que não tenho certeza de que estou qualificado para fornecer, infelizmente).
Cody
2
Concordo que partes da questão são de nível de pesquisa. Existem abordagens alterativas para gerenciar a memória, por exemplo, com base na região (seguindo Tofte, Talpin), com base no tipo afim (Rust). A tradução do cálcio- em combinadores leva a uma explosão de tamanho. λ
Martin Berger

Respostas:

16

Todos os comentários a seguir têm como premissa a escolha de uma estratégia de implementação padrão usando fechamentos para representar valores de função e uma ordem de avaliação de chamada por valor:

  1. Para o cálculo lambda puro, a coleta de lixo não é necessária. Isso ocorre porque não é possível formar ciclos no heap: todo valor recém-alocado pode conter apenas referências a valores alocados anteriormente e, portanto, o gráfico de memória forma um DAG - portanto, a contagem de referência é suficiente para gerenciar a memória.

  2. A maioria das implementações não usa a contagem de referência por dois motivos.

    1. Eles suportam uma forma do tipo ponteiro (por exemplo, o refconstrutor de tipos no ML) e, assim, podem ser formados ciclos verdadeiros no heap.
    2. A contagem de referência é muito menos eficiente que a coleta de lixo, pois
      • requer muito espaço adicional para manter as contagens de referência e
      • atualizar as contagens geralmente é um trabalho desperdiçado, e
      • as atualizações nas contagens criam um monte de contenção de gravação que mata o desempenho paralelo.
  3. Linguagens de tipo linear podem eliminar a contagem de referência (essencialmente porque as contagens são de 0 a 1: o valor tem uma única referência a ele ou está morto e pode ser liberado).

  4. No entanto, a alocação de pilha ainda não é suficiente. Isso ocorre porque é possível formar valores de função que se referem a variáveis ​​livres (ou seja, precisamos implementar fechamentos de funções); se você alocar coisas na pilha, os valores ativos podem ser intercalados com valores mortos, e isso causará assintóticos incorretos. uso de espaço.

  5. Você pode obter os assintóticos corretos substituindo uma pilha por uma "pilha de espaguete" (por exemplo, implemente a pilha como uma lista vinculada na pilha, para poder cortar os quadros mortos, conforme necessário).

  6. Se você deseja uma disciplina de pilha real, pode usar sistemas de tipos baseados em "lógica ordenada" (tipos essencialmente lineares menos troca).

Neel Krishnaswami
fonte
2
Não é a razão mais básica para (2) que - mesmo sem efeitos colaterais observáveis ​​- as implementações desejam ter um operador eficiente para recursão (mútua), isto é, uma que realmente forma um ciclo na pilha?
Andreas Rossberg 12/09
@andreasrossberg: Pensei em mencionar isso, mas deixei de fora, já que você pode usar o combinador y para recursão.
Neel Krishnaswami