Tabulação com Operadores de Modo em Programas Lógicos

João Santos

December 2010

---

Abstract

Logic programming languages, like Prolog, allow the programmer to concentrate on the problem’s declaration instead of worrying about the details of its resolution. Despite Prolog’s popularity, its resolution mechanism shows some limitations that can lead to situations in which queries to syntactically correct programs get into infinite loops. Tabling is an implementation technique that enables the solution of such problems in a very elegant way. This technique is based on saving and reusing the results of sub-computations during the execution of a program and, for that, the results and the tabled subgoals are stored in a proper data structure called the table space.
When we want to evaluate a predicate using tabling, we just need to declare it as table p/n at the top of the program, where p is the predicate name and n its arity. In this thesis, we present an alternative form of declaration of tabled predicates and, for that, we use statements like p(a1, ..., an), where p is the tabled predicate and the ai’s are mode operators. These operators allow the programmer to define different criteria for optimizing the answers that are inserted into the table space. The features added by these operators can then be elegantly used and applied to solve problems of Justification, Preferences and Answer Subsumption.
This thesis addresses the use of such operators in these three areas. We start by seeing how these operators can be used in the generation of justifications for the answers found during the execution of a program. Next, we discuss the set of transformations that allow preference problems to be implemented using mode operators and, then, we discuss the implementation of an answer subsumption mechanism using mode operators. We end this thesis by explaining the changes made to the YapTab engine, the Yap Prolog’s tabling mechanism, in order to support the implementation of this new type of declaration.

Bibtex

@MastersThesis{santos-msc,
  author =  {J. Santos},
  title =   {{Tabulação com Operadores de Modo em Programas Lógicos}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {December},
  year =    {2010},
  type =    {{MSc Thesis}},
  note =    {In Portuguese},
}

Download Thesis

PDF file