>

Programas Circulares

Introdução

Introduzido originalmente como demonstração do poder da lazy evaluation nas linguagens funcionais nos anos 80, os programas circulares são considerados como uma técnica poderosa, concisa, eficiente e elegante para resolver um particular tipo de problema. Se um algoritmo tiver de percorrer uma estrutura de dados várias vezes, numa linguagem de avaliação atrasada, o mesmo poderá ser expresso com uma única travessia.

Como o nome indica, programas circulares caracterizam-se por a sua definição ter uma aparência circular, isto é, um dos argumentos de uma função depende de um dos argumentos que a mesma função retorna x = f(x). Apesar de um programa circular, numa linguagem com strict evaluation nunca irá terminar, enquanto que numa linguagem lazy às vezes conseguirá terminar. A avaliação atrasada irá sempre obter a ordem correcta de processamento, se essa ordem de facto existir. Assim, a função f pela sua definição será virtualmente circular, já que no momento da sua avaliação irá ser decomposta em não circular.

No entanto, também é sabido que os programas circulares são difíceis de entender e escrever. Facilmente o programador define um programa realmente circular, ou seja, que nunca termine. Mas deixemos de conceitos teóricos e passemos para algo mais prático. Por uma questão de hábito e facilidade de demonstração, a linguagem usada irá ser Haskell.

RepMin

Comecemos pelo exemplo clássico repmin, o problema é o seguinte.

Imaginemos que temos uma árvore binária de folhas, queremos obter uma nova árvore morfologicamente idêntica à original, mas agora todas as suas folhas terão que ter o valor mínimo da árvore original.

Programas Circulares: transformação de árvore

Resolução Normal (Múltiplas travessias)

Em Haskell podemos definir uma árvore binária de folhas da seguinte forma.

data Arvore = Folha Int          -- Uma folha terá um valor que será um inteiro
            | Nodo Arvore Arvore -- Um nodo terá duas sub-árvores

Agora para resolver o problema iremos criar a função transforma que irá pegar numa árvore e devolver uma nova árvore.

transforma :: Arvore -> Arvore
transforma arv = replicaArv arv (minArv arv)

Como podemos constatar a função transforma irá dar uso a duas funções.

A função minArv irá calcular o valor mínimo de uma árvore.

minArv :: Arvore -> Int
minArv (Folha x) = x
minArv (Nodo e d) = min (minArv e) (minArv d)

A função replicaArv irá replicar uma dada árvore com um valor mínimo.

replicaArv :: Arvore -> Int -> Arvore
replicaArv (Folha _) m = Folha m
replicaArv (Nodo e d) m = Nodo (replicaArv e m) (replicaArv d m)

Como podemos ver, a árvore irá ser percorrida duas vezes. Uma primeira vez para obter o valor mínimo da árvore e uma segunda vez para replicar a árvore com o valor mínimo.

Resolução Circular (Uma travessia)

Vejamos agora como podemos transformar o código de cima ficando um programa circular. A forma mais simples de efectuar essa transformação é recorrendo à fusão das duas funções através do uso de tuplos. Portanto começamos a definir a função repmin como o par das funções replicaArv e minArv. A nossa função repmin irá receber uma árvore e um hipotético valor mínimo.

repmin :: (Arvore, Int) -> (Arvore, Int)
repmin (a, m) = (replicaArv a m, minArv a)

Vamos agora tentar fundir as duas funções, simplificando o código. Ora uma árvore pode ser folhas ou nodos, portanto temos que ter os dois casos. Comecemos pelas folhas por ser mais simples. Então caso seja uma folha, a linha de cima fica da seguinte forma:

repmin ((Folha x), m) = (replicaArv (Folha x) m, minArv (Folha x))

Usando a definição de replicaArv e minArv obtemos um código equivalente, simplificando-o ainda mais.

repmin ((Folha x), m) = (Folha m, x)

Simples. Vejamos agora no caso de ser um nodo.

repmin ((Nodo e d), m) = (replicaArv (Nodo e d) m, minArv (Nodo e d))

Mais uma vez, usamos as definições das funções replicaArv e minArv.

repmin ((Nodo e d), m) = (Nodo (replicaArv e m) (replicaArv d m), min (minArv e) (minArv d))

Agora o passo seguinte poderá não parecer tão intuitivo. Mas visto que tanto a função replicaArv como a função minArv seguem o mesmo padrão de recursividade, podemos usar a própria definição de repmin para simplificar ainda mais o código.

repmin ((Nodo e d), m) = (Nodo e' d', min m1 m2)
  where (e', m1) = repmin (e, m)
        (d', m2) = repmin (d, m)

Bem, caso se for um Nodo também não há muito mais a fazer. Recapitulemos como temos definido a nossa função repmin:

repmin :: (Arvore, Int) -> (Arvore, Int)
repmin ((Folha x), m) = (Folha m, x)
repmin ((Nodo e d), m) = (Nodo e' d', min m1 m2)
  where (e', m1) = repmin (e, m)
        (d', m2) = repmin (d, m)

Porreiro. Dado uma árvore e um hipotético valor mínimo, replica essa árvore com esse valor hipotético e ao mesmo tempo calcula o valor mínimo da árvore, tudo em apenas uma travessia. Agora fixe fixe era conseguirmos dizer que aquele valor hipotético era o valor mínimo calculado por nós. E é aqui que entra a função circular, redefinamos então a função transforma para nos permitir tal proeza.

transforma :: Arvore -> Arvore
transforma arv = arv'
  where (arv', m) = repmin (arv, m)

E está feito. De salientar o uso do símbolo m nos dois lado da função repmin, ou seja, é ao mesmo tempo o argumento e o resultado da função. No momento de execução da função transforma, o Haskell devido a ser lazy como que por magia irá transformar a árvore com um valor que só terá acesso no futuro, é como se fosse possível viajar no tempo.

Arrows

O exemplo foi feito de forma a demonstrar totalmente o processo de converter o código para a versão circular. Na verdade, o último passo é desnecessário. Haskell possui Arrows, um conceito similar às populares Monads mas mais generalista. Ora com arrows uma pessoa consegue com bastante facilidade descrever e conjugar computações. E como já devem estar à espera, existe uma arrow já pré-definida na biblioteca para o nosso caso. Essa arrow tem de nome loop e tem o seguinte esquema:

Programas Circulares: esquema da arrow loop

A função loop é em si uma arrow que possui internamente uma outra arrow que dado um input irá devolver um output com um auxílio de um feedback. Como podem reparar este feedback irá ser a nossa referencia circular.

 

Do ponto de vista do Haskell, a função loop tem a seguinte assinatura:

loop :: (Arrow a) => a (b, d) (c, d) -> a b c

Analisando a assinatura, podemos ver que a arrow interna tem de ser do tipo a (b, d) (c, d). Vamos ter o input do tipo b , o output do tipo c e o feedback será do tipo d. No fim vamos ter como resultado a arrow a b c, ou seja, uma computação que dados as devolve bs. Vejamos como podemos usar isto no nosso caso.

Já que estamos a trabalhar apenas com funções, para começar podemos dizer que a nossa Arrow a é uma função (->). Então loop fica do seguinte tipo:

loop :: ( (b, d) -> (c, d) ) -> (b -> c)

Visto que o nosso input e output irão ser árvores, portanto o nosso b e c irão ser do tipo Arvore. O feedback irá ser o nosso hipotético valor mínimo, ou seja, o d será um Int. Fazendo estas substituições na assinatura do loop ficamos com.

loop :: ( (Arvore, Int) -> (Arvore, Int) ) -> (Arvore -> Arvore)

Já está mais agradável. A função loop recebe como argumento uma função e devolve outra função. Se vermos com atenção, vimos que a assinatura desta função (a de argumento) é exactamente a mesma que a da nossa função repmin. De facto, para pormos a função repmin como circular basta passar para a função loop como argumento. Visto isto, podemos redefinir a nossa função transforma usando a biblioteca Control.Arrow.

transforma :: Arvore -> Arvore
transforma = loop repmin

Média

Agora que já demonstramos um método simples de como transformar um programa com múltiplas travessias em apenas uma, vamos ver outro exemplo clássico, pois este método simples está longe de ser perfeito. E que nem sempre produz resultados ideais. Mas que se nós estivermos atentos facilmente podemos contornar o problema. Temos então o seguinte problema.

Dado uma lista de valores, queremos calcular a média da lista, e de seguida incrementar cada valor da lista pela média obtida.

Assim de imediato vemos que temos três travessias na lista. Uma travessia para calcular o número de elementos na lista, uma segunda travessia para somar os elementos da lista e uma terceira travessia para incrementar cada valor da lista pela média. De salientar que a primeira travessia e a segunda travessia não dependem uma da outra e portanto é muito simples fazer a sua fusão e é apenas necessário uma travessia. Mas não é esse o ponto em questão, e é para reforçar a ideia, que para cada posição da lista temos que efectuar três operações. Bem, não vou estar agora a fazer passo a passo, mas à primeira tentativa o mais provável era obtermos algo do género.

transforma :: [Double] -> [Double]
transforma = loop incrMedia
 
incrMedia :: ([Double], (Double, Double)) -> ([Double], (Double, Double))
incrMedia ([], _) = ([], (0,0))
incrMedia ((x:xs), (soma, numElems)) = ( (x + media) : xs', (soma' + x, numElems' + 1))
  where (xs', (soma', numElems')) = incrMedia (xs, (soma, numElems))
        media = soma / numElems

O problema deste código é que se formos executar com uma lista nunca irá terminar. O problema está no cálculo da média em todo os passos. Podemos solucionar este problema separando o cálculo da média da travessia da lista, isto é, já termos o nosso feedback (a média) já calculada. A versão correcta seria então.

transforma :: [Double] -> [Double]
transforma = loop incrMedia
 
incrMedia :: ([Double], Double) -> ([Double], Double)
incrMedia (lista, media) = (lista', soma / total)
  where (lista', (soma, total)) = incrMedia' (lista, media)
 
incrMedia' :: ([Double], Double) -> ([Double], (Double, Double))
incrMedia' ([], _) = ([], (0, 0))
incrMedia' ((x:xs), media) = ((x + media) : xs', (soma + x, total + 1))
  where (xs', (soma, total)) = incrMedia' (xs, media)

Como podemos verificar as duas soluções são muito parecidas, mas na última versão inserimos uma função extra no meio para separar o cálculo da média da travessia da lista. É necessário, visto que se tivermos um valor hipotético de média, a assinatura da função não encaixa, já que a cada passo o feedback irá ser o somatório e a contagem dos elementos da lista. Daí termos uma função extra para servir de adaptador, para o nosso feedback ter o mesmo tipo, tanto à entrada como à saída.

Já que uma pessoa está a usar Arrow pode sempre por o código ainda mais conciso, apesar de se tornar um pouco menos legível. Fica ao gosto de cada um a forma que prefere.

transforma :: [Double] -> [Double]
transforma = loop (incrMedia >>> id *** uncurry (/))
 
incrMedia :: ([Double], Double) -> ([Double], (Double, Double))
incrMedia ([], _) = ([], (0, 0))
incrMedia ((x:xs), media) = incrMedia 
                          >>> ((x + media):) *** ((+x) *** (+1)) 
                          $ (xs, media)

Conclusão

Este artigo está a chegar ao fim. Tinha como objectivo dar a conhecer o conceito de programas circulares e espero que tenha tido sucesso. Foi feita apenas uma pequena introdução do conceito, com o auxílio de um método muito simples de transformação de programas. O método aqui indicado tem várias falhas.

  • Nem sempre se obtêm um programa circular válido, que termine.
  • As várias travessias tem de seguir o mesmo padrão recursivo.
  • Devido ao ponto anterior, as travessias tem de ser sempre sobre a mesma estrutura de dados.

O último ponto é bastante importante. Muitos casos tornam necessário a formação de estrutura de dados intermédia entre as várias travessias. Por exemplo, no caso do exemplo da média, se quiséssemos que a lista obtida estivesse ordenada, então o mais normal era usar como uma estrutura intermédia uma árvore binária e implementar algo tipo o QuickSort ou MergeSort. Este novo problema deita logo abaixo o nosso método simples. Para quem tiver interessado recomendo que pesquise um pouco, esta é uma área com alguma investigação e existem vários papers onde são abordados novos métodos (mais complexos que não se enquadram neste artigo), mas que ultrapassam estes problemas referidos. De salientar, que apesar de ser uma área um pouco obscura, já começa a ver-se alguns casos práticos de programas circulares. Sendo os mais usuais, o pretty-printing em que são necessárias várias travessias por questões de formatação ou então compiladores em que também é necessário várias travessias para calcular por exemplo os endereços de jump.

Extras