Introdução a Prolog
Aula “teórico-prática”
O que é Prolog?


Linguagem mais divulgada do paradigma de Programação
em Lógica
Baseado em cláusulas de Horn



P1  P2  P3  ...  Pn  Q
Operacionalização simples, prática e eficiente da metáfora da
programação em lógica
Metáfora da programação em lógica


Programar = Declarar axiomas e regras
Teoria Lógica x Prolog



Axiomas: Fatos prolog
Regras: Regras prolog
Teoremas: Deduzidos a partir dos fatos e regras
Exemplo - Fatos
pam
tom
bob
ann
pat
jim
liz
parent(pam,
parent(tom,
parent(tom,
parent(bob,
parent(bob,
parent(pat,
bob).
bob).
liz).
ann).
pat).
jim).
female(pam).
female(ann).
female(pat).
female(liz).
male(bob).
male(tom).
male(jim).
Exemplo – Perguntas à base de
fatos
pam
tom
bob
ann
pat
jim
liz
Bob é filho de Jim?
- parent(jim, bob).
false
Bob é filho de quem?
- parent(X, bob).
X = pam ;
X = tom ;
Encontre X e Y tal que X é
“progenitor” de Y.
parent(X, Y).
X = pam
Y = bob ;
...
Exemplo – Regras
pam
tom
bob
ann
pat
jim
liz
Quem é o pai de bob?
- parent(X, bob),
male(X).
X = tom
Definindo uma regra para pai
father(X, Y) :- parent(X,
Y), male(X).
Isto é a sintaxe em prolog para
x, y parent(x, y)  male(x) 
father(x, y)
Agora podemos perguntar
- father(X, bob).
X = tom
Exercício 1

Defina as regras: (arquivo family.P)




mother(X,Y)
sister(X, Y)
grandparent(X, Y)
Defina a regra:

aunt(X, Y)

Dica: você pode usar a regra sister(X, Y) definida anteriormente
Exemplo – Regras recursivas
Quais são os ancestrais de jim?
 Podemos expressar a relação
ancestor(X, Y) por uma regra
recursiva
ancestor(X, Y) :father(X, Y).
ancestor(X, Y) :father(X, Z),
ancestor(Z, Y).

pam
tom
bob
ann
pat
liz

Faça as perguntas


jim
Quem são os ancestrais de Jim?
Bob é ancestral de quem? E Jim?
Sintaxe de Prolog







fato -> fa. (abreviação para Formula Atômica)
regra -> fa0 :- fa1, ... , faN.
consulta -> fa1, ... , faN.
fa -> pred(termo1, ... , termoN) | preop termo1 termo2
| termo1 inop termo2 | termo1 termo2 postop
termo -> constante | variável | fa
constante -> átomos | números
pred -> átomo
Sintaxe de Prolog (2)




variável ex: C, Chico, Francisco_carvalho, Chico1, _fatc, _
átomo ex: c, fatc, =>, francisco_carvalho, chico1, ‘chico ia’
número ex: 23
termos, fatos, regras e consultas sem variáveis:



termos, fatos e regras com variáveis:



instanciados (ground)
ex.: person(bob,40,cs).
universais
ex.: father(adao,X).
father(X, Y) :- parent(X, Y), male(X).
consultas com variáveis:


existenciais
ex.: - father(F,P).
Intepretação de um programa
Prolog

P :- Q, R.

Interpretações declarativas



P é verdadeiro se Q e R forem verdadeiros.
Q e R implica P.
Interpretações procedurais

Para resolver o problema P:



Primeiro resolva o subproblema Q
Depois resolva o subproblema R
Para satisfazer P:


Primeiro satisfaça Q
E então satisfaça R
Interpretador Prolog: Controle e Busca
(funcionamento procedural)

Aplica regra de resolução:







com estratégia linear (sempre tenta unificar último fato a provar
com a conclusão de uma cláusula do programa),
na ordem escrita das cláusulas no programa,
com encadeamento de regras regressivo (backward-chaining),
busca em profundidade e
da esquerda para direita das premissas das cláusulas,
e com backtracking sistemático e linear quando a unificação
falha,
e sem occur-check na unificação.
Prolog e aritmética

Operadores aritméticos








+ adição
- subtração
* multiplicação
/ divisão
** potenciação
// divisão inteira
mod módulo (resto da divisão
inteira)
O atribuidor is

Variável is Expr. Aritmética

Exemplos
-
X
-
X
-
X
Y
Z
X = 1 + 2
= 1 + 2
X is 1 + 2
= 3
X is 5/2, Y is 5//2,
Z is 5 mod 2.
= 2.5
= 2
= 1
Prolog e aritmética (2)

Operadores de comparação






> maior que
< menor que
>= maior ou igual
=< menor ou igual
=:= teste de igualdade
aritmética
=\= teste de diferença
aritmética

Exemplos
1 + 2 =:= 2 + 1.
yes
1 + 2 = 2 + 1.
no
1 + A = B + 2.
A = 2
B = 1
-
Exemplo Aritmético - Fatorial
factorial(0, 1).
factorial(N, Fn) :N > 0,
M is N - 1,
factorial(M, Fm),
Fn is N * Fm.
(arquivo fac.P)
- factorial(10, X).
X = 362880
- factorial(10, 362880).
yes
- factorial(10, 10000).
no
Exercício 2


Defina uma regra fib(X, Y) que calcula o número de fibonacci
de X, atribuindo-o a Y.
A sequência de Fibonacci é definida matematicamente como





fib(1) = 1
fib(2) = 1
fib(n) = fib(n – 1) + fib(n – 2)
Use seu programa para calcular o fib(5).
O que acontece quando você calcula o fib(30)?
Adicionando e removendo
cláusulas dinamicamente

Um programa prolog pode ser visto como um banco de dados

Relações



Predicados built-in permitem a atualização do programa em
tempo de execução

Adicionar uma nova cláusula


assert, asserta, assertz
Remover uma cláusula


Explícitas: fatos
Implícitas: regras
retract
No XSB módulos com predicados dinâmicos devem ser
carregados com o comando load_dyn/1
Usando assert para tornar o
programa fib eficiente
fib(1, 1).
fib(2, 1).
fib(N, Fn) :N > 2,
M is N - 1,
fib(M, Fm),
O is N - 2,
fib(O, Fo),
Fn is Fm + Fo,
asserta(fib(N, Fn)).


Agora os resultados parciais
são armazenados, não
precisando serem
recalculados.
Teste fib(40, X).
Ferramentas de Debug


trace/0 : ativa o modo de rastreamento.
O sistema interage com o usuário cada vez que um predicado é:






Podem ser observados predicados específicos com o comando
spy(predicado/aridade).
Diferentes ações escolhidas na interação com o debugador:


ativado inicialmente (call)
retorna com sucesso (exit)
vai fazer backtracking (redo)
falhou completamente (fail)
Creep (step), Leap (continuar até próximo spy), Skip (desabilita trace
até o final desta execução), Abort (aborta a execução atual).
notrace/0, nospy/1.
Mais um Exemplo
Vamos definir a função




Se X < 3 então Y = 0
Se 3  X e X < 6 então Y = 2
Se 6  X então Y = 4
Y
4
2
3
6
X
(arquivo funct.P)
f(X, 0) :- X < 3.
f(X, 2) :- 3 =< X, X < 6.
f(X, 4) :- 6 =< X.
Execução do exemplo


Como prolog se comporta quando
fazemos uma consulta?
Vamos acompanhar a execução
de uma consulta ativando o
mecanismo de trace do xsb.
-
•
trace.
Agora façamos a consulta: f(1,
Y), 2 < Y.
f(X, 0) :- X < 3.
f(X, 2) :- 3 =< X, X < 6.
f(X, 4) :- 6 =< X.
(0)
(1)
(1)
(0)
(2)
(2)
(0)
(1)
(1)
(3)
(3)
(4)
(4)
(0)
Call:
Call:
Exit:
Exit:
Call:
Fail:
Redo:
Redo:
Fail:
Call:
Fail:
Call:
Fail:
Fail:
f(1,_h454) ? c
1 < 3 ? c
1 < 3 ? c
f(1,0) ? c
2 < 0 ? c
2 < 0 ? c
f(1,0) ? c
1 < 3 ? c
1 < 3 ? c
3 =< 1 ? c
3 =< 1 ? c
6 =< 1 ? c
6 =< 1 ? c
f(1,_h454) ? c
Diagrama da execução do
exemplo
f(1, Y)
2<Y
Regra 1
Y=0
1<3
2<0
CUT
Regra 3
Y=4
Regra 2
Y=2
3≤1
1<6
2<2
6≤1
2<4
no
no
2 < 0 no
f(X, 0) :- X < 3.
f(X, 2) :- 3 =< X, X < 6.
f(X, 4) :- 6 =< X.
Regras mutuamente
exclusivas
Evitar backtracking inútil: ! (o cut)


op built-in de pruning, logicamente sempre verificado
com efeito colateral de impedir backtracking:



na sua esquerda na cláusula que ocorre
em outras cláusulas com a mesma conclusão
ex: A :- B, C, D.
C :- M, N, !, P, Q.
C :- R.



impede backtracking P -> N
permite backtracking N -> M, Q -> P,
D -> (R xor Q), (P xor R) -> B
R tentado:


unicamente se M ou N falha
nunca se P ou Q falha
Cut: exemplo

Otimizando o exemplo anterior:
f(X, 0) :- X < 3, !.
f(X, 2) :- 3 =< X, X < 6, !.
f(X, 4) :- 6 =< X.



Nesse caso os cuts alteram apenas o comportamento
procedural do programa.
Se removermos os cuts o programa continuará produzindo os
mesmos resultados.
Green cuts
Cut: exemplo (2)

Podemos otimizar ainda mais
o programa, pensando-o da
seguinte forma:
if (X < 3) then Y = 0
else if (X < 6) then Y = 2
else Y = 4

Eliminamos assim 2
comparações desnecessárias.

Versão anterior:
f(X, 0) :- X < 3, !.
f(X, 2) :- 3 =< X,
X < 6, !.
f(X, 4) :- 6 =< X.

Reescrevemos para:
f(X, 0) :- X < 3, !.
f(X, 2) :- X < 6, !.
f(X, 4).
Cut: exemplo(3)

O que acontece agora se os cuts forem removidos?
f(X, 0) :- X < 3.
f(X, 2) :- X < 6.
f(X, 4).

f(1, Y).
Y = 0;
Y = 2;
Y = 4;


Neste caso os cuts afetam a semântica do programa
Red cuts
Hipótese do mundo fechado

Ao contrário da Lógica de 1a ordem, Prolog não permite nem
fatos, nem conclusões de regras negativos:
~animal_lover(geber).
~kill(X,Y) :- animal_lover(X), animal(Y).

Princípio de economia:



declarar e deduzir apenas o que é verdadeiro,
supor que tudo que não é mencionado nem dedutível é falso
(hipótese do mundo fechado)
Operador de negação por falha

Podemos usar o ! para implementar um operador de negação
por falha, tal que:

not p(X) verificado sse p(X) falha
Negação por falha

Uma maneira de definir a negação por falha:
not(P) :- P, !, fail
;
true.


fail é o objetivo que sempre falha, enquanto que true sempre
tem sucesso.
not já é pré-definido (built-in) no interpretador prolog, como
um operador pré-fixo.
- not true.
no
- not fail.
yes
Voltando ao exemplo da família...

Definimos a relação sister(X, Y) como:



sister(X, Y) :- female(X), parent(Z, X), parent(Z, Y).
Vimos que isso também deduz que uma mulher é irmã dela
mesma: logicamente correto pela definição acima.
Podemos usar a negação por falha para alcançar o resultado
desejado.

sister(X, Y) :- female(X), parent(Z, X), parent(Z, Y), not(X = Y).
Exemplo da família
pam
- sister(X, pat).
X = ann;
no
tom

bob
liz

Conforme o comportamento
esperado.
Experimento:

ann
pat


jim
Modifique a relação sister(X,
Y) para
sister(X, Y) :- not(X = Y),
female(X), parent(Z, X),
parent(Z, Y).
Agora consulte:

- sister(X, pat).
O que aconteceu?

Afinal de contas de acordo com a lógica:



a  b  c  d  e é equivalente a d  a  b  c  e
Negação por falha não tem a mesma semântica da negação
da lógica.
Vamos acompanhar o trace da consulta:
- trace.
- sister(X, pat).
(0) Call: sister(_h446,pat)
(1) Call: not _h446 = pat ?
(1) Fail: not _h446 = pat ?
(0) Fail: sister(_h446,pat)
? c
c
c
? c
O que aconteceu? (2)

Problema com objetivos não instanciados



Quantificação de variáveis diferente na negação por falha
not(X = pat) não é interpretado como “existe X tal que
not(X = pat)”
A quantificação na negação por falha é universal



Para todo X: not(X = pat)?
O que é claramente falso, pois X (não instanciado) unifica-se
perfeitamente com pat
Conclusão: cuidado ao usar cuts e negação por falha.
Prolog: listas
[ e ]: início e fim de lista
, separação entre elementos
|: separação entre 1° elemento (cabeça) e resto da lista (calda)
açúcar sintático para predicado .(Head,Tail)
ex.: [a,[b,c],d] açúcar sintático para .(a,.(.(b,.(c,[])),.(d,[])))
- [a,b,X,p(Y,C)] = [Head|Tail]
Head = a, Tail = [b,X,p(Y,C)]
- [[p(X),[a]],q([b,c])] = [[H|T1]|T2]
H = p(X), T1 = [[a]], T2 = [q([b,c])]
- member(X,[X|_]).
- member(X,[Y|Z]) :- member(X,Z).
- member(b,[a,b,c]) -> yes.
- member(X,[a,b,c]) -> X = a ; X = b ; X = c ; no.

Exemplo: Append


append(L1, L2, L3): L1 e L2 são duas listas e L3 é a sua
concatenação.
Append de uma lista vazia com uma segunda lista é a própria
segunda lista:


append([], L, L).
Append de uma lista [X|L1] com a lista L2 é uma lista [X|L3],
onde L3 é a concatenação da cauda da primeira (L1) com L2.

append([X|L1], L2, [X|L3]) :append(L1, L2, L3).
Exemplo: Append (2)

Exemplos do uso do append

Qual o resultado da concatenação das listas [a, b] e [c, d]?



- append([a,b], [c,d], X).
X = [a, b, c, d]
Que listas concatenadas resultam na lista [a, b, c, d]?






- append(X, Y, [a, b, c, d]).
X = []
Y = [a,b,c,d];
X = [a]
Y = [b,c,d];
…
Exercícios 3


Usando o append, escreva uma regra para apagar os três
últimos elementos de uma lista L, produzindo uma lista L1
(arquivo append.P)
Defina a relação last(Item, List) de forma que Item é o último
elemento de List de duas formas diferentes:


usando append
sem usar append
Prolog x prog. imperativa

Interativo:




compilação transparente integrada na interpretação
rodar programa = consultar um BD
Gerenciamento automático da memória
Mecanismo único de manipulação de dados -- unificação de
termos lógicos -- implementando:




atribuição de valor
passagem de parâmetros
alocação de estruturas
leitura e escrita em campos de estruturas
Prolog x prog. imperativa (2)

Estrutura de dados única: termo Prolog


variáveis lógicas sem tipo estático (tipos dinâmicos)
Controle implícito built-in na estratégia de resolução, ex: Em
programação imperativa
procedure c(E)
const e0:tipoE0;
var E:tipoE, S0:tipoS0, l1:tipo-I1, S1:tipoS1;
do if E = e0 then do S0 := call p0(e0); return S0; end;
else do I1 := call p1(E); S1 := call p2(E,l1); return S1; end;
end;
Em Prolog
c(e0,S0) :- p0(e0,S0).
c(E,S1) :- p1(E,I1), p2(E,I1,S1).
Prolog x prog. funcional
Matematicamente, predicado = relação:
 não-determinismo:




bi-direcionalidade:



respostas múltiplas (disponíveis por backtracking),
unificação e busca built-in,
livra o programador da implementação do controle;
cada argumento pode ser entrada ou saída, dependendo do
contexto de chamada,
única definição para usos diferentes: verificador, instanciador,
resolvedor de restrições, enumerador.
integração imediata com BD relacional
Prolog x prog. funcional (2)

Append em Haskell:
append [] L = L
append H:T L = H : append T L
?- append([a,b],[c,d])
[a,b,c,d]

Append em Prolog:
append([],L,L).
append([H|T1],L,[H|T2]) :- append(T1,L,T2).
?- append([a,b],[c,d],R).
R = [a,b,c,d].

Append relacional codifica várias funções
Vários usos do mesmo predicado

verificador:
?- append([a,b],[c],[a,b,c]). -> yes.
?- append([a,b],[c],[a]). -> no.

instanciador:
?- append([a,b],[c],R). -> R = [a,b,c].
?- append(H,[c],[a,b,c]). -> H = [a,b].

resolvedor de restrições:
?- append(X,Y,[a,b,c]). -> X = [], Y = [a,b,c]
; -> X = [a], Y = [b,c] ...

enumerador:
?- append(X,Y,Z). -> X = [], Y =[], Z = []
; -> X = [_], Y = [], Z = [_] ...
Prolog x programação OO

Funcionalidades built-in:



+ unificação e busca
- tipos, herança e encapsulamento
Ontologicamente:





Entidade Atômica (EA): em OO, valor de tipo built-in
em Prolog, átomo (argumento ou predicado)
Entidade Composta (EC): em OO, objeto
em Prolog, fato
Relação simples entre EC e EA: em OO, atributo de tipo built-in
em Prolog, posição em um predicado
Relação simples entre ECs: em OO, atributo de tipo objeto
em Prolog, predicado
Relação complexa entre entidades: em OO, método
em Prolog, conjunto de regras
Prolog x programação OO:
exemplo

Em OO:
pt[subclass_of planobj;
attrs[X inst_of int, Y inst_of int];
mets[right(Pt inst_of pt) {return self.X >= Pt.X}]]
pt1[inst_of pt; attrs[X = 0, Y = 0]]
pt2[inst_of pt; attrs[X = 1, Y =1]]
?- pt1.right(pt2) -> no.

Em Prolog:
pt(0,0).
pt(1,1).
planobj(pt(_,_)).
right(pt(X1,_),pt(X2,_)) :- X1 >= X2.
?- right(pt(0,0),pt(1,1)). -> no.
Programação em Lógica: Disciplina
Eletiva de Graduação e Pós


Prolog aprofundado
Programação por resolução de restrições a base lógica
(Constraint Logic Programming)






extensão de Prolog com resoluções de inequações e equações
restrições quantitativas (N, Z, R, C)
ou qualitativas (tipos, ontologias)
Escalonamento, raciocínio espacial, otimização,
automação industrial, CAD/CAM, música computacional
Programação em lógica funcional
Programação em lógica orientada a objetos
Programação multiparadigma a base lógica:


lógica + restrições + funcional + OO
todo a IA e mais !
Programação em Lógica: Disciplina
Eletiva de Graduação e Pós

Programação em lógica para engenharia de software



Programação em lógica probabilista e bayesiana


raciocínio com incerteza
Programação em lógica indutiva


especificação formal  prototipagem rápida
aceleração do modelo de desenvolvimento em espiral
aprendizagem de máquina, agentes adaptativos,
mineração de dados, descoberta de conhecimento em BD,
programação automática, bio-informática
Programação em lógica multiagentes



sistemas inteligentes distribuídos
comercio eletrônico
jogos, competição de futebol de robôs
Programação em Lógica: Disciplina
Eletiva de Graduação e Pós

Bancos de dados dedutivos:




Bancos de dados dedutivos orientada a objetos
Bancos de dados dedutivos temporais
Bancos de dados de restrições:


GIS, BD espaciais, BD espaço-temporais,
integração de dados e interoperabilidade
Bancos de dados de restrições orientada a objetos


descoberta de conhecimento em BD, sistemas especialistas de
grande porte, servidores de conhecimento ontológico
toda a IA de grande escala e mais !
Bancos de dados probabilistas:

BD de sensores, data warehousing, integração de dados com fontes
não confiáveis ou mutuamente inconsistentes,
Programação em Lógica: Disciplina
Eletiva de Graduação e Pós

Gramáticas lógicas:





Parser e gerador de linguagem built-in em Prolog
Basta desenvolver gramática (i.e., como com lex e yacc)
Mineração da web, extração de informação na Internet, compilação
tradução automática, geração automática de resumos, chatterbots
APIs Prolog/Java e Prolog/XML

sistemas de informação inteligentes distribuídos e heterogêneos a infraestrutura web





integração de dados, interoperabilidade entre sistemas, mediadores, data
warehousing
comercio eletrônico
agentes inteligentes de recuperação, classificação, extração e notificação
de informação na web, na Internet, em Intranet
inteligência na computação pervasiva
toda a IA embutida e mais !
Programação em Lógica:
Disciplina Eletiva de Graduação e
Pós-Graduação

Aplicação fio condutor para ilustração dos conceitos

“By the year 2050, develop a team of fully autonomous humanoid
robots that can win against the human world soccer champion team.”
http://www.robocup.org
Programação em Lógica: Disciplina
Eletiva de Graduação e Pós
Introdução a Prolog
FIM
Exercício 1 - Respostas
mother(X, Y) :- parent(X, Y), female(X).
sister(X, Y) :- female(X), parent(Z, X), parent(Z, Y).
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
aunt(X, Y) :- sister(X, Z), parent(Z, Y).



Quais são as respostas devolvidas para sister(X, pat). ?
Por que isso ocorre?
Como isso pode ser evitado?

Cenas dos próximos slides...
Exercício 2 - Resposta
fib(1, 1).
fib(2, 1).
fib(N, Fn) :N > 2,
M is N - 1,
fib(M, Fm),
O is N - 2,
fib(O, Fo),
Fn is Fm + Fo.


O programa tem
comportamento exponencial,
para cada passo calculamos
toda a seqüência de fibonacci.
Os mesmos valores são
calculados várias vezes...
Exercícios 3 - Resposta
del3(L, L1) :- append(L1, [_, _, _], L).
last(Item, List) :- append(_, [Item], List).
last2(Item, [Item]).
last2(Item, [_|XL]) :- last2(Item, XL).