LP 07/11/2011

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

		Hoje estamos falando de prolog.

X = kim
Y = holly
X = margaret
Y = kim
X = margaret

greatgrandparent(A,B) :- parent (A, C), parent (C, D), parent(D, B)
// O escopo de uma variável declarada nessa linha acima termina ao fim da linha.
na funçào acima greatgrandparent é verdadeiro só se os 3 parents forem também verdade.

Agora como fazer para saber se x é ancestral de y?

ancestor(X, Y) :- parent (X,Y)
ancestor(X, Y) :- parent (C,Y), ancestor(X, C)

// Prolog é uma linguagem lógica.
// e a familia de linguagens logicas que são declarativas é na verade só o prolog, e derivados dele.

// Note que a ordem que voce coloca as coisas após :- não deveria importar, bastaria que fossem verdade.
// na prática a ordem importa.

// Prolog é quase estaticamente tipada já que só existe 1 tipo o "atomo"
// na prática o significado do atomo só é descoberto em tempo de execução e portanto pode-se dizer que é dinamicamente tipada.

// Casamento de padrão:

A(X, Y, Z) será verdade se X@Y = Z

A([], L, L).
A([H|T], B, [H|Tx]) :- A(T, B, Tx).
// E isso já basta.

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

mmember(X, L), é verdade quando X for um atomo presente na lista L.

mmember(X, [x|_]).
mmember(X, [_|L]) :- mmember(X, L).
// E isso basta.

?- select(X, [1,2,3], L).
// seleciona e exclui um membro da lista.

mselect(H, [H|T], T).
mselect(X, [H|T], [H|L]) :- mselect(X, T, L).
// Isso funciona.

Como reverter uma lista?
mreverse(L, L*). retorna true se L for o reverso de L*

mreverse([],[]).
mreverse([H|T], X) :- mreverse(T, Tx), A(Tx, [H], X).
// Isso basta, note que quando voce chama uma dessas funções o prolog te retorna vários valores possíveis para as variáveis indefinidas.
// parece que letras maiusculas são consideradas variáveis.
// Outra nota, prolog é um algoritimo de tentativa e erro, e ele tenta atribuir valores as variaveis, e vai mostrando todos os verdadeiros que ele encontrar.

vamos aprender a usar o not():
seja uma função sibling (parente)

sibling(A,X) se A irmao de X

sibling(X, Y) :- parent(C,X), parent(C,Y).
// Essa solução retorna que vinicius é irmão de vinicius (e nao queremos isso) como evitar?

sibling(X, Y) :- not(X = Y), parent(C,X), parent(C,Y).
// Isso da sempre falso, porque?
// porque x e y na atribuiçào ainda não tem significado.
// Como corrigir?

sibling(X, Y) :- parent(C,X), parent(C,Y), not(X = Y).
// Isso funciona, pois X é filho de C e Y é filho de C, e ambos não podem ser iguais.

vamos criar a função sublist:

sublist([], []).
sublist([H|T], [H|L]) :- sublist(T,L).
sublist([_|T], L) :- sublist(T, L).
// ou seja se a sublista esta no inicio ou no meio.

intercect(L1, L2) :- member(H, L1), member(H,L2).
// Isso é mto proximo da linguagem de alto nivel.

perm(L, L') é verdade se L é permutação de L'

perm([], []).
perm(T, L) :- member(H, T), select(H, T, L1), perm(L1, L2, select(H, T, L1), perm(L1, L2).
// outra opção:
perm([H|T], L) :- perm(T, Lx), select(H, L, Lx).
// Também funciona da mesma forma.

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

//  hellow world de prolog:

seja o lado oeste e lado leste de um rio.
do lado esquerdo temos: temos um coelho um lobo, uma cabra e um pastor.
existe um conjunto de regras que impede que alguns dos membros fiquem sozinhos em um mesmo lugar.

solution().

Pode-se pensar nesse problema como uma lista de 4 posições: [Padre, Ovelha, Coelho, repolho, lobo)
pode-se dizer que em cada posição dessa lista há uma posição leste ou oeste.

solution([l,l,l,l],  []). // é uma solução.  (a segunda lista é a lista de movimentos)
solution(Config, [Move|Rest]) :- move(Config, Move, NextConfig), safe(NextConfig), solution(NextConfig, rest).

o que é seguro?
safe([man, wolf, goat, cabbage]) :- oneEq(Man, Wolf, Goat), oneEq(Man, Goat, Cabbage)

oneEq(X, X, _). // so retorna verdadeiro se o homem estiver protegendo ao menos um dos membros da cadeia.
oneEq(X, _, X).

move([X, X, Goat, Cabbage], wolf, [Y, Y, Goat, Cabbage])    :- change (X,Y).
move([X, Wolf, X, Cabbage], wolf, [Y, Y, Goat, Cabbage])    :- change (X,Y).
move([X, Wolf, Goat, X], wolf, [Y, Y, Goat, Cabbage])       :- change (X,Y).
move([X, Wolf, Goat, Cabbage], wolf, [Y, Y, Goat, Cabbage]) :- change (X,Y).

ao chamar um program em verilog posso:
? lenght(X, 7), solution([o,o,o,o],X).
sendo X movimentos o numero de movimentos exigidos é 7.
Assim voce evita que o programa tente entrar em loops infinitos,
 sem esse lenght na chamada o programa de fato entrou em loop.