terça-feira, 12 de julho de 2011

Prolog

Certamente Prolog não é meu forte… nunca fiz nada útil em Prolog e não conheço a linguagem tanto quanto gostaria, mas já tive meu samadhi.

Prolog é uma linguagem de programação declarativa de propósito geral, voltada para inteligência artificial e linguística computacional.

Seu nome significa programmation en logique e foi criada no começo da década de 1970 por um grupo liderado por Alain Colmerauer em Marseille, França.

Predicados e domínio


A programação Prolog consiste em definir um conjunto de verdades chamadas fatos e relações entre os fatos, chamadas regras.

De um modo geral, fatos e regras são chamados predicados e o conjunto de predicados do programa é chamado domínio do problema.

Um fato define uma afirmação, uma verdade:
flor(cravo).


Esta linha de código está dizendo «cravo é uma flor», e é um predicado do domínio.

Regra é um predicado condicional:
gosta(ana, X) :- flor(X).


Ana gosta de X se X for uma flor, ou de forma mais precisa: se Ana gosta de X implica que X é um flor, ou seja, leia :- como implica em.

Lembre-se que implicância é uma operação não recíproca.

Consultas


O uso de Prolog se dá através de consultas (queries). Por exemplo, salve as duas linhas acima no arquivo ana.pro, execute o interpretador e digite:
| ?- [ana].
compiling ~/ana.pro for byte code...
~/ana.pro compiled, 2 lines read - 419 bytes written, 14 ms

(1 ms) yes
| ?- gosta(ana, cravo).

yes
| ?- gosta(ana, gato).

no


Tipos


Prolog possui quatro tipos: átomo, termo composto, número e lista. Um fato precisa ser um átomo ou um termo composto.
  • Átomo: é uma constante. Representado por uma sequência de letras, números e underscore iniciada por uma letra minúscula ou uma sequência entre plicas. Ex.: cravo, 'ana.pro', 'Cacilhας, La Batalema'.

  • Termo composto: é uma estrutura complexa. Consiste em um funtor seguido por um ou mais parâmetros entre parêntesis. O funtor deve ser um átomo, os parâmetros podem ser de quaisquer tipos. Ex.: gosta(ana, gato).

  • Número: exatamente o que diz. É representado por dígitos numéricos e ponto (para ponto flutuante.) Ex.: 123, 3.1415.

  • Lista: é uma sequência de elementos de outros tipos. Os delimitadores de início e fim são [] e os elementos são separados por vírgulas. O símbolo pipe (|) por ser usado para representar resto da lista. Ex.: [a, b, c], [abc | SX] (SX é uma lista).

  • String: é um tipo especial de lista que contém apenas números inteiros entre 0 e 255. Ex.: "ABC"[65, 66, 67].


Incógnita


O equivalente a variável em Prolog é a incógnita, que consiste em um valor desconhecido, porém constante, representado por uma sequência similar ao átomo, mas iniciada por uma letra maiúscula.

Por exemplo, em:
gosta(ana, X) :- flor(X).


X é uma incógnita. A solução das consultas feitas acima é obtida encontrando o valor de X, o que é responsabilidade do programa.

Exemplo


Um exemplo clássico de Prolog é a implementação de fatorial:
factorial(0, 1).

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


O que o código diz é que o fatorial de 0 é 1 e se o fatorial de N é F implica que:
  • N é maior que 0 (já está coberto pelo predicado anterior);
  • N1 é igual a N menos 1;
  • O fatorial de N1 é F1;
  • E F é igual a N vezes F1.


Uso:
| ?- [factorial].
compiling ~/factorial.pro for byte code...
~/factorial.pro compiled, 7 lines read - 941 bytes written, 14 ms

(1 ms) yes
| ?- factorial(5, X).

X = 120 ?

yes


Um bom exemplo também é a implementação da solução da torre de Hanói, mas vai fritar seu cérebro:
hanoi(N) :- move(N, esquerda, direita, central).

move(1, X, Y, _) :-
write('mova o disco da torre '),
write(X),
write(' para a torre '),
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).


É claro que isso não é nem o começo. O objetivo é apenas causar água na boca.

[]’s
Cacilhας, La Batalema