FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 1
Faculdade de Ciências e TecnologiaDepartamento de Matemática e Computação
Bacharelado em Ciência da Computação
Linguagens de Programação
Aula 09
Rogério Eduardo Garcia([email protected])
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
2
Linguagens de Programação
Paradigma Lógico
– PROLOG
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 2
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
3
Classificação quanto ao paradigma
Imperativo
Funcional
Lógico
Orientado a Objetos
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
4
Definição (lembrando...)
Uma LP (Linguagem de Programação) é umalinguagem destinada a ser usada por umapessoa para expressar um processo atravésdo qual um computador pode resolver umproblema. Os quatro modelos (paradigmas)de LP correspondem aos pontos de vista dosquatro componentes citados. A eficiência naconstrução e execução de programas dependeda combinação dos quatro pontos de vista.
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 3
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
5
Paradigmas
Paradigma Imperativo
As linguagens imperativas são orientadas aações, onde a computação é vista como umaseqüência de instruções que manipulamvalores de variáveis (leitura e atribuição).
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
6
Paradigma Imperativo
Programas centrados no conceito de umestado (modelado por variáveis) e ações(comandos) que manipulam o estado.
Paradigma também denominado deprocedural, por incluir subrotinas ouprocedimentos como mecanismo deestruturação.
Primeiro paradigma a surgir e ainda muitoimportante.
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 4
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
7
Paradigma Imperativo
Modelo computacional
Entrada Programa Saída
Estado
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
8
Paradigma Imperativo
Exemplos de linguagens imperativas:
FORTRAN
BASIC
COBOL
Pascal
C
Python
ALGOL
Modula
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 5
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
9
Paradigmas
Paradigma Funcional
Sistemas são construídos através da definição,composição e definição de funções.
Foco no processo de resolução do problema.A visão funcional resulta num programa quedescreve as operações que devem serefetuadas para resolver o problema.
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
10
Paradigma Funcional
Trata a programação como uma transformação dedados por funções
Que função deve ser aplicada para transformar minhaentrada na saída desejada?
Ao invés dos passos sucessivos do paradigmaimperativo, a sintaxe da linguagem é apropriada paradefinição de funções compostas que denotamaplicações sucessivas de funções:
função-n(...função-2(função-1(dados))...)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 6
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
11
Paradigma Funcional
Modelo computacional
Entrada Programa Saída
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
12
Paradigma Funcional: Características
Programas são funções que descrevem uma relaçãoexplícita e precisa entre E/S;
Estilo declarativo: não há o conceito de estado nemcomandos como atribuição;
Conceitos sofisticados como polimorfismo, funções dealta ordem e avaliação sob demanda
Aplicação: prototipação em geral e IA
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 7
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
13
Paradigma Funcional
Uma função tem três componentes básicos:– Domínio: conjunto de objetos aos quais a função se aplica)
– Contra-domínio: conjunto de objetos resultantes da aplicação dafunção, e
– Definição: especificação de como um objeto do contra-domínio édeterminado a partir do domínio.
Há um quarto componente opcional: o nome da função.
Função:
f: {domínio} {contra-domínio}
Programa:
p: {possíveis entradas} {possíveis saídas}
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
14
Paradigma Funcional
Exemplo 1: função double
Domínio: Z
Contra-Domíno: Z
Definição: x + x, onde x é elemento do domínio
Nome: double
Notação matemática: double(x) = x + x
double: integer integer
Note que o operador + é usado na definição, e + é uma função também.
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 8
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
15Paradigma Funcional – Exemplos em SCHEME
;;; Função para obtenção do dobro de x, com aplicação do valor 4
(lambda (x) (+ x x)) ==> um procedimento ((lambda (x) (+ x x)) 4) ==> 8
;;;Obtenção de x-y e aplicação com os valores 10 e 7
(define reverse-subtract (lambda (x y) (- y x))) (reverse-subtract 7 10) ==> 3
;;; procedimento Fatorial para obtenção do fatorial de um número inteiro não-
negativo
(define fact (lambda (n) (if (= n 0)
1 ;Caso básico - resulta no valor 1 (* n (fact (- n 1))))))
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
16
Paradigma Funcional
Exemplos de linguagens funcionais:
Scheme– Derivada de LISP
Common LISP– Buscando padronização de LISP
CLOS (Common LISP Object System)– Dialeto de LISP que incorpora elementos de linguagens
orientadas a objetos
ML– Linguagem funcional fortemente tipada
Miranda– Baseada em ML, mas é puramente funcional
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 9
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
17
Paradigma Funcional: Visão Crítica
Vantagens– Manipulação de
programas mais simples:
Prova de propriedades
Transformação(exemplo: otimização)
– Concorrência exploradade forma natural
Problemas– O mundo não é funcional!
– Implementaçõesineficientes
– Mecanismos primitivos deE/S e formatação
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
18
Paradigmas
Paradigma Lógico
O modelo Lógico está relacionado à perspectiva dapessoa: ele encara o problema de uma perspectivalógica. Um programa lógico é equivalente à descriçãodo problema expressa de maneira formal, similar àmaneira que o ser humano raciocinaria sobre ele.
Programação é baseada em fatos, que podem serrelações (associações) entre coisas, e regras, queproduzem fatos deduzidos a partir de outros.
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 10
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
19
Paradigma Lógico
Programação em linguagens declarativas (lógica) requer um estilomais descritivo.
O programador deve conhecer os relacionamentos entre asentidades e conceitos envolvidos para descrever os fatos(cláusulas).
Programas descrevem um conjunto de regras que disparamações quando suas premissas são satisfeitas.
Prolog foi desenvolvida em 1972 para processamento delinguagem natural, na França. O nome vem de PROgrammationen LOGique.
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
20
Paradigma Lógico
Modelo computacional
Entrada Programa Saída
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 11
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
21
Paradigma Lógico: Características
Programas são relações entre E/S
Estilo declarativo, como no paradigmafuncional
Na prática, inclui características imperativas,por questão de eficiência
Aplicações: sistemas especialistas (IA) ebanco de dados
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
22
Paradigma Lógico
Exemplos em Prolog:obrigado_a_fazer(R,A):- robô(R),
capaz_de_fazer(R,A),
perigo(B,H),
humano(H),
fazer_afasta(A,B,H),
proibido_fazer(R,A):-robô(R),
capaz_de_fazer(R,A),
machuca(A,H),
humano(H).
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 12
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
23
Paradigma Lógico
pai(antonio, claudio).
pai(antonio, ana).
pai(claudio, flavio).
pai(claudio, jean)?.
pai(jean, julia).
?pai(antonio,carlos). No
?pai(X,jean). X=claudio
avo(X,Y):-pai(X,Z),pai(Z,Y).?-avo(antonio,jean). yes
Antonio
Cláudio
Flavio
Ana
Jean
Júlia
Programas Prolog consistem em dois tipos de declaração, que são fatos e regras.
Exemplo em Prolog
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
24
Paradigma Lógico – Visão Crítica:
Vantagens– Em princípio, todas do paradigma funcional
– Permite concepção da aplicação em um alto nívelde abstração (por meio de associações entre E/S)
Problemas– Em princípio, todos do paradigma funcional
– Linguagens usualmente não possuem tipos, nemsão de alta ordem
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 13
27
/07
/20
17
Ro
gé
rio
Ed
ua
rdo
Ga
rcia
25Paradigma Lógico Visão Geral de PROLOG
Esquema de funcionamento
Representação do conhecimento para IA
Esquemas de Busca
Elementos básicos da Linguagem
Uso dual de Prolog para sistema inteligente
Como formalismo de representação doconhecimento
Como linguagem de programação
Base de Conhecimento:Fatos e Regras
Prolog
Máquina deInferência:Compilador/
InterpretadorProlog
Ask
TellRetract
Base de Conhecimento:sentenças emformalismo F
Máquina deInferência
implementandoem Prolog
raciocínio Rem formalismo F
Ask
TellRetract
Máquina deInferência:Compilador/
InterpretadorProlog
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 14
Revisão da Lógica de Horn
Para qualquer fórmula da lógica da 1a ordem, existe uma formula
logicamente equivalente em forma normal conjuntiva:p1(...,X1
i,...) ... c1(...,X1k,...) ... pn(...,Xn
j,...) ... cm(...,Xml,...)
Lógica de Horn: sub-conjunto da lógica da 1a ordem restrita aconjunções de cláusulas de Horn
Cláusula de Horn: disjunção de literais com ao máximo um literal positivo
Dividas em 3 sub-categorias:
– Fatos: cláusulas de Horn com zero literal negativo c(...,Xk,...)Em forma normal implicativa: T c(...,Xk,...)
– Regras definidas: cláusulas de Horn com exatamente um literal negativo epelo menos um literal positivo: p1(...,X1
i,...) ... pn(...,Xnj,...) cm(...,Xm
l,...)Em forma normal implicativa: p1(...,X1
i,...) ... pn(...,Xnj,...) cm(...,Xm
l,...)
– Restrições de integridade: cláusulas de Horn com zero literal positivop1(...,X1
i,...) ... pn(...,Xnj,...)
Em forma normal implicativa: p1(...,X1i,...) ... pn(...,Xn
j,...) F
Prolog como linguagem de representação do conhecimento para IA
Sentenças da base de conhecimento Prolog:
– Cláusula de Horn da 1a ordem excluindo: Restrições de integridade
Predicado de igualdade
– Apenas:
Fatos que representam o conhecimento em extensão
Regras definidas que representam o conhecimento em intenção
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 15
Representação do conhecimento simbólico
Regras
Regras + Lógica
Lógica
Regras + Procedimentos
Classes/Objetos
Classes/Objetos + Procedimentos
Classes/Objetos + Lógica
Regras + Classes/Objetos + Procedimentos
Regras + Classes/Objetos + Lógica
Procedimentos
Provadores de Teoremas
Shells de Sistemas Especialistas
Sistemas de Produção
Programação Imperativa
Programação OO
Lógicas descritivas
Programação em lógica
Sistemas de Produção OO
Programação em lógica OO
Redes Semânticas
Frames
Prolog como máquina de inferência para IA
Provador de teorema para a sub-conjunto daImplementa:
– Raciocínio dedutivo dirigido pelo objetivo
– Não monotônico quando BC inclui regras usando comnegação por falha nas premissas
Usa:– Hipótese do mundo fechado
– Hipótese da unicidade do nome
– Unificação sem occur-check
– Encadeamento de regras para trás
– Com backtracking sistemático e cronológico
– Criação da árvore de prova de cima para baixo emprofundidade primeira
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 16
Hipóteses do mundo aberto x fechado
Dado uma base de conhecimento lógica B, existemsentenças lógicas S (consultas Ask) tal que nem S,nem S é conseqüência lógica de B
Exemplo:B = {ônibusPara(garanhuns,10:00), ônibusPara(salgueiro,12:00)}
S = ônibusPara(garanhuns,12:00)
B | S e B | S
Resposta a tal consulta depende da hipótese sobre a completude da informaçãona BC feita pela máquina de inferência
Hipótese de mundo aberto (BC suposta incompleta ):– se B | S e B | S, então Ask(S) = unknown
– utilizada pela lógica clássica (de qualquer ordem) e as lógicas descritivas
Hipótese de mundo fechado (BC suposta completa ):– se B | S e B | S, então Ask(S) = False
– utilizada pela programação em lógica, os sistemas de produção eos bancos de dados
Hipótese do mundo fechado
Concluir Ask(S) = False apenas a partir de B | S não é umainferência dedutivamente correta
Epistemologicamente:
– Ask(S) = False concluído a partir de B | S,
– é mais fraco do que Ask(S) = False derivado a partir de B | S
É uma forma limitada de:
– Abdução
– Raciocínio por default
– Raciocínio não monótono
Maioria da máquinas de inferência que utilizam a hipótese domundo fechado:
– Não armazenam fatos negativos nas suas BC, i.e., não há açõesTell(S)
– Nem são capaz de deduções da forma B | S, apenas B | S
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 17
Hipótese da unicidade do nome
Consulta SQL count * from Curso no BD do ladoretorna?
– 4
Tradução em lógica clássica do conhecimentocontido na tabela:
– course(CS,101) course(CS,102) course(CS,106) course(EE,101) ?
Lógica clássica usa a hipótese do mundo aberto, mas não usa ahipótese da unicidade do nome
Então como a tradução acima não contém:– (CS = EE) (101 = 102) (101 = 106) (102 = 106)
– tradução acima não exclui que a conjunção sereduz a um único literal
Tradução correta:– c,n (c,n) course(c,n) [d,n] {[CS,101],[CS,102],[CS,106],[EE,101]}
Tabela CursoÁrea Númerocs 101cs 102cs 106ee 101
Prolog: sintaxe
Igual a lógica da 1a ordem exceto:– Constantes: começam com letras minúsculas, ou quota ´
– Variáveis:
começam com letras maiúsculas, _, ou números
na BC, todas universalmente quantificadas e de escopo local auma cláusula
nas consultas, todas existencialmente quantificadas
– Fatos da Lógica de Horn T C(...,xk,...)se escrevam c(...,Xk,...). em Prolog
– Regras definidas da Lógica de Horn:P1(...,x1
i,...) ... Pn(...,xnj,...) Cm(...,xm
l,...)se escrevam c(...,Xm
l,...) :- p1(...,X1i,...), ...,pn(...,Xn
j,...).
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 18
Exemplo de West...
West é criminoso ou não?– “A lei americana diz que é proibido vender armas a uma nação
hostil. Cuba possui alguns mísseis, e todos eles foramvendidos pelo Capitão West, que é americano”
Como resolver automaticamente este problema declassificação?
Segundo a IA (simbólica), é preciso:
– Identificar o conhecimento do domínio (modelo do problema)
– Representá-lo utilizando uma linguagem formal derepresentação
– Implementar um mecanismo de inferência para utilizar esseconhecimento
A) Todo americano que vende uma arma a uma nação hostil é criminosoB) Todo país em guerra com uma nação X é hostil a XC) Todo país inimigo político de uma nação X é hostil a XD) Todo míssil é um armaE) Toda bomba é um armaF) Cuba é uma naçãoG) USA é uma naçãoH) Cuba é inimigo político dos USAI) Irã é inimigo político dos USAco
nhec
imen
to p
révi
o
J) West é americanoK) Existe um mísseis em cubaL) Os mísseis de cuba foram vendidos por West co
nhec
imen
to
do p
robl
ema
novo
co
nhec
imen
to M) Cuba possui um míssel M1 - de KO) M1 é uma arma - de D e NP) Cuba é hostil aos USA - de F, G, H e CQ) M1 foi vendido a Cuba por West - de L, M e NR) West é crimonoso - de A, J, O, F, P e Q
Solucionando o caso do cap. West (linguagem natural)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 19
A) x,y,z americano(x) Arma(y) Nação(z) Hostil(z) Vende(x,z,y) Criminoso(x)
B) x Guerra(x,USA) Hostil(x)C) x InimigoPolítico(x,USA) Hostil(x)D) x Míssil(x) Arma(x)E) x Bomba(x) Arma(x)F) Nação(Cuba)G) Nação(USA)H) InimigoPolítico(Cuba,USA)I) InimigoPolítico(Irã,USA)co
nhec
imen
to p
révi
o
J) americano(West)K) $ x Possui(Cuba,x) Míssil(x) L) x Possui(Cuba,x) Míssil(x) Vende(West, Cuba,x) co
nhec
imen
to
do p
robl
ema
novo
co
nhec
imen
to
M) Possui(Cuba,M1) - Eliminação: quantificador existencial eN) Míssil(M1) conjunção de KO) Arma(M1) - Modus Ponens a partir de D e NP) Hostil(Cuba) - Modus Ponens a partir de C e HQ) Vende(West,Cuba,M1) - Modus Ponens a partir de L, M e NR) Criminoso(West) - Modus Ponens a partir de A, J, O, F, P e Q
Solucionando o caso do cap. West (Lógica de primeira ordem)
West é criminoso? em Prolog
Em Lógica de Horn:
americano(P) arma(W) nacao(N) hostil(N) vende(P,N,W) criminoso(P)
possui(nono,m1)
missil(m1)
possui(nono,W) missil(W) vende(west,nono,W)
missil(W) arma(W)
inimigo(N,america) hostil(N)
americano(west)
nacao(nono)
inimigo(nono,america)
nacao(america)
Em Prolog:
criminoso(P) :- americano(P), arma(W),nacao(N), hostil(N), vende(P,N,W).
possui(nono,m1).
missil(m1).
vende(west,nono,W) :- possui(nono,W),missil(W).
arma(W) :- missil(W).
hostil(N) :- inimigo(N,america).
americano(west).
nacao(nono).
inimigo(nono,america).
nacao(america).
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 20
West é criminoso? busca
criminoso(P) :- americano(P), arma(W),nacao(N), hostil(N), vende(P,N,W).
possui(nono,m1).
missil(m1).
vende(west,nono,W) :- possui(nono,W),missil(W).
arma(W) :- missil(W).
hostil(N) :- inimigo(N,america).
americano(west).
nacao(nono).
inimigo(nono,america).
nacao(america).
criminoso(west)? <- yes.–americano(west)? -> yes.
–arma(W)? <- W = m1.
missil(W)? -> W = m1.
–nacao(N)? -> N = nono.
–hostil(nono)? <- yes.
inimigo(nono,america)? -> yes.
–vende(west,nono,m1)? <- yes.
possui(nono,m1)? -> yes.
missil(m1)? -> yes.
criminoso(west)
americano(P) arma(W) nacao(N) hostil(N) vende(P,N,W)
criminoso(west)?
missil(W) possui(nono,W)
nacao(nono)
nacao(america)
possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
inimigo(N,america)
inimigo(nono,america)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 21
criminoso(west)
americano(P) arma(W) nacao(N) hostil(N) vende(P,N,W)
criminoso(west)?
missil(W) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(W) nacao(N) hostil(N) vende(west,N,W)
criminoso(west)?
missil(W) possui(nono,W)
nacao(nono)
nacao(america)
possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
inimigo(N,america)
inimigo(nono,america)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 22
criminoso(west)
americano(west) arma(W) nacao(N) hostil(N) vende(west,N,W)
criminoso(west)?
missil(W) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(W) nacao(N) hostil(N) vende(west,N,W)
criminoso(west)?
missil(W) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 23
criminoso(west)
americano(west) arma(W) nacao(N) hostil(N) vende(west,N,W)
criminoso(west)?
missil(W) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(W) nacao(N) hostil(N) vende(west,N,W)
criminoso(west)?
missil(W) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 24
criminoso(west)
americano(west) arma(W) nacao(N) hostil(N) vende(west,N,W)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,W)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 25
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 26
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 27
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
missil(m1)americano(west)
West é criminoso?Encadeamento de regras para trás
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 28
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 29
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 30
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 31
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 32
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 33
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 34
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)? yes
missil(m1) inimigo(nono,america) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
West é criminoso ? backtracking
criminoso(P) :- americano(P), arma(W),nacao(N), hostil(N), vende(P,N,W).
possui(nono,m1).
missil(m1).
vende(west,nono,W) :- possui(nono,W),missil(W).
arma(W) :- missil(W).
hostil(N) :- inimigo(N,america).
americano(west).
nacao(america).
inimigo(nono,america).
nacao(nono).
criminoso(west)? <- yes.–americano(west)? -> yes.
–arma(W)? <- W = m1.
missil(W)? -> W = m1.
–nacao(N)? -> N = america.
–hostil(america)? <- no.
inimigo(america,america)? -> no.
–backtrack: nacao(N),
N \ {america}? -> N = nono.
–hostil(nono)? <- yes.
inimigo(nono,america)? -> yes.
–vende(west,nono,m1)? <- yes.
possui(nono,m1)? -> yes.
missil(nono,m1)? -> yes.
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 35
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 36
criminoso(west)
americano(west) arma(m1) nacao(america) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(america) hostil(america) vende(west,america,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 37
criminoso(west)
americano(west) arma(m1) nacao(america) hostil(america) vende(west,america,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(america) hostil(america) vende(west,america,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 38
criminoso(west)
americano(west) arma(m1) nacao(america) hostil(america) vende(west,america,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
fail
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(america) hostil(america) vende(west,america,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
fail
backtrack
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 39
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
backtrack
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(N) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 40
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(N) vende(west,N,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
criminoso(west)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
missil(m1) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america) inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para trás
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 41
Algoritmo da máquina de inferência Prolog
Tentar unificar termo do objetivo Oi corrente com as cabeças dasclaúsulas da BC, na ordem de escritura
Seja C a 1a cabeça a se unificar com Oi via subsituição :
– se C for um fato, devolve: T e como resultado
– se C for conclusão da regra C :- P1, ..., Pn, então:
o novo objetivo corrente Oi+1 = P1
se P1 for verdade, então recursivamente tentar provar P2, ..., Pn
Se nenhuma cabeça das claúsulas da BC se unifica com Oi:
– devolver F como resultado, e
– retroceder, buscando uma prova alternativa para Oi-1, o últimoobjetivo provado antes de Oi
West é criminoso?Encadeamento de regras para frente
criminoso(P)
americano(P) arma(W) nacao(N) hostil(N) vende(P,N,W)
criminoso(west)?
missil(W) inimigo(N,america) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 42
criminoso(P)
americano(P) arma(W) nacao(N) hostil(N) vende(P,N,W)
criminoso(west)?
missil(m1) inimigo(nono,N) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
criminoso(P)
americano(P) arma(m1) nacao(N) hostil(N) vende(P,N,W)
criminoso(west)?
missil(W) inimigo(nono,N) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 43
criminoso(P)
americano(P) arma(m1) nacao(N) hostil(N) vende(P,N,W)
criminoso(west)?
missil(m1) inimigo(nono,N) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
criminoso(P)
americano(P) arma(m1) nacao(N) hostil(nono) vende(P,N,W)
criminoso(west)?
missil(W) possui(nono,W)
nacao(nono)
nacao(america)
inimigo(nono,N) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 44
criminoso(P)
americano(P) arma(m1) nacao(N) hostil(nono) vende(P,N,W)
criminoso(west)?
missil(m1) possui(nono,m1)
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,W)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
criminoso(P)
americano(P) arma(m1) nacao(N) hostil(nono) vende(P,N,W)
criminoso(west)?
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 45
criminoso(P)
americano(west) arma(m1) nacao(nono) hostil(nono) vende(west,nono,m1)
criminoso(west)?
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
criminoso(west)
arma(m1) hostil(nono)
criminoso(west)?
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 46
criminoso(west)
arma(m1) hostil(nono)
criminoso(west)? yes
nacao(nono)
nacao(america)
inimigo(nono,america) possui(nono,m1)
vende(west,nono,m1)
West é criminoso?Encadeamento de regras para frente
missil(m1)americano(west)
Encadeamento de regras para tráse resolução
Encadeamento para trás de Prolog é um caso particular derefutação por resolução para Lógica de Horn
Com estratégia de resolução SLD:
– D: para cláusulas Definidas (fatos e regras definidas)
– L: Linear de entrada , i.e., a cada passo, resolve (1) uma dasclausulas iniciais (base de conhecimento e negação da consulta) com(2) cláusula derivada no último passo
– S: com Função de seleção escolhendo:
Escolhendo cláusulas iniciais na ordem de escritura de cima para baixo
Escolhendo os literais de cada cláusula na ordem de escritura daesquerda para direta
A resolução é correta e completa para refutação
Prolog então é uma máquina de inferência correta e completapara a Lógica de Horn?
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 47
West é criminoso? Prova Prolog como refutação com resolução SLD
(americano(P) arma(W)
nacao(N) hostil(N)
vende(P,N,W) criminoso(P)) //1
(T possui(nono,m1)) //2a
(T missil(m1)) //2b
(possui(nono,W) missil(W) vende(west,nono,W)) //3
(T americano(west)) //4
(T nacao(nono)) //5
(T inimigo(nono,america)) //6
(missil(W) arma(W)) //7
(inimigo(N,america) hostil(N)) //8
(T nacao(america)) //9
(criminoso(west) F) //0
1. Resolver 0 com 1 unificando P/west:
americano(west) arma(W) nacao(N)
hostil(N) vende(west,N,W) F //10
2. Resolver 10 com 4:
arma(W) nacao(N) hostil(N)
vende(west,N,W) F //11
3. Resolver 11 com 7:
missil(W) nacao(N) hostil(N)
vende(west,N,W) F //12
4. Resolver 12 com 2b unificando W/m1:
nacao(N) hostil(N) vende(west,N,m1) F //13
5. Resolver 13 com 5 unificando N/nono:
hostil(nono) vende(west,nono,m1) F //14
6. Resolver 14 com 8 unificando N/nono:
inimigo(nono,america) vende(west,nono,m1) F //15
7. Resolver 15 com 6: vende(west,nono,m1) F //16
8. Resolver 16 com 3 unificando W/m1:
possui(nono,m1) missil(m1) F //17
9. Resolver 17 com 2a: missil(m1) F //18
10. Resolver 18 com 2b: F
Prolog devolve a primeira resposta
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).
$ prolog
?- consult(“g.pl”).
yes
?- g(U).
U = b
?- ;
U = a
?- ;
no
?- halt.
$
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 48
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 cascatas
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.
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 49
Prolog puro: sem atribuição explícita, nem predicado de igualdade
Em Prolog, = é o operador de unificação explícita:– é uma consulta lógica que retorno verdadeiro ou falso e potencialmente
instância variáveis
– não é um operador de atribuição como na programação imperativa
– não é um predicado de declaração de igualdade como na lógica dospredicados
?- banana = maca -> no.
?- prof(X,disc(Y,depto(dmc,fct)) = prof(rogerio,disc(lp,Z)).-> X = rogerio, Y = lp, Z = depto(dmc,fct).
Prolog para engenharia de software
Linguagem de especificação formal com semânticadeclarativa lógica
Linguagem de programação de propósito geral emduas camadas:1. Prolog puro: a semântica formal de cada linha do programa é
dada pela formula correspondente em lógica da 1a ordem
2. Predicados extra-lógicos: introduzidos por razões deconveniência
Funcionam com efeitos colaterais como na programaçãoimperativa
Não são bem integrados com o paradigma lógico de Prolog puro
Linguagem de scripting não tipado
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 50
Aspectos de Prolog forada Lógica Clássica de Horn da 1a ordem
Acrescentados por necessidades práticas de programação
Semântica imperativa, funcional, de lógicas não clássicas ouclássicas de ordem superior
– Negação por falha: not
– Controle e poda da busca: ! (cut), repeat, ...
– Entrada/saída: read, write, ...
– Aritmética: is, +, -, *, /, =>, <=, ...
– Modificação dinâmica da base de conhecimento: assert, retract
– Meta-programação: var, =.., name, list
Maioria das extensões de Prolog, os substituem por predicadoslógicos
No entanto, não existe padrão para essas extensões
Prolog para engenharia de software
Permite integrar duas filosofias tradicionalmenteopostas de engenharia de software:
– Métodos formais, SPIV (Specify Prove Implement Verify)
– Prototipagem rápido
Code first, think after
Extreme programming
RUDE (Run Understand Debug Edit)
– Via especificação formal executável
– Em Prolog: Implement é feito via Prove
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 51
Prolog para engenharia de software
Metáfora da programação em lógica para engenharia de software:
– Programar = apenas declarar axiomas e regras
– Execução do programa = construção de prova de teorema
– Compilador/interpretador = provador de teorema
– Estrutura de controle (única) = mecanismo de dedução automática
– Disparar execução do programa = perguntar verdade de um teorema
É um exemplo de paradigma de programação declarativa
Outros paradigmas declarativos:
– Programação funcional, ex Haskell
– Programação por resolução de restrições, ex Eclipse
– Programação por re-escritura, ex XSLT
Programador especifica apenas o que fazer
Como fazê-lo é problema do interpretador ou compilador
Programação procedimental x programação em lógica
1. Modelagem estrutural
2. Modelagem comportamental
3. Codificar estruturas de dados
4. Codificar passo a passo estruturasde controle
5. Compilar/interpretar programa
6. Executar programa
A. Declarar o que é verdade (fatos eregras)
B. Compilar/interpretar programa
C. Fazer consulta sobre verdade de umfato
Não há necessidade de 2 e 4 !
Estrutura de controle única(dedução automática) embutida nocompilador/interpretador usada paratodos os problemas !
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 52
Prolog: listas
[ e ]: início e fim de lista
, separação entre elementos
|: separação entre primeiro elemento (cabeça) 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])]
Prolog: listas - exemplo
member(X,[X|_]).
member(X,[_|Z]) :- member(X,Z).
?- member(b,[a,b,c]) -> yes.
?- member(X,[a,b,c]) -> X = a ; X = b ; X = c ; no.
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 53
Programação relacional:vários usos do mesmo predicado
Definiçaõ única:append([],L,L).
append([H|T1],L,[H|T2]) :- append(T1,L,T2).
Uso como verificador:?- append([a,b],[c],[a,b,c]). -> yes.
?- append([a,b],[c],[a]). -> no.
Uso como instanciador:?- append([a,b],[c],R). -> R = [a,b,c].
?- append(H,[c],[a,b,c]). -> H = [a,b].
Uso como resolvedor de restrições:?- append(X,Y,[a,b,c]). -> X = [], Y = [a,b,c] ; -> X = [a], Y = [b,c] ...
Uso como enumerador:?- append(X,Y,Z). -> X = [], Y =[], Z = [] ; -> X = [_], Y = [], Z = [_] ...
Implementa sozinha funcionalidades de 8 métodos imperativos!
Prolog: aritmética
3 tipos de operadores built-in aritméticos:– calculadores (n-ários infixos): +, -, *, /, mod
– comparadores (binários infixos): =:=, =\=, <, >, =<, >
– o atribuídor is: Variável is ExpressãoAritmética
Expressão aritmética:– fórmula atômica contendo apenas números e calculadores
aritméticos
– todos os argumentos dos calculadores e comparadoresdevem ser instanciados com expressões aritméticas
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 54
Prolog: exemplos de aritmética 1
> ?- 1 + 1 < 1 + 2.
yes
> ?- 1 + 3 =:= 2 + 2.
yes
> ?- 1 + 3 = 2 + 2.
no
> ?- 1 + A = B + 2.
A = 2
B = 1
> ?- 1 + A =:= B + 2.
Error
> ?- A = 2, B = 1, 1 + A =:= B + 2.
A = 2
B = 1
> ?- C = 1 + 2.
C = 1+2
> ?- C == 1 + 2.
no
> ?- C is 1 + 2.
C = 3
> ?- C is D, D = 1 + 2.
Error.
> ?- D = 1 + 2, C is D.
D=1+2
C=3
> ?- -1+2 = +(-(1),2).
no
> ?- -1+2 =:= +(-(1),2).
yes
Prolog: exemplos de aritmética
fac(0,1) :- !.
fac(I,O) :- I1 is I - 1,
fac(I1,O1), O is I * O1.
?- fac(1,X).
X = 1
?- fac(3,X).
X = 6
?- fac(5,X).
X = 120
sum([],0).
sum([H|T],N) :- sum(T,M),
N is H + M.
?- sum([2,1,3,1],S).
S = 7
?- sum([2,10,1],S).
S = 13
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 55
Evitar backtracking inútil: ! (o Cut)
Operador built-in de poda da árvore de prova
Logicamente sempre verificado
Com efeito colateral de impedir backtracking:
– na sua esquerda na cláusula que ocorre
– em outras cláusulas com a mesma conclusão
ex: A :- B, C, D.
C :- M, N, !, P, Q.
C :- R.– impede backtracking P -> N
– permite backtracking N -> M, Q -> P,
D -> (R xor Q), (P xor R) -> B
– R tentado:
unicamente se M ou N falha
nunca se P ou Q falha
Exemplo de Cut
sign(X,-1) :- X<0, !.
sign(X,0) :- X=0, !.
sign(X,1) :- X>0.
?- sign(-2,Y).
Y=-1
yes
?- sign(0,Y).
Y=0
yes
sign(-2,Y)
-2 < 0, !
!
Y=-1
yes
Y=0 Y=1
-2=0, ! -2 > 0
fail fail
Sub-árvore podada
sign(0,Y)
0 < 0, !
Y=-1 Y=0 Y=1
0=0, ! 0 > 0
fail
Sub-árvorepodada
fail !
yes
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 56
Prolog: entrada/saída 1
Ler/escrever estrutura de dados dificilmente pode servisto como resultando de uma dedução:
– E/S não se integre naturalmente no paradigma de PL
– requer predicados extra-lógicos sem semântica declarativa emL1
Predicados built-in de Prolog para E/S:– sempre verificados
– cumprem sua tarefa por efeitos colaterais
– não podem ser re-satisfeitos por backtracking
Prolog: entrada/saída 2
Ler e escrever termos: read, write, display.
Ler e escrever caracteres: get, get0, put.
Formatar a saída legívelmente: nl, tab.
Ligar um canal de E/S com a tela ou com arquivos:tell, telling, told, see, seeing, seen .
Carregar arquivo fonte no ambiente do interpretador:consult, reconsult
ex.: ?- read(X), Z is X + 1, write(Z).
2.
3
X = 2, Z = 3; no
?
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 57
Prolog para bancos de dados Datalog:
– Sub-conjunto de Prolog excluindo símbolos de funções, e assim garantedecidabilidade da inferência da 1a ordem
Estende modelo de dados relacional com visões recursivas
– Fatos datalog de um determinado predicado:
tabelas de um BD relacional
parte extensionais de um BD dedutivo
– Regras definidas datalog:
visões de um BD relacional
parte intencional de um BD dedutivo
Mais compacto (e lento) do que BD inteiramente extensionais:
– Armazena apenas fatos primitivos e freqüentemente requisitados vistoscomo axiomas lógicos
– Consulta a outros são teoremas a provar
Prolog para bancos de dados
Máquina de inferência datalog:– Estende processador de consulta com poder da dedução da 1a
ordem
– É um tamborete de dados dedutivo não persistente
– Consulta ao BD: perguntar verdade de um teorema
BD dedutivo:– Integra serviço de inferência da 1a ordem
– Com serviços tradicionais de BD: persistência, gerenciamento dememória secundária, concorrência e segurança
– Vários sistemas acadêmico
– Nenhum comercial depois de 25 anos de pesquisa
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 58
Vantagens de Prolog
Como formalismo de representaçãodo conhecimento
– Intuitividade das regras com rigorformal da lógica
– Teoria muito completa sobresemântica, corretude e completudeda inferência, limites deexpressividade, complexidade etc.
– Compiladores muito eficientes
– Versátil, serve de base para grandemaioria dos mecanismos deinferência da IA
Como linguagem deprogramação
– Declarativo com semânticaformal
– Conciso
– Eficiente
– De nível suficientemente altopara implementação rápida econcisa de máquinas deinferência
– Computacionalmente completo
– Versátil, serve como linguagemde programação, de script e dedefinição e consulta de dados
Prolog como máquina de inferência para IA
Limitações:
– Unificação sem occur-check: Torna a unificação linear no lugar de quadrática em tempo
Faz com que Prolog pode entrar em loop com algumas regras recursivas pela diretacom funções
– Busca em profundidade primeira Torna inferência econômica em memória
Faz com que Prolog pode entrar em loop com regras recursivas pela esquerda
– Juntos: Inferência sem garantia de completude nem corretude no caso geral
Balanço:
– Imperfeita mas muito eficiente em tempo e memória (competitivo com C sobrevários benchmark)
– Maiorias da imperfeições facilmente contornáveis com um pouco deexperiencia em engenharia do conhecimento em Prolog
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 59
Limitações de Prolog
Como formalismo de representaçãodo conhecimento
– Objetos compostos com restriçõescomplexas
– Raciocínio com hipótese do mundoaberto
– Conhecimento procedimental enumérico
– Tratamento da incerteza
– Atualização da base deconhecimento (Tell e Retract) comsemântica declarativa
– Especificação declarativa deestratégia de busca
Como linguagem deprogramação
– Recursos muito limitados para: Estruturação de objetos
complexos
Programação de larga escala
– Sem recursos para interfacesgráfica, programaçãoconcorrente e distribuída
– Baixa integração commetodologias e ferramentas dedesenvolvimento de largadivulgação UML, RUP, Java, XML, .net,
web services, BD O-R, etc.
Exercícios em Prolog
Digite os exemplos apresentados nestematerial e execute as consultas apresentadas
– Utilize o trace para verificar o esquema de busca
FCT-UNESP 27/07/2017
Prof. Dr. Rogério E. Garcia 60
Extensões de Prolog
PL tabelada, ex, XSB
PL tipada, ex, Mercury
PL funcional, ex, -Prolog PL de ordem superior, ex, Hilog
PL orientada a objetos, ex, F-Logic
PL multi-paradigma, ex, LIFE
PL com restrições, ex, Eclipse
PL concorrente, ex, BinProlog
PL distribuída, ex, Jinni
BD dedutivos, ex, Transaction Logic
Disciplinas:
– Paradigmas de linguagens computacionais
– Programação declarativa e banco dedados inteligentes
PL com negação explícita
PL com disjunções
PL abdutiva
PL indutiva
PL probabilista
Disciplinas:– Agentes autônomos e sistemas
multiagentes
– Engenharia do conhecimento esistemas especialistas
– Aprendizagem de máquina