Controle de Fluxo em Prolog por Utilização de Primitivas de Suspensão
José Vieira
July 2010
Abstract
Tabling is an implementation technique that overcomes some of the
well-known limitations of Prolog systems in dealing with infinite
loops in programs that are syntactically correct. The tabling
technique consists of storing intermediate answers for subgoals in a
proper space, called the table space, so that they can be reused when
a repeated subgoal appears. This technique can be implemented at
low-level engine or it can be implemented at an high-level, using the
Prolog language itself, by applying program transformation to add to
the original program a set of control primitives that can be also
implemented in Prolog.
In this thesis we discuss the problems, advantages and dissadvantages
of using mechanisms to suspend and resume the computation at the
Prolog level. These mechanisms can be used and are well suited for
every kind of problems and algorithms that explore a search space. We
will focus our attention to the problem of implementing the tabling
technique at an high-level by using this mecanisms but, in shuch a
way, that the execution model is very close to the execution model of
the low-level engine.
Our study showed that the high-level tabling module has slightly worse
execution times when compared to the YapTab system. These execution
times were expected. However, the fact that our implementation reduce
the complexity of the implementation, makes it quite attractive to
experiment and try different execution strategies and/or new
extensions for tabled evaluation.
Bibtex
@MastersThesis{vieira-msc,
author = {J. Vieira},
title = {{Controle de Fluxo em Prolog por Utilização de Primitivas de Suspensão}},
school = {University of Porto},
address = {Portugal},
month = {July},
year = {2010},
type = {{MSc Thesis}},
note = {In Portuguese},
}
Download Thesis
PDF file