Batched Evaluation of Linear Tabled Logic Programs
Miguel Areias and Ricardo Rocha
2013
Abstract
Logic Programming languages, such as Prolog, provide a high-level,
declarative approach to programming. Despite the power, flexibility
and good performance that Prolog systems have achieved, some
deficiencies in Prolog's evaluation strategy - SLD resolution - limit
the potential of the logic programming paradigm. Tabled evaluation is
a recognized and powerful technique that overcomes SLD's
susceptibility in dealing with recursion and redundant
sub-computations. In a tabled evaluation, there are several points
where we may have to choose between different tabling operations. The
decision on which operation to perform is determined by the scheduling
algorithm. The two most successful tabling scheduling algorithms are
local scheduling and batched scheduling. In previous work, we have
developed a framework, on top of the Yap Prolog system, that supports
the combination of different linear tabling strategies for local
scheduling. In this work, we propose the extension of our framework to
support batched scheduling. In particular, we are interested in the
two most successful linear tabling strategies, the DRA and DRE
strategies. To the best of our knowledge, no other Prolog system
supports both strategies simultaneously for batched scheduling. Our
experimental results show that the combination of the DRA and DRE
strategies can effectively reduce the execution time for batched
evaluation.
Bibtex
@Article{areias-comsis13,
author = {M. Areias and R. Rocha},
title = {{Batched Evaluation of Linear Tabled Logic Programs}},
journal = {Journal of Computer Science and Information Systems,
Special Issue on Advances in Model Driven Engineering, Languages and Agents},
pages = {1775--1797},
volume = {10},
number = {4},
month = {October},
year = {2013},
}
Download Paper
PDF file
Computer Science and Information Systems