Aulas Práticas

---

Aula 10: Predicados de Segunda Ordem e outros predicados primitivos disponibilizados pelo Prolog

Predicados de segunda ordem

Existem meta-predicados que permitem coleccionar todas as soluções para um dado objectivo de prova (ver User's Manual ou o help).

• findall(?Template,:Goal,?Bag) : Bag é a lista de instâncias de Template encontradas nas provas de Goal. A ordem da lista corresponde à ordem em que são encontradas as respostas. Se não existirem instanciações para Template, Bag unifica com a lista vazia.
• bagof(?Template,:Goal,?Bag) : Semelhante a findall, mas se Goal falhar, bagof falha.
• setof(?Template,:Goal,?Set) : Semelhante a bagof, mas a lista é ordenada e sem repetições.

Exemplo:

| ?- findall(X, member(X,[1,2,3]), L).
L = [1,2,3]
yes

Relacionados com os apresentados, encontramos outros predicados de ordem superior, como o bem conhecido map (do haskell). No Prolog o predicado maplist implementa a funcionalidade análoga.

Exercícios:

• Teste os predicados apresentados codificando exemplos apropriados.
• Utilize o predicado findall para determinar todas as soluções para o problema das N rainhas com N=8.

Outras características do Prolog

Manipulação da base de conhecimento: O Prolog permite manipular dinamicamente a base de conhecimento (inserir ou remover factos ou regras). Para isso disponibiliza os predicados assert, retract, rectractall (e variantes...).

Input/Output: tal como qualquer linguagem com o mínimo de preocupações práticas, é possível realizar operações de Input/Output. Para o efeito dispõe-se dos predicados write, read (entre outros, e com muitas variantes...); open e close para maniputação de ficheiros, etc...

Exercícios:

• Consulte a documentação relativa aos predicados referidos e teste cada um deles com exemplos apropriados.
• Extenda o programa das N rainhas com um predicado runQueens que interrogue o utilizador sobre o número de rainhas a considerar e imprima no écran todas as soluções admissíveis.

---

Aula 9: Estratégia Gerar e Testar.

Estratégia Gerar e Testar

O mecanismo de backtracking do PROLOG torna possível codificar, de forma directa, a estratégia de gerar e testar para encontrar a solução de um determinado problema. Segundo esta estratégia, o problema é decomposto em duas fases:

• Gera-se "soluções cadidatas" para o problema.
• Verifica-se se a "solução candidata" satisfaz os requisitos do problema (e é, portanto, uma "solução efectiva").

Podemos assim identificar o padrão com a seguinte regra PROLOG:

resolve(X) :- gera(X), testa(X).

Note-se o papel preponderante do backtracking para encontrar uma dada solução para resolve(X): o predicado gera(X) instancia X com uma possível solução. No caso de testa(X) falhar (a solução proposta não satisfaz os requisitos impostos pelo problema), o mecanismo de backtracking permite que gera(X) instancie uma nova alternativa, até que se encontre a solução pretendida.

O predicado gera acaba normalmente por se revelar o ponto crítico na aplicação desta estratégia: por um lado, pretende-se que ele cubra todas as possíveis soluções para o problema (caso contrário, podemos nunca gerar a solução requerida). Por outro, e por questões de eficiência, vamos pretender que ele produza o mínimo de soluções erradas (para minimizar o espaço de busca) -- na prática, este esforço de minimização traduz-se por eliminar candidatos notoriamente errados e por encontrar codificações apropriadas para as possíveis soluções.

Vejamos um exemplo concreto: pretende-se encontrar um divisor para um dado número N (diferente de 1 e N).

fromToL(L,U,[]) :- U < L, !.
fromToL(L,U,[L|X]) :- L1 is L+1, fromToL(L1,U,X).

gera(N,X) :- fromToL(2,N-1,L), member(X,L).

testa(N,X) :- N mod X =:= 0.

divisor(N,X) :- gera(N,X), testa(N,X).

Mas o programa apresentado pode ser consideravelmente optimizado se observarmos que nos é suficiente encontrar um divisor entre 2 e sqrt(N) (se X>sqrt(N) é um divisor de N, então também será N/X<sqrt(N)). Dessa forma teríamos:

divisor2(N,X) :- fromtoL(2,sqrt(N),L), member(X,L), N mod X =:= 0.
 

• Verifique ambos os programas para um número primo elevado (e.g. 209953, 331777, 472393, ...)
• Utilize a estratégia generate & test para determinar a raiz de um natural, definida da seguinte forma: um número natural X é a raiz de N quando X²<=N e (X+1)²>N

Problema das N rainhas.

Um exemplo clássico de programação em PROLOG consiste em escrever um predicado que permita resolver o problema das n rainhas. Esse problema consiste em dispor n rainas num tabuleiro de damas com dimensão n*n, sem que qualquer rainha se encontre ameaçada por outra. Como um exemplo de uma solução temos (num tabuleiro 4*4):

		Q
Q
			Q
	Q

Note que cada linha e cada coluna deve conter uma, e só uma, rainha (porquê?). Dito isto, verificamos que uma forma expedita de representar as soluções para este problema consiste em utilizar uma lista que informe qual a coluna em que é colocada a rainha de cada uma das linhas (a solução do exemplo seria [3,1,4,2], querendo dizer que a rainha da primeira linha aparece na terceira coluna, a da segunda linha na primeira coluna, etc.) -- desta forma, aparece uma rainha em cada linha "por construção". A restrição de aparecer uma única rainha por cada coluna é traduzida por deverem aparecer na lista todos os números de 1 a 4, ou seja, a lista deve ser uma permutação de [1,2,3,4]. Temos assim resolvido o sub-problema de gerar soluções candidatas: são simplesmente permutações da lista [1..N].

Na fase de teste, falta unicamente verificar que nenhuma rainha está no alcance da diagonal de uma outra. Para isso notamos que:

• Duas rainhas estão numa diagonal / sse a soma da linha e coluna da posição de cada uma delas for igual;
• Duas rainhas estão numa diagonal \ sse a diferença da linha e coluna da posição de cada uma delas for igual.

Com base no que foi referido, codifique um predicado nrainhas(+N,?X) que determine uma solução para o problema das N-rainhas.

---

Aula 8: Implementação do algoritmo Davis-Putnam em Prolog.

Pretende-se definir um programa que permita verificar se uma dada fórmula é uma contradição pelo método de Davis Putnam. Para o efeito, sugere-se que considere o seguinte predicado matCNF que converte uma Forma Normal Conjuntiva (FNC) na respectiva forma matricial (como uma lista de listas):

% -----------------------------------------------------------------
%  matCNF(+FNC,?MAT)
%
% FNC é uma forma normal conjuntiva e MAT é a sua representação sob a forma
% de matriz (lista de listas de literais).
% obs: os literais são da forma "atom" ou "-atom".
matCNF((A /\ B),M) :- !, matCNF(A,MA), matCNF(B,MB), append(MA,MB,M).
matCNF((A \/ B),C) :- !, matCNF(A,[CA]), matCNF(B,[CB]), union2(CA,CB,C).
matCNF(~Lit, [[-Lit]]) :- !.
matCNF(Lit, [[Lit]]).

union2([],L,[L]).
union2([X|L1],L2,L3) :- member2(X,L2), !, union2(L1,L2,L3).
union2([X|_],L2,[])  :- (-Xn=X;-X=Xn), member2(Xn,L2), !.
union2([X|L1],L2,L3) :- union2(L1,[X|L2],L3).

member2(X,[Y|_]) :- X==Y, !.
member2(X,[_|T]) :- member2(X,T).

Exercícios:

• Defina o predicado de split/3 que determine o particionamento de uma FNC.
• Defina o predicado davisPutnam/1 que verifique se uma fórmula proposicional é inconsistente.

---

---

Aula 7: Lógica Proposicional em Prolog.

Cálculo de Sequentes.

Pretende-se definir um predicado em Prolog que implemente as regras do cálculo de sequentes LC. Para tal deverá considerar que os sequentes são constituídos por pares de listas, sendo portanto o predicado pretendido da forma lc(+Gamma,+Delta) (Gamma e Delta são listas de fórmulas e o predicado verificará se o sequente Gamma |- Delta é válido ou não).

Formas Normais.

Defina os predicados:

• nnf(+Form, -NNF) que determine a forma normal negativa de uma fórmula.
• cnf(+NNF, -CNF) que determina a forma normal conjuntiva (FNC) de uma fórmula dada na FNN.

---

Aula 6: Manipulação de fórmulas de lógica proposicional em Prolog.

Definição de Operadores em Prolog.

O Prolog permite definir operadores prefixos, sufixos ou infixos. Para tal devemos utilizar o predicado pré-definido op( Prec , Type , Name ). O argumento Name é o nome do operador definido; Prec é um número entre 0 e 1200 que determinará a sua precedência e Type determina o seu tipo e associatividade. Por exemplo, o operador de soma binário + está definido como op(700, yfx, +). A precedência 700 irá determinar que tenha menos precedência do que a multiplicação (definida com precedência 500 - note que um número menor indica maior precedência do operador), e o tipo yfx caracteriza o operador como infixo e associativo à esquerda. Outras possibilidades para o tipo dos operadores são: xfy, xfx para operadores infixos associativos à direita e sem associatividade; fx, fy para operadores prefixos e xf, yf para operadores sufixos.

Alguns dos operadores pré-definidos do Prolog são:

:- op( 1200, xfx, [ :-, --> ]).
:- op( 1200,  fx, [ :-, ?- ]).
:- op( 1100, xfy, [ ; ]).
:- op( 1000, xfy, [ ',' ]).
:- op(  700, xfx, [ =, is, =.., ==, \==, =:=, =\=, <, >, =<, >= ]).
:- op(  500, yfx, [ +, -]).
:- op(  500,  fx, [ +, - ]).
:- op(  300, xfx, [ mod ]).
:- op(  200, xfy, [ ^ ]).

• Faça um pequeno predicado que lhe permita confirmar a maior precedência do operador * face ao operador +.

Manipulação de fórmulas de lógica proposicional em Prolog.

A definição de operadores permite que a sintaxe do Prolog se aproxime do domínio onde se está a trabalhar. Considere que se pretendem representar fórmulas da Lógica Proposicional em Prolog. Em vez de considerar termos como or(not(p), and( and(p, r), not(q))), podemos utilizar operadores que nos permitam aproximar a sua representação da utilizada habitualmente. Assim definimos:

:- op( 550, xfy, ==>). 
:- op( 540, yfx, \/).
:- op( 520, yfx, /\).
:- op( 510, fy, ~).   

que denotam os operadores de implicação, disjunção, conjunção e negação. Assim, a fórmula apresentada atrás pode ser escrita como (~p  \/  p  /\ r /\ ~q) (note o papel da precedência e associatividade).

Exercícios:

• Defina o predicado props(+Form,-Props) que calcule o conjunto de símbolos de proposições utilizados na fórmula dada.
• Defina o predicado val(+Form,+Mod) que verifique se a fórmula é válida no modelo passado como argumento.
• Como poderia reformular a definição do predicado val por forma a que não seja necessário instanciar o modelo (ou seja, construir o predicado valM(+Form, ?Mod).

---

Aula 5: Utilização de cut e negação por falha.

O predicado pré-definido cut (!) permite eliminar ramos nas árvores de derivação de predicados Prolog. Operacionalmente, o cut pode ser caracterizado da seguinte forma: Durante o processo de prova, a 1a passagem pelo cut é sempre verdadeira (com sucesso). Se por backtracking se voltar ao cut, então o cut faz falhar o predicado que está na cabeça da regra.

A utilização do cut está normalmente associada a questões de eficiência: os ramos da árvore que são eliminados acabariam eventualmente por falhar, e assim poupamos trabalho ao motor de inferência do Prolog. Esta utilização do cut é considerada benigna (green cut), porque não se afecta o significado dos predicados. Tomemos como exemplo um predicado que verifique se o terceiro argumento é o mínimo dos dois primeiros. Podería ser definido como:

minimo(X,Y,Y) :- X >= Y.
minimo(X,Y,X) :- X < Y.

Mas podemos facilmente observar que, uma vez verificado que X>=Y, não faz sentido tentar verificar que X<Y. Assim sendo, faz sentido colocar um cut no final da primeira cláusula:

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

• Estaria correcto eliminar também o predicado X<Y na segunda cláusula? Justifique com exemplos apropriados.

É importante referir que certas utilizações do cut alteram propositadamente o comportamento do programa (tipicamente para impedir que a execução do programa entre em ciclo). Essas utilizações são normalmente consideradas "mais perigosas" (red cuts) porque obrigam a que o programador detenha uma ideia muito precisa sobre o processo de construção da derivação por parte do Prolog.

• Considere a seguinte base de conhecimento:

q(0,X,Y) :- p(X), !, p(Y).
q(_,X,b) :- p(X).
q(_,c,Y) :- p(Y), !.
p(a). p(b).

• • Quais são as soluções admissíveis para os objectivos q(1,X,Y) e q(0,X,Y).
  • Apresente as árvores de derivação correspondentes aos objectivos da alínea anterior.

• Considere o seguinte programa que pretende inserir o primeiro argumento (um número) na lista ordenada passada no segundo argumento.

insert(X,[H|T],[H|T1]) :- X>H, !, insert(X,T,T1).
insert(X,L,[X|L]).

• • Mostre, avaliando um objectivo apropriado, que o programa está incorrecto.
  • Como o poderá corrigir?

Negação por falha.

Por vezes pretende-se garantir que um dado predicado não é válido. A utilização do cut (em conjunção com o predicado pré-definido fail que falha sempre) permite codificar uma forma restrita de negação: a "negação por falha". Considere o seguinte predicado:

neg(X) :- X, !, fail.
neg(X).

Note que neg(X) falha sempre que o Prolog consiga construir uma derivação para X. Por outro lado, sucede se falhar na construção dessa derivação (entra na segunda cláusula, que é trivialmente satisfeita). Obs.: o predicado pré-definido do Prolog \+ corresponde ao predicado neg apresentado.

• Verifique o resultado de neg em predicados já definidos.
• Considere o seguinte programa:

estudante(paulo). 
casado(joao). 
estudante_solteiro(X) :- \+ casado(X), estudante(X).

• • Como explica a resposta às questões estudante_solteiro(paulo) e estudante_solteiro(X)

---

Aula 4: Exercícios de Manipulação de Listas e Tipos Algébricos

Manipulação de Listas

• Defina last/2 que verifique se o último elemento de uma lista é um dado.
• Defina append/3 que concatene duas listas.
• Utilize o predicado append para definir os predicados prefixo e sufixo que verificam se uma lista é prefixo ou sufixo doutra.
• Defina split/4 que separe os elementos de uma lista nos menores e maiores que um dado valor.
• Considere o predicado:

takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

• • O que faz este predicado?
  • Construa a árvore de procura de soluções para a questão takeout(X,[1,2,3],Y).
• Utilize o predicado takeout para definir um predicado que determine se uma lista é permutação de uma outra.

Tipos Algébricos

A utilização de termos permite a manipulação em Prolog de valores de tipos algébricos (que em Haskell seriam declarados com data). Um primeiro exemplo disso já foi ilustrado na última aula quando se manipularam naturais (zero, suc(zero), etc.). Para sistematizar, vejamos agora como manipular um outro tipo algébrico bem conhecido: as árvores binárias. Uma escolha óbvia para representar os seus valores será considerar o átomo vazia para representar a árvore vazia e termos da forma nodo(X,E,D) para representar nodos intermédios (com valor X, sub-árvore esquerda E e sub-árvore direita D). Temos então como exemplos de termos: vazia, nodo(4, vazia, vazia), etc.

Note no entanto que em Prolog não existe a noção de tipo (e.g. não podemos, à priori, condicionar um dado argumento de um predicado a ser uma árvore binária --- a única alternativa será definir-se um predicado que suceda para termos que tenham a estrutura prescrita...)

• Defina um predicado arvBin/1 que verifique se o termo dado é uma árvore binária (e.g. deve falhar para termos como vazia(nodo,vazia(nodo))).
• Defina um predicado que verifique se uma lista é uma travessia in-order de uma árvore.
• Defina predicados que determinem:
  • uma árvore é uma Árvore Binária de Procura
  • uma lista está ordenada.

---

Aula 3: Árvores de derivação do Prolog.

Considere-se a definição do predicado member/2

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

Este predicado foi definido na última aula com o objectivo de verificar se um elemento está contido numa lista. De facto, podemos utiliza-lo como:

?- member(2,[1,2,3]).
true .

?- member(4,[1,2,3]).
fail.

Mas podemos também utiliza-lo com variáveis não instanciadas com o objectivo de determinar quais os elementos de uma lista:

?- member(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3 ;
fail.

Ou até para determinar soluções a questões mais complicadas, como (mais um exemplo da última aula):

?- member(X,[3,5,4,6,5,7]), X mod 2 =:= 0.
X = 4 ;
X = 6 ;
fail.

O objectivo desta aula é o de se perceber como é que o Prolog consegue chegar às soluções apresentadas (substituições de variáveis que validam o objectivo).

Inferência do Prolog

Um objectivo em Prolog consiste numa lista de predicados. O resultado da "execução" desse objectivo num interpretador consiste numa substituição que verifique esses predicados. O processo construção da substituição é normalmente designado por inferência, e pode ser justificado construindo uma árvore como se descreve:

1. Na raiz da árvore, coloca-se a lista de predicados. O Prolog irá processar cada predicado dessa lista por ordem.
2. Para cada predicado, o Prolog irá procurar encontrar na base de conhecimento uma instância dum facto ou duma regra cuja cabeça unifique com esse predicado. Esta procura processa-se também pela ordem pela qual as definições ocorrem na base de conhecimento.
3. Quando é encontrada uma regra nas condições referidas, cria-se um descendente na árvore contendo a lista já afectada pela substituição resultante da unificação (relembre que o resultada na unificação é uma substituição das variáveis) e onde o predicado em análise é substituído pelo lado direito da regra (ou simplesmente desaparece, no caso dos factos). É habitual anotarmos os arcos da árvore com as substituições resultantes das unificações.
4. Quando existe mais do que uma possibilidade para a referida unificação (e.g. várias regras são aplicáveis), traduz-se por uma ramificação da árvore de inferência.
5. Operacionalmente, o Prolog trata esta ramificação pelo mecanismo de backtracking (travessia depth-first da árvore).
6. Quando a lista de predicados fica vazia, cria-se uma folha na árvore denotada como true --- representa um resultado apresentado ao utilizador (a substituição calculada ao longo do caminho).
7. Quando não existe qualquer regra na base de conhecimento que unifique com o primeiro predicado da lista, cria-se uma folha denotada por fail .

A árvore de derivação para o objectivo "member(X,[1,2]), X mod 2 ==0" será:

Exercícios:

• Considere a seguinte definição do predicado factorial:

fact(1,0).
fact(R,X) :- X2 is X-1, fact(R2,X2), R is X*R2.

• • Apresente a árvore de inferência para o objectivo fact(R,2).
  • Comente os resultados obtidos. Explique, em particular, que problemas aponta à solução apresentada.
  • Como pode ultrapassar os problemas detectados.
• Considere o seguinte predicado:

nat2int(zero,0).
nat2int(suc(X),N) :- nat2int(X,N2), N is N2+1.

• • Apresente a árvore de inferência para o objectivo nat2int(suc(suc(zero)),X).
  • Apresente a árvore de inferência para o objectivo nat2int(X,2).
  • Comente os resultados obtidos.
  • Consegue propor alguma forma de ultrapassar os problemas detectados?

Tracing e Debug

Uma forma expedita de detectar problemas em programas Prolog consiste em utilizar o mecanismo de tracing. Esse mecanismo permite "monitorizar" determinados predicados durante o processo de inferência. Considere-se novamente o objectivo considerado atrás que faz uso do predicado member/2:

?- trace(member).
%         member/2: [call, redo, exit, fail]
true.

[debug]  ?- member(X,[1,2]), X mod 2 =:= 0.
 T Call: (8) member(_G318, [1, 2])
 T Exit: (8) member(1, [1, 2])
 T Redo: (8) member(_G318, [1, 2])
 T Call: (9) member(_G318, [2])
 T Exit: (9) member(2, [2])
 T Exit: (8) member(2, [1, 2])
X = 2 ;
 T Redo: (9) member(_G318, [2])
 T Call: (10) member(_G318, [])
 T Fail: (10) member(_G318, [])
fail.

Note que o Prolog sinalizada diferentes eventos relativos ao predicado observado:

• Call: o predicado em "resolução";
• Exit: o predicado foi resolvido com sucesso (pode por isso ser removido da lista de objectivos);
• Redo: nova visita ao predicado (por backtracking);
• Fail: predicado falha definitivamente (já não existem mais alternativas para o backtracking).

Exercício:

• Interprete o resultado do trace apresentado na árvore de inferência apresentada acima.
• Realize análises de traces para as restantes árvores construídas nesta aula...

---

Aula 2: Operações aritméticas e Manipulação de listas.

Operações aritméticas

Já vimos que o Prolog aceita termos que representem expressões matemáticas, como 3+4*2. Mas quando manipulamos esses termos estamos normalmente interessados em avaliar essas expressões (i.e. calcular o seu resultado). O Prolog disponibiliza para o efeito o predicado is que avalia o segundo argumento e unifica o resultado com o primeiro. Alguns exemplos (onde se utiliza a notação infixa para o predicado):

?- X is 3+2.
X = 5.

?- 3+2 is 2+3.
fail.

?- 5 is 3+2.
true.

?- 5 is X+2.
ERROR: is/2: Arguments are not sufficiently instantiated

Um aspecto importante na utilização do predicado is é a assimetria induzida: o segundo argumento deve ser sempre uma expressão completamente instanciada. Assim, se definirmos o predicado:

soma(X,Y,Z) :- X is Y + Z.

devemos considerar o segundo e o terceiro argumentos como "argumentos de entrada", que necessitam estar devidamente instanciados. Uma forma compacta de se exprimir esse facto (normalmente utilizada na documentação) é através da assinatura soma(-X,+Y,+Z) --- assim identifica-se o argumento Y e Z como de entrada e X como de saída.

Exercício:

• Defina o predicado factorial(-R,+X) que suceda quando R for o factorial de X.
• Uma forma alternativa de lidar com números naturais consiste em considerar termos zero, suc(zero), suc(suc(zero)), etc. (i.e. utilizar notação unária para os naturais). Defina o predicado nat2int que sucede quando o primeiro argumento é a representação unária do segundo.
• No predicado definido na alínea anterior, verifique:
  • que argumentos tem de ser utilizados como entrada e como saída;
  • o que acontece quando solicita ao interpretador várias respostas.
• Verifique, com o auxílio do mecanismo de help do SWI-Prolog (ou da documentação on-line, se preferir) qual a funcionalidade oferecida pelos operadores:

  =:=, =\=, <, =<, ==, @< 

Manipulação de listas

Um exemplo de um tipo estruturado muito utilizado em Prolog são as listas. A sintaxe pré-definida é [] que denota a lista vazia e [H|T] que denota a lista com cabeça H e cauda T.

• Defina member/2 que verifica se um elemento pertence a uma lista.
• Utilize o predicado member para determinar quais dos elementos da lista [3,5,4,6,5,7] são pares.
• Defina um predicado que permita calcular o somatório de uma lista de inteiros.
• O que alteraria, no predicado definido na alínea anterior, para calcular o somatório de uma lista de expressões inteiras?
• Defina o predicado concat/3 que verifique quando uma lista é a concatenação de outras duas. Verifique o resultado quando o invoca com diferentes listas instanciadas.

---

Aula 1: Apresentação da linguagem PROLOG

Ao longo das aulas práticas de Lógica Computacional fazer uso da linguagem PROLOG. O interpretador adoptado será o SWI-Prolog que está disponível para para a generalidade das plataformas (MS-Windows, Linux, macOSX).

Conceitos Preliminares

Termos: o Prolog é uma linguagem simbólica que manipula termos que podem ser:

• Variáveis - denotadas por identificadores começados por letras maiúsculas (e.g. X, Y, Xs, ...);
• Constantes - átomos (identificadores começados por letras minúsculas) ou valores de tipos pré-definidos como inteiros, reais, strings, etc. (e.g. abc, xyz, 32, 3.1415)
• Termos Compostos - termos da forma f(t1,...,tn) onde f é designado por functor (nome da função) e t1...tn são termos (e.g. xyz(X,abc), abc(abc(abc,abc)), +(4,2))

obs.: como iremos ver adiante, o Prolog permite a declaração de operadores infixos. Assim irá permitir escrever 4 + 2 como alternativa ao termo +(4,2) (o mesmo se aplica a outros operadores infixos que serão apresentados adiante).

Substituições e Unificação: o que caracteriza as variáveis é o facto de elas poderem vir a ser substituidas por outros termos. Considere-se o termo t(X,Y): se substituirmos X por abc(A,3) e Y por Z obtemos o termos t(abc(A,3),Z).

Uma operação fundamental no modelo de execução do Prolog é o que se designa por Unificação de dois termos. A ideia consiste em encontrar uma substituição que iguale (se possível) os termos dados. Vejamos alguns exemplos:

• X = 4, Y = 3 é um unificador dos termos abc(3,X) e abc(Y,4);
• X = 4, Y = 3 é um unificador dos termos abc(X,X) e abc(Y,4);
• os termos abc(3,4) e abc(X,X) não dispõe de unificador.

Uma característica dos unificadores apresentados é que se tratam sempre dos unificadores mais gerais (qualquer outra substituição que unifique os termos pode ser expressa como um refinamento da substituição dada). Adiante iremos ter oportunidade de aprofundar estes aspectos mais teóricos... Para já interessa reter que o Prolog, quando unificar dois termos, determina sempre o unificador mais geral (i.e. a substituição mais simples que iguala os termos).

EXERCÍCIO: Determine o unificador mais geral para os seguintes pares de termos (se existir... naturalmente):

• f(X,g(Y)) e g(X,f(Y))
• f(X,g(Y)) e Z
• f(X,g(y)) e f(g(y),X)
• f(X) e X
• f(X) e f(3+2)
• f(3) e f(2+1)
• f(3) e A(X)

Programas em Prolog

Executar um programa em Prolog consiste em interrogar o interpretador sobre a validade de um dado predicado lógico. A resposta mais simples será então true ou fail (se o predicado for válido ou não, respectivamente).

Objectivo (Goal):

Quando se invoca o SWI-Prolog, surge o prompt ?- que assinala que o interpretador aguarda a introdução de um objectivo (ou query, ou goal).

Calvin:~ jba$ /opt/local/bin/swipl 
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.51)
Copyright (c) 1990-2008 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- 

Como referimos, o objectivo será um predicado lógico. Iremos ter oportunidade de definir novos predicados mas, para já, concentremo-nos na utilização do predicado pré-definido =/2 (o /2 significa que o predicado espera dois argumentos). Este predicado será válido precisamente quando os termos que forem passados como argumentos unificarem. Assim podemos introduzir:

?- =(3,3).
true.

?- 3=3.
true.

?- 3=2.
fail.

?- 3=X.
X = 3.

?- 3+2=X.
X = 3+2.

?- 3 + X = Y * 2.
fail.

?- 

Os exemplos apresentados revelam-nos duas coisas: (1) podemos utilizar a notação infixa e, (2) quando no objectivo estão envolvidas veriáveis o Prolog retorna uma substituição dessas variáveis que verifiquem o predicado (ou falha, se não existir nenhuma substituição nessas condições) --- podemos então dizer que, intuitivamente, as variáveis dos objectivos estão quantificadas existencialmente.

EXERCÍCIO: Interrogue o interpretador de Prolog por forma a ele retornar os unificadores mais gerais atrás solicitados.

Factos (base de conhecimento I):

Referimos que executar um programa em Prolog consiste em interrogar o interpretador relativamente a um objectivo. Mas, em que é que consiste um programa Prolog?. Um programa em Prolog será a base de conhecimento que o interpretador utiliza para determinar a validade do objectivo pedido. Essa base de conhecimento será consituída por:

• Factos: que estabelecem a validade imediata (de instâncias) de predicados;
• Regras: que condicionam a validade de predicados à validade de sub-objectivos.

Comecemos pelos primeiros. Como exemplos de factos podemos ter:

pai(joao,manuel).
pai(cristina, jose).
pai(joaquim,manuel).
pai(francisco,joao).
pai(helena,joao)

Com base nestes factos, diriamos que pai(joaquim,manuel) é válido mas pai(joaquim,jose) já não o é (porque nada estabelece a sua validade). Para verificar isso com o Prolog, necessitamos de carregar a base de conhecimento no interpretador. Para tal devemos:

• gravar um ficheiro com os factos apresentados (normalmente dá-se a extensão ".pl" aos ficheiros Prolog, e.g. "pai.pl");
• carregar o ficheiro no interpretador por intermédio do predicado pré-definido consult (e.g. "consult(pai.pl)").

EXERCÍCIO: Verifique a validade de alguns objectivos com a base de conhecimento apresentada. O que acontece quando se inclui variáveis?

Por vezes, o interpretador retorna uma substituição de resultado sem voltar ao prompt inicial. Isso assinala que a solução apresentada é uma de várias possíveis, podendo o utilizador:

• digitar . e retornar ao prompt inicial;
• digitar ; para solicitar outra solução.

EXERCÍCIO:

• introduza um predicado que permita determinar todos os filhos de "manuel".
• o que aconteceria se incluisse na base de conhecimento o facto pai(X,carlos) ? Experimente... (verifique o impacto de o incluir no início e no fim da base de conhecimento).

O exercício anterior permite concluir que, nos factos, devemos realizar uma interpretação universal das variáveis.

Se as questões colocadas ao interpretador de Prolog são predicados lógicos, é natural perguntarmo-nos como construir predicados à custa de conectivas lógicas (como e, ou, etc.). O Prolog tem definido os operadores:

• conjunção: denotado por uma vírgula (,)
• disjunção: denotado por um ponto e vírgula (;)

(As restantes conectivas lógicas proposicionais serão introduzidas mais tarde.)

Regras (base de conhecimento II):

A expressividade do Prolog resulta do facto de permitir incluir, na base de conhecimento, regras que condicionam a validade de um predicado (colocado no lado esquerdo do operador :-, e designado por cabeça da regra) à validade de um conjunto de outros predicados (designados por corpo da regra). A título de exemplo, temos que a regra:

avo(X,Y) :- pai(X,Z), pai(Z,Y).

Quando acrescentada à base de conhecimento apresentada acima, permite que o Prolog responda afirmativamente ao predicado avo(francisco,manuel). No processo, o interpretador verificará os predicados pai(francisco,joao) e pai(joao,manuel).

Note que nas regras, as variáveis que ocorrem na cabeça da regra devem ser entendidas como quantificadas universalmente (como nos factos). Já as que só ocorrem no corpo da regra devem ser entendidas como quantificadas existencialmente (como nos objectivos).

Exercício: Estenda a base de conhecimento para exprimir outros graus de parentesco, como "irmão", "tio", etc.

---