Programação funcional: idéias corretas sobre concorrência e estado?

Os defensores do FP alegaram que a concorrência é fácil porque seu paradigma evita um estado mutável. Eu não entendo.

Imagine que estamos criando um rastreamento de masmorra multijogador (semelhante a um roguel) usando FP, onde enfatizamos funções puras e estruturas de dados imutáveis. Geramos uma masmorra composta por salas, corredores, heróis, monstros e saques. Nosso mundo é efetivamente um gráfico objeto de estruturas e seus relacionamentos. À medida que as coisas mudam, nossa representação do mundo é alterada para refletir essas mudanças. Nosso herói mata um rato, pega uma espada curta, etc.

Para mim, o mundo (realidade atual) carrega essa ideia de estado e sinto falta de como a FP supera isso. À medida que nosso herói age, as funções alteram o estado do mundo. Parece que toda decisão (AI ou humana) precisa se basear no estado do mundo como está no presente. Onde permitiríamos a simultaneidade? Não podemos ter vários processos simultâneos para corrigir o estado do mundo, para que um processo não baseie seus resultados em algum estado expirado. Parece-me que todo controle deve ocorrer dentro de um único loop de controle, de modo que estamos sempre processando o estado presente representado pelo nosso gráfico de objetos atual do mundo.

Claramente, existem situações perfeitamente adequadas para simultaneidade (ou seja, ao processar tarefas isoladas cujos estados são independentes um do outro).

Não vejo como a concorrência é útil no meu exemplo e esse pode ser o problema. Eu posso estar deturpando a reivindicação de alguma forma.

Alguém pode representar melhor essa reivindicação?

Vou tentar sugerir a resposta. Esta não é uma resposta, apenas uma ilustração introdutória. A resposta de @jk aponta para a coisa real, zíperes.

Imagine que você tem uma estrutura de árvore imutável. Você deseja alterar um nó inserindo um filho. Como resultado, você obtém uma árvore totalmente nova.

Mas a maior parte da nova árvore é exatamente igual à antiga. Uma implementação inteligente reutilizaria a maioria dos fragmentos de árvore, direcionando ponteiros ao redor do nó alterado:

O livro de Okasaki está cheio de exemplos como este.

Então, suponho que você possa alterar razoavelmente pequenas partes do seu mundo de jogo a cada movimento (pegar uma moeda) e alterar apenas pequenas partes da estrutura de dados do seu mundo (a célula onde a moeda foi retirada). As peças que pertencem apenas a estados anteriores serão coletadas com o tempo.

Isso provavelmente leva alguma consideração ao projetar a estrutura do mundo dos jogos de dados de maneira apropriada. Infelizmente, não sou especialista nesses assuntos. Definitivamente, deve ser algo além de uma matriz NxM que alguém usaria como estrutura de dados mutáveis. Provavelmente deveria consistir em pedaços menores (corredores - células individuais) que apontam um para o outro, como os nós das árvores.

A resposta do 9000 é metade da resposta, estruturas de dados persistentes permitem reutilizar partes inalteradas.

Você já deve estar pensando "ei, e se eu quiser mudar a raiz da árvore?" como está no exemplo, dado que agora significa alterar todos os nós. É aqui que os zíperes vêm em socorro. Eles permitem que o elemento em um foco seja alterado em O (1), e o foco pode ser movido para qualquer lugar da estrutura.

O outro ponto dos zíperes é que existe um zíper para praticamente qualquer tipo de dados que você deseja

Programas de estilo funcional criam muitas oportunidades como essa para usar simultaneidade. Sempre que você transforma, filtra ou agrega uma coleção, e tudo é puro ou imutável, há uma oportunidade para a operação ser acelerada pela simultaneidade.

Por exemplo, suponha que você execute decisões de IA independentemente uma da outra e em nenhuma ordem específica. Eles não se revezam, todos tomam uma decisão simultaneamente e o mundo avança. O código pode ficar assim:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

Você tem uma função para calcular o que um monstro fará com um estado mundial e aplicá-lo a todos os monstros como parte da computação do próximo estado mundial. Isso é algo natural a se fazer em uma linguagem funcional, e o compilador é livre para executar a etapa 'aplicar a todos os monstros' em paralelo.

Em uma linguagem imperativa, é mais provável que você repita todos os monstros, aplicando seus efeitos ao mundo. É mais fácil fazê-lo dessa maneira, porque você não deseja lidar com clonagem ou aliasing complicado. O compilador não pode executar os cálculos de monstro em paralelo nesse caso, porque as decisões iniciais dos monstros afetam as decisões posteriores dos monstros.

Ouvir algumas palestras de Rich Hickey - essa em particular - aliviou minha confusão. Em um deles, ele indicou que não há problema em que processos concorrentes possam não ter o estado mais atual. Eu precisava ouvir aquilo. O que eu estava tendo problemas para digerir era que os programas realmente aceitariam basear as decisões em instantâneos do mundo que foram substituídos por outros mais recentes. Fiquei me perguntando como a FP simultânea contornou a questão de basear as decisões no estado antigo.

Em um aplicativo bancário, nunca desejaríamos basear uma decisão em um instantâneo de estado que foi substituído por um mais novo (ocorreu uma retirada).

Essa simultaneidade é fácil porque o paradigma do FP evita o estado mutável é uma afirmação técnica que não tenta dizer nada sobre os méritos lógicos de basear as decisões em estados potencialmente antigos. O FP ainda modela a mudança de estado. Não há como contornar isso.

Os defensores do FP alegaram que a concorrência é fácil porque seu paradigma evita um estado mutável. Eu não entendo.

Eu queria abordar essa questão geral como alguém que é um neófito funcional, mas que tem tido muitos efeitos colaterais ao longo dos anos e gostaria de mitigá-los, por todos os tipos de razões, incluindo razões mais fáceis (ou especificamente "mais seguras, menos propenso a erros ") simultaneidade. Quando olho para meus colegas funcionais e o que eles estão fazendo, a grama parece um pouco mais verde e cheira melhor, pelo menos nesse aspecto.

Algoritmos seriais

Dito isto, sobre o seu exemplo específico, se o seu problema é de natureza serial e B não pode ser executado até que A seja concluído, conceitualmente você não pode executar A e B em paralelo, não importa o quê. Você precisa encontrar uma maneira de quebrar a dependência da ordem, como na sua resposta, com base em movimentos paralelos usando o antigo estado do jogo ou usar uma estrutura de dados que permita que partes dela sejam modificadas independentemente para eliminar a dependência da ordem, conforme proposto nas outras respostas. , ou algo desse tipo. Mas há definitivamente uma parcela de problemas de design conceitual como este, onde você não pode necessariamente multithread tudo tão facilmente porque as coisas são imutáveis. Algumas coisas serão de natureza serial até que você encontre uma maneira inteligente de quebrar a dependência do pedido, se isso for possível.

Simultaneidade mais fácil

Dito isto, há muitos casos em que não conseguimos paralelizar programas que envolvem efeitos colaterais em lugares que poderiam melhorar potencialmente significativamente o desempenho simplesmente por causa da possibilidade de que ele pode não ser thread-safe. Um dos casos em que a eliminação do estado mutável (ou mais especificamente, efeitos colaterais externos) ajuda muito, como eu vejo, é que ele transforma "pode ​​ou não ser seguro para threads " em "definitivamente seguro para threads" .

Para tornar essa afirmação um pouco mais concreta, considere que eu lhe dou uma tarefa para implementar uma função de classificação em C que aceita um comparador e a usa para classificar uma matriz de elementos. Ele deve ser bastante generalizado, mas vou dar uma suposição fácil de que ele será usado contra entradas de uma escala (milhões de elementos ou mais) que, sem dúvida, será benéfico usar sempre uma implementação multithread. Você pode multithread sua função de classificação?

O problema é que você não pode, porque os comparadores que sua função de classificação chama podemcausar efeitos colaterais, a menos que você saiba como eles são implementados (ou, pelo menos, documentados) para todos os casos possíveis, o que é praticamente impossível sem a degeneralização da função. Um comparador pode fazer algo nojento como modificar uma variável global dentro de uma maneira não atômica. 99,9999% dos comparadores podem não fazer isso, mas ainda não podemos multithread essa função generalizada simplesmente devido aos 0,00001% dos casos que podem causar efeitos colaterais. Como resultado, talvez você precise oferecer uma função de classificação single-threaded e multithread e passar a responsabilidade aos programadores que a utilizam para decidir qual usar com base na segurança do thread. E as pessoas ainda podem usar a versão de thread único e perder oportunidades de multithread porque também podem não ter certeza se o comparador é seguro para threads,

Há muita inteligência que pode estar envolvida na racionalização da segurança das coisas sem abrir bloqueios em todos os lugares, o que pode desaparecer se tivermos apenas garantias de que as funções não causarão efeitos colaterais no presente e no futuro. E há medo: medo prático, porque quem já teve que depurar uma condição de corrida muitas vezes provavelmente hesitaria em multithreading qualquer coisa que eles não possam ter 110% de certeza é segura para threads e permanecerá como tal. Mesmo para os mais paranóicos (dos quais eu provavelmente sou pelo menos limítrofe), a função pura fornece a sensação de alívio e confiança que podemos chamar em paralelo com segurança.

E esse é um dos principais casos em que considero tão benéfico se você puder obter uma garantia absoluta de que tais funções são seguras contra threads, o que você obtém com linguagens funcionais puras. A outra é que as linguagens funcionais geralmente promovem a criação de funções livres de efeitos colaterais em primeiro lugar. Por exemplo, eles podem fornecer estruturas de dados persistentes, onde é razoavelmente eficiente inserir uma estrutura de dados massiva e gerar uma nova, com apenas uma pequena parte dela alterada do original sem tocar no original. Aqueles que trabalham sem essas estruturas de dados podem querer modificá-los diretamente e perder alguma segurança de encadeamento ao longo do caminho.

Efeitos colaterais

Dito isto, eu discordo de uma parte com todo o respeito devido aos meus amigos funcionais (que eu acho super legais):

[...] porque seu paradigma evita um estado mutável.

Não é necessariamente imutabilidade que torna a concorrência tão prática quanto eu a vejo. São funções que evitam causar efeitos colaterais. Se uma função insere uma matriz para classificar, copia e depois modifica a cópia para classificar seu conteúdo e gera a cópia, ela ainda é tão segura quanto a thread que uma que trabalha com algum tipo de matriz imutável, mesmo se você estiver passando a mesma entrada matriz a partir de vários segmentos. Então, acho que ainda há um lugar para tipos mutáveis ​​na criação de código muito compatível com a concorrência, por assim dizer, embora haja muitos benefícios adicionais para tipos imutáveis, incluindo estruturas de dados persistentes que eu não uso tanto por suas propriedades imutáveis, mas para elimine a despesa de ter que copiar tudo em profundidade para criar funções livres de efeitos colaterais.

E muitas vezes há sobrecarga para tornar as funções livres de efeitos colaterais na forma de embaralhar e copiar alguns dados adicionais, talvez um nível extra de indireção e, possivelmente, algum GC em partes de uma estrutura de dados persistente, mas eu olho para um dos meus amigos que tem uma máquina de 32 núcleos e acho que a troca provavelmente vale a pena se pudermos fazer mais coisas com mais confiança em paralelo.