Programação lógica ou declarativa é um paradigma bastante alienígena para programadores imperativos.

O paradigma de programação mais popular, programação imperativa, consiste em dar ordens ao computador que alteram o estado geral do sistema. É o mais popular por ser mais fácil e próximo do microprograma, que funciona de forma imperativa.

Porém nem de longe é o mais eficiente do ponto de vista da criação e da manutenilibidade, tendendo a gerar códigos de difícil manutenção e com maior densidade de bugs por linha de código.

Um concorrente do paradigma imperativo é a programação funcional, baseada no cálculo-λ, que resolve os problemas de integridade encontrados na programação imperativa com constraints.

Mas ainda há outro paradigma que difere da abordagem dos dois citados: a programação lógica, também chamada programação declarativa.

Enquanto na programação imperativa ordens alteram o estado da máquina e na programação funcional valores são passados através de cadeias de funções, na programação lógica é declarado um domínio de verdades, enquanto a execução em si consiste em “perguntas” (queries) feitas a esse domínio.

Ao contrário da programação imperativa, nenhuma ordem é dada ao sistema, apenas perguntas, e, ao contrário da programação funcional, efeitos colaterais são amplamente tolerados.

Esses efeitos colaterais vão desde comuncação I/O a até alterações no domínio de verdades – ou seja: o sistema pode aprender novas verdades.

O domínio de verdade consiste em um conjunto de predicados, e há duas formas de definir um predicado: dizendo se ele é verdadeiro ou falso, ou definindo o predicado como uma cadeia de outros predicados.

Como exemplo vamos determinar os valores da sequência de Fibonacci em programação lógica usando acumuladores, assim como fizemos no artigo sobre acumuladores em programação funcional.

Fibonacci

Vamos primeiro definir a sequência como um conjunto de verdades.

Como se trata de uma árvore binária, temos duas paradas, que são definidas como os dois primeiros valores da sequência sendo 1.

Em Prolog dizemos que é verdade que o elemento na posição 0 é igual a 1:

fibonacci(0, 1).

E que o elemento na posição 1 é igual 1:

fibonacci(1, 1).

Em seguinda, podemos definir o passo: cada elemento é a soma dos dois anteriores. Então, dado o elemento N, sendo N1 o anterior a ele e N2 o anterior a este segundo, podemos determinar os elementos nestas posições (R1 e R2), para então dizer que o resultado da posição N é a soma de R1 e R2:

fibonacci(N, R) :- succ(N1, N),
                   succ(N2, N1),
                   fibonacci(N1, R1),
                   fibonacci(N2, R2),
                   plus(R1, R2, R).

Já temos a definição lógica da sequência de Fibonacci! Porém de forma muito ineficiente, construindo uma árvore binária, empilheirando stacks de funções uns sobre os outros.

Para resolver o problema, precisamos fazer uma solução linear tirando proveito de TCO. Para tanto, usaremos dois acumuladores.

Acumuladores

Vamos descartar tudo o que fizemos até agora. Precisamos redefinir o cálculo como uma chamada para a função com acumuladores, passando os valores iniciais para os acumuladores. Como usaremos o segundo acumulador como resultado, o primeiro (descartado) conterá 0.

Também adicionaremos uma verificação de valor, para evitar a passagem de valores negativos:

fibonacci(N, R) :- N >= 0,
                   fibonacci(N, 0, 1, R).

Assim, o elemento na posição N é R se N for maior ou igual a zero e a última pergunta (fibonacci(N, 0, 1, R)) for verdadeira.

Agora vamos definir este último predicado. A parada pode ser definida como:

fibonacci(0, _, R, R) :- !.

Significa que, chegando a N valendo 0, ignora-se o primeiro acumulador e a resposta é igual ao segundo acumulador. o Sinal ! indica que, se o caso bater com esta definição, ignorar qualquer outra; o símbolo _ indica que o parâmetro deve ser ignorado.

O passo pode ser definido como: N1 é o antecessor de N – ou melhor, N é o sucessor de N1, AB é a soma dos acumuladores A e B, e para o índice N1 o primeiro acumulador é B e o segundo AB:

fibonacci(N, A, B, R) :- succ(N1, N),
                         plus(A, B, AB),
                         fibonacci(N1, B, AB, R).

Já temos a sequência e podemos testá-la:

sh$ swipl -q
?- [fibonacci].
true.

?- fibonacci(5, X).
X = 8.

Cadeia de predicados

Também podemos definir a função como uma cadeia de predicados, usando a sintaxe -->.

Precisaremos instalar o pacote lambda:

?- pack_install(lambda).

E no código fibonacci.pl:

:- [library(lambda)].

Reescrevendo a parada:

fibonacci(0, _) --> '='.

A sintaxe --> entende que o predicado recebe dois parâmetros extra: o resultado do predicado anterior da cadeia e o valor a ser passado para o próximo predicado.

Por exemplo:

d --> a(1), b, c(test).

é o mesmp que:

d(P1, R) :- a(1, P1, R1),
            b(R1, R2),
            c(test, R2, R).

'=' é o mesmo que garantir igualdade: '='(P1,R), ou P1 = R.

Precisamos abordar cada predicado da cadeia e convertê-lo nesse formato.

Aqui temos dois problemas (solucionáveis): o primeiro predicado define o valor de N1 sem alterar a cadeira. Para isso usamos {}:

{ succ(N1, N1) },

Segundo precisamos guardar o valor do segundo acumulador em um slot qualquer, por isso precisamos da biblioteca lambda: pegar B e repassá-lo para o próximo predicado da cadeia:

call(\B^B^B^(true), B),

Isso equivale ao lambda λbbb.TRUE atribuindo o valor dos parâmetros (idênticos) a B. Os dois últimos predicados (plus/3 e fibonacci/4) já estão organizados para receber e repassar ao cumulador:

fibonacci(N, A) --> { succ(N1, N) },
                    call(\B^B^B^(true), B),
                    plus(A),
                    fibonacci(N1, B).

Testando:

?- [fibonacci].
true.

?- forall(between(0, 10, X), (fibonacci(X, F), writeln({X, F}))).
{0,1}
{1,1}
{2,2}
{3,3}
{4,5}
{5,8}
{6,13}
{7,21}
{8,34}
{9,55}
{10,89}
true.