LP 16/11/2011

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

		Falando de atomos em prolog.

Todas as estruturas são atomos sem muitos significados atribuidos a eles, como nós estamos acostumados.

por exemplo se pergunto:

?- X = 2 + 1
é retornado:
X = 2+1

Hoje vamos falar sobre a interpretação semantica em prolog, ou seja, como fazer para aquela soma acima retornar 3?

myLength([],0).
myLength([_|Tail], Len) :- myLength(Tail, TailLen), Len = TailLen + 1.
O que isso retorna para:

?- myLength([1,2,3],X).

retorna: X = 0+1+1+1

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

A semantica is faz:
avalio a da direita e unifico com a da esquerda.

assim:
X is 2 + 1
retorna:
X = 3

3 is 2+1.
retorna:
true.

2+1 is 3
retorna:
false.

3 is X
da erro pois X ainda não foi instanciado.

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

A semantica de =:= avalia ambos os lados, e unifica os resultados assim temos:

2+1 =:= 3.
true.

2+1 =:= 1+2
true.

mas:
2+1 =:= X
da erro de compilação pois X ainda não foi instanciado.

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

A semantica do == é como a do =:=.

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

façamos uma função para somar uma lista.

sum([],0).
sum([H|T], N) :- sum(T, N1), N is H + N1.

Realizar a chamada:
sum(X, 2).
gera erro porque?
porque o H a direita do is na função sum não teria sido definido.

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

fact(0,1).
fact(1,1).
fact(N,F) :- integer(N), N > 1, N1 is N-1, fact (N1, F1), F is F1 * N;

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

Função para detectar primos:

is_prime(2).
is_prime(3).

is_prime(P) :- integer(P), P > 3, P mod 2 =\= 0, \+ has_factor(P,3).

has_factor(N, L) :- N mod L =:= 0.
has_factor(N, L) :- L * L < N, L2 is L + 2, has_factor(N, L2).

O professor pediu um aluno por um número de 5 digitos primo, o cara arranjou um:
24113
E era primo mesmo xP.

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

Vamos fazer uma função range, que diz se uma lista representa uma sequencia de número do numéro I ao K?

"range(I, K, L)"

// Eu perdi a implementação disso.

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

como fazer para descobrir todos os números primos dentro de um determinado range?

range(2, 14, L), member(N, L), is_prime(N).

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

  Vamos tentar criar um algoritimo de um problema NP-Completo?

  Seja o problema de descobrir se dado um conjunto de números, existe uma subconjunto cuja soma seja N.

  Vamos fazer então uma função intSum:

  intSum(L, N, S) :- subList(L, S), sum(S, N).

  subList([], []).
  subList([H|T], [H|R]) :- subList(T,R).

Isso soluicionaria um problema NP completo em 6 linhas.
Mas ainda não consegui copiar tudo.

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

Vamos resolver outro problema NP, o problema das 8 rainhas:
Para quais posições 8 rainhas poderiam ficar em um tabuleiro de xadrez sem estarem na mira uma das outras?

legal([]).
legal([]) :-
	member(X, [1,2,3,4,5,6,7,8])
	member(Y, [1,2,3,4,5,6,7,8])
        noCheck(X/Y, Rest). //ou seja essa rainha não coloca nenhuma das rainhas da lista em cheque.

noCheck(_, []).
noCheck(X/Y, [X1/Y1 | Rest ]) :-
	X =/= X1,
        Y =/= Y1,
	abs(Y1-Y) =/= abs(X1-X),
	noCheck(X/Y, Rest).

Isso deve funcionar, porém, vai gerar soluções praticamente iguais.
Para evitar isso podemos fazer:
? length X is 8, e X is [1/_, 2/_, 3/_, 4/_, 5/_, 6/_, 7/_, 8/_], legal(X), findAll
// foi algo assi, ele encontrou 92 posiçòes diferentes.

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

Seja um arquivo dicionário de uma linguagem:

casa.
pato.
escola.
mingau.

Para sabermos se uma palavra é um anagrama nessa linguagem,
perm([], []).
perm(L, [H|T]) :- select(H, L, T), perm(R,T).

file_to_list(FILE, LIST) :-
	see(FILE), inquire([], LIST), seen.

inquire(IN, OUT) :-
	read(Data == end_of_file -> OUT = IN; atom_codes(Data, LData), inquire(LData|IN, OUT).

find_anagram(Dic, A, S) :-
	file_to_list(Dic, L), perm(A, X), member(X, L), name(S, X).

// Bem nao consegui copiar tudinho eu acho. mas isso acho que foi quase tudo.
// Fim da aula!