Probabilistic Logic Programming (PLP) emerged as one of the most prominent approaches to cope with real-world domains. The distribution semantics is one of most used in PLP, as it is followed by many languages, such as Independent Choice Logic, PRISM, pD, Logic Programs with Annotated Disjunctions (LPADs) and ProbLog. A possible system that allows performing inference on LPADs is PITA, which transforms the input LPAD into a Prolog program containing calls to library predicates for handling Binary Decision Diagrams (BDDs). In particular, BDDs are used to compactly encode explanations for goals and e ciently compute their probability. However, PITA needs modedirected tabling (also called tabling with answer subsumption), which has been implemented in SWI-Prolog only recently. This paper shows how SWI-Prolog has been extended to include correct answer subsumption and how the PITA transformation has been changed to use SWI-Prolog implementation.
Probabilistic Programming (PP) [
In PLP, the distribution semantics [
The PITA algorithm (for \Probabilistic Inference with Tabling and Answer
subsumption"), presented in [
Tabling is a logic programming technique for saving time and ensuring termination for programs without function symbols. With tabling, the Prolog interpreter keeps a store of the subgoals encountered in a derivation together with answers to these subgoals. The stored answers are then retrieved in successive calls of the subgoals, to avoid their re-computation and in nite loops.
PITA is also used in machine learning systems: EMBLEM [
Initially, PITA was implemented in the XSB and YAP systems, which allow
the use of answer subsumption. We decided to port it to SWI-Prolog in order to
exploit the SWISH framework for developing web applications [
The porting of PITA to the SWI-Prolog system led to the extension of its tabling implementation to feature answer subsumption as well. With answer subsumption, or mode-directed tabling, the answers for a goal are aggregated when the individual answers are not needed.
In this paper, we discuss the extension implemented in SWI-Prolog's tabling and present how we modi ed PITA to cope with the new SWI-Prolog implementation of mode-directed tabling.
The paper is organized as follows. Section 2 brie y introduces PLP and in particular the LPAD language. Section 3 discusses tabling in SWI-Prolog, while Section 4 illustrates the implementation of answer subsumption. Section 5 presents the PITA algorithm and transformation, and Section 6 its adaptation to SWI-Prolog. Finally, Section 7 concludes the paper. 2
PLP languages under the distribution semantics [
Logic Programs with Annotated Disjunctions (LPADs) [
In LPADs, heads of clauses are disjunctions in which each atom is annotated with a probability. An LPAD T is a nite set of clauses: T = fC1; : : : ; Cng. Each clause Ci takes the form: hi1 : i1; : : : ; hivi : ivi : bi1; : : : ; biui , where hi1; : : : ; hivi are logical atoms, bi1; : : : ; biui are logical literals and i1; : : : ; ivi are real numbers in the interval [0; 1] that sum to 1. bi1; : : : ; biui is indicated with body(Ci). Note that if vi = 1 the clause corresponds to a non-disjunctive clause. We also allow clauses where Pvki=1 ik < 1: in this case the head of the annotated disjunctive clause implicitly contains an extra atom null that does not appear in the body of any clause and whose annotation is 1 Pvki=1 ik. We denote by ground(T ) the grounding of an LPAD T .
We present here the semantics of LPADs for the case of no function symbols,
for the case of function symbols see [
Each grounding Ci j of a clause Ci corresponds to a random variable Xij
with values f1; : : : ; vig, i.e., it indicates which head literal is chosen. The random
variables Xij are independent of each other. An atomic choice [
A selection is a set of atomic choices that, for each clause Ci j in ground(T ), contains an atomic choice (Ci; j ; k). A selection identi es a normal logic program l de ned as l = f(hik : body(Ci)) j j(Ci; j ; k) 2 g. l is called a world of T . Since the random variables associated to ground clauses are independent, we can assign a probability to instances: P (l ) = Q(Ci; j;k)2 ik.
We consider only sound LPADs where, for each selection , the well-founded model of the program l chosen by is two-valued. We write l j= q to mean that the query q is true in the well-founded model of the program l . Since the well-founded model of each world is two-valued, q can only be true or false in l .
We denote the set of all instances by LT . Let P (l) be the distribution over instances. The probability of a query q given an instance l is P (qjl) = 1 if l j= q and 0 otherwise. The probability of a query q is given by
P (q) = X P (q; l) = X P (qjl)P (l) = l2LT l2LT
X l2LT :lj=q
P (l) (1) Example 1. The following LPAD models the appearance of medical symptoms as a consequence of disease. A person may sneeze if he has the u or if he has hay fever:
C1 = strong sneezing(X) : 0:3 ; moderate sneezing(X) : 0:5
u(X): C2 = strong sneezing(X) : 0:2 ; moderate sneezing(X) : 0:6
hay fever (X): C3 = u(bob):
C4 = hay fever (bob): Here clauses C1 and C2 have three alternatives in the head of which the one associated to atom null is left implicit. This program has 9 worlds, the query strong sneezing(bob) is true in 5 of them, and P (strong sneezing(bob)) = 0:3 0:2 + 0:3 0:6 + 0:3 0:2 + 0:2 0:5 + 0:2 0:2 = 0:44. 3
Tabling is a logic programming technique for saving time and ensuring termination for programs without function symbols.
With tabling, the Prolog interpreter keeps a store of the subgoals encountered
in a derivation together with answers to these subgoals. If one of the subgoals
is encountered again, its answers are retrieved from the store rather than
recomputing them. Tabling is implemented in the Prolog systems XSB [
Tabling is implemented in SWI-Prolog using delimited control [
Example 2. We report here the example shown in [
If we modify p by replacing writeln(Cont) with call(Cont), then the input would be ?- p. before shift after shift end In this case, continuation is called and, therefore, the goal writeln('after shift') is executed.
Predicates are declared as tabled using the table/1 directive. Tabled predicates are transformed in order to collect answers. This transformation makes use of the table/2 predicate, which retrieves the table data structure containing the answers to the tabled predicate.
Example 3. The program on the left is transformed in that shown on the right :- table p/2. p(X,Y) :- p(X,Z), e(Z,Y). p(X,Y) :- e(X,Y).
p(X,Y) :- table(p(X,Y),p_aux(X,Y)). ! p_aux(X,Y) :- p(X,Z), e(Z,Y).
p_aux(X,Y) :- e(X,Y).
When a tabled predicate is called, the execution enters in a delimited answer computation starting the reset phase. If this phase succeeds normally, the answer is added to the table of the tabled predicate. If the tabled predicate calls a predicate that is tabled as well, then the computation enters in the shift phase without producing an answer and the rst predicate is suspended, capturing the reminder in Cont. At this point the so-called completion phase starts, collecting all the possible continuation, to nd answers for the tabled predicate in the reset phase.
A call to a tabled predicate can be either a leader or a follower: a leader has only non-tabled ancestors in the call graph, while a follower has a tabled ancestor in the call graph. The leader and the followers that are his descendants make up a scheduling component. completion is performed on one component at a time.
Each component is associated to a global worklist, i.e., a queue of tables. There is a table for each subgoal for the tabled predicates, called call variants, mapping it to a data structure containing its answers, in the form of an answer trie.
Each table is also associated to a local worklist that is a dequeue containing answers and dependencies. A dependency is a triple formed by a source, a continuation and a target. If collecting answers for a tabled call p requires the answers for a tabled call q (q may be p itself), then p is the target and q is the source. A dependency indicates that, given an answer for the source call q, we can obtain an answer for the target call p by resuming the suspended continuation. The continuation's answer is then uni ed with p.
During the completion phase, tables from the global worklist are extracted one at a time and the local worklist of the considered table is used to nd all the answers for the corresponding tabled call. During the reset phase, each time an answer is found for a call p, it is added to the list of answers in the table for p and to the left of the dequeue of the local worklist of subgoals calling p, while each time the execution enters in the shift phase a new dependency for p is added to the right of its worklist. Then, pairs (answer, dependency) are extracted from the dequeue of the local worklist to try to nd new answers. Note that the answer in the pair is an answer for the source predicate. Pairs are created by associating an answer to the dependency that is immediately to its right in the dequeue. After the combination, the answer and the dependency just combined are swapped, moving the answer to the right of the dependency, meaning that their pair have been already tested. Then, answer and dependency from the pair are combined using values in answer to instantiate variables in source, continuation and, eventually, in target, and the predicate in continuation is called to nd new answers for the target, i.e., instantiate all the remaining free variables in target. The new answer for target is then added to the answers list in its table and to the left of the dequeue of the local worklists where the predicate is the source of some dependencies. The completion phase stops when all the answers in all the local worklists are on the left of all the dependencies, meaning that all the combinations have been tested and no more answers can be found.
Note that in the real implementation there are some minor di erences with this description due to performance reasons. For example, answers and dependencies in local worklists are considered in homogeneous batches instead of one at a time and the combination of the two batches is performed by means of Cartesian product. Moreover, the batches containing answers contain also answers for predicates di erent from that in source, however, during the combination if answer and dependency do not match then their combination is discarded.
When all the answers for the subogoal in the reset phase are found, they are returned by table/2 one at a time to continue the computation of the query. 4
As seen in the previous section, plain tabling creates an answer table per call variant and guarantees termination if the created data structures are nite. For example, this allows us to prove whether a graph connects the nodes A and B while the graph is undirected or cyclic. However, it does not allow us to return the path between A and B because an in nite number of such paths can be constructed by going back and forth or following cycles. This limitation also blocks us from obtaining all proofs for a logical theory.
The above problem is resolved using tabling with answer subsumption, also
called mode-directed tabling [
To facilitate PITA, we extended SWI-Prolog's original tabling implementation with mode-directed tabling. The speci cation was inherited from XSB, B-Prolog and YAP and includes the most generic aggregation function called lattice that allows a user de ned predicate to determine the subsumer for the aggregated answer so far and a new answer. The implementation is straight forward. The modi ed table/1 directive is used to determine the term that is used for call variant detection and compile a combined aggregation predicate that is called for each answer that is added to the table. The answer table has been extended such that each answer in the answer trie can be assigned an aggregated value. The above mentioned generated predicate is called on each answer to maintain the aggregated answer.
Note that tabling does not guarantee a particular order in which suspended computations are resumed and thus requires the aggregation function to produce the correct result regardless of the order.
Furthermore, if one mode-directed tabled goal is the follower of another as in the example below where, given the goal p(A), p/1 is the leader and s/1 the follower we get incorrect results because s/1 may succeed multiple times with partial answers. :- table p(lattice(or/3)), s(lattice(or/3)). or(A,B,A-B). p(A) :- s(A). s(1). s(2).
In the initial implementation of mode-directed tabling in SWI-Prolog, the query p(A) succeeded with answer A = 1-2-(1-2) instead of the desired A = (1-2).
This has been highlighted in [
In the semantics, aggregation is a post-processing step. Real systems
aggregate intermediate results during resolution for e ciency and to avoid loops.
The authors of [
In order to make SWI-Prolog sound, we modi ed its tabling
implementation by creating a new component for every fresh mode-directed tabled goal we
encounter. This component is completed before execution of the parent
component is resumed with the complete aggregated result. This ensures soundness
with respect to the theoretical semantics of [
The PITA system [
BDDO), or(+BDD1, +BDD2, -BDDO): Boolean operations between BDDs; { add var(+N Val,+Probs,-Var): addition of a new multi-valued variable with
N Val values and parameters Probs; { equality(+Var,+Value,-BDD): BDD represents Var=Value, i.e. that the random variable Var is assigned Value in the BDD; { ret prob(+BDD,-P): returns the probability of the formula encoded by BDD. As said above, add var(+N Val,+Probs,-Var) adds a new random variable associated to a new instantiation of a rule with N Val head atoms and parameters list Probs. The auxiliary predicate get_var_n/4 is used to wrap add_var/3 and avoid adding a new variable when one already exists for an instantiation. As shown below, a new fact var(R,S,Var) is asserted each time a new random variable is created, where R is an identi er for the LPAD clause, S is a list of constants, one for each variable of the clause, and Var is an integer that identi es the random variable associated with clause R under a particular grounding. The auxiliary predicate has the following de nition get_var_n(R,S,Probs,Var):(var(R,S,Var) ->
true ; ).
length(Probs,L), add_var(L,Probs,Var), assert(var(R,S,Var)) where Probs is a list of oats that stores the parameters in the head of rule R. R, S and Probs are input arguments while Var is an output argument. assert/1 is a builtin Prolog predicate that adds its argument to the program, allowing its dynamic extension.
The PITA transformation applies to atoms, literals, conjunction of literals and clauses. The transformation for an atom a and a variable D, P IT A(a; D), is a with the variable D added as the last argument. The transformation for a negative literal b = not a, P IT A(b; D), is the expression
(P IT A(a; DN ) ! not(DN; D); one(D)) which is an if-then-else construct in Prolog: if P IT A(a; DN ) evaluates to true, then not(DN; D) is called, otherwise one(D) is called. 4 http://vlsi.colorado.edu/~fabio/ 5 BDDs are represented in CUDD as pointers to their root node.
Example 5 (Example 1 Cont.). If we associate the random variables X11 with (C1; fX=bobg; 1), X12 with (C1; fX=bobg; 2), X13 with (C1; fX=bobg; 3) X21 with (C2; fX=bobg; 1), X22 with (C2; fX=bobg; 2) and X23 with (C2; fX=bobg; 3), the BDD corresponding with the set LT for query strong sneezing(bob) is shown in Figure 1. The probability of the query is computed by following the BDD and C11 X21 1 n1 n2 0 computing the probability of each node
Prob(n2) = 0:2 1 + 0:8 0 = 0:2
Prob(n1) = 0:3 1 + 0:7 0:2 = 0:44 so P (strong sneezing(bob)) = Prob(n1) = 0:44 as shown in Example 1. 6
PITA in SWI-Prolog adds the library predicate: { and check(+D1,+D2,-DO) fails if one of the input arguments is the BDD representing the Boolean constant 0, otherwise it succeeds returning the conjunction of the input arguments.
The tabling implementation in SWI-Prolog doesn't handle cut thus the if-thenelse construct cannot be used to implement negation. In SWI-Prolog the transformation for a negative literal b = not a, P IT A(b; DN ) is the conjunction P IT A(a; D); not(D; DN ). A conjunction of literals b1; : : : ; bm becomes: P IT A(b1; : : : ; bm; D) = one(DD0);
P IT A(b1; D1); and check(DD0; D1; DD1); : : : ;
P IT A(bm; Dm); and check(DDm 1; Dm; D): Clauses are then transformed as in PITA for XSB. Moreover, for each predicate p=n, an extra clause of the form p(X1; : : : ; Xn; D)
nonvar(X1); : : : ; nonvar(Xn); zero(D): is added to the program, where nonvar=1 is an extra-logical predicate that succeeds if its argument is not a variable. We call these zero clauses.
Such a transformation is used in combination with answer subsumption. Each predicate is tabled and answer subsumption is applied to the BDD argument added by the PITA transformation, de ning as lattice the or/3 predicate. This combines every BDD, which corresponds to a di erent explanation for the call variant of the predicate, in order to compute a nal BDD representing the set of all the explanations. If the goal fails, the only BDD returned is the one representing the 0 constant, which leads to the fail of and check/3, otherwise, the zero BDD is disjoint with other BDDs, maintaining unchanged their truth value.
In this way, negative literals b = not a are handled by rst collecting the BDD representing all the explanations for a by means of answer subsumption. The nal BDD is then negated to nd the BDD for b. 7
In this paper we presented an extension of the tabling system of SWI-Prolog
for including sound answer subsumption. Moreover, we presented an extension
of the PITA transformation, which takes an LPAD program and translates it
into a normal program using the tabling implementation of SWI-Prolog.
Possible future directions for improving the tabling implementation are sharing tables
between threads, incremental tabling, handling negation, improving space and
time performance. We will also extend PITA to handle other reasoning types,
such as inference and learning for probabilistic abductive logic programs,
extending [