CONTROLE PROCEDURAL DE RACIOCÍNIO EM PROLOGtacla/SI2/cap06/007-ctrlProceduralRac... · CARACTERÍSTICAS DA LINGUAGEM PROLOG ... Exemplo pg. 57 apostila Prof. Palazzo – função

CONTROLE PROCEDURAL DE RACIOCÍNIO EM PROLOG

CARACTERÍSTICAS DA LINGUAGEM PROLOG

• Não é completamente declarativa! – envolve aspectos procedurais.

• Declarativa • KB = regras e fatos • descrevem a situação/problema

• Procedural – interfere nas inferências produzidas

• KB é varrida top-down; cláusulas da esquerda para direita • ordem das cláusulas interfere • backtracking • operador cut (interfere no backtracking)


P(X):- Q(X), R(X).

Semântica declarativa Todo X que é Q(X) e R(X) tem-se (acarreta, tem por consequência) que P(X).

Semântica Procedural Para provar P(X), primeiro prova-se Q(X) e depois R(X).


Programas com mesma semântica DECLARATIVA podem produzir diferentes resultados devido aos aspectos procedurais da linguagem.

Conteúdos

• Backtracking

• Recursividade

• Operador cut

• Closed World Assumption

• Negação por falha

BACKTRACKING

• Backtracking: – busca realizada pelo PROLOG é em profundidade

– backtracking volta quando a prova da query falha em um ramo

– No shell, usuário pode solicitar novo resultado – isto produzirá backtracking (;)

• Compreender – backtracking quando a prova da query falha em um ramo

– a importância da ordem dos predicados

Backtracking

gosta(joao,X)

gosta(renata,jazz) fail

gosta(joao, jazz)

X/jazz

gosta(joao,X)

gosta(renata,renata) fail

gosta(joao, renata)

X/renata

gosta(joao,lasanha)

gosta(renata,lasanha) TRUE

gosta(joao, lasanha)

X/lasanha gosta(joão, jazz).

gosta(joão, renata).

gosta(joão, lasanha).

gosta(renata, joão).

gosta(renata, lasanha).

? gosta(joao, X), gosta(renata, X).

Extraído de (Palazzo, 1997, pg. 52).

Linhas tracejadas=backtracking

Backtracking

• Fazer exercícios:

– cap. 06: 00-exercicios-backtracking

Recursividade

• Objetivo: – compreender recursividade em PROLOG – a importância da ordem das cláusulas e objetivos – Recursividade à esquerda e à direita – Término de recursividade – backtracking na recursividade

Recursividade

a

b

c

d

Considere o mundo de blocos ao lado e a seguinte KB com a definição recursiva de above:

on(a,b).

on(b,c).

on(c,d).

above(X,Y):-on(X,Y).

above(X,Y):-on(X,Z),above(Z,Y).

Em destaque vermelho, a cláusula BASE que dá

um ponto final à recursividade. A cláusula em azul,

é a cláusula RECURSIVA.

A cláusula recursiva deve levar à cláusula base para que termine! Em algum momento, above(Z,Y) DEVE ser provada por on(Z,Y) – com as devidas substituições.

on(a,b)

above(b,d)

above(a,d)

Recursividade (prova ok)

on(a,b).

on(b,c).

on(c,d).

above(X,Y):-on(X,Y). %C1

above(X,Y):-on(X,Z),above(Z,Y). %C2

above(a,d)

on(a,d) fail

on(a, Z)

C1:X/a, Y/d

C2:X/a, Y/d

above(b, d) on(a, b)

C2:Z/b

on(b,d)

C1:X/b, Y/d

fail

on(b, Z)

C2:X/b, Y/d

on(b, c)

C2:Z/c

above(c, d)

on(c,d)

TRUE

C1:X/c, Y/d

backtracking

a

b

c

d

on(a,b)

above(b,d)

above(a,d)

Recursividade (visualizações)

on(a,b).

on(b,c).

on(c,d).



above(a,d)

on(a, Z)

above(b, d) on(a, b)

on(b, Z)

on(b, c)

above(c, d)

on(c,d)

a

b

c

d

on(a,b)

above(b,d)

above(a,d)

Recursividade (falha)

a

b

c

d

on(a,b).

on(b,c).

on(c,d).



above(b,a)

on(b,a) fail

on(b, Z)

C1:X/b, Y/a

C2:X/b, Y/a

above(c, a) on(b, c)

C2:Z/c

on(c,a)

C1:X/c, Y/a

fail

on(c, Z)

C2:X/c, Y/a

on(c, d)

C2:Z/d

above(d, a)

on(d,a) fail

C1:X/d, Y/a

on(d, Z)

C2:X/d, Y/a

fail

backtracking

Recursividade: ordem das cláusulas

Ao invertermos as cláusulas BASE com RECURSIVA, o que ocorre?

on(a,b).

on(b,c).

on(c,d).

above(X,Y):-on(X,Z),above(Z,Y).

above(X,Y):-on(X,Y).

a

b

c

d

on(a,b)

above(b,d)

above(a,d)

Os resultados são apresentados em ordem diferente da solução anterior.

?- above(a,X).

X = b ;

X = c ;

X = d.

?- above(a,X).

X = d ;

X = c ;

X = b.

anterior atual: inversão base e recursiva

Recursividade: ordem das cláusulas

• Exercício

– desenhe a árvore de derivação PROLOG para o caso do slide anterior. Query = ?above(a,d)

Recursividade: ordem dos objetivos

E se invertermos os (sub)objetivos da cláusula REDUTORA?

on(a,b). on(b,c). on(c,d). above(X,Y):-above(Z,Y), on(X,Z). above(X,Y):-on(X,Y).

a

b

c

d

on(a,b)

above(b,d)

above(a,d)

Do ponto de vista declarativo, continua igual! Ex. Para provar above(a,d) temos que encontrar: 1. um Z que esteja acima de d (Z=b) 2. a deve estar em cima deste Z mas, como fica a árvore de derivação SLD de PROLOG?

Recursividade: ordem dos objetivos

a

b

c

d

on(a,b).

on(b,c).

on(c,d).

above(X,Y):-above(Z,Y), on(X,Z). %R

above(X,Y):-on(X,Y). %B

above(Z1, d)

R: Y/d, Z/Z1

above(Z1, d)

R:X/Z1, Y/d

above(Z1, d)

R:Z/Z1, Y/d

…

ERROR: Out of local stack

above(a,d)

on(a,Z1)

on(a,Z1)

on(a,Z1)

R: X/a, Y/d

Recursividade

• Exercícios:

– Cap 6. ex070-00-unificacao-recursividade.pl

Operador CUT

• Cut (!) – Interrompe o backtracking

– Valorado como • true na prova;

• false no backtracking

– Aplicações: • aumento da eficiência, exclusão mútua

CUT: EXEMPLO

Exemplo pg. 57 apostila Prof. Palazzo – função degrau

f(X,0) :- X<3. %C1

f(X,2) :- X>=3, X<6. %C2

f(X,4) :- X>=6. %C3

?- f(1,Y), Y>2. %Q f(1,0)

C1: X/1, Y/0

0>2 fail

1<3 true

Q: Y/0

f(1,2)

C2: X/1, Y/2

X>=3 fail

f(1,4)

X>=6 fail

C3: X/1, Y/4

Programador sabe que somente uma das cláusulas pode satisfazer a query, no entanto, todas serão verificadas se não usar o CUT.

CUT: EXEMPLO


f(X,0) :- X<3, !. %C1 f(X,2) :- X>=3, X<6, !. %C2 f(X,4) :- X>=6. %C3

?- f(1,Y), Y>2. %Q f(1,0)

C1: X/1, Y/0

0>2 fail

1<3 true Q: Y/0

f(1,2)

C2: X/1, Y/2

X>=3 fail

f(1,4)

X>=6 fail

C3: X/1, Y/4

CUT impede o backtracking – observe que é um ramo and.

! true

Compromete-se com todos as substituições já feitas: X/1 e Y/0

CUT: EXEMPLO


f(X,0) :- X<3, !. %C1 f(X,2) :- X>=3, X<6, !. %C2 f(X,4) :- X>=6. %C3

f(4,0)

C1: X/4, Y/0

4<6 true

4<3 fail C2: X/4, Y/2

É possível melhorar a eficiência do programa impedindo reavaliações de X.

f(X,0) :- X<3, !. %C1 f(X,2) :- X<6, !. %C2 f(X,4). %C3

?- f(4,Y), Y>2. %Q !

true 2>2 fail

?- f(4,Y), Y>2. %Q

4>=3 true

reavaliação evitada

Q: Y/2

RED CUT


true

C3: X/1, Y/4

A modificação anterior introduziu um erro de

semântica.

f(X,0) :- X<3, !. %C1 f(X,2) :- X<6, !. %C2 f(X,4). %C3

?- f(1, 4). true.

?- f(1, 4) %Q

Cuts que modificam o significado do programa são

chamados de RED CUTS.

f(1,4) não unifica com

f(X,0)

f(1,4) não unifica com

f(X,2)

RED CUT

• Qual a solução?

– exercício…

– solução em ex240-20-cut-funcao-degrau.pl-mais-eficiente-redcut-corrigido.pl

• Mais exercícios em • Cap 6.: 30-exercicios-cut

Closed World Assumption

• Pressuposto do mundo fechado

– adotado por PROLOG

040-exercicios-CWA

Negação por falha

• Negaçã obtida quando PROLOG não consegue provar algo.

• Negação por falha é diferente de negação lógica (tem um componente procedural)

Negação por falha

solteiro(X) :- \+ casado(X).

Para solteiro(X) ser verdadeiro, o PROLOG tem que falhar na prova casado(X).

Exemplo

solteiro(X) :- casado(X), !, fail.

De uma forma explícita:

Se X é casado, ocorre fail na prova de solteiro(X).

Negação por falha

casado(pedro). casado(ana). casado(marcelo). professor(artur). solteiro(X) :- \+ casado(X).

?solteiro(artur)

\+ casado(artur)

true

?professor(artur), solteiro(artur)

X/artur

professor(artur) true

\+ casado(artur)

true

Duas queries que funcionam como esperado

X/artur

Negação por falha


?solteiro(X)

casado(pedro)

true

X/pedro

Query que não funciona como esperado

RESPOSTA esperada: artur obtida: false.

Necessário utilizar a forma EXPLÍCITA para compreensão: solteiro(X) :- casado(X), !, fail.

! true

fail

fail força PROLOG retornar false e o cut impede nova substituição

Negação por falha


?solteiro(X), professor(X).

casado(pedro)

true

X/pedro

Query que não funciona como esperado

RESPOSTA esperada: artur obtida: false.

Necessário utilizar a forma EXPLÍCITA para compreensão: solteiro(X) :- casado(X), !, fail.

! true

fail

fail força PROLOG retornar false e o cut impede nova substituição

Negação por falha vs. negação lógica

Vx (~casado(x) solteiro(x)) Domínio={a,b,c} casado={a} Pela fórmula em LPO, deduz-se que b e c são solteiros.

Considere a query: ?- solteiro(X). PROLOG não consegue responder deduzir que b e c são solteiros. E, além disso, retorna FALSO, como se não existissem solteiros. Isto se deve ao aspecto procedural. Prolog não tenta todas as substituições possíveis para X, só aquelas que unificam com o predicado casado(x) – no caso, somente casado(a). Isto difere da LPO.

casado(a). pessoa(a). pessoa(b). pessoa(c). solteiro(X) :- \+ casado(X).

Negação por Falha

• exercícios

050-exercicios-negacao-por-falha

Documents

CONTROLE PROCEDURAL DE RACIOCÍNIO EM PROLOGtacla/SI2/cap06/007-ctrlProceduralRac... · CARACTERÍSTICAS DA LINGUAGEM PROLOG ... Exemplo pg. 57 apostila Prof. Palazzo – função