|Did you know ...||Search Documentation:|
|Pack tabling_dra -- README.md|
Port to SWI-Prolog's C @ https://github.com/logicmoo/swipl-devel/ for the "dra" memoizing interpreter
General description Written by Feliks Kluzniak at UTD (January 2009). -------------------
A simple (and very inefficient) interpreter that emulates "top-down tabled programming", as described in
 Hai-Feng Guo, Gopal Gupta: Tabled Logic Programming with Dynamic Ordering of Alternatives (17th ICLP, 2001)
There are two significant changes with respect to the description in the paper:
Here, "new answer for a tabled goal" means an answer that has not yet been seen (and tabled) for a variant of the goal.
The default behaviour is intended to help computations converge more quickly. The user is given an option to change it, because some predicates may produce a very large (even infinite) set of answers on backtracking, and the application might not require those answers.
The terminology has been modified under the influence of
 Neng-Fa Zhou, Taisuke Sato, Yi-Dong Shen: Linear Tabling Strategies and Optimizations (TPLP 2008 (?))
More specifically, "masters" are called "pioneers" (although in a sense somewhat different than in : we use "pioneer" for "topmost looping goal"), and "strongly connected components" are called "clusters".
Note that "clusters" are detected dynamically, to achieve greater precision (a dependency graph among static calls can only be a rough approximation, a dependency graph among predicates is rougher still).
Some predicates are "tabled", because the user has declared them to be such by using an appropriate directive, e.g.,
:- table p/2 .
All calls to a tabled predicate that are present in the interpreted program are called "tabled calls". Instances of such calls are called "tabled goals". In general, we will use the term "call" to refer to a static entity in the program, and "goal" to refer to an instance of a call. We will also avoid the conventional overloading of the term "goal" in yet another way: we will call a sequence (i.e., conjunction) of goals just that (unless we can refer to it as a "query" or a "resolvent").
Similarly, the user can declare a predicate to be "coinductive", by using another kind of directive, e.g.,
:- coinductive0 p/2 . :- coinductive1 q/3 .
Calls and goals that refer to a coinductive predicate will also be called "coinductive".
Data structures ---------------
The interpreter uses a number of tables that store information accumulated during a computation. A computation consists in reading a program and executing a number of queries. A query is a sequence (i.e., conjunction) of goals.
The tables (implemented as dynamic predicates of Prolog) are:
-- is_coinductive0( generic head ) -- is_coinductive1( generic head ) -- is_tabled( generic head ) -- is_old_first( generic head )
Each of these tables contains an entry for each predicate that has been declared as having the corresponding property (i.e., as coinductive, table etc.). For instance, when the interpreter reads :- coinductive0 p/2 . it stores the fact is_coinductive0( p( _, _ ) ). A "coinductive0" declaration is deemed to supersede "coinductive1", and information about a predicate that has been so declared is stored both in coinductive0/1 and coinductive1/1. These tables are cleared only before reading in a new program.
a) Tabled and coinductive predicates should be declared as such in the program file, e.g., :- table ancestor/2. :- coinductive0 comember/2. :- coinductive1 comember/2.
"coinductive1" means that if there are coinductive hypotheses with which a goal unifies, then the usual clauses will not be tried after the hypotheses are exhausted (this is "new style" coinduction).
b) To include files use the usual Prolog syntax: :- [ file1, file2, ... ].
c) To declare predicates used in an interpreted program as dynamic, use :- dynamic p/k.
d) By default, a goal produces new (i.e., heretofore unknown) answers before producing old ones. To reverse this behaviour, use
:- old_first p/k.
or :- old_first all.
e) To produce a wallpaper traces use the traces directive. For example,
:- traces p/3, q/0, r/1.
:- traces all.
These directives are cumulative.
f) To print out subsets of the current answer table, use
:- answers( Goal, Pattern ).
this will print all tabled answers that are associated with a variant of Goal and unifiable with Pattern. To get a dump of the entire table, use just
:- answers( _, _ ).
[K steps, M new answers tabled (N in all)]
where K, M and N are some natural numbers. K is the number of evaluated goals, M is the number of new additions to the answer table, N is the current size of the answer table.
essence_hook( T, T ).
This predicate is invoked in certain contexts when:
The primary intended use is to suppress arguments that carry only administrative information and that may differ in two terms that are "semantically" equal or variants of each other. (Such, for example, is the argument that carries the set of coinductive hypotheses in a co-logic program translated into Prolog: see "../coind/translate_clp". Mind you, that translation need not be applied to programs executed by this interpreter).
For example, the presence of
essence_hook( p( A, B, _ ), p( A, B ) ).
will result in "
p( a, b, c )" and "
p( a, b, d )" being treated as
identical, as each of them will be translated to "
p( a, b )" before
NOTE: This facility should be used with the utmost caution, as it may drastically affect the semantics of the interpreted program in a fashion that would be hard to understand for someone who does not understand the details of the interpreter.
The top level notes "never_tabled" declarations in the table "is_never_tabled". For example,
:- never_tabled p/1, q/2.
will be stored as
is_never_tabled( p( _ ) ). is_never_tabled( q( _, _ ) ).
The intended meaning is that "never_tabled" predicates do not make use (directly or indirectly) of the special features provided by the metainterpreter, so their invocations can be handled just by handing them over to Prolog (which would presumably speed up the computation).
Please note that the never_tabled predicates (which should be defined in files mentioned in ":-
load_is_support( filename )." directives) are compiled into the module "never_tabled" (unless they are defined within other modules).
The metainterpreter should provide the following predicates ("hooks") that will be called by the top level:
Defines patterns for built-in predicates from the host system that can be invoked by the interpreted program. For example, to allow writeln/2, declare:
is_cuts_ok( writeln( _, _ ) ).
This will be called before loading a new program, giving the metainterpreter an opportunity to (re)initialise its data structures.
Whenever the top level encounters a legal directive ":- D" (see above), it invokes "
process_directive( D )" to give the interpreter a chance to act upon the directive.
This would be the main entry point of the metainterpreter. Whenever the top level encounters a query (of the form "?- Q."), it will display the query and then call "
dra_call_interp( Q )". Depending on the result, it will then display "No", or "Yes" (preceded by a display of bindings acquired by the variables occurring in "Q"); in the latter case it will also backtrack to obtain more solutions.