Efficient Storing Mechanisms for Tabled Logic Programs

João Raimundo

December 2010


Abstract

Programming languages are an unique method to communicate with machines. Declarative languages, such as logic programming languages, provide features like a high-level and declarative syntax, simplifying the communication between man-and-machine. Arguably, Prolog is the most famous and used logic programming language. Prolog uses SLD resolution in order to provide good performance in the computation of complex real world problems. Although SLD resolution proved to be very effective, in some cases, this procedure show some restrictions when dealing with infinite loops and redundant sub-computations.
One of the most successful techniques proposed to overcome SLD's susceptibility, is tabling. The tabling mechanism consists in storing the subgoals and the respective answers of a program in a table space in such a way that, in later stages of a program's evaluation, repeated subgoal calls use the answers stored in the tables, avoiding the subgoal re-evaluation. Tabling success largely depends on the implementation of the table space, its data structures and algorithms. Arguably, the most successful data structure for tabling is tries. Nevertheless, when tabling is used in applications that have large quantities of data, it can lead to overgrown tables and quickly fill up the system's memory.
With this research, we try to provide alternative designs and structures, not only to the table space organization but also to the tabled data representation. We do so, by proposing a new design for the table space organization where all terms in tabled subgoal calls and tabled answers are represented only once in a common global trie instead of being spread over several different trie data structures, suggesting three different approaches. At tabled data representation, we propose a new representation of list terms for tries that avoids the recursive nature of the WAM representation of list terms in which tries are based.
The results obtained in our experiments when using the YapTab tabling system, show significant reductions on memory usage, without compromising running time. Memory usage is reduced when using any of the three different global trie designs and also in the new representation of list terms, providing the necessary data to make it clear that our proposals can provide more compact and efficient representations of the table space, when applying tabling mechanisms to Prolog.

Bibtex

@MastersThesis{raimundo-msc,
  author =  {J. Raimundo},
  title =   {{Efficient Storing Mechanisms for Tabled Logic Programs}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {December},
  year =    {2010},
  type =    {{MSc Thesis}},
}

Download Thesis

PDF file