Skip to content

O caso de Enumerable infinito

13 de Maio de 2014

No ultimo ano tenho trabalhado bastante com o conceito de  lambdas e monads. Em particular o conceito de monads aplicados a filtrar e transformar coleções.
Comecei a pensar como isso poderia ser trazido para o Middleheaven. Isto foi antes do java 7  e nesse momento não existia java 8 e o conceito de Stream.

A verdade é que esse conceito é maior que as linguagens e está presente em muitas delas. Aliás está presente na Apache Commons Collection desde o inicio.

O conceito é simples, você começa com uma coleção qualquer, transforma para um objeto que suporte operações de filtro/transformação – normalmente usando algum tipo de decorador. Configura os filtros/transformações através de métodos encadeados, como se fosse um construtor e no fim executa tudo de uma vez só em uma mistura de Command e Composite.

A vantagem disto é que o fluxo pode ser bem complexo mas apenas um único for será executado. É a versão moderna de “for is evil”. Tradicionalmente em java fazemos todas as iterações explicitamente usando for, mas existem grandes vantagens em utilização repetição implícita. A principal delas é que podem existir otimizações ou o uso de processamento paralelo pode ser usado

O principal era ter uma classe que suportasse operações de filtro/transformação. Hoje existe o Stream em java, mas na época o Middlheaven ganhou o Enumerable. Foi difícil achar um nome porque a maioria dos nomes que se adequariam já estão tomados. O nome foi emprestado da API de C#. O Enumerable é um Iterable que permite mais operações, como filter e map.

Conceptualmente o Enumerable pode ter infinitos elementos. Isto é uma propriedade comum neste tipo de objetos e é seguida pelo objeto Stream do java 8 e a sua contraparte IEnumerable no C#. Pelo menos em teoria.
Mas ao implementar a API comecei a notar que muitos dos algoritmos dependiam de usar o atributo size para saber quando elementos existiam no Enumerable. Ora, isto, conceptualmente estava errado, porque não ha tamanho quando ha infinitos elementos.
O IEnumerable e o Stream resolvem isto com exceções, mas não me parecia uma forma elegante. Procurei por ai, como resolver isto.

Achei uma palestra meio louca e assustadora sobre Scala, em que no meio de muita confusão ha duas ou três coisas interessantes. Uma delas, é exactamente lidar com o tamanho infinito.
O truque é encapsular o tamanho em uma classe e utilizar a class para prever o tamanho, mas sem nunca o calcular, pois. Isto nos trás ao conceito de tipos de tamanho: determinável e desconhecido.
O tipo determinável pode ser ainda : infinito, contável e calculável. Infinito significa que não existirá fim para a enumeração. Contável significa que podemos obter o tamanho com complexidade O(1), como acontece se realmente o nosso Enumerable apenas está encapsulando um List – que acontece a grande maioria das vezes.
E finalmente calculável, que significa que é possível terminar a enumeração e saber quantos elementos tem, mas ao custo de iterá-los a todos (uma operação que nos custará O(n) onde n é tamanho que queremos determinar).

Mas ai nasceu um outro problema. Para os tipos contável e calculável é possível ter uma propriedade que nos retorna o tamanho. Contudo, sendo que podem haver muitos elementos, que tipo de dado escolher? int ? long ? bigInteger ?

Parece um pouco exagerado ter que usar BigInteger para retornar o tamanho de Enumerable, mas o fato é que realmente pode ser muito grande. Grande demais para um int ou um long. Mas isto é em teoria, na prática, a maioria dos casos é o encapsulamento de um Collection qualquer que é a base da iteração. Na prática int seria suficiente, mas em teoria não, o que quebraria a API.

Seria possível remover o conceito de que o Enumerable pode ser infinito, isto simplificaria muito a API e poderiamos remover o conceito de que pode ter mais elementos que Integer.MAX_VALUE, contudo o futuro é de máquinas com 64 bits ou mais. Poderíamos usar long. É um bom valor quando estamos retornando dados de um banco, por um tempo será suficiente. Contudo, mesmo assim travaríamos o contrato da API.

A solução foi apelar para um outro componente do MiddleHeaven, o Numeral. Em particular aquele que representa um numero inteiro.. Numeral é uma representação abstrata de um número com três sub tipos até agora, inteiro, decimal e complexo – representados pelos tipos BigInt, Real e Complex. O BigInt é um Numeral que pode representar números inteiros.
Dei-me conta que este nome é meio confuso. A ideia do nome é porque ele representava um numero de 64 bits maior que um int e por isso o Big. Mas se confunde com BigInteger. Sendo assim resolvi mudar o nome para Int.  E assim temos os tipos Int, Real e Complex.

O MiddleHeaven desacopla o modelo abstrato da quantidade da sua representação.  Int, Real e Complexa são classes abstratas e a classe que realmente representa o valor não é pública. A implementação concreta para representar o Int era a classe LongInteger que usava um long como forma interna de guardar o valor, para representação e base da aritmética. Contudo ocupa 64 bits a todo o momento, quando a maior parte das vezes só precisamos de 32 bits, ou menos. O ideal era ter um tipo que fosse aumentando conforme necessário. Isto, aliado à necessidade de ter um range extenso para o tamanho de um Enumerable trouxe a ideia de um range dinâmico. Assim o  Enumerable retorna um EnumerableSize que têm vários sub tipos e para os que podem obter o valor do tamanho com exactidão, eles retornam um Int.

Porque a construção de qualquer Int passar por um método de fábrica valueOf é o método que determina qual a classe que melhor se adéqua ao valor a representar. O mais baixo é um int de 32 bits representado pela class Int32 ( é dificil arranjar nomes para tanta classe, então simplesmente coloquei o numero de bits na frente – à lá .NET style. Contudo, porque esta classe é privada ao pacote o nome realmente não interessa muito)
Sempre que for feita uma operação em que se obtenha um numero que não cabe em 32 bits, ou seja, quando acontece um overflow, automaticamente os valores são promovidos a Int64. Se o mesmo acontecer com os valores em Int64, eles serão promovidos a BigInt.  BigInt é a implementação de Int que se utiliza de um BigInteger internamente. Teoricamente BigInteger pode conter um número de qualquer tamanho (a custo de operações aritmética mais lentas). A partir dai, se existir um problema de oveflow uma exceção será lançada. Para que isso acontece é preciso um número seja realmente absurdamente astronômico. Isto permite que o tamanho de Enumerable seja igualmente astronômico.

O próximo passo poderia ser criar e usar Int8 e/ou Int16 e ir promovendo à medida que necessário já que maioria dos números que nos interessam estão nesse limite.

Este caso é muito semelhante ao que a JVM faz com os primitivos. Ela permite que os menores sejam usados como se fossem os maiores através de promoção automática. A diferença é que ao fazer uma operação com um tipo de numero e perante um overflow não acontece uma promoção automática, mas sim algo inesperado. Para todos os inteiros de n bits , ao somar 1 ao maior inteiro de n bits obtemos o menor inteiro de n bits. E ao subtrair 1 do menor inteiro obtemos ele mesmo! Sim. É verdade, obtemos ele mesmo.
Na realidade é pouco mais complicado que isso, porque para fazer cálculos a VM sempre promove os valores para int e depois dos cálculos coloca de volta no tipo original. O problema é que pode ser que o resultado não caiba de volta no tipo original. Não ha nenhum mecanismo de auto-promoção durante os cálculos.Nem poderia, já que os tipos primitivos não são polimórficos.

O que o Int oferece é encapsulamento e polimorfismo para resolver isto. O tipo concreto do objeto passa de um sutipo de Int para o outro sem que o programador note, pois ele sempre trabalha com a classe Int. Assim é sempre garantida a correta representação do valor.Esta propriedade não existia antes com o LongInteger porque , ao ser baseado num long, tinha os mesmos problemas aritméticos que o long primitivo.

Alguns algoritmos passaram a ser impossíveis caso o Enumerable seja infinito, como por exemplo colocar o Enumeble em um ArrayList ( que só pode conter Integer.MAX_VAlUE valores) ou executar sort(). Contudo, existem rumores para a criação de uma API de arrays de 64bits em futuras versões do java o que indica
que o limite do array não é em si mesmo, constante.

Tudo isto pode parecer desnecessário, mas é realmente um problema conceptual que pode danificar uma API (como vimos no exemplo do Scala). A nova API de Datas e Tempos do java é a prova que são necessárias APIs mais corretas e com melhores abstrações e a nova api JSR 354 de Money and Currency que está na forja para o Java 9, segue o mesmo caminho. Inclusive cai no mesmo problemas de tipos abstratos para valores numéricos, sendo obrigada a definir um novo tipo de Number, o Decimal, que seria um objeto capaz de presentar o mesmo que um long tanto em casas inteiras como em casas decimais.
Um BigDecimal seria demasiado devido à performance necessária, e um double não é suficiente para esta façanha pois não pode representar corretamente todos os números neste intervalo. Todas as potencias negativas de 10 são dizimas infinitas em base 2, o que leva a problemas para representar 0.10 e 0.01 centavos. Aliás este problema é toda a base para a necessidade uma API de Money e por isso que o MiddleHeaven também tem a sua.
Infelizmente a api de Money está planejada para trabalhar com arredondamentos em divisões intermediárias, enquanto a API do Middleheaven usa o padrão Ratio para evitar divisões em todos os passos até ao fim. Para isso o objeto Money faz uso de um Real para o seu valor, pois o Real é implementado com padrão Ratio como a divisão de dois BigInteger (e agora acabando de escrever isto, acabo de ver que Real deveria ser implementado como a fração de dois Int e não de dois BigInteger…).

Com o tempo verifiquei que a necessidade do valor do Money ser um Real não deriva apenas do padrão Ratio, e sim do fato que embora, conceptualmente o Money represente um valor finito de centavos, em algumas contas- como o calculo de juros , essa regra não
é simples de aplicar pois a aritmética exige o uso de números reais nos calculos resultando em números com várias casas decimais. Bom, mas a história do Money é outra história para outro dia…

Achei que o caso do refatorar o Int era um caso interessante de como uma parte do MiddleHeaven – o Enumerable – ajudou a encontrar problemas conceptuais em outra parte – o Numeral, em particular o Int. Isto porque quis me manter fiel ao conceito de um um Enumerable pode ter uma valor astronômico de elementos, inclusive, infinitos, mas sem cair no custo de usar sempre BigInteger – bom, pelos menos não até que seja realmente necessário.

 

Deixe um Comentário

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s

%d bloggers like this: