Prolog

Prolog (Programação Lógica) é uma linguagem de programação que se enquadra no paradigma de Programação em Lógica Matemática. É uma linguagem de uso geral que é especialmente associada com a inteligência artificial e linguística computacional. Consiste numa linguagem puramente lógica, que pode ser chamada de Prolog puro, e numa linguagem concreta, a qual acrescenta o Prolog puro com componentes extra-lógicos.

O uso Prolog puro foi originalmente restrito em provas do teorema da resolução com Cláusulas de Horn do formato

H :- B1, …, Bn..

A aplicação do provador de teoremas trata estas cláusulas como procedimentos

para mostrar/resolver H, mostrar/resolver B1 and … and Bn.

O Prolog puro foi então estendido para incluir a negação por falha, na qual condições negativas da forma not(Bi) são mostradas por tentativa e falha para resolver as condições positivas correspondentes Bi).

O nome Prolog para a linguagem concreta foi escolhido por Philippe Roussel como uma abreviação de “PROgrammation en LOGique”. Foi criada em meados de 1972 por Alain Colmerauer e Philippe Roussel, baseados no conceito de Robert Kowalski da interpretação procedimental das cláusulas de Horn. A motivação para isso veio em parte da vontade de reconciliar o uso da lógica como uma linguagem declarativa de representação do conhecimento com a representação procedimental do conhecimento, que era popular na América do Norte no final da década de 1960 para início de 1970.

Muito do desenvolvimento moderno do Prolog veio dos projetos de computadores da quinta geração (FGCS), que desenvolveu uma variante do Prolog chamada Kernel Language para seu primeiro sistema operacional.

Apesar do longo tempo de desenvolvimento, Prolog ainda não é uma linguagem portável, já que cada implementação usa rotinas completamente diferentes e incompatíveis entre si. Por exemplo, um programa trivial que faz um loop de ler uma linha da console e escreve a mesma linha, terminando quando for entrada uma linha vazia, é impossível de ser escrito de forma que qualquer interpretador consiga rodar.

História A linguagem de programação Prolog nasceu de um projeto que não tinha por foco a implementação de uma linguagem de programação, mas o processamento de linguagens naturais. Na Universidade de Marselha, Alain Colmerauer e Robert Pasero trabalhavam na parte de linguagem natural e Jean Trudel e Philippe Roussel trabalhavam na parte de dedução do projeto. Interessado pelo método de resolução SL, Trudel persuadiu um dos seus inventores, Robert Kowalski, que se uniu ao projeto. O projeto resultou em uma versão preliminar da linguagem Prolog em fins de 1971 sendo que a versão definitiva apareceu em fins de 1972.

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 interativo, a partir de consultas (queries) formuladas pelo usuário, 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.

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.

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 asserção (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 utilizado e reutilizado a vontade no programa para denotar variáveis diferentes, enquanto qualquer outra notação representa, ou é, o mesmo objeto para o programa todo.

Átomos As constantes de texto são introduzidas por meio de átomos. Um átomo é uma sequê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 sequência entre aspas simples (ex: 'um átomo contendo espaços').

Um átomo pode ser definido das seguintes maneiras:

começando com letra minúscula: pedro henrique_iv

como uma sequência de caracteres entre aspas simples: 'quem é você?' 'eu não sei'.

Números Um número é uma sequê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.

exemplos: 321 3.21

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 subtraço (_).

exemplos: X Nome Rei_da_Espanha

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 quaisquer 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).

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

o átomo [] é uma lista vazia; 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

Strings Strings são normalmente escritas como uma sequê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.

Fatos Programar em Prolog é bem diferente de programar em uma linguagem procedimental. 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 José é o pai de Ana?

pai(ana,jose). pai(jose,ana).

Em ambos os casos 'pai' é a cabeça e 'ana' e 'jose' são argumentos. Entretanto, no primeiro caso Ana vem primeiro na lista de argumentos, e no segundo, quem vem primeiro é José (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(jose,ana). pai(maria,joao).

Alguns predicados são pre-definidos 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.

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).

(X é avô de Z se X é pai de Y e Y é pai de Z)

Isso significa "se alguém é pai de outra pessoa, que por sua vez é pai de uma terceira, então ele é avô". O antecedente e o consequente estão na ordem inversa do que é normalmente encontrado na notação da lógica: o consequente é escrito primeiro e é chamado a cabeça da regra, o antecedente é chamado corpo. A conjunção (e) é escrita como ",", enquanto a disjunção (ou) é escrita como ";". Também é possível colocar múltiplos predicados em um mesmo corpo, unindo seus antecedentes por disjunção, como 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.

Uma maneira de simular tal regra, usando o operador de negação, é:

a:-c,not(b).

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: