Introduction

Probabilistic Programming (PP) [13] allows users to define complex probabilistic models and perform inference and learning on them. In fact, many real-world domains can only be represented effectively by exploiting uncertainty. To model complex domains containing many uncertain relationships among their entities, Probabilistic Logic Programming (PLP) [8,16] has emerged among the PP proposals as one of the most prominent approaches to cope with such relationships.

In PLP, the distribution semantics [22] is at the basis of many languages. Examples of languages that follow the distribution semantics are Independent Choice Logic [14], PRISM [22], Logic Programs with Annotated Disjunctions (LPADs) [28] and ProbLog [9]. All these languages have the same expressive power as a theory in one language can be translated into another [7]. LPADs offer a general syntax as the constructs of all the other languages can be directly encoded in this language.

The PITA algorithm (for "Probabilistic Inference with Tabling and Answer subsumption"), presented in [18,19,20], takes as input an LPAD and builds Binary Decision Diagrams (BDDs) for every subgoal encountered during the derivation of the query. The use of BDDs is due to the fact that they allow an efficient computation of the probability of the query. Specifically, PITA transforms the input LPAD into a normal logic program in which the subgoals have an extra argument storing a BDD that represents the explanations for their answers. As its name implies, PITA uses tabling with answer subsumption to store explanations for a goal.

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 infinite loops.

PITA is also used in machine learning systems: EMBLEM [4,3] and SLIP-COVER [5], performing respectively parameter and structure learning, use PITA for computing the probability of examples.

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 [29]. This allowed us to develop cplint on SWISH [1], a web application for probabilistic logic programming available at http://cplint.eu.

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 modified PITA to cope with the new SWI-Prolog implementation of mode-directed tabling.

The paper is organized as follows. Section 2 briefly 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.

Probabilistic Logic Programming

PLP languages under the distribution semantics [22] have been used to represent a wide variety of domains [1,2,17]. A program in a language adopting the distribution semantics defines a probability distribution over normal logic programs called worlds. Each normal program is assumed to have a total well-founded model [25]. Then, the distribution is extended to queries and the probability of a query is obtained by marginalizing the joint distribution of the query and the programs.

Logic Programs with Annotated Disjunctions (LPADs) [27] have the most general syntax among PLP languages under the distribution semantics.

In LPADs, heads of clauses are disjunctions in which each atom is annotated with a probability. An LPAD T is a finite set of clauses: T = {C 1 , . . . , C n }. Each clause C i takes the form: h i1 : Π i1 ; . . . ; h ivi : Π ivi : − b i1 , . . . , b iui , where h i1 , . . . , h ivi are logical atoms, b i1 , . . . , b iui are logical literals and Π i1 , . . . , Π ivi are real numbers in the interval [0, 1] that sum to 1. b i1 , . . . , b iui is indicated with body(C i ). Note that if v i = 1 the clause corresponds to a non-disjunctive clause. We also allow clauses where vi k=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 − vi k=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 [15].

Each grounding C i θ j of a clause C i corresponds to a random variable X ij with values {1, . . . , v i }, i.e., it indicates which head literal is chosen. The random variables X ij are independent of each other. An atomic choice [14] is a triple (C i , θ j , k) where C i ∈ T , θ j is a substitution that grounds C i and k ∈ {1, . . . , v i } identifies one of the head atoms. In practice (C i , θ j , k) corresponds to an assignment X ij = k.

A selection σ is a set of atomic choices that, for each clause C i θ j in ground(T ), contains an atomic choice (C i , θ j , k). A selection σ identifies a normal logic program l σ defined as l σ = {(h ik : − body(C i ))θ j |(C i , θ j , k) ∈ σ}. 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 σ ) = (Ci,θj ,k)∈σ Π 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 σ |= 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 L T . Let P (l) be the distribution over instances. The probability of a query q given an instance l is P (q|l) = 1 if l |= q and 0 otherwise. The probability of a query q is given by

P (q) = l∈L T P (q, l) = l∈L T P (q|l)P (l) = l∈L T :l|=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 flu or if he has hay fever:

C 1 = strong sneezing(X) : 0.3 ; moderate sneezing(X) : 0.5 ← flu(X). C 2 = strong sneezing(X) : 0.2 ; moderate sneezing(X) : 0.6 ← hay fever (X). C 3 = flu(bob). C 4 = hay fever (bob).

Here clauses C 1 and C 2 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.

Tabling

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 [24], YAP [21] and SWI-Prolog [30].

Tabling is implemented in SWI-Prolog using delimited control [10]. Delimited control [6,11] was originally introduced in functional programming and is based on two operators, implemented in SWI-Prolog with the predicates reset(Goal,Cont,Term1) and shift(Term2). The first executes the goal in Goal and unifies the other two arguments on the basis of the results of calls to shift/1 during the execution of the goal. If Goal calls shift/1, the execution of the goal is interrupted, the rest of its code up to the nearest call to reset/3, called delimited continuation, is represented as a Prolog term and unified with Cont in reset/3, while the value Term2 in shift/1 is unified with Term1 in reset/3. Finally, the execution restarts from the code just after the call to reset/3. Example 2. We report here the example shown in [10]. Consider the following program: p :-reset(q,Cont,Term1), writeln(Term1), writeln(Cont), writeln('end'). q :-writeln('before shift'), shift('return value'), writeln('after shift').

shift/1 instantiates Cont with the writeln('after shift') goal and Term1 with the term 'return value' in reset/3. The output of this program is:

?-p. before shift return value [$cont$(785488,[])] end

As one can see, when entering in q the execution is interrupted by the call to shift/1. The continuation in this case is not called, therefore what follows the call to shift/1 is not executed. 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 first predicate is suspended, capturing the reminder in Cont. At this point the so-called completion phase starts, collecting all the possible continuation, to find 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 unified 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 find 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 find 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 find 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 differences 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 different 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.

Mode-Directed Tabling and Answer Subsumption

As seen in the previous section, plain tabling creates an answer table per call variant and guarantees termination if the created data structures are finite. 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 infinite 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 [24,26]. In mode-directed tabling, a subset of the predicate arguments defines the call variant while answers for the remaining arguments are aggregated. A classical aggregation is, following the example above, computing the minimum or shortest path. As the minimum can be considered to subsume higher values this technique is also called Answer Subsumption.

To facilitate PITA, we extended SWI-Prolog's original tabling implementation with mode-directed tabling. The specification was inherited from XSB, B-Prolog and YAP and includes the most generic aggregation function called lattice that allows a user defined predicate to determine the subsumer for the aggregated answer so far and a new answer. The implementation is straight forward. The modified 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 [26] that showed that many implementations of mode-directed tabling produce unsound results. The authors of [26] thus define a formal semantics for mode-directed tabling that allows the evaluation of the soundness of implementations. For the program above, the semantics returns A = (1-2).

In the semantics, aggregation is a post-processing step. Real systems aggregate intermediate results during resolution for efficiency and to avoid loops. The authors of [26] discuss conditions for this greedy strategy to be sound with respect to the theoretical semantics.

In order to make SWI-Prolog sound, we modified 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 [26], provided that within the subcomponent we do not encounter a variant of a tabled goal that was started before the subcomponent but has not yet been completed.

PITA

The PITA system [18,19,20] where Probs is a list of floats 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.

Example 5 (Example 1 Cont.). If we associate the random variables X 11 with (C 1 , {X/bob}, 1), X 12 with (C 1 , {X/bob}, 2), X 13 with (C 1 , {X/bob}, 3) X 21 with (C 2 , {X/bob}, 1), X 22 with (C 2 , {X/bob}, 2) and X 23 with (C 2 , {X/bob}, 3), the BDD corresponding with the set L T for query strong sneezing(bob) is shown in Figure 1. The probability of the query is computed by following the BDD and 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, defining as lattice the or/3 predicate. This combines every BDD, which corresponds to a different explanation for the call variant of the predicate, in order to compute a final 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 first collecting the BDD representing all the explanations for a by means of answer subsumption. The final BDD is then negated to find the BDD for b.

Conclusion

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 [12]. In addition, we plan to make a comparison with XSB in terms of performance.