Multithreaded Tabling for Logic Programming
Miguel Areias
May 2015
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.
Tabling is a recognized and powerful technique that improves the
declarativeness and expressiveness of traditional Prolog systems in
dealing with recursion and redundant computations. In a nutshell,
tabling consists of storing intermediate answers for subgoals so that
they can be reused when a similar subgoal appears. The tabling
technique can thus be viewed as a natural tool to implement dynamic
programming problems, where a general recursive strategy divides a
problem in simple sub-problems that, often, are the same.
Multithreading is a technique that enables computers to support
multiple concurrent paths of execution within a single process without
the need of having an entire copy of the program. When tabling is
combined with multithreading, we have the best of both worlds, since
we can exploit the combination of higher declarative semantics with
higher procedural control. However, despite the availability of both
tabling and multithreading in some Prolog systems, the implementation
of these two features implies complex ties to each other and to the
underlying engine.
In this thesis, we propose a new approach for multithreaded tabling
where each thread views its tables as private but, at the engine
level, we will use common table space where tables are shared among
all threads. We present three designs for our common table space
approach: No Sharing (NS), Subgoal Sharing (SS) and Full Sharing (FS),
and show how to exploit their advantages. Additionally, we introduce a
novel memory allocator and two lock-free trie data structures that are
specially aimed for environments with the characteristics of our
framework. The results obtained with this thesis are very promising
and open several research directions for future work.
Bibtex
@PhdThesis{areias-phd,
author = {M. Areias},
title = {{Multithreaded Tabling for Logic Programming}},
school = {University of Porto},
address = {Portugal},
month = {May},
year = {2015},
type = {{PhD Thesis}},
}
Download Thesis
PDF file