Aula 12

Livro texto

Prolog interativo

Continuando prolog basico

vamos assumir o banco de dados

parent(alberto,beatriz).
parent(alberto,carlos).
parent(alberto,zeca).
parent(denise,beatriz).
parent(denise,zeca).
parent(elisa,carlos).
parent(beatriz,flavio).
parent(gustavo,flavio).

a primeira definição de (meio) irmao - pelo menos um parent em comum (neste caso o Z).

     irmao(X,Y) :- parent(Z,X),parent(Z,Y).

testando

      ?- irmao(beatriz,K).

respostas

K = beatriz
K = carlos
K = zeca

beatriz é meio irmã de beatriz? Sim segundo a definição, mas claramente queremos pessoas diferentes.

o =

a operação = em prolog é a operação de unificação que dicutimos ate agora

pedro = antonio      -> falha
X = antonio          -> da certo e X passa a valer  antonio
antonio = X          ->  da certo e X passa a valer antonio
antonio = X, X = Y   -> da certo e X e Y valem anotonio
X = Y                -> da certo e X e Y terao o mesmo valor (quando um assumir um )
X = Y, Y = antonio, X = pedro   -> falha

unificação é uma mistura de teste de igualdade e atribuição (bidirecional)

o not +

Negaçao em prolog é complicada pois não há boleanos. Um predicado nao retorna True, e um not não transforma esse valor para False.

Negação em prolog indica se o predicado de dentro deu ou não certo. negation by failure

not p(..)     ou    \+ p(..)

vai dar certo, se p(...) falhar

\+ ( p(..), q(..) )

vai dar certo se (p(..),q(..) ) falhar

meio irmao

irmao(X,Y) :- parent(Z,X), parent(Z,Y), \+ X=Y.

irmao cheio

irmao_cheio(X,Y) :- parent(Pai,X), parent(Pai,Y),
                    parent(Mae,X), parent(Mae,Y),
                    \+ Mae = Pai,
                    \+ X=Y.

Avô

dado o predicados pai(a,b) se a é pai de b, e mae(a,b)

avo(A,N) :- pai(A,M), mae(M,N).
avo(A,N) :- pai(A,P), pai(P,N).

o ; ou

o ; é o operador ou.

   a(..), b(..), ( c(..) ; d(..) ).

vai tentar provar a depois b e depois c .

Se c falhar, ele vai tentar d antes de dar o backtraking.

Avo pode ser escrito com o ;

 avo(Avo,Neto) :- pai(Avo,X), ( mae(X,Neto) ; pai(X,Neto) ).

Descendente https://en.wikibooks.org/wiki/Prolog/Recursive_Rules

descende(X,Ansestral) :- parent(Ansestral,X).
descende(X,Ansestral) :- parent(Ansestral, Filho), 
                               descende(X,Filho).

Coloque o caso base antes.

o caso recursivo tambem poderia ser escrito como

descende(X,Ansestral) :- parent(PAI, X), descende(PAI,Ansestral).

Numeros em Prolog

A coisa mais importante é que expressões matematicas só são calculadas em 2 contextos

X*4/Y > Z**2
X is Y+2

is calcula o valor do lado direito e unifica com o lado esquerdo.

Expressões podem não dar certo em tempo de execução pois algumas variáveis podem não ter valor no momento da execução

Y is X+2, X = 2
X = 4, Y = X+2

NAO use o = numa expressão matemática.

X = 2
X is 2

comparações

A > B
A >= B

A =< B

A =:= B  igualdade aritimetica 
A =\= B  desigualdade aritimetica

Listas

Heterogeneas, entre [ ]

[1, 2, [5,6], abobora, [] ]

Pattern matching:

[Cabeca|Resto] -- equivale ao (cabeca:resto) do haskell
[]

[X|R] nao casa com a lista vazia

[1,2,3] = [X|R]
X = 1, R = [2,3]

Exemplos

tam([],0).
tam([_|R],N) :- tam(R,NN), N is NN+1.
tam(L,N) = tamx(L,N,0).
tamx([],N,Acc) :- Acc=N.
tamx([X|R],N,Acc) :- AA is Acc+1, tamx(R,N,AA).

nesta ultima regra o prolog indica singleton variable X . Isso é um warning que a variavel X aparece só uma vez, e isso pode ser um erro com consequencias graves na hora de rocar ou nao ser nada serio como no caso acima.

Voce pode usar a variavel anonima _

Modo

quando vc programa tam vc assume que vc recebe a lista (+) e vai devolver o tamanho dela (-)

tam modo (+-)

Erros

tam([],0).
tam([_|R],N) :- tam(R,N), N is N+1.  <- erro

tam([_|R],N) :- tam(R,NN), N = NN+1.  <- correto

N is N+1 nunca da certo! Ou N nao tem valor, e a expressão da um erro, ou N tem valor e o lado esquerdo não unifica com o lado esquerdo

tamx([X|R],N,Acc) :- tamx(R,N,Acc+1).   <- erro

tamx([X|R],N,Acc) :-  AA is Acc+1, tamx(R,N,AA).  <- correto

Lembre-se expressões matematicas NAO sao avaliadas em passagem de parametros.

Exemplo 2

Soma dos elementos de uma lista soma(+LISTA,-SOMA)

soma([],S) :- S=0.
soma([X|R],S) :- soma(R,SS), S is SS+X.

ou

soma([], 0). 
soma([X|R],S) :- soma(R,SS), S is SS+X.

exemplo 3

soma dos números pares de uma lista somapares(+LISTA,-SOMA)

somapares([], 0).
somapares([X|R], SP) :- X mod 2 =:= 0, somapares(R,SS),
                        SP is SS+X.
somapares([X|R], SP) :- somapares(R,SS), SP=SS.

se X é par , ele executa a 2a regra. Se X é impar, o primeiro predicado da 2a regra falha, e o prolog executa a 3a regra.

Nao precisamos de IF/ELSE. A 2a regra testa para a condição X mod 2 =:= 0 e contém o THEN. A 3a regra contem o ELSE.

Outra versão

somapares([],0).
somapares([X|R], SP) :- X mod 2 =:= 0, somapares(R,SS),
                        SP is SS+X.
somapares([_|R], SP) :- somapares(R,SP).

Outra versão

somapares([], 0).
somapares([X|R], SP) :- somapares(R,SS),
            (X mod 2 =:= 0 , SP is SS+X 
         ;   SP=SS).

Exercícios

Da aula 1 e 2 e haskell - use acumuladores quando necessario.

o append(+,+, -)

append([],A,A).
append([X|R],A,AA) :- append(R,A,RR), AA = [X|RR].

ou 

append([],A,A).
append([X|R], A, [X|RR]) :- append(R,A,RR).
intercala1([1,2,3], [4,5,6,7,8], X).
 X =  [1,4,2,5,3,6]
intercala2([1,2,3], [4,5,6,7,8], Y),
 Y =   [1,4,2,5,3,6,7,8]
shiftr([1,2,3,4],X)
 X = [4,1,2,3]