Aulas Práticas
Aula 8: 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
- Utilize o predicado
findall
para determinar todas as soluções para o problema das N rainhas com N=8.
Aula 7: 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 X2<=N e (X+1)2>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):
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 6: Manipulação de fórmulas lógicas proposicionais 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 lógicas proposicionais 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(1130, xfy, <=>). % equivalencia
:- op(1110, xfy, =>). % implicação
%:- op( 1100, xfy, [ ; ]). % disjunção
%:- op( 1000, xfy, [ ',' ]). % conjunção
:- op( 500, fy, ~). % negação
Estamos a utilizar os operadores de conjunção e disjunção do Prolog (se preferir, pode definir os operadores
/\
e
\/
). Assim, a fórmula apresentada atrás pode ser escrita como
(~p ; p , r, ~q)
(note o papel da precedência e associatividade).
- Defina um predicado que, dado uma fórmula proposicional, determine a Forma Normal Negativa (FNN).
- 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, considere os seguintes predicatos que convertem uma FNN na respectiva Forma Normal Conjuntiva (FNC), e que colocam esta última na sua forma matricial (como uma lista de listas) :
% -----------------------------------------------------------------
% fnc(+NNF,?FNC)
%
% NNF é uma forma normal negatiiva e FNC a respectiva forma normal conjuntiva
cnf(((A,B);C), (F1,F2)) :- !, cnf((A;C),F1), cnf((B;C),F2).
cnf((A;(B,C)), (F1,F2)) :- !, cnf((A;B),F1), cnf((A;C),F2).
cnf((A;B), F) :- !, cnf(A, A1), cnf(B, B1),
(/*IF*/ (A1=(C,D); B1=(C,D)) ->
/*THEN*/ cnf((A1;B1), F) ;
/*ELSE*/ F=(A1;B1) ).
cnf((A,B), (A1,B1)) :- !, cnf(A, A1), cnf(B, B1).
cnf(Lit, Lit).
% -----------------------------------------------------------------
% matCNF(+FNC,?MAT)
%
% FNC é uma forma normal conjuntiva e MAT é a sua representação sob a forma
% de matriz (lista de listas de literais).
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).
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, 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" porque obriga a que o programador detenha uma ideia muito precisa sobre o processo de construção da derivação por parte do Prolog.
- Relembre as seguintes alternativas para calcular o multiplicação de naturais:
a(zero, Y, Y).
a(suc(X), Y, suc(Z)) :- a(X,Y,Z).
m1(zero, _, zero).
m1(suc(X), Y, Z) :- a(Y, W, Z), m1(X,Y,W).
m2(zero, _, zero).
m2(suc(X), Y, Z) :- m2(X,Y,W), a(Y, W, Z).
-
- Seria possível impedir a computação infinita de
m2
por intermédio da introdução de cuts?
- A introdução de cuts também faria sentido para
m1
? Onde? Justifique.
- 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: Árvores de Prova. Tipos algébricos
Árvores de Prova em Prolog
Operacionalmente, o
Prolog segue uma estratégia
top down,
depth-first para encontrar soluções das questões colocadas. O processo de
Unificação permite concretizar as questões colocadas definindo as condições em que a questão inicial é satisfeita (a substituição obtida). Quando o motor de inferência se depara com uma situação de "falha", retrocede na árvore de prova por forma a tentar novas alternativas.
- Relembre o predicado
member
que verifica se um elemento pertence a uma lista. Construa a árvore de procura de soluções para a questão member(X,[1,2,3]).
- Considere agora o predicado
takeout/3
referido na última aula. Construa a árvore de procura de soluções para a questão takeout(X,[1,2,3],Y).
Tipos algébricos em Prolog
A utilização de termos permite a manipulação em Prolog de valores de tipos algébricos (que em
Haskell seriam declarados com
data
). Por exemplo, árvores binárias podem ser representadas por termos como
vazia
,
nodo(vazia, vazia)
, etc.
- 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.
Note no entanto que em
Prolog não existe a noção de tipo. De facto nada nos impede de considerar termos como
vazia(nodo,vazia(nodo))
.
Aula 3: Continuação da 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?
- Utilize o predicado
takeout
para definir um predicado que determine se uma lista é permutação de uma outra.
Aula 2: Utilização de termos, introdução à manipulação de Listas.
Termos Estruturados
Para além dos tipos primitivos, o Prolog admite termos estruturados da forma
f(t1,t2,...,tn), onde
f é o
functor do termo e
t1,...tn são sub-termos.
Uma aplicação típica de termos estruturados é para organizar a informação contida num programa. Por exemplo, podemos armazenar datas com termos da forma "data(25,abril,2007)". O seguinte predicado extrai o dia duma data armazenada dessa forma:
diaData(D,data(D,_,_)).
- Defina o predicado
valData/1
que verifique se uma data é correcta.
Nada nos impede de considerarmos termos arbitrariamente complicados. Em particular, podemos considerar termos de natureza recursiva como a representação dos naturais com os construtores
zero
e
suc
(i.e.
zero
,
suc(zero)
,
suc(suc(zero))
, etc.).
- Defina o predicado
nat/1
que verifique se um termo é um natural na representação referida.
- Defina
soma/3
que verifique se o terceiro argumento é a soma dos dois primeiros.
- Mostre como usar o predicado
soma/3
para calcular a subtração de dois naturais.
- Defina predicados
int2nat/2
e nat2int/2
que convertam naturais em inteiros e vice-versa.
Introdução às Listas em Prolog
Um exemplo de um tipo estruturado que está pré-definido no Prolog são as listas. A sintaxe mais prática é
[]
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.
Aula 1: Apresentação da linguagem PROLOG
Exemplo de apresentação
Tipos Primitivos
- Variáveis:
- Átomos:
- Inteiros:
- Reais:
Unificação, Igualdade, Atribuição