Por que usamos estruturas de dados persistentes na programação funcional?

A programação funcional emprega estruturas de dados persistentes e objetos imutáveis. Minha pergunta é por que é crucial ter essas estruturas de dados aqui? Quero entender em um nível baixo o que aconteceria se a estrutura de dados não fosse persistente? O programa falharia com mais frequência?

Quando você trabalha com objetos de dados imutáveis, as funções têm a propriedade de que toda vez que você as chama com as mesmas entradas, elas produzem as mesmas saídas. Isso facilita a conceitualização de cálculos e a correção. Também os torna mais fáceis de testar.

Isso é apenas o começo. Como a matemática trabalha há muito tempo com funções, há muitas técnicas de raciocínio que podemos emprestar da matemática e usá-las para um raciocínio rigoroso sobre os programas. A vantagem mais importante do meu ponto de vista é que os sistemas de tipos para programas funcionais são bem desenvolvidos. Portanto, se você cometer um erro em algum lugar, as chances são muito altas de que isso apareça como uma incompatibilidade de tipo. Portanto, os programas funcionais digitados tendem a ser muito mais confiáveis ​​que os programas imperativos.

Ao trabalhar com objetos de dados mutáveis, por outro lado, você primeiro tem a carga cognitiva de lembrar e gerenciar os vários estados pelos quais o objeto passa durante uma computação. Você deve tomar as providências na ordem certa, certificando-se de que todas as propriedades necessárias para uma etapa específica sejam satisfeitas nesse ponto. É fácil cometer erros, e os sistemas de tipos não são poderosos o suficiente para detectar esses erros.

A matemática nunca funcionou com objetos de dados mutáveis. Portanto, não há técnicas de raciocínio que possamos emprestar delas. Existem muitas de nossas próprias técnicas desenvolvidas em Ciência da Computação, especialmente a Floyd-Hoare Logic . No entanto, são mais difíceis de dominar do que as técnicas matemáticas padrão, a maioria dos alunos não consegue lidar com elas e, portanto, raramente são ensinadas.

Para uma rápida visão geral de como os dois paradigmas diferem, você pode consultar os primeiros folhetos das minhas notas de aula sobre Princípios de Linguagens de Programação .

É mais fácil trabalhar corretamente com estruturas de dados persistentes do que trabalhar com estruturas de dados mutáveis. Eu diria que essa é a principal vantagem.

Obviamente, teoricamente, qualquer coisa que fazemos com estruturas de dados persistentes também podemos fazer com estruturas mutáveis ​​e vice-versa. Em muitos casos, estruturas de dados persistentes incorrem em custos extras, geralmente porque partes delas precisam ser copiadas. Essas considerações teriam tornado as estruturas de dados persistentes muito menos atraentes 30 anos atrás, quando os supercomputadores tinham menos memória que o seu telefone celular. Atualmente, porém, os principais gargalos na produção de software parecem ser o tempo de desenvolvimento e os custos de manutenção. Assim, estamos dispostos a sacrificar alguma eficiência na execução por eficiência no desenvolvimento.

Por que é mais fácil usar estruturas de dados persistentes? Porque os humanos são muito ruins em rastrear aliases e outros tipos de interações inesperadas entre diferentes partes de um programa. Eles pensam automaticamente porque duas coisas são chamadas xe y, então, não têm nada em comum. Afinal, é preciso esforço para descobrir que "a estrela da manhã" e "a estrela da noite" são realmente a mesma coisa. Da mesma forma, é muito fácil esquecer que uma estrutura de dados pode mudar porque outros threads estão trabalhando com ela ou porque chamamos um método que altera a estrutura de dados etc. Muitas dessas preocupações simplesmente não estão presentes quando trabalhamos com estruturas de dados persistentes.

As estruturas de dados persistentes também têm outras vantagens técnicas. Geralmente é mais fácil otimizá-los. Por exemplo, você sempre pode copiar uma estrutura de dados persistente para outro nó da nuvem, se desejar, não há preocupação com a sincronização.

Adicionando às respostas de outras pessoas e reforçando uma abordagem matemática, a programação funcional também possui uma sinergia agradável com a Álgebra Relacional e as Conexões de Galois.

Isso é extremamente útil na área de Métodos formais.
Por exemplo:

• As provas formais na verificação do programa são simplificadas com a Verificação Estática Estendida;
• Várias propriedades da Álgebra relacional são úteis na solução de SAT, com ferramentas como Alloy;
• O Galois Connections permite uma abordagem de cálculo da especificação de software, como visto neste blog , com referência a um artigo , de Shin-Cheng Mu e José Nuno Oliveira.
• As conexões de Galois (e programação funcional) podem ser usadas da maneira Design por contrato, uma vez que são um conceito mais geral que o Hoare Logic.

Exemplo

$\{p\} P \{q\}$$[P] \cdot \phi_p \subseteq \phi_q \cdot [P]$

• $[P]$$P$
• $\phi_p$$\phi_q)$$p$$q$

Essa abordagem também permite o cálculo de pré-condição mais fraco e mais forte , o que é útil em várias situações.

Quero entender em um nível baixo o que aconteceria se a estrutura de dados não fosse persistente?

Vejamos um gerador de números pseudo-aleatórios com um enorme espaço de estado (como " Mersenne twister " com um estado de 2450 bytes) como uma estrutura de dados. Nós realmente não queremos usar nenhum número aleatório mais de uma vez, então parece haver poucas razões para implementar isso como uma estrutura de dados persistente e imutável. Agora vamos perguntar a si mesmos o que pode dar errado no código a seguir:

mt_gen = CreateMersenneTwisterPRNGen(seed)
integral = MonteCarloIntegral_Bulk(mt_gen) + MonteCarloIntegral_Boundary(mt_gen)

A maioria das linguagens de programação não especificar a ordem em que MonteCarloIntegral_Bulke MonteCarloIntegral_Boundaryserá avaliado. Se os dois fizerem referência a um mt_gen mutável como argumento, o resultado desse cálculo poderá depender da plataforma. Pior ainda, pode haver plataformas em que o resultado não seja reproduzível entre diferentes execuções.

Pode-se projetar uma estrutura de dados mutável eficiente para mt_gen, de modo que qualquer intercalação da execução MonteCarloIntegral_Bulke MonteCarloIntegral_Boundarydê um resultado "correto", mas uma intercalação diferente geralmente leve a um resultado "correto". Essa não reprodutibilidade torna a função correspondente "impura" e também leva a alguns outros problemas.

A não reprodutibilidade pode ser evitada aplicando uma ordem de execução sequencial fixa. Mas, nesse caso, o código pode ser organizado de tal maneira que apenas uma única referência ao mt_gen esteja disponível a qualquer momento. Em uma linguagem de programação funcional digitada, tipos de exclusividade podem ser usados ​​para impor essa restrição, permitindo atualizações mutáveis ​​seguras também no contexto de linguagens de programação funcionais puras. Tudo isso pode parecer bom e elegante, mas pelo menos em teoria as simulações de Monte Carlo são embaraçosamente paralelas, e nossa "solução" acabou de destruir essa propriedade. Este não é apenas um problema teórico, mas uma questão prática muito real. No entanto, precisamos modificar (a funcionalidade oferecida por) nosso gerador de números pseudo-aleatórios e a sequência de números aleatórios que produz, e nenhuma linguagem de programação pode fazer isso automaticamente por nós. (É claro que podemos usar uma biblioteca de números pseudoaleatórios diferente que já oferece a funcionalidade necessária.)

Em um nível baixo, estruturas de dados mutáveis ​​facilmente levam à não reprodutibilidade (e, portanto, impureza), se a ordem de execução não for seqüencial e fixa. Uma estratégia imperativa típica para lidar com esses problemas é ter fases sequenciais com ordem de execução fixa, durante as quais as estruturas de dados mutáveis ​​são alteradas, e fases paralelas com ordem de execução arbitrária, durante as quais todas as estruturas de dados mutáveis ​​compartilhadas permanecem constantes.

Andrej Bauer levantou a questão do alias para estruturas de dados mutáveis. Curiosamente, diferentes linguagens imperativas como Fortran e C têm suposições diferentes sobre o alias permitido de argumentos de função, e a maioria dos programadores não sabe que sua linguagem possui um modelo de alias.

A imutabilidade e a semântica de valores podem ser um pouco superestimadas. O mais importante é que o sistema de tipos e a estrutura lógica (como o modelo de máquina abstrata, o modelo de alias, o modelo de simultaneidade ou o modelo de gerenciamento de memória) da sua linguagem de programação ofereça suporte suficiente para trabalhar "com segurança" com dados "eficientes" estruturas. A introdução de "mover semântica" para o C ++ 11 pode parecer um grande passo em termos de pureza e "segurança" de um ponto de vista teórico, mas na prática é o contrário. O sistema de tipos e a estrutura lógica da linguagem foram estendidos para remover grandes partes do perigo associado à nova semântica. (E mesmo que as arestas permaneçam, isso não significa que isso não poderia ser melhorado com um "melhor"

Uday Reddy levantou a questão de que a matemática nunca funcionou com objetos de dados mutáveis ​​e que os sistemas de tipos para programas funcionais são bem desenvolvidos para objetos de dados imutáveis. Isso me lembrou a explicação de Jean-Yves Girard de que a matemática não é usada para trabalhar com objetos mutáveis, quando ele tenta motivar a lógica linear.

Pode-se perguntar como estender o sistema de tipos e a estrutura lógica das linguagens de programação funcionais para permitir trabalhar "com segurança" com estruturas de dados não-persistentes mutáveis ​​"eficientes". Um problema aqui pode ser que a lógica clássica e as álgebras booleanas podem não ser a melhor estrutura lógica para trabalhar com estruturas de dados mutáveis. Talvez a lógica linear e os monoides comutativos possam ser mais adequados para essa tarefa? Talvez eu devesse ler o que Philip Wadler tem a dizer sobre lógica linear como sistema de tipos para linguagens de programação funcional? Porém, mesmo que a lógica linear não consiga resolver esse problema, isso não significa que o sistema de tipos e a estrutura lógica de uma linguagem de programação funcional não possam ser estendidos para permitir "seguro" e "eficiente"