Practical Work: Tabling in Logic Programming

Tabling is a recognized and powerful implementation technique that improves the declarativeness of traditional Prolog systems in dealing with recursion and redundant computations. Tabling consists of saving and reusing the results of sub-computations during the execution of a program and, for that, the calls and the answers to tabled subgoals are stored in a proper data structure called the table space.

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 use iterative computations of tabled subgoals to compute fix-points. The main idea of linear tabling is to maintain a single execution tree where tabled subgoals always extend the current computation without requiring suspension and resumption of sub-computations

The most efficient approach to support tabled evaluation in a Prolog system is to modify and extend the low-level engine. Although this approach is ideal for run-time efficiency, it is not easily portable to other Prolog systems as engine level modifications are rather complex and time consuming. A simpler approach is to apply source level transformations to a tabled program and then use external tabling primitives to provide direct control over the search strategy. In this work, it is proposed that you use the latter approach to implement linear tabling on top of the Yap Prolog system.


We can distinguish two main components for the proposed approach: the component that implements the source level transformations and the component that implements the support for the external tabling primitives. For the purpose of this work, you can consider that programs are already re-written as desired and only the support for the external tabling primitives is missing.

To implement the table space you can take advantage of the tries module of the Yap system. The tries module can be loaded in Yap with the directive:

:- use_module(library(tries)).

Some examples of tabled programs and on how to use the tries module can be found here.

What to Deliver?

A ZIP file including: The correction of the implementation will be more valuable than its efficiency. A good structure and readability of the code will be also valued.


The ZIP file (containing the items described above) must be submitted by email until April 20 and presented orally in the week after (April 23-27, date/time to be specified).