Upload
fabio-moura-pereira
View
244
Download
2
Embed Size (px)
Citation preview
Programação em Lógica Programação em Lógica MatemáticaMatemática
PrologProlog– 04 –– 04 –
Inteligência ArtificialInteligência ArtificialFábio M. PereiraFábio M. Pereira
Baseado emBaseado emAmzi! inc. – www.amzi.comAmzi! inc. – www.amzi.com
PrologProlog►RegrasRegras►Como Regras FuncionamComo Regras Funcionam►Usando RegrasUsando Regras►ExercíciosExercícios
RegrasRegras►Um predicado é definido por cláusulas, Um predicado é definido por cláusulas,
que podem ser fatos ou regrasque podem ser fatos ou regras►Uma regra não é nada mais que uma Uma regra não é nada mais que uma
consulta armazenadaconsulta armazenada►A sua sintaxe éA sua sintaxe é
cabeça :- corpo.cabeça :- corpo. cabeçacabeça – uma definição do predicado (da – uma definição do predicado (da
mesma forma como um fatomesma forma como um fato :-:- – o símbolo de – o símbolo de pescoçopescoço, as vezes lido , as vezes lido
como “se”como “se” corpocorpo – um ou mais objetivos (uma consulta) – um ou mais objetivos (uma consulta)
Exemplo (1)Exemplo (1)► Uma consulta que encontra onde as coisas Uma consulta que encontra onde as coisas
comestíveis estão pode ser armazenada como comestíveis estão pode ser armazenada como uma regra com o predicado de nome uma regra com o predicado de nome local_comida/2local_comida/2local_comida(X,Y) :- local(X,Y), comestivel(X).local_comida(X,Y) :- local(X,Y), comestivel(X). Existe algum X para comer na sala Y se X está Existe algum X para comer na sala Y se X está
localizado em Y e X é comestívellocalizado em Y e X é comestível► Utilizando ...Utilizando ...
?- ?- local_comida(X, cozinha).local_comida(X, cozinha).X = maçã ;X = maçã ;X = biscoito ;X = biscoito ;NoNo
?- ?- local_comida(Comida, ‘sala de jantar’).local_comida(Comida, ‘sala de jantar’).NoNo
Exemplo (2)Exemplo (2)► Podemos checar por coisas específicasPodemos checar por coisas específicas
?- ?- local_comida(maçã, cozinha).local_comida(maçã, cozinha).YesYes
►Ou podemos listar tudoOu podemos listar tudo?- ?- local_comida(Comida, Sala).local_comida(Comida, Sala).Comida = maçãComida = maçãSala = cozinha ;Sala = cozinha ;
Comida = biscoitoComida = biscoitoSala = cozinha ;Sala = cozinha ;
NoNo
Múltiplas CláusulasMúltiplas Cláusulas►Da mesma forma que podemos ter múltiplos Da mesma forma que podemos ter múltiplos
fatos definindo um predicado, também fatos definindo um predicado, também podemos ter múltiplas regraspodemos ter múltiplas regras
► Se quisermos o Se quisermos o brócolisbrócolis incluído em incluído em local_comida/2local_comida/2local_comida(X,Y) :- local(X,Y), comestivel(X).local_comida(X,Y) :- local(X,Y), comestivel(X).local_comida(X,Y) :- local(X,Y), gosto_ruim(X).local_comida(X,Y) :- local(X,Y), gosto_ruim(X).
► Agora ...Agora ...?- ?- local_comida(X, cozinha).local_comida(X, cozinha).X = maçã ;X = maçã ;X = biscoito ;X = biscoito ;X = brócolis ;X = brócolis ;NoNo
Como Regras FuncionamComo Regras Funcionam► Com regras, Prolog unifica o objetivo padrão Com regras, Prolog unifica o objetivo padrão
com a cabeça da cláusulacom a cabeça da cláusula► Se a unificação é bem sucedida, então Prolog Se a unificação é bem sucedida, então Prolog
inicia uma nova consulta usando os objetivos inicia uma nova consulta usando os objetivos do corpo da cláusulado corpo da cláusula
► Regras, em seu efeito, levam a múltiplos Regras, em seu efeito, levam a múltiplos níveis de consultasníveis de consultas O primeiro nível é composto do objetivo originalO primeiro nível é composto do objetivo original O próximo nível é uma nova consulta composta de O próximo nível é uma nova consulta composta de
objetivos encontrados no corpo da cláusula do objetivos encontrados no corpo da cláusula do primeiro nívelprimeiro nível
Cada nível pode criar níveis mais profundosCada nível pode criar níveis mais profundos Teoricamente, isto pode continuar Teoricamente, isto pode continuar
indefinidamente, na prática, continua até o limite indefinidamente, na prática, continua até o limite de memória disponívelde memória disponível
Controle de Fluxo com RegrasControle de Fluxo com Regras
►Note como o backtracking a partir do Note como o backtracking a partir do segundo objetivo do primeiro nível agora leva segundo objetivo do primeiro nível agora leva ao segundo nívelao segundo nível
►Neste exemplo, o objetivo central do primeiro Neste exemplo, o objetivo central do primeiro nível é bem sucedido ou falha se o seu corpo nível é bem sucedido ou falha se o seu corpo é bem sucedido ou falhaé bem sucedido ou falha
[debug] ?- local_comida(Comida,cozinha). Call: (7) local_comida(_G286, cozinha) ? creep Call: (8) local(_G286, cozinha) ? creep Exit: (8) local(maçã, cozinha) ? creep Call: (8) comestivel(maçã) ? creep Exit: (8) comestivel(maçã) ? creep Exit: (7) local_comida(maçã, cozinha) ? creep
Comida = maçã ;
Fail: (8) comestivel(maçã) ? creep Redo: (8) local(_G286, cozinha) ? creep Exit: (8) local(brócolis, cozinha) ? creep Call: (8) comestivel(brócolis) ? creep Fail: (8) comestivel(brócolis) ? creep Redo: (8) local(_G286, cozinha) ? creep Exit: (8) local(biscoito, cozinha) ? creep Call: (8) comestivel(biscoito) ? creep Exit: (8) comestivel(biscoito) ? creep Exit: (7) local_comida(biscoito, cozinha) ? creep
Comida = biscoito ;
Fail: (8) comestivel(biscoito) ? creep Redo: (8) local(_G286, cozinha) ? creep Fail: (8) local(_G286, cozinha) ? creep Redo: (7) local_comida(_G286, cozinha) ? creep Call: (8) local(_G286, cozinha) ? creep Exit: (8) local(maçã, cozinha) ? creep Call: (8) gosto_ruim(maçã) ? creep Fail: (8) gosto_ruim(maçã) ? creep Redo: (8) local(_G286, cozinha) ? creep Exit: (8) local(brócolis, cozinha) ? creep Call: (8) gosto_ruim(brócolis) ? creep Exit: (8) gosto_ruim(brócolis) ? creep Exit: (7) local_comida(brócolis, cozinha) ? creep
Comida = brócolis ;
Fail: (8) gosto_ruim(brócolis) ? creep Redo: (8) local(_G286, cozinha) ? creep Exit: (8) local(biscoito, cozinha) ? creep Call: (8) gosto_ruim(biscoito) ? creep Fail: (8) gosto_ruim(biscoito) ? creep Redo: (8) local(_G286, cozinha) ? creep Fail: (8) local(_G286, cozinha) ? creep Fail: (7) local_comida(_G286, cozinha) ? creep
No
Rastreamento de Rastreamento de local_comida/2local_comida/2
Usando Regras (1)Usando Regras (1)► Através do uso de regras, podemos solucionar o Através do uso de regras, podemos solucionar o
problema das portas com um único caminhoproblema das portas com um único caminho► Podemos definir um novo predicado de Podemos definir um novo predicado de dois dois
caminhoscaminhos, com duas cláusulas, chamado , com duas cláusulas, chamado conexao/2conexao/2conexao(X,Y):- porta(X,Y).conexao(X,Y):- porta(X,Y).conexao(X,Y):- porta(Y,X).conexao(X,Y):- porta(Y,X). A sala X está conectada à sala Y se existe uma porta de A sala X está conectada à sala Y se existe uma porta de
X a Y, X a Y, ouou se existe uma porta de Y a X se existe uma porta de Y a X?- ?- conexao(cozinha, escritório).conexao(cozinha, escritório).YesYes?- ?- conexao(escritório, cozinha).conexao(escritório, cozinha).YesYes
Usando Regras (2)Usando Regras (2)► Podemos agora listar todas as conexões (o dobro do Podemos agora listar todas as conexões (o dobro do
número de portas) com uma consulta geralnúmero de portas) com uma consulta geral?- ?- conexao(X,Y).conexao(X,Y).X = escritórioX = escritórioY = saguão ;Y = saguão ;
X = cozinhaX = cozinhaY = escritório ;Y = escritório ;......X = saguãoX = saguãoY = escritório ;Y = escritório ;
X = escritórioX = escritórioY = cozinha ;Y = cozinha ;......
Nani Search (1)Nani Search (1)► Podemos agora acrescentar novas regras a Nani Podemos agora acrescentar novas regras a Nani
SearchSearch► olhar/0olhar/0 – irá informar ao jogador onde ele/ela – irá informar ao jogador onde ele/ela
está, quais objetos existem na sala, e quais as está, quais objetos existem na sala, e quais as salas adjacentessalas adjacentes
► Iniciaremos com Iniciaremos com lista_objetos/1lista_objetos/1, que lista todos os , que lista todos os objetos em uma salaobjetos em uma salalista_objetos(Lugar):- local(X, Lugar), tab(2), write(X), lista_objetos(Lugar):- local(X, Lugar), tab(2), write(X),
nl, fail.nl, fail. Agora podemos usarAgora podemos usar?- ?- lista_objetos(cozinha).lista_objetos(cozinha).
maçãmaçãbrócolisbrócolisbiscoitobiscoito
NoNo
Nani Search (2)Nani Search (2)► Existe um pequeno problema com Existe um pequeno problema com
lista_objetos/1lista_objetos/1 Ela nos dá a lista, mas sempre falhaEla nos dá a lista, mas sempre falha Tudo bem, se a chamamos diretamente, mas não Tudo bem, se a chamamos diretamente, mas não
permite o uso em conjunção com outras regras permite o uso em conjunção com outras regras que a seguem (a direita do diagrama)que a seguem (a direita do diagrama)
► Solucionaremos este problema adicionando Solucionaremos este problema adicionando uma segunda cláusula uma segunda cláusula lista_objetos/1lista_objetos/1 que que sempre é bem sucedidasempre é bem sucedidalista_objetos(Lugar):- local(X, Lugar), tab(2), lista_objetos(Lugar):- local(X, Lugar), tab(2),
write(X), nl, fail.write(X), nl, fail.lista_objetos(QualquerLugar).lista_objetos(QualquerLugar).
Nani Search (3)Nani Search (3)► Agora, quando a primeira cláusula falha, a Agora, quando a primeira cláusula falha, a
segunda cláusula será tentadasegunda cláusula será tentada Uma vez que o seu argumento é uma variável, ela Uma vez que o seu argumento é uma variável, ela
casará com sucesso com qualquer coisa, causando casará com sucesso com qualquer coisa, causando lista_objetos/1lista_objetos/1 ser sempre bem sucedida e sair pela ser sempre bem sucedida e sair pela porta ‘porta ‘ExitExit’’
► Como na segunda cláusula de Como na segunda cláusula de lista_objetos/1lista_objetos/1 nós nós não nos preocupamos com o valor da variável, não nos preocupamos com o valor da variável, ela é simplesmente um “ela é simplesmente um “marcador de lugarmarcador de lugar”” Para estas situações existe uma variável especial Para estas situações existe uma variável especial
chamada de chamada de variável anônimavariável anônima, representada por um , representada por um underscore (_)underscore (_)
lista_objetos(_).lista_objetos(_).
Nani Search (4)Nani Search (4)► Agora escreveremos o predicado Agora escreveremos o predicado
lista_conexoes/1lista_conexoes/1, que mostra todas as conexões , que mostra todas as conexões de uma salade uma sala
► Uma vez que regras podem referenciar outras Uma vez que regras podem referenciar outras regras, bem como fatos, podemos escrever regras, bem como fatos, podemos escrever lista_conexoes/1lista_conexoes/1 da mesma forma que da mesma forma que lista_objetos/1lista_objetos/1 usando a regra usando a regra conexao/2conexao/2lista_conexoes(Lugar):- conexao(Lugar, X), tab(2), lista_conexoes(Lugar):- conexao(Lugar, X), tab(2),
write(X), nl, fail.write(X), nl, fail.lista_conexoes(_).lista_conexoes(_).
► Testando ...Testando ...?- ?- lista_conexoes(saguão).lista_conexoes(saguão).
sala de jantarsala de jantarescritórioescritório
YesYes
Nani Search (5)Nani Search (5)► Agora estamos prontos para escrever Agora estamos prontos para escrever olhar/0olhar/0►O fato único O fato único aqui(cozinha)aqui(cozinha) nos informa onde nos informa onde
estamos no jogoestamos no jogo Veremos mais a frente como dinamicamente Veremos mais a frente como dinamicamente
mudar mudar aqui/1aqui/1► Podemos usá-lo junto com os dois predicados Podemos usá-lo junto com os dois predicados
de listagem para escrever de listagem para escrever olhar/0olhar/0olhar :-olhar :-
aqui(Lugar), aqui(Lugar), write(‘Você está no(a) ’), write(Lugar), nl, write(‘Você está no(a) ’), write(Lugar), nl, write(‘Você pode ver:’), nl, lista_objetos(Lugar), write(‘Você pode ver:’), nl, lista_objetos(Lugar), write(‘Você pode ir para:’), nl, write(‘Você pode ir para:’), nl, lista_conexoes(Lugar).lista_conexoes(Lugar).
Nani Search (6)Nani Search (6)► Veremos como funciona Veremos como funciona olhar/0olhar/0
?- ?- olhar.olhar.Você está no(a) cozinhaVocê está no(a) cozinhaVocê pode ver:Você pode ver:
maçãmaçãbrócolisbrócolisbiscoitobiscoito
Você pode ir para:Você pode ir para:escritórioescritórioporãoporãosala de jantarsala de jantar
YesYes
– – Sumário –Sumário –►Regras PrologRegras Prolog
Um programa Prolog é um banco de dados Um programa Prolog é um banco de dados de de fatos fatos e e regrasregras inter-relacionadas inter-relacionadas
As regras se comunicam através de As regras se comunicam através de unificaçãounificação – casamento de padrões interno – casamento de padrões interno de Prologde Prolog
As regras se comunicam com o usuário As regras se comunicam com o usuário através de através de predicados internospredicados internos como como write/1write/1
Regras podem ser Regras podem ser consultadasconsultadas individualmente através do promptindividualmente através do prompt
– – Sumário –Sumário –►Controle de Fluxo em PrologControle de Fluxo em Prolog
O comportamento de execução das regras O comportamento de execução das regras é controlado pelo mecanismo de busca é controlado pelo mecanismo de busca interno de Prolog chamado interno de Prolog chamado backtrackingbacktracking
Podemos forçar o backtracking com o Podemos forçar o backtracking com o predicado interno predicado interno fail/0fail/0
Podemos forçar o sucesso de um predicado Podemos forçar o sucesso de um predicado adicionando uma cláusula final com uma adicionando uma cláusula final com uma variável anônimavariável anônima como argumento e sem como argumento e sem corpocorpo
– – Sumário –Sumário –► Aspectos de Programação em PrologAspectos de Programação em Prolog
Fatos Fatos no banco de dados (localizações, portas, ...) no banco de dados (localizações, portas, ...) substituem a definição convencional de substituem a definição convencional de dadosdados
A busca por A busca por backtrackingbacktracking (lista_objetos/1) (lista_objetos/1) substitui a codificação de muitos construtores de substitui a codificação de muitos construtores de laçoslaços
A troca de controle através do A troca de controle através do casamento de casamento de padrõespadrões (conexao/2) substitui (conexao/2) substitui testes condicionaistestes condicionais e estruturas de e estruturas de ramificaçãoramificação
As regras podem ser testadas individualmente, As regras podem ser testadas individualmente, encorajando o encorajando o desenvolvimento modulardesenvolvimento modular
Regras podem chamar regras encorajando Regras podem chamar regras encorajando práticas de programação de práticas de programação de abstração proceduralabstração procedural e e abstração de dadosabstração de dados►olhar/0 não sabe como lista_objetos/1 funciona e como os olhar/0 não sabe como lista_objetos/1 funciona e como os
dados de local estão armazenadosdados de local estão armazenados
Exercícios (1)Exercícios (1)►Considerando o seguinte banco de dadosConsiderando o seguinte banco de dados
a(a1, 1).a(a1, 1). b(1, b1).b(1, b1).a(A, 2).a(A, 2). b(2, B).b(2, B).a(a3, N).a(a3, N). b(N, b3).b(N, b3).c(X,Y):- a(X,N), b(N,Y).c(X,Y):- a(X,N), b(N,Y).d(X,Y):- a(X,N), b(Y,N).d(X,Y):- a(X,N), b(Y,N).d(X,Y):- a(N,X), b(N,Y).d(X,Y):- a(N,X), b(N,Y).
►Qual o resultado das consultasQual o resultado das consultas?- ?- a(X, 2).a(X, 2). ?- ?- b(X, kalamazoo).b(X, kalamazoo).?- ?- c(X, b3).c(X, b3). ?- ?- c(X, Y).c(X, Y). ?- ?- d(X, Y).d(X, Y).
Exercícios (2)Exercícios (2)► Banco de Dados GenealógicoBanco de Dados Genealógico
Crie regras para vários relacionamentos familiares Crie regras para vários relacionamentos familiares que foram desenvolvidos como consultas na aula que foram desenvolvidos como consultas na aula anterioranterior
mae(M, F):- pais(M, F), mulher(M).mae(M, F):- pais(M, F), mulher(M). Crie uma regra para irmãosCrie uma regra para irmãos
►Rastreie o predicado para visualizar o seu funcionamentoRastreie o predicado para visualizar o seu funcionamento Podemos resolver o problema de indivíduos serem Podemos resolver o problema de indivíduos serem
irmãos deles mesmos através do predicado interno irmãos deles mesmos através do predicado interno que é bem sucedido caso dois valores sejam que é bem sucedido caso dois valores sejam diferentes e falha caso sejam iguaisdiferentes e falha caso sejam iguais►O predicado é \= (X,Y).O predicado é \= (X,Y).►Também podemos escrevê-lo na forma X \= YTambém podemos escrevê-lo na forma X \= Y
Use o predicado irmãos para definir regras Use o predicado irmãos para definir regras adicionais para irmãos, irmãs, tios, tias e primosadicionais para irmãos, irmãs, tios, tias e primos
Exercícios (3)Exercícios (3)► Banco de Dados GenealógicoBanco de Dados Genealógico
O predicado para representar casamento leva ao O predicado para representar casamento leva ao problema da porta com dois caminhos (porta/2)problema da porta com dois caminhos (porta/2)►Utilize uma solução idêntica para implementá-loUtilize uma solução idêntica para implementá-lo
Adicione regras para tios e tias que consiga Adicione regras para tios e tias que consiga acrescentar tios e tias por casamento e não apenas acrescentar tios e tias por casamento e não apenas por sanguepor sangue
Escreva um predicado para avôEscreva um predicado para avô►Rastreie o uso de avo(alguem, X). e avo(X, alguem). que Rastreie o uso de avo(alguem, X). e avo(X, alguem). que
encontra avôs e netosencontra avôs e netos►Dependendo de como você escrevê-lo, ele poderá precisar de Dependendo de como você escrevê-lo, ele poderá precisar de
muito mais passos em uma consulta que em outramuito mais passos em uma consulta que em outra►Escreva dois predicados, um chamado avo/2 e outro chamado Escreva dois predicados, um chamado avo/2 e outro chamado
neto/2neto/2►Certifique-se de que ambos são eficientesCertifique-se de que ambos são eficientes
O que vem a seguir?O que vem a seguir?
►AritméticaAritmética►Gerenciando DadosGerenciando Dados► ......