0% acharam este documento útil (0 voto)

15 visualizações63 páginas

Fundamentos de Prolog: Sintaxe e Conceitos

Enviado por

valney.maia

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

0% acharam este documento útil (0 voto)

15 visualizações63 páginas

Fundamentos de Prolog: Sintaxe e Conceitos

Enviado por

valney.maia

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Fundamentos de Linguagens de Programação

Prolog

Nelson Carvalho Sandes

Centro de Ciências Tecnológicas - CCT

Universidade Federal do Cariri

2022

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Visão Geral

Prolog é uma linguagem de programação que utiliza o

paradigma lógico.
Normalmente é aplicada em Inteligência Artificial e Linguı́stica
Computacional.
Ela é uma linguagem declarativa. Ou seja, ao invés de se
programar passo à passo um conjunto de instruções,
normalmente é fornecido uma descrição do problema que se
pretende resolver.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Conceitos

Em prolog exitem três conceitos que são fundamentais: fatos,

regras e objetivos.
Uma coleção de fatos e regras é denominada de base de
conhecimento. Boa parte da programação em Prolog nada
mais é do que a escrita de bases de conhecimento.
Após a construção de nossa base de conhecimento, podemos
alcançar nossos objetivos através de perguntas (queries)
realizadas.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

[Base de Conhecimento 1]: 5 fatos

Consultas
?- mulher(mia).
Base de Conhecimento 1 true
mulher(mia). ?-
tocaGuitarra(jody).
mulher(jody).
true
mulher(yolanda).
?-
tocaGuitarra(jody). tocaGuitarra(mia).
festa. false
?- festa.
true
Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri
Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

[Base de Conhecimento 2]: 2 fatos e 3 regras

Base de Conhecimento 2
feliz(yolanda).
Consultas
ouveMusica(mia).
?- tocaGuitarra(mia).
ouveMusica(yolanda) :-
true
feliz(yolanda).
?-
tocaGuitarra(mia) :-
tocaGuitarra(yolanda).
ouveMusica(mia).
true
tocaGuitarra(yolanda) :-
ouveMusica(yolanda).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Caracterı́sticas lógicas

Na base de conhecimento 2, utiliza-se a regra de inferência

”modus ponens”.
Além disso, em prolog, podemos representar conjunções e
disjunções utilizando vı́rgula ”,” e ponto e vı́rgula ”;”
respectivamente.
Levando em consideração a base 1:
1 mulher(mia) , mulher(marta). - false
2 mulher(marta) ; mulher(mia). - true

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

[Base de Conhecimento 3]: 5 fatos

Base de Conhecimento 3
Consultas
mulher(mia).
?- mulher(X).
mulher(jody).
X = mia;
mulher(yolanda).
X = jody;
gosta(vicent, mia).
X = yolanda
gosta(marsellus, mia).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

[Base de Conhecimento 3]: 5 fatos

Base de Conhecimento 3 Consultas

mulher(mia). ? - gosta(X, mia).

mulher(jody). X = vicent;

mulher(yolanda). X = marsellus

gosta(vicent, mia). ? - gosta(vicent, X),

mulher(X).
gosta(marsellus, mia).
X = mia

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe de Prolog
Termos

Agora que temos uma noção de PROLOG, podemos analisar

os detalhes de forma mais cuidadosa.
Como construimos fatos, regras e objetivos? - Através de
termos.
Em prolog, existem 4 tipos de termos: átomos, números,
variáveis e termos complexos.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Sı́mbolos à disposição

Antes de entender um termo, precisamos entender os sı́mbolos

que estão disponı́veis em PROLOG.
Pode-se utilizar letras letras maiúsculas: A, B, ..., Z; letras
minúsculas: a, b, ..., z.
Também é possı́vel usar digitos: 0, 1, 2, ..., 9; caracteres
especiais: +, -, *, /, <, >.
O espaço em branco também é considerado um sı́mbolo,
embora seja invisı́vel.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Termos - Átomos

Um átomo é:
1 Um conjunto de caracteres que começa com letra minúscula e
pode conter letras maiúsculas, digitos e o carácter underscore
( ): maria, homem, hamburguer big, tocaGuitarra.
2 Uma sequência de caracteres entre aspas simples: ’Vicent’,
’Batido ao Leite’, ’&$#abc’, ’ha ha’.
3 Uma sequência de caracteres especiais: ===@, ; e :- são
átomos. Alguns desses átomos tem significados especiais na
linguagem.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Termos - Números

Ponto flutuante:
Apesar dos números reais não serem tão comuns nas aplicações
de prolog, elas suportam números ponto flutuante: 1657.3087
Inteiros
Os números iteiros (...-2, -1, 0, 1, 2, 3 ...) vão ser úteis em
diversas aplicações de prolog. Por exemplo: contar o números
de elementos de uma lista. Exemplos: 23, 1001, 0, -365.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Termos - Variáveis

Uma variável é uma cadeia de caracteres que inicia com letra

maiúscula ou underscore. Ela pode conter letras minúsculas,
digitos e o sı́mbolo underscore.
Exemplos: X, Y, X 526, Lista, Cauda, input.
A variável constituı́da apenas por um underscore é especial.
É designada por variável anônima e será discutida
posteriormente.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Termos complexos

Os átomos, os números e as variáveis são componentes

básicos. Agora, precisamos saber em como os combinar para a
obtenção de termos complexos.
Os termos complexos são constituı́dos por um functor seguido
de uma sequência de argumentos.
Um functor precisa ser um átomo, ou seja, as variáveis não
podem ser usadas como functores. Por outro lado, os
argumentos podem ser quaisquer termos.
Exemplo: tocaGuitarra(jody), gosta(vicent, mia) e
temCiume(marsellus,W).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Termos complexos

A definição de functor nos permite escrever termos mais

complexos do que os vistos anteriormente.
Por exemplo, é possı́vel construir termos complexos a partir de
outros termos complexos
esconde(X, pai(pai(pai(maria))))
O termo acima é um termo complexo que está de acordo com
a definição. Ele possui um functor que é um átomo e
argumentos que podem ser quaisquer termos.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Aridade

O número de argumentos que um termo complexo tem é a

sua aridade.
Por exemplo, mulher(mia) é um termo complexo de aridade 1.
Por outro lado, gosta(vicent, mia) é um termo complexo de
aridade 2.
A aridade é importante em prolog, já que é permitido que se
definam dois functors com o mesmo nome e aridades
diferentes.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Sintaxe Prolog
Aridade

É possı́vel ter os termos gosta(vicent, mia) de aridade 2 e

gosta(vicent, marsellus, mia) de aridade 3;
Nesse caso, o prolog vai considerar o predicado gosta, de
aridade 2, diferente do predicado gosta de aridade 3.
Na documentação de prolog é comum representar os
predicados com o sufixo / seguido de um número que indica a
sua aridade. Levando em consideração a base de
conhecimento 3 (slide 9), terı́amos a nomeclatura:
mulher/1
gosta/2

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Exercı́cios
Quais das sequências de caractere são átomos, quais são variáveis e quais não são nem
uma coisa nem outra?

vINCENT
’hamburguer big kahu’
Massagem
hamburguer big kahu
variavel123
’ Jules’
Variavel2000
Jules
hambuguer big kahuna

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Exercı́cios
Definir quem é átomo, variável, termos complexos e quais não são termos

gosta(Vincent, mia)
e(gr hamb(X), kah(X))
’gosta(Vicent, mia)’
e(gr hamb(a), kah(b))
Butch(pugilista)
(Butch mata Vincent)
pugilista(Butch)
mata(Butch Vincent)
hambuguer big kahuna

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Unificação

Ao responder uma consulta, o interpretador Prolog precisa

instanciar variáveis. Isto é, atribuir valor às variáveis.
Informalmente, dizemos que dois termos podem ser
unificados se eles são iguais ou se possuem variáveis que
podem ser instanciadas de forma a tornar os termos identicos.
Por exemplo:
mia e mia.
2 e 2.
X e mia.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Unificação

De um jeito formal, podemos dizer que dois termos podem ser

unificados se, e somente se, uma das condições abaixo for
verdadeira:
1 Os dois termos são constantes (números ou átomos) e iguais.
2 Um dos termos é uma variável.
3 Ambos os termos são complexos com o mesmo functor, a
mesma aridade e os argumentos correspondentes podem ser
unificados.
O predicado = pode ser usado para verificar se dois termos
são unificáveis.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Unificação

Exemplos corretos de unificação

=(casa, casa).
=(pai(james, harry), pai(X, harry)).
’mia’ = mia.
X = mia.
=(X, Y).
k(s(g), Y) = k(X, t(k))
Exemplo incorreto:
gosta(X, X) = gosta(vincent, mia).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Demonstração de Pesquisa

Agora que sabemos sobre

Base de Conhecimento
unificação, veremos como
o Prolog realiza uma busca f(a).
na base de conhecimento f(b).
para verificar se um objetivo g(a).
é satisfeito.
g(b).
Qual o passo à passo do
h(b).
prolog quando realizamos
executamos a query: k(X). k(X) : f(X), g(X), h(X).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Demonstração de Pesquisa
Busca na base de conhecimento

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Demonstração de Pesquisa

Base de Conhecimento
Agora vamos considerar a
seguinte base ao lado. loves(vincent, mia).
O que o Prolog faria na loves(marcellus, mia).
busca jealous(X, Y). ? jealous(X, Y) :- loves(X,
Z), loves(Y, Z).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Demonstração de Pesquisa
Busca na base de conhecimento

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão

Também é possı́vel definir um predicado recursivamente.

Informalmente, um predicado é definido por recursão se numa
ou mais regras da sua definição houver referências a si próprio.
Vamos discutir um exemplo prático para ver a importância da
recursão na linguagem prolog: O problema dos descendentes.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão

Considerando a base de
conhecimento ao lado, qual Base de Conhecimento
seria o problema da regra
filho(bridget, caroline).
descendente?
filho(caroline, donna).
Ela seria falha se
estivéssimos buscando uma descendente(X, Y) :-
descedência maior. Por filho(X, Y).
exemplo, na busca de uma descendente(X, Y) :-
descedência entre uma filho(X, Z), filho(Z, Y).
pessoa e o seu bisavô.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão

Base de Conhecimento
filho(bridget, caroline).
Poderı́amos tratar o
filho(caroline, donna).
problema adicionando mais
regras. filho(donna, emily).
Solução deselegante, já que descendente(X, Y) :-
se acrescentássemos mais filho(X, Y).
fatos a respeito da relação descendente(X, Y) :-
filho, terı́amos que adicionar filho(X, Z), filho(Z, Y).
mais regras. descendente(X, Y) :-
filho(X, Z 1), filho(Z 1,
Z 2), filho(Z 2, Y).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão

Utilizar uma regra com Base de Conhecimento

recursão é útil nesses casos. filho(martha, charlotte).
A solução vai cobrir os filho(charlotte, caroline).
diversos casos e, ao mesmo
tempo, não precisará ser filho(caroline, laura).
modificada a medida que filho(laura, rose).
fatos são adicionados. descendente(X, Y) :-
Qual busca o prolog iria filho(X, Y).
realizar com a querie descendente(X, Y) :-
descendente(martha, filho(X, Z),
laura)? descendente(Z, Y).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão
Busca

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão
Exercı́cio

Considerando a seguinte base de conhecimento:

vooDireto(saarbruecken, dudweiler).
vooDireto(forbach, saarbruecken).
vooDireto(freyming, forbach).
vooDireto(stAvold, freyming).
vooDireto(fahlquemont, stAvold).
vooDireto(metz, fahlquemont).
vooDireto(nancy, metz).
Criar um predicado recursivo viajar de para/2 que indique
quando é possı́vel viajar entre duas cidades. Por exemplo,
viajar de para(nancy, saarbruecken) deve retornar true.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Definição

Uma lista pode ser vista como um conjunto de itens. Por

exemplo:
[mia, vincent, jules, yolanda]
[mia, ladrao(honey bunny), X, 2, mia]
[]
[mia, [vincent, jules], [butch, namorada(butch)]]
[[], morto(z), [2, [b, c]], [], Z, [2, [b, c]]]´

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Definição

Com os exemplos mostrados, podemos inferir algumas coisas

sobre as listas de prolog:
As listas são especificadas ao escrever os seus elementos entre
colchetes (os sı́mbolos[ e ]). Além disso, os elementos são
separados por vı́rgula.
A partir do segundo exemplo, podemos ver que qualquer
objeto Prolog pode fazer parte de uma lista. Temos mia, que é
um átomo; o segundo elemento é um termo complexo
ladrao(honey bunny); O terceiro elemento é uma variávei X; o
quarto elemento é 2, que é um número. Além disso o mesmo
elemento pode ocorrer mais de uma vez.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Definição

Continuando a análise do slide anterior:

O terceiro exemplo mostra uma lista vazia. A lista vazia é
aquela que não possui nenhum elemento. Ao definirmos o
comprimento de uma lista como a quantidade de elementos
que ela possui, podemos dizer que a lista vazia possui
comprimento 0.
O quarto exemplo ilustra a existência de listas que incluem
outras listas como seus elementos. O comprimento da lista
desse exemplo é 3.
Qual seria o comprimento das listas dos exepmlos 1 e 2?

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Cabeça e Cauda

Uma lista não vazia pode ser vista como sendo constituı́da de
duas partes:
Cabeça.
Calda.
A cabeça é simplesmente o primeiro item da lista; a cauda é
todo o resto.
De forma mais precisa, a cauda é a lista que sobra quando
removemos o primeiro elemento da lista. Desse modo, a
cauda de uma lista é sempre uma lista.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Cabeça e Cauda: Exemplos

Na lista [mia, vincent, jules, yolanda]

Cabeça: mia.
Calda: [vincent, jules, yolanda]
Já na lista: [[], morto(z), [2, [b, c]], [], Z, [2, [b, c]]]
Cabeça: [].
Calda: [morto(z), [2, [b, c]], [], Z, [2, [b, c]]]
Finalmente, na lista: [morto(z)]
Cabeça: morto(z).
Calda: []

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Cabeça e Cauda

A lista vazia não possui cabeça nem cauda.

Ou seja, ela não tem uma estrutura interna; para Prolog, [] é
uma lista especial.
A condição de lista especial em Prolog é útil ao se manipular
uma lista de forma recursiva.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Cabeça e Cauda

O Prolog possui um operador pré-definido | que pode ser

usado para decompor uma lista em cabeça e cauda.
A utilização mais óbvia de | é a extração de informação a
partir das listas. Por exemplo:
[X | Y] = [mia, vincent, jules, yolanda]
X = mia
Y = [vincent, jules, yolanda]
Já no exemplo abaixo, temos:
[X | Y] = []
false

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Cabeça e Cauda

Também podemos saber quais são os dois primeiros elementos

da lista utilizando o seguinte comando:
[X, Y| W] = [mia, vincent, jules, yolanda]
X = mia
Y = vincent
W = [jules, yolanda]

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Cabeça e Cauda

Suponha que queremos descobrir o segundo e quarto

elementos de uma lista:
[X1, X2, X3, X4| W] = [mia, vincent, jules, yolanda, marcos,
lucy, liz]
X1 = mia
X2 = vincent
X3 = jules
X4 = yolanda
W = [marcos, lucy, liz]
Essa abordagem pode não ser muito elegante. Podemos usar
a variável anônima para uma aboragem melhor.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Listas
Cabeça e Cauda

Suponha que queremos descobrir o segundo e quarto

elementos de uma lista:
[ , X2, , X4| ] = [mia, vincent, jules, yolanda, marcos, lucy,
liz]
X2 = vincent
X4 = yolanda
O sı́mbolo é uma variável anônima. Utilizamos quando
precisamos de uma variável mas não estamos interessados no
valor dela.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão e lista

Recursão e lista
Exemplo

Vamos analisar como escrever em prolog um termo complexo

que retorna verdadeiro caso um elemento pertença à uma
lista.
member(X, [X|T]).
member(X, [H|T]) :- member(X, T).
Como existem variáveis que não são de nosso interesse,
podemos reescrever da seguinte forma:
member(X, [X| ]).
member(X, [ |T]) :- member(X, T).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Recursão e lista

Recursão e lista
Exemplo

Vamos analisar o código member para o seguinte caso:

member(vincent, [yolanda, trudy, vincent, jules])
member(X, [X| ]).
member(X, [ |T]) :- member(X, T).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Tópicos

1 Introdução

2 Sintaxe de Prolog

3 Unificação

4 Demonstração de Pesquisa

5 Recursão

6 Listas
Recursão e lista
7 Aritmética

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética
Exemplo

Apesar da aritmética não ser tão presente nos problemas de

processamento simbólico, ela é importante para definir alguns
conceitos, como, por exemplo, o comprimento de uma lista.
A linguagem Prolog disponibiliza um certo número de
operações aritméticas básicas para manipular números inteiros
(...-3, -2, -1, 0, 1, 2, 3...) e números ponto flutuante.
Vamos analisar como Prolog trata as quatro operações básicas
de adição, multiplicação, subtração e divisão.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Operações em Prolog

Operações Aritméticas Notação em Prolog

6+2=8 8 is 6 + 2.
6 ∗ 2 = 12 12 is 6 * 2.
6-2=4 4 is 6 - 2.
6÷2=3 3 is 6/2.
7÷2=3 3 is 7/2.
1 é o resto de 7 ÷ 2 1 is mod(7,2).

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética
Exemplos

Notação em Prolog Notação em Prolog

8 is 6 + 2 X is 6 + 2.
true. X=8
-2 is 6 - 8 X is 6 - 2.
true. X=4
1 is mod(7,2). R is 6*2.
true. R = 12

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética
Regras

Também podemos criar regras utilizando aritmética. Por

exemplo, poderı́amos criar a regra:
soma 3 e duplica(X, Y) :- Y is (X + 3)*2
Dessa forma, se consultarmos soma 3 e duplica(3, Y), o
interpretador Prolog irá retornar:
Y = 12

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética
Regras

Ainda usando o exemplo:

soma 3 e duplica(X, Y) :- Y is (X + 3)*2
Temos que ter cuidado ao consultar:
soma 3 e duplica(X, 12).
Essa consulta daria um erro, já que terı́amos a expressão: 12
is (X+3)*2 e, como X não está instanciado, o interpretador
não consegue concluir a consulta.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética
Regras

O predicado is é responsável por fazer o Prolog calcular

operações aritméticas.
Ao fazer X = 3+2, estamos apenas atribuindoo termo 3+2
para a variàvel X.
X = 3+2.
true
Em sı́ntese, o predicado is faz com que o Prolog se comporte
de uma forma pouco usual.
Normalmente, o Prolog tenta realizar unificações de variáveis
com estruturas. Como a aritmética é útil, ela foi introduzida
na linguagem.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética

Também podemos usar a nomeclatura tradicional do prolog

para fazer operações aritméticas. Por exemplo:
X is +(3,2).
X=5
is (X, +(3,2)).
X=5

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética e Listas

Combinando aritmética e recursão, podemos calcular, por

exemplo, o comprimento de uma lista.
Podemos definir duas condições para o comprimento de uma
lista:
0, se a lista está vazia.
1 + comp(T), em que comp(T) é o comprimento da cauda.
Passando essa ideia para Prolog, temos:
comp([], X) :- X is 0.
comp([ | T], N) :- comp(T, X), N is X + 1;

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Aritmética
Comparações

Alguns dos predicados aritméticos conseguem fazer operações

sem usar o predicado is.
Isso ocorre ao serem feitas comparações entre dois números
inteiros.
Vamos ver alguns exemplos nos próximos Slides.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Comparações em Prolog

Comparações Notação em Prolog

x <y X < Y.
x ≤y X =< Y.
x =y X =:= Y.
x ̸= y X = \ = Y.
x ≥y X >= Y.
x >y X > Y.

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação
Introdução Sintaxe de Prolog Unificação Demonstração de Pesquisa Recursão Listas Aritmética

Referências
Comparações

Referências Utilizadas
Conceitos de Linguagens de Programação (RobertW. Sebesta).
Aprenda Prolog Já. (Patrick Blackburn, Johan Bos, Kristina
Striegnitz)
Referências para aprofundamento:
The art of Prolog (Sterling e Shapiro, 1994).
Natural Language Processing for Prolog Programmers
(Covington, 1994)
Artificial Intelligence Techniques in Prolog (Shoham, 1994)

Sandes Centro de Ciências Tecnológicas - CCT Universidade Federal do Cariri

Fundamentos de Linguagens de Programação