Previous Up

8.3  Approximate Generalised Propagation

The syntax Goal infers most can also be varied to invoke different levels of Generalised Propagation. Other alternatives are Goal infers ic, Goal infers unique, and Goal infers consistent. The strongest constraint is generated by Goal infers most, but it can be expensive to compute. The other alternatives may be evaluated more efficiently, and may yield a better overall performance on different applications. We call them “approximations”, since the information they produce during propagation is a (weaker) approximation of the information produced by the strongest constraint.

We illustrate the different approximations supported by the current version of Propia on a single small example. The results for Goal infers most reflect the problem that structured terms cannot appear in IC integer domains.

 
p(1,a).
p(2,f(Z)).
p(3,3).
?- p(X, Y) infers most.
X = X{1 .. 3}
Y = Y
There is 1 delayed goal.
Yes (0.00s cpu)

?- X :: 1 .. 3, p(X, Y) infers most.
X = X{1 .. 3}
Y = Y
There is 1 delayed goal.
Yes (0.00s cpu)

?- p(2, Y) infers most.
Y = f(_326)
There is 1 delayed goal.
Yes (0.00s cpu)

The first approximation we will introduce in this section is one that searches for the unique answer to the query. It is written Goal infers unique. This is cheap because as soon as two different answers to the query have been found, the constraint evaluation terminates and the constraint is delayed again until new information becomes available. Here are two examples of this approximation. In the first example notice that no domain is produced for X.

?- p(X, Y) infers unique.
X = X
Y = Y
There is 1 delayed goal.
Yes (0.00s cpu)

In the second example, by contrast, infers unique yields the same result as infers most:

 
?- p(X,X) infers unique.
X = 3
Yes (0.00s cpu)

The next example shows that unique can even capture nonground answers:

?- p(2, X) infers unique.
X = f(Z)
Yes (0.00s cpu)

The next approximation we shall describe is even weaker: it tests if there is an answer and if not it fails. If there is an answer it checks to see if the constraint is already true.

?- p(1, X) infers consistent.
X = X
There is 1 delayed goal.
Yes (0.00s cpu)

?- p(1, a) infers consistent.
Yes (0.00s cpu)

?- p(1, X) infers consistent, X = b.
No (0.00s cpu)

The strongest language infers most extracts any information possible from the loaded constraint solvers. The solvers currently handled by Propia are unification (which is the built-in solver of Prolog), ic and ic_symbolic. The IC library is loaded by lib(ic) and the symbolic library by lib(ic_symbolic). These libraries are described elsewhere. If both libraries are loaded, then infers most extracts information from unification, IC domains and symbolic domains. For example:

 
 p(f(X),1) :- X *>=0, X *=< 10.
 p(f(X),1) :- X=12.

with the above program

 
?- p(X, Y) infers most.
X = f(_338{0.0 .. 12.0})
Y = Y{[1, 2]}
There is 1 delayed goal.
Yes (0.00s cpu)

The approximation infers ic is similar to infers most. However, while infers most extracts information based on whatever constraint solvers are loaded, the others only infers information derived from the specified constraint solver. Here’s the same example using infers ic:

 
?- p(X, Y) infers ic.
X = f(_353{0.0 .. 12.0})
Y = Y{[1, 2]}
There is 1 delayed goal.
Yes (0.00s cpu)

One rather special approximation langue is infers ac, where ac stands for arc-consistency. This has similar semantics to infers ic, but is implemented very efficiently using the built-in element constraint of the IC solver. The limitation is that Goal infers ac is implemented by executing the goal repeatedly to find all the solutions, and then manipulating the complete set of solutions. It will only work in case there are finitely many solutions and they are all ground.

Finally it is possible to invoke Propia in such a way as to influence its waking conditions. To do this, use the standard suspend syntax. For example “forward checking” can be implemented as follows:

propagate(Goal,fc) :- !,
    suspend(Goal,7,Goal->inst) infers most.

In this case the Propia constraint wakes up each time a variable in the goal is instantiated.

The default priority for Propia constraints is 3. However, in the above example, the priority of the Propia constraint has been set to 7.


Previous Up