Edit page

Meta-Predicados, Arimética, IO, Estruturas

Meta-Predicados sobre Listas

tip

Existe, em Prolog, overloading de predicados: podemos associar o mesmo nome de predicado a aridades diferentes. Sempre que virem a definição de uma função escrita do género <nome_pred>/<numero>, <numero> corresponde ao número de argumentos que a função recebe (a sua aridade, portanto).

Existe um conjunto de predicados built-in em Prolog que nos vão ser muito úteis, tanto no projeto como nas avaliações semanais.

length

Predicado built-in que recebe dois argumentos, uma lista e uma variável, e devolve <variável> = <comprimento>.

% Exemplo de interação
?- length([1,2,3,4,5], L).
L = 5.

append

Recebe dois ou três argumentos, uma ou duas listas e uma variável. Permite interações como as demonstradas abaixo:

% interações com append/3
?- append([1,2,3], [4,5], X).
X = [1,2,3,4,5].
?- append(X, [Ultimo], [1,2,3]).
X = [1,2],
Ultimo = 3.
?- append([1,2,3], Resto, L).
L = [1,2,3 | Resto].

% append/2 aceita uma lista de listas e "alisa-as" 1 nível:
?- append([[1,2], [3]], L).
L = [1, 2, 3].
?- append([[1,2],[3,4], [5,6]], X).
X = [1,2,3,4,5,6].
?- append([[1,2], X, [a,b,c]], [1,2,3,4,5,a,b,c]).
X = [3,4,5].
?- append([[1,2], [[3]]], L).
L = [1, 2, [3]].

maplist

O maplist é um predicado built-in com enormes semelhanças ao map do Python: em FP, vimos que ao dar-lhe uma função como argumento, map retornava o resultado da aplicação dessa função aos elementos da lista argumento. No maplist do Prolog passa-se algo do mesmo género. Ocorre em 4 variantes, maplist/2, maplist/3, maplist/4 e maplist/5, correspondendo os números à quantidade de argumentos que aceita (ao chamar a função, não usamos esta notação, apenas usamos maplist). O primeiro argumento é sempre a função/predicado que queremos utilizar, e os seguintes as listas que queremos que sejam operadas pela função. É natural que não faça muito sentido nas primeiras vezes que utilizarmos este predicado, mas à medida que o tempo vai passando vamos apercebendo-nos das potencialidades do maplist (e da sua simplicidade).

Como nota, é importante referir que para os maplist que aceitam mais que uma lista, todas as listas devem ser do mesmo tamanho.

O último pormenor pode ser reproduzido através de:

% programa:
just_one(1).

% interação
?- maplist(just_one, E).
E = []; % temos de carregar no ; para ver os resultados a aparecer
E = [1];
E = [1,1];
...

% esta interação nunca "para", o que é oposto ao que queremos - uma resposta concisa

Exemplos de interações corretas:

% maplist/2 - chama o predicado e
% verifica se o predicado é verdadeiro para cada elemento da lista

?- maplist(atom, [a, b, c]).
true.
? maplist(nonvar, [X, 1, P]).
false.
% par(N) - N é par
?- maplist(par, [1,2,3,4]).
false.

% dobro(X, Y) - Y é o dobro de X
?- maplist(dobro, [1,2,3,4,5], L).
L = [2,4,6,8,10].

% soma(X, Y, Z) - Z é a soma de X com Y
?- maplist(soma, [1,2,3,4,5], [1,2,3,4,5], L).
L = [2,4,6,8,10].
?- maplist(soma(10), [1,2,3,4,5], L).
L = [11,12,13,14,15].

Talvez seja um pouco difícil de perceber ao início as diferenças entre cada predicado, principalmente nestes com aridades diferentes: experimentem com listas e programas diferentes para tentar perceber o que é que está de facto a acontecer!

include, exclude

Os meta-predicados include e exclude funcionam, tal como o nome indica, de formas diretamente opostas. Ambos recebem 3 argumentos, sendo o primeiro o predicado "filtrador", o segundo a lista que queremos filtrar e a terceira a lista devolvida após o filtro estar concluído.

% programa
is_odd(I) :- 0 =\= I mod 2.
% irá ser abordado mais à frente, mas =\= é "valores de expressões diferentes" e mod é o resto
are_identical(X, Y) :- X == Y.
count_vars(L, Res) :- include(var, L, L_vars), length(L_vars, Res).

% interação
?- include(is_odd, [1,2,3,4,5,6], Odd).
Odd = [1,3,5].
?- exclude(is_odd, [1,2,3,4,5,6], Even).
Even = [2,4,6].
?- exclude(are_identical(3), [1,2,3,4,3,2,1], L).
L = [1,2,4,2,1].
% podemos escrever o objetivo acima de outra maneira, mais interessante
?- exclude(=(3), [1,2,3,4,3,2,1], L).
L = [1,2,4,2,1].
% operações semelhantes ocorrem ao alterar o = por <, >, ...
?- count_vars([1,2,4,X,Y,p, A], L).
L = 3.

findall, setof

O findall e o setof têm estruturas semelhantes:

findall(<termo>, <objetivo>, <lista>).
setof(<termo>, <objetivo>, <lista>).

Ambos funcionam de modo semelhante, <lista> vai ter os termos que satisfaçam <objetivo>. Contudo, <lista> em findall pode conter elementos repetidos, enquanto que em setof isso não ocorre: um set corresponde precisamente a um conjunto sem elementos repetidos e ordenado.

Interações possíveis seriam, por exemplo:

% note-se que member/2 recebe um termo e uma lista, e verifica se
% o termo está presente na lista (devolvendo true/false)

?- findall(X, (member(X, [6,2,4,5,4,7]), X mod 2 =:= 0), L).
L = [6,2,4,4].
?- setof(X, (member(X, [6,2,4,5,4,7]), X mod 2 =:= 0), L).
L = [2,4,6].

Nota

A interação seguinte foi bastante útil no projeto de 2020/2021 - pode, potencialmente, ser útil no projeto do ano curricular em que estão a ver estes resumos, pelo que valerá a pena prestar particular atenção ao mesmo.

% sublist(SL, L, N) - SL é uma sublista de L de comprimento N
sublist(SL, L, N) :- append([_, SL, _], L), length(SL, N).

?- L = [1,2,3,4,5,6], sublist(SL, L, 4).
L = [1, 2, 3, 4, 5, 6],
SL = [1, 2, 3, 4]
L = [1, 2, 3, 4, 5, 6],
SL = [2, 3, 4, 5]
L = [1, 2, 3, 4, 5, 6],
SL = [3, 4, 5, 6]
false.

No programa acima, podemos ler append([_, SL, _], L), que é algo como "SL é uma sublista de L, onde ambos os _ são o que vem (ou não) atrás e à frente de SL em L, mas que não nos interessa". Como queremos todas as sublistas de L de comprimento N, primeiro é devolvida a resposta com os 4 primeiros elementos, de seguida com os elementos de 1 a 5 e por fim com os últimos 4 elementos.

Podemos, ainda, querer uma lista com todas as sublistas - aqui entra o findall:

sublists(L, N, SLs) :- findall(SL, sublist(SL, L, N), SLs).
% aqui, SLs é uma lista com todas as sublistas pretendidas.

?- L = [1,2,3,4,5,6], sublists(L, 4, SLs).
L = [1,2,3,4,5,6],
SLs = [[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]].

Esta implementação tem, contudo, um problema, que provavelmente vão encontrar ao tentar resolver o projeto.

% caso façamos:
?- L = [V1,V2,V3,V4,V5,V6], sublists(L, 4, SLs).
% o que é devolvido é
L = [V1,V2,V3,V4,V5,V6],
SLs = [[_1056, _1062, _1068, _1074], [_1026, _1032, _1038, _1044], [_996, _1002, _1008, _1014]].
% que não é o que queríamos (queríamos uma lista cujas sublistas incluem as variáveis Vn)
% dependendo da aplicação, pode ser irrelevante - no projeto interessa
% porque é que isto acontece? "não me perguntes porque é que faz, mas faz" - prof.

Como é que podemos solucionar isto? Utilizando o bagof, que faz algo muito semelhante ao findall, com a particularidade de no caso de termos uma lista com variáveis, as variáveis (para este propósito) serem tratadas como queremos aqui:

% a diferença entre programas é exclusivamente usar bagof em vez de findall
?- L = [V1,V2,V3,V4,V5,V6], sublistas(L, 4, SLs).
L = [V1, V2, V3, V4, V5, V6],
SLs = [[V1, V2, V3, V4], [V2, V3, V4, V5], [V3, V4, V5, V6]].

% temos ainda que sublistas de tamanho maior que o comprimento de L retornam false
?- L = [V1,V2,V3,V4,V5,V6], sublistas(L, 7, SLs).
false.
% que pode ser um problema, caso quiséssemos, aqui, uma lista vazia em vez de false

% como resolver o problema? adicionar uma cláusula ao programa:
sublists(_, _, []).
% para além disso, adicionar `!` (cuja utilidade será explicada à frente) à cláusula original:
sublists(L, N, SLs) :- bagof(SL, sublista(SL, L, N), SLs), !.
% de notar que a cláusula que vem primeiro é esta última, só depois é que vem a cláusula que adicionámos

Aqui, a utilidade do operador de corte é: "se isto não der falso, continua e não uses mais cláusula nenhuma a seguir; se der, salta esta cláusula e usa o que vier a seguir".

Aritmética

De seguida estão apresentadas algumas operações aritméticas que podem ser úteis:

Operação Significado
A+B, +(A, B) soma entre A e B
A-B, -(A, B) diferença entre A e B
A*B, *(A, B) produto entre A e B
A/B, /(A, B) quociente real entre A e B
A//B, //(A,B) quociente inteiro entre A e B
A^B, ^(A, B), A\*\*B, \*\*(A, B) A elevado a B
-A simétrico de A
sin(A), cos(A), tan(A) seno, cosseno, tangente de A
log(A) logaritmo natural de A (base e, portanto)
abs(A) módulo/valor absoluto de A
sqrt(A) raiz quadrada de A
max(A, B) maior valor entre A e B
min(A, B) menor valor entre A e B
rem(A, B), mod(A, B) resto da divisão inteira entre A e B
gcd(A, B) maior divisor comum entre A e B
lcm(A, B) menor múltiplo comum entre A e B
sign(A) -1 se A < 0, 0 se A == 0, 1 se A > 0
random(A) valor tal que 0 <= valor < A
random_between(A, B) valor tal que A <= valor <= B
round(A) arredonda (para o int + próximo) A
floor(A), ceiling(A), float(A), integer(A) devolve o chão, teto, representação decimal ou representação inteira de A
>>, <<, xor shift left, right, xor
\/ bitwise or (cursed)
/\ bitwise and (cursed)

Temos também operações relacionais:

Operação Significado
>, <, >=, =< vocês conhecem estas (de realçar que aqui usa-se =<, não <=)
A = B true caso A e B unifiquem
A \= B true caso A e B não unifiquem
A == B true caso A e B forem a mesma coisa
A \== B true caso A e B não sejam a mesma coisa
Exp1 =:= Exp2 true caso o valor de Exp1 seja o mesmo que o de Exp2
Exp1 =\= Exp2 true caso o valor de Exp1 não seja o mesmo que o de Exp2

De realçar que ainda há uma variação de >, <, >=, =<, com @ antes do operador, que funciona como uma espécie de strcmp, ou seja, compara dois termos alfabeticamente. Podemos observar uma interação possível no exemplo abaixo:

?- likes(mary, pizza) @< likes(mary, plums).
true.
?- X = +(2, 3).
X = 2+3.
?- 2 + X = Y + 3.
X = 3,
Y = 2.
?- 3 + 5 = 5 + 3.
false.
?- 3 + 5 =:= 5 + 3.
true.
?- X = 9, X + 1 = 10.
false.
?- X = 9, X + 1 == +(9,1).
X = 9.
?- X = 9, X + 1 =:= 10.
X = 9.

Temos ainda o is, onde primeiro é avaliada a expressão da direita e depois há a tentativa de unificação com o termo da esquerda.

% (equivalente a ?- a = 8.)
?- a is 6 + 2.
false.
% (equivalente a ?- 6 + 2 = 8.)
?- 6 + 2 is 6 + 2.
false.
% (equivalente a ?- s(8) = 8.)
?- s(8) is 6 + 2.
false.
% (equivalente a ?- X = 8.)
?- X is 6 + 2.
X = 8.
?- X is 6 + 2, Y is X ** 2.
X = 8,
Y = 64.

Criação do predicado potência, equivalente à operação **:

% potencia(B, E, P) - B elevado a E é P

% qualquer coisa elevada a 0 é 1
potencia(_, 0, 1).

%  caso contrário:
potencia(B, E, P) :-
  E > 0,
  NextE is E - 1,
  potencia(B, NextE, NextRes),
  P is B*NextRes.

Leitura/Escrita

O Prolog, tal como as outras linguagens de programação, também apresenta instruções de leitura e escrita de dados, instruções estas que correspondem a predicados.

Instruções de Leitura

Utilizamos, para leitura, o predicado read/1, que unifica o termo escrito como input com o termo argumento. Para além de na prompt termos de utilizar o ponto final, temos de o escrever também no input.

Interações básicas:

?- read(a).
|: a.
true.
?- read(a).
|: b.
false.
?- X = 5, read(X).
|: 3+2.
false.
?- X = +(3,2), read(X).
|: 3+2.
X = 3+2.
?- read(X).
|: 3 mais 2.
ERROR: Stream user_input:0:72 Syntax error:Operator expected
?- read(X).
|: mais(3,2).
X = mais(3, 2).

Um objetivo que utilize o predicado read só tem sucesso uma vez, isto é, qualquer tentativa posterior será falhada.

% par(X) - X é par.
par(X) :- X mod 2 =:= 0.
% le_e_verifica_par - o número lido é par.
le_e_verifica_par :- read(X), par(X).

?- par(8).
true.
?- le_e_verifica_par.
|: 5.
false.
?- le_e_verifica_par.
|: 6.
true.

Instruções de escrita

Temos, para efeitos de escrita, três predicados pré-definidos: write/1, que escreve o valor do seu argumento e não muda de linha, writeln/1 que escreve o valor do seu argumento e muda de linha e nl/0 que muda de linha.

Interações básicas:

?- write(a),write(5).
a5
true.
?- writeln(a),write(5).
a
5.
true.
?- write(a),nl,write(5).
a
5.
true.
?- read(X),writeln(X + 5).
|: 2.
2+5
X = 2.
?- read(X),Y is X + 5,writeln(Y).
|: 2.
7
X = 2,
Y = 7.

Estruturas

Já vimos anteriormente vários tipos elementares de dados - átomos, números, variáveis, entre outros. Contudo, podemos ainda combinar tipos de dados elementares para construir tipos de dados mais complexos, estruturados. Em Prolog, representá-los-emos através de termos compostos, sendo estes considerados estruturas.

De volta aos velhinhos TADs de FP, sabemos que um tipo de dados tem, por norma, de ter definidos construtores, seletores, reconhecedores e testes.

Tentemos criar uma estrutura chamada data. Essa estrutura poderá ter, por ex., um construtor, faz_data e seletores, ano_de, mes_de e dia_de. Em termos abstratos, podemos considerar a data como um termo de três argumentos, onde data é uma espécie de functor. Assim sendo, a estrutura poderá ser algo do género data(A, M, D), cujos ano, mês e dia são, respetivamente, A, M e D. Com base nesta ideia, podemos construir alguns predicados:

% construtor
faz_data(A, M, D, data(A, M, D)).

% seletores
% para cada seletor, só nos interessa um "atributo", pelo que o resto pode ser
% representado por uma variável anónima
ano_de(data(A, _, _), A).
mes_de(data(_, M, _), M).
dia_de(data(_, _, D), D).

% podemos ainda definir alguns modificadores
% o atributo atual é irrelevante dado que o queremos mudar, pelo que pode
% ser representada por uma variável anónima
muda_ano(A, data(_, M, D), data(A, M, D)).
muda_mes(M, data(A, _, D), data(A, M, D)).
muda_dia(D, data(A, M, _), data(A, M, D)).

Ora, tal como em FP, a utilidade dos TADs por si só não se cinge aos tipos em concreto, mas sim aos programas que com eles podemos criar. No exemplo seguinte, podemos ver precisamente um exemplo disso mesmo, onde utilizamos os TADs definidos anteriormente para alterar uma data:

% prox_ano(Hoje, Futuro) - data equivalente a hoje do próximo ano

prox_ano(Hoje, Futuro) :-
  ano_de(Hoje, A),
  NextYear is A + 1,
  muda_ano(NextYear, Hoje, Futuro).

% interação possível:

?- prox_ano(faz_data(2014, 4, 2), Futuro).
Futuro = data(2015, 4, 2).

Nos slides há um exemplo giro do problema do homem, do lobo, da cabra e da couve, e no livro há um semelhante mas sobre três casas coloridas se quiserem ver mais coisas deste género.

Apenas para Windows

Para correr código de dentro de um programa rapidamente sem criar um ficheiro, pode-se escrever [user]. na prompt, seguido do código para pôr dentro do programa, seguido de Ctrl-D (EOF).