Prolog

Origem: Wikipédia, a enciclopédia livre.

O Prolog, acrónimo do francês Programmation en Logique (Programação em Lógica), é uma linguagem de programação que se enquadra no paradigma de Programação em Lógica Matemática, e foi criada por Alain Colmerauer por volta de 1972.

[editar] Características

O Prolog é uma linguagem declarativa, significando que em vez de o programa estipular a maneira de chegar à solução, passo a passo, (como nas linguagens procedimentais ou imperativas), limita-se a fornecer uma descrição do problema que se pretende computar. Usa uma coleção base de dados de fatos e de relações lógicas (regras) que exprimem o domínio relacional do problema a resolver.

Um programa pode rodar num modo interactivo, a partir de perguntas (queries) formuladas pelo utente, usando a base de dados (os 'fatos') e as regras relacionais (essencialmente implicações lógicas: se.. então), e o mecanismo de unificação para produzir (por uma cadeia de deduções lógicas) a solução.

O Prolog é baseado num subconjunto do cálculo de predicados de primeira ordem, o que é definido por cláusulas de Horn. A execução de um programa em Prolog é efetivamente a prova de um teorema por resolução de primeira ordem. Alguns conceitos fundamentais são unificação, recursão, e backtracking.

[editar] Tipos de dados

Prolog não emprega tipos de dados do mesmo modo que as linguagens de programação mais comuns normalmente fazem. Todos os dados são tratados como sendo de um único tipo, Termo, cuja natureza depende da forma como esse termo foi declarado. Ou seja, os elementos léxicos utilizados na sua declaração determinam se esse termo será um número, um texto, uma variável, uma estrutura complexa e assim por diante.

[editar] Escopo dos Identificadores

Com exceção de átomos numéricos, funções ou predicados construídos, os nomes em Prolog para constantes, variáveis, funções e predicados, não têm nenhum significado intrínseco e podem ser escolhidos livremente pelo programador. Em geral, duas notações distintas denotarão ou serão objetos distintos. Como em qualquer linguagem de programação, a cada nome deve ser dado um escopo.

Em Prolog, as regras de escopo são:

• O escopo de uma variável é a assertiva (fato, regra, ou consulta) na qual aparece.
• O escopo de qualquer outro nome (constante, nome de função, ou nome de predicado) é todo o programa.

Isto significa que um nome de variável pode ser usado e reusado a vontade no programa para denotar variáveis diferentes, enquanto qualquer outra notação representa, ou é, o mesmo objeto para o programa todo.

[editar] Átomos

As constantes de texto são introduzidas por meio de átomos. Um átomo é uma seqüência constituída de letras, números e underscore, mas iniciando com uma letra minúscula. Se um átomo não alfanumérico é necessário, pode-se usar qualquer seqüência entre apóstrofos (ex: 'um átomo contendo espaços').

[editar] Números

Um número é uma seqüência de dígitos, permitindo também os sinais de . (para números reais), - (número negativo) e e (notação científica). Algumas implementações do Prolog não fazem distinção entre inteiros e números reais.

[editar] Variáveis

Variáveis são declaradas da mesma forma que átomos, porém iniciando com uma letra maiúscula ou underscore. No ambiente Prolog uma variável não é um contêiner cujo valor pode ser atribuído (como ocorre nas linguagens imperativas). Seu comportamento é mais próximo de um padrão, que é incrementalmente especificado pela unificação. Em outras palavras, uma variável Prolog é como uma incógnita, cujo valor é desconhecido a princípio mas, após descoberto, não sofre mais mudanças.

Um tipo especial de variável, a variável anônima (explicada mais adiante), é uma expressão que significa 'qualquer variável', e é escrita como um único underscore(_).

[editar] Termos compostos

Termos compostos são a única forma de se expressar estruturas de dados complexas em Prolog. Um termo composto consiste de uma cabeça, também chamada funtor (que é obrigatoriamente um átomo) e parâmetros (de quaiquer tipos) listados entre parênteses e separados por vírgulas.

O número de parâmetros, chamado aridade do termo, é significativo. Um termo é identificado por sua cabeça e aridade, normalmente escrita como funtor/aridade. Átomos e números também podem ser identificados dessa forma, como um termo de aridade zero (ex: um_atomo/0).

[editar] Listas

Uma lista não é um tipo de dados à parte, mas sim definida por uma construção recursiva (usando o termo '.'/2):

1. o átomo [] é uma lista vazia;
2. se T é uma lista e H é um elemento, então o termo '.'(H, T) é uma lista.

O primeiro elemento, chamado cabeça, é H, que é seguida pelo conteúdo do restante da lista, T, também chamado de cauda. A lista [1, 2, 3] seria representada internamente como '.'(1, '.'(2, '.'(3, []))). Um atalho sintático é [H | T], que é mais usado para construir regras. Uma lista pode ser processada como um todo processando o primeiro elemento, e em seguida o restante da lista, de forma recursiva.

Para conveniência do programador, as listas podem ser construídas e destruídas de várias formas.

• Enumerando os elementos: [abc, 1, f(x), Y, g(A,rst)]
• Precedendo-a com um elemento: [abc | L1]
• Precedendo-a com múltiplos elementos: [abc, 1, f(x) | L2]
• Expandindo o termo: '.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A,rst), [])))))
• O predicado append

[editar] Strings

Strings são normalmente escritas como uma seqüência de caracteres entre aspas. É comum serem representadas internamente como listas de códigos de caracteres, em geral utilizando a codificação local ou Unicode, se o sistema dá suporte a Unicode. O ISO Prolog também permite que strings sejam representadas por uma lista de átomos com um único caractere.

[editar] Fatos

Programar em Prolog é bem diferente de programar em uma linguagem procedural. Em Prolog se fornece fatos e regras para uma base de dados; então se executam consultas ou queries a essa base de dados. A unidade básica do Prolog é o predicado, que é postulado verdadeiro. Um predicado consiste de uma cabeça e um número de argumentos. Por exemplo:

gato(tom).

Isso informa à base de dados o fato que 'tom' é um 'gato'. Formalmente, 'gato' é a cabeça e 'tom' é o único argumento do predicado. Alguns exemplos de consultas que podem ser feitas ao interpretador Prolog baseado nesse fato:

tom é um gato?

?- gato(tom).  
     yes.

que coisas (conhecidas) são gatos?

?- gato(X).  
     X = tom;
     yes.

Predicados são normalmente definidos para expressar algum fato sobre o mundo que o programa deve conhecer. Na maioria dos casos, o uso de predicados requer uma certa convenção. Por exemplo, qual das duas versões abaixo significaria que Bob é o pai de Sally?

pai(sally,bob).
pai(bob,sally).

Em ambos os casos 'pai' é a cabeça e 'sally' e 'bob' são argumentos. Entretanto, no primeiro caso Sally vem primeiro na lista de argumentos, e no segundo, quem vem primeiro é Bob (a ordem nos argumentos é importante). O primeiro caso é um exemplo de definição na ordem Verbo Sujeito Objeto, e o segundo, na ordem Verbo Objeto Sujeito. Como Prolog não entende Português, ambas as versões estão corretas de acordo com seu escopo; no entanto é uma boa prática de programação escolher uma única convenção para ser usada no mesmo programa, para evitar escrever algo como

pai(bob,sally).
pai(jessica,james).

Alguns predicados são predefinidos na própria linguagem, permitindo que os programas Prolog desempenhem atividades rotineiras (como entrada/saída, uso de gráficos e outros tipos de comunicação com o sistema operacional). Por exemplo, o predicado write pode ser usado para saída na tela. Então,

 write('Olá'). 

vai exibir a palavra 'Olá' na tela.

[editar] Regras

O segundo tipo de predicado no Prolog é a regra, também chamada de "cláusula". Um exemplo de uma regra é

luz(acesa) :- interruptor(ligado). 

O ":-" significa "se"; essa regra significa que luz(acesa) é verdadeiro se interruptor(ligado) é verdadeiro. Regras podem também fazer uso de variáveis, como por exemplo,

avo(X,Z) :- pai(X,Y), pai(Y,Z).

Isso significa "se algém é pai de outra pessoa, que por sua vez é pai de uma terceira, então ele é avô". O antecedente e o conseqüente estão na ordem inversa do que é normalmente encontrado na notação da lógica: o conseqüente é escrito primeiro e é chamao a cabeça da regra, o antecedente é chamado corpo. Conjunção (e) é escrito como ",", enquanto disjunção (ou) é escrito como ";". Também é possível colocar múltiplos predicados em um mesmo corpo, unindo seus antecedentes por disjunção, por exemplo:

a :- b;c;d.

que é equivalente às três regras separadas:

a :- b.
a :- c. 
a :- d.

No entanto não são permitidas regras como:

a;b :- c.

Ou seja, "se c então a ou b". Isso é devido à restrição às cláusulas de Horn.

[editar] Regras Recursivas

Regras recursivas devem ser permitidas a fim de tornar a linguagem útil para muitas aplicações. Um predicado definido por uma regra recursiva deve necessariamente ter, no mínimo uma definição não recursiva. Se isto não acontecer, a definição é logicamente mal-formada e o programa ficaria em laço infinito. Um exemplo de regra recursiva seria a definição de uma base de dados sobre relações familiares que responda questões sobre ancestralidade. Isto pode ser definido da seguinte forma:

ancestral(X,Y) :- mãe(X,Y).
ancestral(X,Y) :- pai(X,Y).
ancestral(X,Y) :- mãe(X,Z),ancestral(Z,Y).
ancestral(X,Y) :- pai(X,Z),ancestral(Z,Y).

Além disso, é necessário tomar cuidado com a ordem na qual casamentos são procurados para metas. Se invertermos a ordem nas regras recursivas do predicado ancestral, isto é

ancestral(X,Y) :- ancestral(Z,Y),mãe(X,Z).
ancestral(X,Y) :- ancestral(Z,Y),pai(X,Z).

o programa fará um laço.

[editar] Avaliação

Quando o interpretador recebe uma consulta, ele tenta encontrar predicados que se encaixam à consulta, sejam eles fatos diretos ou regras que possuem o termo consultado como conclusão. Por exemplo:

irmaos(X,Y) :- filho(X,Z), filho(Y,Z).
filho(X,Y) :- pai(Y,X).
filho(X,Y) :- mae(Y,X).
mae(trude, sally).
pai(tom, sally).
pai(tom, erica).
pai(mike, tom).

De acordo com essa base, a seguinte consulta é avaliada como verdadeira:

?- irmaos(sally, erica).
     yes.

O interpretador chega a esse resultado utilizando a regra irmaos(X,Y), unificando sally com X e erica com Y. Isso significa que a consulta pode ser expandida para filho(sally,Z), filho(erica,Z). A resolução dessa conjunção é feita procurando-se todos os pais possíveis para sally. Entretanto, filho(sally,trude) não leva a uma solução viável, porque se Z for substituído por trude, filho(erica,trude) deveria ser verdadeiro, e nenhum fato que afirma (ou alguma regra que pode satisfazer) isso está presente. Então, em vez disso Z é sustituído por tom, descobrindo-se que erica e sally são irmãos de qualquer forma. O código

filho(X,Y) :- pai(Y,X).

pode parecer suspeito. Afinal, não só pais tem filhos. No entanto esse código significa, na verdade, que todo pai tem filhos (da mesma forma que a regra seguinte significa que toda mãe tem filhos). Para descobrir se alguém é pai, pode-se usar o código

?- pai(X,_).

ou

pai(X) :- pai(X,_).

que simplesmente não se importa com quem é o filho (o underscore é uma variável anônima).

[editar] Negação

Tipicamente, uma consulta é avaliada falsa no caso de não estar presente nenhuma regra positiva ou fato que dá suporte ao termo proposto. Isso é chamado hipótese de mundo fechado; assume-se que tudo o que é importante saber está na base de dados, de modo que não existe um mundo exterior que pode possuir evidências desconhecidas. Em outras palavras, se um fato não é conhecido ser verdadeiro (ou falso), assume-se que ele é falso.

Uma regra como

legal(X) :- \+ ilegal(X).

pode ser avaliada somente pela busca exaustiva de todas as coisas que são ilegais e comparando elas com X, e se nenhum fato ilegal for descoberto ser o mesmo que X, X é legal. Isso é chamado negação por falha. O operador prefixo \+/1 usado acima implementa a negação por falha em compiladores ISO Prolog.

[editar] Operadores de Controle

[editar] Backtracking

Backtracking é um procedimento dentro da linguagem Prolog. Uma busca inicial em um programa nesta linguagem segue o padrão Busca em profundidade (depth-first search), ou seja, a árvore é percorrida sistematicamente de cima para baixo e da esquerda para direita. Quando essa pesquisa falha, ou é encontrado um nodo terminal da árvore, entra em funcionamento o mecanismo de Backtracking. Esse procedimento faz com que o sistema retorne pelo mesmo caminho percorrido com a finalidade de encontrar soluções alternativas.

[editar] Comando Cut

O comando cut permite indicar ao Prolog quais submetas já satisfeitas não necessita considerar de novo ao realizar um backtracking. Isto é, ele aborta o processo de backtracking. O uso do comando cut é importante porque permite que o programa rode mais rápido, sem perder tempo com submetas que não contribuem para determinar a resposta da meta. Além disso, o programa ocupará menos memória, pois não será necessário armazenar todas as submetas analisadas (pontos do backtracking). Em alguns casos, o cut evita que o programa entre em laço infinito.

cabeça :- objetivo1, ..., objetivon, !, objetivon+1, ..., objetivon+m

[editar] Comando Fail

O predicado pré-definido fail sempre falha. O operador de corte pode ser combinado com o predicado fail para produzir uma falha forçada. Uma conjunção de objetivos da forma

cabeça :- objetivo1, ..., objetivon, !, fail.

é usada para informar ao PROLOG: se a execução chegou até esse ponto, então pode abandonar a tentativa de satisfazer a regra. A conjunção falha devido ao fail, e o objetivo-pai falha devido ao corte.

[editar] Execução

Prolog é uma linguagem lógica, portanto em teoria o programador não deveria ter de se preocupar com como ela executa. Entretanto, às vezes é prudente levar em conta como o algoritmo de inferência funciona, para evitar que o programa Prolog execute por um tempo denecessariamente longo (ou mesmo infinito).

Por exemplo, pode-se escrever um código para contar o número de elementos em uma lista.

elems([],0).
elems([H|T], X) :- elems(T, Y), X is Y + 1.

Isso simplesmente diz: Se a lista está vazia, o número de elementos é zero. Se a lista não é vazia, então X é um a mais que Y, que por sua vez é o número de elementos no restante da lista, excluído-se seu primeiro elemento.

Nesse caso, existe uma distinção clara entre os casos no antecedente das regras. Mas no caso a seguir, onde se decide por continuar ou não jogando em um cassino:

jogar(X) :- temdinheiro(X).
jogar(X) :- temcredito(X), \+ temdinheiro(X).

Se você tem dinheiro, você continua jogando. Se você perdeu todo o dinheiro, você precisa pegar emprestado, ou então não é possível jogar mais. temdinheiro(X) pode ser uma função muito custosa - por exemplo, ela pode acessar sua conta de banco na internet para verificar seu saldo, o que leva tempo. Entretanto, o mesmo pode-se dizer de temcredito(X).

Em teoria, as implementações Prolog poderiam avaliar essas regras fora de ordem, de modo que elas poderiam ser escritas como:

jogar(X) :- temcredito(X), \+ temdinheiro(X).
jogar(X) :- temdinheiro(X).

Isso está correto, porque as duas opções se excluem mutuamente. Entretanto, verificar se você precisa de um empréstimo não é necessário se você já sabe que tem dinheiro. Então, na prática, implementações Prolog vão verificar a primeira regra primeiro (de fato, a maioria delas vai sempre tentar as regras na ordem em que estão presentes na base). Pode-se usar o operador de corte para informar ao interpretador para não testar a segunda opção se a primeira é suficiente. Por exemplo:

jogar(X) :- temdinheiro(X),!.
jogar(X) :- temcredito(X), \+ temdinheiro(X).

Isso é chamado um operador de corte verde. O ! simplesmente informa ao interpretador para parar de buscar por alternativas. Mas deve-se notar que se você precisa de um empréstimo será necessário verificar a segunda regra, e isso será feito. Verificando o temdinheiro na segunda regra é desnecessário, já que é conhecido o fato de que você não tem, ou a segunda regra não seria sequer avaliada. Então pode-se modificar o código para

jogar(X) :- temdinheiro(X),!.
jogar(X) :- temcredito(X).

Isso é chamado um operador de corte vermelho, porque é arriscado fazer isso. O programa agora depende da colocação correta do operador de corte e da ordem das regras para determinar seu significado lógico. Acidentes de recorta-e-cola por exemplo são comuns e difíceis de detectar. Se as regras forem misturadas, você pode terminar estourando seu cartão de crédito antes de gastar seu dinheiro.

[editar] Exemplos de código

[editar] Quicksort

split(H, [A|X], [A|Y], Z) :-
  order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :-
  not(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).
quicksort([], X, X).
quicksort([H|T], S, X) :-
  split(H, T, A, B),
  quicksort(A, S, [H|Y]),
  quicksort(B, Y, X).

[editar] Torre de Hanoi

hanoi(N) :- move(N, left, centre, right).
move(0, _, _, _) :- !.
move(N, A, B, C) :-
  M is N-1,
  move(M, A, C, B), inform(A, B), move(M, C, B, A).
inform(X, Y) :-
  write('move a disc from the '),write(X), write(' pole to the '), write(Y), write(' pole'),
  nl.

[editar] Mergesort

split([], K, [], []).
split(XS, K, [], XS)            :-
        K < 1.
split([X|XS], K, [X|YS], ZS)    :-
        K >= 1,
        P is K -1,
        split(XS, P, YS, ZS).

merge1([], [], []).
merge1(XS, [], XS).
merge1([], YS, YS).
merge1([X|XS], [Y|YS], [X|ZS])  :-
        X =< Y,
        merge1(XS, [Y|YS], ZS).
merge1([X|XS], [Y|YS], [Y|ZS])  :-
        Y < X,
        merge1([X|XS], YS, ZS).

mergesort([], []).
mergesort([X], [X]).
mergesort([X, Y], [X, Y])       :-
        X =< Y, !.
mergesort([X, Y], [Y, X])       :-
        X > Y, !.
mergesort(XS, ZS)               :-
        length(XS, L),
        L > 0,
        K is L / 2,
        split(XS, K, XS1, XS2),
        mergesort(XS1, YS1),
        mergesort(XS2, YS2),
        merge1(YS1, YS2, ZS), !.

[editar] Implementações

• LPA Prolog (http://www.lpa.co.uk/)
• Open Prolog (http://www.cs.tcd.ie/open-prolog/)
• Ciao Prolog (http://www.clip.dia.fi.upm.es/Software/Ciao)
• GNU Prolog (http://gnu-prolog.inria.fr)
• YAP Prolog (http://www.ncc.up.pt/~vsc/Yap)
• SWI Prolog (http://www.swi-prolog.org)
• SICStus Prolog (http://www.sics.se/sicstus/)
• Amzi! Prolog (http://www.amzi.com/)
• B-Prolog (http://www.probp.com/)
• TuProlog (http://tuprolog.sourceforge.net/)
• XSB (http://xsb.sourceforge.net/)
• Trinc Prolog (http://www.trinc-prolog.com)
• Strawberry Prolog (http://www.dobrev.com/)
• hProlog ( http://www.cs.kuleuven.ac.be/~bmd/hProlog/ )
• ilProlog ( http://www.pharmadm.com/dmax.asp )
• CxProlog ( http://ctp.di.fct.unl.pt/~amd/cxprolog/ )
• NanoProlog ( http://ctp.di.fct.unl.pt/~amd/cxprolog/ )
• Visual Prolog ( http://visual-prolog.com/ )

[editar] Extensões

• Visual Prolog ( http://www.visual-prolog.com/ ), também conhecido como PDC Prolog e Turbo Prolog. Visual Prolog é um dialeto de Prolog fortemente tipado que é consideravelmente diferente do Prolog padrão. Foi desenvolvido e divulgado como Turbo Prolog enquanto sob controle da Borland, mas hoje é desenvolvido pela empresa Danish PDC (Prolog Development Center) que foi quem o criou.

[editar] Referências

• http://www.ulbra.tche.br/~danielnm/ia/intpro/intpro.html (não encontrado)
• Runnable examples
• A Prolog interpreter in a Java applet
• Prolog: The ISO standard
• Fundamental Prolog Tutorial
• Prolog Tutorial
• Visual Prolog Tutorial
• Visual Prolog Examples
• Prolog Development Center
• Alain Colmerauer's and Philippe Roussel's account of the birth of Prolog
• BEBREGAL, Benjamín Callejas; ACIOLY, Benedito Melo Lógica para Ciência da Computação