Cálculo e Manipulação de Programas Circulares


Os programas circulares são um belo argumento usado em favor do poder
expressivo e da elegância associados a um paradigma lazy.  

Mais, foi demonstrado que qualquer algoritmo baseado numa estratégia
de travessias múltiplas sobre uma estrutura de dados pode ser
implementado como um programa circular, que apenas atravessa uma
estrutura de dados, e uma única vez.

Melhor ainda, quando um programador opta por este estilo de
programação, deixa de ter de se preocupar com a definição de
estruturas de dados intermédias, que seriam, segundo outras estilos,
essenciais para partilhar informação entre as múltiplas travessias
(recorde-se que, agora, existe apenas uma!). Ainda por cima, o
programador não tem de resolver o problema (não raras vezes complexo!)
de escalonar as diferentes travessias: determinar, por exemplo, que
valores necessitam estar computados para que uma determinada travessia
possa computar alguns outros. Este problema é resolvido, em tempo de
execução, pela máquina lazy.

No entanto, e porque a execução destes programas está tão
intrinsecamente associada a uma computacionalmente dispendiosa máquina
lazy, esta tende a ser mais lenta quando comparada com a execução de
seus equivalentes, escritos noutros estilos.

Nesta comunicação apresentarei o trabalho que tenho vindo a realizar,
e que permite a manipulação de programas circulares, e a sua
transformação em programas equivalentes, (comprovadamente) muito
eficientes, de forma totalmente automática e garantidamente correcta.

Este trabalho permite que um programador possa especificar os seus
algoritmos usando programação circular, para depois obter
implementações muito eficientes dos seus algoritmos; isto sem ter tido
o trabalho de definir estruturas de dados intermédias nem sequer de
determinar uma ordem de execução para as múltiplas travessias. 

Além do potencial acréscimo de trabalho, estas tarefas podem ainda
originar a introdução de erros.


Apesar de tudo, é costume apontar-se que é difícil escrever programas
circulares.

Neste sentido, apresentaremos também, nesta comunicação, regras de
cálculo, que provamos serem correctas, e que permitem derivar
programas circulares a partir de programas escritos à la MP1.

Estes programas circulares podem então ser, novamente, transformados
em programas equivalentes, muito eficientes.