.\" ----------------------- seca1.t ----------------------
.sh 1 "Extension Tables"
.pp
Extension tables store the calls and answers for a predicate. If a
call has been made before, answers are retrieved from the extension
table instead of being recomputed. Extension tables provide a
caching mechanism for Prolog. In addition, extension tables affect
the termination characteristics of recursive programs. Some Prolog
programs, which are logically correct, enter an infinite loop due
to recursive predicates. An extension table saved on recursive 
predicates can find all answers (provided the set of such answers is
finite) and terminate 
for some logic programs for which Prolog's evaluation strategy 
enters an infinite loop. Iterations over the extension table 
execution strategy provides complete evaluation of queries over
function-free Horn clause programs. 
.pp	
To be able to use the simple extension table evaluation on a set of
predicates, the source file should either be consulted, or 
compiled with the \fBt\fR option (the \fBt\fR option 
keeps the assembler from optimizing subroutine linkage and allows 
the extension table facility to intercept calls to predicates). 
.pp
To use extension table execution, all predicates that are to be 
saved in the extension table must be passed to \fIet\fR/1. For example,
.(l
	| ?\- et([pred1/1, pred2/2]), et(pred3/2)
.)l
will set up ``ET-points'' for the for predicates \fIpred1\fR/1, \fIpred2\fR/2 and
\fIpred3\fR/2, which will cause extension tables for these predicates to be
maintained during execution. At the time of the call to \fIet\fR/1, these predicates
must be defined, either by having been loaded, or through \fIconsult\fR.
.pp
The predicate \fInoet\fR/1 takes a list of predicate/arity pairs for
which ET-points should be deleted.  Notice that
once an ET-point has been set up for a predicate, it will be maintained
unless explicitly deleted via \fInoet\fR/1.
If the definition of a predicate which has an ET-point defined is to be updated,
the ET-point must first be deleted via \fInoet\fR/1.
The predicate can then be reloaded and a new ET-point established.
This is enforced by the failure of the goal ``et(P/N)'' if an
ET-point already exists for the argument predicate.  In this case,
the following error message will be displayed:
.(l
	*et* already defined for: P/N
.)l
.pp			
There are, in fact, two extension table algorithms: a simple one, which
simply caches calls to predicates which have ET-points defined; and a
complete ET algorithm, which iterates the simple extension table algorithm until
no more answers can be found.  The simple algorithm is more efficient than the
complete one; however, the simple algorithm is not complete for certain 
especially nasty forms of mutual recursion, while the complete
algorithm is.  To use the simple extension table algorithm,
predicates can simply be called as usual.
The complete extension table algorithm may be used via the query
.(l
	| ?\- et_\|star(Query).
.)l
.lp
The extension table algorithm is intended for predicates that are ``essentially
pure'', and results are not guaranteed for code using impure code.
The extension table algorithm saves only those answers which are
not instances of what is already in the
table, and uses these answers if the current call is an instance of a call
already made.  For example, if a call \fIp\fR(\fIX\fR, \fIY\fR\^), with
\fIX\fR and \fIY\fR uninstantiated, is encountered and inserted into the
extension table, then a subsequent call \fIp\fR(\fIX\fR, \fIb\fR) will be
computed using the answers for \fIp\fR(\fIX\fR, \fIY\fR\^) already in the
extension table.  Notice that this might not work
if var/nonvar tests are used on the second argument
in the evaluation of \fIp\fR.
.pp
Another problem with using impure code is that if an ET predicate is cut
over, then the saved call implies that all answers for that predicate were
computed,
but there are only partial results in the ET because of the cut.
So on a subsequent call the incomplete extension table answers are used
when all answers are expected.
.(l
Example:
	r(X,Y) :\- p(X,Y),q(Y,Z),!,fail.
	| ?\-  r(X,Y) ; p(X,Y).
.)l
.lp
Let p be an ET predicate whose evaluation yields many tuples.
In the evaluation of the query, r(X,Y) makes a call to p(X,Y).
Assuming that there is a tuple such that q(Y,Z) succeeds with the
first p tuple then the evaluation of p is cut over. The call to p(X,Y)
in the query uses the extension table because of the previous call
in the evaluation of r(X,Y). Only one answer is found, whereas the
relation p contains many tuples, so the computation is not complete.
Note that "cuts" used within the evaluation of an ET predicate are ok,
as long as they don't cut over the evaluation of another ET predicate. 
The evaluation of the predicate that uses cuts does not cut over any et
processing (such as storing or retrieving answers) so that the tuples that
are computed are saved. In the following example, the ET is used to generate
prime numbers where an ET point is put on prime/1.
.(l
Example:

prime(I) :\- globalset(globalgenint(2)),fail.			/* Generating Primes */
prime(I) :\- genint(I), not(div(I)).
div(I) :\- prime(X), 0 is I mod X.

genint(N) :\- 
    repeat,
	globalgenint(N),
	N1 is N+1,
	globalset(globalgenint(N1)).
.)l
.lp
The following summarizes the library predicates supporting the extension
table facility:
.sp
.lp
\fBet\fR(\fIL\fR)
.ip
Sets up an ET-point on the predicates \fIL\fR, which causes calls and
anwers to these predicates to be saved in an ``extension table''.
.(x b
(L)	 et/1
.)x
\fIL\fR is either a term \fIPred\fR/\fIArity\fR, where \fIPred\fR is a predicate
symbol and \fIArity\fR its arity, or a set of such terms represented as a list.
\fIL\fR must be
instantiated, and the predicates specified in it defined, at the time of
the call to \fIet\fR/1.  Gives error messages and fails if any of
the predicates in \fIL\fR is undefined, or if an ET-point
already exists on any of them; in this case, no ET-point
is set up on any of the predicates in \fIL\fR.
.lp
\fBet_\|\fBstar\fR(Goal\fR\^)
.ip
Invokes the complete extension table algorithm on the goal \fIGoal\fR.
.(x b
(L)	 et_\|star/1
.)x
.lp
\fBet_\^points\fR(\fIL\fR)
.ip
Unifies \fIL\fR with a list of predicates for which an ET-point is
defined.  \fIL\fR is the empty list [] if there are no ET-points defined.
.(x b
(L)	 et_\^points/1
.)x
.lp
\fBnoet\fR(\fIL\fR)
.ip
Deletes ET-points on the predicates specified in \fIL\fR.
.(x b
(L)	 noet/1
.)x
\fIL\fR is either a term \fIP\fR/\fIN\fR, where \fIP\fR is the name of a
predicate and \fIN\fR its arity, or a set of such terms represented as a
list.  Gives error messages and
fails if there is no ET-point on any of the predicates specified in
\fIL\fR.  Deleting an ET-point for a predicate also removes the calls and
answers stored in the extension table for that predicate.  The extension
tables for all predicates for which ET-points are defined may be deleted
using \fIet_\^points\fR/1 in cojnunction with \fInoet\fR/1.

\fIL\fR must be instantiated at the time of the call to \fInoet\fR/1.
.lp
\fBet_\|remove(\fIL\^)
.ip
Removes both calls and answers for the predicates specified in \fIL\fR.  In
effect, this results in the extension table for these predicates to be set
to empty.  \fIL\fR must be instantiated at the time of the call to
either a term \fIP\fR/\fIN\fR, where \fIP\fR is a
predicate with arity \fIN\fR, or a list of such terms.  An error occurs if
any of the predicates in \fIL\fR does not have an ET-point set.

All extension tables can be emptied by using \fIet_\^points\fR/1 in
conjunction with \fIet_\^remove\fR/1.
.(x b
(L)	 et_\|remove/1
.)x
.lp
\fBet_\|answers\fR\^(\fIP\fR/\fIN\fR, \fITerm\fR\^)
.ip
Retrieves the answers stored in the extension table for the predicate \fIP\fR/\fIN\fR
in \fITerm\fR one at a time.  \fITerm\fR is of the form
\fIP\fR(\fIt\fR\*<1\*>, ..., \fIt\*<N\*>\fR).  An error results and
\fIet_\^answers\fR/2 fails if \fIP\fR/\fIN\fR is not fully specified (ground),
or if \fIP\fR/\fIN\fR does not have an ET-point set.
.lp
\fBet_\|calls\fR(\fIP/N\fR, \fITerm\fR\^)
.ip
Retrieves the calls stored in the extension table for the predicate \fIP/N\fR
in \fITerm\fR one at a time.  \fITerm\fR is of the form
\fIP\fR(\fIt\fR\*<1\*>, ..., \fIt\*<N\*>\fR).  An error results and
\fIet_\^calls\fR/2 fails if \fIP\fR/\fIN\fR is not fully specified (ground),
or if \fIP\fR/\fIN\fR does not have an ET-point set.
.(x b
(L)	 et_\|calls/2
.)x
.lp
.\" -------------------- end of section seca1.t ----------------------