An Efficient Implementation of Linear Tabling Based on Dynamic Reordering of Alternatives

• Type: Article in International Conference Proceedings Book
• Date: 2010

Authors

Miguel Areias (Author) FCUP; Ricardo Rocha (Author) FCUP

Conference proceedings International

Title: PRACTICAL ASPECTS OF DECLARATIVE LANGUAGES, PROCEEDINGS

Pages: 279-293

12th International Symposium on Practical Aspects of Declarative Languages

Madrid, SPAIN, JAN 18-19, 2010

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 3 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-CBR

DOI: 10.1007/978-3-642-11503-5_23

Abstract (EN): Tabling is a technique of resolution that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. We can distinguish two main categories of tabling mechanisms: suspension-based tabling and linear tabling. In suspension-based tabling, a tabled evaluation can be seen as a sequence of sub-computations that suspend and later resume. Linear tabling mechanisms maintain a single execution tree where tabled subgoals always extend the current computation without requiring suspension and resumption of sub-computations. In this work, we present a new and efficient implementation of linear tabling, but for that we have extended an already existent suspension-based implementation, the YapTab engine. Our design is based on dynamic reordering of alternatives but it innovates by considering a strategy that schedules the re-evaluation of tabled calls in a similar manner to the suspension-based strategies of YapTab. Our implementation also shares the underlying execution environment and most of the data structures used to implement tabling in YapTab. We thus argue that all these common features allows us to make a first and fair comparison between suspension-based and linear tabling and, therefore, better understand the advantages and weaknesses of each.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15