View
1.365
Download
0
Category
Preview:
Citation preview
Linguagem de Programação Lógica ‐ PrologProf. Iális Cavalcante
Engenharia da Computação – UFC/Sobral
0. SumárioAmbienteIniciando um programaFatos e RegrasOperadores e AritméticaEstruturasRecursividadeListas
AmbienteRecursos requeridos:◦ Editor de texto (escrita de programas);
◦ Ambiente de desenvolvimento (SWI-Prolog - http://www.swi-prolog.org/);
◦ Controle dos diretórios e arquivos;
Interpretador vs Compilador◦ Um compilador transforma seu programa em um arquivo
executável, cujo arquivo pode ser executado fora doambiente de desenvolvimento.
◦ Um interpretador executa seu programa linha por linhadentro dos recursos do ambiente de desenvolvimento.
◦ Interpretador Prolog
Iniciando um programaEscreva um programa com o código abaixo:gosta(maria,comida).
gosta(maria,vinho).
gosta(joao, vinho).
gosta(joao, maria).
◦ Não coloque espaço após o ponto;
◦ Não escreva qualquer termo com letra maiúscula;
◦ Adicione uma linha em branco ao final de tudo;
Salve como “intro.pl”Abra o arquivo no SWI-PrologVerifique a compilação (há erros?)Entre com: [intro].
Iniciando um programa
Teste o comando listing.Execute algumas consultas:◦ gosta(maria,comida).◦ gosta(joao, vinho).◦ gosta(joao, comida).
Quando terminado pode sair de intro com o comando halt
Fatos e RegrasO programa criado anteriormente pode ser adicionado por mais fatos.Realize novos testes a cada modificação:◦ gosta(joao,X).
◦ gosta(maria,X).
◦ gosta(Y, comida).
◦ gosta(Y, vinho).
Para a formação de uma regra é necessário a estrutura condicional a partir de um operador:
Operador Significado
:- if
, and
; or
Fatos e RegrasExemplo de fatos:amiga(joana,maria).
amiga(maria,joana).
amiga(maria,clara).
amiga(clara,maria).
ama(joana,maria).
ama(maria,joana).
Exemplo de regra (amiga_intima):amiga_intima(Ela1,Ela2) :-
amiga(Ela1,Ela2), amiga(Ela2,Ela1), ama(Ela1,Ela2), ama(Ela2,Ela1).
?- amiga_intima(maria,joana).
yes
?- amiga_intima(maria,clara).
no
Fatos e Regras
Exercícios: crie regras para expressar as seguintes frases...◦ João gosta de qualquer coisa que Maria gosta.
João gosta de alguma coisa se Maria gosta de alguma coisa.
◦ João gosta de qualquer um que gosta de vinho.
João gosta de alguém se alguém gosta de vinho.
◦ João gosta de qualquer um que goste deles mesmos.
Fatos e RegrasJames I
Charles I Elizabeth
Catherine Charles II James II
Sophia
George I
Fatos e RegrasDefina os fatos presentes nessa árvore da família...% macho(P) é verdadeiro quando P é macho
macho(james1).
macho(charles1).
macho(charles2).
macho(james2).
macho(george1).
% femea(P) é verdadeiro quando P é fêmea
femea(catherine).
femea(elizabeth).
femea(sophia).
Fatos e RegrasContinuando...% pai(C,P) é verdadeiro quando C tem um pai chamado P
pai(charles1, james1).
pai(elizabeth, james1).
pai(charles2, charles1).
pai(catherine, charles1).
pai(james2, charles1).
pai(sophia, elizabeth).
pai(george1, sophia).
Salve o programa como familia.pl e faça algumas buscas.
Fatos e Regras◦ George I é o pai de Charles I?◦ Quem é o pai de Charles I?◦ Quem são os filhos de Charles I?
Tente adicionar as seguintes regras e verifique o resultado:◦ M é a mãe de P se ela é um pai de P e é fêmea.◦ F é o pai de P se ele é pai de P e é macho.◦ X é irmã(o) de Y se ambos têm os mesmos pais.
Operadores e AritméticaAridade◦ A aridade de um predicado é simplesmente o
número de argumentos que ele possui.◦ Prolog se referencia à aridade porque permite
diferentes predicados com o mesmo nome mas com aridade diferente.
O uso desse recurso não é recomendável: legibilidade...
Uso de espaços◦ Evitar ao máximo, principalmente na definição
dos fatos.
Operadores e Aritmética
Comentários% - para uma linha simples/*
Para mais de uma linha a ser comentada*/
Entrada/Saída simples◦ nl – move o cursor para uma nova linha na
tela◦ write(X) – escreve X na tela
Operadores e AritméticaOperadores relacionais: <, >, >=, =<, =, etc.◦ positive(N) :- N>0.
◦ non_zero(N) :- N<0 ; N>0.
Operadores aritméticos: +, -, *, /◦ Funções como sqrt, exp, cos,... Mas com comportamento
diferente.
◦ “1+4”, “3+2” e “5*1” são trabalhados de formas diferentes.
primo(2).
primo(3).
primo(5).
...
◦ As consultas “primo(1+1)” or “primo(5*1)” falharão!
◦ “X is 1+1, primo(X).” terá sucesso!
Operadores e AritméticaTeste a expressão:◦ X is sqrt(9), Y is 2 ** 4, Z is floor(3.14).
Teste as expressões a seguir e entenda o funcionamento das relações em Prolog:◦ N is 1+1. ◦ N is 1+1, P is N*2, Q is P+Q. ◦ N is X+1. ◦ I is I+1. ◦ I is 6, I is I+1. ◦ I is 6, J is I+1.
Apenas duas consultas são válidas!
Operadores e AritméticaTodas as operações em Prolog são tratadas como relações.Sendo uma função definida em C/C++ para calcular o valor mínimo entre dois números:
int minimum(int x, int y) {
if (x < y) return x;
else return y;
}
Em Prolog, essa função será representada por uma relação.
Operadores e AritméticaEm geral, uma função que tem k argumentos será representada em Prolog como uma relação com:◦ k+1 argumentos;◦ Sendo que o último é usado para carregar o
resultado;
Então em Prolog, escreve-se:% minimum(X,Y,Z) é verdadeiro se Z é o mínimo de X e Yminimum(X,Y,X) :- X<Y. minimum(X,Y,Y) :- X>=Y.
Estruturas (Structure)
Forma geral:estrutura-nome (atributo, ..., atributo )Parece um predicado, mas aqui representam objeto. Não representam relações.Se diferenciam, porque estruturassempre surgem como argumentos.
EstruturasSupondo que queremos representar carros como os atributos: marca, anos de uso (idade), preço. Chamaremos uma estrutura carro de três lugares, por exemplo: carro(ford,3,5000) representando um carro Ford de 3 anos de uso com valor de venda R$ 5.000,00.
% possui(P,C) é verdadeiro se P tem um carro que combina com C
possui(joao, carro(ford,3,5000)).
possui(joao, carro(opel,2,6000)).
possui(gil, carro(toyota,5,1000)).
possui(gil, carro(ford,2,2000)).
E fazemos a pergunta: “Que tipo de Ford o Gil possui?"
Consulta: possui(gil, carro(ford, Idade, Preco)) Resposta: Idade=2, Preco=2000
EstruturasSe quiser somente recuperar a informação sobre alguns campos pode-se utilizar o marcador _ (underline) que retorna qualquer valor existente| ?- possui(Pessoa, carro(ford,_,_)).
Pessoa = joao ? ;
Pessoa = gil
yes
◦ O underscore "_" indica que não se quer saber qual fato se casa com os campos apresentados.
◦ Se quiser saber qual marca de carro foi vendida abaixo de 5000, deve-se verificar:
| ?- possui(_, carro(Marca,_,Preco)), Preco < 5000.
Marca = toyota
Preco = 1000 ? ;
Marca = ford
Preco = 2000
yes
RecursividadeQuando se usa a recursão deve-se conhecer três coisas:◦ Algum conjunto (ou “estrutura de dados”) sobre a qual está sendo feita
a recursão: exemplos comuns incluem números, arrays, árvores, etc.
◦ Uma definição de caso base, normalmente lida com uma estrutura vazia.
◦ Uma definição de caso recursivo, explicando como trabalhar um caso não-trivial em termos de algumas versões de valores menores que ele mesmo.
Fatorial: por definição, o fatorial de algum número n, escrito n! é n*n-1*n-2*…*1. Nós podemos expressar em termos de recursão como segue: ◦ Estrutura de Dados: números naturais
◦ Caso Base: 0! = 1
◦ Caso Recursivo: Para qualquer n>0, nós temos n! = n * (n-1)!
◦ Perceba que foi definido n! em termos de (n-1)!. Pode-se fazer isso a partir do momento que se conhece que (n-1) < n
ListasO formato de uma lista segue uma seqüência de valores, correspondente a um vetor em C.Exemplo: [joao, maria, patricia][‘string’, 6, maria, X] também é válida;Lista vazia: [ ]Lista não-vazia: contém cabeça (head) com o primeiro elemento e cauda (tail) contendo os outros elementos.Exemplo: [joao, maria, patricia]◦ Cabeça: joao◦ Cauda: [maria, patricia]
ListasNotação específica para listas:[Hd | Tl] denota que a lista possui cabeça Hd e com cauda uma lista Tl.[joao, maria, patricia] -> [ joao | [maria, patricia] ] ->
-> [joao | [maria | [patricia] ] ] -> [joao | [maria | [patricia | [ ] ] ] ]
Processamento de listas utiliza regras de unificação:◦ O único termo que unifica com [ ] é [ ];◦ [H1 | T1] unifica com [H2 | T2] se H1 unifica com H2
e T1 unifica com T2
ListasQuase todos os predicados que utilizam listas são recursivos:◦ Caso base: a lista vazia [ ];
◦ Caso recursivo: para uma lista da forma [H | T], execute alguma ação na cabeça H e chame o predicado recursivamente usando a cauda T.
Tamanho de uma lista: size(Lista,Tam).% size(List,N) is true if List has N elements
size([],0).
size([H|T],N) :- size(T,N1), N is N1+1.
Definindo:◦ O tamanho da lista vazia é 0;
◦ O tamanho da lista [H | T] é: 1+(tamanho de T).
ListasSomando uma lista: supondo que seja formada apenas por números.
% somaLista(List, N) é verdadeiro se os elementos de Lista somam para N
somaLista([],0).
somaLista([H|T],N) :- somaLista (T,N1), N is N1+H.
Verificação de elemento na lista:
% contem(Elem, Lista) é verdadeiro se Lista contém Elem
contem(X,[X|_]).
contem(X,[_|T]) :- contem(X,T).
contem(2, [1,2,3])
contem(E, [1,2,3])
contem(E, [2,1,2])
contem(E, [])
Listas como Acumuladores% print_to(N) - prints out all the numbers down from N to 0
print_to(0) :- write(0).
print_to(N) :- N>0, write(N), nl, N1 is N-1, print_to(N1).
print_to(5).
Imprime todos os números entre N e 0, N ≥ 0.Como armazenar este resultado em um vetor? [H| T]
collect_to(0,[]).collect_to(N,[N|T]) :- N>0, N1 is N-1, collect_to(N1,T).
Listas como AcumuladoresUnindo duas listas:◦ O predicado join_list(L1,L2,L3) define “se quisermos juntar L1 e
L2 conseguimos L3".
Considerando as possibilidades para L1 ◦ L1 é uma lista vazia, neste caso L3 é L2
◦ L1 está na forma[H1 | T1]. Se fixar L2 ao seu final, consegue-se uma lista em que a cabeça ainda é H1, mas cuja cauda é a junção de T1 e L2
join_list(L1,L2,L3) :- L1=[], L3=L2.
join_list(L1,L2,L3) :- L1=[H1|T1], join_list(T1,L2,T3), L3=[H1|T3].
Outras possibilidades?
Listas como Acumuladoresjoin_list([], L2, L2).join_list([H1|T1], L2, [H1|L3]) :- join_list(T1,L2,L3).
join_list([],L2,L3) :- L3=L2.join_list([H1|T1],L2,L3) :- join_list(T1,L2,T3), L3=[H1|T3].
join_list([1,2],[6,7],X). join_list(X, [5,6], [3,5,6]). join_list([3,4], Y, [3,4,5,6]). join_list(X,Y,[1,2]).
Listas como AcumuladoresInvertendo uma lista (duas maneiras):
% bad_reverse(L1,L2) - uma implementação ruim de inversão de lista
bad_reverse([],[]).
bad_reverse([H|T], L2) :-
bad_reverse(T,NT), append(NT,[H],L2).
% myreverse(?List, ?Reversed)
% é verdadeiro quando Reversed possui os mesmos elementos que List mas em ordem inversa
good_reverse(List, Reversed) :- good_reverse(List, [], Reversed).
good_reverse([], Reversed, Reversed).
good_reverse([Head|Tail], SoFar, Reversed) :- good_reverse(Tail, [Head|SoFar], Reversed).
Listas como Acumuladores
Exercícios:◦ Escreva predicados para os seguintes
problemas:cutlast(L1,L2) que é verdadeiro se L2 é L1 com o último elemento removido. trim(L1,N,L2) que é verdadeiro se L2 contém somente os N primeiros elementos de L1 evens(L1,L2) que é verdadeiro se L2 contém somente aqueles elementos de L1 que são pares, e na mesma ordem.
Backtracking e CutSuponha um programa que avalie a necessidade de atendimento de um paciente de acordo com sua idade:
grau(N, primeiro) :- N>=70. grau(N, segundo) :- N<70, N>=63. grau(N, terceiro) :- N<63, N>=55. grau(N, quarto) :- N<55, N>=50. grau(N, espera) :- N<50, N>=40. grau(N, falha) :- N<40.
grau(75, G) -> G = primeiroMas avalia ainda todas as outras condições!
Backtracking e Cutint pri(int n) { return n>=70; }
int seg(int n) { return n<70 && n>=63; }
// ... preenchendo o resto ...
int fal(int n) { return n<40; }
switch(n) {
case(pri(n)): cout << “Primeiro"; break;
case(seg(n)): cout << “Segundo"; break;
case(ter(n)): cout << “Terceiro"; break;
case(qua(n)): cout << “Quarto"; break;
case(esp(n)): cout << “Espera"; break;
case(fal(n)): cout << “Falha";
}
Avalia todos!
Avalia apenas o válido!
Backtracking e CutPara melhorar o desempenho pode-se usar o recurso: ! (cut).Funciona como o break em C;
grau(N, primeiro) :- N>=70, !. grau(N, segundo) :- N>=63, !. grau(N, terceiro) :- N>=55, !. grau(N, quarto) :- N>=50, !. grau(N, espera) :- N>=40, !. grau(N, falha) :- N<40.
Recommended