tutorial prolog - livro de prolog
camila abacaxi | comentários
Editora da Universidade Católica de Pelotas / UCPEL
1. LÓGICA E PROGRAMAÇÃO DE COMPUTADORES1
1.1 AS RAÍZES1 1.2 PROGRAMAÇÃO EM LÓGICA2 1.3 APLICAÇÕES4 1.4 A QUINTA GERAÇÃO6 1.5 PORQUE ESTUDAR PROLOG8 RESUMO 9
2. A LINGUAGEM PROLOG11
2.1 FATOS11 2.2 REGRAS14 2.3 CONSTRUÇÕES RECURSIVAS17 2.4 CONSULTAS19 2.5 O SIGNIFICADO DOS PROGRAMAS PROLOG21 RESUMO 2 EXERCÍCIOS 2
3. SINTAXE E SEMÂNTICA24
3.1 OBJETOS24 3.2 UNIFICAÇÃO27 3.3 SEMÂNTICA DECLARATIVA E SEMÂNTICA PROCEDIMENTAL28 3.4 SEMÂNTICA OPERACIONAL30 RESUMO 30 EXERCÍCIOS 31
4. OPERADORES E ARITMÉTICA33
4.1 OPERADORES33 4.2 ARITMÉTICA36 RESUMO 38 EXERCÍCIOS 39
5. PROCESSAMENTO DE LISTAS41
5.1 REPRESENTAÇÃO DE LISTAS41 5.2 OPERAÇÕES SOBRE LISTAS42 5.3 OUTROS EXEMPLOS48 RESUMO 49 EXERCÍCIOS 50
6.1 BACKTRACKING51 6.2 O OPERADOR "CUT"52 6.3 APLICAÇÕES DO CUT56 6.4 NEGAÇÃO POR FALHA57 6.5 CUIDADOS COM O CUT E A NEGAÇÃO58 RESUMO 60 EXERCÍCIOS 60
7. ESTRUTURAS DE DADOS62
7.1 RECUPERAÇÃO DE INFORMAÇÕES62 7.2 ABSTRAÇÃO DE DADOS64 7.3 UM AUTÔMATO FINITO NÃO-DETERMINÍSTICO65 7.4 PLANEJAMENTO DE ROTEIROS AÉREOS67 RESUMO 69 EXERCÍCIOS 69
8. ENTRADA E SAÍDA71
8.1 ARQUIVOS DE DADOS71 8.2 PROCESSAMENTO DE ARQUIVOS DE TERMOS73 8.3 PROCESSAMENTO DE CARACTERES77 8.4 CONVERSÃO DE TERMOS78 8.5 LEITURA DE PROGRAMAS79 RESUMO 80 EXERCÍCIOS 80
9. PREDICADOS EXTRALÓGICOS82
9.1 TIPOS DE TERMOS82 9.2 CONSTRUÇÃO E DECOMPOSIÇÃO DE TERMOS84 9.3 EQUIVALÊNCIAS E DESIGUALDADES85 9.4 PROGRAMAS OU BASES DE DADOS?86 9.5 RECURSOS PARA O CONTROLE DE PROGRAMAS89
9.6 BAGOF, SETOF E FINDALL89 RESUMO 91 EXERCÍCIOS 91
10. LÓGICA E BASES DE DADOS93
10.1 BASES DE DADOS RELACIONAIS93 10.2 RECUPERAÇÃO DE INFORMAÇÕES95 10.3 ATUALIZAÇÃO DA BASE DE DADOS96 10.4 MODELAGEM DE DADOS97 10.5 ALÉM DO MODELO RELACIONAL99 10.6 REDES SEMÂNTICAS99 RESUMO 103 EXERCÍCIOS 103
1. PROGRAMAÇÃO SIMBÓLICA105
1.1 DIFERENCIAÇÃO SIMBÓLICA105 1.2 MANIPULAÇÃO DE FÓRMULAS105 1.3 OS OPERADORES REVISITADOS105 1.4 AVALIAÇÃO DE FÓRMULAS106 1.5 SIMPLIFICAÇÃO ALGÉBRICA107 1.6 INTEGRAÇÃO109 RESUMO 109 EXERCÍCIOS 110
12. METODOLOGIA DA PROGRAMAÇÃO EM LÓGICA111
12.1 PRINCÍPIOS GERAIS DA BOA PROGRAMAÇÃO111 12.2 COMO PENSAR EM PROLOG112 12.3 ESTILO DE PROGRAMAÇÃO114 12.4 DEPURAÇÃO DE PROGRAMAS116 12.5 EFICIÊNCIA117 12.6 PROGRAMAÇÃO ITERATIVA122 RESUMO 123 EXERCÍCIOS 124
13. OPERAÇÕES SOBRE ESTRUTURAS DE DADOS125
13.1 CLASSIFICAÇÃO EM LISTAS125 13.2 REPRESENTAÇÃO DE CONJUNTOS127 13.3 DICIONÁRIOS BINÁRIOS129 13.4 INSERÇÃO E REMOÇÃO DE ITENS EM DICIONÁRIOS BINÁRIOS130 13.5 APRESENTAÇÃO DE ÁRVORES133 13.6 GRAFOS133 RESUMO 138 EXERCÍCIOS 139
14. ESTRATÉGIAS PARA A SOLUÇÃO DE PROBLEMAS140
14.1 CONCEITOS BÁSICOS140 14.2 PESQUISA EM PROFUNDIDADE143 14.3 PESQUISA EM AMPLITUDE146 14.4 PESQUISA EM GRAFOS, OTIMIZAÇÃO E COMPLEXIDADE150 RESUMO 151 EXERCÍCIOS 151
15. PESQUISA HEURÍSTICA153
15.1 BEST-FIRST SEARCH153 15.2 UMA APLICAÇÃO DA PESQUISA HEURÍSTICA158 RESUMO 160 EXERCÍCIOS 161
16. REDUÇÃO DE PROBLEMAS E GRAFOS E/OU162
16.1 REPRESENTAÇÃO DE PROBLEMAS162 16.2 EXEMPLOS DE REPRESENTAÇÃO DE PROBLEMAS EM GRAFOS E/OU165 16.3 PROCEDIMENTOS BÁSICOS DE PESQUISA EM GRAFOS E/OU167 16.4 PESQUISA HEURÍSTICA EM GRAFOS E/OU170 RESUMO 178 EXERCÍCIOS 178
APÊNDICE A179
A.2 SEMÂNTICA MODELO-TEORÉTICA182 A.3 SEMÂNTICA PROVA-TEORÉTICA189
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 graduaçã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 emprego é 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 investigou 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 processadores poderosos a custos reduzidos, bem como pela disseminação do uso de arquiteturas paralelas.
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 especificaçã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 editorial, 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. 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 supostamente 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 mundo, 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 declaraçõ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 entender 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ática 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ógica na 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 formalizaçã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. Alguns 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 teoria 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, realizados pelo alemão Kurt Gödel e o francês Jacques Herbrand. Ambos, em suas dissertações de doutorado, 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 produzido por Gödel, em 1931, com a descoberta do "teorema da incompleteza dos sistemas de formalização da aritmética". A prova deste teorema se baseava nos denominados paradoxos de autoreferê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.
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, diversos 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 computacional 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 oferecer 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 simples 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 objetos 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 possí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 Princípio da Resolução com a programação de computadores deve-se a Cordell C. Green (1969) que mostrou 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 Robert 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 computacional, 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 essencial, necessário para adaptar os conceitos relacionados com a prova de teoremas às técnicas computacionais já dominadas pelos programadores. Aperfeiçoamentos realizados nas técnicas de implementação também foram de grande importância para o emprego da lógica como linguagem de programaçã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 també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 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 solucionado, 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 atravé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 sentenças de um programa em 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 convencional e programação em lógica.