Usos de estruturas de dados persistentes em linguagens não funcionais

Os idiomas puramente funcionais ou quase puramente funcionais se beneficiam de estruturas de dados persistentes porque são imutáveis ​​e se encaixam bem no estilo sem estado de programação funcional.

Mas, de tempos em tempos, vemos bibliotecas de estruturas de dados persistentes para linguagens (baseadas em estado, OOP) como Java. Uma afirmação frequentemente ouvida em favor de estruturas de dados persistentes é que, por serem imutáveis, são seguras para threads .

No entanto, o motivo pelo qual as estruturas de dados persistentes são seguras para thread é que, se um thread "adicionar" um elemento a uma coleção persistente, a operação retornará uma nova coleção como a original, mas com o elemento adicionado. Outros tópicos, portanto, veem a coleção original. As duas coleções compartilham muito estado interno, é claro - é por isso que essas estruturas persistentes são eficientes.

Mas como segmentos diferentes veem diferentes estados de dados, parece que as estruturas de dados persistentes não são suficientes para lidar com cenários em que um segmento faz uma alteração visível para outros segmentos. Para isso, parece que devemos usar dispositivos como átomos, referências, memória transacional de software ou mesmo mecanismos clássicos de bloqueio e sincronização.

Por que, então, a imutabilidade dos PDSs é apontada como algo benéfico para a "segurança de threads"? Existem exemplos reais de PDSs que ajudam na sincronização ou na solução de problemas de simultaneidade? Ou os PDSs são simplesmente uma maneira de fornecer uma interface sem estado para um objeto em suporte a um estilo de programação funcional?

Estruturas de dados persistentes / imutáveis ​​não resolvem problemas de concorrência por conta própria, mas facilitam muito a solução deles.

Considere um encadeamento T1 que passa um conjunto S para outro encadeamento T2. Se S é mutável, T1 tem um problema: ele perde o controle do que acontece com S. O thread T2 pode modificá-lo, portanto T1 não pode confiar no conteúdo de S. E vice-versa - T2 não pode ter certeza de que T1 não modifica S enquanto T2 opera nele.

Uma solução é adicionar algum tipo de contrato à comunicação de T1 e T2, de modo que apenas um dos encadeamentos possa modificar S. Isso é passível de erros e sobrecarrega o design e a implementação.

Outra solução é que T1 ou T2 clonam a estrutura de dados (ou ambas, se não estiverem coordenadas). No entanto, se S não for persistente, esse é um O (n) caro operação .

Se você tem uma estrutura de dados persistente, está livre dessa carga. Você pode passar uma estrutura para outro thread e não precisa se preocupar com o que ela faz com ele. Ambos os threads têm acesso à versão original e podem fazer operações arbitrárias - não influencia o que o outro thread vê.

Consulte também: estrutura de dados persistente vs imutável .

Por que, então, a imutabilidade dos PDSs é apontada como algo benéfico para a "segurança de threads"? Existem exemplos reais de PDSs que ajudam na sincronização ou na solução de problemas de simultaneidade?

O principal benefício de um PDS nesse caso é que você pode modificar uma parte dos dados sem tornar tudo único (sem copiar tudo em profundidade, por assim dizer). Isso tem muitos benefícios em potencial, além de permitir que você escreva funções baratas e sem efeitos colaterais: instanciar dados copiados e colados, sistemas triviais de desfazer, recursos triviais de reprodução em jogos, edição trivial não destrutiva, segurança trivial de exceção, etc. etc. etc.

Pode-se imaginar uma estrutura de dados que seria persistente, mas mutável. Por exemplo, você pode pegar uma lista vinculada, representada por um ponteiro para o primeiro nó, e uma operação de pré-adição que retornaria uma nova lista, consistindo em um novo nó principal mais a lista anterior. Como você ainda tem a referência ao cabeçalho anterior, é possível acessar e modificar esta lista, que também foi incorporada à nova lista. Embora possível, esse paradigma não oferece os benefícios de estruturas de dados persistentes e imutáveis, por exemplo, certamente não é seguro para threads por padrão. No entanto, ele pode ser usado desde que o desenvolvedor saiba o que está fazendo, por exemplo, para eficiência de espaço. Observe também que, embora a estrutura possa ser mutável no nível do idioma, nada impede que o código a modifique,

Para encurtar a história, sem imutabilidade (imposta pela linguagem ou por convenção), a persistência das estruturas de dados perde alguns de seus benefícios (segurança do encadeamento), mas outros não (eficiência de espaço para alguns cenários).

Quanto a exemplos de linguagens não funcionais, o Java String.substring() usa o que eu chamaria de estrutura de dados persistente. A String é representada por uma matriz de caracteres mais as compensações de início e fim do intervalo da matriz que é realmente usado. Quando uma substring é criada, o novo objeto reutiliza a mesma matriz de caracteres, apenas com os desvios iniciais e finais modificados. Como Stringé imutável, é (em relação aosubstring() operação, não a outras) uma estrutura de dados persistente e imutável.

A imutabilidade das estruturas de dados é a parte relevante para a segurança do encadeamento. Sua persistência (reutilização de chunks existentes quando uma nova estrutura é criada) é relevante para a eficiência ao trabalhar com essas coleções. Como são imutáveis, uma operação como a adição de um item não modifica a estrutura existente, mas retorna uma nova, com o elemento adicional anexado. Se toda vez que toda a estrutura for copiada, começar com uma coleção vazia e adicionar 1000 elementos um a um para terminar com uma coleção de 1000 elementos, criaria objetos temporários com 0 + 1 + 2 + ... + 999 = 500000 elementos no total, o que seria um enorme desperdício. Com estruturas de dados persistentes, isso pode ser evitado, pois a coleção de 1 elemento é reutilizada na de 2 elementos, que é reutilizada na de 3 elementos e assim por diante,

Eu sou reconhecidamente tendencioso como alguém que aplica esses conceitos em C ++ pela linguagem e sua natureza, assim como meu domínio e até mesmo pela maneira como usamos a linguagem. Mas, considerando essas coisas, acho projetos imutáveis são o aspecto menos interessante quando se trata de colher grande parte dos benefícios associados à programação funcional, como segurança de threads, facilidade de raciocínio sobre o sistema, encontrar mais reutilização de funções (e descobrir que podemos combiná-los em qualquer ordem, sem surpresas desagradáveis), etc.

Pegue este exemplo simplista de C ++ (reconhecidamente não otimizado para simplificar, para evitar me envergonhar na frente de qualquer especialista em processamento de imagem):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

Embora a implementação dessa função mude o estado local (e temporário) na forma de duas variáveis ​​de contador e uma imagem local temporária para a saída, ela não tem efeitos colaterais externos. Ele insere uma imagem e gera uma nova. Podemos multithread para o conteúdo de nossos corações. É fácil de raciocinar, fácil de testar completamente. É seguro para exceções, pois, se algo der errado, a nova imagem será descartada automaticamente e não precisaremos nos preocupar em reverter efeitos colaterais externos (não há imagens externas sendo modificadas fora do escopo da função, por assim dizer).

Vejo pouco a ganhar e potencialmente muito a perder, tornando Imageimutável no contexto acima, em C ++, exceto para potencialmente tornar a função acima mais difícil de implementar e possivelmente um pouco menos eficiente.

Pureza

Portanto, funções puras (livres de efeitos colaterais externos ) são muito interessantes para mim, e enfatizo a importância de favorecê-las com frequência para os membros da equipe, mesmo em C ++. Porém, projetos imutáveis, aplicados em geral apenas em contextos e nuances ausentes, não são tão interessantes para mim, pois, dada a natureza imperativa da linguagem, muitas vezes é útil e prático poder modificar alguns objetos temporários locais no processo de maneira eficiente (ambos para desenvolvedor e hardware) implementando uma função pura.

Cópia barata de estruturas robustas

A segunda propriedade mais útil que encontro é a capacidade de copiar, de maneira barata, as estruturas de dados realmente pesadas, quando o custo de fazê-lo, como normalmente seria incorrido para tornar as funções puras, dada sua natureza estrita de entrada / saída, não seria trivial. Não seriam pequenas estruturas que podem caber na pilha. Seriam estruturas grandes e pesadas, como toda aScene de um videogame.

Nesse caso, a sobrecarga de cópia pode impedir oportunidades de um paralelismo efetivo, porque pode ser difícil paralelizar a física e renderizar efetivamente sem travar e gargalhar uma à outra se a física estiver mudando a cena que o renderizador está tentando desenhar simultaneamente e, ao mesmo tempo, tendo uma profunda profundidade física. copiar toda a cena do jogo apenas para produzir um quadro com a física aplicada pode ser igualmente ineficaz. No entanto, se o sistema de física fosse "puro" no sentido de que apenas introduziu uma cena e produziu uma nova com a física aplicada, e essa pureza não custou a cópia astronômica aérea, ele poderia operar com segurança em paralelo com a física. renderizador sem um esperando pelo outro.

Portanto, a capacidade de copiar de maneira barata os dados realmente pesados ​​do estado do seu aplicativo e gerar novas versões modificadas com custo mínimo para processamento e uso da memória pode realmente abrir novas portas para a pureza e o paralelismo eficaz, e aí encontro muitas lições para aprender de como as estruturas de dados persistentes são implementadas. Mas tudo o que criamos usando essas lições não precisa ser totalmente persistente ou oferecer interfaces imutáveis ​​(ele pode usar a cópia na gravação, por exemplo, ou um "construtor / transitório"), para atingir essa capacidade de ser muito barato copiar e modificar apenas seções da cópia sem dobrar o uso e o acesso à memória em nossa busca por paralelismo e pureza em nossas funções / sistemas / pipeline.

Imutabilidade

Finalmente, há a imutabilidade que considero a menos interessante dessas três, mas ela pode impor, com mão de ferro, quando certos designs de objetos não devem ser usados ​​como temporários locais para uma função pura e, em um contexto mais amplo, um valioso tipo de "pureza no nível do objeto", pois em todos os métodos não causa mais efeitos colaterais externos (não altera mais as variáveis ​​de membros fora do escopo local imediato do método).

E embora eu considere o menos interessante desses três em linguagens como C ++, certamente pode simplificar o teste, a segurança de threads e o raciocínio de objetos não triviais. Pode ser uma carga de trabalho trabalhar com a garantia de que um objeto não pode receber nenhuma combinação de estado exclusiva fora do construtor, por exemplo, e que podemos distribuí-lo livremente, mesmo por referência / ponteiro, sem depender da constância e da leitura. apenas iteradores e manipuladores e tal, garantindo (bem, pelo menos o máximo que pudermos no idioma) que seu conteúdo original não será alterado.

Mas acho isso a propriedade menos interessante porque a maioria dos objetos que considero benéficos como sendo usados ​​temporariamente, de forma mutável, para implementar uma função pura (ou mesmo um conceito mais amplo, como um "sistema puro" que pode ser um objeto ou uma série de funciona com o efeito final de simplesmente introduzir algo e produzir algo novo sem tocar em mais nada), e acho que a imutabilidade levada às extremidades em uma linguagem amplamente imperativa é um objetivo bastante contraproducente. Eu o aplicaria com moderação nas partes da base de código em que realmente ajuda mais.

Finalmente:

[...] parece que estruturas de dados persistentes não são suficientes para lidar com cenários em que um thread faz uma alteração que é visível para outros threads. Para isso, parece que devemos usar dispositivos como átomos, referências, memória transacional de software ou mesmo mecanismos clássicos de bloqueio e sincronização.

Naturalmente, se o seu design exigir que modificações (no sentido do design do usuário final) sejam visíveis para vários threads simultaneamente à medida que ocorrem, voltamos à sincronização ou, pelo menos, à prancheta para descobrir algumas maneiras sofisticadas de lidar com isso ( Eu já vi alguns exemplos muito elaborados usados ​​por especialistas que lidam com esse tipo de problema na programação funcional).

Mas eu descobri que, uma vez que você obtém esse tipo de cópia e capacidade de produzir versões parcialmente modificadas de estruturas pesadas, como é o caso das estruturas de dados persistentes como exemplo, muitas vezes abre muitas portas e oportunidades que você pode não pensamos antes em paralelizar código que pode ser executado de forma completamente independente um do outro em um tipo de pipeline paralelo estrito de E / S. Mesmo que algumas partes do algoritmo precisem ser de natureza serial, você pode adiar esse processamento para um único encadeamento, mas descobrir que a inclinação desses conceitos abriu portas para facilitar e sem preocupação paralelizar 90% do trabalho pesado, por exemplo,