Prolog Controles (Slide 1)

Prévia do material em texto

Prolog e
Controle de 
Programas 
Solange Rezende
Aula Passada
 Discussão das primeiras atividades
 Entregar foto selfie até dia 11/08 (próxima sexta);
 Reflexão sobre o filme “Poder além da vida”;
 Lembrem-se das 3 lições aprendidas.
 Andragogia 
 Arte de auxiliar adultos a aprender;
 Importância de manter o foco para ser bem 
sucedido.
 Breve introdução à Programação Lógica
Programação Lógica (PL)
 Uma das principais ideias da PL é a de
que um algoritmo é constituído por
dois elementos disjuntos:
◦ Lógica: corresponde à definição do
que deve ser solucionado;
◦ Controle: estabelece como a solução
deve ser obtida.
 A tarefa do programador em PL é 
especificar o componente lógico do 
algoritmo. 
 O controle da execução é exercido por 
um sistema de inferência inerente à 
linguagem lógica.
Síntese - Programação Lógica
• Programação Procedural:
Programa = Algoritmo + Estruturas de 
Dados
• Programação Lógica
Algoritmo = Lógica + Controle
Programa = Lógica + Controle + Estruturas 
de Dados
• Em PL, programa-se de forma 
declarativa, ou seja, especificando 
o que deve ser computado ao invés 
de como deve ser computado
Programação em Prolog
Programar em Prolog envolve:
–declarar alguns fatos a 
respeito de objetos e seus 
relacionamentos
–definir algumas regras sobre 
os objetos e seus 
relacionamentos e
– fazer perguntas sobre os 
objetos e seus relacionamentos
Programação Lógica e Prolog
• O conhecimento (programas e/ou dados 
lógica) é expresso por fatos e regras
◦ Fatos: cláusulas que denotam uma verdade
incondicional
(1) João é uma criança. -> crianca(joao).
(2) Chocolate é doce. -> doce(chocolate).
◦ Regras: cláusulas que definem condições
que devem ser satisfeitas para que uma
certa declaração seja considerada verdadeira
(1) Crianças gostam de alimentos desde que eles sejam
doces.
gosta(Alguem,Alimento):-
crianca(Alguem),
doce(Alimento).
Controle de Programas Prolog
• O processamento (controle) é
realizado mediante consultas à base de
cláusulas, por meio do mecanismo de
inferência
(1) João gosta de chocolate?
?- gosta(joao,chocolate).
• Controlar a execução de um programa 
consiste em ordenar as cláusulas dentro 
do programa e as metas dentro da 
cláusula. 
• Prolog tenta satisfazer uma submeta antes 
de continuar com outra meta. É a 
aplicação da BUSCA EM 
PROFUNDIDADE.
Controle 1 - E e OU
• E  especifica uma conjunção de
metas ( , ). Todas as metas dentro
de uma cláusula, separadas por
vírgulas, devem ser satisfeitas para
que a cláusula tenha sucesso.
• Ex:
• Conjunção de metas no corpo de uma
regra
a:- b,c,d.
• Conjunção de metas em uma pergunta
?- b,c,d.
Controle 1 - E e OU 
• OU  especifica uma disjunção de
metas ( ; ou | ). Todas as metas de
um dos lados de uma disjunção têm
que ser satisfeitas para que a
disjunção tenha sucesso.
• Sugestão para implementações
• Evite o OU no corpo de uma regra
a:-b,c;d,e,f.
• Utilize cláusulas diferentes
a:-b,c.
a:-d,e,f.
(cont.)
Controle 2 - Backtracking
Considere a base de dados com os
seguintes fatos:
gosta(joao, jazz).
gosta(joao, marcia).
gosta(joao, feijoada).
gosta(marcia, joao).
gosta(marcia, feijoada).
 O objetivo é descobrir o que ambos
(João e Márcia) gostam:
?- gosta(joao, X), gosta(marcia, X).
?- gosta(joao, X), gosta(marcia, X).
1. Ele descobre que João gosta de jazz.
2. X/jazz <- (X instância com jazz)
3. Prolog tenta satisfazer o 2º predicado, verificando se
Márcia gosta de jazz.
4. Falha porque não consegue provar que Márcia gosta
de jazz.
5. Faz o BACKTRACKING e tenta resatisfazer
gosta(joao, X), deixando de lado o valor jazz.
6. Descobre que João gosta de Márcia.
7. X/marcia <- (X instância com marcia)
8. Tenta satisfazer o 2º predicado, verificando se Márcia
gosta de Márcia.
9. Falha.
10. Faz o Backtracking e tenta satisfazer gosta(joao, X).
11. Descobre que João gosta de feijoada.
12. X/feijoada <- (X instância com feijoada )
13. Obtém sucesso com X/feijoada, pois Márcia também
gosta de feijoada.
(cont.)
Controle 3 - Corte 
Prolog em busca de uma solução
sempre faz automaticamente o
Backtracking.
• O Backtracking não controlado pode tornar
um programa ineficiente.
• Algumas vezes torna-se necessário
controlá-lo, isto é feito através de um
predicado especial chamado corte ( ! ).
2 razões para uso do corte:
1. Tornar o programa mais rápido (reduz
o espaço de busca);
2. Fazer com que o programa ocupe
menos espaço na memória.
O corte deve ser usado com cuidado !!!
Considere o ex.: f(x) = 0 se x  3
2 se x  3 e x  6
4 se x  6
Em Prolog esta função pode ter a seguinte
forma (versão 1):
f(X,0) :- X  3.
f(X,2) :- 3 = X, X  6.
f(X,4) :- 6 = X.
Ao se interrogar Prolog com:
?- f(1,Y), 2Y.
◦ Y é instanciado com 0 e a prova 20 falha.
◦ Antes de admitir que a interrogação não é
satisfeita, Prolog tenta, via backtracking, as
outras duas alternativas, que pela própria
definição de f(X), não serão satisfeitas.
(cont.)
Para prevenir backtracking inútil,
pode-se explicitamente direcionar Prolog
a não realizá-lo. Considere a versão 2:
f(X,0) :- X  3, !.
f(X,2) :- 3 = X, X  6, !.
f(X,4) :- 6 = X.
 O Prolog tentará o backtracking, não além do ponto
marcado com !, se a mesma interrogação anterior for
feita (?- f(1,Y), 2Y. ).
 As duas cláusulas alternativas não serão ativadas.
 A 2ª versão é mais eficiente.
(cont.)
• corte acima é denominado CORTE VERDE,
pois a sua adição ou remoção não afeta o
significado do programa.
O CORTE VERMELHO afeta o significado
declarativo de um programa. Cortes
vermelhos tornam um programa difícil de
ser entendido e devem ser usados com
muito cuidado.
Ex.: se x  3 então f(x) = 0
caso contrário se x  6 então f(x) = 2
caso contrário f(x) = 4
Versão 3
f(X,0) :- X  3, !.
f(X,2) :- X  6, !.
f(X,4).
• Este programa produz os mesmos resultados que
as versões 1 e 2 e é ainda mais eficiente.
• Entretanto, a introdução dos cortes alterou o
significado declarativo do programa, uma vez
que se eles forem retirados, o programa produz
soluções incorretas.
(cont.)
Outros exemplos usando corte
Considere o programa
p(1).
p(2) :- !.
p(3).
Considere o programa
p(1).
p(2) :- !.
p(3).
a) ?- p(X).
X = 1 ;
X = 2 ;
no
b) ?- p(X), p(Y).
X = 1 X = 1 X = 2 X = 2 no
Y = 1 ; Y = 2 ; Y = 1 ; Y = 2 ;
Considere as seguintes
interrogações:
c) ?- p(X), !, p(Y).
X = 1 X = 1 no
Y = 1 ; Y = 2 ;
(cont.)
Observar o significado dos programas com 
o Corte
i) p :- a,b.
p :- c.
ii) p :- a,!,b.
p :- c.
iii) p :- c.
p :- a,!,b
p <-> (a & b) v cp <-> (a & b) v c
p <-> (a & b) v (~a & c)p <-> (a & b) v (~a & c)
p <-> c v (a & b)p <-> c v (a & b)
(cont.)
Controle 4 - Corte Seletivo 
Permite que algumas metas não sejam
consideradas durante o backtracking –
indicadas por [! !] .
Ex.:
A :- B, [! C, D !], E.
Se E falhar, o backtracking ignora as
metas C e D e tenta resatisfazer a meta B.
A :- B, C, D, !, E.
Se E falhar o backtracking encontra o
corte na volta e A falha.
Controle 5 - Falha 
Obriga um programa a fazer o
backtracking com o uso de falha (fail)
eleitor(X) :-
menor(X),
!, fail.
/* se X é menor de idade então ele não é obrigado a
votar - ou seja, corta e falha para não satisfazer
eleitor na próxima cláusula */
eleitor(X) :-
cidadao (X),
idade(X, Y),
Y >= 16. 
Controle 6 - Negação
• not(P) ou not P ou \+P no qual 
P é uma meta. 
• Se P tiver sucesso, not(P) falha, caso 
contrário not(P) tem sucesso.
• Prolog assume mundo fechado, isto é, tudo 
que está declarado como fato(asserção) 
ou pode ser deduzido é verdade, caso 
contrário é falso.
• O not está implementado pelo 
seguinte meta-programa
not(P) :- P, !, fail.
not(P).
• I- Observar a instanciação de 
variáveis quando usa-se negação em 
Prolog
• Considere o seguinte programa
r(a).
q(b).
p(X) :- not (r(X)).
• As interrogações 
?- q(X), p(X). 
?- p(X), q(X).
são logicamente equivalentes? 
Execute e explique os resultados.
(cont.)
• II - A mudança na ordem das submetas 
de uma cláusula normalmente causam 
problemas quando o not está presente
• Considere o seguinte programa
funcionario_solteiro(X):-
funcionario(X),
not casado(X).
funcionario('Joao').
casado('Jose').
?-funcionario_solteiro(X).
X = 'Joao' ;
no.
?-funcionario_solteiro(X).
X = 'Joao' ;
no.
• Agora considere que o funcionário é 
solteiro se não é casado e é funcionário
novo_funcionario_solteiro(X):-
not casado(X),
funcionario(X).
?- novo_funcionario_solteiro(X).
Falha, ignorando que X=‘Joao’é solução
?- novo_funcionario_solteiro(X).
Falha, ignorando que X=‘Joao’é solução
(cont.)
Controle 7 - Repeat
Ex.: le_imprime :-
repeat,
read(X),
write(X),
nl,
X=fim.
repeat é um predicado que
sempre tem sucesso.
• Repeat permite a busca de soluções alternativas para
predicados que não sofrem/permitem o backtracking ou que
tem múltiplas soluções.
Slides baseados em:
Bratko, I.; Prolog Programming for Artificial 
Intelligence, 3rd Edition, Pearson 
Education, 2001.
Clocksin, W.F.; Mellish, C.S.; Programming in 
Prolog, 5th Edition, Springer-Verlag, 2003.
Material elaborado por
Solange Oliveira Rezende