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