Introdução ao Prolog

Prolog é uma linguagem de programação que utiliza o paradigma de programação em lógica - especifica o quê e o que lhe deve ser feito. Concebida com o objetivo inicial de resolver problemas associados à inteligência artificial/tradução de linguagem natural, hoje em dia as suas aplicações vão desde a LN/IA à lógica e à computação numérica e simbólica.

Conceitos Básicos

O conceito base por detrás de Prolog é perguntarmos algo à prompt, e com a informação de que dispõe, o programa responde - se souber, dá-nos uma resposta (e diz que conseguiu dá-la). Caso contrário, responde que não sabe responder à pergunta, tendo em conta a informação que tem.

Termos

Um dos conceitos importantes em Prolog é o termo, que, tal como na LPO, consiste numa variável, constante, ou função que as aceita como argumentos (um termo composto, portanto).

Quanto às constantes, estas podem ser átomos ou números. Os átomos podem ser:

• como "nomes" numa LP normal (i.e postMalone, ciDADE, zero), começando sempre por minúscula;
• cadeias de carateres, utilizando plicas. Aqui, a primeira letra pode ser maiúscula (ou até _). São exemplos 'cidade', 'LeBron' e '_poster';
• um átomo especial (! , [ , ] , ; , { , } , + , - , * , / , **), sendo estes últimos pouco utilizados.

Se introduzirmos atom(<argumento>) na prompt, o Prolog devolve true. ou false., conforme o argumento seja um átomo ou não.

Quanto aos números, vamos aqui considerar, como termos, apenas números inteiros. Se introduzirmos number(<argumento>) na prompt, o Prolog devolve true. ou false., conforme o argumento seja um número ou não.

Podemos ainda escrever atomic(<argumento>) para verificar se o argumento é uma constante.

De seguida, passamos às variáveis: começam sempre por maiúscula ou _ (sendo que _ por si só é a variável anónima, utilizada quando o valor da variável não tem interesse numa expressão).

Várias ocorrências de variáveis anónimas numa mesma expressão correspondem a ocorrências distintas, e devem ser tratadas como tal - não é necessariamente a mesma variável em cada sítio!

Podemos escrever var(<argumento>) e nonvar(<argumento>) para verificar se o argumento é uma variável segundo as convenções supra-referidas.

Por fim, temos:

• Termos Compostos - correspondem à aplicação de um functor a um dado número de argumentos. Um functor é necessariamente um átomo. Existem funções pré-embutidas em Prolog, tais como +, *, /. São exemplos vencedor(X), 'vencedor'(_X), +(5, X), 5 + X. De realçar que escrever +(5, X) e 5 + X é exatamente a mesma coisa!

• Literais - corresponde à aplicação de um predicado ao número apropriado de termos (devolve verdadeiro ou falso). Um literal de aridade (nº de argumentos) zero é um átomo. Sintaticamente, não existe diferença entre termos compostos e literais - decidir se é uma coisa ou outra depende do contexto. São exemplos mae(Marge, Bart), filho(Bart, Marge).

Programas

Constituídos por uma sequência de cláusulas determinadas. As cláusulas aceitam literais, funcionando tal como na LPO. Aqui, a implicação $\leftarrow$ é representada por :-.

A noção de cláusula determinada é igual à da LPO: correspondem a cláusulas com cabeça.

Voltamos a ter Afirmações, que funcionam como informações "concretas" dadas aos programa: pai(Homer, Bart) e comprarCigarros(pai, filhoRandom), por exemplo.

Aparecem também de novo as Regras, que correspondem a informações "formais"/regras dadas ao programa: por exemplo, ant(X,Y) :- ad(X, Y).

Os Objetivos são, claro, tudo o que damos à prompt. Tal como na LPO, correspondem a cláusulas com corpo e sem cabeça.

Podemos ainda ter cláusulas iterativas, cláusulas cujo corpo apenas contém um literal, sendo este igual ao utilizado na cabeça da cláusula. Um exemplo seria liga(X, Y) :- liga(Y, X).

Unificação de termos

Voltamos, aqui, a considerar a noção de unificação. Na prompt, escrever <expressão> = <expressão>* para verificar se é unificável, <expressão> \= <expressão> para verificar o contrário.

* O Prolog devolve false. caso não sejam unificáveis. Caso sejam, pode devolver tanto devolver a unificação concreta que torna a expressão verdadeira como true., caso a unificação não tenha uma resposta concreta. Abaixo encontram-se exemplos de tentativas de unificação.

?- a = b.
false.
?- f(X, a) = f(b, X).
false.

---

?- f(X, a) = f(b, Y).
X = b, Y = a.

---

?- X = X.
true.
?- f(_, _) = f(a, b).
true.

Neste último caso, não há uma resposta concreta. Além disso, como podemos observar nesse exemplo, as variáveis anónimas são consideradas variáveis distintas: se não fossem, o Prolog retornaria false.!

Comparação de termos

Na prompt, escrever <expressão> == <expressão> para verificar se são iguais, <expressão> \== <expressão> para verificar o contrário.

?- b == a.
false.
?- 'a' == a.
true.
?- X == a.
false.
?- X = a, X == a.
X = a.

Neste último exemplo, o programa vai primeiro tentar unificar X com a e só depois é que ocorre a comparação, comparação que ocorre agora entre a e a (e que dá, portanto, true.).

Semântica

Para provar um objetivo, o Prolog recorre a uma Resolução SLD com função de seleção, função esta que escolhe o primeiro literal na cláusula objetivo, e com uma regra de procura que escolhe a primeira cláusula que se pode unificar com o literal selecionado da cláusula objetivo, dentro da sequência de cláusulas que corresponde ao programa.

Podemos olhar para a semântica da programação em lógica de duas formas distintas:

Exemplos de resoluções

Consideraremos, nesta secção, o programa

% os comentários começam com percentagens
ad(marge, bart).
ad(srB, marge).

ant(X, Y) :- ad(X, Y).
ant(X, Z) :- ant(X, Y), ad(Y, Z).

Podem testar os exemplos seguintes na GUI do SWI-Prolog ao criar um ficheiro .pl com o código acima, e dentro do SWI-Prolog ir a Consult e escolher esse ficheiro. De seguida, na prompt, escrever os objetivos indicados e verificar a resposta (isto em Windows). Em Linux, instalar a package swi-prolog. Correr swipl <nome do ficheiro> abrirá uma command line interativa, onde podemos interagir com o programa associado ao ficheiro.

Podíamos ainda ter o caso de só haver ramos falhados - nesse caso, o Prolog responderia false., equivalente a "não sei". Esta equivalência tem por base a hipótese do mundo fechado - o Prolog assume que tudo o que não consegue derivar é falso.

Devemos ainda ter em consideração 2 pontos:

• Ao definir um predicado, devemos definir as afirmações (cláusulas só com cabeça) antes das regras; dizemos isto devido às afirmações não terem corpo, e a unificação leva ao desaparecimento do literal (queremos isto o mais "cedo" no programa possível).

• Devemos evitar recursão à esquerda, ou seja, em vez de escrever pred1(A, C) :- pred1(A, B), pred2(B, C). devemos trocar a ordem de pred1(A, B) e pred2(B, C). Caso contrário, poderemos entrar em ciclos infinitos, visto que a função de seleção do Prolog é $\alpha_{1}$, e ao escolher o ramo mais à esquerda estaremos a entrar em recursões infinitas.

Caso haja mais que uma resposta a um dado objetivo dado um programa, podemos continuar a premir ; até o Prolog esgotar os ramos bem sucedidos (nessa situação responderá false. e encerrará).

Listas

Em Prolog, listas são tipos estruturados de informação pré-definidos. Tal como em Python, os seus elementos são separados por vírgulas, estando delimitados por [ ]. Os elementos podem ser termos (variáveis, constantes ou termos compostos) ou outras listas, podendo, claro está, existir a lista vazia ([]).

[]
[a,b,c]
[[], [a, b], c, d]
[X, r(a, b, c), 6]

Uma lista não vazia pode ser vista como sendo constituída por 2 entidades, o primeiro elemento e o resto. Havendo pelo menos um elemento, existe sempre um primeiro elemento; nesta "representação", não tem necessariamente de haver resto. Se houver, o Prolog retorná-lo-á em forma de lista. Utilizamos o padrão [P | R], com o operador |, para separar o Primeiro elemento do Resto. A unificação de [P|R] com uma lista resultará numa interação deste género:

?- [a, b] = [P | R].
P = a,
% podemos observar abaixo que b vem no "formato de lista"
R = [b].
% se ainda não tivesse ficado explícito, as vírgulas indicam que a solução "ainda não acabou",
% enquanto que o ponto e vírgula indica que são soluções distintas

?- [a] = [P | R].
P = a,
R = [].

?- [] = [P | R].
false.
% não há unificação possível, visto que não há primeiro elemento

Exemplos de programas envolvendo listas

% membro(E, L) - E é membro da lista L.
membro(E, [E|_]).
membro(E, [_|R]) :- membro(E, R).

?- membro(a, [a, b, c]).
true.
?- membro(c, [f, g, h]).
false.
?- membro(a, []).
false.
?- membro([a, b], [a, [a, b], c]).
true.
?- membro(X, [a, b, c]).
X = a;
X = b;
X = c;
false.

% lista da qual a é o primeiro elemento, e a variável _G268 é o resto
X = [a|_G268];
% lista da qual a é o segundo elemento, e por aí em diante
X = [_G8, a|_G12];
X = [_G8, _G11, a|_G15];
X = [_G8, _G11, _G14, a|_G18];
X = [_G8, _G11, _G14, _G17, a|_G21.
% porque é que o Prolog dá estes nomes às variáveis? Não faço a menor ideia
% segundo a Prof, "começam por um _ e
% seguem-se uma série de caracteres que não nos interessam"
% take that as you will

% utilização do | em conjunto com a variável anónima, _, para separar elementos
?- [a, b, c] = [_, Y | Z].
Y = b,
Z = [c].
?- [a, b, c] = [_, _, Y | Z].
Y = c,
Z = [].

% utilização do operador | para aceder a elementos de uma lista
?- [1, 2, 3, 4] = [Prim, Seg, Terc | R].
Prim = 1,
Seg = 2,
Terc = 3,
R = [4].
?- [1, 2, 3] = [Prim, Seg, Terc | R].
Prim = 1,
Seg = 2,
Terc = 3,
R = [].
?- [1, 2] = [Prim, Seg, Terc | R].
false.
% relembrar que Prim, Seg e Terc continuam a ser variáveis
% não havendo uma unificação que envolva as 3, o Prolog devolve false

Encontram-se abaixo dois exemplos de programas relativamente básicos, mas que podem ajudar à familiarização com a linguagem. Recomendo que experimentem escrever os programas sozinhos, indo ver a solução apenas caso fiquem presos (ou, tendo chegado ao fim, para confirmar).

% junta(X, Y, Z) - Z é o resultado de juntar X a Y
junta([], L, L).
% a junção da lista vazia a uma lista qualquer é a própria lista
junta([P | R], L1, [P | L2]) :- junta(R, L1, L2).
% sendo L2 a junção de R a L1,
% a junção de uma lista iniciada por P com resto R a L1 dá uma lista P | L2

?- junta([], [a, b], L).
L = [a, b].
?- junta([c, b], [a], L).
L = [c, b, a].
?- junta([a, b], X, [a, b, c, d]).
X = [c, d].

% temos ainda uma interação mais interessante,
% para descobrir vários "pedaços" que levam a uma lista
?- junta(X, Y, [1, 2]).
X = [],
Y = [1, 2];
X = [1],
Y = [2];
X = [1, 2],
Y = [];
false.
% tivemos 3 soluções diferentes

% inverte(L, LI) - LI é L invertida
inverte([], []).
% a inversão da lista vazia é ela própria
inverte([P | R], LI) :- inverte(R, RI), junta(RI, [P], LI).
% sendo RI a inversão de R, e LI a junção de RI a P,
% a inversão de P|R resultará em LI

?- inverte([a, b, c], [c, b, a]).
true.
% [c, b, a] é [a, b, c] invertida - true
?- inverte([a, b, c], X).
X = [c, b, a].
% encontra a invertida de [a, b, c]
?- inverte(X, [a, b, c]).
X = [c, b, a].
% encontra a lista da qual [a, b, c] é a invertida

inverte([], I, I).
% a invertida da lista vazia corresponde ao acumulador atual
inverte([P | R], Ac, I) :- inverte(R, [P | Ac], I).
% sendo R uma lista com acumulador atual P|Ac,
% então a sua invertida I é igual à lista [P|R] com acumulador atual Ac
inverte(L, I) :- inverte(L, [], I).

Há ainda mais exemplos nos slides e no livro.