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
functional-programming
haskell
Nicholas Grasevski
fonte
fonte
Respostas:
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:
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.
A maioria das implementações não usa a contagem de referência por dois motivos.
ref
construtor de tipos no ML) e, assim, podem ser formados ciclos verdadeiros no heap.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).
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.
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).
Se você deseja uma disciplina de pilha real, pode usar sistemas de tipos baseados em "lógica ordenada" (tipos essencialmente lineares menos troca).
fonte