Trouble in Paradise: Answer Completion

The engine for XSB performs both Prolog style and answer resolution, along with delay and simplification. What it does not do is to perform an operation called answer completion which is needed in certain (pathological?) programs.

Exercise 5.3.7   Consider the following program:

:- table p/1,r/0,s/0.
ac_p(X):- ac_p(X).
ac_p(X):- tnot(ac_s).

ac_s:- tnot(ac_r).
ac_s:- ac_p(X).

ac_r:- tnot(ac_s),ac_r.

Using either the predicate from Exercise 5.3.6 or some other method, determine the truth value of ac_p(X). What should the value be? (hint: what is the value of ac_s/1?).

For certain programs, XSB will delay a literal (such as ac_p(X) that it will not be able to later simplify away. In such a case, an operation, called answer completion is needed to remove the clause

      p(X):- p(X)|

Without answer completion, XSB may consider some answers to be undefined rather than false. It is thus is sound, but not complete for terminating programs to the well-founded semantics. Answer completion is not available for Version 2.5 of XSB, as it is expensive and the need for answer completion arises rarely in practice. However answer completion will be included at some level in future versions of XSB.