Todas as linguagens funcionais usam coleta de lixo?

Existe uma linguagem funcional que permita usar a semântica da pilha - destruição determinística automática no final do escopo?

Não que eu saiba, embora eu não seja um especialista em programação funcional.

Parece bastante difícil em princípio, porque os valores retornados das funções podem conter referências a outros valores que foram criados (na pilha) dentro da mesma função, ou podem ter sido passados ​​tão facilmente como um parâmetro ou referenciados por algo passado em como um parâmetro. Em C, esse problema é tratado ao permitir que ponteiros oscilantes (ou mais precisamente, comportamento indefinido) possam ocorrer se o programador não acertar as coisas. Esse não é o tipo de solução que os designers de linguagem funcional aprovam.

Existem possíveis soluções, no entanto. Uma idéia é tornar a vida útil do valor parte do tipo do valor, juntamente com as referências a ele, e definir regras baseadas em tipo que impedem que valores alocados à pilha sejam retornados ou referenciados por algo retornado de função. Não resolvi as implicações, mas suspeito que seria horrível.

Para o código monádico, há outra solução que é (realmente ou quase) monádica também e poderia fornecer um tipo de IORef destruído automaticamente por determinação determinística. O princípio é definir ações de "aninhamento". Quando combinados (usando um operador associativo), eles definem um fluxo de controle de aninhamento - acho que "elemento XML", com os valores mais à esquerda, fornecendo o par externo de etiqueta de início e fim. Essas "tags XML" estão apenas definindo a ordem das ações monádicas em outro nível de abstração.

Em algum momento (no lado direito da cadeia de composição associativa), você precisa de algum tipo de terminador para finalizar o aninhamento - algo para preencher o buraco no meio. A necessidade de um terminador é o que provavelmente significa que o operador de composição de aninhamento não é monádico; porém, novamente, não tenho muita certeza, pois não trabalhei nos detalhes. Como toda aplicação que o terminador faz é converter uma ação de aninhamento em efetivamente uma ação monádica normal composta, talvez não - isso não afeta necessariamente o operador de composição de aninhamento.

Muitas dessas ações especiais teriam uma etapa "tag final" nula e equiparariam a etapa "tag inicial" a alguma ação monádica simples. Mas alguns representariam declarações de variáveis. Eles representariam o construtor com a tag de início e o destruidor com a tag de finalização. Então você recebe algo como ...

act = terminate ((def-var "hello" ) >>>= \h ->
                 (def-var " world") >>>= \w ->
                 (use-val ((get h) ++ (get w)))
                )

Traduzindo para uma composição monádica com a seguinte ordem de execução, cada tag (não elemento) se torna uma ação monádica normal ...

<def-var val="hello">  --  construction
  <def-var val=" world>  --  construction
    <use-val ...>
      <terminator/>
    </use-val>  --  do nothing
  </def-val>  --  destruction
</def-val>  --  destruction

Regras como essa podem permitir a implementação de RAII no estilo C ++. As referências do tipo IORef não podem escapar de seu escopo, por razões semelhantes às por que os IORefs normais não podem escapar da mônada - as regras da composição associativa não fornecem como a referência escapar.

EDIT - eu quase esqueci de dizer - há uma área definida que não tenho certeza sobre aqui. É importante garantir que uma variável externa não possa fazer referência a uma interna, basicamente, portanto, deve haver restrições quanto ao que você pode fazer com essas referências do tipo IORef. Mais uma vez, não trabalhei com todos os detalhes.

Portanto, a construção poderia, por exemplo, abrir um arquivo cuja destruição é encerrada. A construção poderia abrir um encaixe cuja destruição se fecha. Basicamente, como em C ++, as variáveis ​​se tornam gerenciadores de recursos. Mas, diferentemente do C ++, não há objetos alocados em heap que não podem ser destruídos automaticamente.

Embora essa estrutura suporte RAII, você ainda precisa de um coletor de lixo. Embora uma ação de aninhamento possa alocar e liberar memória, tratando-a como um recurso, ainda existem todas as referências a valores funcionais (potencialmente compartilhados) dentro desse pedaço de memória e em outros lugares. Como a memória pode ser simplesmente alocada na pilha, evitando a necessidade de um heap free, o significado real (se houver) é para outros tipos de gerenciamento de recursos.

Portanto, o que isso alcança é separar o gerenciamento de recursos no estilo RAII do gerenciamento de memória, pelo menos no caso em que o RAII se baseia no escopo de aninhamento simples. Você ainda precisa de um coletor de lixo para gerenciamento de memória, mas obtém limpeza determinística automática, segura e oportuna, de outros recursos.

Se você considera C ++ uma linguagem funcional (possui lambdas), é um exemplo de linguagem que não usa uma coleta de lixo.

Devo dizer que a pergunta é um pouco mal definida, porque pressupõe que há uma coleção padrão de "linguagens funcionais". Quase toda linguagem de programação suporta alguma quantidade de programação funcional. E, quase toda linguagem de programação suporta alguma quantidade de programação imperativa. Onde traçar a linha para dizer qual é uma linguagem funcional e qual é uma linguagem imperativa, além de guiada por preconceitos culturais e dogmas populares?

Uma maneira melhor de formular a pergunta seria "é possível suportar a programação funcional em uma memória alocada por pilha". A resposta é, como já mencionado, muito difícil. O estilo de programação funcional promove a alocação de estruturas de dados recursivas à vontade, o que requer uma memória heap (seja coleta de lixo ou contagem de referência). No entanto, existe uma técnica de análise de compilador bastante sofisticada chamada análise de memória baseada em região, na qual o compilador pode dividir o heap em grandes blocos que podem ser alocados e desalocados automaticamente, de maneira semelhante à alocação de pilha. A página da Wikipedia lista várias implementações da técnica, para linguagens "funcionais" e "imperativas".