LP 09/11/2011

   # # # # # # # # # # # # # #
  # Linguagens de Programação #
  # Prof. Fernando Pereira    #
  # notasdogarcia.blog.com    #
   # # # # # # # # # # # # # #

		Joe A. Robinson escreveu um artigo sobre a unificação que é um dos mais citados em computação.

A busca é pelo Most General Unifier (MGU)

pai(x,y) = pai(x,f)

Qual o menor predicado que faria dessa afirmação verdadeira?

{y=f}
mas existem outras que também teriam esse efeito ex:
{y=f, x=joao)

Mas a mais geral é a primeira.

?- reverse([1,2,3], X).
imprime na tela:
X = [3, 2, 1].

?- X=0, Y is X + 1
imprime:
X=0,
Y=1.

programa em prolog:
p :- q, r. /* boolean p() { return q() && r(); } */
q :- s.    /* boolean p() { return s(); } */
r :- s.    /* boolean r() { return s(); } */
s.    /* boolean s() { return true; } */

p :- q, r. /* boolean p() { return ; }*/
p :- s.    /* boolean p() { return ; }*/
p.         /* boolean p() { return ; }*/
r.         /* boolean p() { return ; }*/
s :-       /* boolean p() { return ; }*/

?- X = f(X)
imprime:
X = f(**) // (asteriscos duplos indicam infinidade)

?- append([], X, [a|X]).
X = [a|**]

?- N = N + 1
N = ** + L

?- N is N + 1
ERROR: is/2: Arguments are not sufficiently instantiated.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Vamos programar em pseudo-codigo um interpretador de Prolog:

function res (clause, goals)
  let sub = MGU ( hd (clause), hd(goals))
  return sub((tl(clause)) @ t1(goals))

function solve(goals)
  if goals = nil then succeed()!!!
  else para cada clause c in program, /* em ordem */ faça:
    if hd(c) nao unifica com hd(goals) then fail!!!
    else solve(res(c, goals))

reverse(Y,Y).
reverse(Y,X) :- ....

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Vamos tentar usar nosso interpretador para ver se isso funciona.

p(f(Y)) :- q(Y), r(Y).
q(g(Z)).
q(h(Z)).
r(h(a)).

Se tentarmos:
? p(X)
X = (f(h))(a)

goal(p(X))
O programa tem 4 clausulas. (cada linha) e cada clausula é uma lista.
s(p(X))
s( Res ([p(f(Y)), q(Y), r(Y)], [p(X)]) )
Daqui casando a cabeça das listas temos: X = f(Y)
removendo a cabeça da clausula e substituindo X=f(Y) não obtemos nada já que não há ocorrencias de X na clausula então fica:
s([q(Y), r(Y)])
s( Res ([p(f(Y)), q(Y), r(Y)], [q(Y), r(Y)]) )
recursivamente, repetidos o processo do res.
Vamos buscar a unificação: na clausula 1: encontramos? não. na clausula 2? sim.
na 3 também mas vamos empilhar e voltar depois, na 4 não.

s(res([q(g(z))],[q(Y),r(Y)]))
verifique que a primeira clausula e meta se unificam gerando: Y=g(z)
substituindo isso na outra meta temos:

s([r(g(Z))])
mas verificando as clausulas, não encontramos solução, então desistimos desse caminho.

Vamo desempilhar a clausula 3 que empilhamos a pouco.
Y = h(z)
S(res( [g(h(Z))], [g(Y), r(Y)]  ))

unificando as cabeças temos:
Y=h(Z)

substituindo temos:

S([r(h(Z))])
unificando com a quarta clausula temos que:
{Z = a}

S( res( [r(h(a))], [r(h(Z))] ))
de algum modo chegamos em S([])
que encerra o processamento.

X = f(Y), Y= h(Z), Z = a
isso gera uma solução válida.

X = f(h(a))

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

p :- p.
p.

// o professor chamou ? consult(p)
Como o programa analiza as clausulas em ordem, ele entra em loop, pois para ele provar que a meta p é verdade ele precisa primeiro de provar que p é verdade =/.
acho que é isso. ou o inverso disso.

agora:

p.
p :- p.

seria verdade infinitas vezes, mas ele pararia após imprimir o primeiro p e só continuaria imprimindo por requisição do usuário.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

vamos programar uma funções append A:

A([], L, L).
A([H|Ta], B, [H|Tc]) :- A(Ta, B, Tc).

S( A(X, Y, [1,2]))
quantos casos isso é verdade? 3.
o prolog nós veremos tentará 4 e uma falhará.

chamando pra primeira clausula temos que:
{ X = [], Y=L0, [1,2]=L0 }
S(A([],L0,[1,2])) // não é necessário continuar,
mass é necessário casar os dois últimos termos.
chegariamos que Y0 = [1,2].

Agora ele tentou voltar pro inicio e tentar a partir da segunda clausula,
ele repetiu os passos para solucionar essa afirmativa também.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

// Nesse finzinho de aula iremos falar de reflexão.
// Isso é a capacidade de uma linguagem de observer seu próprio funcionamento.

Em java nos teriamos reflexão passiva, podemos observar o tipo de um dado, durante sua execução, e entender quantos campo ela tem.
Em python temos reflexão ativa. Podemos alterar por exemplo uma função de uma classe em tempo de execução.

prolog tem também reflexão passiva.
Não havendo estados em prolog, é preciso

( a extensão de prolog é .pl )

report :- write('Voce esta aqui: '), at(You), write(You), nn1

step(Dest) :-
  at(You),
  connect(You, Dest),
  //Para dizer que um estado mudou, ou seja dizer que at(You) agora é falso, porque voce se moveu:
  retract(at(You)),
  assert(at(Dest)),
  write('Voce acabou de sair de: '), write(You), n1
  write('Voce acabou de chegar em: '), write(Dest), n1

Para demonstrar isso ele deu vários asserts que definirão algumas verdades para o inicio do funcionamento do programa.
?- assert(connect(a,b)).
Definiu que a conecta-se a b.
e deu tb assert(at(a)). então voce esta em a no inicio, e mostrou como isso funciona.