Recursão, corte e procura em Prolog

Para somar [1,2,3], primeiro resolvemos a soma da cauda e só depois avaliamos a adição. Isto distingue o cálculo aritmético com is da unificação de termos com =. Mais adiante, os mesmos mecanismos de procura permitem enumerar caminhos num labirinto.

Listas e aritmética

Listas usam [Cabeça|Cauda], como o (x:xs) do Haskell. Somar uma lista é caso base mais passo recursivo:

soma([], 0).
soma([H|T], S) :- soma(T, R), S is H + R.

Cada chamada usa variáveis frescas. A consulta soma([1,2,3],S) espera o resultado R1 de soma([2,3],R1); esta espera R2 de soma([3],R2), que espera R3 de soma([],R3).

O caso base liga R3=0. No regresso calculamos R2 is 3+0, R1 is 2+3 e S is 1+5, obtendo S=6. O is avalia o lado direito como expressão aritmética e unifica com a esquerda, pelo que sem ele S = H + R ligaria S à expressão por avaliar em vez do número. Todas as variáveis do lado direito têm de estar ligadas quando ele corre; para comparar resultados numéricos, usa =:=.

Corte e findall

Por omissão, o Prolog explora todas as alternativas ao pedir mais soluções. O corte, !, poda: descarta escolhas criadas desde a entrada no predicado até ao corte e as cláusulas alternativas desse predicado. Objetivos à direita ainda podem ter várias soluções.

maximo(X, Y, X) :- X >= Y, !.
maximo(X, Y, Y) :- X < Y.

Com o corte, maximo(3, 5, M) usa a primeira cláusula, falha no teste, e o corte nunca chega a correr; a segunda dá M = 5. Com maximo(7, 5, M), o teste passa, o corte elimina a segunda cláusula, e M = 7 sem deixar alternativa pendente. Este corte é verde nesse contrato, ou seja retirá-lo não acrescenta uma resposta lógica. Um corte que mude respostas é vermelho.

Contrasta com um corte vermelho, que decide antes de testar:

mau_maximo(X, Y, X) :- !.
mau_maximo(X, Y, Y) :- X < Y.

A query ?- mau_maximo(3, 5, M). responde M = 3, que está errado. Compara os conjuntos de respostas no modo (+,+,-):

O corte é vermelho porque altera o conjunto de respostas, mas a resposta errada 3 já existe sem corte, pela primeira cláusula, que decide sem comparar. A posição do teste, por si só, não define a cor do corte; no maximo verde, retirar o corte não acrescenta respostas lógicas nesse contrato.

Para juntar todas as respostas numa lista em vez de as pedir uma a uma, usa findall:

?- findall(C, pai(ana, C), Cs).
Cs = [leo].

O segundo argumento é o objetivo, o primeiro diz o que colecionar de cada solução. Com os factos da página anterior, só leo é filho da Ana.

Caminhos e visitados

Modela o labirinto como ligações e procura um caminho acumulando visitados para não andar em círculos:

ligado(a, b). ligado(b, c). ligado(b, d). ligado(c, e). ligado(d, e).

caminho(X, X, _, [X]).
caminho(X, Z, Visitados, [X|Resto]) :-
  ligado(X, Y),
  \+ member(Y, Visitados),
  caminho(Y, Z, [Y|Visitados], Resto).

A query ?- caminho(a, e, [a], C). faz procura em profundidade: de a vai a b (única saída); de b tenta c primeiro (ordem das cláusulas); de c chega a e, que unifica com o caso base. Responde C = [a, b, c, e]; ao pedir mais soluções retrocede até b, tenta d, e encontra [a, b, d, e].

soma([], 0).
soma([H|T], S) :- soma(T, R), S is H + R.

maximo(X, Y, X) :- X >= Y, !.
maximo(X, Y, Y) :- X < Y.

main :- soma([1,2,3], S), write(S), nl, maximo(7, 5, M), write(M), nl.

No grafo finito, cada passo visita um estado novo no caminho, por isso não podemos prolongá-lo indefinidamente. O caso base produz a resposta ao chegar ao destino. A ordem dos factos decide qual caminho é tentado primeiro, mas não substitui a condição de progresso.

SICStus na aula, SWI em casa

O Prolog da cadeira é o SICStus e o do navegador destas páginas é o SWI; a sintaxe base das cláusulas é comum, mas os predicados de biblioteca e de escrita diferem. Para escrita portátil, usa write/1 e nl/0. Alguns exemplos no navegador usam writeln/1, identificado aqui como a forma SWI; não assumes que todas as bibliotecas se carregam da mesma maneira. O que muda é o ambiente:

:- use_module(library(lists)).

Uma relação pode funcionar em vários sentidos

juntar([], Ys, Ys).
juntar([X|Xs], Ys, [X|Zs]) :- juntar(Xs, Ys, Zs).

juntar([a,b],[c],Z) constrói [a,b,c]; juntar(X,Y,[a,b]) procura divisões: X=[],Y=[a,b]; X=[a],Y=[b]; X=[a,b],Y=[], ou seja a mesma relação serve para construir e decompor. Uma função com is pode perder essa reversibilidade, porque o lado direito exige números conhecidos.

Definir membro por membro(X,[X|_]). e membro(X,[_|T]) :- membro(X,T). produz uma resposta por ocorrência. Com [a,b,a], há duas provas de membro(a,...), mesmo que a substituição seja a mesma. A base de conhecimento não é automaticamente um conjunto de respostas sem repetições.

Aritmética e identidade

As operações respondem a perguntas diferentes:

X = Y pode criar uma ligação entre variáveis. X == Y apenas testa se já são o mesmo termo.

Uma desigualdade por não unificação, X \= Y, falha se os termos puderem ser unificados agora. Com as duas variáveis livres, falha, embora depois pudéssemos dar-lhes valores diferentes. dif(X,Y) em SWI-Prolog adia a restrição de diferença. Para escrever código portátil para a cadeira, distingue estes contratos e confirma os predicados disponíveis no SICStus.

Modos de chamada e is

Documenta cada predicado com o modo, por exemplo soma(+ListaDeNumeros, -Total): com saída livre, soma([1,2,3],S) calcula S=6, e com saída instanciada, soma([1,2,3],6) confirma enquanto soma([1,2,3],5) falha. soma([1,X],6) não resolve uma equação para X, pois chega a is com um operando desconhecido e produz um erro de instanciação. Os modos indicam como usar o predicado, mas não são declarações de tipo verificadas pelo motor.

Acumuladores e terminação

A soma recursiva desta página faz primeiro a soma da cauda e depois a adição. Uma versão com acumulador transporta o total parcial:

soma_acc(Xs,S) :- soma_acc(Xs,0,S).
soma_acc([],A,A).
soma_acc([X|Xs],A,S) :- B is A+X, soma_acc(Xs,B,S).

Com uma lista finita de números, o comprimento da lista diminui até zero; com uma lista livre, este programa pode tentar gerar listas e acabar numa expressão aritmética com uma variável desconhecida. Documenta o modo esperado, por exemplo soma_acc(+ListaDeNumeros,-Total).

Reconhecer um corte vermelho

Se a segunda cláusula de maximo fosse apenas maximo(_,Y,Y), retirar o corte permitiria também devolver Y quando X fosse maior. O corte corrigiria a escolha naquele modo, mas alteraria as respostas lógicas: seria vermelho. Há ainda um contraexemplo com resultado já preenchido: maximo(7,5,5) pode saltar a primeira cabeça e ter sucesso na segunda. A versão desta página conserva a guarda X < Y e recusa essa resposta errada.

Usa cortes depois de conhecer o conjunto de respostas sem eles. Desenha que escolhas cada corte elimina, verifica objetivos à direita e testa resultados já instanciados. A aparência de determinismo numa só consulta não prova correção nos restantes modos.

Negar a existência de um irmão

Suponhamos uma base finita que regista as crianças Ana, Bruno e Rui uma vez em crianca/1. Tomás é pai de Ana e Bruno; Inês é mãe apenas de Ana; José e Maria são os pais de Rui. Nesta base, Ana e Bruno têm um irmão por partilharem Tomás, mesmo não tendo ambos os pais em comum.

Para procurar crianças sem irmãos, gera primeiro uma criança e só depois pergunta se existe algum progenitor partilhado com outra:

sem_irmaos(P) :-
    crianca(P),
    \+ (progenitor(M,P), progenitor(M,O), O \= P).

Com P=ana, o objetivo negado encontra M=tomas, O=bruno, por isso falha. Com P=rui, nenhum dos dois progenitores tem outra criança registada e a negação sucede. O resultado depende da completude destes registos, não é uma conclusão sobre familiares que a base desconhece.

Mover progenitor(M,P) para fora da negação mudaria a pergunta para «existe um progenitor sem outra criança». Inês faria Ana passar, apesar de ter Bruno como irmão. Rui poderia ainda aparecer duas vezes, uma por cada progenitor. crianca/1 fornece um candidato único; as provas internas da negação não acrescentam respostas para esse candidato.

Exigir existência em cada elemento da lista

Um utilizador pode ver um vídeo seu ou de alguém que segue. «Pode ver todos os vídeos pedidos» exige verificar cada id pedido, incluindo que esse vídeo existe:

pode_ver(U,V) :- video(V,D), (D=U ; segue(U,D)).
todos_visiveis(U,Vs) :- utilizador(U), todos(U,Vs).
todos(_,[]).
todos(U,[V|Vs]) :- pode_ver(U,V), todos(U,Vs).

O contrato usa um utilizador conhecido e uma lista própria finita de ids instanciados; cada vídeo tem um proprietário único. Uma lista vazia passa para um utilizador registado. Um vídeo ausente faz falhar video/2, e um proprietário não seguido faz falhar a permissão. A recursão só continua depois de validar a cabeça.

Contrasta com procurar uma violação apenas entre vídeos existentes:

incompleto(U,Vs) :-
    \+ (member(V,Vs), video(V,D), \+ (D=U ; segue(U,D))).

Para [99], sem video(99,_), o objetivo interior falha antes de testar a permissão. A negação exterior sucede e aceita erradamente o pedido. O id desapareceu da procura de contraexemplos; não foi validado. Se preferires uma dupla negação para «todos», o contraexemplo deve incluir tanto ausência como falta de permissão.

crianca(ana).
crianca(bruno).
crianca(rui).
progenitor(tomas,ana).
progenitor(ines,ana).
progenitor(tomas,bruno).
progenitor(jose,rui).
progenitor(maria,rui).

sem_irmaos(P) :-
    crianca(P),
    \+ (progenitor(M,P), progenitor(M,O), O \= P).

utilizador(ana).
utilizador(bruno).
utilizador(carla).
segue(ana,bruno).
video(10,ana).
video(11,bruno).
video(12,carla).

pode_ver(U,V) :- video(V,D), (D=U ; segue(U,D)).
todos_visiveis(U,Vs) :- utilizador(U), todos(U,Vs).
todos(_,[]).
todos(U,[V|Vs]) :- pode_ver(U,V), todos(U,Vs).

% Contraexemplo: videos desconhecidos desaparecem da procura de violacoes.
incompleto(U,Vs) :-
    \+ (member(V,Vs), video(V,D), \+ (D=U ; segue(U,D))).

main :-
    findall(P,sem_irmaos(P),Ps), write(Ps), nl,
    (todos_visiveis(ana,[10,11]) -> write(permitidos) ; write(recusados)), nl,
    (todos_visiveis(ana,[99]) -> write(permitidos) ; write(recusados)), nl,
    (incompleto(ana,[99]) -> write(aceite_erradamente) ; write(recusado)), nl.

A base do exemplo dá [rui], aceita os vídeos 10 e 11 para Ana, recusa 99 no predicado completo e mostra a aceitação errada pelo incompleto. Usa write/1 e nl/0, formas comuns a SWI e SICStus; a execução no navegador é SWI.