Prolog
Prolog é uma linguagem de programação que se alinha ao paradigma da Programação em Lógica Matemática. É uma linguagem de uso geral, mas é especialmente associada à inteligência artificial e à linguística computacional. Ela é composta por uma linguagem puramente lógica, conhecida como Prolog puro, e por uma linguagem concreta que adiciona componentes extra-lógicos ao Prolog puro.
Pontos-chave
- Prolog é uma linguagem de programação baseada em lógica matemática, ideal para IA e linguística computacional.
- Sua origem está em um projeto de processamento de linguagens naturais na Universidade de Marselha em 1971-1972.
- É uma linguagem declarativa que descreve problemas usando fatos e regras lógicas, em vez de passos procedimentais.
- O Prolog utiliza conceitos como unificação, recursão e backtracking para resolver problemas.
- Todos os dados são tratados como 'Termos', cuja natureza é definida pela forma como são declarados (números, strings, variáveis, estruturas).
Imagem: Wladyslaw Sojka · BY-SA · Openverse
A linguagem de programação Prolog surgiu de um projeto focado no processamento de linguagens naturais na Universidade de Marselha. Alain Colmerauer e Robert Pasero trabalharam na parte de linguagem natural, enquanto Jean Trudel e Philippe Roussel cuidaram da dedução. Robert Kowalski, um dos inventores do método de resolução SL, juntou-se ao projeto a convite de Trudel. Isso levou a uma versão preliminar do Prolog no final de 1971 e à versão definitiva no final de 1972.
Imagem: Numerius · BY-ND · Openverse
Prolog é uma linguagem declarativa, o que significa que o programador descreve o problema em vez de detalhar os passos para a solução. Ela opera com uma base de dados de fatos e regras lógicas (implicações 'se... então') que definem o domínio do problema. Um programa Prolog pode ser executado interativamente por meio de consultas (queries) que usam essa base de dados e um mecanismo de unificação para deduzir soluções. A linguagem é baseada em um subconjunto do cálculo de predicados de primeira ordem, especificamente cláusulas de Horn, e sua execução é uma prova de teorema por resolução. Conceitos fundamentais incluem unificação, recursão e backtracking.
Imagem: carulmare · BY · Openverse
Diferente da maioria das linguagens, Prolog não possui tipos de dados distintos no sentido tradicional. Todos os dados são considerados um único tipo, o 'Termo', e sua natureza (número, texto, variável, estrutura) é determinada pela forma como é declarado. Strings são geralmente sequências de caracteres entre aspas e podem ser representadas internamente como listas de códigos de caracteres. O ISO Prolog também permite strings como listas de átomos de um único caractere.
Escopo de Identificadores
Com exceção de números, funções ou predicados construídos, os nomes em Prolog para constantes, variáveis, funções e predicados não têm significado intrínseco e podem ser escolhidos livremente. Duas notações distintas geralmente representam objetos distintos. Assim como em outras linguagens, cada nome tem um escopo, permitindo que nomes de variáveis sejam reutilizados para denotar variáveis diferentes, enquanto outras notações representam o mesmo objeto em todo o programa.
Átomos (Constantes de Texto)
Constantes de texto são introduzidas por átomos. Um átomo é uma sequência de letras, números e underscores, que deve começar com uma letra minúscula. Para átomos não alfanuméricos ou com espaços, usa-se qualquer sequência entre aspas simples (ex: 'um átomo com espaços').
Números
Um número é uma sequência de dígitos que pode incluir '.' (para reais), '-' (para negativos) e 'e' (para notação científica). Algumas implementações de Prolog não diferenciam inteiros de números reais.
Variáveis
Variáveis são declaradas de forma similar aos átomos, mas começam com uma letra maiúscula ou underscore. Em Prolog, uma variável não é um contêiner com valor atribuível como em linguagens imperativas; ela age mais como um padrão que é incrementalmente especificado pela unificação. É como uma incógnita cujo valor, uma vez descoberto, não muda. A variável anônima, escrita como um único underscore (_), significa 'qualquer variável'.
Termos Compostos
Termos compostos são a maneira de expressar estruturas de dados complexas em Prolog. Consistem em uma cabeça (funtor, que é um átomo) e parâmetros (de qualquer tipo) entre parênteses, separados por vírgulas. O número de parâmetros é a aridade do termo. Um termo é identificado por sua cabeça e aridade (ex: funtor/aridade). Átomos e números podem ser vistos como termos de aridade zero (ex: um_atomo/0).
Listas
Listas não são um tipo de dado separado, mas são definidas recursivamente usando o termo '.'/2. O primeiro elemento é a cabeça (H), seguido pelo restante da lista, a cauda (T). Por exemplo, [1, 2, 3] é internamente '.'(1, '.'(2, '.'(3, []))). A sintaxe [H | T] é um atalho comum para construir regras. Listas são processadas recursivamente, tratando o primeiro elemento e depois o restante. O Prolog oferece várias formas convenientes para construir e manipular listas.
Imagem: Roland Berger · BY-SA · Openverse
Programar em Prolog difere da programação procedural. Em Prolog, você fornece fatos e regras a uma base de dados e, em seguida, realiza consultas (queries) a essa base. A unidade fundamental é o predicado, que é postulado como verdadeiro. Um predicado tem uma cabeça e um número de argumentos. Por exemplo, 'gato(tom).' informa que 'tom' é um 'gato', onde 'gato' é a cabeça e 'tom' é o argumento. Predicados expressam fatos sobre o mundo que o programa deve conhecer. É crucial estabelecer uma convenção para a ordem dos argumentos (ex: pai(Ana, Jose) ou pai(Jose, Ana)) e mantê-la consistente para evitar ambiguidades, já que Prolog não interpreta o significado semântico dos nomes.
Imagem: Sandro Halank, Wikimedia Commons · BY-SA · Openverse
O segundo tipo de predicado em Prolog é a regra, também chamada de 'cláusula'. Uma regra como 'luz(acesa) :- interruptor(ligado).' significa que 'luz(acesa)' é verdadeiro SE 'interruptor(ligado)' é verdadeiro. Regras podem usar variáveis, como em 'avô(X, Z) :- pai(X, Y), pai(Y, Z).', que significa 'X é avô de Z se X é pai de Y E Y é pai de Z'. O consequente (cabeça da regra) é escrito primeiro, e o antecedente (corpo) vem depois. A conjunção 'e' é representada por ',', e a disjunção 'ou' por ';'. É possível ter múltiplos predicados no corpo de uma regra unidos por disjunção, mas certas estruturas de regras não são permitidas.
Regras Recursivas
Regras recursivas são essenciais para muitas aplicações em Prolog. Um predicado definido recursivamente deve ter, no mínimo, uma definição não recursiva para evitar laços infinitos. Um exemplo é a definição de ancestralidade: 'ancestral(X, Y) :- pai(X, Y).' e 'ancestral(X, Y) :- pai(X, Z), ancestral(Z, Y).'. É importante ter cuidado com a ordem das unificações em regras recursivas, pois a inversão pode levar a comportamentos inesperados ou laços infinitos.
Imagem: Sandro Halank, Wikimedia Commons · BY-SA · Openverse
Quando o interpretador Prolog recebe uma consulta, ele busca por predicados (fatos diretos ou regras) que correspondam à consulta. Por exemplo, para a regra 'irmaos(X,Y) :- filho(X,Z), filho(Y,Z).', que em lógica de primeira ordem significa '∀X ∀Y ∀Z((filho(X,Z) ^ filho(Y,Z)) → irmaos(X,Y))', uma consulta como 'irmaos(ana, erica).' é avaliada como verdadeira. O interpretador unifica 'ana' com X e 'erica' com Y, expandindo a consulta para 'filho(ana,Z), filho(erica,Z)'. Ele tenta encontrar um Z que satisfaça ambos os 'filho'. Se 'filho(ana,marcia)' não levar a uma solução viável (pois 'filho(erica,marcia)' não é verdadeiro), ele tenta outra opção, como 'filho(ana,tomas)', e se 'filho(erica,tomas)' for verdadeiro, então a consulta é satisfeita.
Negação por Falha
Em Prolog, uma consulta é considerada falsa se não houver nenhuma regra ou fato positivo que a suporte. Isso é conhecido como 'hipótese do mundo fechado', onde se assume que toda a informação relevante está na base de dados. Se um fato não é conhecido como verdadeiro, ele é assumido como falso. A negação por falha é implementada pelo operador prefixo '\+/1' (ou 'not/1' em alguns dialetos), que avalia uma consulta buscando exaustivamente por evidências positivas e falha se nenhuma for encontrada. Por exemplo, 'legal(X) :- \+ ilegal(X).' significa que X é legal se não for possível provar que X é ilegal.
Imagem: Maxxl2 · BY-SA · Openverse
Os operadores de controle em Prolog permitem gerenciar o fluxo de execução e otimizar o desempenho do programa, especialmente em relação ao mecanismo de backtracking.
Backtracking
Backtracking é um procedimento fundamental em Prolog. A busca inicial em um programa segue um padrão de Busca em Profundidade (depth-first search), percorrendo a árvore de cima para baixo e da esquerda para a direita. Quando uma pesquisa falha ou atinge um nó terminal, o mecanismo de backtracking é ativado. Ele faz com que o sistema retorne pelo caminho percorrido para encontrar soluções alternativas. Por exemplo, em uma consulta 'pai(X, Y), filho(Y, Z).', se a busca por 'filho(Y, Z)' falha, o sistema retorna ao ponto onde encontrou uma solução para 'pai(X, Y)' para tentar outra alternativa.
Comando Cut (!)
O comando 'cut' (!) é um operador que indica ao Prolog que sub-objetivos já satisfeitos não precisam ser reconsiderados durante o backtracking, abortando esse processo. Seu uso é crucial para otimizar a velocidade do programa, evitando buscas desnecessárias, e para reduzir o consumo de memória, pois não é preciso armazenar todos os pontos de backtracking. Em certos casos, o 'cut' também previne que o programa entre em laços infinitos. Um exemplo é um código que busca o primeiro filho do sexo masculino e para após encontrá-lo.
Comando Fail
O predicado pré-definido 'fail' sempre falha. Ele pode ser combinado com o operador 'cut' para forçar uma falha. Uma conjunção de objetivos como ':- !, fail.' informa ao Prolog que, se a execução chegou a esse ponto, ele deve abandonar a tentativa de satisfazer a regra. A conjunção falha devido ao 'fail', e o objetivo-pai falha devido ao 'cut'. Um exemplo é 'gosta(ana, X) :- gato(X), !, fail; mamifero(X).', que significa 'Ana gosta de mamíferos, exceto de gatos'.
Imagem: Sandro Halank, Wikimedia Commons · BY-SA · Openverse
Embora Prolog seja uma linguagem lógica e, em teoria, o programador não devesse se preocupar com a execução, é prudente considerar como o algoritmo de inferência funciona para evitar programas excessivamente lentos ou infinitos. Por exemplo, ao contar elementos em uma lista: 'tamanho([], 0).' (lista vazia tem 0 elementos) e 'tamanho([_ | T], N) :- tamanho(T, Y), N is Y + 1.' (se a lista não é vazia, N é 1 mais o tamanho da cauda). Há uma distinção clara entre os casos. No entanto, em um cenário como 'jogar_cassino(X) :- temdinheiro(X). jogar_cassino(X) :- temcredito(X).', onde 'temdinheiro(X)' e 'temcredito(X)' podem ser funções custosas (ex: acessar conta bancária), a ordem e a eficiência da avaliação se tornam importantes.
Imagem: Sandro Halank, Wikimedia Commons · BY-SA · Openverse
Prolog oferece uma notação especial chamada Gramática de Cláusulas Definidas (Definite Clause Grammars - DCGs). Uma regra definida com '-->/2' em vez de ':-/2' é expandida por um pré-processador (expand_term/2, similar a macros) em cláusulas Prolog comuns. DCGs são amplamente utilizadas para escrever parsers e geradores de listas, além de fornecerem uma interface conveniente para operações sobre diferenças de listas.
Imagem: Ma▀▄Ga · BY-SA · Openverse
A seguir, alguns exemplos de programas implementados em ISO-Prolog, demonstrando a aplicação da linguagem em algoritmos conhecidos.
Quicksort
Implementação do algoritmo Quicksort para ordenação de listas em Prolog. Este exemplo ilustra como a lógica declarativa pode ser usada para descrever o processo de divisão e conquista do Quicksort.
Mergesort
Implementação do algoritmo de ordenação Mergesort em Prolog. Similar ao Quicksort, este exemplo demonstra a aplicação da linguagem para um algoritmo de ordenação baseado na divisão da lista e posterior fusão ordenada.
