Answers, Returns, and Templates

Given a table entry $(S,{\cal A},Status)$, the set of variables in $S$ is sometimes called the substitution factor of $S$. The order of arguments in the substitution factor corresponds to the order of distinct variables in a left-to-right traversal of $S$. Each answer in ${\cal A}$ substitutes values for the variables in the substitution factor of $S$; this substitution is sometimes called an answer substitution. The table inspection predicates allow access to substitution factors and answer substitutions through a family of terms whose principle functors are ret/n, where n is the size of the substitution factor.

Example 6.14.1   Let $S =$ p(X,f(Y)) be a producer subgoal (or simply, a subgoal if call-variance is used). Using the ret/nnotation, the substitution factor can be depicted as ret(X,Y), while the answer substitution {X=a,Y=b} is depicted as ret(a,b). Note that the application of the answer substitution to the producer subgoal yields the answer p(a,f(b)).

To take a slightly more complex example, consider the subgoal q(X) where X is an attributed variable whose attribute is f(Z,Y,Y). In this case the substitution factor is ret(X,Z,Y).$\Box$

In a similar manner, XSB maintains substitutions between producer subgoals and consuming subgoals when subsumption-based tabling is used. The return template for a consuming call is a substitution mapping variables of its producer to subterms of the call. This template can then be used to select returns from the producer which satisfy the consuming call. Note, then, that a return template of a subsumed subgoal may show partial instantiations. Return templates are also represented as ret/n terms in the manner described above.

Example 6.14.2   Let p/2 of the previous example be evaluated using subsumption and let $S$ be present in its table. Further, let $S_1$: p(A,f(B)) and $S_2$: p(g(Z),f(b)) be two consuming subgoals of $S$. Then the return template of $S_1$ is ret(A,B) and that of $S_2$ is ret(g(Z),b). $S_1$, being a variant of $S$, selects all returns of $S$ such that {X=A,Y=B}. $S_2$, on the other hand, selects only relevant answers of $S$, those where the returns satisfy {X=g(Z),Y=b}.$\Box$