Sintaxe e Semântica
do
PROLOG
Introdução à programação em Prolog
PROLOG = PROgramming in LOGic
Linguagem baseada num subconjunto da lógica de predicados de 1ª ordem
(cláusulas de Horn)
programa = conjunto de cláusulas (axiomas)
Cláusulas:
A :- A1, ... , An. Regra ou cláusula não unitária
A é verdadeiro se A1 e ... e An são verdadeiros.
Uma forma de resolver A é resolver A1 e ... e An.
A.
Lógica para Programação
Facto ou cláusula unitária
A é verdadeiro.
2
Introdução à programação em Prolog
Exemplo de programa P:
gosta(jorge, futebol).
gosta(jorge, cinema).
gosta(maria,X) :- gosta(X, futebol), gosta(X, cinema).
Interrogações ou perguntas (“queries”) sobre o programa P:
?- gosta(jorge, futebol).
(gosta(jorge,futebol) prova-se a partir de P ?)
yes.
?- gosta(jorge, maria).
no.
?- gosta(jorge,X).
(Existe algum valor para X tal que
gosta(jorge,X) se prova a partir de P)
X = futebol;
(‘;’ indica “procure outra resposta”)
X = cinema;
no.
(não há mais respostas)
Lógica para Programação
3
Introdução à programação em Prolog
 O Prolog é uma linguagem de programação para computação simbólica
(não numérica), particularmente, adaptada à resolução de problemas que
envolvam objectos e relações entre objectos, num determinado
contexto.
 Definir cada relação através de tuplos de objectos (lista dos argumentos da
relação) que satisfazem (i.e. tornam verdadeira) essa relação.
 Cada argumento da relação pode ser uma constante (objectos concretos
num determinado contexto) ou uma variável que denotam um objecto
arbitrário num determinado contexto.
 Questionar o programa acerca das relações definidas, i.e. para cada
questão, introduzir uma conjunção de objectivos que devem ser
satisfeitos pelo programa.
 As respostas às questões podem ser positivas (no caso do objectivo ser
satisfeito, assim, diz-se que o objectivo é bem sucedido) ou negativas (no
caso do objectivo não ser satisfeito, assim, diz-se que o objectivo falhou).
Lógica para Programação
4
Sintaxe e Semântica dos Programas em Prolog
SINTAXE
termos
termos simples
constantes
átomos
Lógica para Programação
inteiros
termos compostos
variáveis
reais
5
Sintaxe e Semântica dos Programas em Prolog
 ÁTOMOS
 Correspondem a nomes próprios em linguagem natural que
representam relações, funções ou objectos.
 Podem ter as seguintes formas
 sequências de letras do alfabeto latino, dígitos ou ‘_’,
iniciadas por uma letra minúscula (e.g. gosta, jorge,
ana_maria, x, a1);
 sequências de caracteres especiais (‘+’, ’-‘, ’*’, ’/’, ’\’, ’:’, ’=’,
etc.) Ex: :-, >, >=, -->, $$
(Cuidado: algumas sequências têm significado pré-definido
como, por exemplo, a sequência ‘:-‘);
 sequências de caracteres entre plicas (e.g. ‘Bom dia’, ‘123’).
Lógica para Programação
6
Sintaxe e Semântica dos Programas em Prolog
INTEIROS E REAIS
Exemplos
0, 999, -12, 1.0, -13.8e+8, 
A amplitude da representação dos inteiros e reais depende da implementação do
Prolog.
VARIÁVEIS
Representam objectos definidos mas não identificados; variáveis no sentido matemático
e não no sentido habitual atribuído nas linguagens de programação imperativa.
 sequências de letras, dígitos ou ‘_’, iniciadas por uma letra maiúscula ou por ‘_’
Exemplos
X, L, Lista, Valor, _3
 variáveis anónimas
Se uma variável ocorre somente uma vez numa cláusula, não necessita ter um
nome e, assim, pode ser nomeada (anonimamente) por ‘_’.
Exemplo
gosta(ana,X):- bonito(X),tem_carro_marca(X,_).
Lógica para Programação
7
Outro Exemplo
Para qualquer X, X tem um filho se X é progenitor de Y.
has_child(X) : parent(X,Y)
pam
tom
Como a variável Y ocorre apenas uma vez no corpo da
cláusula, pode ser substituída por uma variável
anónima.
has_child(X) : parent(X,_)
liz
bob
Para a árvore genealógica ao lado que resultados
obtemos para os objectivos que se seguem?
?  has_child(X).
ann
pat
?  parent(X,_).
Nota
O alcance de uma variável está restrito à claúsula onde
ocorre.
Lógica para Programação
jim
8
Termos Compostos
Um termo composto é formado a partir de um functor que define um objecto
estruturado (ou estrutura), i.e. um objecto constituído por componentes
(termos simples ou compostos)
Exemplo
A data pode ser representada por uma estrutura constituída por três
componentes: dia, mês e ano.
data(25,abril,1974)
Representação de um functor
Um functor é representado por um nome (na sintaxe associada aos átomos)
concatenado com uma sequência de termos simples ou compostos, separados
por vírgulas, e delimitados à esquerda pelo parêntesis esquerdo e à direita
pelo parêntesis direito.
O functor caracteriza-se pelo seu nome e a sua aridade.
Lógica para Programação
9
Termos Compostos
functor argumento
Exemplo
maior(
sucessor( N )
,
N )
termo composto termo simples
functor principal
1º argumento
2º argumento
termo composto
Nota
Podemos associar o mesmo nome a functores diferentes (a aridade distingue
um functor) como, por exemplo, no caso de ponto(X,Y) e ponto(X,Y,Z).
Lógica para Programação
10
Termos Compostos
functores como operadores
É conveniente, por vezes, escrever alguns functores binários (com aridade 2)
como operadores infixos e functores unários como operadores prefixos ou
sufixos.
Exemplo
X*Y, A>B+X, X+2*Y como representação alternativa de,
respectivamente, *(X,Y), >(A,+(B+X)), +(X,*(2,Y)).
Nota
A possibilidade de utilizar essa notação mais conveniente está dependente da
declaração do functor como operador com determinado tipo e precedência
(pré-definida para os operadores aritméticos usuais e alguns outros).
Lógica para Programação
11
Termos Compostos
cláusulas como termos compostos
Uma cláusula da forma:
A :- A1, ..., An.
é um termo composto constituído pelo functor especial ‘:-‘ aplicado ao termo A,
designado por cabeça da claúsula, e à conjunção dos termos A1,...,An,
designada por corpo da cláusula (a especificação de uma cláusula termina
sempre com um ponto).
Lógica para Programação
12
Objectivos e Predicados
Os termos principais que ocorrem numa cláusula (ou numa
interrogação) são chamados objectivos. Assim, um objectivo é um
termo que se distingue apenas pelo contexto em que ocorre.
A cabeça de uma cláusula é constituída por um único objectivo.
O corpo pode ser constituído por zero ou mais objectivos.
As claúsulas sem corpo (factos) e com cabeça A são escritas na
forma: A.
O predicado (ou procedimento) para um dado functor, num
programa, é o conjunto de claúsulas cuja cabeça tem esse
functor como functor principal.
Exemplo
gosta(X, Y) :- irmão(X, Y).
gosta(X, Y) :- pai(X,Y).
predicado gosta
gosta(ana, josé).
pai(raul, maria).
pai(X, Y) :- filho(Y, X).
Lógica para Programação
predicado pai
13
Instâncias de cláusulas
Uma instância de uma cláusula é obtida substituindo uniformemente uma variável por
um novo termo, para zero ou mais das variáveis da cláusula.
Exemplo:
cláusula:gosta(X, Y) :- gosta(X, Z), gosta(Z, Y).
Instâncias
gosta(X1, Y1) :- gosta(X1, Z1), gosta(Z1, Y1).
gosta(X, X)
:- gosta(X, Z), gosta(Z, X).
gosta(ana,Y) :- gosta(ana, Z), gosta(Z, Y).
gosta(ministro(a), b) :gosta(ministro(a), W), gosta(W, b).
Lógica para Programação
Substituições
{ X/X1, Y/Y1, Z/Z1}
{ Y/X }
{ X/ana }
{X/ministro(a), Y/b, Z/W}
14
Unificação
Um objectivo O1 unifica com outro objectivo O2, se existe uma
instância comum de O1 e de O2 (obtida por uma substituição s).
gosta(X, jorge) unifica com gosta(ana,X) ? Não
Unificação de um objectivo O com a cabeça de uma cláusula C:
gosta(X, jorge) unifica com a cabeça de
gosta(ana,X) :- gosta(X,fut), gosta(X,cin). ?
As variáveis de uma cláusula são variáveis locais dessa cláusula.
Podemos renomear as variáveis numa cláusula, de modo a que não
tenha variáveis em comum com o objectivo dado, sem alterar o seu
significado.
gosta(ana,X1) :- gosta(X1,fut), gosta(X1,cin).
Lógica para Programação
15
Unificação
 Quando dizemos informalmente que um objectivo O unifica com a
cabeça de uma cláusula C, pretendemos dizer que unifica com a
cláusula, após renomear as suas variáveis de modo a não ter
variáveis em comum com O.
gosta(X, jorge)
unifica com a cabeça de
gosta(ana,X1) :- gosta(X1,fut), gosta(X1,cin).
?
Sim!
Lógica para Programação
16
SEMÂNTICA DECLARATIVA DE UM PROGRAMA
Um objectivo é verdadeiro se unifica com a cabeça de uma claúsula C e se todos
os objectivos no corpo da instância de C resultante da unificação são verdadeiros.
 Definição recursiva
 Não refere a ordem das cláusulas no programa nem a ordem dos objectivos
no corpo das cláusulas
Exemplo
programa P:
significado declarativo de P:
descende(X,Y) :- descende(X, Z), filho(Z,Y). X Y Z (descende(X, Z)  filho(Z, Y) 
descende(X, Y) )
descende(X,Y) :- filho(X,Y).
 X Y ( filho(X, Y)  descende(X, Y) )
filho(rui, carlos).
 filho(rui, carlos)
filho(jorge, rui).
 filho(jorge, rui).
Segundo a semântica declarativa de P, o objectivo descende(jorge, carlos) é
verdadeiro.
Lógica para Programação
17
SEMÂNTICA PROCEDIMENTAL/OPERACIONAL DE UM PROGRAMA
 Define como é que o processador do Prolog executa (ou satisfaz) um
objectivo/interrrogação sobre um programa P
 A execução de um objectivo pode
 terminar com sucesso (obtendo-se a resposta “yes” ou valores para as
variáveis do objectivo)
 ou terminar com insucesso ou falha (obtendo-se a resposta “no”)
 ou não terminar.
 A execução de um objectivo O com functor principal F é encarada
como uma chamada do procedimento para F. Para executar O, o
processador procura, sequencialmente nas cláusulas do procedimento
F, a 1ª cláusula cuja cabeça unifica com O, e tenta executar o seu
corpo. Se não tiver sucesso, continuará a procura a partir da cláusula
seguinte de F.
 A ordem das cláusulas no programa e a ordem dos objectivos no
corpo das cláusulas são relevantes.
Lógica para Programação
18
SEMÂNTICA PROCEDIMENTAL/OPERACIONAL DE UM PROGRAMA
A execução de um objectivo O sobre um programa P, corresponde a:
(1)
Posicionar-se no início de P;
(2)
Procurar a próxima cláusula C cuja cabeça unifica com O,
(seja CI a instância de C resultante dessa unificação)
(2.1) Se existe e tem corpo vazio, termina com sucesso.
(2.2) Se existe e tem corpo não vazio, então executar o corpo de
CI (isto é, reduzir a execução de O à execução do corpo de
CI);
(2.1.1) Se a execução do corpo de CI for bem sucedida, então
termina com sucesso
(2.1.2) Se a execução do corpo de CI falhar, então voltar a
(2). (retrocesso ou “backtracking”)
(2.3) Se não existe, a execução falha.
A execução de uma sequência de objectivos O1, ..., On, corresponde a executar O1,
obtendo uma substituição de variáveis s1, e executar a sequência O2’,..., On’, onde
O2’,...,On’ são as instâncias de O2,...,On, resultantes da aplicação de s1.
Lógica para Programação
19
Interpretação declarativa vs procedimental
Interpretação Declarativa
Incide sobre as relações definidas no programa e, assim, determina
qual o output (i.e. a resposta) do programa para um dado input (i.e.
para uma dada questão).
Interpretação Procedimental
Incide sobre como o programa produz um output para um dado input,
i.e. como as relações são valiadas pela implementação do Prolog.
A abstracção dos detalhes envolvidos na interpretação procedimental
dos programas é considerada uma vantagem visto que, assim, permite
ao programador concentrar-se essencialmente nos aspectos
declarativos da programação. Mas, em programas relativamente
grandes, os aspectos procedimentais não podem ser total ignorados
por razões de eficiência na execução dos programas.
Lógica para Programação
20
Árvore de execução
 Representação da sequência de estados da execução de um objectivo.

representa sucesso ;
representa falha
 Diferentes ramos terminados por
representam diferentes soluções
?- gosta(X,Y)
Exemplo 1:
{X/maria }
{X/jorge,Y/fut}
Programa
{X/jorge,Y/cin}
gosta(jorge, fut).
gosta(jorge, cin).
gosta(maria,X) :- gosta(X, fut), gosta(X, cin).
Interrogação
?- gosta(X,Y) .
Lógica para Programação
gosta(Y,fut), gosta(Y,cin)
{Y/jorge}
gosta(jorge,cin)
{Y/maria }
gosta(fut,fut), gosta(fut,cin)
gosta(maria,cin)
21
Árvore de execução
Exemplo 2:
descende(X,Y) :- filho(X,Y).
descende(X,Y) :- descende(X, Z), filho(Z,Y).
?- descende(jorge,carlos)
filho(rui, carlos) .
filho(jorge,carlos)
filho(jorge, rui).
descende(jorge,Z), filho(Z, carlos)
filho(jorge,Z), filho(Z, carlos)
filho(rui, carlos)
descende(jorge,Z1), filho(Z1,Z), filho(Z, carlos)
filho(jorge,Z1), filho(Z1,Z), filho(Z, carlos)
filho(rui,Z), filho(Z, carlos)
filho(carlos, carlos)
Lógica para Programação
22
…
Exemplo 3
Árvore genealógica
família Smith
(parcial)
da
pam
tom
Objectos
pam, tom, bob, liz, ann, pat e jim
Relação
X é ascendente de Y (predicado
parent(X,Y))
ann
Instâncias (da relação parent no
contexto da família Smith)
parent(pam,bob), parent(tom,bob),
parent(tom,liz), parent(bob,ann),
parent(bob,pat) e parent(bob,jim)
Lógica para Programação
liz
bob
pat
jim
23
Exemplo 3 (objectivos)
pam
? – parent(bob,pat). (“O bob é ascendente de pat?”)
tom
yes
? – parent(liz,pat). (“A liz é ascendente de pat?”)
no
liz
? – parent(tom,ben). (“O tom é ascendente de pam?”)
bob
no
? – parent(X,liz). (“Quem são os ascendentes de liz?”)
X = tom;
ann
pat
no
? – parent(bob,X). (“Quem são os descendentes de bob?”)
jim
X = ann;
X=jim;
X= pat;
no
? – parent(X,Y). (“Quem é descendente de quem?”)
? – parent(tom,X),parent(X,Y).
X = pam
(“Quem são os filhos e os netos de tom”)
Y = bob;
X = bob
? – parent(X,ann),parent(X,pat)
Y = ann;
(“Quem é ascendente de ann e pat?”)
X = bob
X = bob;
Y = jim;
no
…
Lógica para Programação
24
