Baixe Fundamentos de Prolog: uma breve Fundamentos de Prolog: uma breve i e outras Notas de estudo em PDF para Cultura, somente na Docsity! Fundamentos de Prolog: uma breve introdução à programação em lógica Jacques Robin, DI-UFPE jr@di.ufpe.br, www.di.ufpe.br/~jr O que é Prolog?  Primeiro e mais usado linguagem do paradigma da Programação em Lógica (PL)  Operacionalização simples, prática e eficiente da PL  PL unifica:  Engenharia de Software (especificação formal, linguagens de programação)  IA (raciocino e Representação do Conhecimento (RC))  Banco de Dados -- Dedutivos (BDDs)  Teoria Lógica (TL) das provas PL x resto do mundo  PL x programação imperativa, funcional e 00:  mais declarativa, mais alto-nível  mais versátil -- linguagem única para: especificar formalmente e implementar programar aplicações, scripts e consultas em BD  PL x outros formalismos de RC:  melhor fundamentação teórica  melhor integração com o resto da ciência computação  PL = base interessante para integração de paradigmas  PL = caso particular de programação por restrições Cláusulas de Horn  Formulas de L1:  em forma normal implicativa (todas as variáveis implicitamente universalmente quantificadas)  com premissas todas positivas  e uma conclusão única e positiva.  Padrão: P1 & ... & Pn => C  Muitas mas nem todas as formulas de L1 tem conjunto equivalente de cláusulas de Horn, cex: V X,Y animal_lover(X) & animal(Y) & kills(X,Y) => F  Programa Prolog = conjunto (implicitamente conjuntivo) de cláusulas de Horn Programa Prolog e cláusulas de Horn  Fatos Prolog:  cláusulas de Horn com premissa única T implícita  ex: C. <=> T => C  Regras Prolog:  outras cláusulas de Horn  ex: C :- P1, ... ,Pn. <=> P1 & ... & Pn => C  Premissas de cláusulas com a mesma conclusão são implicitamente disjuntivas:  ex: {C :- P1, ... ,Pn., C :- Q1, ... ,Qm} <=> (P1& ... & Pn) v (Q1 & ... & Qm) => C  Escopo das variáveis = uma cláusula West é criminoso? em L1 V P,W,N american(P) & weapon(W) & nation(N) & hostile(N) & sells(P,N,W) => criminal(P) E W owns(nono,W) & missile(W) V W owns(nono,W) & missile(W) => sells(west,nono,W) V X missile(W) => weapon(W) V X enemy(N,america) => hostile(N) american(west) nation(nono) enemy(nono,america) nation(america) american(P) & weapon(W) & nation(N) & hostile(N) & sells(P,N,W) => criminal(P) owns(nono,m1) missile(m1) owns(nono,W) & missile(W) => sells(west,nono,W) missile(W) => weapon(W) enemy(N,america) => hostile(N) american(west) nation(nono) enemy(nono,america) nation(america) West é criminoso? em Prolog american(P) & weapon(W) & nation(N) & hostile(N) & sells(P,N,W) => criminal(P) owns(nono,m1) missile(m1) owns(nono,W) & missile(W) => sells(west,nono,W) missile(W) => weapon(W) enemy(N,america) => hostile(N) american(west) nation(nono) enemy(nono,america) nation(america) criminal(P) :- american(P), weapon(W), nation(N), hostile(N), sells(P,N,W). owns(nono,m1). missile(m1). sells(west,nono,W) :- owns(nono,W), missile(W). weapon(W) :- missile(W). hostile(N) :- enemy(N,america). american(west). nation(nono). enemy(nono,america). nation(america). West é criminoso? busca criminal(P) :- american(P), weapon(W), nation(N), hostile(N), sells(P,N,W). owns(nono,m1). missile(m1). sells(west,nono,W) :- owns(nono,W), missile(W). weapon(W) :- missile(W). hostile(N) :- enemy(N,america). american(west). nation(nono). enemy(nono,america). nation(america). criminal(west)? <- yes. american(west)? -> yes. weapon(W)? <- W = m1. missile(W)? -> W = m1. nation(N)? -> N = nono. hostile(nono)? <- yes. enemy(nono,america)? -> yes. sells(west,nono,m1)? <- yes. owns(nono,m1)? -> yes. missile(m1)? -> yes. Forçar o backtracking para obter todas as respostas g1(a). g21(a). g3(a). g4(a). g1(b). g21(b). g22(b). g3(b). g(X) :- g1(X), g2(X). g(X) :- g3(X), g4(X). g2(X) :- g21(X), g22(X). g(U)? <- U = b.  g1(U)? -> U = a.  g2(a)? <- no.  g21(a)? -> yes.  g22(a)? -> no.  g1(U), U \ {a}? -> U = b.  g2(b)? <- yes.  g21(b)? -> yes.  g22(b)? -> yes. ;  g1(U), U \ {a,b} ? -> no. Backtracking em cascadas g1(a). g21(a). g3(a). g4(a). g1(b). g21(b). g22(b). g3(b). g(X) :- g1(X), g2(X). g(X) :- g3(X), g4(X). g2(X) :- g21(X), g22(X). g(U), g \ {g1,g2}? <- U = a.  g3(U)? -> U = a.  g4(a)? -> yes. ;  g3(U), U \ {a}? -> U = b.  g4(b)? -> no.  g3(U), U \ {a,b}? -> no. g(U), g \ {g1,g2 ; g3,g4}? - > no. Sintaxe 1  fato -> fa. (abrev. para Formula Atômica)  regra -> fa0 :- fa1, ... , faN.  consulta -> fa1, ... , faN.  fa -> pred(termo1, ... , termoN) | preop termo1 termo2 | termo1 inop termo2 | termo1 termo2 postop  termo -> constante | variável | fa  constante -> átomos | numeros  pred -> átomo  Ao invés de L1: nenhuma distinção entre predicados e funções Semântica  Programa Prolog P possui 2 semânticas:  semântica declarativa = semântica das formulas de L1 correspondendo as cláusulas de P em geral:  conjunto mínimo de termos instanciados verificando P  extensão de P como BDD  modelo de Herbrand  semântica procedimental = execução do algoritmo de resolução sobre P  Maioria dos predicados built-in:  funcionam por efeitos colaterais  não possuem semântica declarativa em L1 Listas  [ e ]: início e fim de lista , separação entre eltos |: separação entre 1o elto e resto da lista  ?- [a,b,X,p(Y,C)] = [Head|Tail] Head = a, Tail = [b,X,p(Y,C)] ?- [[p(X),[a]],q([b,c])] = [[H|T1]|T2] H = p(X), T1 = [[a]], T2 = [q([b,c])]  member(X,[X|_]). member(X,[Y|Z]) :- member(X,Z). ?- member(b,[a,b,c]) -> yes. ?- member(X,[a,b,c]) -> X = a ; X = b ; X = c ; no. Igualdade x unificação  Ao invés de L1, Prolog não inclui operador de igualdade semântica.  = operador de unificação sintática:  não declara nada, apenas teste se 2 termos podem se tornar igual por unificação das suas variáveis  falha com termos ground sintaticamente diferentes  == operador de igualdade sintática:  também apenas teste igualdade de 2 termos, sem tentar unificar as suas variáveis  falha com termos sintaticamente diferentes, mesmo universais Cut: exemplo f1(X,0) :- X < 3. f1(X,2) :- 3 =< X, X < 6. f1(X,4) :- 6 =< X.  f1(1,Y), 2 < Y? <- no  f1(1,Y)? -> X = 1, Y = 0 1 < 3? -> yes  2 < 0? -> no  f1(1,Y)? -> X = 1, Y = 2 3 =< 1? -> no  f1(1,Y)? -> X = 1, Y = 4 6 =< 1? -> no f2(X,0) :- X < 3, !. f2(X,2) :- 3 =< X, < 6, !. f2(X,4) :- 6 <= X, !.  f2(1,Y), 2 < Y? <- no  f2(1,Y)? -> X = 1, Y = 0 1 < 3? -> yes  2 < 0? -> no Cut: exemplo (cont.) f3(X,0) :- X < 3, !. f3(X,2) :- X < 6, !. f3(X,4). ?- f3(1,Y). Y = 0 ?- ; no. ?-  Esses cuts modificam até a semântica declarativa do programa f4(X,0) :- X < 3. f4(X,2) :- X < 6. f4(X,4). ?- f4(1,Y). Y = 0 ?- ; Y = 2. ?- Hipótese do mundo fechado  Ao invés de L1, Prolog não permite nem fatos, nem conclusões de regras negativos, cex: ~animal_lover(geber). ~kill(X,Y) :- animal_lover(X), animal(Y).  Princípio de economia:  declarar e deduzir apenas o que é verdadeiro,  supor que tudo que não é mencionado nem deduzível é falso (hipótese do mundo fechado)  Operador de negação por falha em premissas:  not p(X) verificado sse p(X) falha  =/= de ~p(X) verificado sse ~p(X) no BDE ou na conclusão de uma regra com premissas verificadas Prolog x sistemas de produção: controle  Raciocino dirigido pelo objetivo (e não pelos dados)  Regras encadeada para trás (e não para frente)  Busca em de cima para baixo e em profundidade na árvore de prova (e não de baixo para cima e em largura)  Sempre dispara 1a regra aplicável encontrada (ie, sem resolução de conflitos)  Backtracking quando 1a regra leva a uma falha Prolog x sistemas de produção: poder expressivo  Fatos universais (e não apenas instanciados):  ex: ancestral(X,adão).  Unificação (e não apenas matching):  bidirecional  variáveis lógicas podem ser instanciadas com termos compostos (e não apenas atómicos)  ex: ?- prof(X,disc(ia,dept(di,ufpe))) = prof(pessoa(geber,Y),disc(ia,Z)) -> X = pessoa(geber,Y), Z = dept(di,ufpe). Prolog x resolução em L1  Restrições de Prolog com respeito a L1:  apenas cláusulas de Horn  sem igualdade semântica  unificação sem verificação de ocorrência  Extensões de Prolog com respeito a L1:  predicados (e não apenas funções) como construtores de termos  predicados built-in de segunda ordem  Outras diferencias com respeito a L1:  negação por falha (limitada mas não monótona) Prolog x programação imperativa 2  Estrutura de dados única: termo Prolog  variáveis lógicas sem tipo estático  Controle implícito built-in na estrategia de resolução, ex: Em programação imperativa procedure c(E) const e0:tipoE0; var E:tipoE, S0:tipoS0, l1:tipo-I1, S1:tipoS1; do if E = e0 then do S0 := call p0(e0); return S0; end; else do I1 := call p1(E); S1 := call p2(E,l1); return S1; end; end; Em Prolog c(e0,S0) :- p0(e0,S0). c(E,S1) :- p1(E,I1), p2(E,I1,S1). Prolog x programação funcional 1 Matematicamente, predicado = relação:  não-determinismo:  respostas múltiplas (disponíveis por backtracking),  unificação e busca built-in,  livra o programador da implementação do controle;  bi-direcionalidade:  cada argumento pode ser entrada ou saída, dependendo do contexto de chamada,  única definição para usos diferentes: verificador, instanciador, resolvedor de restrições, enumerador.  integração imediata com BD relacional Prolog x programação funcional 2  Append em Lisp: (defun append(L1,L2) (cond ((null L1) L2)) (T (cons (first L1) (append (rest L1) L2)))))) ?- append([a,b],[c,d]) [a,b,c,d]  Append em Prolog: append([],L,L). append([H|T1],L,[H|T2]) :- append(T1,L,T2). ?- append([a,b],[c,d],R). R = [a,b,c,d].  Append relacional codifica 8 funções Prolog x programação OO: exemplo  Em OO: pt[subclass_of planobj; attrs[X inst_of int, Y inst_of int]; mets[right(Pt inst_of pt) {return self.X >= Pt.X}]] pt1[inst_of pt; attrs[X = 0, Y = 0]] pt2[inst_of pt; attrs[X = 1, Y =1]] ?- pt1.above(pt2) -> no.  Em Prolog: pt(0,0). pt(1,1). planobj(pt(_,_)). right(pt(X1,_),pt(X2,_) :- X1 >= X2. ?- above(pt(0,0),pt(1,1)). -> no. Programação por restrições  Programar = declarar restrições sobre os valores v1, ... vn, de um conjunto de variáveis V1, ..., Vn:  o dominio Di associado a cada variável Vi  equações e inequações Pj(Vp, ..., Vq) ligando-as  Executar programa:  fazer uma consulta sobre a compatibilidade de restrições de entrada Pk(Vr, ..., Vs) com as restrições do programa  recuperar em saída todos os valores (v11, ... , vn1) ... (v1l, ..., vnl) de (V1, ... , Vn) que satisfazem ambos Pj(Vp, ... , Vq) e Pk(Vr, ..., Vs). Programação por restrições: exemplo integer(N). integer(S). sumto(0,0). sumto(N,S) :- 1 =< N, N =< S, sumto(N - 1, S - N). ?- S =< 3, sumto(N,S). (N = 0, S = 0), (N = 1, S = 1), (N = 2, S = 3). Propagação recursiva de restrições: 1: 1 =< N1 = N =< S1 = S =< 3  (N1,S1) in {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)} 2: 1 =< N2 = N1 - 1 =< S2 = S1 - N1 =< 2  (N2,S2) in {(1,1),(1,2),(2,1),(2,2)} => (N1,S1) in {(2,3),(2,4), (3,4),(3,5)}  N1 = 2, S1 = 3 => N2 = 1, S2 = 1 Prolog como restrições: exemplo prof(X,disc(ia,dept(di,ufpe))) ?- prof(pessoa(geber,Y),disc(ia,Z)) 1: prof = prof, 2 = 2 2: X = pessoa(geber,Y), disc = disc, 2 = 2, 3: ia = ia, dept(di,ufpe) = Z 4: fundo das arvores atingindas  devolve as equações não trivais: X = pessoa(geber,Y), Z = dept(di,ufpe). Linguagens de PL multiparadigma  PL concorrente, paralela (Concurrent Prolog, Parlog)  PL funcional (Lambda-Prolog, LeFun)  PL OO (Logtalk, Objlog, Login, F-Logic)  PL por restrições, ie, Prolog + (in)equações:  aritméticas (CLP(R), CHIP, Prolog3)  de tipos (Login)  buleanas (CHIP, Prolog3)  PL para Internet, predicados built-in para:  protocolos http, ftp, mail, news, etc.  parsing de páginas HTML para termos Prolog  PiLLoW, Logicweb Ficou curioso? Tem mais!  Disciplina de Programação em Lógica:  Prolog  LIFE: PL funcional, OO e por restrições de tipos, e com interface para BD relacional  Florid: PL OO com igualdade semântica e sintaxe de ordem superior, para BD dedutivo e Internet  projeto: implementar agentes inteligentes para a RoboCup  Projetos de pesquisa:  CRUIJFF: ambiente de programação de agentes inteligentes integrando os paradigmas lógica, funcional, e por restrições sobre uma base Java.  Web SKWASH: agentes inteligentes de data mining de Web log file e geração de resumos hipertextuais