Orientador : Wagner C. Amaral

Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica

Resumo: A implementação de interpretadores para a linguagem da Lógica de Ordem Superior (LOS) constitui-se num desafio ainda não vencido. Pode-se dividi-Io em duas partes: (a) tornar a linguagem mais amigável permitindo estimular sua adoção e (b) dotar as implementações com um desempenho que não...

Resumo: A implementação de interpretadores para a linguagem da Lógica de Ordem Superior (LOS) constitui-se num desafio ainda não vencido. Pode-se dividi-Io em duas partes: (a) tornar a linguagem mais amigável permitindo estimular sua adoção e (b) dotar as implementações com um desempenho que não sacrifique sua usabilidade. A linguagem de programação para a LOS utiliza os conceitos do À-cálculo e os recursos de tipificação de Russel. Sua sintaxe é portanto mais complexa do que aquela da Lógica de Primeira Ordem (LPO). A técnica de derivação de algum conhecimento em uma base
de conhecimento, formalizada conforme suas regras, assemelha-se com aquela da LPO que é chamada de resolução. Qualquer sistema de provas em LOS deve atender a restrições de uma linguagem fortemente tipada e a unificação, que apresenta problemas de incompletude, pode gerar mais do que um unificador. Isto torna a pesquisa nâ.o-determinística e faz com que a derivação contenha mais uma fonte de retroencadeamento, quando comparada com modelo de programação em LPO. Este trabalho expõe e analisa a implementação de um interpretador para a LOS sujeita a sentenças definidas positivas as quais contêm propriedades adequadas à mecanização semelhantes àquelas das cláusulas de HORN da LPO. Problemas de indecidibilidade são contornados e os vários aspectos computacionais são descritos como a formação da base de
conhecimento, sua gramática e a P-derivação, que é o método de obtenção de provas sobre a base. Central a estes procedimentos encontra-se a unificação que apresenta complexidade elevada e cujo processamento é razão de depauperação na qualidade do sistema. Uma proposta de enfoque alternativa é oferecida com o propósito de atenuar os efeitos sobre a lentidão do sistema. O algoritmo resultante indica ganhos no desempenho e apresenta uma interpretação mais facilitada do mecanismo da unificação

Abstract: Efficient Interpreter implementations for Righer Order Logic (ROL) programming language still remain as a challenge that can be splitted into two classes: (a) to make the language friendlier in order to stimulate the user to adopt it, and (b) to provi de the interpreter with a performance...

Abstract: Efficient Interpreter implementations for Righer Order Logic (ROL) programming language still remain as a challenge that can be splitted into two classes: (a) to make the language friendlier in order to stimulate the user to adopt it, and (b) to provi de the interpreter with a performance that does not damage its usability. This paper resulted from an ROL interpreter prototypation, called À-PROLOG. Only the positive definite sentençes are used in the language. They are similar to those of the First Order Logic (FOL) programing language and present some apropriate mechanization properties.
One kind of implementation is discribed and its computational aspects are analysed. They include the knowledgernent base formation, the grarnrnar of the sentences and the P-derivation, which is the method of deriving proofs over the base.
The unification is the most important interpreter procedure and has high complexity. Its processing is one of the reazons for the depaupering of system quality. In this paper the analisies of the MATCR and SIMPL algorithms that were developed for this purpose are used to supply a new unification algorithm which, in contrast to MATCR, shows initial performance gains and an easier procedural interpretation oí the unification mechanism