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

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2010

Autores

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

Ata de Conferência Internacional

Título: PRACTICAL ASPECTS OF DECLARATIVE LANGUAGES, PROCEEDINGS

Páginas: 279-293

12th International Symposium on Practical Aspects of Declarative Languages

Madrid, SPAIN, JAN 18-19, 2010

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 3 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 15