Multithreaded Tabling for Logic Programming

Miguel Areias

May 2015


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.


  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