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. / 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 innite 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 conrmed 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.
| Identifer | oai:union.ndltd.org:up.pt/oai:repositorio-aberto.up.pt:10216/74598 |
| Date | January 2010 |
| Creators | MIGUEL AREIAS |
| Contributors | Ricardo Rocha, Faculdade de Ciências |
| Source Sets | Universidade do Porto |
| Language | English |
| Detected Language | Portuguese |
| Type | Dissertação |
| Format | application/pdf |
| Rights | openAccess, https://creativecommons.org/licenses/by-nc/4.0/ |
Page generated in 0.0209 seconds