Prolog é uma linguagem de programação geralmente usada para inteligência artificial e linguística computacional.

Grafo em árvore
Faz um tempo que eu não uso Prolog então esse é meio um tutorial relâmpago para eu relembrar um pouco. São um apanhado de exemplos básicos e um guia de instalação e uso do swi-prolog no Ubuntu.

Instalação e Uso

No Ubuntu há duas implementações de prolog disponíveis, a gprolog e a swi-prolog. Eu vou ficar com o swi-prolog que é um interpretador de prolog. Para instala-lo:

sudo apt-get install swi-prolog

Isso vai instalar o binário swipl que é o interpretador de Prolog.

Exemplo 1 - Fatorial

Crie um arquivo chamado fatorial.pl com esse conteúdo:

factorial(0,1). 

factorial(N,F) :-
   N>0,
   N1 is N-1,
   factorial(N1,F1),
   F is N * F1.

Estando na mesma pasta do arquivo, chame o interpretador swipl:

$ swipl
Welcome to SWI-Prolog (Multi-threaded, Version 5.6.14)
Copyright (c) 1990-2006 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['fatorial.pl'].
% fatorial.pl compiled 0.00 sec, 760 bytes

Yes
?-

O comando ['arquivo.pl']. (com ponto) vai carregar e interpretar um arquivo chamado arquivo.pl. Algumas “perguntas” que podemos fazer ao programa:

?- fatorial(0,1).
Yes
?- fatorial(10,What).
What = 3628800
Yes

As perguntas feitas foram:

  • Fatorial de 0 é 1?
  • Quanto é o fatorial de 10?

Exemplo 2 - Torres de Hanoi

O famoso problema das Torres de Hanoi. Num arquivo chamado hanoi.pl escreva:

move(1,X,Y,_) :-
    write('Move top disk from '),
    write(X),
    write(' to '),
    write(Y),
    nl.
move(N,X,Y,Z) :-
    N>1,
    M is N-1,
    move(M,X,Z,Y),
    move(1,X,Y,_),
    move(M,Z,Y,X).

Carregando o programa com ['hanoi.pl']. dentro do swipl podemos fazer o teste:

?- move(3,left,right,center).
Move top disk from left to right
Move top disk from left to center
Move top disk from right to center
Move top disk from left to right
Move top disk from center to left
Move top disk from center to right
Move top disk from left to right

yes

Exemplo 3 - Grafo

Suponha o seguinte grafo que será representado no código-fonte:

Um grafo de 5 vértices
Vamos representa-lo no código-fonte a seguir que também possui definições para caminhos e viagens.

edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

path(A,B,Path) :-
       travel(A,B,[A],Q),
       reverse(Q,Path).

travel(A,B,P,[B|P]) :-
       connected(A,B).
travel(A,B,Visited,Path) :-
       connected(A,C),
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path).

Vamos perguntar qual o caminho entre 1 e 5:

?- path(1,5,W).
W = [1, 2, 5]
Yes

De onde veio e para onde vai o caminho 1, 2, 5, 4.

?- path(DE, PARA, [1,2,5,4]).
DE = 1
PARA = 4
Yes

Referencias