On Applying Linear Tabling to Logic Programs

• Tipo: Tese
• Data: 2010

Autores

MIGUEL AREIAS (Autor) FCUP; Ricardo Rocha (Coordenador) FCUP

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

CORDIS: Ciências Físicas > Ciência de computadores

Instituições Associadas

FCUP - Faculdade de Ciências da Universidade do Porto

Outras Informações

Resumo (PT): As linguagens de Programação em Lógica que derivam da lógica de Horn, tal como o Prolog, têm mecanismos de resolução baseados em inferência que são bastante conhecidos. Embora o Prolog seja uma linguagem com bastante sucesso, o seu potencial é limitado pelo seu mecanismo de resolucão, que é baseado na resolucão SLD. O mecanismo de resolução SLD foi provado ser bastante ineficiente quando avalia programas logicos que têm ciclos infinitos ou sub-computações redundantes. A tabulacão é uma técnica de implementação bastante reconhecida e poderosa que permite ultrapassar essas limitações em sistemas de Prolog que são baseados na resolução SLD. Actualmente, a técnica de tabulação pode ser dividida em dois grandes mecanismos: por suspensão das pilhas de execução e por execução linear. Os mecanismos por suspensão das pilhas de execução são considerados terem melhores resultados, no entanto eles têm mais requisitos em termos de memória e são mais complexos de implementar do que os mecanismos lineares. O trabalho apresentado nesta tese pretende fazer um estudo aprofundado sobre os mecanismos de tabulação linear, de forma a perceber como as diferentes estratégias de tabulação afectam o fluxo de avaliação de um programa lógico e melhoram a performance geral do sistema. As estratégias SLDT e DRA são duas das mais conhecidas e bem sucedidas estratégias implementadas em sistemas de tabulação linear. Neste trabalho, propomos uma nova estratégia, que foi denominada de DRS, e apresentamos uma plataforma integrada, que suporta a combinação das três estratégias. A nossa implementação partilha o ambiente de execução e a maioria das estructuras de dados usadas pela máquina de execução do YapTab, que é o actual mecanismo de tabulação baseado em suspensão de pilhas do sistema Yap Prolog. A combinação de todas as estratégias e mecanismos na nossa plataforma permitiu-nos fazer uma primeira comparação justa entre todas as estratégias lineares, usadas sozinhas ou combinadas, e o mecanismo original do YapTab, de forma a perceber as vantagens e desvantagens de cada um. Os resultados obtidos, confirmam que os mecanismos baseados em suspensão têm, no geral, melhores resultados do que os mecanismos lineares, sendo que a diferença entre os resultados de ambos os sistemas pode ser em grande parte reduzida através da combinação correcta das melhores estratégias lineares.

Abstract (EN): Logic programming languages, such as Prolog, are derived from Horn Clause Logic and provide a well understood resolution based inference mechanism. Although Prolog is a popular and successful language, its potential is limited by the SLD resolution method on which it is based. SLD resolution was proven to be inecient when dealing with innite loops and redundant subcomputations. Tabled evaluation is a recognized and powerful technique that overcomes those limitations on traditional Prolog systems based on SLD resolution. We can distinguish two main categories of tabling mechanisms: suspension-based tabling and linear-based tabling. While suspension-based mechanisms are considered to obtain better results in general, they have more memory space requirements and are more complex and hard to implement than linear tabling mechanisms. The work presented on this thesis was focused on making a deep study about linear tabling, in order to understand how dierent linear tabling strategies can aect the evaluation ow of tabled programs and improve its overall performance. Arguably, the SLDT and DRA strategies are the two most successful extensions to standard linear tabled evaluation. In this work, we propose a new strategy, named DRS, and we present a framework, on top of the Yap system, that supports the combination of all these three linear tabling strategies. Our implementation shares the underlying execution environment and most of the data structures used to implement tabling in the YapTab engine, which is the actual suspension-based tabling mechanism of the Yap Prolog system. All these common features allows us to make a rst and fair comparison between the linear tabling strategies, used solely or combined with the other, and YapTab's suspension-based mechanism, in order to better understand the advantages and weaknesses of each feature. The obtained results conrmed that suspension-based mechanisms have, in general, better performance than linear tabling and that the dierence between both mechanisms can be highly reduced by using the correct combination of linear tabling strategies.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Notas: Academic Department: Department of Computer Science, Faculty of Sciences, University of Porto

Nº de páginas: 138