Minicurso Prolog

Universidade Federal de AlagoasCampus Arapiraca

Disciplina: Paradigmas de Linguagem de Programação

Jackson Rodrigues CostaKarlos Albertto Ricardo Netto

Luis Adelmo Barbosa LeiteVanessa Rodrigues

Prolog

História 1879 – Proposta por Frege a partir dos

Cálculos de predicados.

1972 – Primeira implementação a linguagem Prolog realizada por Alain Colmerauer.

1974 – Formalização semântica da programação com clausulas de Horn.

1977 – Prolog de Edimburgo.

2

Programação Lógica Um programa em lógica é então a representação

de determinado problema ou situação expressa através de um conjunto finito de um tipo especial de sentenças lógicas denominadas cláusulas.

Algoritmo pode ser dividido em : Lógica Controle

3

Programação Lógica

4

O programador precisa apenas definir a os componentes lógicos de um algoritmo, deixando o controle da execução para ser exercido pelo sistema de programação em lógica utilizado.

Especificações são programas; Capacidade dedutiva; Não-determinismo; Reversibilidade das relações; Tríplice interpretação dos programas em lógica;

● semântica declarativa● semântica operacional● semântica procedimental

Recursão.

Aplicações

Sistema baseados em conhecimento; Sistemas de bases de dados; Sistemas especialistas; Processamento de linguagem natural; Educação; Arquiteturas não-convencionais.

5

Porque estudar prolog

Fácil aprendizado; Implementa com precisão todos os

modelos surgidos nos últimos anos; Defini precisamente Sistemas reflexivos; Libera o programador dos problemas

associados ao controle de rotinas.

6

Prolog É uma linguagem orientada ao processamento simbólico; Representa uma implementação da lógica como linguagem

de programação; Apresenta uma semântica declarativa inerente à lógica; Permite a definição de programas reversíveis; Permite a obtenção de respostas alternativas; Suporta código recursivo e iterativo ; Permite associar o processo de especificação ao processo de

codificação de programas; Representa programas e dados através do mesmo

formalismo; Incorpora facilidades computacionais extra lógicas e

metalógicas.

7

instalação

● Sudo apt-get install swi-prolog

Fatos O fato é formada por um predicado, seus

argumentos (objetos) e finalizamos a instrução com um ponto(.)

Exemplo:

progenitor(joão, josé).

9

Exemplo prático

10

Regras ● As regras declaram coisas que podem ser

ou não verdadeiras, dependendo da satisfação das condições dadas.

Exemplo:Para todo X e YX é mãe de Y se

X é progenitor de Y eX é feminino.

11

Exemplo prático

12

irmã(X, Y) :-progenitor(Z, X),progenitor(Z,Y),

feminino(X),diferente(X, Y).

Construções recursivas Recursividade – é um princípio que nos

permite obter a solução de um problema a partir da solução de uma instância menor dele mesmo.

Exemplo:Para todo X e Z

X é antepassado de Z seX é progenitor de Z.

13

Exemplo prático

14

Consultas Consulta - É sempre uma sequência

composta por um ou mais objetivos. Para obter a resposta, o sistema Prolog tenta satisfazer todos os objetivos que compõem a consulta, interpretando-os como uma conjunção.

Exemplo:

?- progenitor(josé, íris).

15

Sintaxe e Semântica

Objetos

Especifica formas diferentes para cada tipo de objeto

Nenhuma informação adicional como o seu tipo de dados é necessária.

Maiúsculas

Minúsculas

Tipos de ÁtomosLetras ou dígitos, caractere especial, letras minúsculas

Ex: socrates, nil, x47, x_y.

Cadeia de caractere especiais

Ex: <--------->, ::=, =/=

Caracteres quaisquer desde que entre apóstrofos

Ex: ‘D.Pedro I’, ’21 de dezembro de 2012’

Exemplos

gosta(maria, chocolate).

gosta(maria, vinho).

gosta(pedro, vinho).

gosta(pedro, maria).

Perguntas:

Pedro gosta de maria e maria gostade pedro ?

Quem gosta de chocolate ?

Variáveis

Cadeia de letras, dígitos, e do caractere especial (_)

Ex: X, Resultado, Lista_de_Alunos, _ , etc.

Estruturas

São formadas por um funtor seguidos de componentes separadas por virgulas e colocadas entre parênteses.

Estruturas de Árvores

(a + b) * (c - 5)

*(+(a,b), -(c,5))

Unificação

Unificam se:

Se forem idênticos

As variáveis de ambos os termos podem ser instanciadas com objetos de maneira que, após a substituição das variáveis por esses objetos, os termos se tornam idênticos.

data(D, M, 2012).

data(X, março, A).

?-data(D,M,2012) = data(X, março, A).

Tipos de Operadores

Operadores e AritméticaNa matemática costuma-se escrever na forma infixa.

2*a + b*c

Prolog entende:

+(*(2,a),(b,c))

Aritmética

Definir operadoresO programador pode definir os operadores

Pedro tem informações.

tem(pedro, informações)

josé ama maria.

ama(josé, maria)

:- op(600, xfx, tem).

Tabela de prioridade

Listas

29

Representação de Listas

Lista são estruturas simples de dados;

[Brasil, Uruguai, Argentina, Paraguai]

Isso é apenas a aparência externa da lista;

Objetos são arvores em Prolog;

Então como representar listas como objetos em Prolog?

30

Representação de Listas

Dois casos devem ser observados:

Listas vazias;

Listas não-vazias;

Representação do primeiro caso: []

No segundo caso:

A lista é constituída por cabeça e corpo;

31

Cabeça pode ser qualquer objeto;

Obrigatoriamente, o corpo é um lista;

Os dois são unidos em uma estrutura;

Representando listas, temos:

•(Cabeça, Corpo)

Representando o exemplo anterior, podemos fazer:

•(Brasil, •(Uruguai, •(Argentina, •(Paraguai, [])))).

32

Representação de Listas

•(Brasil, •(Uruguai, •(Argentina, •(Paraguai, [])))).

33

Representação de Listas

•(Brasil, •(Uruguai, •(Argentina, •(Paraguai, [])))).

34

Representação de Listas

Corpo

•(Brasil, •(Uruguai, •(Argentina, •(Paraguai, [])))).

35

Representação de Listas

CabeçaCorpo

O ultimo corpo da lista tem seu corpo vazio ([]);

O uso de “•” pode trazer confusão;

Em Prolog a notação é mais simples para as listas;

Em Prolog, [H|T] representam um lista onde:

H é a cabeça;

T é o corpo.

36

Representação de Listas

Exemplo de consulta com lista:

idades([[andre, 25], [jose, 30]]).

No programa consulte assim:

idades([[_,A], [_,B]]).

idades([[A,_], [B,_]]).

Outras formas de consulta:

idades([[andre,_], [jose,_]]).

37

Operações sobre Listas

Operações sobre Listas

Representação mais genérica:

[H|T], onde H vem de Head e T de Tail;

Exemplos:

primeiro([P|_], P).

ultimo([U], U).

ultimo([_|R], U) :- ultimo(R, U).

Agora consulte assim:

primeiro([a,b,c,d], P).

ultimo(([9,8,7],X).

38

Exemplo de concatenação de listas:

conc([], L, L).

conc([X | L1], L2, [X | L3]) :-

conc(L1, L2, L3).

Utilização do programa:

conc([a, b, c], [1, 2, 3], L).

conc([a, [b, c], d], [a, [], b], L).

conc(L1, L2, [a, b, c]).

conc(_, [X, g, Y | _], [a, b, c, d, e, f, g, h]).

Operações sobre Listas

Remoção de elementos de uma Lista:

remover(X, [X | C], C).

remover(X, [Y | C], [Y | D]) :-

remover(X, C, D).

Utilização do programa:

remover(a, [a, b, a, a], L).

remover(a, L, [b, c, d]).

40

Operações sobre Listas

Inversão de listas:

inverter([], []).

inverter([X | Y], Z) :-

inverter(Y, Y1),

conc(Y1, [X], Z).

Utilização do programa:

inverter([a, b, c], [c, b, a]).

inverter([a, b, c], X).

41

Operações sobre Listas

Length:

length([a,b], X).

length([a,b], 3).

Member:

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

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

Sort:

sort([4,1,9], X).

sort([2,1,1,2],[1,2]).

sort([2,1,1,2],[2,1,1,2]).

42

Predicados Úteis com Listas

Append:

append([1,2], [3,4], X).

append(A, [3,4], [1,2,3,4]).

Nextto:

nextto(3, 4, [1,2,3,4]).

nextto(4, 3, [1,2,3,4]).

nextto(3, 4, [1,2,3,0,4]).

43

Predicados Úteis com Listas

BacktrackingObserve o seguinte código:

antepassado(X, Z) :-

progenitor(X, Z).

antepassado(X, Z) :-

progenitor(X, Y),

antepassado(Y, Z).

O que acontece nesse código?

Tomando os exemplos anteriores de arvore genealógica, podemos perguntar, “João é antepassado de Íris?”.

Dois caminhos existentes;

44

Tomamos o primeiro programa;

antepassado(X, Z) :-

progenitor(X, Z).

?-antepassado(João, Íris).

?-progenitor(João,Íris).

Isso vai dar falha!

45

Backtracking

Então após a falha o Prolog retorna ao programa original e busca por soluções alternativas;

Mesmo caminho;

Ao voltar todo caminho é desfeito;

Exemplo:

gosta(joão, jazz).

gosta(joão, renata).

gosta(joão, lasanha).

gosta(renata, joão).

gosta(renata, lasanha).

Analisando:

?-gosta(joão, X), gosta(renata, X).

46

Backtracking

Comando CutAs vezes, o Backtracking pode ser ineficiente;

o “cut” aborta o processo de Backtracking;

Benefícios:

Programa roda mais rápido;

Ocupa menos memória;

Em alguns casos, evita laços-infinitos.

Principais aplicações:

Eliminar soluções alternativas da árvore de pesquisa quando uma já é suficiente;

Encerrar a pesquisa quando a continuação levar ao infinito;

Na implementação da negação como regra de falha.

47

Exemplo:

mamifero(X) :- gato(X).

mamifero(X) :- cachorro(X).

mamifero(X) :- rato(X).

gato(tom).

rato(jerry).

cachorro(spike).

gosta(ana,X) :- gato(X),!.

gosta(ana,X) :- mamifero(X).

48

Comando Cut

Negação por Falha

Como podemos dizer isso em Prolog?

“Maria gosta de todos os animais, menos de cobras”.

49

Negação por FalhaComo podemos dizer isso em Prolog?

“Maria gosta de todos os animais, menos de cobras”.

gosta(maria, X) :-

cobra(X), !, fail.

gosta(maria, X) :-

animal(X).

O cut evita o backtracking e o fail irá ocasionar na falha da cláusula.

Também podemos usar para definir a relação diferente(X, Y):

diferente(X, Y) :- X=Y, !, fail; true.

Se Objetivo é bem-sucedido então not(Objetivo) falha, senão not(Objetivo) é bem-sucedido.

not(P) :- P, !, fail; true.

50

Estruturas de Dadose

Entrada e Saída

Estruturas de Dados

● Base de Dados pode ser naturalmente representada em prolog com um conjunto de fatos;

● Para recuperação de informação estruturada em base de dados

– Mecanismos de consultas;

– Mecanismos de unificação;

Recuperação de Informações

Recuperação de Informações

● Recuperar todas as famílias “oliveira”

– ?-família(pessoa(_, oliveira, _, _), _, _).● Famílias cuja mãe não trabalhar

– ?-família(_, pessoa(_, _, _, nt), _).● Famílias que não tem filhos

– ?-família(_, _, []).● Famílias com 3 filhos ou mais

– ?-família(_, _, [_, _, _| _]).

Recuperação de Informações● Nome e Sobrenome de todas as pessoas

– ?-existe(pessoa(Nome, Sobrenome, _, _)).● Saber quem nasceu em 93

– ?-filho(X), nasceu(X, data(_,_,93)).● Pessoas nascidas antes de 76

– ?-existe(pessoa(_, _, data(_,_,A), nt), A < 76.

Recuperação de Informações

● As pessoas com salário maior 1000

– ?- existe(Pessoa),

nasceu(Pessoa, data(_,_,A)),

A > 65,

salário(Pessoa, Salário),

Salário > 5000.● Saber as famílias e suas rendas

– ?-família(Pai, Mãe, Filhos),

total([Pai, Mãe | Filhos], RFam).

Abstração de Dados● Técnica de programação que facilita a

representação de estruturas de dados complexas;

● Contribui para a legibilidade do programa;

● Construções matemáticas abstratas, como autômatos, podem ser traduzidas diretamente para especificações executáveis;

Abstração de Dados – Autômatos

Consultas

● ?-aceita(s1, [a, a, a, b]).● ?-aceita(S, [a, b]).● ?-aceita(s1, [X, Y, Z]).

Abstração de Dados

● Problema pode ser abordado de várias maneiras;

– Variando sua representação;

– Inclusão de tratamento de redundância pode ocasionar economia de computação;

● Muitas vezes, o passo chave para resolução de um problema é a generalização;

Entrada e Saída

● Entradas e Saídas são executadas por meio de predicados pré-definidos;

● Predicados para leitura e escrita de termos são:

– read(Termo), write(Termo).

● Predicados para formatação de texto:– tab(N), nl;

Entrada e Saída

● ?-escreveLista2([[a, b, c], [d, e, f], [g, h, i]]).

Entrada e Saída

Entrada e Saída

● Também pode-se trabalhar com entrada e saída de arquivos;

● Pode gardar consultas nestes arquivos e executá-las lendo o arquivo;

● Predicados:– see(A);

– tell(A);

– seen;

– told;

Perguntas?