002 LAB1

Prévia do material em texto

Laboratório 1
Introdução à Linguagem de Programação
PROLOG
Edmilson Marmo Moreira
Universidade Federal de Itajubá - UNIFEI
Instituto de Engenharia de Sistemas e Tecnologias da Informação - IESTI
“Creio no Deus que fez os homens e não no deus que os homens fizeram”.
Karr
1 Considerações Iniciais
A linguagem de programação Prolog, abreviação de PROgramming in LOGic, é uma
linguagem de programação declarativa, que foi concebida por Colmerauer e Roussel em
1972, sendo sua primeira versão feita em Fortran por Battani e Meloniem 1973. Desde
então tem sido utilizada para aplicações de computação simbólica, como banco de da-
dos relacionais, compreensão de linguagem natural, automação de projetos, análise de
estruturas bioqúımicas e sistemas especialistas.
Linguagens de programação espećıficas raramente são boas para todos os tipos de
problema. Fortran (significando FORmula TRANslation), por exemplo, é utilizado prin-
cipalmente por cientistas e matemáticos. Muitas implementações de Prolog não têm a ha-
bilidade de tratar problemas “numericamente complicados” ou “processamento de texto”;
em vez disto, Prolog foi projetado para cuidar de “problemas lógicos”, isto é, problemas
para os quais uma decisão tem que ser tomada de uma forma ordenada. Prolog tenta
fazer com que o computador “raciocine” ao encontro de uma solução .
Como o nome implica, Prolog depende da manipulação lógica, entretanto não é a
única, pois, existem outras linguagens no campo geral da “programação lógica”. Tais
linguagens operam com lógica de proposição, conhecida também por lógica de pre-
dicado ou cálculo proposicional. Por exemplos, as seguintes declarações são fatos:
Pessoas com tênis para basquete jogam basquete.
A pessoaXX tem tênis para basquete.
1
Matemática Discreta - Notas de Aula - Laboratório 01 - 2
O que pode ser deduzido, calculado, computado e determinado destes fatos é que a
pessoaXX joga basquete.
O Prolog faz com que o computador cuide da parte dedutiva. De fato, Prolog tem
uma máquina de dedução interna que automaticamente percorre os fatos e constrói ou
testa conclusões lógicas.
2 Linguagens Imperativas × Linguagens Declarativas
Uma vez que Prolog é uma linguagem declarativa, ela exige que se declare regras e
fatos a respeito de determinados śımbolos, para depois perguntar-lhe se uma determinada
meta segue de uma forma lógica destas regras e fatos. A máquina dedutiva que faz
esta verificação é parte do próprio Prolog. Muitas das caracteŕısticas únicas do Prolog
envolvem interações de procedimentos com o núcleo declarativo do Prolog.
Nas linguagens imperativas, como C++, é necessário, além de declarar fatos e regras,
utilizar a linguagem para informar ao compilador como procurar uma solução, onde olhar,
quando parar, e assim por diante. Poucas linhas de uma linguagem declarativa podem
fazer tanto trabalho quanto muitas linhas de uma linguagem imperativa.
A distinção entre as linguagens imperativas e as linguagens declarativas é uma das ra-
zões pela qual uma implementação do Prolog (como o Turbo Prolog) seja uma ferramenta
tão boa para aplicações de Inteligência Artificial .
3 Estrutura de um Programa Prolog
O conjunto de declarações que constituem um programa em Prolog é também conhe-
cido como um banco de dados Prolog. Os itens em um banco de dados Prolog têm
uma entre duas formas, conhecidas em Prolog como fatos e regras .
Os fatos de Prolog permitem a definição de predicados por meio da declaração de
quais itens pertencentes a algum conjunto universo (ou domı́nio) satisfazem os predicados.
Como exemplo, suponha que se deseja criar um programa em Prolog que descreva as
cadeias alimentares em uma determinada região ecológica. Pode-se começar com um
predicado binário come. Descreve-se, então, o predicado fornecendo os pares de elementos
do domı́nio que tornam come verdadeiro. Pode-se ter, então, os seguintes fatos no banco
de dados:
come(urso, peixe).
come(urso, raposa).
Matemática Discreta - Notas de Aula - Laboratório 01 - 3
come(veado, grama).
Nesse exemplo, “urso”, “peixe”, “raposa”, “veado” e “grama” são constantes, pois represen-
tam elementos espećıficos do conjunto universo. Como o domı́nio propriamente dito nunca
é especificado, exceto através dos predicados, neste ponto pode-se considerar o conjunto
universo como consistindo em “urso”, “peixe”, “raposa”, “veado” e “grama”. É responsabi-
lidade do usuário manter uma compreensão e utilização consistente dos predicados em um
programa Prolog. Assim, come(urso, peixe) poderia ser usado para representar o fato
de que os ursos comem peixes ou de que os peixes comem ursos! Por convenção come(X,
Y) significa que “X come Y ”.
3.1 Partes do Programa
A maioria dos programas Prolog (executados no Turbo Prolog) são organizados em
quatro partes principais:
CLAUSES: Os fatos que se constroem a partir dos objetivos e relacionamentos estão des-
critos nesta seção. As cláusulas também contém regras e outros elementos que serão
discutidos posteriormente.
PREDICATES: Predicados são os relacionamentos. O termo “predicado” é emprestado da
lógica formal, que é uma das ráızes do Prolog. Sempre que o programa for utilizar
um determinado predicado nas cláusulas, será preciso declará-lo formalmente na
seção de predicados.
DOMAINS: O Turbo Prolog necessita de mais de um ńıvel de explicação antes que se diga
que o programa está completo. É preciso informar os argumentos que o predicado
vai utilizar. Para manter mı́nima a utilização da memória do computador e tornar
os programas mais fáceis de serem depurados.
GOAL: Esta é a seção que informa o que se deseja descobrir ou o que se deseja que o
computador faça com as informações fornecidas nas três seções anteriores.
Normalmente, um programa tem ao menos os predicados e as cláusulas, mas é posśıvel
ter um programa que seja apenas uma seção de meta.
O Turbo Prolog não diferencia letras maiúsculas de minúsculas, a não ser em śımbolos,
onde os iniciados por maiúscula são considerados variáveis. Para criar uma padronização,
aconselha-se a escrever os programas usando sempre letra minúscula, deixando as letras
maiúsculas somente para as variáveis.
Matemática Discreta - Notas de Aula - Laboratório 01 - 4
3.2 O Primeiro Exemplo
A seguir tem-se o exemplo de um programa simples em Prolog. Este programa possui
as 3 partes básicas (Domains, Predicates e Clauses). Ele é bastante conhecido e foi
proposto no livro de Clocksin e Mellish (1984).
/*
* Primeiro Programa
*/
Domains
tipo_nome = symbol
Predicates
gosta (tipo_nome, tipo_nome).
Clauses
gosta (maria, queijo).
gosta (jose, goiabada).
gosta (maria, livro).
gosta (pedro, livro).
Para iniciar o programa é necessário apresentar as seguintes questões ao interpretador
Prolog:
gosta (maria, dinheiro).
gosta (jose, queijo).
gosta (maria, livro).
gosta (pedro, livro).
4 Variáveis
Uma variável em Prolog sempre começa com uma letra maiúscula. Uma variável pode
estar instanciada, quando estiver assumindo o valor de um objeto, ou não-instanciada, caso
contrário.
Considerando a seguinte base de conhecimento:
come(urso, peixe).
come(urso, raposa).
come(veado, grama).
Matemática Discreta - Notas de Aula - Laboratório 01 - 5
Ao ser realizada a questão: “come(urso, X).”, a variável X está inicialmente não-
instanciada. O Prolog procura então na base de conhecimento por um fato que se
iguale a questão, isto é, que tenha o mesmo predicado, o mesmo número de argumentos
e que o primeiro argumento seja urso. A procura é feita na ordem em que os fatos são
encontrados na base de conhecimento. Ao encontrar o primeiro fato, o Prolog verifica
se todos os requisitos estão cumpridos e instancia a variável X com o objeto peixe.
No Turbo Prolog, se estiver sendo realizado uma buscaatravés da janela de diálogo
(um goal externo), após encontrar o primeiro valor de X, o programa continua procurando
na base de conhecimento por outros valores e, no final, apresenta uma lista com todas as
respostas. Porém, se for um goal interno (dentro do programa), o Prolog só encontrará a
primeira resposta, a não ser que seja realizado um tratamento apropriado no mecanismo
de recursão. Isto será visto mais adiante.
Outro tipo de variável conveniente em algumas situações é a variável anônima, tam-
bém conhecida como variável vazia. Esta variável é escrita apenas com um travessão. A
variável anônima é utilizada nos mesmos locais em que são utilizadas as variáveis-padrão,
mas nunca é inicializada com um valor determinado.
O exemplo a seguir apresenta uma meta que utiliza uma variável anônima.
come(urso,_).
Neste caso, o resultado será yes, ou seja, urso come alguém. Mas, pelo fato de ter
sido utilizado uma variável vazia, não há informação de quem ele come. O Turbo Prolog
apenas procura um fato que tem o predicado come e dois argumentos (urso como primeiro
argumento e qualquer coisa como segundo argumento). Ele não precisa saber mais.
A aridade de um predicado é o número de argumentos que aquele predicado possui.
O predicado come possui aridade 2. Programas que utilizam predicados com aridades
maiores poderão trabalhar com metas mais complexas.
5 Metas Compostas
As metas podem ser ainda mais complexas. Por exemplo, as metas também podem
lidar com fatos múltiplos. Caso se proponha a meta:
come(urso,peixe) and come(urso,raposa).
estará sendo perguntado: é verdade pelas cláusulas que urso come peixe e urso come
raposa? Esta meta composta será considerada verdadeira apenas se as duas metas indi-
viduais forem verdadeiras.
Matemática Discreta - Notas de Aula - Laboratório 01 - 6
Pelo fato de muitas outras implementações Prolog utilizarem uma v́ırgula para sig-
nificar a conjunção, o Turbo Prolog também oferece esta opção, de modo que a meta
composta acima poderá ser escrita como:
come(urso,peixe), come(urso,raposa).
Também é posśıvel construir metas compostas utilizado o operador de disjunção OR.
Da mesma forma que uma v́ırgula pode substituir AND, um ponto-e-v́ırgula pode tomar o
lugar de OR. Uma meta semelhante a anterior, utilizando o operador de disjunção, pode
ser descrita da seguinte forma:
come(urso,peixe) or come(urso,raposa).
Existem diversos outros operadores que permitem produzir metas compostas, in-
cluindo os operadores < e >, como, por exemplo, a meta a seguir:
come(urso, X) and X > "peixe".
6 Regras e Retrocesso
O Prolog tem muito mais a oferecer do que apenas os fatos elementares e variáveis do
exemplo anterior. As regras são utilizadas para construir relações entre fatos, explicitando
as dependências entre eles. Ao contrário dos fatos, que são incondicionais, as regras
especificam coisas que podem ser verdadeiras se algumas condições forem satisfeitas. As
regras possuem duas partes:
1. O corpo, que define as condições e se encontra na parte direita da regra; e
2. A cabeça, que define a conclusão e se encontra na parte esquerda da regra.
A cabeça e o corpo são separados pelo comando IF, mas também é posśıvel usar
śımbolo :- que possui o mesmo significado. Uma regra sempre é terminada com um
ponto final.
O exemplo a seguir ilustra o uso de regras:
/*
* Segundo Exemplo
*/
Matemática Discreta - Notas de Aula - Laboratório 01 - 7
Domains
tipo_nome = symbol
Predicates
homem (tipo_nome).
mulher (tipo_nome).
genitor(tipo_nome, tipo_nome).
irma (tipo_nome, tipo_nome).
Clauses
/* fatos */
genitor (antonio, leonardo).
genitor (tereza, leonardo).
genitor (constantino, karina).
genitor (regina, karina).
genitor (constantino, luiz).
genitor (regina, luiz).
mulher (tereza).
mulher (karina).
mulher (regina).
homem (antonio).
homem (leonardo).
homem (constantino).
homem (luiz).
/* regras */
irma (X, Y) :- genitor (Z, X),
genitor (Z, Y),
mulher (X),
X <> Y.
Ao ser proposta a meta “irma (karina, luiz).”, o Turbo Prolog inicialmente pro-
cura por um fato igual a questão. Após não encontrar o fato, encontra uma regra que
declara como é a relação irma. Neste momento, instancia as variáveis da regra:
X = karina e Y = luiz
Depois o Prolog tenta descobrir se a regra é valida, verificando se a parte condicional da
regra é verdadeira. O goal original transforma-se em um conjunto de sub-metas dadas
Matemática Discreta - Notas de Aula - Laboratório 01 - 8
pela regra. Se todas as sub-metas da regra forem verdadeiras, a cabeça da regra e o goal
original também serão, e o Prolog retorna yes.
O retrocesso (backtracking) é um mecanismo usado pelo Prolog para encontrar fatos
ou regras adicionais que satisfaçam uma meta quando a tentativa corrente de unificação
falha, em questões com sub-metas. O Prolog utiliza marcadores para definir os pontos
onde uma nova tentativa de solução deve ser procurada. Toda vez que é realizada uma
questão, o Prolog tenta solucioná-la comparando a questão com os fatos na base de
conhecimento. Quando a questão possui muitas sub-metas, a falha em uma busca pode
acontecer. Neste momento, o Prolog precisa de uma maneira de identificar os pontos onde
deve tentar modificar a solução corrente para procurar uma resposta certa. O retrocesso
é a implementação deste mecanismo.
7 Entrada e Sáıda
O Turbo Prolog fornece ao programador os seguintes predicados padrões para a en-
trada e sáıda de dados:
WRITE: usado para escrever uma mensagem no dispositivo padrão de sáıda, geralmente a
janela de diálogo. O argumento deste comando pode ser tanto uma variável como
um objeto.
READLN: usado para ler uma string ou um śımbolo do dispositivo padrão de entrada,
geralmente o teclado, e guardá-lo em uma variável.
O Turbo Prolog possui outros predicados de leitura, um para cada tipo de objeto a
ser lido. São eles:
READINT: usado para ler um número inteiro.
READCHAR: usado para ler um caracter.
READREAL: usado para a leitura de um número em ponto flutuante.
O exemplo a seguir ilustra o uso dos predicados de entrada e sáıda:
/*
* Terceiro Exemplo
*/
Domains
Matemática Discreta - Notas de Aula - Laboratório 01 - 9
nome, fone = symbol
Predicates
telefone (nome, fone)
Clauses
telefone ("Alberto", "921-1234").
telefone ("Joaquim", "921-2345").
telefone ("Eduardo", "921-3456").
Goal
write("Entre com o nome: "),
readln(Nome),
telefone(Nome, Telefone),
write("O telefone de ", Nome, " e ", Telefone).
8 Controle de Retrocesso
O Turbo Prolog tem uma série de predicados intŕınsecos, bem como comandos, que
o tornam uma linguagem de programação de uso geral e não apenas uma implementação
lógica. Neste contexto, há duas importantes funções de controle de retrocesso: cut “!” e
“fail”. O controle do backtracking é importante, pois é uma das maneiras de provocar
repetição, sendo outra maneira o uso da recursão.
O predicado fail sempre retorna uma falha na unificação. Com isso, força o Pro-
log a fazer o retrocesso, repetindo os predicados anteriores ao predicado fail. Por ser
muito importante, o uso deste predicado para forçar o backtracking é chamado de método
“Backtrack After Fail” de controle.
Como foi discutido anteriormente, existem dois tipos de metas em Turbo Prolog:
externa e interna. Uma meta interna tem a mesma sintaxe que uma meta externa. A
diferença é que a meta interna é localizada dentro do código do programa. Quando exis-
te uma meta interna o Prolog apresenta apenas uma resposta, o primeiro predicado da
lista, caso exista. O predicado fail obriga o Prolog a retroceder até o começo da meta e
começar de novo as procuras de concordância. Desta forma, Prolog gerará uma lista com
todas as alternativas encontradas que satisfaçam a consulta realizada.
Outro predicado importante para o controle da recursão éo cut “!”. Ao contrário do
predicado fail, em algumas situações é preciso impedir que o programa volte atrás em
uma decisão tomada (backtracking).
Matemática Discreta - Notas de Aula - Laboratório 01 - 10
O corte é usado para interromper a recursão em dois casos:
• Nas condições anteriores a ele na mesma regra.
• Nas regras abaixo daquelas em que ele aparece.
Por exemplo, seja a regra que não contenha corte com o seguinte formato:
<a> :- <b>, <c>, <d>.
Tal regra diz, na interpretação declarativa, que <a> é verdadeiro se <b>, <c> e <d> forem
verdadeiros. Isto equivale a dizer que se <b>, <c> e <d> forem verdadeiros, então <a> é
verdadeiro.
O corte pode ser traduzido por “quando e só quando”. Assim sendo, uma frase com o
formato:
<a> :- <b>, <c>, <d>, !, <e>, <f>.
deve receber a interpretação do tipo, se <b>, <c> e <d> são verdadeiros, então <a> é
verdadeiro quando e só quando <e> e <f> são verdadeiros. Em outras palavras, o Prolog
tenta satisfazer as sub-metas <b>, <c> e <d>, podendo realizar o backtracking entre estas
cláusulas até que <d> seja satisfeita, o que causará a passagem da busca do Prolog da
esquerda para direita do corte. Depois dessa passagem, o Prolog pode tentar satisfazer as
cláusulas <e> e <f>, tendo ou não que realizar o backtracking para isso, até o momento que
a cláusula <e> falha. Neste caso, não é mais posśıvel voltar para escolher outra unificação
para a cláusula <d> e toda a regra <a> falha.
Os cortes são chamados de verdes quando não mudam o resultado da busca ou ver-
melhos quando mudam o resultado. O corte verde é usado para eliminar os marcadores
do backtracking, que são ponteiros que ocupam espaço na memória.
O programa Prolog a seguir ilustra o uso dos cortes verdes. Os predicados do programa
definem a seguinte função:
f(x) =

0 se x < 3,
2 se x ≥ 3 e x < 6,
4 se x ≥ 6
Matemática Discreta - Notas de Aula - Laboratório 01 - 11
/*
* Quarto Exemplo
*/
Domains
numero = integer
Predicates
f (numero, numero)
Clauses
f(X,0) :- X < 3,!.
f(X,2) :- 3 <= X, X < 6,!.
f(X,4) :- 6 <= X,!.
Neste exemplo, se forem retirados os cortes as respostas serão as mesmas. Pode-se
notar que com o uso do corte, elimina-se a passagem do programa por regras que não
serão úteis para resolução do problema.
A mesma função poderia ser definida através de predicados com cortes vermelhos,
como no código seguinte:
/*
* Quinto Exemplo
*/
Domains
numero = integer
Predicates
f (numero, numero)
Clauses
f(X,0) :- X < 3,!.
f(X,2) :- X < 6,!.
f(X,4) :- 6 <= X,!.
Neste exemplo, caso não houvesse cortes, o Prolog, dependendo da consulta, apresen-
taria mais de um resultado . Por exemplo, para a meta:
f(2, Y).
Matemática Discreta - Notas de Aula - Laboratório 01 - 12
seria apresentado as respostas:
Y=0
Y=2
Y=4
3 Solutions
pois, a busca casaria com cada fato existente na base de conhecimento.
Finalmente é preciso considerar que ao se utilizar o predicado de corte em conjunto
com falhas, provocadas pelo predicado fail ou por uma regra, obtém-se um poderoso
método de controle. Neste método, as falhas (do fail ou de uma regra) são usadas
para forçar o backtracking até que uma condição espećıfica seja encontrada, quando se
usa o corte para terminá-lo. Esse método é parecido com as estruturas de repetição das
linguagens imperativas. O próximo exemplo ilustra esta situação:
/*
* Sexto Exemplo
*/
Domains
tipo_nome = symbol
Predicates
aluno(tipo_nome).
escreve_ate(tipo_nome).
controle_do_corte(tipo_nome, tipo_nome).
Clauses
aluno(alice).
aluno(beatriz).
aluno(karina).
aluno(lucas).
aluno(mateus).
aluno(roberto).
escreve_ate (Nome_final) :-
aluno (Nome),
write (Nome),
nl,
controle_do_corte(Nome, Nome_final), !.
Matemática Discreta - Notas de Aula - Laboratório 01 - 13
controle_do_corte(Nome_2, Nome_final_2) :-
Nome_2 = Nome_final_2.
A regra controle_do_corte falha quando os nomes não são iguais, provocando back-
tracking e evitando o corte do predicado, até que o nome corrente da busca seja igual ao
final, dado pelo usuário.
9 Recursão
Outro método muito usado para causar a repetição em programas escritos em Prolog
é a recursão. Toda recursão é composta por duas regras: a primeira, que define a condição
de parada da recursão; e a segunda, onde é feita a chamada à função recursiva. O próximo
programa calcula o fatorial de um número, ilustrando o uso da recursividade em Prolog:
/*
* Setimo Exemplo
*/
Domains
tipo_numero = integer
Predicates
fatorial (tipo_numero, tipo_numero).
Clauses
fatorial (0, Resultado) :- Resultado = 1,!.
fatorial (Numero, Resultado) :-
Numero_menos_1 = Numero - 1,
fatorial(Numero_menos_1, Resultado_parcial),
Resultado = Numero * Resultado_parcial.
10 Listas
A lista é uma estrutura de dados simples largamente utilizada em programação não-
numérica. Uma lista é uma sequência de ı́tens como: ana, pedro, paulo, joao. Esta lista
pode ser representada em Prolog como:
[ana, pedro, paulo, joao].
Matemática Discreta - Notas de Aula - Laboratório 01 - 14
A lista vazia é representada por []. A lista não-vazia contém duas partes:
• A cabeça da lista, ou seja, o primeiro elemento da lista.
• A cauda da lista, ou seja, a lista sem o primeiro elemento.
Por exemplo, para a lista anterior, ana é a cabeça da lista e [pedro, paulo, joao]
é a cauda da lista, que também é uma lista.
No Turbo Prolog, para que um fato ou uma regra possa ter uma lista como argumento,
deve-se definir na seção Domains quais listas serão usadas no programa e de que tipo de
objetos essas listas serão compostas. Por exemplo, para se definir um tipo que é uma lista
de inteiros, declara-se:
lista_inteiros = integer*
Aqui, * indica que lista_inteiros é uma lista, composta por elementos do tipo inteiro.
Uma lista é armazenada na memória como uma árvore binária, onde o primeiro ele-
mento é guardado junto com um ponteiro para o resto da lista.
Variáveis são muitas vezes usadas para representar elementos desconhecidos e elemen-
tos genéricos de uma lista. Por exemplo:
[A, B, pedro]
O primeiro e o segundo elementos desta lista são genéricos ou desconhecidos e, por con-
seguinte, estão representados por variáveis. O terceiro elemento é conhecido e está repre-
sentado pelo objeto pedro.
Um número indeterminado de elementos genéricos na cauda de uma lista pode ser
representado por uma barra vertical (|) seguida de uma variável, como no exemplo a
seguir, indicando que após o segundo elemento há uma quantidade ignorada de elementos
desconhecidos ou genéricos:
[rosa, margarida | X]
A barra vertical pode ser traduzida por “resto da lista”. Isto faz com que [5,9,7|X]
seja considerada como a lista cujo primeiro elemento é 5, o segundo elemento é 9, o terceiro
elemento é 7 e o resto dos elementos é X.
Um padrão de lista muito importante é aquele cujo o primeiro elemento é uma variável
e cujo resto da lista é também uma variável. Exemplos deste padrão são:
Matemática Discreta - Notas de Aula - Laboratório 01 - 15
[X|Y]
[Primeiro|Resto]
[Topo|Cauda]
Tais listas representam qualquer lista com pelo menos um elemento. Considere o caso
de [X|Y]. Este padrão pode ser instanciado a lista [ana] de um único elemento desde que
X represente o valor ana e Y represente a lista vazia.
O exemplo a seguir imprime uma lista usando recursão:
/*
* Oitavo Exemplo
*/
Domains
nome = symbol
lista_de_nomes = nome*
Predicates
alunos(lista_de_nomes).
imprime_lista(lista_de_nomes).
Clauses
/* fatos */
alunos([karina, beatriz, alice, lucas, mateus, marcelo, andre, roberto]).
/* regras */
imprime_lista([]).
imprime_lista([Cabeca|Cauda]) :- write (Cabeca),
nl, imprime_lista(Cauda).
Goal
alunos (X),
write("A lista com todos os alunos declarados e’:"),
nl, imprime_lista(X).
Um ponto importante a ser considerado é a forma de se concatenarduas listas. Su-
pondo a seguinte relação:
concatena[L1, L2, L3]
Matemática Discreta - Notas de Aula - Laboratório 01 - 16
Onde L1 e L2 são duas listas e L3 é o resultado da concatenação de L1 e L2. Por
exemplo:
concatena([a,b],[c,d],[a,b,c,d]).
é verdade, entretanto a consulta:
concatena([a,b],[c,d],[c,d,a,b]).
é falsa.
Na definição da relação para concatenação de lista, é preciso tratar dois casos, depen-
dendo do primeiro argumento X:
1. Se o primeiro argumento é uma lista vazia, então o segundo e o terceiro argumentos
precisam ser a mesma lista. Isto é definido pelo seguinte fato Prolog:
concatena([],L,L).
2. Se o primeiro elemento não é uma lista vazia, então ele tem cabeça e cauda. Seja o
primeiro argumento a seguinte lista genérica [X|L1]. O resultado da concatenação
desta lista com a lista L2 é uma lista [X|L3], onde L3 é a concatenação de L1 (cauda
da primeira lista) com L2 (segunda lista). Em Prolog, esta regra é escrita como:
concatena([X|L1], L2, [X|L3]) :- concatena(L1, L2, L3).
O exemplo a seguir ilustra o que foi exposto:
/*
* Nono Exemplo
*/
Domains
nome = symbol
lista_de_nomes = nome*
Predicates
concatena (lista_de_nomes,lista_de_nomes,lista_de_nomes).
clauses
/* regras */
concatena ([],L,L).
concatena ([N|L1],L2,[N|L3]) :-
concatena (L1,L2,L3).
Matemática Discreta - Notas de Aula - Laboratório 01 - 17
11 Bancos de Dados Dinâmicos em Prolog
O Turbo Prolog permite a construção de bancos de dados dinâmicos, isto é, que po-
dem ser alterados e armazenados em disco para nova utilização. Esses bancos armazenam
fatos. Os predicados que definem os fatos usados no banco de dados dinâmico devem ser
declarados na parte Database do programa e não na Predicates. Assim, um mesmo pro-
grama pode ter fatos declarados na parte de Predicates, que só podem ser alterados com
a modificação do código fonte do programa, e fatos guardados em um arquivo separado,
que podem ser carregados, modificados e salvos.
O Turbo Prolog fornece ao programador os seguintes predicados para manipular ban-
cos de dados dinâmicos:
AssertA: Acrescenta um fato ao banco de dados armazenado na memória do computa-
dor. Ele acrescenta o novo fato no ińıcio das cláusulas de mesmo predicado.
AssertZ: Semelhante ao anterior, porém adiciona o novo fato após as cláusulas de mesmo
predicado.
Retract: É um predicado usado para retirar um fato do banco de dados. Ele retirará o
primeiro fato que casar com o seu argumento.
FindAll: Predicado que procura no banco de dados todos os fatos que combinem com
seu primeiro argumento no predicado passado pelo seu segundo argumento, e os
coloca em uma lista, que é seu terceiro argumento.
Consult: Utilizado para carregar um banco de dados do disco para a memória. Este
predicado recebe como argumento o nome do arquivo a ser carregado. Uma obser-
vação que deve ser feita é que este predicado carregará o banco de dados do disco
concatenando-o com o da memória. Por exemplo, se o usuário carregar duas vezes
o mesmo banco de dados, ele ficará na memória com duas cópias de todos os fatos
carregados, uma após a outra.
Save: Transfere todos os fatos existentes na memória para um arquivo.
11.1 Um Exemplo de Aplicação
A seguir tem-se o exemplo de um programa com bando de dados em Prolog. O
programa implementa uma agenda de telefones com uma interface com o usuário através
de menus de texto. Ele guarda um nome e um número para cada entrada no banco de
dados.
Matemática Discreta - Notas de Aula - Laboratório 01 - 18
/*
* Um Exemplo de Banco de Dados em Prolog
*/
Domains
tipo_nome, tipo_telefone = string.
Database
agenda(tipo_nome, tipo_telefone).
Predicates
menu (integer). /* gerencia a interacao com o usuario.*/
processa (integer). /* processa a escolha do usuario. */
erro. /* processa erro na escolha da opcao do menu. */
adiciona. /* adiciona novo item na agenda */
deleta. /* retira item da agenda */
procura. /* procura item na agenda */
carrega. /* carrega agenda de um arquivo */
salva. /* salva a agenda em um arquivo. */
Clauses
/* Clausula que controla a interacao com o usuario. */
menu(Escolha):- Escolha = 6,
write ("Terminado!").
menu(_):- nl,
write("Escolha uma opcao: "), nl,
write("1. Adiciona um telefone ao Banco de Dados"), nl,
write("2. Deleta um telefone do Banco de Dados"), nl,
write("3. Procura um telefone"), nl,
write("4. Carrega o arquivo do Banco de Dados"),nl,
write("5. Salva o Banco de Dados em um arquivo"), nl,
write("6. Termina. "),nl,
write(" "),nl,
readint(Escolha),
processa (Escolha), menu(Escolha).
/* Clausulas que processam a escolha do usuario. */
processa (1) :- adiciona.
processa (2) :- deleta.
Matemática Discreta - Notas de Aula - Laboratório 01 - 19
processa (3) :- procura.
processa (4) :- carrega.
processa (5) :- salva.
/* se a escolha foi 6, confirma saida. */
processa (6) :- write ("Tem certeza que deseja terminar? (s/n)"),
readln(Resposta),
frontchar (Resposta,’s’,_).
processa(6) :- menu(0).
/* processa entradas invalidas */
processa (Escolha) :- Escolha < 1, erro.
processa (Escolha) :- Escolha > 6, erro.
erro :- write ("Por favor entre numeros entre 1 e 6."),
nl,
write ("Tecle algo para continuar."),
readchar (_).
/* Clausulas que implementam as rotinas de manipulacao do DB.*/
/* adiciona um telefone */
adiciona :- write ("Adicionando um telefone ao B D."), nl,
write ("Entre o nome: "),
readln (Nome),
write ("Entre o telefone dele:"),
readln (Telefone),
assertz (agenda (Nome, Telefone)),
write ("Telefone adicionado ao B D."),
nl.
/* deleta um telefone do BD */
deleta :- write ("Deletando um telefone do B D."), nl,
write ("Entre o nome: "),
readln (Nome),
write ("Entre o telefone dele: "),
readln (Telefone),
retract (agenda (Nome, Telefone)),
Matemática Discreta - Notas de Aula - Laboratório 01 - 20
write ("Telefone retirado do B D."),
nl.
deleta :- write ("Telefone nao encontrado!!!"), nl.
/* procura um telefone */
procura :- write ("Procurando um telefone no B D."), nl,
write ("Entre o nome: "),
readln (Nome),
agenda (Nome, Telefone),
write ("O telefone do(a) ", Nome, " e’ ",Telefone,"."),
nl.
procura :- write ("Telefone nao encontrado!!!"), nl.
/* carrega o arquivo com o banco de dados */
carrega :- write ("Carregando o arquivo com o B D."), nl,
write ("Qual o nome do arquivo? "),
readln(Nome_do_arquivo),
consult(Nome_do_arquivo),
write("Carregado!"),
nl.
/* salva o arquivo com o banco de dados */
salva :- write ("Salvando o Banco de Dados."), nl,
write ("Qual o nome do arquivo? "),
readln(Nome_do_arquivo),
save(Nome_do_arquivo),
write("Salvo!"),
nl.
/* Inicia o programa */
Goal
menu(0).
Matemática Discreta - Notas de Aula - Laboratório 01 - 21
Finalmente, o predicado pré-definido Findall gera uma lista com todas as alternativas
encontradas que satisfaça a uma determinada consulta. O próximo exemplo ilustra o uso
deste predicado.
/*
* Exemplo do uso de Findall
*/
Domains
ListaNomes = symbol*.
Predicates
Aluno (symbol, integer).
TesteFindall.
MostraLista (ListaNomes).
clauses
Aluno(pedro, 9).
Aluno(joao, 10).
Aluno(joaquim, 9).
MostraLista([]).
MostraLista([X|Y]) :- write (X), nl, MostraLista(Y).
TesteFindall :-
Findall(X, Aluno(X,_), L),
MostraLista(L),
nl.
12 Exerćıcios
1. Sejam pai e mae as relações como definidas nos fatos abaixo:
pai(joao, joaquim).
pai(edmilson, lucas).
pai(edmilson, mateus).
pai(joaquim, bruno).
mae(karina, lucas).
mae(karina, mateus).
Matemática Discreta - Notas de Aula - Laboratório 01 - 22
mae(silvia, bruno).
mae(laura, joaquim).
Qual será a resposta de Prolog para as seguintes consultas:
(a) pai(joao, X).
(b) pai(X, joaquim).
(c) pai(joao, X), pai(X, bruno).
2. Em relação aos fatos da questão anterior, formule em Prolog as seguintes consultas
sobre as relações pai e mae:
(a) Quem é o pai de bruno?
(b) Maria tem filhos?
(c) Quem é oavô de bruno?
3. Defina a relação neto a partir das relações pai e mae.
4. Faça uma regra que receba um nome, procurando-o na base de dados e imprimindo
Encontrei todas as vezes que ele aparecer na base.
5. Implemente regras para o tratamento de listas que:
(a) Calcule o comprimento de uma lista.
(b) Insira um elemento em uma lista.
(c) Retire um elemento de uma lista.
(d) Substitua elementos em uma lista.
(e) Encontre o n-ésimo elemento de uma lista.
(f) Inverta uma lista.
6. Defina os seguintes predicados Prolog:
(a) listapar(Lista) - que é verdadeiro quando o número de elementos da lista
for par.
(b) listaimpar(Lista) - que é verdadeiro quando o número de elementos da lista
for ı́mpar.
7. Descreva um programa Prolog para verificar se uma determinada lista de caracteres
(char) é um paĺındromo. Um paĺındromo é uma palavra ou número cuja leitura é
a mesma, quer se faça da esquerda para a direita, ou da direita para a esquerda.
Matemática Discreta - Notas de Aula - Laboratório 01 - 23
8. Simule o programa Prolog a seguir, apresentando sua sáıda, e explique qual é o
objetivo dos seus predicados:
Domains
ListaInt=integer*
Predicates
Prova1(ListaInt, ListaInt).
Prova2(ListaInt, ListaInt, ListaInt).
Clauses
Prova1(A,B) :- Prova2(C,[D,E|F],A),
write(D," ",E," ",F),nl,
D < E, !,
Prova2(C,[E,D|F],G),
Prova1(G,B).
Prova1(A,A).
Prova2([],L,L).
Prova2([A|B],C,[A|D]):-Prova2(B,C,D).
Goal
write("Saida:"),nl,
Prova1([2,3,4,1],X),
write(X),nl.
9. Faça um programa em PROLOG que leia um banco de dados de nome “Dados.txt”
e imprima uma lista de todas as pessoas que torcem para um determinado clube.
Em seguida, deve ser apresentado o total de torcedores daquele clube na base. O
arquivo “Dados.txt” possui fatos para o predicado Pessoa(symbol,Lista) em que
Lista é uma lista de symbol e o primeiro parâmetro representa o nome da pessoa
e o segundo parâmetro representa os times preferidos.
Referências
CLOCKSIN, W. F.; MELLISH, C. S. Programming in Prolog. Berlin: Springer-Verlag,
1984.
GERSTING, J. L. Fundamentos Matemáticos Para a Ciência da Computação. 4a. ed.
Rio de Janeiro: Livros Técnicos e Cient́ıficos Editora S.A., 2001. 538 p.
ROBINSON, P. R. Turbo Prolog - Guia do Usuário. São Paulo: McGraw-Hill, 1988.
287 p.