Programação Funcional - Imutabilidade

Eu estou tentando entender como lidar com dados imutáveis ​​no FP (especificamente no F #, mas outros FP também estão bem) e romper o velho hábito do pensamento de estado completo (estilo OOP). Uma parte da resposta selecionada para a pergunta aqui reiterou minha busca por quaisquer write-ups em torno de problemas resolvidos por representações com estado no OOP com imutáveis ​​no FP (por exemplo: uma fila com produtores e consumidores). Quaisquer pensamentos ou links são bem-vindos? Desde já, obrigado.

Edit : Para esclarecer um pouco mais a questão, como as estruturas imutáveis ​​(ex: fila) seriam compartilhadas simultaneamente entre vários threads (ex: produtor e consumidor) no FP

Embora às vezes seja expresso dessa maneira, a programação funcional¹ não impede cálculos com estado. O que ele faz é forçar o programador a tornar o estado explícito.

Por exemplo, vamos pegar a estrutura básica de algum programa usando uma fila imperativa (em alguma pseudo-linguagem):

q := Queue.new();
while (true) {
    if (Queue.is_empty(q)) {
        Queue.add(q, producer());
    } else {
        consumer(Queue.take(q));
    }
}

A estrutura correspondente com uma estrutura de dados da fila funcional (ainda em uma linguagem imperativa, para resolver uma diferença de cada vez) ficaria assim:

q := Queue.empty;
while (true) {
    if (q = Queue.empty) {
        q := Queue.add(q, producer());
    } else {
        (tail, element) := Queue.take(q);
        consumer(element);
        q := tail;
    }
}

Como a fila agora é imutável, o próprio objeto não muda. Nesse pseudo-código, qele próprio é uma variável; as atribuições q := Queue.add(…)e q := tailfaça com que aponte para um objeto diferente. A interface das funções da fila mudou: cada uma deve retornar o novo objeto da fila resultante da operação.

Em uma linguagem puramente funcional, ou seja, em uma linguagem sem efeito colateral, você precisa explicitar todos os estados. Como o produtor e o consumidor provavelmente estão fazendo algo, o estado deles também deve estar na interface do chamador.

main_loop(q, other_state) {
    if (q = Queue.empty) {
        let (new_state, element) = producer(other_state);
        main_loop(Queue.add(q, element), new_state);
    } else {
        let (tail, element) = Queue.take(q);
        let new_state = consumer(other_state, element);
        main_loop(tail, new_state);
    }
}
main_loop(Queue.empty, initial_state)

Observe como agora cada parte do estado é gerenciada explicitamente. As funções de manipulação de fila tomam uma fila como entrada e produzem uma nova fila como saída. O produtor e o consumidor também passam seu estado.

A programação simultânea não se encaixa tão bem na programação funcional, mas se encaixa muito bem na programação funcional. A idéia é executar vários nós de computação separados e permitir que eles troquem mensagens. Cada nó executa um programa funcional e seu estado muda à medida que envia e recebe mensagens.

Continuando o exemplo, como há uma única fila, ela é gerenciada por um nó específico. Os consumidores enviam uma mensagem a esse nó para obter um elemento. Os produtores enviam a esse nó uma mensagem para adicionar um elemento.

main_loop(q) =
    consumer->consume(q->take()) || q->add(producer->produce());
    main_loop(q)

A única linguagem "industrializada" que acerta a concorrência³ é Erlang . Aprender Erlang é definitivamente o caminho para a iluminação⁴ sobre programação simultânea.

Todo mundo muda para idiomas sem efeitos colaterais agora!

Term _{Este termo tem vários significados; aqui eu acho que você está usando isso para significar programação sem efeitos colaterais, e esse é o significado que eu também estou usando.}
² _{Programar com estado implícito é uma programação imperativa ; a orientação a objetos é uma preocupação completamente ortogonal.}
³ _{Inflamatório, eu sei, mas estou falando sério. Threads com memória compartilhada é a linguagem assembly da programação simultânea. A passagem de mensagens é muito mais fácil de entender, e a falta de efeitos colaterais realmente brilha assim que você introduz a simultaneidade.}
⁴ _{E isso vem de alguém que não é fã de Erlang, mas por outros motivos.}

O comportamento de estado em um idioma de FP é implementado como uma transformação de um estado anterior para um novo estado. Por exemplo, enfileirar seria uma transformação de uma fila e um valor para uma nova fila com o valor enfileirado. Retirar da fila seria uma transformação de uma fila para um valor e uma nova fila com o valor removido. Construções como mônadas foram criadas para abstrair essa transformação de estado (e outros resultados da computação) de maneiras úteis

... problemas resolvidos por representações com estado no OOP com imutáveis ​​no FP (por exemplo: uma fila com produtores e consumidores)

Sua pergunta é o que é chamado de "problema XY". Especificamente, o conceito que você cita (fila com produtores e consumidores) é na verdade uma solução e não um "problema", como você descreve. Isso apresenta uma dificuldade, porque você está solicitando uma implementação puramente funcional de algo que é inerentemente impuro. Então, minha resposta começa com uma pergunta: qual é o problema que você está tentando resolver?

Existem várias maneiras de vários produtores enviarem seus resultados para um único consumidor compartilhado. Talvez a solução mais óbvia no F # seja tornar o consumidor um agente (também conhecido como MailboxProcessor) e enviar aos produtores Postseus resultados para o agente do consumidor. Isso usa uma fila internamente e não é pura (o envio de mensagens em F # é um efeito colateral não controlado, uma impureza).

No entanto, é bem provável que o problema subjacente seja algo mais parecido com o padrão de dispersão-coleta da programação paralela. Para resolver esse problema, você pode criar uma matriz de valores de entrada e depois Array.Parallel.mapsobre eles e reunir os resultados usando uma série Array.reduce. Como alternativa, você pode usar funções do PSeqmódulo para processar os elementos das sequências em paralelo.

Devo também enfatizar que não há nada de errado com o pensamento estatal. A pureza tem vantagens, mas certamente não é uma panacéia, e você deve se conscientizar também de suas deficiências. De fato, é exatamente por isso que o F # não é uma linguagem funcional pura: para que você possa usar as impurezas quando preferidas.

Clojure tem um conceito muito bem pensado de estado e identidade, que está intimamente relacionado à simultaneidade. A imutabilidade desempenha um papel importante, todos os valores no Clojure são imutáveis ​​e podem ser acessados ​​através de referências. As referências são mais do que simples indicadores. Eles gerenciam o acesso ao valor e existem vários tipos deles com diferentes semânticas. Uma referência pode ser modificada para apontar para um novo valor (imutável), e essa alteração é garantida como atômica. No entanto, após a modificação, todos os outros threads ainda funcionam com o valor original, pelo menos até que acessem a referência novamente.

Eu recomendo que você leia um excelente artigo sobre estado e identidade no Clojure , que explica os detalhes muito melhor do que eu.