On Applying Linear Tabling to Logic Programs

Abstract

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.