Completely Evaluated Subgoals

Knowing when a subgoal is completely evaluated can be useful when programming with tabling. Simply put, a subgoal $S$ is completely evaluated if an evaluation can produce no more answers for $S$. The computational strategy of XSB makes great use of complete evaluation so that understanding this concept and its implications can be of great help to a programmer.

Consider a simple approach to incorporating negation into tabling. Each time a negative goal is called, a separate table is opened for the negative call. This evaluation of the call is carried on to termination. If the evaluation terminates, its answers if any, are used to determine the success of failure of the calling goal. This general mechanism underlies early formulations for tabling stratified programs [21,40]. Of course this method may not be efficient. Every time a new negative goal is called, a new table must be started, and run to termination. We would like to use information already derived from the computation to answer a new query, if at all possible -- just as with definite programs.

XSB addresses this problem by keeping track of the state of each subgoal in the table. A call can have a state of complete, incomplete or not_yet_called. Calls that do have table entries may be either $complete$ or $incomplete$. A subgoal in a table is marked $complete$ only after it is determined to be completely evaluated; otherwise the subgoal is $incomplete$. If a tabled subgoal is not present in the table, it is termed not_yet_called. XSB contains predicates that allow a user to examine the state of a given table (Section 6.12).

Using these concepts, we can overview how tabled negation is evaluated for stratified programs. If a literal tnot(S) is called, where S is a tabled subgoal, the evaluation checks the state of S. If S is $complete$ the engine simply determines whether the table contains an answer for S. Otherwise the engine $suspends$ the computation path leading to tnot(S) until S is completed (and calls S if necessary). Whenever a suspended subgoal tnot(S) is completed with no answers, the engine resumes the evaluation at the point where it had been suspended. We note that because of this behavior, tracing programs that heavily use negation may produce behavior unexpected by the user.