Pequeno glossário de Prolog

Ontem eu escrevi um artigo simples sobre Prolog.

O artigo na Wikipédia em português me pareceu pouco completo e bastante confuso. Tem informações legais lá, mas em comparação com a versão em inglês deixa a desejar.

Não pretendo completar o que está escrito na Wikipédia (senão deveria completar lá), apenas descomplicar um pouco.

Pra começar, é preciso entender a estrutura de um programa em Prolog: consiste em um domínio de verdades, parecido com uma base de dados, e o ponto de entrada é uma pergunta (query). Dito isso, vamos definir os conceitos dentro do código:

• Termo: qualquer dado em Prolog é chamado termo.
• Átomo: é um nome de propósito geral sem significado inerente. É representado por uma sequência de letras e alguns caracteres, começando por uma letra minúscula, ou qualquer sequência entre piclas ('…'). Por exemplo: hanoi
• Número: pode ser inteiro ou de ponto flutuante, não diferente de outras linguagens.
• Termo composto: consiste em um átomo, chamado functor (que é uma cabeça ou cabeçalho) seguido de uma sequência de termos e/ou incógnitas separados por vírgulas e entre parêntesis, chamada argumentos. Por exemplo: hanoi(5, R)
• Predicado: é uma função booleana, ou seja, que retorna verdadeiro ou falso. Um predicado pode ser um átomo ou um termo composto e deve ser definido por um fato ou por uma regra.
• Operador: é um predicado normal de aridade 2, mas que pode ser representado de forma diferente. Por exemplo, o sinal de igual:

X = 2

É o mesmo que:

'='(X, 2)

• Variável: prefiro evitar a expressão “variável”, pois ela é falsa, apesar de ser o nome oficial. Prefiro “incógnita”: a incógnita pode estar ligada (bound) ou não (unbound) a um termo e tem comportamento diferente de acordo com estar ou não ligada. É representada por uma sequência de letras iniciando por uma letra maiúscula ou um underscore (_). Por exemplo: X
• Fato: indica que determinado predicado retorna verdadeiro. É um átomo ou termo composto seguido de um ponto. Por exemplo:

default(5).

• Regra: condiciona o resultado de um predicado ao resultado de outro. É um átomo ou termo seguido de :- e então o predicado ao qual ele está condicionado. Por exemplo:.

move(_, X, Y, _, R) :- move(1, X, Y, _, R).

• Pergunta (query): É a chamada de um predicado. Pode retornar verdadeiro, falso ou gerar uma exceção. No código, é uma linha iniciada por :- e terminada por ponto. No prompt ?- basta digitar o predicado seguido de um ponto e pressionar a tecla Enter.

Um detalhe importante é que coisas que não parecem predicados, também são! Por exemplo:

• Vírgula: é operador (','/2) que avalia o primeiro um predicado (argumento) e só avalia o segundo se o primeiro for verdadeiro, ou seja, E lógico.

N1 is N - 1, fact(N1, F1)

• Ponto e vírgula: operador (';'/2) que avalia o primeiro predicado e só avalia o segundo se o primeiro for falso, ou seja, OU lógico.
• Exclamação: é um predicado de aridade 0 ('!'/0) que indica que, se a regra atual “casar” (match) com a pergunta, os próximos fatos ou regras não serão avaliados.
• Qualquer operação matemática.

Como exemplo, segue uma implementação da resolução da torre de Hanói:

% -*- Prolog -*-
:- module(hanoi, [hanoi/0, hanoi/1, hanoi/2]).

hanoi :- hanoi(R), findall(_, show(R), _).
hanoi(R) :- default(N), hanoi(N, R).
hanoi(N, R) :- N > 0,
               findall(X,
                       move(N,
                            'a esquerda',
                            'a direita',
                            'o centro', X),
                       R).

default(5).

move(1, X, Y, _, move(X, Y)) :- !.
move(N, X, Y, Z, R) :- N1 is N - 1, move(N1, X, Z, Y, R).
move(_, X, Y, _, R) :- move(1, X, Y, _, R).
move(N, X, Y, Z, R) :- N1 is N - 1, move(N1, Z, Y, X, R).

show(move(X, Y)) :- format('mova o disco d~w para ~w~n', [X, Y]).
show([X|_]) :- show(X).
show([_|Rest]) :- show(Rest).

Consegue entender como funciona?

Para gerar um executável com SWI Prolog:

bash$ prolog -f hanoi.pl \
-g 'use_module(library(save)), qsave_program(hanoi, [goal(hanoi)])' \
-t halt

Bônus

Há um açúcar sintático em prolog, que é -->:

a --> b, c(x), d.

Significa o mesmo que:

a(Start, End) :- b(Start, V1), c(x, V1, V2), d(V2, End).

[]’s
ℭacilhας, ℒa ℬatalema