Scala

Estruturas de dados persistentes em Scala

Típicamente, quando falamos em persistência de objetos, nos referimos a seu armazenamento de longo prazo em algum tipo de banco de dados. No entanto, no paradigma de programação funcional, “estruturas de dados persistentes” tem um outro significado.

Antes de nos aprofundarmos no assunto vejamos um exemplo de estrutura de dados persistente:
val vetor = Vector[String]()
val vetor2 = vetor :+ "João"
val vetor3 = vetor2 :+ "Maria"
val vetor4 = vetor3 :+ "Homer Simpson"
println(vetor4)
// SAIDA> Vector(João, Maria, Homer Simpson)

Primeiro criamos um Vector imutável vazio, preparado para trabalhar com ítens do tipo String. O vetor é imutável, logo não podemos acrescentar-lhe valores: note que não só o nome ligado ao Vetor(vetor, vetor2, etc) é imutável, o próprio vetor o é. Como, então, acrescentamos ítens a esse vetor? A resposta é: copiando vetor e agregando-lhe um ítem ao início(usando +:) ou a seu fim usando :+. Foi o que fizemos nas linhas seguintes: vetor2 contém uma cópia de vetor com o nome João adicionado, vetor 3 tem a cópia dos dois anteriores mais a String “Maria”, e assim por diante.

À primeira vista, notamos que a cópia de um Vector que contenha grande quantidade de dados pode se tornar um processo demorado. Pior, a estrutura de dados anterior ficará solta na memória, sem qualquer uso. A essa estrutura que acabamos de copiar, para depois substituir, damos o nome de estrutura de dados persistente. Antes de falarmos dela, vamos examinar como, e onde, se originam.

Tipos referenciais e seus “ponteiros”
Em Scala tudo é um objeto. E nós sabemos, da especificação da JVM, que objetos são tipos referenciais, ou seja, quando passamos uma variável que referencia um objeto a uma função, sua referência é passada(um “ponteiro”) e não uma cópia do objeto. Em Java, objetos e tipos primitivos são dois conceitos distintos: os primeiros são passados por referência, os últimos por cópia de valor. Ou seja, quando passamos um int a uma função em Java, o valor do int é copiado. Porém se chamarmos uma função passando-lhe um objeto, a referência ao objeto(o ponteiro) será copiada, não o conteúdo do objeto. Desta forma dizemos que métodos em Java trabalham sempre com cópias dos parâmetros(“pass by value”), o que é verdade, mas causa confusão no caso de objetos pois sua referência é copiada, não o objeto em si. Então ao alterar o objeto dentro do corpo do método ao qual foi passado estaremos alterando também o objeto fora dele – mas não alteramos seu “ponteiro”(referências são ponteiros no fim das contas). Estes efeitos colaterais de objetos mutáveis geram incontáveis bugs e problemas de sincronização quando trabalhamos com várias Threads.

Scala não tem o equivalente a tipos primitivos. Todos os valores de Scala são tratados como referencias pela JVM. A linguagem Scala distingue entre tipos valorados(AnyVal) e tipos referenciais(AnyRef), mas esta é uma distinção da linguagem a qual é processada pelo compilador, e não da JVM. Ao ser compilado, os bytecodes da JVM podem ter apenas tipos primitivos e tipos referenciais.

Logo, ao adicionarmos um valor a um Vector imutável, o compilador obtém uma referência ao Vector original, agrega-lhe um item, e retorna o endereço do novo Vector que contém os ítens anteriores + o item agregado. O novo Vector pode ter sido otimizado para tentar reusar a cópia dos dados existentes no antigo Vector, o que evitaria a cópia de todos seus objetos. Porém esta é uma otimização, e não a forma como estruturas de dados persistentes funcionam na teoria.

Estruturas de dados persistentes
No exemplo acima, o que acontece então com as referências a vetor, vetor2 e vetor3, se iremos trabalhar apenas com vetor4? Estas persistem na memória até que o coletor de lixo(GC) identifique quais referências foram destruidas e podem ser descartadas, e quais ainda estão em uso.

Ao agregar os ítens “João”, “Maria”, inutilizamos pelo menos uma das referências antigas, as quais persistirão na memória até que o GC faça sua limpeza. Essas estruturas que “sobram” à partir da manipulação de dados imutáveis chamamos de estruturas de dados persistentes.

Preço da imutabilidade
Na Ciência da Computação, assim como na Física, existe um intercâmbio permanente entre espaço e tempo. Quando criamos um cache, estamos trocando tempo por espaço: tempo de processamento, por dados já processados ocupando mais espaço em memória para evitar novo processamento.

No caso contrário, quando programadores demoscene geram gráficos em tempo real, em vez de armazená-los em arquivos de imagens, estão trocando espaço por tempo, usando mais processador para gerar os gráficos, porém dando origem a minúsculos programas que geram suas próprias músicas e gráficos, sem gravar nada em arquivos.

A imutabilidade tem, também, seu preço. No caso, dados imutáveis consomem mas de ambos, espaço E tempo! O leitor talvez se pergunte, então qual é a contrapartida?

Esta é a grande questão na recente popularização das linguagens funcionais: com hardware cada vez mais barato, podemos nos dar ao luxo de desperdiçar memória e ciclos de processamento sem, em tese, aumentar demasiadamente o custo operacional. Tudo isso para termos sistemas mais confiáveis e algoritmos mais elegantes.

Os dados imutáveis tem diversas vantagens, as quais exigiriam alguns artigos para serem totalmente esgotadas. Em resumo, trata-se de permitir a ampla paralelização do processamento da informação e evitar pequenos defeitos oriundos de alterações inesperadas nos dados.

Dados imutáveis podem ser tratados como unidades indivisíveis: sabemos que não podem ser alterados, logo podemos contar com sua imutabilidade na hora de criarmos algoritmos multitarefa(se os dados não mudam, não precisamos nos preocupar com sicronização de acesso aos mesmos) os quais podem ser processados em lados opostos do mundo sem que seja exigida comunicação permanente entre os processadores.

Esta paralelização em grande escala deu origem a algoritmos como Map-Reduce, onde dados imutáveis são mapeados a máquinas distribuídas(processo Map) e posteriormente agregadas e sintetizadas em resultados usáveis(processo Reduce). O algoritmo MapReduce nada mais é que uma aplicação em grande escala de um conceito de programação funcional!

Conclusão
As estruturas de dados persistentes são um efeito colateral da programação funcional e do uso de dados imutáveis. O compilador Scala procura otimizar seu uso, minimizando o desperdício que ocorre naturalmente ao aplicarmos dados imutáveis. Em igualdade de condições, e sem aplicar otimizações, as estruturas de dados imutáveis tem performance inferior àquelas mutáveis. Porém, com a melhoria e ampla disponibilidade de hardware a baixos preços, podemos sacrificar um pouco de performance para obtermos sistemas mais confiáveis e algoritmos mais claros e elegantes.

Standard