Programação em logica, prolog e restriçõs : poder de expressão v.s. eficiencia

Orientadores: Antonio E. Costa Pereira, Tomasz KowaltowskiDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica Estatistica e Ciencia da ComputaçãoResumo: Apresenta-se inicialmente uma introdução à programação em lógica através de uma abordagem evolutiva. Começando de um sistema formal de primeira ordem bastante complexo, descreve-se o conceito de prova de teoremas e sua automação. A partir daí apresenta-se a idéia de eficiência da prova. Os principais avanços obtidos durante o século XX nesta área são apontados, dando-se ênfase ao princípio de resolução de Robinson. Ao restringir a linguagem do sistema formal às sentenças de Horn, obtem-se uma grande melhora da eficiência do mecanismo de prova, preservando razoável poder de expressão. Alguns problemas relativos à expressividade da linguagem são apontados assim como formas em que têm sido abordados na atualidade. Uma delas é a programação por restrições. Na segunda parte do trabalho é apresentada a implementação de um interpretador/sistema de execução para a linguagem Prolog. A partir de uma especificação breve, de alto nivel, são introduzidos, incrementalmente, os detalhes de implementação de nivel mais baixo (estruturas de dados, controle de execução) até se obter um programa puramente procedimental escrito numa linguagem convencional (C). Finalmente, os conceitos de programação por restrições mencionados no inicio do trabalho são apresentados de forma mais detalhada para que se possa ter uma visão mais clara do seu funcionamento na prática. Assim, adotando uma abordagem semelhante à utilizada para descrever o compilador Prolog, é apresentado um interpretador de alto nivel para programas de restrições e, após alguns refinamentos, é obtido um conjunto de instruções que pode ser implementado numa linguagem de programação convencional.Abstract: An introduction to logic programming is initially presented by means of an evolutionary approach. Starting with a fairly complex first order formal system, the concepts of theorem proving and its automatization are described. From there the idea of proof efficiency is presented. The most significant advances obtained during the 20th century in this area are pointed out emphasizing Robinson's resolution principle. Restraining the formal system's language to Horn sentences, a major improvement of the proof mechanism is obtained, preserving reasonable expressive power. Some problems related to language expressiveness and the ways in which they have been recently approached are shown. One of these approaches is constraint programming. In the second part of the work, the implementation of an interpreter/runtime system for the Prolog language is shown. From a brief, high-level specification, lower-level implementation details (data structures, execution control) are introduced until a purely procedural program written in a conventional language (C) is obtained. Finally, the contraint programming concepts mentioned in the first part are presented in a more detailed form in order to allow for a clearer vision of how it works in practice. Thus, by means of an approach similar to that used to describe the Prolog compiler, a high-level interpreter for constraint programs is presented and, after some refinements, an instruction set that may be implemented in a conventional programming language is obtained.MestradoMestre em Ciência da Computaçã