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.
Implementation
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:
- Prolog files (can be only one) implementing the support for the
tabling primitives.
- Prolog files (one per tabled program) with the re-written code
for the given tabled programs (can be the same as the program's
transformation proposed in the examples).
- Small report (no more than 5 pages) in PDF format describing the
work done (free structure) and including:
- Brief description of the re-written algorithm.
- Brief description of the algorithm used to implement linear
tabling and provide direct control over the search strategy
(include details about the tabling primitives being used and
how they are chained, main data structures, relevant auxiliary
predicates, ...).
- Running times per tabled program and number of tabled subgoals
and tabled answers obtained during the execution of each
tabled program.
- Main difficulties encountered in the development of the work (if any).
The correction of the implementation will be more valuable than its
efficiency. A good structure and readability of the code will be also
valued.
Deadline
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).