Hostname: page-component-7b7567c8c-tnzcf Total loading time: 0 Render date: 2026-11-14T09:50:18.682Z Has data issue: false hasContentIssue false

On combining linear-based strategies for tabled evaluation of logic programs

Published online by Cambridge University Press:  06 July 2011

MIGUEL AREIAS
Affiliation:
CRACS & INESC-Porto LA, Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: miguel-areias@dcc.fc.up.pt, ricroc@dcc.fc.up.pt)
RICARDO ROCHA
Affiliation:
CRACS & INESC-Porto LA, Faculty of Sciences, University of Porto, Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal (e-mail: miguel-areias@dcc.fc.up.pt, ricroc@dcc.fc.up.pt)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Tabled evaluation is a recognized and powerful technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant subcomputations. We can distinguish two main categories of tabling mechanisms: suspension-based tabling and linear tabling. While suspension-based mechanisms are considered to obtain better results in general, they have more memory space requirements and are more complex and harder to implement than linear tabling mechanisms. Arguably, the SLDT and Dynamic Reordering of Alternatives (DRA) strategies are the two most successful extensions to standard linear tabled evaluation. In this work, we propose a new strategy, named dynamic reordering of solutions, and we present a framework, on top of the Yap system, that supports the combination of all these three strategies. Our implementation shares the underlying execution environment and most of the data structures used to implement tabling in Yap. We thus argue that all these common features allows us to make a first and fair comparison between these different linear tabling strategies and, therefore, better understand the advantages and weaknesses of each, when used solely or combined with the others.

Information

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2011