Syntax

Initially an SLP clause was a Prolog clause with the addition of probability label. This label had to be a number between 0 and 1. For instance the program:

1/2 :: nat( 0 ).
1/2 :: nat( s(X) ) :-
         nat( X ).

fits a geometric distribution over the natural numbers. Posing the query $?- nat( Y ).$ 10,000 times will instantiate variable $Y$ to each number with probability similar to that shown in Fig. 19. In the plot, the y-axis plots probability for each instantiation while the x-axis plots the $ith$ instantiation term starting from $i=1, Y = 0$.

Figure 19: Geometric distribution over naturals.

The restriction to probabilistic labels that are known numbers has been proven too strong in practice. In MCMCMS we allow for functions involving a number or variables and which are evaluated at call-time. For example the following program defines a uniform distribution over element selections from a list.

:- pvars( umember(L,_E,_R), [T-length(L,T)] ). 

1/L       : [L] : umember( El, [El|T] ).
1 - (1/L) : [L] : umember( El, [_|T] ) :-
                [L-1] : umember( El, T ).

The pvars/2 directive is optional. When it is present, $umember(X,[a,b,c])$ is a valid query, whereas the query $[3] :: umember(X,[a,b,c])$ can be used both when the directive is present and when it is absent.

Returning to the definition of the predicate, note that the base case is selected with probability $1/L$ and the recursive case with probability $1 - 1/L$. When $L$ is the length of the list in the second argument, this predicate will select an element from the list with uniform distribution. An example of this happening is shown in Fig. 20. The probability with which each element is selected, is equal to the product of the edges in the path from the root to its leaf. In the case of $Y=b$, $p(Y=b) = 2/3 * 1/2 = 1/3$. Similarly for the other cases.

Figure 20: Selecting with uniform distribution.

For the purposes of MCMC the query $umember(X,[a,b,c])$ creates a maximum of $3$ choice points. For example when $X=b$ the path is $[2-2/3,1-1/2]$, where $1$ and $2$ are internal clause indices assigned order to the clauses of umember/2 from top to bottom in the order they appear in the source file. The number of, probablitistic, choice points is a crucial dimension in the selection of a bactrack point as described in Section 5.1, also see [Angelopoulos CussensAngelopoulos Cussens2004].

It is possible to reduce the number of choice points $umember(X,[a,b,c])$ creates by using the declaration

$$:- s\_tail\_recursive( umember/2 ).$$

When this is present, the above query will always create a single choice point: $1-1/3$ in the case of $X = a$ and $2-2/3$ otherwise. The base case clause of the predicate should appear at the top, followed by the recursive clause(s). Note that the declaration is only effective when the body of a recursive clause does not leave any probabilistic choice-points.

The directive, forces the probabilistic backtrack points of predicate with specification to be ingnored. Only and all the points created at calls to this predicate are ignored. Points left by the body of clauses of such a predicate to other predicates are valid backtracking choices.