Universidade Federal do Maranhão Curso de Pós … · Observação: Nada impede a definição de fatos que não são mais corretos. ... Prolog usa o conceito de regras para representar

Universidade Federal do Maranhão

Curso de Pós-Graduação em Engenharia de Eletricidade

Área de Concentração:

Ciência de da Computação

Linguagens e Ferramentas para a IA

Programação Lógica : A Linguagem PROLOG

Por

Prof. Dr. Sofiane Labidi

2004

A Linguagem Prolog - Prof. Dr. Sofiane Labidi

Sumário

PARTE I. INTRODUÇÃO ..........................................................................................................................4

1.LINGUAGENS DA INFORMÁTICA..................................................................................................................5

2.PROGRAMAÇÃO MULTI-PARADIGMAS........................................................................................................6

3.HISTÓRICO..................................................................................................................................................8

4.CARACTERÍSTICAS E APLICAÇÕES..............................................................................................................9

5.PROGRAMAÇÃO LÓGICA...........................................................................................................................10

PARTE II. PRINCÍPIOS DA PROGRAMAÇÃO EM PROLOG......................................................11

6.FATOS.......................................................................................................................................................12

7.CONSULTA................................................................................................................................................14

7.1Uso das Variáveis..............................................................................................................................14

7.2Conjunção..........................................................................................................................................16

8.TÉCNICA DE BUSCA DO MOTOR PROLOG.................................................................................................18

9.USO DAS REGRAS.....................................................................................................................................19

PARTE III. ESTRUTURAS DA LINGUAGEM.......................................................................................22

10.CONSTITUINTES ELEMENTARES..............................................................................................................23

10.1Termos.............................................................................................................................................23

10.1.1Átomos.......................................................................................................................................2310.1.2Variável......................................................................................................................................24

10.2Relações...........................................................................................................................................25

11.CLÁUSULAS.............................................................................................................................................26

12.REPRESENTAÇÃO DOS OBJETOS PROLOG...............................................................................................28

13.ALGORITMO DE UNIFICAÇÃO DE ROBINSON..........................................................................................29

14.PACOTE (PACKAGES)..............................................................................................................................31

15.ESTRUTURA DE UM PROGRAMA PROLOG................................................................................................32

16.ALGUMAS DEFINIÇÕES...........................................................................................................................33

17.SIGNIFICAÇÃO OPERACIONAL.................................................................................................................34

18.UMA VISÃO PROCEDURAL DE PROLOG..................................................................................................35

PARTE IV. CONTROLE..........................................................................................................................36

19.INTRODUÇÃO...........................................................................................................................................37

20.O CUT......................................................................................................................................................38

20.1Busca determinística (green cut).....................................................................................................38

20.2Otimização (green cut)....................................................................................................................39

20.3Modificação da semântica (red cut)............................................................................................39

21.O FAIL....................................................................................................................................................40

22.OUTRAS ESTRUTURAS DE CONTROLE......................................................................................................41

2


23.NEGAÇÃO................................................................................................................................................42

PARTE V. OPERAÇÕES..........................................................................................................................44

24.OPERAÇÕES RELACIONAIS.....................................................................................................................45

25.OPERAÇÕES ARITMÉTICAS.....................................................................................................................47

26.EXERCÍCIOS.............................................................................................................................................48

PARTE VI. ESTRUTURA DAS LISTAS................................................................................................49

27.LISTAS.....................................................................................................................................................50

28.OPERAÇÕES BÁSICAS SOBRE AS LISTAS:.................................................................................................52

29. EXERCÍCIOS............................................................................................................................................55

PARTE VII. ENTRADAS E SAÍDAS......................................................................................................56

30.ENTRADAS..............................................................................................................................................57

31.SAÍDAS....................................................................................................................................................59

PARTE VIII. ESTRUTURAS DE REPETIÇÃO......................................................................................61

32.REPEAT...................................................................................................................................................62

PARTE IX. MANIPULAÇÃO DE ARQUIVOS......................................................................................63

33.SAÍDA PADRÃO.......................................................................................................................................64

34.ENTRADA PADRÃO..................................................................................................................................66

35.CONSULTA DE BANCOS DE DADOS.........................................................................................................68

36.DEFINIÇÃO..............................................................................................................................................70

PRTE X. PROJETOS...................................................................................................................................71

3


PARTE I. INTRODUÇÃO

4


1. Linguagens da Informática

São formalismos que permitem de resolver problemas escrevendo

"Programas"!

Basicamente, existe dois tipos de linguagens: Imperativa, Declarativa, etc.

5


2. Programação Multi-Paradigmas

Existem vários paradigmas de programação:

• Programação Procedural / Imperativa (ou Convencional)Instrução = Ordem (nos dois sentidos: ordem para a máquina eordem nos enunciados).Especificação da solução em termos de comportamento da máquina.

• Programação Orientada a ObjetoInstrução básica = Envio de mensagem.Especificação da solução em termos de interações entre objetosInstâncias de uma hierarquia de classes (categorias de objetos).

• Programação FuncionalInstrução = Função (que calcula e retorna um valor: a solução).Especificação da solução em termos de valores calculados.

• Programação Lógica (Declarativa)Instrução = RelaçãoEspecificação da solução em termos de relações entre entidades.

• Programaçõa Visual;

• Programação Paralela; Distribuída, Concorrente, etc.

Cada paradigma tem suas vantagens e inconvenientes. Será que é

interessante combinar os paradigmas? É interessante desenvolver linguagens que

suportem diferentes paradigmas? Existem tentativas de combinar a orientação a

objeto as categorias de linguagens. Por exemplo, as linguagens: ObjLog, CLOS,

etc.

6


A IA usa muito a Programação Funcional (Lisp, Scheme, ML, etc.) e a

Programação Lógica (principalmente PROLOG).

7


3. Histórico

• Muitos séculos atrás apareceu a lógica tradicional com Aristóteles.

• A formalização da lógica começou apenas no século 19, com

DeMoragan e Boole (Lógica Booleana).

• No século 20, tivemos o desenvolvimento de muitos princípios da

lógica como a teoria de demonstração por refutação de Herbrand (1930), o

princípio de resolução de Robinson (1965), a SLD resolution de Kowalski

(1971), etc.

• Em 1973, tivemos o desenvolvimento do primeiro interpretador

Prolog (escrito em Fortran) pela equipe GIA (Grupo de Inteligência

Artificial) de Colmerauer da Universidade de Marselha. Prolog é a primeira

linguagem de programação baseada na lógica.

• Prolog se desenvolveu bastante no meio universitário. A partir de

1981, Prolog comecou a ter algumas aplicações na indústria.

• O primeiro compilador foi desenvolvido pela equipe de David

Warren na Universidade de Edinburgh (em Borland Turbo-Pascal) em 1982:

o que significou uma grande virada!

• Em 1992, inicio a definição de uma norma ISO para Prolog, além

do desenvolvimento de vários ambientes de programação em Prolog: Prolog

de Marselha, LPA Prolog, DELPHI Prolog, etc.

8


4. Características e Aplicações

Prolog é uma linguagem declarativa baseada nos princípios da lógica.

Mesmo não respeitando inteiramente estes princípios.

É uma linguagem simples: o usuário especifica o conhecimento sem se

preocupar com a sua aplicação. Isto é feito pelo motor do Prolog (baseado no

algoritmo de unificação de Robinson).

Um programa Prolog é uma especificação executável.

O sucesso do Prolog fez com que ele fosse escolhido pelos japoneses como a

linguagem da máquina de quinta geração.

As principais aplicações de Prolog são:

• Tratamento da liguagem natural;

• Banco de dados;

• Automação de projetos;

• Sistemas especialistas, etc.

9


5. Programação Lógica

Programar em lógica ⇒ Descrever o universo do problema.

Um programa Prolog é um conjunto de:

• Propriedades; e

• de relações.

Um programa Prolog é, portanto, um conjunto de afirmações. Ela não é uma

descrição da solução do problema.

Um problema é um conjunto de perguntas sobre os objetos do universo da

aplicação.

A execução de um programa implica a dedução de novas relações a partir

das afirmações do programa.

10


PARTE II. PRINCÍPIOS DA PROGRAMAÇÃO EM PROLOG

11


6. Fatos

Os fatos são afirmações corretas sobre os objetos do universo da aplicação.

Cada fato exprime um relacionamento entre os objetos envolvidos. Por exemplo, o

fato “João gosta de cinema” é um relacionamento entre os objetos

“joão” e “flores”.

Em Prolog, os fatos são representados de uma maneira simples, baseados na

lógica:

gosta(joao,flores).% afirmação que João gosta de flores.

pai(roberto,joao). % afirmação que Roberto é o pai de João.

Observação.

• Os nomes dos relacionamentos e dos objetos devem começar por uma letra

minúscula. Estes relacionamentos são chamados predicados.

• O relacionamento é escrito primeiro e os objetos em seguida. Os objetos são

separados por uma vírgula e agrupados entre parênteses. Os objetos são

chamados argumentos do predicado.

• A representação termina por um ponto (.).

Deve-se prestar atenção na ordem pela qual os objetos são expressos, pois

pai(roberto,joao) e pai(joao,roberto) não têm o mesmo

significado.

Os predicados podem ter um número arbitrário de objetos. Isto define o grau

do predicado ou a aridade. Por exemplo, gostar é um fato binário, mas podemos

ter relacionamentos unários, ternários, etc.

12


homem(joao). % João é um homemmulher(marci).capital(paris,franca). % Paris é a Capital da França

da(marcia,maria,livro). % Márcia deu um livro para Maria

Em um mesmo programa podemos ter um mesmo predicado com aridades

diferentes:

pais(brasil). % Brasil é um paíspais(brasil,brasilia,portugues,real).

% mais informações sobre o Brasil.

Observação: Nada impede a definição de fatos que não são mais corretos.

Prolog funciona de modo monótono.

capital(brasil,rio). % Para Prolog isto é um fato verdadeiro.

O conjunto de fatos Prolog é geralmente chamado Base de Dados.

13


7. Consulta

A consulta é uma pergunta sobre os fatos da base de dados.

Em Prolog, a pergunta é similar sintaticamente aos fatos:

?- capital(paris,franca).yes % a resposta é sim

?- homem(marcia).no % a resposta é não

Para responder à pergunta, Prolog tentar fazer um pattern matching entre a

pergunta e os fatos da base de dados. A pergunta é um objetivo que Prolog tenta

verificar como verdadeiro ou satisfazer.

O não (a resposta no) não deveria ser interpretado como a não verdadeira (o

false), pois significa que não é provável, uma vez que pode por exemplo faltar

informações na base de dados.

7.1 Uso das Variáveis

As últimas perguntas não são muito interessantes. Um outro tipo de pergunta

à base pode ser por exemplo: “Quem gosta de flores?”

Para exprimir tal pergunta é preciso usar uma variável, a qual Prolog vai

tentar identificar:

?- gosta(X,flores).

Esta é uma indicação a Prolog de procurar na base de dados todas as

instâncias possíveis (os objetos) de X que satisfaçam esta afirmação.

14


Para fazer a diferença entre os nomes dos objetos e as variáveis, Prolog usa a

convenção de que cada variável deve começar por uma letra maiúscula e (ao

contrário) o nome dos objetos deve começar por uma letra minúscula.

Exemplos de consulta:

%% Base de Fatos:

gosta(carlos,dançar).gosta(joao,maria).gosta(roberto,flores).gosta(roberto,dançar).

% Do que gosta João? ?- gosta(joao,X).X=maria

% Quem gosta de dançar??- gosta(X,dancar).X=carlos ;X=roberto

% Quais objetos ligados pelo predicado gostar?(quem gosta de que ?)

?- gosta(X,Y).X = carlos ,Y = dancar ;

X = joao ,Y = maria ;

X = roberto ,Y = flores ;

15


X = roberto ,Y = dançar

Essas perguntas vão procurar na base todos os objetos que são ligados pelo

relacionamento (predicado) indicado.

7.2 Conjunção

Podemos combinar objetivos na mesma pergunta. Para exprimir a conjunção

é preciso separar os objetivos por uma vírgula (,).

Exemplo:

Suponhamos que temos a seguinte base de dados:

%% Base de Fatos

gosta(adriana,nadar).gosta(silvio,nadar).gosta(rodrigo,nadar).gosta(roberto,flores).gosta(joao,maria).gosta(juliano,flores).gosta(roberto,dancar).

mora(adriana,fortaleza).mora(silvio,sao_luis).mora(mauro,recife).mora(juliano,sao_luis).mora(roberto,belem).mora(sara,sao_luis).

Figura 1. Exemplo de Base de Dados Prolog

16


Para responder a pregunta : “Quem são os ’ludovicentes’ que gostam de flores?”, escrevermos:

?- gosta(X,flores), mora(X,sao_luis).X = juliano

Para responder a tal pergunta Prolog tenta satisfazer todos os objetivos, em

ordem.

17


8. Técnica de Busca do Motor Prolog

Para simular o trabalho do motor Prolog respondendo à pergunta: “Quem

gosta de flores e mora em São Luís?” mostramos a seguinte árvore:

| ?- gosta(X,flores), mora(X,sao_luis).X = juliano

Figura 2. Simulação de uma busca em Prolog

Qual é a estratégia de busca aplicada por Prolog?

18

gosta(X,flores)mora(X,sao_luis)

X=robertomora(X,sao_luis)

X=robertoX=silvio

X=robertoX=juliano

X=robertoX=sara

X=julianomora(X,sao_luis)

X=julianoX=silvio

X=julianoX=juliano

X=robertoX=sara

fail fail fail fail sucesso fail

Backtracking(retrocesso)


9. Uso das Regras

Os fatos definem relacionamentos entre objetos específicos.

Sejam os seguintes fatos:

cerveja(antarctica).cerveja(kaiser).cerveja(brahma).cerveja(cerpa).cerveja(heinecken).

pessoa(leonardo).

Suponhamos agora que nós queremos exprimir o fato que Leonardo gosta de

todos os tipos de cerveja :

Uma solução seria de introduzir os fatos um a um :

gosta(leonardo,antartica).gosta(leonardo,kaiser).gosta(leonardo,brahma).gosta(leonardo,cerpa).gosta(leonardo,heinecken).

No entanto, esta solução não é muito prática.

Prolog usa o conceito de regras para representar esse tipo de informação.

Uma regra é uma generalização das afirmações sobre os objetos do universo da

aplicação.

19


Exemplo:

Na linguagem natural, para exprimir uma regra usamos a palavra “Se”:

X é um pássaro se X é um animal que tem asas.X e Y são irmãos se eles tem os mesmos pais.

Leonardo gosta de Y se Y é uma cerveja.

Em Prolog, o se (o if) é representado pelo símbolo :-

Escrevemos, então:

gosta(leonardo,X) :- cerveja(X).passaro(X) :- animal(X), tem(X,asas).

avo(X,Y) :- pai(X,Z), pai(Z,Y). % usando a conjunção

Semântica:

X é o avô de Y, se existe uma pessoa Z, tal que X é o pai de Z e Z é o pai de Y.

Uma regra pode ser expressa em termos da disjunção dos fatos:pais(X,Y) :- pai(X,Y);

mãe(X,Y). % usando a disjunção

% X é pai de Y, se X é a mãe de X ou X é o pai de Y.

Atenção: A disjunção é geralmente expressa, dividindo-se

a regra em duas:

pais(X,Y) :- pai(X,Y).pais(X,Y) :- mae(X,Y).

As regras são chamadas cláusulas, eles permitam de inferir novos fatos.

20


Aplicação:

Exprima as seguintes relações e clausulas em Prolog.

1. Chirac é o presidente da França.2. Irmão.3. Primo.4. O inimigo de um amigo é um inimigo.5. Sara gosta de todos os gaúchos.6. Os professores ficam satisfeitos quando seus alunos são dedicados.7. Onde moram todos os que gostam da música ?

21


PARTE III. ESTRUTURAS DA LINGUAGEM

22


10. Constituintes elementares

Temos os termos e as relações.

10.1 Termos

Um termo da linguagem Prolog representa um objeto do universo do

problema. Um termo pode ser um objeto desconhecido:

- uma variável ou um objeto concreto

- ou um átomo.

10.1.1 Átomos

Um átomo (ou constante) representa, portanto, um objeto específico do

universo do problema.

Existem os átomos numéricos, alfanuméricos, quotados e especiais:

Átomos Numéricos:Os inteiros: 125 -30 425 +24 0NB. Em LPA Prolog os inteiros são representados em 4 bytes ⇒ ∈ [-2147483648..2147483647].

E os reais: 3.14159 -10.8 5.003E3 -2.5e24NB. Em LPA Prolog os reais são representados em 8 bytes ⇒

∈ [2.2e-308..1.7e308].

Átomos Alfanuméricos:

Começa por uma letra minúscula e é composto por letras (maiúsculas ou minúsculas), dígitos numéricos (0-9), o underscore e alguns caracteres especiais.

23


Exemplos: pai imposto_de_Renda mora amar nome2

Átomos Quotados:

Universidade' '524' 'Olho d''Agua' 'urbano'

Átomos Especiais:

! ; , [] {}

10.1.2 Variável

Uma variável é um átomo representando um objeto desconhecido do universo

do problema. O nome de uma variável é uma seqüência de alfanuméricos que

começa por uma letra maiúscula (de A até Z) ou um underscore ( _ ).

Exemplos: Pessoa Disciplina_2 X var A1, _altura

Variável anônima:

É o underscore (_) usado sozinho.

Quando usamos a variável anônima, Prolog não vai tentar instanciá-la.

A noção de variável é muito importante, pois em uma pergunta o motor

Prolog tenta buscar os valores que satisfaçam as variáveis da relação.

| ?- homem(X).X = joao ;X = roberto

24


Observação:

Prolog não tenta buscar os valores de uma variável anônima.

| ?- gostar(X,_). % quem gosta de alguma coisa?

X = joao ; % sem precisamos saber do que é?X = joao

10.2 Relações

Uma relação (ou termo funcional ou regra) possui a forma:

f(t1, t2, t3, ..., tn)

onde: - f é um símbolo funcional e

- t1, ..., tn um conjunto de termos e/ou relações.

Exemplos: idade(karine,24) homem(ricardo) g(X,_,10) aridade (grau) 2 aridade 1

Relações compostas: pessoa(carlos, 22, (cohama, sao_luis)).

pessoa(roberto,21,endereco(8,’rua 1’,centro)).

25


11. Cláusulas

Uma cláusula é uma afirmação da forma:

T :- Q1, ..., Qn.

Onde: T é a cabeça da cláusula, e

Q1, ..., Qn o corpo da cláusula.

Uma cláusula pode ser uma afirmação certa ou condicional (regra):

Afirmação condicional:

Uma cláusula é uma afirmação condicional (ou regra) se:

T ≠ ∅ e {Q1, ..., Qn} ≠ ∅

Exemplo: mesmo_pai(X,Y) :- pai(P,X), pai(P,Y).

A semântica informal dessa é: se todos os termos funcionais do corpo são

verificados (verdadeiros) então o átomo da cabeça é verdadeiro.

:- é a implicação lógica, é o AND lógico.; é o OR lógico.

Afirmação incondicional (certa):

Uma cláusula é uma afirmação incondicional (ou certa) se:

T ≠ ∅ e {Q1, ..., Qn} = ∅ exemplo: gosta(juliano,cantar).

Pergunta:

Quando a cabeça é vazia (T=∅), então a cláusula é uma pergunta.

26


exemplo: ?- gosta(X, cantar). % quem gosta de cantar?X=juliano

gosta(X,nadar), pai(Y,X). % Quais os pais das pessoas quem gostam de nadar ?

X = joao , Y = roberto ;

27


12. Representação dos Objetos Prolog

A estrutura básica que Prolog utiliza para representar seus objetos é a

estrutura de árvore.

Qualquer cláusula Prolog pode ser representada sob a forma de uma árvore.

T :- Q1, ..., Qn.

é representada da seguinte maneira:

Q2

T

Q1 Qn...

Tal árvore é chamado árvore de prova (proof tree).

28


13. Algoritmo de Unificação de Robinson

Para solucionar uma pergunta, o motor Prolog é baseado no algoritmo de

unificação de Robinson.

Para unificar dois termos T1 e T2, o motor calcula o unificador mais genérico

de T1, T2.

Exemplo: Para responder a pergunta: “Quem é a mãe de João?”, escrevemos:

mae(X, joao). % e a resposta de Prolog é:

X=maria

Isto é o resultado da unificação dos duas árvores:

maria joao X joao

mae mae

A unificação dessas duas arvores implicaque X deve ser igual a maria

Versão Simplificada do Algoritmo de Robinson:

Unificar (E1, E2)Se E1 ou E2 é um átomo, então seja E1 o átomo (trocar E1 e E2 se precisa)

Se E1 = E2 então retornar yes

29


Se E1 é uma variável, Retornar E1=E2Se E2 é uma variável, retornar E2=E1Senão retornar no (insucesso)

Senão Seja F1 o 10 elemento de E1 e T1 o resto F2 o 10 elemento de E2 e T2 o resto

Z=unificar(F1,F2)Se Z=no, retornar noSenão unificar (T1,T2).

30


14. Pacote (packages)

Um Programa Prolog é uma conjunto de cláusulas ordenadas em pacotes.

Pacote:

conjunto de cláusulas que compartilham:

• o mesmo símbolo de predicado (a cabeça das clásulas) e

• a mesma aridade (o grau das cláusulas).

Duas regras do mesmo pacote são ligadas pelo ou lógico (o OR).

exemplo: pais(X,Y) :- pai(X,Y).pais(X,Y) :- mae(X,Y).

Observação:

p :- a1, a2, a3.P :- b1, b2,.

Isto significa:

(a1 and a2 and a3) or (b1 and b2) ⇒ p

31


15. Estrutura de um programa Prolog

Um programa Prolog é organizado da seguinte forma:

Programa: conjunto de pacotes

Pacote: conjunto de cláusulas (do mesmo predicado, mesma aridade)

Cláusula: átomo_lógico.

| átomo_lógico :- átomo_lógico,..., átomo_lógico.

Átomo_lógico: símbolo_de_predicado

| símbolo_de_predicado(termo,..., termo)

Termo: átomo (ou constante)

| variável

| símbolo_funcional (termo, ..., termo) % ou relação

32


16. Algumas Definições

SubstituiçãoÉ a função:

{variáveis} → {conjunto dos termos}

Instância

Imagem de um termo (átomo, cláusula) por uma substituição.

(é o resultado da substituição das variáveis).

Unificação

Dois termos T1 e T2 são unificáveis se existe uma substituição s tal

que s(T1)=s(T2).

exemplo: f(X,b) e f(a,Y) são unificáveis quando

s={X=a,Y=b}

Denotação de um programa

A significação lógica de um programa Prolog P é definida por sua

denotação DEN(P).

DEN(P) é o conjunto de átomos que são derivados logicamente de

P. Isto é (geralmente) um conjunto infinito.

Uma resposta Prolog a uma pergunta A é o conjunto S das instâncias

de A pertencendo a denotação de P: DEN(P).

33


17. Significação Operacional

Dado um objetivo a demostrar, o motor Prolog tenta calcular todas suas

instâncias pertencentes à denotação do programa.

Princípio:

Percorrer em profundidade, da esquerda para direta, a árvore de busca.

Escolher as regras a partir do primeiro pacote do programa.

Escolher as folhas a partir da esquerda.

Observação:

A ordem das regras nos pacotes e a ordem dos átomos nas cláusulas é

muito significativa.

34


18. Uma Visão Procedural de Prolog

Podemos fazer um “mapeamento” entre a estrutura de um programa Prolog e

a programação Procedural:

Pergunta: é uma chamada a um procedimento (procedure call)

Unificação: é a transmissão de parâmetros

Pacote: Procedimento (procedure)

Cláusulas: Definição dos procedimentos.

35


PARTE IV. CONTROLE

36


19. Introdução

O custo de percorrer toda árvore de busca é muito elevado. Portanto, é

necessário definir mecanismos para delimitar a busca, objetivando a eficiência, ou

seja, economizar tempo e espaço.

Um outro objetivo que motivou a definição das estruturas de controle é o

problema da expressão da negação.

Embora a escolha da ordem das cláusulas nos pacotes e da ordem dos átomos

nas cláusulas implique em um certo controle sobre a busca, temos a definição de

estruturas especiais de controle, principalmente o corte (o cut).

37


20. O cut

Notação: !

A chamada do cut sempre tem sucesso (nunca falha).

O cut não tem uma significação lógica. Mas tem como conseqüência a

modificação da árvore de busca: a chamada do cut proibia toda tentativa de busca

nos outros galhos da árvore de busca (as outras cláusulas do pacote).

Objetivos do uso do cut:

O cut é usado para delimitação do campo de busca e pode ter como objetivo:

• a busca determinística e a otimização (green cut) ou

• a modificação da semântica do programa (red cut).

20.1 Busca determinística (green cut)| ?- gosta(joao,X).X = nadar ;X = ia % neste caso a busca não é determinística.

| ?- gosta(joao,X),!.X = nadar

O cut aqui faz com que Prolog pare na primeira ocorrência de uma solução (é

a busca determinística).

Observação: Existe um predicado de LPA Prolog que faz isso: one.

exemplo: one(homem(X)). % é equivalente a: homem(X),!.X=joao

38


20.2 Otimização (green cut)

Para evitar a busca inútil ou infinita.

herdar(X,Y) :- ako(X,Y), !.herdar(X,Y) :- ako(X,Z), herdar(Z,Y).

é melhor do que escrever:

herdar(X,Y) :- ako(X,Y).herdar(X,Y) :- ako(X,Z), herdar(Z,Y).

20.3 Modificação da semântica (red cut)

min(X,Y,X) :- =<(X,Y), !.min(X,Y,Y).

% se X é ≤ a Y então o min é X senão o min é Y.

39

akoako

...

akoako

lazeres

esporte

música

pPop

cinema

artes_marciais

isa

...

...


21. O Fail

O predicado predefinido fail, encontra a falha da busca e provoca o

backtracking (retrocesso) para reavaliação do objetivo, ou seja, para procurar

novas soluções.

O fail é usado, geralmente, com o cut.

Exemplo:

Para representar esta afirmação: “João não gosta de artes marciais”

escreve-se:gosta(joao,X) :- isa(X,C),

herdar(C,a_marciais), !, fail.

gosta(joao,X).

40


22. Outras estruturas de controle

Objetivo1 -> objetivo2 % se objetivo 1, então objetivo 2.

Esta estrutura permite representar as regras de produção.

Ela é definida como seguinte:

o1 -> o2 :- o1, !, o2.

Exemplo:

read(N), >=(N,0), =<(N,10) -> write('Nota valida').

Objetivo1 -> objetivo2; objetivo3.

Para exprimir a estrutura “Se ... Senão ... ” :

Se objetivo 1 é verdadeiro, então objetivo 2, senão objetivo 3.

Exemplo: Cálculo do mínimo entre dois números.

min(X,Y,M) :- X =< Y -> M is X; M is Y.

Tal estrutura é definida da seguinte maneira:

o1 -> o2; o3 :- o1, !, o2.o1 -> o2; o3 :- o3.

41


23. Negação

Infelizmente, em Prolog, podemos somente definir a sentença verdadeira.

Todo fato exprimido é considerado como verdadeiro: jovem(sandra).

não(A) ∉ DEN(P)

Um solução para definição da negação é a negação por falha: uma

propriedade que não podemos demonstrar é considerada como falsa (hipótese do

mundo incluso ou mundo fechado).

nao(P) :- P, !, fail. % para qualquer termo Pnao(P).

Prolog implementa este operador: not.A negação não aceita variáveis ⇒ não podemos escrever: not(homem(X)).

Exemplo de uso:

homem(joao).yes

nao(homem(joao)).no

nao(nao(homem(joao))).yes

Críticas:

42


• Trabalha em um mundo incluso (fechado).

• O not não possui uma semântica clara:

Exemplo:

homem(joao).homem(roberto).adulto(roberto).

?- homem(X), not(adulto(X)).X=joao

?- not(adulto(X)), homem(X).no

43


PARTE V. OPERAÇÕES

44


24. Operações Relacionais

< menor 2<3. yes ou <(2,3).=< menor ou igual *

> maior

>= maior ou igual

= igualdade 7=7. yes ou =(7,7).

Para as expressões:

=:= igualdade de expressões (3*2)=:=(5+1). yes(3*2)=(5+1). no7=:=7. ?

=\= diferente(ou \=, e az vezes <>)

Exemplos: a cláusula maior:

maior (X,Y) :- X > Y.

maior(7,5). yes

a cláusula nota_valida:

nota_valida(X) :- (X>=0), (X=<10).

nota_valida(10.5). no

45


Comparação dos termos:

Podemos também comparar termos (expressões), basta preceder o operador

relacional do átomo especial @ :

bernardo @> adriano. yes

bernardo == bernardo. yesbernardo \= adriano. yes

Para as listas também:

[a,b,c] @>= [a,b,c]. yes[a,e] @> [a,b,2]. yes[a] @> [1]. yes

[a,b,c] = = [a,b,c]. yes

A comparação é feita sobre os códigos (ASCII) entre os elementos dos

termos da esquerda para a direita.

46


25. Operações Aritméticas

+ adição

- subtração

* multiplicação

/ divisão

mod resto da divisão inteira

(exp. 7 mod 2 = 1 e 7 / 2 = 3.5)

X is Expressão Atribuição dos valor da expressão para variável local X.Expressão é uma expressão aritmética.

Exemplo: a cláusula média:

media (X1,X2,M) :- M is (X1 + X2) / 2.media(6,8,Res). Res=7.

Exemplos de implementação de funções matemáticas:

f(x)=2*X2 +3*X –1f(A,Res) :- Res is 2*A*A+3*A-1.

f(-1,X)X=-2

47


26. Exercícios

1. Defina a função fatorial.

fat(0,1) :-!. % caso N=0 não é preciso explorar a regra 2fat(N,F) :- N1 is N-1, fat(N1,Y), F is Y*N.

fat(5,X).X=120

Esta solução é melhor do que escrever:

fat(0,1).fat(N,F) :- N \= 0, N1 is N-1,

fat(N1,Y), F is Y*N.

2. Defina a função fib:

fib(0)=1;fib(1)=1;fib(n)=fib(n-1) + fib (n-2).

48


PARTE VI. ESTRUTURA DAS LISTAS

49


27. Listas

É a melhor forma, em Prolog, para estruturação e manipulação de dados.

A notação da base é um pouco complicada:

.(termo, lista)

Mas existe uma notação simplificada:

[t1, t2, t3, ..., tn] n>=0

exemplos: [a,b,c,i,h] [5,2,8,0,1]

Quando n =0, a lista é vazia: []

Uma lista tem duas partes:

• A cabeça e

• O corpo (o resto).

Como conseqüência, existe uma outra notação:

[X|Y] onde X é a cabeça e Y é o corpo.

exemplo: lista([2,3,8,1]).

?- lista([A|B]).A=2, B=[3,8,1]

Listas compostas:

[[uma,lista,composta],a,b,[4,6,9],c]]

50


Cabeça e Corpo:

Como acabamos de mostrar, uma lista pode ser anotada como: [X|Y]Onde X é a cabeça e Y o resto (o corpo).

Por exemplo: A lista [A|B] pode ser unificada com a lista [4,3,2,1,9,0]

Dando: A=4 e B=[3,2,1,9,0]

Existe uma outra notação derivada:

[X,Y,Z|L]unificada com uma lista, retorna seu primeiro termo (X), segundo (Y), terceiro (Z) e o resto da lista (L).

Exemplo:lista([4,3,2,1,9,0]).

lista([A,B,C|L]).A=4, B=3, C=2 e L=[1,9,0]

51


28. Operações básicas sobre as listas:

Concatenação de listas:

append append(L1,L2,L).Concatena duas listas.

append([a,b,c],[1,2],X).X=[a,b,c,1,2]

Geração:

append(A,B,[a,b,c]).A = [] ,B = [a,b,c] ;

A = [a] ,B = [b,c] ;

A = [a,b] ,B = [c] ;

A = [a,b,c] ,B = []

Tamanho de uma lista

length(termo, comprimento)

retorna o comprimento de uma lista.

52


length([1,3,5,2],C)C=4

length([5,[a,b,c],2],C)C=3

Atenção: Não confundir length e len, len retorna o comprimento de

um termo.len(sarah, C).C = 5

Membro

member(Elemento, Lista).

member(2,[3,2,4,1]).yes

Remoção

remove(Elemento, Lista, Resto)removeall(Elemento, Lista, Resto)

para remover uma ocorrência de um elemento ou todas as ocorrências.

| ?- remove(4,[3,4,1,5,4],L).L = [3,1,5,4] ;L = [3,4,1,5] ;

53


removeall(4,[3,4,1,5,4],L).L = [3,1,5]

Reverter

reverse(Lista, List_Invertida)Para reverter uma lista.

reverse([2,3,1],L).L = [1,3,2]reverse([1,2,[a,b,c],3],X).X = [3,[a,b,c],2,1]

54


29. Exercícios

1. Implementar em Prolog todos esses predicados.

2. Definir o predicado palindromo sobre as listas.

3. Ordenar uma lista de diferentes maneiras.

55


PARTE VII. ENTRADAS E SAÍDAS

56


30. Entradas

A principal

read(X) ler uma entrada a partir do teclado e atribuir a ela a variável X.read(X).|: 5.X=5

Observe que a entrada deve terminar com um ponto (.).

Para entrar uma frase é preciso delimitá-la por apóstrofos:| ?- read(X).|: 'A via e boa'.X = ' A via e boa '

read(termo) ler uma entrada a partir do teclado e comparar com o

termo.read(domingo).|: domingo.yes

Outras

get(X) ler um caractere a partir do teclado e atribuir seu código ASCII a X.

| ?- get(X).|: AX = 65 % o código ascii do caractere A é 65

57


(o get0 faz a mesma coisa, só que o get não considera os caracteres em branco)

58


31. Saídas

A principal

write('Tchau!'). % Imprimi uma mensagem na tela .write(tchau).

Se a mensagem é composta, é preciso usar os apóstrofos.

write(A). % Imprimi na tela o conteúdo da variável A.

Outras

put(X) pega um inteiro X (entre 0 e 255) e imprimi os

caracteres correspondentes ao código ascii X.

| ?- put(65).A

display(X) | ?- write(2-1).2 - 1

| ?- display(2-1).(-)(2,1)

Diferente do write (que aguarda a ordem da

expressão para imprimir), o display imprimi uma

expressão na ordem de execução do Prolog.

skip(X) ler a partir do teclado até encontrar o caracter de

código ascii especificado: o inteiro X.

| ?- skip(65).

59


|: 6|: .|: a|: Ayes

Formatações:nl nl (new line) para pular uma linha.

tab(X) para pular X brancos.

Exemplo:

go :- write('Seu nome? '), read(Nome), nl, write('Oi'), tab(2), write(Nome),

nl.

| ?- go.Seu nome? |: samy.

Oi samy

60


PARTE VIII. ESTRUTURAS DE REPETIÇÃO

61


32. Repeat

O repeat provoca a repetição da execução da próxima cláusula até que a

condição seja verificada.

Exemplo:

leia :- repeat, read(N), N=5.% neste caso a condição é N=5.

Isto implica que leia vai ser repetida até que o usuário entre com o valor 5.

Repeat é definido como seguinte:

repeat.

repeat :- repeat.

62


PARTE IX. MANIPULAÇÃO DE ARQUIVOS

63


33. Saída Padrão

Um arquivo pode ser usado para leitura:

• arquivo de entrada

• ou para escrever arquivo de saída.

Criação e Abertura de arquivos de saída

tell(arq). Abre um arquivo de saída. Se o arquivo não existe,

então o tell irá criá-lo.

tell(meu_arq).yes

?- tell('exemp.dat').yes

telling(X). Retorna o nome do último arquivo de saída aberto (a

saída atual).

| ?- telling(X).X = 'c:\pro386w\meu_arq'

telling(arq). Verifica se o arquivo é o arquivo de saída atual.

| ?- telling('c:\pro386w\meu_arq').yes

| ?- telling(meu_arq).no

64


Por defaut, a saída padrão é o monitor, chamada user:

| ?- telling(X).X=user

Dicionário dos arquivos abertos

fdict(X). Retorna o dicionário (a lista) dos arquivos abertos.

| ?- fdict(X).X=['c:\pro386w\meuarq', 'c:\pro386w\exemp.dat']

Fechar os arquivos de saída abertos

told. O told retorna à saída padrão (user).

Portanto ele fecha o último arquivo de saída aberto.

told.telling(X).X=user

65


34. Entrada Padrão

see(arq). Abre um arquivo arq para entrada.

see(meu_arq).yes

seeing(X). retorna o nome do último arquivo de entrada aberto (a

entrada atual).

| ?- seeing(X).X = 'c:\pro386w\meu_arq'

seeing(arq). Verifica se o arquivo é o arquivo de entrada atual.

| ?- seeing('c:\pro386w\meu_arq').yes

| ?- seeing(meu_arq).no

Por defaut, a entrada padrão é o teclado, chamada

user:

| ?- telling(X).X=user

Fechar os arquivos de entrada abertos:

seen. Retorna à entrada padrão. Portanto, fecha o último

arquivo de entrada aberto.

66


seen.seeing(X).X=user

Fechar qualquer arquivo:

close(arq). Fechar um arquivo, seja de entrada ou de saída.

close(meu_arq).yes

close('exemp.dat').yes

67


35. Consulta de Bancos de Dados

Carregar arquivos de dados

Os fatos de um problema podem ser armazenados em um arquivo específico

de dados, por exemplo 'familia.dat'.

Para carregar tal arquivo na memória:

consult('familia.dat'). % por default a extensão do % arquivo é .pl

Quando o arquivo é modificado é preciso carregá-lo de novo. Um novo

consult carrega uma nova cópia na memória do computador (perto da

memória).

Por isso existe um outro predicado reconsult que carrega o novo arquivo

sem precisar ter uma nova cópia dele:

reconsult('familia.dat').

Listagem de pacotes:

listing(X). lista todas as relações de predicado X.

listing(homem)./* homem/1 */homem( joao ).homem( roberto ).yes

listing(avoo)./* avoo/2 */ avo( X, Y ) :-

68


pai( X, Z ), pai( Z, Y ).

Inserir novos fatos:

assert(X). Para inserir um novo fato X ou uma nova Regra.

assert(homem(juliano)).yes

assertz(homem(junior)).yes % inserir no final do pacote

homem

asserta(homem(adriano)).yes % inseri no início do pacote homem

listing(homem)./* homem/1 */homem( adriano ).homem( joao ).homem( roberto ).homem( juliano ).homem( junior ).yes

Remover fatos:

retarct(X). remova o fato X da base.

69


36. Definição

Extensão das gramáticas algébricas, objetivando fornecer uma linguagem de

especificação de gramáticas da linguagem.

A DCG é uma classe de programas Prolog que tem a vantagem de fornecer

um especificação executável.

A implementação é muito simples em Prolog, graças a unificação.

70


PRTE X. PROJETOS

71

Documents

Universidade Federal do Maranhão Curso de Pós … · Observação: Nada impede a definição de fatos que não são mais corretos. ... Prolog usa o conceito de regras para representar