Introdução à programação em PROLOG

Prévia do material em texto

INTRODUÇÃO À PROGRAMAÇÃO
PROLOG
Luiz A. M. Palazzo
Editora da Universidade Católica de Pelotas / UCPEL
Rua Félix da Cunha, 412 - Fone (0532)22-1555 - Fax (0532)25-3105
Pelotas - RS - Brasil
EDUCAT
Editora da Universidade Católica de Pelotas
Pelotas, 1997
©
 1997 LUIZ A. M. PALAZZO
SUMÁRIO
1. LÓGICA E PROGRAMAÇÃO DE COMPUTADORES 1
1.1 AS RAÍZES 1
1.2 PROGRAMAÇÃO EM LÓGICA 2
1.3 APLICAÇÕES 4
1.4 A QUINTA GERAÇÃO 6
1.5 PORQUE ESTUDAR PROLOG 8
RESUMO 9
2. A LINGUAGEM PROLOG 11
2.1 FATOS 11
2.2 REGRAS 14
2.3 CONSTRUÇÕES RECURSIVAS 17
2.4 CONSULTAS 19
2.5 O SIGNIFICADO DOS PROGRAMAS PROLOG 21
RESUMO 22
EXERCÍCIOS 22
3. SINTAXE E SEMÂNTICA 24
3.1 OBJETOS 24
3.2 UNIFICAÇÃO 27
3.3 SEMÂNTICA DECLARATIVA E SEMÂNTICA PROCEDIMENTAL 28
3.4 SEMÂNTICA OPERACIONAL 30
RESUMO 30
EXERCÍCIOS 31
4. OPERADORES E ARITMÉTICA 33
4.1 OPERADORES 33
4.2 ARITMÉTICA 36
RESUMO 38
EXERCÍCIOS 39
5. PROCESSAMENTO DE LISTAS 41
5.1 REPRESENTAÇÃO DE LISTAS 41
5.2 OPERAÇÕES SOBRE LISTAS 42
5.3 OUTROS EXEMPLOS 48
RESUMO 49
EXERCÍCIOS 50
6. CONTROLE 51
6.1 BACKTRACKING 51
6.2 O OPERADOR "CUT" 52
6.3 APLICAÇÕES DO CUT 56
6.4 NEGAÇÃO POR FALHA 57
6.5 CUIDADOS COM O CUT E A NEGAÇÃO 58
RESUMO 60
EXERCÍCIOS 60
7. ESTRUTURAS DE DADOS 62
7.1 RECUPERAÇÃO DE INFORMAÇÕES 62
7.2 ABSTRAÇÃO DE DADOS 64
7.3 UM AUTÔMATO FINITO NÃO-DETERMINÍSTICO 65
7.4 PLANEJAMENTO DE ROTEIROS AÉREOS 67
RESUMO 69
EXERCÍCIOS 69
8. ENTRADA E SAÍDA 71
8.1 ARQUIVOS DE DADOS 71
8.2 PROCESSAMENTO DE ARQUIVOS DE TERMOS 73
8.3 PROCESSAMENTO DE CARACTERES 77
8.4 CONVERSÃO DE TERMOS 78
8.5 LEITURA DE PROGRAMAS 79
RESUMO 80
EXERCÍCIOS 80
9. PREDICADOS EXTRALÓGICOS 82
9.1 TIPOS DE TERMOS 82
9.2 CONSTRUÇÃO E DECOMPOSIÇÃO DE TERMOS 84
9.3 EQUIVALÊNCIAS E DESIGUALDADES 85
9.4 PROGRAMAS OU BASES DE DADOS? 86
9.5 RECURSOS PARA O CONTROLE DE PROGRAMAS 89
9.6 BAGOF, SETOF E FINDALL 89
RESUMO 91
EXERCÍCIOS 91
10. LÓGICA E BASES DE DADOS 93
10.1 BASES DE DADOS RELACIONAIS 93
10.2 RECUPERAÇÃO DE INFORMAÇÕES 95
10.3 ATUALIZAÇÃO DA BASE DE DADOS 96
10.4 MODELAGEM DE DADOS 97
10.5 ALÉM DO MODELO RELACIONAL 99
10.6 REDES SEMÂNTICAS 99
RESUMO 103
EXERCÍCIOS 103
11. PROGRAMAÇÃO SIMBÓLICA 105
11.1 DIFERENCIAÇÃO SIMBÓLICA 105
11.2 MANIPULAÇÃO DE FÓRMULAS 105
11.3 OS OPERADORES REVISITADOS 105
11.4 AVALIAÇÃO DE FÓRMULAS 106
11.5 SIMPLIFICAÇÃO ALGÉBRICA 107
11.6 INTEGRAÇÃO 109
RESUMO 109
EXERCÍCIOS 110
12. METODOLOGIA DA PROGRAMAÇÃO EM LÓGICA 111
12.1 PRINCÍPIOS GERAIS DA BOA PROGRAMAÇÃO 111
12.2 COMO PENSAR EM PROLOG 112
12.3 ESTILO DE PROGRAMAÇÃO 114
12.4 DEPURAÇÃO DE PROGRAMAS 116
12.5 EFICIÊNCIA 117
12.6 PROGRAMAÇÃO ITERATIVA 122
RESUMO 123
EXERCÍCIOS 124
13. OPERAÇÕES SOBRE ESTRUTURAS DE DADOS 125
13.1 CLASSIFICAÇÃO EM LISTAS 125
13.2 REPRESENTAÇÃO DE CONJUNTOS 127
13.3 DICIONÁRIOS BINÁRIOS 129
13.4 INSERÇÃO E REMOÇÃO DE ITENS EM DICIONÁRIOS BINÁRIOS 130
13.5 APRESENTAÇÃO DE ÁRVORES 133
13.6 GRAFOS 133
RESUMO 138
EXERCÍCIOS 139
14. ESTRATÉGIAS PARA A SOLUÇÃO DE PROBLEMAS 140
14.1 CONCEITOS BÁSICOS 140
14.2 PESQUISA EM PROFUNDIDADE 143
14.3 PESQUISA EM AMPLITUDE 146
14.4 PESQUISA EM GRAFOS, OTIMIZAÇÃO E COMPLEXIDADE 150
RESUMO 151
EXERCÍCIOS 151
15. PESQUISA HEURÍSTICA 153
15.1 BEST-FIRST SEARCH 153
15.2 UMA APLICAÇÃO DA PESQUISA HEURÍSTICA 158
RESUMO 160
EXERCÍCIOS 161
16. REDUÇÃO DE PROBLEMAS E GRAFOS E/OU 162
16.1 REPRESENTAÇÃO DE PROBLEMAS 162
16.2 EXEMPLOS DE REPRESENTAÇÃO DE PROBLEMAS EM GRAFOS E/OU 165
16.3 PROCEDIMENTOS BÁSICOS DE PESQUISA EM GRAFOS E/OU 167
16.4 PESQUISA HEURÍSTICA EM GRAFOS E/OU 170
RESUMO 178
EXERCÍCIOS 178
APÊNDICE A 179
A.2 SEMÂNTICA MODELO-TEORÉTICA 182
A.3 SEMÂNTICA PROVA-TEORÉTICA 189
BIBLIOGRAFIA 191
Tanto pelo privilégio da amizade de vários anos, como pela condição de colega profissional
do prof. Luiz Antonio Palazzo, já há muito acompanho sua contribuição à cultura em Ciência
da Computação na região em que trabalhamos (zona sul do Rio Grande do Sul). Com gradu-
ação e pós-graduação pela UFRGS, vem marcando sua atuação desde a época de estudante,
tanto no meio acadêmico como na comunidade em geral, por uma postura de vanguarda na
busca de tecnologias para um uso racional e eficiente da computação. Sem dúvida, este livro
permitirá que um número maior de pessoas se beneficiem de sua larga experiência no ofício
de ensinar.
A estrutura do livro mescla o contexto histórico da Inteligência Artificial (IA) com o estudo
do Prolog, uma das mais difundidas linguagens para Programação em Lógica. O conteúdo,
por sua vez, tem como ponto alto contemplar uma rigorosa conceituação formal, cujo empre-
go é caracterizado por exemplos claros e significativos.
O emprego das linguagens para Programação em Lógica ganhou significativo impulso com o
projeto Japonês de Sistemas Computacionais de Quinta Geração (1982-1992), o qual investi-
gou alternativas de hardware e software para atender o desenvolvimento de aplicações que
contemplavam metas ambiciosas, tais como reconhecimento de imagens, processamento da
linguagem natural, processamento de conhecimento, etc.
As linguagens para Programação em Lógica, a exemplo do Prolog, outrora empregadas
principalmente na prototipação, já podem ser utilizadas para resolver, com bom desempenho,
complexos problemas reais de IA. Isto se tornou possível pela disponibilidade de processado-
res poderosos a custos reduzidos, bem como pela disseminação do uso de arquiteturas para-
lelas.
Neste trabalho são ressaltadas, com muita propriedade, as vantagens do emprego da lógica
clausal para programação de computadores, resgatando a "elegância" das linguagens para
Programação em Lógica, nas quais o programador tem como principal preocupação a espe-
cificação em Prolog do problema a ser resolvido, ficando a cargo do sistema computacional
a gerência dos mecanismos de busca das possíveis soluções.
Esta obra moderna, das poucas em português no seu estilo, vem preencher uma lacuna edito-
rial, trazendo a estudantes e profissionais da ciência da computação uma abordagem ampla,
porém não menos crítica e objetiva, das perspectivas do uso da Programação em Lógica.
Adenauer Corrêa Yamin
Pelotas, RS
1
1. LÓGICA E PROGRAMAÇÃO DE COMPUTADORES
A lógica é a ciência do pensamento correto1. Esta declaração não implica contudo em afirmar que ela
seja a ciência da verdade. Mesmo que tudo o que se permita afirmar dentro da lógica seja suposta-
mente verdadeiro em determinado contexto, as mesmas afirmações podem resultar falsas se aplicadas
ao mundo real. Os filósofos da lógica afirmam que, "para entender o que realmente acontece no mun-
do, precisamos entender o que não acontece", isto é, as propriedades invariantes das entidades ou
objetos que o compõem. Com essa idéia em mente, podemos considerar lógicos os conjuntos de de-
clarações que possuem a propriedade de ser verdadeiros ou falsos independentemente do tempo ou
lugar que ocupam no universo considerado. Este insigth inicial costuma ser de grande valia para en-
tender como a lógica pode ser empregada na programação de computadores com grande vantagem
sobre as linguagens convencionais. O cálculo proposicional, que é o subconjunto da lógica matemáti-
ca mais diretamente envolvido nesse processo, formaliza a estrutura lógica mais elementar do discurso
definindo precisamente o significado dos conetivos e, ou, não, se...então e outros. No presente capí-
tulo esboça-se a forma como evoluiu a idéia de empregar a lógica como linguagem de programação de
computadores, comenta-se os principais usos e aplicações das linguagens baseadas na lógica, relata-se
os resultados mais significativos obtidos ao longo dos dez anos do controvertido projeto japonês para
o desenvolvimento dos denominados "Computadores de Quinta Geração" e, por fim, se tenta antecipar
as perspectivas mais promissoras da pesquisa neste ramo do conhecimento científico.
1.1 AS RAÍZES
O uso da lógicana representação dos processos de raciocínio remonta aos estudos de Boole (1815-
1864) e de De Morgan (1806-1871), sobre o que veio a ser mais tarde chamado "Álgebra de Boole".
Como o próprio nome indica, esses trabalhos estavam mais próximos de outras teorias matemáticas do
que propriamente da lógica. Deve-se ao matemático alemão Göttlob Frege no seu "Begriffsschrift"
(1879) a primeira versão do que hoje denominamos cálculo de predicados, proposto por ele como uma
ferramenta para formalizar princípios lógicos. Esse sistema oferecia uma notação rica e consistente
que Frege pretendia adequada para a representação de todos os conceitos matemáticos e para a for-
malização exata do raciocínio dedutivo sobre tais conceitos, o que, afinal, acabou acontecendo.
No final do século passado a matemática havia atingido um estágio de desenvolvimento mais do que
propício à exploração do novo instrumento proposto por Frege. Os matemáticos estavam abertos a
novas áreas de pesquisa que demandavam profundo entendimento lógico assim como procedimentos
sistemáticos de prova de teoremas mais poderosos e eficientes do que os até então empregados. Al-
guns dos trabalhos mais significativos deste período foram a reconstrução axiomática da geometria
abstrata por David Hilbert, a aritimética proposta por Giuseppe Peano e a exploração intuitiva da teo-
ria geral dos conjuntos, por Georg Cantor, que também produziu a iluminada teoria dos números
transfinitos. O relacionamento entre lógica e matemática foi profundamente investigado por Alfred
North Whitehead e Bertrand Russel, que em "Principia Mathematica" (1910) demonstraram ser a ló-
gica um instrumento adequado para a representação formal de grande parte da matemática.
Um passo muito importante foi dado em 1930, em estudos simultâneos, porém independentes, reali-
zados pelo alemão Kurt Gödel e o francês Jacques Herbrand. Ambos, em suas dissertações de douto-
rado, demonstraram que o mecanismo de prova do cálculo de predicados poderia oferecer uma prova
formal de toda proposição logicamente verdadeira. O resultado de maior impacto foi entretanto pro-
duzido por Gödel, em 1931, com a descoberta do "teorema da incompleteza dos sistemas de formali-
zação da aritmética". A prova deste teorema se baseava nos denominados paradoxos de auto-
referência (declarações do tipo: "Esta sentença é falsa", que não podem ser provadas nem verdadeiras
 
1
 Na realidade, de uma certa classe de pensamento correto.
2
nem falsas). Em 1934, Alfred Tarski produziu a primeira teoria semântica rigorosamente formal do
cálculo de predicados, introduzindo conceitos precisos para "satisfatibilidade", "verdade" (em uma
dada interpretação), "conseqüência lógica" e outras noções relacionadas. Ainda na década de 30, di-
versos outros estudos - entre os quais os de Alan Turing, Alonzo Church e outros - aproximaram
muito o cálculo de predicados da forma com que é hoje conhecido e estudado.
No início da Segunda Guerra Mundial, em 1939, toda a fundamentação teórica básica da lógica com-
putacional estava pronta. Faltava apenas um meio prático para realizar o imenso volume de computa-
ções necessárias aos procedimentos de prova. Apenas exemplos muito simples podiam ser resolvidos
manualmente. O estado de guerra deslocou a maior parte dos recursos destinados à pesquisa teórica,
nos EUA, Europa e Japão para as técnicas de assassinato em massa. Foi somente a partir da metade
dos anos 50 que o desenvolvimento da então novíssima tecnologia dos computadores conseguiu ofe-
recer aos pesquisadores o potencial computacional necessário para a realização de experiências mais
significativas com o cálculo de predicados.
Em 1958, uma forma simplificada do cálculo de predicados denominada forma clausal começou a
despertar o interesse dos estudiosos do assunto. Tal forma empregava um tipo particular muito sim-
ples de sentença lógica denominada cláusula. Uma cláusula é uma (possivelmente vazia) disjunção de
literais. Também por essa época, Dag Prawitz (1960) propôs um novo tipo de operação sobre os ob-
jetos do cálculo de predicados, que mais tarde veio a ser conhecida por unificação. A unificação se
revelou fundamental para o desenvolvimento de sistemas simbólicos e de programação em lógica.
A programação em lógica em sistemas computacionais, entretanto, somente se tornou realmente pos-
sível a partir da pesquisa sobre prova automática de teoremas, particularmente no desenvolvimento do
Princípio da Resolução por J. A. Robinson (1965). Um dos primeiros trabalhos relacionando o Prin-
cípio da Resolução com a programação de computadores deve-se a Cordell C. Green (1969) que mos-
trou como o mecanismo para a extração de respostas em sistemas de resolução poderia ser empregado
para sintetizar programas convencionais.
A expressão "programação em lógica" (logic programming, originalmente em inglês) é devido a Ro-
bert Kowalski (1974) e designa o uso da lógica como linguagem de programação de computadores.
Kowalski identificou, em um particular procedimento de prova de teoremas, um procedimento com-
putacional, permitindo uma interpretação procedimental da lógica e estabelecendo as condições que
nos permitem entendê-la como uma linguagem de programação de uso geral. Este foi um avanço es-
sencial, necessário para adaptar os conceitos relacionados com a prova de teoremas às técnicas com-
putacionais já dominadas pelos programadores. Aperfeiçoamentos realizados nas técnicas de imple-
mentação também foram de grande importância para o emprego da lógica como linguagem de pro-
gramação. O primeiro interpretador experimental foi desenvolvido por um grupo de pesquisadores
liderados por Alain Colmerauer na Universidade de Aix-Marseille (1972) com o nome de Prolog, um
acrônimo para "Programmation en Logique". Seguindo-se a este primeiro passo, implementações mais
"praticas" foram desenvolvidas por Battani e Meloni (1973), Bruynooghe (1976) e, principalmente,
David H. D. Warren, Luís Moniz Pereira e outros pesquisadores da Universidade de Edimburgo
(U.K.) que, em 1977, formalmente definiram o sistema hoje denominado "Prolog de Edimburgo",
usado como referência para a maioria das atuais implementações da linguagem Prolog. Deve-se tam-
bém a Warren a especificação da WAM (Warren Abstract Machine), um modelo formal empregado
até hoje na pesquisa de arquiteturas computacionais orientadas à programação em lógica.
1.2 PROGRAMAÇÃO EM LÓGICA
Uma das principais idéias da programação em lógica é de que um algoritmo é constituído por dois
elementos disjuntos: a lógica e o controle. O componente lógico corresponde à definição do que deve
ser solucionado, enquanto que o componente de controle estabelece como a solução pode ser obtida.
O programador precisa somente descrever o componente lógico de um algoritmo, deixando o controle
3
da execução para ser exercido pelo sistema de programação em lógica utilizado. Em outras palavras, a
tarefa do programador passa a ser simplesmente a especificação do problema que deve ser soluciona-
do, razão pela qual as linguagens lógicas podem ser vistas simultaneamente como linguagens para
especificação formal e linguagens para a programação de computadores.
Um programa em lógica é então a representação de determinado problema ou situação expressa atra-
vés de um conjunto finito de um tipo especial de sentenças lógicas denominadas cláusulas. Ao contrá-
rio de programas em Pascal ou C, um programa em lógica não é a descrição de um procedimento para
se obter a solução de um problema. Na realidade o sistema utilizado no processamento de programas
em lógica é inteiramente responsável pelo procedimento a ser adotado na sua execução. Um programa
em lógica pode também ser visto alternativamente como uma base de dados, exceto que as bases de
dados convencionais descrevem apenas fatos tais como "Oscar é um avestruz", enquanto que as sen-
tenças de um programaem lógica possuem um alcance mais genérico, permitindo a representação de
regras como em "Todo avestruz é um pássaro", o que não possui correspondência em bases de dados
convencionais. Na figura abaixo se procura explicitar as principais diferenças entre programação con-
vencional e programação em lógica.
PROGRAMAS CONVENCIONAIS PROGRAMAS EM LÓGICA
Processamento Numérico Processamento Simbólico
Soluções Algorítmicas Soluções Heurísticas
Estruturas de Controle e Conhecimento Integradas Estruturas de Controle e Conhecimento Separadas
Difícil Modificação Fácil Modificação
Somente Respostas Totalmente Corretas Incluem Respostas Parcialmente Corretas
Somente a Melhor Solução Possível Incluem Todas as Soluções Possíveis
Figura 1.1 Programas Convencionais x Programas em Lógica
O paradigma fundamental da programação em lógica é o da programação declarativa, em oposição à
programação procedimental típica das linguagens convencionais. A programação declarativa engloba
também a programação funcional, cujo exemplo mais conhecido é a linguagem Lisp. Lembrando en-
tretanto que Lisp data de 1960, a programação funcional é um estilo conhecido há bastante tempo, ao
contrário da programação em lógica, que só ganhou ímpeto a partir dos anos 80, quando foi escolhida
como a linguagem básica do projeto japonês para o desenvolvimento dos denominados computadores
de quinta geração. O ponto focal da programação em lógica consiste em identificar a noção de com-
putação com a noção de dedução. Mais precisamente, os sistemas de programação em lógica reduzem
a execução de programas à pesquisa da refutação das sentenças do programa em conjunto com a ne-
gação da sentença que expressa a consulta, seguindo a regra: "uma refutação é a dedução de uma
contradição".
Pode-se então expressar conhecimento (programas e/ou dados) em Prolog por meio de cláusulas de
dois tipos: fatos e regras2. Um fato denota uma verdade incondicional, enquanto que as regras defi-
nem as condições que devem ser satisfeitas para que uma certa declaração seja considerada verdadei-
ra. Como fatos e regras podem ser utilizados conjuntamente, nenhum componente dedutivo adicional
precisa ser utilizado. Além disso, como regras recursivas e não-determinismo são permitidos, os pro-
gramadores podem obter descrições muito claras, concisas e não-redundantes da informação que de-
sejam representar. Como não há distinção entre argumentos de entrada e de saída, qualquer combina-
ção de argumentos pode ser empregada.
Os termos "programação em lógica" e "programação Prolog" tendem a ser empregados indistinta-
mente. Deve-se, entretanto, destacar que a linguagem Prolog é apenas uma particular abordagem da
programação em lógica. As características mais marcantes dos sistemas de programação em lógica em
geral - e da linguagem Prolog em particular - são as seguintes:
 
2
 Ver o Apêndice A para uma abordagem mais formal.
4
• Especificações são Programas: A linguagem de especificação é entendida pela máquina e é,
por si só, uma linguagem de programação. Naturalmente, o refinamento de especificações é
mais efetivo do que o refinamento de programas. Um número ilimitado de cláusulas diferentes
pode ser usado e predicados (procedimentos) com qualquer número de argumentos são possí-
veis. Não há distinção entre o programa e os dados. As cláusulas podem ser usadas com grande
vantagem sobre as construções convencionais para a representação de tipos abstratos de dados.
A adequação da lógica para a representação simultânea de programas e suas especificações a
torna um instrumento especialmente útil para o desenvolvimento de ambientes e protótipos.
• Capacidade Dedutiva: O conceito de computação confunde-se com o de (passo de) inferência.
A execução de um programa é a prova do teorema representado pela consulta formulada, com
base nos axiomas representados pelas cláusulas (fatos e regras) do programa.
• Não-determinismo: Os procedimentos podem apresentar múltiplas respostas, da mesma forma
que podem solucionar múltiplas e aleatoriamente variáveis condições de entrada. Através de um
mecanismo especial, denominado "backtracking", uma seqüência de resultados alternativos
pode ser obtida.
• Reversibilidade das Relações: (Ou "computação bidirecional"). Os argumentos de um proce-
dimento podem alternativamente, em diferentes chamadas representar ora parâmetros de entra-
da, ora de saída. Os procedimentos podem assim ser projetados para atender a múltiplos propó-
sitos. A execução pode ocorrer em qualquer sentido, dependendo do contexto. Por exemplo, o
mesmo procedimento para inserir um elemento no topo de uma pilha qualquer pode ser usado,
em sentido contrário, para remover o elemento que se encontrar no topo desta pilha.
• Tríplice Interpretação dos Programas em Lógica: Um programa em lógica pode ser seman-
ticamente interpretado de três modos distintos: (1) por meio da semântica declarativa, inerente
à lógica, (2) por meio da semântica procedimental, onde as cláusulas dos programas são vistas
como entrada para um método de prova e, (3) por meio da semântica operacional, onde as cláu-
sulas são vistas como comandos para um procedimento particular de prova por refutação. Essas
três interpretações são intercambiáveis segundo a particular abordagem que se mostrar mais
vantajosa ao problema que se tenta solucionar.
• Recursão: A recursão, em Prolog, é a forma natural de ver e representar dados e programas.
Entretanto, na sintaxe da linguagem não há laços do tipo "for" ou "while" (apesar de poderem
ser facilmente programados), simplesmente porque eles são absolutamente desnecessários.
Também são dispensados comandos de atribuição e, evidentemente, o "goto". Uma estrutura de
dados contendo variáveis livres pode ser retornada como a saída de um procedimento. Essas va-
riáveis livres podem ser posteriormente instanciadas por outros procedimentos produzindo o
efeito de atribuições implícitas a estruturas de dados. Onde for necessário, variáveis livres são
automaticamente agrupadas por meio de referências transparentes ao programador. Assim, as
variáveis lógicas um potencial de representação significativamente maior do que oferecido por
operações de atribuição e referência nas linguagens convencionais.
A premissa básica da programação em lógica é portanto que "computação é inferência controlada".
Tal visão da computação tem se mostrado extremamente produtiva, na medida em que conduz à idéia
de que computadores podem ser projetados com a arquitetura de máquinas de inferência. Grande parte
da pesquisa sobre computação paralela, conduzida hoje nos EUA, Europa e Japão, emprega a progra-
mação em lógica como instrumento básico para a especificação de novas arquiteturas de hardware e o
desenvolvimento de máquinas abstratas não-convencionais.
1.3 APLICAÇÕES
Um dos primeiros usos da programação em lógica foi a representação e análise de subconjuntos da
linguagem natural. Esta foi inclusive a aplicação que motivou Alain Colmerauer a desenvolver a pri-
5
meira implementação da linguagem Prolog. Logo em seguida, outros pesquisadores da área da inteli-
gência artificial propuseram diversas novas aplicações para o novo instrumento. Alguns dos primeiros
trabalhos com Prolog envolviam a formulação de planos e a escrita de compiladores, por Pereira e
Warren (1977), prova de teoremas em geometria por R. Welhan (1976) e a solução de problemas de
mecânica, por Bundy et al. (1979). As aplicações relatadas desde então, multiplicaram-se velozmente.
Concentraremos aqui a atenção em um conjunto das principais áreas investigadas com o concurso da
programação em lógica.
• Sistemas Baseados em Conhecimento (SBCs): Ou knowledge-based systems, são sistemas
que aplicam mecanismos automatizados de raciocínio para a representação e inferência de co-
nhecimento. Tais sistemas costumam ser identificados como simplesmente "de inteligência arti-ficial aplicada" e representam uma abrangente classe de aplicações da qual todas as demais se-
riam aproximadamente subclasses. A tecnologia dos SBCs foi identificada na Inglaterra pelo
Relatório Alvey (1982) como uma das quatro tecnologias necessárias à completa exploração
dos computadores de quinta geração. As outras seriam: interface homem-máquina (MMI), inte-
gração de circuitos em ultra-grande escala (ULSI) e engenharia de software (SE). O relaciona-
mento entre SBCs e a nova geração de computadores é, na verdade, altamente simbiótica, cada
uma dessas áreas é necessária para a realização do completo potencial da outra.
• Sistemas de Bases de Dados (BDs): Uma particularmente bem definida aplicação dos SBCs
são bases de dados. BDs convencionais tradicionalmente manipulam dados como coleções de
relações armazenadas de modo extensional sob a forma de tabelas. O modelo relacional serviu
de base à implementação de diversos sistemas fundamentados na álgebra relacional, que ofere-
ce operadores tais como junção e projeção. O processador de consultas de uma BD convencio-
nal deriva, a partir de uma consulta fornecida como entrada, alguma conjunção específica de
tais operações algébricas que um programa gerenciador então aplica às tabelas visando a recu-
peração de conjuntos de dados (n-tuplas) apropriados, se existirem. O potencial da programação
em lógica para a representação e consulta à BDs foi simultaneamente investigado, em 1978, por
van Emden, Kowalski e Tärnlund. As três pesquisas estabeleceram que a recuperação de dados
- um problema básico em BDs convencionais - é intrínseca ao mecanismo de inferência dos in-
terpretadores lógicos. Desde então diversos sistemas tem sido propostos para a representação de
BDs por meio de programas em lógica.
• Sistemas Especialistas (SEs): Um sistema especialista é uma forma de SBC especialmente
projetado para emular a especialização humana em algum domínio específico. Tipicamente um
SE irá possuir uma base de conhecimento (BC) formada de fatos, regras e heurísticas sobre o
domínio, juntamente com a capacidade de entabular comunicação interativa com seus usuários,
de modo muito próximo ao que um especialista humano faria. Além disso os SEs devem ser ca-
pazes de oferecer sugestões e conselhos aos usuários e, também, melhorar o próprio desempe-
nho a partir da experiência, isto é, adquirir novos conhecimentos e heurísticas com essa intera-
ção. Diversos sistemas especialistas foram construídos com base na programação em lógica,
como por exemplo o sistema ORBI, para a análise de recursos ambientais desenvolvido por Pe-
reira et al. na Universidade Nova de Lisboa.
• Processamento da Linguagem Natural (PLN): O PLN é da maior importância para o desen-
volvimento de ferramentas para a comunicação homem-máquina em geral e para a construção
de interfaces de SBCs em particular. A implementação de sistemas de PLN em computadores
requer não somente a formalização sintática, como também - o grande problema - a formaliza-
ção semântica, isto é, o correto significado das palavras, sentenças, frases, expressões, etc. que
povoam a comunicação natural humana. O uso da lógica das cláusulas de Horn3 para este pro-
pósito foi inicialmente investigado por Colmerauer, o próprio criador do Prolog (1973), e poste-
riormente por Kowalski (1974). Ambos mostraram (1) que as cláusulas de Horn eram adequa-
das à representação de qualquer gramática livre-de-contexto (GLC), (2) permitiam que ques-
 
3
 Assim denominadas em homenagem a Alfred Horn, que primeiro lhes estudou as propriedades, em 1951.
6
tões sobre a estrutura de sentenças em linguagem natural fossem formuladas como objetivos ao
sistema, e (3) que diferentes procedimentos de prova aplicados a representações lógicas da lin-
guagem natural correspondiam a diferentes estratégias de análise.
• Educação: A programação em lógica poderá vir a oferecer no futuro uma contribuição bastante
significativa ao uso educacional de computadores. Esta proposta foi testada em 1978 quando
Kowalski introduziu a programação em lógica na Park House Middle School em Wimbledon,
na Inglaterra, usando acesso on-line aos computadores do Imperial College. O sucesso do em-
preendimento conduziu a um projeto mais abrangente denominado "Lógica como Linguagem
de Programação para Crianças", inaugurado em 1980 na Inglaterra com recursos do Conselho
de Pesquisa Científica daquele país. Os resultados obtidos desde então tem mostrado que a pro-
gramação em lógica não somente é assimilada mais facilmente do que as linguagens convenci-
onais, como também pode ser introduzida até mesmo a crianças na faixa dos 10 a 12 anos, as
quais ainda se beneficiam do desenvolvimento do pensamento lógico-formal que o uso de lin-
guagens como o Prolog induz.
• Arquiteturas Não-Convencionais: Esta área vem se tornando cada vez mais um campo extre-
mamente fértil para o uso da programação em lógica especialmente na especificação e imple-
mentação de máquinas abstratas de processamento paralelo. O paralelismo pode ser modelado
pela programação em lógica em variados graus de atividade se implementado em conjunto com
o mecanismo de unificação. Duas implementações iniciais nesse sentido foram o Parlog, des-
envolvido em 1984 por Clark e Gregory, e o Concurrent Prolog (CP), por Shapiro em 1983. O
projeto da Quinta Geração, introduzido na próxima seção, foi fortemente orientado ao uso da
programação em lógica em sistemas de processamento paralelo.
Muitas outras aplicações poderiam ainda ser citadas, principalmente na área da inteligência artificial,
que tem no Prolog e no Lisp as suas duas linguagens mais importantes. Novas tecnologias de hardwa-
re e software tais como sistemas massivamente paralelos, redes de computadores, assistentes inteli-
gentes, bases de dados semânticas, etc., tornam o uso do Prolog (e de outras linguagens baseadas em
lógica) cada vez mais atraentes
1.4 A QUINTA GERAÇÃO
Em 1979 o governo japonês iniciou estudos para um novo, ambicioso e único projeto na área da com-
putação normalmente denominado Sistemas Computacionais de Quinta Geração cujo objetivo princi-
pal era o desenvolvimento, no espaço de uma década, de hardware e software de alto desempenho,
caracterizando uma nova geração de computadores. O projeto iniciou em 1982 e foi oficialmente en-
cerrado em maio de 1992. Muito foi dito e escrito sobre o projeto, que produziu inúmeros resultados e
diversos subprodutos ao longo desses dez anos. Um de seus principais méritos, entretanto, parece ter
sido chamar a atenção da comunidade científica mundial para as potencialidades da lógica como lin-
guagem de programação de computadores. Sistemas de processamento lógico paralelo derivados do
Prolog foram desenvolvidos para servir como linguagens-núcleo (kernel languages) dos novos equi-
pamentos que seriam produzidos a partir dos resultados do projeto. Considerado um sucesso por seus
dirigentes, o projeto foi entretanto criticado por não haver conseguido colocar as tecnologias desen-
volvidas à disposição do grande público. Em outras palavras: ainda não dispomos hoje (1994) de mi-
crocomputadores pessoais de quinta geração - denominados máquinas PSI (Personal Sequential Infe-
rence machines) - comercialmente viáveis para o grande público. Os resultados teóricos obtidos e os
protótipos construídos foram entretanto de grande valia para que num futuro próximo isso venha a ser
possível. Nestas novas máquinas o papel da linguagem assembly será desempenhado por um dialeto
do Prolog orientado ao processamento paralelo.
Um relatório sobre o projeto, organizado por Ehud Shapiro e David Warren em 1993, reuniu as opini-
ões de diversos pesquisadores dele participantes, entre os quais Kazuhiro Fuchi, seu líder, Robert
Kowalski, Koichi Furukawa, Kazunori Ueda e outros. Todos os depoimentos foram unânimes em
7
declarar que os objetivos do projeto foramplenamente atingidos. Na Figura 1.2 é mostrada uma
adaptação em português do diagrama "de intenções" apresentado por Fuchi, no Fifth Generation
Computer Systems Congress de 1981 (FGCS'81), o congresso que deu a conhecer ao mundo um dos
mais ambiciosos projetos da história da computação.
ANO 1 ANO 5 ANO 10
� Network --- Ótica ---
� Personal Inference Machine (Redução a chips)
Máquina Prolog + �
(Novo Software) LISPAPL
Smalltalk
PS, etc.
Programação:
 em lógica e
 funcional
(comparáveis às máquinas
de grande porte de 1981)
� Ambientes de Programação Inteligentes
� Ambientes de Projeto Orientados à Prototipagem
� Máquinas Altamente Configuráveis (Chips e Módulos)
� Supermáquinas (Realmente Inteligentes)
Nova Linguagem
5G Core Language
(INFERENCE MACHINE)
Data Flow Machine
Database Machine
Paralelismo
Associatividade
� SOFTWARE -----------> Engenharia de Conhecimento
 (Acumulação) --------------------------------------------------------->
 Engenharia de Software (Teorias Básicas)
 Pesquisa em Inteligência Artificial
Solução de Problemas: 
Bases de Conhecimento: 
Simbolismo em Alto 
Nível:
Planejamento
Programação
Prova de Teoremas
Jogos
Entendimento da
Linguagem Natural
Consultas
Figura 1.2 Diagrama Conceitual do Projeto do Computador de Quinta Geração
Segundo o relatório de Shapiro e Warren, um dos primeiros passos do projeto consistiu em definir
uma linguagem de programação em lógica que ao mesmo tempo fosse adequada ao paralelismo do
hardware e aos requisitos sofisticados especificados para o software. Baseada no Parlog e no Cuncur-
rent Prolog, uma equipe de pesquisadores liderada por Kazunori Ueda desenvolveu a linguagem GHC
(Guarded Horn Clauses), que deu origem à KL0 (Kernel Language Zero). Um refinamento dessa ver-
são beta4, realizado pela equipe de Takashi Chikayama produziu, em 1987, a linguagem KL1. Todos
os sub-projetos do FGCS foram revistos para trabalhar com essa linguagem. Em 1988 os primeiros
protótipos do computador de quinta geração foram construídos, recebendo o nome genérico de Pa-
rallel Inference Machines (PIMs). Tais computadores possuiam arquitetura massivamente paralela e
tinham velocidade de processamento calculada em MLIPS (milhões de inferências lógicas por segun-
do). Uma dessas máquinas, denominada Multi-PSI foi apresentada com grande sucesso no FGCS'88.
 
4
 Uma versão distribuida a grupos selecionados de usuários para teste e depuração.
8
A linguagem KL1 foi empregada para escrever o sistema operacional PIMOS (Parallel Inference Ma-
chine Operating System), em 1988. É importante ressaltar aqui que a linguagem KL1 é uma lingua-
gem de muito alto nível5 e, ao mesmo tempo, uma linguagem de máquina, isto é, adequada à progra-
mação a nível de registradores, posições de memória e portas lógicas. As versões mais recentes do
PIMOS provam definitivamente que KL1 (agora já KL2) é uma linguagem muito mais adequada do
que as linguagens convencionais para a construção de software básico em máquinas paralelas. Outras
linguagens de programação foram - e ainda vem sendo - pesquisadas. Por exemplo, uma linguagem de
programação em lógica com restrições denominada GDCC foi projetada em um nível ainda mais alto
que a KL1. Uma outra linguagem, denominada "Quixote" foi produzida para lidar com bases de dados
dedutivas e orientadas a objetos. Para o gerenciamento de sistemas paralelos distribuídos foi especifi-
cada a linguagem Kappa-P. Todas essas linguagens, com as quais - ou com seus dialetos - todos cer-
tamente estaremos em contato num futuro próximo, estão baseadas nos conceitos e resultados da pes-
quisa em programação em lógica.
Tecnicamente considera-se que o projeto atingiu a primeira parte de seus objetivos: diversos compu-
tadores paralelos foram construídos. Tais computadores são denominados coletivamente de máquinas
de inferência paralela (PIMs), incorporam a linguagem KL1 e o sistema operacional PIMOS. Além
disso as máquinas PIM mais recentemente construídas lograram atingir um pico de desempenho da
ordem de 1 gigalips (1 bilhão de inferências lógicas por segundo), o que era um dos objetívos con-
cretos do projeto considerados mais difíceis de atingir.
A segunda parte do projeto, entretanto, a construção de máquinas orientadas à bases de dados (data-
base machines) foi menos claramente abordada. Tal objetivo foi reformulado a partir do sucesso obti-
do com a construção de linguagens de programação em lógica concorrente para a construção de im-
plementações baseadas em KL1 na mesma plataforma de hardware das máquinas PIM.
De um modo geral, entretanto, considera-se que o projeto demonstrou ser a tecnologia PIM bem suce-
dida em novas aplicações envolvendo paralelismo em diversas áreas, especialmente computação não-
numérica e inteligência artificial. Em suma, segundo o relatório Shapiro-Warren:
"(...) uma ponte foi construída entre a computação paralela e as aplicações envolvendo inte-
ligência artificial. Entretanto, as duas extremidades finais da ponte ainda se encontram por
concluir e a ponte em si é mais frágil do que poderia ter sido. É sem dúvida ainda muito cedo
para se esperar que a ponte seja inaugurada recebendo uma grande aclamação."
1.5 PORQUE ESTUDAR PROLOG
Normalmente há um gap de 10 a 20 anos entre o estágio básico de uma pesquisa tecnológica e o mo-
mento em que esta é colocada à disposição da sociedade consumidora. Na área de informática esse
intervalo costuma ser menor, entretanto, estamos assistindo a uma completa transformação: do para-
digma da quarta geração, ora em fase de esgotamento6 para arquiteturas inovadoras, contemplando
sistemas de processamento paralelo, a concorrência de processos e layers baseados em lógica. A
grande explosão da informática atualmente persegue conceitos tais como interoperabilidade, conecti-
vidade, orientação a objetos, sistemas multimídia, agentes inteligentes cooperativos, hiperdocumen-
tos, realidade virtual, inteligência de máquina e outros, cuja evolução irá determinar nos próximos
anos uma mudança tão radical quanto foi a das carruagens para os veículos automotores - mais ainda,
segundo alguns autores, - terminando por transformar completamente a própria estrutura social.
A programação Prolog é uma excelente porta de entrada para a informática do futuro, tendo em vista
 
5
 Quanto mais alto o nível de uma linguagem, mais próxima da linguagem natural ela se encontra.
6
 As atuais tecnologias de integração de circuitos (VLSI/ULSI) tendem a atingir os limites físicos além dos quais se tornam
economicamente inviáveis.
9
que, entre outras vantagens:
(1)É de aprendizado muito mais fácil e natural do que as linguagens procedimentais convencio-
nais, podendo inclusive ser ministrada a estudantes entre o final do primeiro e o início do se-
gundo grau com grande aproveitamento;
(2) Implementa com precisão todos os novos modelos surgidos nos últimos anos, inclusive redes
neurais, algoritmos genéticos, sociedades de agentes inteligentes, sistemas concorrentes e pa-
ralelos;
(3)Permite a implementação de extensões, inclusive em nível meta, e a definição precisa de siste-
mas reflexivos (essenciais, por exemplo, à robótica);
(4)Libera o programador dos problemas associados ao controle de suas rotinas, permitindo-lhe
concentrar-se nos aspectos lógicos da situação a representar.
Tem sido observada a tendência de substituição paulatina no mercado de trabalho dos serviços de
programação pelos de especificação. Isso ocorre por várias razões, dentre elas porque as especifica-
ções podem ser formalmente provadas corretas, o que não ocorre com facilidade nos programas con-
vencionais. Essa transição - da arte de programar à ciência de especificar - vem estimulando o apare-
cimento de linguagenscomo o Prolog, que pode ser visto como sendo simultaneamente uma lingua-
gem de programação e de especificação (ou, como querem alguns, como uma linguagem de especifi-
cações diretamente executáveis em computadores).
Vem também ocorrendo aceleradamente a popularização de ambientes e interfaces cada vez mais
próximos do usuário final e oferecendo recursos muito poderosos para a personalização de programas
de acordo com as preferências individuais. Isso permite supor que, num futuro próximo, qualquer
pessoa, mesmo sem formação específica em programação, poderá interagir facilmente com computa-
dores, em níveis muito elevados7, dispensando em grande parte a programação, tal como é hoje co-
nhecida. Por outro lado, a construção de tais ambientes ira depender de profissionais bem mais prepa-
rados do que um programador em Pascal, por exemplo. Deverão, tais profissionais, possuir um currí-
culo muito mais rico, abrangendo a teoria da computação, lógica matemática, álgebra relacional, filo-
sofia, arquiteturas concorrentes e paralelas, etc. Serão necessários entretanto em número muito maior
do que se imaginava no início dos anos 80, quando essa tendência ainda não se apresentava perfeita-
mente delineada, uma vez que praticamente todo software colocado no mercado deverá ser produzido
a partir de suas especificações formais.
Um último motivo - não menos importante que os demais já apresentados - deve ainda ser considera-
do: A expressividade herdada da lógica torna a linguagem Prolog um instrumento especialmente po-
deroso, adequado para a descrição do mundo real com todos os seus contornos, nuances e sutilezas.
Nos poucos casos em que a representação se torna mais difícil - na representação temporal, por exem-
plo - a flexibilidade do Prolog em aceitar o desenvolvimento de extensões semanticamente precisas e
incorporá-las ao seu mecanismo de produção de inferências, remove qualquer impedimento para o seu
emprego em virtualmente qualquer área do conhecimento.
RESUMO
• A programação em lógica, tal como a conhecemos hoje, tem suas raízes no cálculo de predica-
dos, proposto por Frege em 1879. Diversos estudos posteriores foram de grande importância
para sua evolução, com destaque para as investigações de Herbrand, Gödel, Tarski, Prawitz,
Robinson e Green;
• A primeira implementação da linguagem Prolog foi realizada por Alain Colmerauer e sua equi-
 
7
 Ao nível da linguagem coloquial falada ou escrita, por exemplo.
10
pe, na Universidade de Aix-Marseille em 1972. A formalização semântica da programação com
cláusulas de Horn é devida a Kowalski (1974) e a especificação do primeiro "standard" - o
Prolog de Edimburgo - foi realizada por Warren e Pereira em 1977;
• As principais características que diferenciam os programas em lógica dos programas convenci-
onais são as seguintes:
(1) Processamento simbólico,
(2) Soluções heurísticas,
(3) Estruturas de controle e conhecimento separadas,
(4) Fácil modificação,
(5) Incluem respostas parcialmente corretas, e
(6) Incluem todas as soluções possíveis;
• Além disso, os sistemas de programação em lógica em geral e a linguagem Prolog em particular
possuem as seguintes propriedades:
(1) Funcionam simultaneamente como linguagem de programação e de especificação,
(2)Possuem capacidade dedutiva,
(3)Operam de forma não-determinística,
(4)Permitem a representação de relações reversíveis,
(5)Permitem interpretação declarativa, procedimental e operacional, e
(6)São naturalmente recursivos;
• As principais aplicação da programação em lógica são:
(1)Sistemas Baseados em Conhecimento SBCs),
(2)Sistemas de Bases de Dados (BDs),
(3)Sistemas Especialistas (SEs),
(4)Processamento da Linguagem Natural (PLN),
(5)Educação, e
(6)Modelagem de Arquiteturas Não-Convencionais;
• O projeto japonês para o desenvolvimento de Sistemas Computacionais de Quinta Geração ini-
ciou em 1982 e foi oficialmente concluído em maio de 1992. Apesar de ficarem aquém do espe-
rado, os resultados produzidos permitem claramente antever o papel preponderante que a pro-
gramação em lógica deverá representar nos futuros sistemas computacionais;
• A crescente necessidade de garantir a qualidade do software substituindo programas por especi-
ficações formais diretamente executáveis, aliada à evolução das características do hardware,
que passam a explorar cada vez mais os conceitos de concorrência e paralelismo, tornam a lin-
guagem Prolog uma excelente porta de entrada para a informática do futuro.
11
2. A LINGUAGEM PROLOG
A principal utilização da linguagem Prolog reside no domínio da programação simbólica, não-
numérica, sendo especialmente adequada à solução de problemas, envolvendo objetos e relações entre
objetos. O advento da linguagem Prolog reforçou a tese de que a lógica é um formalismo conveniente
para representar e processar conhecimento. Seu uso evita que o programador descreva os procedi-
mentos necessários para a solução de um problema, permitindo que ele expresse declarativamente
apenas a sua estrutura lógica, através de fatos, regras e consultas. Algumas das principais característi-
cas da linguagem Prolog são:
• É uma linguagem orientada ao processamento simbólico;
• Representa uma implementação da lógica como linguagem de programação;
• Apresenta uma semântica declarativa inerente à lógica;
• Permite a definição de programas reversíveis, isto é, programas que não distinguem entre os
argumentos de entrada e os de saída;
• Permite a obtenção de respostas alternativas;
• Suporta código recursivo e iterativo para a descrição de processos e problemas, dispensando os
mecanismos tradicionais de controle, tais como while, repeat, etc;
• Permite associar o processo de especificação ao processo de codificação de programas;
• Representa programas e dados através do mesmo formalismo;
• Incorpora facilidades computacionais extralógicas e metalógicas.
No presente capítulo introduz-se informalmente os conceitos essenciais da linguagem Prolog, visando
conduzir rapidamente o leitor ao domínio da sintaxe e a um entendimento intuitivo da semântica asso-
ciada aos programas.
2.1 FATOS
Considere a árvore genealógica mostrada na Figura 2.1. É possível definir, entre os objetos (indivídu-
os) mostrados, uma relação denominada progenitor que associa um indivíduo a um dos seus progeni-
tores. Por exemplo, o fato de que João é um dos progenitores de José pode ser denotado por:
progenitor(joão, josé).
onde progenitor é o nome da relação e joão e josé são os seus argumentos. Por razões que se tornarão
claras mais tarde, escreve-se aqui nomes de pessoas (como João) iniciando com letra minúscula. A
relação progenitor completa, como representada na figura acima pode ser definida pelo seguinte pro-
grama Prolog:
progenitor(maria, josé).
progenitor(joão, josé).
progenitor(joão, ana).
progenitor(josé, júlia).
progenitor(josé, íris).
progenitor(íris, jorge).
O programa acima compõe-se de seis cláusulas, cada uma das quais denota um fato acerca da relação
progenitor. Se o programa for submetido a um sistema Prolog, este será capaz de responder algumas
questões sobre a relação ali representada. Por exemplo: "José é o progenitor de Íris?". Uma consulta
como essa deve ser formulada ao sistema precedida por um "?-". Esta combinação de sinais denota
que se está formulando uma pergunta. Como há um fato no programa declarando explicitamente que
12
José é o progenitor de Íris, o sistema responde "sim".
?-progenitor(josé, íris).
sim
Maria João
José Ana
Júlia Íris
Jorge
Figura 2.1 Uma árvore genealógica
Uma outra questão poderia ser: "Ana é um dos progenitores de Jorge?". Nesse caso o sistema respon-
de "não", porque não há nenhuma cláusula no programa que permita deduzir tal fato.
?-progenitor(ana, jorge).
não
A questão "Luís é progenitor de Maria?" também obteria a resposta "não",porque o programa nem
sequer conhece alguém com o nome Luís.
?-progenitor(luís, maria).
não
Perguntas mais interessantes podem também ser formuladas, por exemplo: "Quem é progenitor de
Íris?". Para fazer isso introduz-se uma variável, por exemplo "X" na posição do argumento corres-
pondente ao progenitor de Íris. Desta feita o sistema não se limitará a responder "sim" ou "não", mas
irá procurar (e informar caso for encontrado) um valor de X que torne a assertiva "X é progenitor de
Íris" verdadeira.
?-progenitor(X, íris).
X=josé
Da mesma forma a questão "Quem são os filhos de José?" pode ser formulada com a introdução de
uma variável na posição do argumento correspondente ao filhos de José. Note que, neste caso, mais de
uma resposta verdadeira pode ser encontrada. O sistema irá fornecer a primeira que encontrar e
aguardar manifestação por parte do usuário. Se este desejar outras soluções deve digitar um ponto-e-
vírgula (;), do contrário digita um ponto (.), o que informa ao sistema que a solução fornecida é sufi-
ciente.
?-progenitor(josé, X).
X=júlia;
X=íris;
não
Aqui a última resposta obtida foi "não" significando que todas as soluções válidas já foram forneci-
das. Uma questão mais geral para o programa seria: "Quem é progenitor de quem?" ou, com outra
formulação: "Encontre X e Y tal que X é progenitor de Y". O sistema, em resposta, irá fornecer (en-
quanto se desejar, digitando ";") todos os pares progenitor-filho até que estes se esgotem (quando
então responde "não") ou até que se resolva encerrar a apresentação de novas soluções (digitando ".").
No exemplo a seguir iremos nos satisfazer com as três primeiras soluções encontradas.
?-progenitor(X, Y).
13
X=maria Y=josé;
X=joão Y=josé;
X=joão Y=ana.
Pode-se formular questões ainda mais complicadas ao programa, como "Quem são os avós de Jor-
ge?". Como nosso programa não possui diretamente a relação avô, esta consulta precisa ser dividida
em duas etapas, como pode ser visto na Figura 2.2. A saber:
(1) Quem é progenitor de Jorge? (Por exemplo, Y) e
(2) Quem é progenitor de Y? (Por exemplo, X)
Esta consulta em Prolog é escrita como uma seqüência de duas consultas simples, cuja leitura pode
ser: "Encontre X e Y tais que X é progenitor de Y e Y é progenitor de Jorge".
?-progenitor(X, Y), progenitor(Y, jorge).
X=josé Y=íris
X
Y
Jorge
progenitor
progenitor
avô
Figura 2.2 A relação avô em função de progenitor
Observe que se mudarmos a ordem das consultas na composição, o significado lógico permanece o
mesmo, apesar do resultado ser informado na ordem inversa:
?-progenitor(Y, jorge), progenitor(X, Y).
Y=íris X=josé
De modo similar podemos perguntar: "Quem é neto de João?":
?-progenitor(joão, X), progenitor(X, Y).
X=josé Y=júlia;
X=josé Y=íris.
Ainda uma outra pergunta poderia ser: "José e Ana possuem algum progenitor em comum?". Nova-
mente é necessário decompor a questão em duas etapas, formulando-a alternativamente como: "En-
contre um X tal que X seja simultaneamente progenitor de José e Ana".
?-progenitor(X, josé), progenitor(X, ana).
X=joão
Por meio dos exemplos apresentados até aqui acredita-se ter sido possível ilustrar os seguintes pontos:
• Uma relação como progenitor pode ser facilmente definida em Prolog estabelecendo-se as tu-
plas de objetos que satisfazem a relação;
• O usuário pode facilmente consultar o sistema Prolog sobre as relações definidas em seu pro-
grama;
• Um programa Prolog é constituído de cláusulas, cada uma das quais é encerrada por um ponto
(.);
• Os argumentos das relações podem ser objetos concretos (como júlia e íris) ou objetos genéri-
cos (como X e Y). Objetos concretos em um programa são denominados átomos, enquanto que
os objetos genéricos são denominados variáveis;
14
• Consultas ao sistema são constituídas por um ou mais objetivos, cuja seqüência denota a sua
conjunção;
• Uma resposta a uma consulta pode ser positiva ou negativa, dependendo se o objetivo corres-
pondente foi alcançado ou não. No primeiro caso dizemos que a consulta foi bem-sucedida e,
no segundo, que a consulta falhou;
• Se várias respostas satisfizerem a uma consulta, então o sistema Prolog irá fornecer tantas
quantas forem desejadas pelo usuário.
2.2 REGRAS
O programa da árvore genealógica pode ser facilmente ampliado de muitas maneiras interessantes.
Inicialmente vamos adicionar informação sobre o sexo das pessoas ali representadas. Isso pode ser
feito simplesmente acrescentando os seguintes fatos ao programa:
masculino(joão).
masculino(josé).
masculino(jorge).
feminino(maria).
feminino(júlia).
feminino(ana).
feminino(íris).
As relações introduzidas no programa são masculino e feminino . Tais relações são unárias, isto é,
possuem um único argumento. Uma relação binária, como progenitor, é definida entre pares de obje-
tos, enquanto que as relações unárias podem ser usadas para declarar propriedades simples desses
objetos. A primeira cláusula unária da relação masculino pode ser lida como: "João é do sexo mascu-
lino". Poderia ser conveniente declarar a mesma informação presente nas relações unárias masculino e
feminino em uma única relação binária sexo:
sexo(joão, masculino).
sexo(maria, feminino).
sexo(josé, masculino). ... etc.
A próxima extensão ao programa será a introdução da relação filho como o inverso da relação proge-
nitor. Pode-se definir a relação filho de modo semelhante à utilizada para definir a relação progenitor,
isto é fornecendo uma lista de fatos, cada um dos quais fazendo referência a um par de pessoas tal que
uma seja filho da outra. Por exemplo:
filho(josé, joão).
Entretanto podemos definir a relação "filho" de uma maneira muito mais elegante, fazendo o uso do
fato de que ela é o inverso da relação progenitor e esta já está definida. Tal alternativa pode ser base-
ada na seguinte declaração lógica:
Para todo X e Y
Y é filho de X se
X é progenitor de Y.
Essa formulação já se encontra bastante próxima do formalismo adotado em Prolog. A cláusula cor-
respondente, com a mesma leitura acima, é:
filho(Y, X) :- progenitor(X, Y).
que também pode ser lida como: "Para todo X e Y, se X é progenitor de Y, então Y é filho de X".
Cláusulas Prolog desse tipo são denominadas regras. Há uma diferença importante entre regras e fa-
tos. Um fato é sempre verdadeiro, enquanto regras especificam algo que "pode ser verdadeiro se al-
gumas condições forem satisfeitas". As regras tem:
• Uma parte de conclusão (o lado esquerdo da cláusula), e
15
• Uma parte de condição (o lado direito da cláusula).
O símbolo ":-" significa "se" e separa a cláusula em conclusão, ou cabeça da cláusula, e condição ou
corpo da cláusula, como é mostrado no esquema abaixo. Se a condição expressa pelo corpo da cláu-
sula - progenitor (X, Y) - é verdadeira então, segue como conseqüência lógica que a cabeça - filho(Y,
X) - também o é. Por outro lado, se não for possível demonstrar que o corpo da cláusula é verdadeiro,
o mesmo irá se aplicar à cabeça.
filho(Y, X) :- progenitor(X, Y)
A maioria dos sistemas Prolog, na ausência de caracteres ASCII adequados, emprega o símbolo com-
posto ":-" para denotar a implicação "¬". Aqui, por uma questão de clareza, adotaremos este último
símbolo, que é o normalmente empregado na programação em lógica com cláusulas definidas.
A utilização das regras pelo sistema Prolog é ilustrada pelo seguinte exemplo: vamos perguntar ao
programa se José é filho de Maria:
?-filho(josé, maria).
Não há nenhum fato a esse respeito no programa, portanto a única forma de considerar esta questão é
aplicando a regra correspondente. A regra é genérica, no sentido de ser aplicável a quaisquer objetos
X e Y. Logo pode ser aplicada a objetos particulares, como josé e maria. Para aplicar a regra, Y será
substituído por josé e X por maria. Dizemos que as variáveis X e Y se tornaram instanciadas para:
X=mariae Y=josé
A parte de condição se transformou então no objetivo progenitor(maria, josé). Em seguida o sistema
passa a tentar verificar se essa condição é verdadeira. Assim o objetivo inicial, filho(josé, maria), foi
substituído pelo sub-objetivo progenitor(maria, josé). Esse novo objetivo apresenta-se como trivial,
uma vez que há um fato no programa estabelecendo exatamente que Maria é um dos progenitores de
José. Isso significa que a parte de condição da regra é verdadeira, portanto a parte de conclusão tam-
bém é verdadeira e o sistema responde "sim".
Vamos agora adicionar mais algumas relações ao nosso programa. A especificação, por exemplo, da
relação mãe entre dois objetos do nosso domínio pode ser escrita baseada na seguinte declaração lógi-
ca:
Para todo X e Y
X é mãe de Y se
X é progenitor de Y e
X é feminino.
que, traduzida para Prolog, conduz à seguinte regra:
mãe(X, Y) :- progenitor(X, Y), feminino(X).
onde a vírgula entre as duas condições indica a sua conjunção, significando que, para satisfazer o
corpo da regra, ambas as condições devem ser verdadeiras. A relação avô, apresentada anteriormente
na Figura 2.2, pode agora ser definida em Prolog por:
avô(X, Z) :- progenitor(X, Y), progenitor(Y, Z).
Neste ponto é interessante comentar alguma coisa sobre o layout dos programas Prolog. Estes podem
ser escritos quase que com total liberdade, de modo que podemos inserir espaços e mudar de linha
onde e quando melhor nos aprouver. Em geral, porém, desejamos produzir programas de boa aparên-
cia, elegantes e sobretudo fáceis de ser lidos. Com essa finalidade, normalmente se prefere escrever a
cabeça da cláusula e os objetivos da condição cada um em uma nova linha. Para destacar a conclusão,
identamos os objetivos. A cláusula avô, por exemplo, seria escrita:
avô(X, Z) :-
progenitor(X, Y),
progenitor(Y, Z).
16
Adicionaremos ainda uma última relação ao nosso programa para exemplificar mais uma particulari-
dade da linguagem Prolog. Uma cláusula para a relação irmã se embasaria na seguinte declaração
lógica:
Para todo X e Y
X é irmã de Y se
X e Y possuem um progenitor comum e
X é do sexo feminino.
Ou, sob a forma de regra Prolog:
irmã(X, Y) :-
progenitor(Z, X),
progenitor(Z, Y),
feminino(X).
Deve-se atentar para a forma sob a qual o requisito "X e Y possuem um progenitor comum" foi expres-
sa. A seguinte formulação lógica foi adotada: "Algum Z deve ser progenitor de X e esse mesmo Z deve
também ser progenitor de Y". Uma forma alternativa, porém menos elegante, de representar a mesma
condição seria: "Z1 é progenitor de X e Z2 é progenitor de Y e Z1 é igual a Z2". Se consultarmos o
sistema com "Júlia é irmã de Íris?" , obteremos, como é esperado, um "sim" como resposta. Podería-
mos então concluir que a relação irmã, conforme anteriormente definida, funciona corretamente, en-
tretanto, há uma falha muito sutil que se revela quando perguntamos: "Quem é irmã de Íris?". O sis-
tema irá nos fornecer duas respostas:
?-irmã(X, íris).
X=júlia;
X=íris
dando a entender que Íris é irmã de si própria. Isso não é certamente o que se tinha em mente na defi-
nição de irmã, entretanto, de acordo com a regra formulada, a resposta obtida pelo sistema é perfeita-
mente lógica. Nossa regra sobre irmãs não menciona que X e Y não devem ser os mesmos para que X
seja irmã de Y. Como isso não foi requerido, o sistema, com toda razão, assume que X e Y podem
denotar a mesma pessoa e irá achar que toda pessoa do sexo feminino que possui um progenitor é
irmã de si própria.
Para corrigir esta distorção é necessário acrescentar a condição de que X e Y devem ser diferentes.
Isso pode ser feito de diversas maneiras, conforme se verá mais adiante. Por enquanto vamos assumir
que uma relação diferente(X, Y) seja reconhecida pelo sistema como verdadeira se e somente se X e Y
não forem iguais. A regra para a relação irmã fica então definida por:
irmã(X, Y) :-
progenitor(Z, X),
progenitor(Z,Y),
feminino(X),
diferente(X, Y).
Os pontos mais importantes vistos na presente seção foram:
• Programas Prolog podem ser ampliados pela simples adição de novas cláusulas;
• As cláusulas Prolog podem ser de três tipos distintos: fatos, regras e consultas;
• Os fatos declaram coisas que são incondicionalmente verdadeiras;
• As regras declaram coisas que podem ser ou não verdadeiras, dependendo da satisfação das
condições dadas;
• Por meio de consultas podemos interrogar o programa acerca de que coisas são verdadeiras;
• As cláusulas Prolog são constituídas por uma cabeça e um corpo. O corpo é uma lista de objeti-
vos separados por vírgulas que devem ser interpretadas como conjunções;
• Fatos são cláusulas que só possuem cabeça, enquanto que as consultas só possuem corpo e as
regras possuem cabeça e corpo;
17
• Ao longo de uma computação, uma variável pode ser substituída por outro objeto. Dizemos
então que a variável está instanciada;
• As variáveis são assumidas como universalmente quantificadas nas regras e nos fatos e existen-
cialmente quantificadas nas consultas
2.3 CONSTRUÇÕES RECURSIVAS
Iremos adicionar agora ao programa a relação antepassado, que será definida a partir da relação pro-
genitor. A definição necessita ser expressa por meio de duas regras, a primeira das quais definirá os
antepassados diretos (imediatos) e a segunda os antepassados indiretos. Dizemos que um certo X é
antepassado indireto de algum Z se há uma cadeia de progenitura entre X e Z como é ilustrado na
Figura 2.3. Na árvore genealógica da Figura 2.1, João é antepassado direto de Ana e antepassado indi-
reto de Júlia.
A primeira regra, que define os antepassados diretos, é bastante simples e pode ser formulada da se-
guinte maneira:
Para todo X e Z
X é antepassado de Z se
X é progenitor de Z.
Maria João
Júlia Íris
Jorge
progenitor progenitor
progenitor(a)
(b)
antepassado direto
antepassado indireto
Figura 2.3 Exemplos da relação antepassado
ou, traduzindo para Prolog:
antepassado(X, Z) :-
progenitor(X, Z).
Por outro lado, a segunda regra é mais complicada, porque a cadeia de progenitores poderia se esten-
der indefinidamente. Uma primeira tentativa seria escrever uma cláusula para cada posição possível
na cadeia. Isso conduziria a um conjunto de cláusulas do tipo:
antepassado(X, Z) :-
progenitor(X, Y),
progenitor(Y, Z).
antepassado(X, Z) :-
progenitor(X, Y1),
progenitor(Y1, Y2),
progenitor(Y2, Z).
antepassado(X, Z) :-
progenitor(X, Y1),
progenitor(Y1, Y2),
progenitor(Y2, Y3),
progenitor(Y3, Z). ... etc.
Isso conduziria a um programa muito grande e que, de qualquer modo, somente funcionaria até um
determinado limite, isto é, somente forneceria antepassados até uma certa profundidade na árvore
18
genealógica de uma família, porque a cadeia de pessoas entre o antepassado e seu descendente seria
limitada pelo tamanho da maior cláusula definindo essa relação. Há entretanto uma formulação ele-
gante e correta para a relação antepassado que não apresenta qualquer limitação. A idéia básica é
definir a relação em termos de si própria, empregando um estilo de programação em lógica denomina-
do recursivo:
Para todo X e Z
X é antepassado de Z se
existe um Y tal que
X é progenitor de Y e
Y é antepassado de Z.
A cláusula Prolog correspondente é:
antepassado(X, Z) :-
progenitor(X, Y),
antepassado(Y, Z).
Assim é possível construir um programa completo para a relação antepassado composto de duas re-
gras: uma para os antepassados diretos e outra para os indiretos. Reescrevendo as duas juntas tem-se:
antepassado(X, Z) :-
progenitor(X, Z).
antepassado(X, Z) :-
progenitor(X, Y),
antepassado(Y, Z).
Tal definição pode causar certa surpresa, tendo em vista a seguinte pergunta: Como é possível ao de-
finir alguma coisa empregar essa mesma coisa se ela ainda não está completamente definida? Tais
definições são denominadas recursivase do ponto de vista da lógica são perfeitamente corretas e inte-
ligíveis, o que deve ficar claro, pela observação da Figura 2.4. Por outro lado o sistema Prolog deve
muito do seu potencial de expressividade à capacidade intrínseca que possui de utilizar facilmente
definições recursivas. O uso de recursão é, em realidade, uma das principais características herdadas
da lógica pela linguagem Prolog.
Z
X
Y
antepassado
antepassado
progenitor
Figura 2.4 Formulação recursiva da relação antepassado
Há ainda uma questão importante a ser respondida: Como realmente o sistema Prolog utiliza o pro-
grama para encontrar as informações procuradas? Uma explicação informal será fornecida na próxima
seção, antes porém vamos reunir todas as partes do programa que foi sendo gradualmente ampliado
pela adição de novos fatos e regras. A forma final do programa é mostrada na Figura 2.5. O programa
ali apresentado define diversas relações: progenitor, masculino, feminino, antepassado, etc. A relação
antepassado, por exemplo, é definida por meio de duas cláusulas. Dizemos que cada uma delas é so-
bre a relação antepassado. Algumas vezes pode ser conveniente considerar o conjunto completo de
cláusulas sobre a mesma relação. Tal conjunto de cláusulas é denominado um predicado.
19
Na Figura 2.5, as duas regras sobre a relação antepassado foram distinguidas com os nomes [pr1] e
[pr2] que foram adicionados como comentários ao programa. Tais nomes serão empregados adiante
como referência a essas regras. Os comentários que aparecem em um programa são normalmente ig-
norados pelo sistema Prolog, servindo apenas para melhorar a legibilidade do programa impresso. Os
comentários se distinguem do resto do programa por se encontrarem incluídos entre os delimitadores
especiais "/*" e "*/". Um outro método, mais conveniente para comentários curtos, utiliza o caracter
de percentual "%": todo o texto informado entre o "%" e o final da linha é interpretado como comen-
tário. Por exemplo:
/* Isto é um comentário. */
% E isto também.
progenitor(maria, josé). % Maria é progenitor de José.
progenitor(joão, josé).
progenitor(joão, ana).
progenitor(josé, júlia).
progenitor(josé, íris).
progenitor(íris, jorge).
masculino(joão). % João é do sexo masculino.
masculino(josé).
masculino(jorge).
feminino(maria). % Maria é do sexo feminino.
feminino(ana).
feminino(júlia).
feminino(íris).
filho(Y, X) :- % Y é filho de X se
 progenitor(X,Y). % X é progenitor de Y.
mãe(X,Y) :- % X é mãe de Y se
 progenitor(X, Y), % X é progenitor de Y e
 feminino(X). % X é do sexo feminino.
avô(X, Z) :- % X é avô de Z se
 progenitor(X, Y), % X é progenitor de Y e
 progenitor(Y, Z). % Y é progenitor de Z.
irmã(X, Y) :- % X é irmã de Y se
 progenitor(Z, X), % X tem um progenitor, Z que
 progenitor(Z, Y), % é também progenitor de Y e
 feminino(X), % X é do sexo feminino e
 diferente(X, Y). % X e Y são diferentes.
antepassado(X, Z) :- % X é antepassado de Z se
 progenitor(X, Z). % X é progenitor de Z. [pr1]
antepassado(X, Z) :- % X é antepassado de Z se
 progenitor(X, Y), % X é progenitor de Y e
 antepassado(Y, Z). % Y é antepassado de Z. [pr2]
Figura 2.5 Um programa Prolog
2.4 CONSULTAS
Uma consulta em Prolog é sempre uma seqüência composta por um ou mais objetivos. Para obter a
resposta, o sistema Prolog tenta satisfazer todos os objetivos que compõem a consulta, interpretando-
os como uma conjunção. Satisfazer um objetivo significa demonstrar que esse objetivo é verdadeiro,
assumindo que as relações que o implicam são verdadeiras no contexto do programa. Se a questão
também contém variáveis, o sistema Prolog deverá encontrar ainda os objetos particulares que, atri-
buídos às variáveis, satisfazem a todos os sub-objetivos propostos na consulta. A particular instancia-
ção das variáveis com os objetos que tornam o objetivo verdadeiro é então apresentada ao usuário. Se
não for possível encontrar, no contexto do programa, nenhuma instanciação comum de suas variáveis
que permita derivar algum dos sub-objetivos propostos então a resposta será "não".
Uma visão apropriada da interpretação de um programa Prolog em termos matemáticos é a seguinte:
O sistema Prolog aceita os fatos e regras como um conjunto de axiomas e a consulta do usuário como
um teorema a ser provado. A tarefa do sistema é demonstrar que o teorema pode ser provado com
base nos axiomas representados pelo conjunto das cláusulas que constituem o programa. Essa visão
20
será ilustrada com um exemplo clássico da lógica de Aristóteles. Sejam os axiomas:
Todos os homens são falíveis.
Sócrates é um homem.
Um teorema que deriva logicamente desses dois axiomas é:
Sócrates é falível
O primeiro axioma pode ser reescrito como: "Para todo X, se X é um homem então X é falível". Nessa
mesma linha o exemplo pode ser escrito em Prolog como se segue:
falível(X) :-
homem(X).
homem(sócrates).
?-falível(X).
X=sócrates
Um exemplo mais complexo, extraído do programa apresentada na Figura 2.5 é:
?-antepassado(joão, íris).
Sabe-se que progenitor(josé, íris) é um fato. Usando esse fato e a regra [pr1], podemos concluir ante-
passado(josé, íris). Este é um fato derivado. Não pode ser encontrado explícito no programa, mas
pode ser derivado a partir dos fatos e regras ali presentes. Um passo de inferência como esse pode ser
escrito em uma forma mais complexa como:
progenitor(josé, íris) ���� antepassado(josé, íris)
que pode ser lido assim: "de progenitor(josé, íris) segue, pela regra [pr1] que antepassado(josé,
íris)". Além disso sabemos que progenitor(joão, josé) é fato. Usando este fato e o fato derivado, ante-
passado(josé, íris), podemos concluir, pela regra [pr2], que o objetivo proposto, antepassado(joão,
íris) é verdadeiro. O processo completo, formado por dois passos de inferência, pode ser escrito:
progenitor(josé, íris) ���� antepassado(josé, íris)
e
progenitor(joão, josé) e antepassado(josé, íris) ���� antepassado(joão, íris)
Mostrou-se assim o que pode ser uma seqüência de passos de inferência usada para satisfazer um ob-
jetivo. Tal seqüência denomina-se seqüência de prova. A extração de uma seqüência de prova do
contexto formado por um programa e uma consulta é obtida pelo sistema na ordem inversa da empre-
gada acima. Ao invés de iniciar a inferência a partir dos fatos, o Prolog começa com os objetivos e ,
usando as regras, substitui os objetivos correntes por novos objetivos até que estes se tornem fatos.
Dada por exemplo a questão: "João é antepassado de Íris?", o sistema tenta encontrar uma cláusula
no programa a partir da qual o oibjetivo seja conseqüência imediata. Obviamente, as únicas cláusulas
relevantes para essa finalidade são [pr1] e [pr2], que são sobre a relação antepassado, porque são as
únicas cujas cabeças podem ser unificadas com o objetivo formulado. Tais cláusulas representam dois
caminhos alternativos que o sistema pode seguir. Inicialmente o Prolog irá tentar a que aparece em
primeiro lugar no programa:
antepassado(X, Z) :- progenitor(X, Z).
uma vez que o objetivo é antepassado(joão, íris), as variáveis na regra devem ser instanciadas por
X=joão e Y=íris. O objetivo inicial, antepassado(joão, íris) é então substituído por um novo objetivo:
progenitor(joão, íris)
Não há, entretanto, nenhuma cláusula no programa cuja cabeça possa ser unificada com progeni-
tor(joão, íris), logo este objetivo falha. Então o Prolog retorna ao objetivo original (backtracking)
para tentar um caminho alternativo que permita derivar o objetivo antepassado(joão, íris). A regra
[pr2] é então tentada:
antepassado(X, Z) :-
progenitor(X, Y),
21
antepassado(Y, Z).
Como anteriormente, as variáveis X e Z são instanciadaspara joão e íris, respectivamente. A variável
Y, entretanto, não está instanciada ainda. O objetivo original, antepassado(joão, íris) é então substi-
tuído por dois novos objetivos derivados por meio da regra [pr2]:
progenitor(joão, Y), antepassado(Y, íris).
Encontrando-se agora face a dois objetivos, o sistema tenta satisfazê-los na ordem em que estão for-
mulados. O primeiro deles é fácil: progenitor(joão, Y) pode ser unificado com dois fatos do programa:
progenitor(joão, josé) e progenitor(joão, ana). Mais uma vez, o caminho a ser tentado deve correspon-
der à ordem em que os fatos estão escritos no programa. A variável Y é então instanciada com josé
nos dois objetivos acima, ficando o primeiro deles imediatamente satisfeito. O objetivo remanescente
é então:
antepassado(josé, íris).
Para satisfazer tal objetivo, a regra [pr1] é mais uma vez empregada. Essa segunda aplicação de [pr1],
entretanto, nada tem a ver com a sua utilização anterior, isto é, o sistema Prolog usa um novo conjunto
de variáveis na regra cada vez que esta é aplicada. Para indicar isso iremos renomear as variáveis em
[pr1] nessa nova aplicação, da seguinte maneira:
antepassado(X', Z') :-
progenitor(X', Z').
A cabeça da regra deve então ser unificada como o nosso objetivo corrente, que é antepassado(josé,
íris). A instanciação de X'e Y' fica: X'=josé e Y'=íris e o objetivo corrente é substituído por:
progenitor(josé, íris)
Esse objetivo é imediatamente satisfeito, porque aparece no programa como um fato. O sistema en-
controu então um caminho que lhe permite provar, no contexto oferecido pelo programa dado, o obje-
tivo originalmente formulado, e portanto responde "sim".
2.5 O SIGNIFICADO DOS PROGRAMAS PROLOG
Assume-se que um programa Prolog possua três interpretações semânticas básicas. A saber: interpre-
tação declarativa, interpretação procedimental, e interpretação operacional.
Na interpretação declarativa entende-se que as cláusulas que definem o programa descrevem uma
teoria de primeira ordem. Na interpretação procedimentas, as cláusulas são vistas como entrada para
um método de prova. Finalmente, na interpretação operacional as cláusulas são vistas como comandos
para um procedimento particular de prova por refutação.
Tais alternativas semânticas são valiosas em termos de entendimento e codificação de programas
Prolog. A interpretação declarativa permite que o programador modele um dado problema através de
assertivas acerca dos objetos do universo de discurso, simplificando a tarefa de programação Prolog
em relação a outras linguagens tipicamente procedimentais como Pascal ou C. A interpretação proce-
dimental permite que o programador identifique e descreva o problema pela redução do mesmo a sub-
problemas, através da definição de uma série de chamadas a procedimentos. Por fim, a interpretação
operacional reintroduz a idéia de controle da execução (que é irrelevante do ponto de vista da semân-
tica declarativa), através da ordenação das cláusulas e dos objetivos dentro das cláusulas em um pro-
grama Prolog. Essa útima interpretação é semelhante à semântica operacional de muitas linguagens
convencionais de programação, e deve ser considerada, principalmente em grandes programas, por
questões de eficiência. É interessante notar que o programador pode comutar de uma interpretação
para outra, produzindo um efeito sinérgico que facilita consideravelmente a codificação dos progra-
mas Prolog.
22
Essa habilidade específica do Prolog, de trabalhar em detalhes procedimentais de ação sobre o seu
próprio domínio de definição, isto é, a capacidade de ser meta-programado, é uma das principais
vantagens da linguagem. Ela encoraja o programador a considerar a semântica declarativa de seus
programas de modo relativamente independente dos seus significados procedimental e operacional.
Uma vez que os resultados do programa são considerados, em princípio, pelo seu significado declara-
tivo, isto deveria ser, por decorrência, suficiente para a codificação de programas Prolog. Isso possui
grande importância pratica, pois os aspectos declarativos do programa são em geral mais fáceis de
entender do que os detalhes operacionais. Para tirar vantagem dessa característica o programador deve
se concentrar principalmente no significado declarativo e , sempre que possível, evitar os detalhes de
execução. A abordagem declarativa, na realidade, torna a programação em Prolog mais fácil do que
nas linguagens convencionais. Infelizmente, entretanto, essa interpretação nem sempre é suficiente.
Como deverá ficar claro mais adiante, em problemas de maior complexidade os aspectos operacionais
não podem ser ignorados. Apesar de tudo, a atribuição de significado declarativo aos programas Pro-
log deve ser estimulada, na extensão limitada por suas restrições de ordem prática.
RESUMO
• A programação em Prolog consiste em estabelecer relações entre objetos e em formular con-
sultas sobre tais relações.
• Um programa Prolog é formado por cláusulas. Há três tipos de cláusulas: fatos ou assertivas,
regras ou procedimentos e consultas;
• Uma relação pode ser especificada por meio de fatos, que estabelecem as tuplas de objetos que
satisfazem a relação, por meio de regras, que estabelecem condições para a satisfação das rela-
ções, ou por meio de combinações de fatos e regras descrevendo a relação;
• Denomina-se predicado ao conjunto de fatos e regras empregados para descrever uma determi-
nada relação;
• Interrogar um programa acerca de suas relações por meio de uma consulta corresponde a con-
sultar uma base de conhecimento. A resposta do sistema Prolog consiste em um conjunto de
objetos que satisfazem as condições originalmente estabelecidas pela consulta;
• Em Prolog, estabelecer se um objeto satisfaz a uma consulta é freqüentemente um problema de
certa complexidade, que envolve inferência lógica e a exploração de caminhos alternativos em
uma árvore de busca ou de pesquisa, com a possível utilização de mecanismos especiais de re-
torno (backtracking). Tudo isso é feito automaticamente pelo sistema, de forma transparente ao
usuário;
• Três tipos de semântica são atribuídas aos programas Prolog: declarativa, procedimental e ope-
racional. O programador deve empregá-las conforme o problema a ser resolvido, tirando pro-
veito da situação apresentada.
EXERCÍCIOS
2.1 Amplie o programa apresentado na Figura 2.5 para representar as relações tio, prima, cunhado e
sogra.
2.2 Programe a relação descendente(X, Y), onde X é descendente de Y.
2.3 Escreva um programa Prolog para representar o seguinte:
João nasceu em Pelotas e Jean nasceu em Paris.
Pelotas fica no Rio Grande do Sul.
Paris fica na França.
Só é gaúcho quem nasceu no Rio Grande do Sul.
23
2.4 Escreva um programa Prolog para representar o seguinte:
Os corpos celeste dignos de nota são as estrelas, os planetas e os cometas.
Vênus é um corpo celeste, mas não é uma estrela.
Os cometas possuem cauda quando estão perto do sol.
Vênus está perto do sol, mas não possui cauda.
2.5 Assuma que os arcos em um grafo expressem custos, como no exemplo abaixo:
A
B
C
D
E
F
3
5
4
2
4
5
2
2
e sejam descritos através de assertivas da forma
arco(R, S, T)
significando que há um arco de custo T entre os nodos R e S. Por exemplo, arco(A, B, 3) descre-
ve um arco de custo 3 entre os nodos A e B. Assuma também que o relacionamento mais(X, Y,
Z) vale quando X+Y=Z. Defina o relacionamento custo(U, V, L) de forma a expressar que existe
um caminho de custo L entre os nodos U e V.
24
3. SINTAXE E SEMÂNTICA
Prolog é um nome comum para uma família de sistemas que implementam a lógica de predicados
como linguagem de programação. Algumas destas implementações, como o Prolog de Edimburgo e o
IC-Prolog, são bastante conhecidas nos meios acadêmicos. Outras, como o microProlog, o Quintus-
Prolog e o Arity Prolog ganharam popularidade