Programação em Lógica
Programação em Lógica
• Programas em Lógica
• Prolog
• Técnicas de programação
Gabriel David
FEUP - Rua dos Bragas, 4099 Porto Codex - PORTUGAL
Tel. 351-2-2041842 - Fax: 351-2-2059280
Email: [email protected]
URL: http://www.fe.up.pt
1
Lógica e computadores

Lógica




linguagem precisa para a expressão dos objectivos, conhecimento e
assunções
fundamento para a dedução de consequências a partir de premissas
limitada apenas pela capacidade humana de raciocínio
Computadores



também requerem uma formulação precisa de objectivos e
assunções
dificuldades iniciais de construção  desenho da linguagem de
instrução das máquinas dominada pelo hardware
seguiram-se linguagens cada vez mais abstractas, mas
essencialmente baseadas na arquitectura de von Neumann
Prolog - 2
Paradigma

Programação em Lógica



derivada de um modelo abstracto, natural para o raciocínio
humano, independente de máquinas concretas
exprimir o conhecimento relevante e as assunções como
axiomas lógicos; formalizar o problema como uma expressão
lógica a ser provada a partir dos axiomas
Exemplo - conhecimento (dois axiomas):
1 humano(Sócrates)
2 x humano(X)  mortal(X)

problema
mortal(Sócrates)?

Sim! É uma consequência lógica dos axiomas

eliminação do universal e modus ponens
Prolog - 3
Fundamento

1965 Robinson: Princípio da Resolução


Cláusula de Horn



A se B1, B2, ..., Bn
Leitura declarativa


base matemática das provas desenvolvida no contexto dos
sistemas de demonstração de teoremas
A é verdadeiro se todos os Bi's forem verdadeiros
Conhecimento: conjunto de cláusulas de Horn
Sistema de inferência


prova construtiva de um golo a partir dos axiomas
só baseada no algoritmo da unificação e no princípio da
resolução
Prolog - 4
Origens

1970's Kowalski: leitura procedimental da
cláusula de Horn:



1970's Colmerauer (Marselha): implementação


sistema demonstrador de teoremas chamado Prolog
(Programmation en Logique)
1978/79 Edinburgo


para resolver/executar A, resolver/executar B1 e B2 e ... Bn
A é visto como a cabeça de um procedimento e os Bi's o corpo
primeiras implementações eficientes de Prolog;
estabelecimento de um estilo
1981 projecto japonês da Quinta Geração de
Computadores

construir máquinas para executar directamente Prolog
Prolog - 5
Programa em Lógica




Programa em Lógica - conjunto de axiomas ou
regras (cláusulas de Horn) que definem relações
entre objectos
Computação - dedução de consequências do
programa
Significado do programa - conjunto de
consequências definido pelo programa
Arte da Programação em Lógica - construir
programas concisos e elegantes, que tenham o
significado pretendido
Prolog - 6
Factos




relação ou predicado
objectos ou indivíduos
facto
interpretação
gosta
joao, maria
gosta( joao, maria ).
O João gosta da Maria.
Notas:
 nada se diz sobre o recíproco
 nomes de predicados e de objectos começam com minúscula
(átomos)
 predicados primeiro, objectos em lista ordenada
 ponto final
A interpretação é convencional, mas essencial para a
compreensão da formulação do problema.
Prolog - 7
Programas simples
Um conjunto de factos é um programa
situação.
Família
pai( terach, abraao ).
pai( terach, nachor ).
pai( terach, haran ).
pai( abraao, isaac ).
pai( haran, lot ).
pai( haran, milcah ).
pai( isaac, jacob ).
pai( haran, yiscah ).
mae( sara, isaac ).
descreve uma
macho( terach ).
macho( abraao ).
macho( nachor ).
macho( haran ).
macho( isaac ).
macho( lot ).
macho( jacob ).
femea( sara ).
femea( milcah ).
femea( yiscah ).
Soma
soma( 0, 0, 0 ).
soma( 0, 1, 1 ).
soma( 0, 2, 2 );
soma( 1, 0 ,1 ).
soma( 1, 1, 2 ).
Prolog - 8
Perguntas

pergunta ou golo (goal)


sintacticamente semelhante a um facto
gosta( joao, maria )? ou
?- gosta( joao, maria )
sistema responde 'yes' se existir no programa o facto
gosta( joao, maria ).
Um facto G. afirma que o golo G é verdadeiro.
Uma pergunta G? interroga se o golo é verdadeiro.
Prolog - 9
Regra de dedução 1: identidade
 Um golo é verdadeiro relativamente a um programa, se for uma
sua consequência lógica.
Regra da identidade:
de G deduzir G
 Uma pergunta é uma consequência lógica de um facto idêntico.
 Operacionalmente: procurar um facto no programa que seja
idêntico à pergunta.
programa
conclusão
pai( abraao, isaac )
pai( abraao, isaac ).
pai( haran, lot ).
…
femea( sara ).
femea(abraao)
femea( milcah ).
americano( clinton )
femea( yiscah ).
Prolog - 10
Respostas negativas
Ex: (programa da Família)
pai( abraao, isaac )?
yes
femea(abraao )?
no
americano( clinton )?
no


Resposta 'no' - significa que o golo não é consequência
lógica do programa, mas nada diz sobre a sua veracidade.
possível interpretação de 'no':
• tanto quanto sei, não, i.e,
• não consegui provar o golo com os factos de que disponho.
Prolog - 11
Programas para quê?
Realidade

Programa
A se B.
C se A.
B.
computação

Conclusões
A, B, C
Prolog - 12
Interpretação


indivíduos — constantes e termos
afirmações — factos e golos


relacionam indivíduos; são verdadeiras ou falsas
Objectivo: se a interpretação I dos factos
representados no programa for correcta, então
todas as conclusões computadas a partir do
programa correspondem, nessa interpretação, a
afirmações também verdadeiras

mesmo que não directamente observáveis - daí o carácter
inteligente destas
Prolog - 13
Variável lógica
Variável - representa um indivíduo não especificado
[não uma posição de memória].

Ex: de quem é que Abraão é pai?

fazer perguntas com os vários indivíduos até obter uma
resposta 'yes'
• pai( abraao, lot )? no
• pai( abraao, milcah )? no
• pai( abraao, isaac )? yes

ou perguntar
• pai( abraao, X )?

significando:
pergunta existencial
variáveis nas perguntas são
implicitamente existenciais
Nota: começa com maiúscula.
• existe algum indivíduo X que faça com que o golo seja uma
consequência lógica do programa?

resultado:
Uma variável resume muitas perguntas.
• X = isaac
Prolog - 14
Termos
1) Constantes e variáveis são termos
2) Termos compostos são termos:
functor + lista de argumentos
nome/aridade
termos
arv/3
arv/3
nil
3
5
R
nil
• termos base (ground)
nome( joao, costa )
nome/2
- sem variáveis
lista( a, lista( b, nil ) ) lista/2
• termos não base (nonground)
s(0)
s/1
- com variáveis
- estruturas incompletas
Termos
arv( arv(nil,3,nil), 5, R) arv/3
• são a única estrutura de dados
• interpretação de um termo é um indivíduo
• um predicado é V ou F (não confundir com termo)
Prolog - 15
Substituição
Substituição - conjunto finito de pares Xi=ti
Xi variável, ti termo,
Xi  Xj para todo o i  j e
Xi não ocorre em tj para todo i, j

Ex: q = { X = isaac } e G= pai( abraao, X )

aplicação da substituição q aos argumentos de G
Gq = pai( abraao, X )q = pai( abraao, isaac ).
instância de A, a variável X está instanciada
não existe a noção de atribuição



Prolog - 16
Exemplos de substituição

Ex: possui( joao, livro( lusiadas, autor( luis, camoes) ) ).



possui( joao, X )?
 X= livro( lusiadas, autor( luis, camoes ) )
possui( Nome, livro( Obra, autor( _, camoes ) ) )?




livro( lusiadas, autor( luis, camoes) ) é um termo cuja
interpretação dá um indivíduo, um exemplar dos Lusíadas
Quem possui alguma obra do Camões ?
Nome= joao, Obra= lusiadas
o símbolo _ é uma variável anónima e portanto não aparece
na resposta.
as respostas dadas pelo Prolog são substituições.
Prolog - 17
Regra de dedução 2: generalização
Generalização - uma pergunta existencial P é uma consequência
lógica de uma sua instância, Pq, para qualquer substituição q.


de pai( abraao, isaac ) concluir pai( abraao, X ), pois existe
um X (X= isaac) que torna este verdadeiro
operacionalmente, para responder a uma pergunta existencial
com variáveis, procurar um facto que seja uma instância dessa
pergunta; a resposta é essa instância, representada pela
substituição respectiva
conclusão
pai( abraao, X )
programa
pai( abraao, isaac ).
X= isaac
Prolog - 18
Soluções múltiplas

Podem existir soluções múltiplas: quais as
soluções de soma( A, B, 4 )?



{A=0, B=4}, {A=1, B=3}, {A=2, B=2},
{A=3, B=1}, {A=4, B=0}
Quais as soluções de soma( A, A, 4 )?


a substituição de A na pergunta é feita só de uma vez,
pelo que o significado é
qual o número que somado consigo próprio dá 4?,
{A=2}
Prolog - 19
Regra de dedução 3: instanciação
Instanciação - de um facto universalmente quantificado P, deduzir uma
sua instância Pq, para qualquer substituição q.

Suponha-se que todos os elementos da Família
gostam de maná.




Em vez disto, pode-se usar um facto universal.



gosta( abraao, mana ).
gosta( terach, mana ).
•••
gosta( X, mana ).
A variável resume muitos factos.
As variáveis nos factos estão universalmente
quantificadas.
Prolog - 20
Exemplos de instanciação

Operacionalmente:


pergunta sem variáveis — encontrar um facto de que a pergunta
seja instância
Ex: incluir o facto soma( 0, X, X ) no programa significa que o
0 é o elemento neutro da adição.
programa
gosta( X, mana).
conclusão
gosta( abraao, mana )
Prolog - 21
Combinação de regras

Operacionalmente:


pergunta com variáveis — procurar uma instância comum à
pergunta e ao facto, o que envolve dois passos: instanciação (do
facto para a instância) e generalização (da instância para a
pergunta)
Ex: soma( 0, 3, Y ), a partir do facto soma( 0, X, X ) e da
instância comum soma( 0, 3, 3), responde {Y=3} (substituições
sem variáveis da pergunta, não aparecem na resposta)
programa
soma( 0, 3, Y ).
conclusão
soma( 0, 3, Y )
instância
comum
Y= 3
soma( 0, 3, 3 )
Prolog - 22
Perguntas conjuntivas

pergunta conjuntiva é aquela que possui mais do
que um golo
• pai( abraao, isaac ), mae( sara, isaac )?



vírgula = conjunção
resposta a perguntas sem variáveis é a conjunção das respostas
a cada golo
perguntas com variáveis partilhadas por vários
golos
• pai( haran, X ), macho (X )?
• Haran tem algum filho homem?


o alcance da variável é a pergunta conjuntiva
também estas variáveis são existenciais
Prolog - 23
Variáveis partilhadas

operacionalmente, para resolver A1, A2, ..., An?
encontrar uma substituição q tal que A1 q, A2 q, ...
An q sejam instâncias sem variáveis de factos no
programa.


solução: {X=lot}
Uso: restrição — dentre os filhos de Haran
escolher só os machos
• Ex: pai( terach, X), pai( X, Y )?

- escolhe os filhos de Terach que por sua vez têm filhos, i.e.,
netos
Prolog - 24
Regras
Regra - define uma nova relação em termos das relações existentes.

dá um nome a uma pergunta conjuntiva;
transforma-a numa pergunta simples
• avo( X, Y )  pai( X, Z ), pai( Z, Y ),

forma geral das cláusulas de Horn
•
(cabeça)
(corpo)
–
facto
A
–
regra
A  B1, B2, ... Bn
– pergunta
B

leitura procedimental




a pergunta
é traduzida por
e reduzida a
para concluir
 avo( terach, Y )
 pai( terach, Z ), pai( Z, Y )
 pai( haran, Y )
{Z=haran}
 { Z=haran, Y=lot}
Prolog - 25
Leitura declarativa
• avo( X, Y )  pai( X, Z ), pai( Z, Y ),

regra vista como um axioma lógico




 denota implicação lógica
lê-se: para todo o X, Y e Z, X é avô de Y se X for o pai de Z e Z
o pai de Y
as variáveis nas regras (caso particular: factos) são
quantificadas universalmente
leitura alternativa: para todo o X e Y, X é avô de Y se existir um
Z tal que X seja o pai de Z e Z o pai de Y
Prolog - 26
Equivalências
• avo( X, Y )  pai( X, Z ), pai( Z, Y ),

justificação da segunda leitura

equivalências: a  b  a  ~b; X, p(X)  ~x: ~p(X)

X Y Z avo( X, Y)  pai( X, Z ), pai( Z, Y )
X Y Z avo( X, Y)  ~[ pai( X, Z ), pai( Z, Y )]
X Y avo( X, Y)  Z ~[ pai( X, Z ), pai( Z, Y )]
X Y avo( X, Y)  ~Z: [ pai( X, Z ), pai( Z, Y )]
X Y avo( X, Y)  Z: [ pai( X, Z ), pai( Z, Y )]
só as variáveis dos golos da pergunta interessam para a
expressão da substituição






variáveis nas perguntas (cláusulas só com corpo)
são portanto existenciais
Prolog - 27
Regra de dedução 4: modus ponens

Lei do modus ponens universal trata das deduções
via regras

diz que da regra
• R= (A  B1, B2, ..., Bn)

e dos factos
• B'1. B'2. .... B'n.



se pode deduzir A' se A'  B'1, B'2, ..., B'n for uma instância
de R.
[identidade e instanciação são casos particulares]
Um programa em lógica é um conjunto finito de
regras.
Prolog - 28
Consequência lógica

Um golo quantificado existencialmente G é uma
consequência lógica de um programa P, se existir
uma cláusula em P com uma instância sem
variáveis
A  B1, B2, ..., Bn, n0,
tal que B1, B2, ..., Bn sejam consequências lógicas
de P e A uma instância de G.

responder a perguntas é aplicar (redução) o modus ponens da
frente para trás o número de vezes necessário para ir do golo
até aos factos
a) escolhendo uma instância do golo e
b) uma regra para aplicar, recursivamente.
Prolog - 29
Procedimentos
Procedimento - colecção de regras com o mesmo predicado na cabeça.

para obter todos os netos — acrescentar definições
em falta ao procedimento do predicado avo/2.
•
•
•
•

avo( X, Y )  pai( X, Z ), pai( Z, Y ),
avo( X, Y )  pai( X, Z ), mae( Z, Y ),
avo( X, Y )  mae( X, Z ), pai( Z, Y ),
avo( X, Y )  mae( X, Z ), mae( Z, Y ),
outra representação, mais compacta
 progenitor( X, Y )  pai( X, Y ),
 progenitor( X, Y )  mae( X, Y ),
 avo( X, Y )  progenitor( X, Z ), progenitor( Z, Y ),

progenitor/2 tem duas alternativas — é uma forma de
representar disjunção
Prolog - 30
Traço de uma execução
avo( X, jacob )

progenitor( X, Z ), progenitor( Z, jacob ) 
progenitor( X, Z ), pai( Z, jacob)
progenitor( X, isaac )
mae( X, isaac )


{Z= isaac }
{Z= isaac }
{Z= isaac, X= sara}
resolvente - pergunta conjuntiva com os golos ainda a processar
traço - evolução da computação, com a indicação de
a) golo seleccionado
b) regra escolhida para a redução
c) substituição associada
 - resolvente vazia (= true)
Prolog - 31
Outro traço de execução
avo( X, jacob )
progenitor( X, Z ), progenitor( Z, jacob )


pai( X, Z ), progenitor( Z, jacob )
progenitor( isaac, jacob )
pai( isaac, jacob )
 { X=abraao, Z= isaac }
{ X=abraao, Z= isaac }
{ X=abraao, Z= isaac}
Prolog - 32
Unificação




um termo T é uma instância comum de T1 e T2 se existirem
substituições q1 e q2 tais que T=T1q1 e T=T2q2
um termo S é mais geral do que um termo T, se T for uma
instância de S e S não for uma instância de T
um termo S é uma variante de um termo T se se puderem
converter um no outro por simples renomeação de variáveis
um unificador de dois termos é uma substituição que torna os
dois termos iguais
livro( Titulo, autor( Proprio, camoes), data(1585, Mes, Dia)) )
livro( lusiadas, autor( luis, Apelido), Ano )
q = {Titulo=lusiadas, Proprio=luis, Apelido=camoes,
Ano= data(1585, Mes, Dia)}
Prolog - 33
Algoritmo de unificação

o algoritmo de unificação produz o unificador ou
reporta falha



baseia-se na comparação de functores e na tentativa de unificar
os respectivos argumentos, propagando cada substituição a
todas as ocorrências de variáveis
o resultado é o unificador mais geral possível (a respectiva
instância é a mais geral de todas as instâncias)
verificação de ocorrência - para unificar uma variável S com
um termo T, T não pode conter S [não há unificador mais geral
para X e s(X)]
Prolog - 34
Interpretador abstracto
Entrada
Saída
Algoritmo


programa P
golo G
Gq, se existir, ou falha
inicializar a resolvente para ser o golo G
enquanto a resolvente não estiver vazia fazer
• escolher um golo A da resolvente e uma cláusula (renomeada)
A'  B1, B2, ..., Bn n0
em P tal que A e A' unifiquem com unificador q
(sair do ciclo se não existirem tais golo e cláusula)
• remover A da resolvente e adicionar-lhe B1, B2, ..., Bn
• aplicar q à resolvente e a G

se a resolvente estiver vazia devolver G, se não reportar falha
Prolog - 35
Bases de dados



conjunto de factos = base de dados (BD extensional)
regras = vistas (BD intencional)
predicado só com factos = relação
pai( Pai, Filho ), mae( Mae, Filho ), macho( Pessoa ),
femea( Pessoa ) [esquemas]
definição de vistas
progenitor( P, Filho )  pai (P, Filho ).
progenitor( P, Filho )  mae( P, Filho ).
irmao( X, Y ) 
progenitor( P, X ), progenitor( P, Y ), macho( X ), X \= Y.
tio( Tio, Sob )  irmao( Tio, P ), progenitor( P, Sob ).
antepassado( A, X )  progenitor( A, X ).
antepassado( A, X )  progenitor( A, Y ), antepassado( Y, X ).
Prolog - 36
PL vs BD relacionais


programação em lógica — extensão ao modelo
relacional, fornece uma linguagem integrada de
acesso aos dados, e de programação de aplicações
operações básicas


reunião
r_uniao_s( X1, ..., Xn )  r( X1, ..., Xn )
r_uniao_s( X1, ..., Xn )  s( X1, ..., Xn )
diferença
• requer um predicado de negação
r_menos_s( X1, ..., Xn )  r( X1, ..., Xn ), not s( X1, ..., Xn )
é verdadeiro relativamente a um programa P
se G não for uma consequência lógica de P
not G
Prolog - 37
Operações da álgebra relacional

produto cartesiano
r_vezes_s( X1, ..., Xm, Xm+1, ..., Xm+n )
 r( X1, ..., Xm ), s( Xm+1, ..., Xm+n )

projecção
r13( X1, X3 )  r( X1, X2, X3 )

selecção
r1( X1, X2, X3 )  r( X1, X2, X3 ), X2 > X3

operações derivadas


intersecção
r_inter_s( X1, ..., Xn )  r( X1, ..., Xn ), s( X1, ..., Xn )
junção natural
r_join_y( X1, X2, X3 )  r( X1, X2 ), s( X2, X3 )
Prolog - 38
Estilo de programação

dois estilos
1) exprimir a informação à custa de relações entre indivíduos
atómicos
2) codificar informação em termos, indivíduos complexos e
manipular estruturas

arte: encontrar o adequado nível de abstracção


esconder os detalhes da representação — independência dos
dados
evidenciar associações entre indivíduos, evitando redundâncias
— normalização
Prolog - 39
Representação de informação



Representar o facto de o João possuir um exemplar dos
Lusíadas de Luís de Camões, editado em 1940.
Codificação em termos complexos, com poucos predicados

possui( joao, livro( lusiadas, autor( luis, camoes), 1940 ) ).

Quem possui livros editados em 1940?
?- possui( X, livro( _, _, 1940 ) ).
Codificação baseada em predicados, com termos simples

escritor( 1, luis, camoes).
livro( 427, lusiadas, 1940 ).
autor( 1, 427).
pessoa(1002, joao ).
possui( 1002, 427 ).
?- possui( CodP, CodL), pessoa( CodP, X ), livro(CodL, _, 1940).
Prolog - 40
Tipos


não existe noção independente de tipo; existem
predicados que definem implicitamente tipos
tipo — conjunto de termos



definição de tipo — (muitas vezes) predicado unário
tipo macho definido como o conjunto dos termos X tais que
macho(X) é verdade
tipos recursivos simples — definidos por programas em lógica
unários recursivos
• inteiros, listas, árvores binárias

inteiros: predicado de tipo

% natural( X )  X é um número natural
% sn(0) denota n
natural( 0 ).
natural( s(X) )  natural( X ).
s(X) representa o sucessor de X
Prolog - 41
Aritmética

relação de ordem
% X  Y  se X e Y são números naturais e X  Y (notação infixa de ''( X, Y ) )
0  X  natural( X ).
s(X)  s(Y)  X  Y

traço de um golo:
s(s(0))  s(0)
s(0)  0
• este golo não tem redução porque não unifica com nenhuma
cabeça de cláusula — o traço falha ( para suceder teria que
terminar em )
Prolog - 42
Adição

operação de adição como relação ternária
% soma( X, Y, Z )  se X, Y e Z são números naturais e Z
é a soma de X e Y
soma( 0, X, X )  natural( X ).
soma( s(X), Y, s(Z) )  soma( X, Y, Z ).

definição de tipo recursivo permite forma
compacta para a adição, em vez da explícita
Prolog - 43
Múltiplos usos

uso funcional
soma( s(s(0)), s(0), X )
soma( s(0), s(0), Z1 ) { X = s( Z1) }
soma( 0, s(0), Z2 )
{ Z1 = s(Z2), X = s(s(Z2)) }

{ Z2 = s(0), Z1 = s(s(0)), X = s(s(s(0))) }
 note como se constrói um termo para devolver em X, à custa de o
manter aberto com uma variável e da unificação que causa
instanciação parcial

uso invertido
soma( s(0), Y, s(s(s(0)))
soma( 0, Y, s(s(0)) )

{ Y= s(s(0)) }
 note como se define o resultado e se pergunta as parcelas
Prolog - 44
Várias soluções

Traço com soluções múltiplas
soma( X, Y, s(s(s(0))) )

;
soma( X, Y, s(s(s(0))) )
soma( X1, Y, s(s(0)) )

{ X= 0, Y= s(s(s(0))) }
{ X= s(X1) }
{ X1= 0, Y= s(s(0)) }
etc.
;
{no}

pede-se uma nova solução com um sinal “;”
Prolog - 45
Significado
Significado de um programa P, M(P), é o conjunto dos
golos completamente instanciados dedutíveis de P.

esquema da relação/predicado descreve o
significado pretendido M, também definido em
termos de golos na relação

relativamente ao significado pretendido
• programa correcto M(P)  M
• programa completo M  M(P)

objectivo: programas correctos e completos ou, pelo menos,
correctos
Prolog - 46
Listas
Lista — estrutura de dados binária em que o 1º
argumento é um elemento e o 2º recursivamente o
resto da lista; a base da recursão é a lista vazia []
Representações
formal
par
elementos
•(a, •(b, []) )
•
a
•
[a | [b | []] ]
[a, b]
b
[]
.(a,[])
b []
.(a, .(b, .(c, [])))
.(a, X)
.(a, .(b, X))
cabeça
cauda
[a|[]]
[a|[b|[c | []]
[a|X]
[a | [b | X] ]
[a]
[a, b, c]
[a|X]
[a,b| X]
Prolog - 47
Manipulação de listas
 definição de tipo
% lista( Xs )  Xs é uma lista
lista( [] ).
lista( [1,2,3] )  lista( [2,3] )
R: { X= 1, Xs=[2,3] }
lista([X | Xs] )  lista( Xs ).
 membro de uma lista
% member( X, Xs )  X é um elemento
da lista Xs
omite-se
member( X, [X|Xs] )  lista( Xs ).
member(X, [Z| Xs] )  member( X, Xs ).
•
nomes das variáveis são
arbitrários e locais às regras
•
mas convém ter uma disciplina
member(b, [a,b,c]).
R: yes
member(X, [a,b,c] )
R: { X= a } ou {X=b} ou {X = c}
member(b, Xs)
R: { Xs= [b]} ou {Xs = [X, b|Z]}
Prolog - 48
Predicados sobre listas

Comprimento de uma lista
% comp( Xs, N )  a lista Xs tem N elementos
comp( [], 0 ).
comp( [X| Xs], s(N) )  comp(Xs, N ).

Prefixo e sufixo de uma lista
% prefixo(Ps, Xs )  Ps é uma sublista
consecutiva no início da lista Xs
prefixo( [], Xs ) .
prefixo( [X|Xs], [X| Ys] )  prefixo( Xs, Ys ).
sufixo( Xs, Xs ) .
sufixo( Xs, [Y| Ys] )  sufixo( Xs, Ys ).
Prolog - 49
Concatenação
% append( Xs, Ys, Zs )  se Zs for o resultado da concatenacao de Xs e Ys
append( [], Ys, Ys ).
append( [X|Xs], Ys, [X|Zs] )  append( Xs, Ys, Zs ).
 programa semelhante em estrutura ao da soma de
inteiros, mas assimétrico no primeiro argumento:
append( [a,b], [c,d], Zs )
append( Xs, [c,d], [a,b,c,d] )
append( [b], [c,d], Zs1 )
{ Zs= [a|Zs1] }
append( Xs1, [c,d], [b,c,d] )
{ Xs= [a|Xs1] }
append( [], [c,d], Zs2 )
{ Zs1= [b|Zs2] }
append( Xs2, [c,d], [c,d] )
{ Xs1= [b|Xs2] }

{ Zs2= [c,d] }

{ Xs2= [ ] }
R: Zs = [a,b,c,d]

R: Xs = [a,b]
partição de uma lista
• append( Xs, Ys, [a,b,c,d] )

tem múltiplas soluções e aplicações variadas
• member( X, Xs )  append( As, [X|Ys], Xs )
Prolog - 50
Aplicações da concatenação

Sublistas
% sublista( Sub, Lista )  Sub é uma sublista de Lista
% prefixo de sufixo
sublista( Sub, Lista )  prefixo( Sub, Xs ), sufixo( Xs, Lista ).
% ou
sublista(Xs, AsXsBs ) 
append( As, XsBs, AsXsBs ), append( Xs, Bs, XsBs ).

Inverter uma lista
% inverte( Lista, Inv )  Inv é o resultado de inverter Lista
% algoritmo ingénuo
inverte( [], [] ).
inverte( [X| Xs], Zs )  inverte( Xs, Ys ), append( Ys, [X], Zs ).
Prolog - 51
Árvore de prova


Árvore de prova — os nós são os golos reduzidos durante a
computação; a raiz é o golo da pergunta; há arcos de cada nó para todos
os nós obtidos daquele por um passo de redução.
Objectivo: mais declarativa do que o traço, mostrar as razões da dedução.
inverte( [b,c,d], [d,c,b] )
inverte( [c,d], [d,c] )
append([d,c], [b], [d,c,b] )
inverte( [d], [d] ) append([d], [c], [d,c] )
inverte( [], [] )
append([c], [b], [c,b] )
append([], [d], [d] ) append([], [c], [c] ) append([], [b], [b] )
Dimensão da árvore de prova quadrática no número de elementos da lista a inverter.
Prolog - 52
Evitar a concatenação
Inverter sem concatenação (tentativa)
% inverte( Lista, Inv )  Inv é o resultado de inverter Lista
% algoritmo sem append
inverte( [X| Xs], Acc )  inverte( Xs, [X|Acc] ).
inverte( [], Acc ).
•
traço
inverte( [b,c,d],[] )
inverte( [c,d], [b] )
inverte( [d], [c,b] )
inverte( [], [d,c,b] )


inverteu, mas ... e o resultado?
Prolog - 53
Acumuladores

Inverter sem concatenação usando acumulador para extrair o
resultado (por unificação no último passo)
% inverte( Lista, Inv )  Inv é o resultado de inverter Lista
% algoritmo com acumulador (argumento suplementar)
inverte( Xs, Ys )  inverte( Xs, [], Ys ).
inverte( [X| Xs], Acc, Ys )  inverte( Xs, [X|Acc], Ys ).
inverte( [], Ys, Ys ).
•
traço
inverte( [b,c,d],Ys )
inverte( [b,c,d],[], Ys )
inverte( [c,d], [b], Ys )
inverte( [d], [c,b], Ys )
inverte( [], [d,c,b], Ys )


{ Ys= [d,c,b] }
este traço corresponde a uma árvore de tamanho linear no número
de elementos da lista
Prolog - 54
Filtro
% apaga( Lista, X, SemXs )  a lista SemXs é Lista com todos os X
removidos
apaga( [X| Xs], X, Ys )  apaga( Xs, X, Ys ).
apaga( [X| Xs], Z, [X|Ys] )  XZ, apaga( Xs, Z, Ys ).
apaga( [], X, [] ).

A condição XZ na segunda regra é essencial para obter resultados
correctos
Prolog - 55
Ordenação
% quicksort( Xs, Ys )  a lista Ys é uma permutação ordenada de Xs
quicksort( [X| Xs], Ys ) 
particao( Xs, X, Pequenos, Grandes ),
quicksort( Pequenos, Ps),
quicksort( Grandes, Gs ),
append( Ps, [X| Gs], Ys ).
quicksort( [], [] ).
particao( [X| Xs ], Y, [X| Ls], Bs )  X  Y, particao( Xs, Y, Ls, Bs ).
particao( [X| Xs ], Y, Ls, [X| Bs] )  X > Y, particao( Xs, Y, Ls, Bs ).
particao( [], Y, [], [] ).
Prolog - 56
Árvores

Árvore - estrutura duplamente recursiva
% arvore(Arv )  Arv é uma árvore
arvore( void).
arvore( arv(Elem, Esq, Dir) )  arvore( Esq ), arvore( Dir ).
% membro_arv( E, A )  E é um elemento da árvore binária A
membro_arv( X, arv(X,E,D) ).
membro_arv( X, arv(Z,E,D) )  membro_arv(X, E ).
membro_arv( X, arv(Z,E,D) )  membro_arv(X, D ).
% isomorfa(Arv1, Arv2 )  Arv1 e Arv2 são isomorfas
isomorfa( void, void ).
isomorfa( arv(X,Esq1,Dir1), arv(X,Esq2,Dir2) )  isomorfa( Esq1, Esq2),
isomorfa(Dir1, Dir2 ).
isomorfa( arv(X,Esq1,Dir1), arv(X,Esq2,Dir2) )  isomorfa( Esq1, Dir2),
isomorfa(Dir1, Esq2 ).
% pre_ordem( Arv, Pre )  Pre é uma travessia em preordem da árvore Arv
pre_ordem( arv(X,E,D), Pre )  pre_ordem( E, Es ), pre_ordem( D, Ds ),
append( [X| Es], Ds, Pre ).
pre_ordem( void, [] ).
Prolog - 57
Árvore de pesquisa

Árvore de pesquisa de um golo G relativamente a
um programa P

raiz da árvore: G

nós: resolventes, com um golo seleccionado

arcos a sair de um nó: um por cada cláusula de P cuja cabeça
unifica com o golo seleccionado no nó

cada caminho na árvore, desde a raiz: computação de G por P

folhas: nós de sucesso, se corresponderem a resolventes vazias;
nós de falha se o golo selecionado não puder ser reduzido
Prolog - 58
Árvore de pesquisa do Jacob
avo( X, jacob )
progenitor( X, Z ), progenitor( Z, jacob )
progenitor( X, Z ), pai( Z, jacob)
progenitor( X, Z ), mae( Z, jacob)
{Z= isaac }
progenitor( X, isaac )
pai( X, isaac )
mae( X, isaac )
{X= abraao}

sucesso
X=abraao, Z=isaac
falha
{X= sara}

sucesso
X=sara, Z=isaac
Prolog - 59
Outra árvore de pesquisa
avo( X, jacob )
progenitor( X, Z ), progenitor( Z, jacob )
pai( X, Z ), progenitor( Z, jacob)
pai( X, Z ), pai( Z, jacob)
mae( X, Z ), pai( Z, jacob)
pai( X, Z ), mae( Z, jacob )
{Z= isaac}
pai( X, isaac )
{X= abraao}

sucesso
X=abraao, Z=isaac
mae( X, Z ), progenitor( Z, jacob)
falha
pai( X, Z ), mae( Z, jacob )
{Z= isaac}
mae( X, isaac )
falha
{X= sara}

sucesso
X=sara, Z=isaac
Prolog - 60
Características destas árvores




árvore de pesquisa: independente do critério de
selecção de cláusulas (tem todas as alternativas)
podem existir várias árvores de pesquisa diferentes
para o mesmo golo e o mesmo programa,
conforme o critério de selecção dos golos
conclusão principal: o número de nós de sucesso é
o mesmo em todas elas
uma árvore de pesquisa resume todas as respostas;
chama-se de pesquisa porque um interpretador
concreto terá que ter uma estratégia para percorrer
a árvore em busca de soluções (pesquisa em
profundidade, em largura, em paralelo, ...)
Prolog - 61
Computações infinitas
append( Xs, [c,d], Ys)
{Xs= [X|Xs1], Ys= [X|Ys1]}
append( Xs1, [c,d], Ys1)
{Xs1= [X1|Xs2], Ys1= [X1|Ys2]}
append( Xs2, [c,d], Ys2)
{Xs2= [X2|Xs3], Ys2= [X2|Ys3]}
{Xs= [], Ys= [c,d]}

{Xs1= [], Ys1= [c,d]}

{Xs2= [], Ys2= [c,d]}

°
°
°
°
°
ramos infinitos na árvore° correspondem a computações
sem fim
uma pesquisa em profundidade pode perder-se num ramo infinito
avaliar a complexidade de uma pergunta: (interpretadores que
pesquisem sequencialmente toda a árvore) melhor analisar o
número de nós da árvore de pesquisa do que da árvore de prova
(esta inclui não determinismo)
append( Xs3, [c,d], Ys3)



Prolog - 62
Negação por falha






os programas em lógica descrevem o que é verdade; o falso é omitido
certas relações são mais fáceis de especificar com a negação
disjunto( Xs, Ys )  not ( member( X, Xs ), member( X, Ys ) )
para obter conclusões negativas: assunção do mundo fechado
 not G é uma consequência do programa P se G não for uma
consequência de P (mesmo que G dê ramo infinito)
árvore de pesquisa finitamente falhada: não contém nós de sucesso nem
ramos infinitos
conjunto de falha finita do programa P: conjunto dos golos que têm uma
árvore finitamente falhada relativamente a P
árvore finitamente falhada:
progenitor( isaac, X )
pai( isaac, X )
mae(isaac, X)
falha
falha
Dedução usando negação por falha: not G é uma consequência de P se
G estiver no conjunto de falha finita de P
Prolog - 63