Getting an order into predicate resolution

Question

Look at the following goals (I am using swi-prolog with clpfd from Markus Triska):

result(Input,Result) :-
    Input #> 10,
    Result=decline.
result(Input,Result) :-
    Input in 0..20,
    Result=offer.

A possible query looks like this:

?- result(15,B).
B = decline ;
B = offer.

I want to add an order or some sort of solution priority. If "decline" is a valid response for Input=15, then the second goal should not be considered anymore, so that only B=decline is a solution but not B=offer.

I know that I could add a !/0 but then the other way round would not work. Give me all possible answers for this predicate.

Considering this example, a Result=offer should only be true for Input 0..10, because otherwise the higher prior decline goal should fire.

Am I thinking too imperative when I try to consider an order within predicates?

Finned

I also know that I could of course change the constraints for the Input variable but this should not be the solution. – Finned

There is an order within clauses of a predicate. I think changing the constraints for the Input variable is the solution here. – Xavier

Yes, you are thinking quite procedurally, but that's a problem in and of itself. Why are you using CLP/FD? The way you set it up, it doesn't look like a constrain-and-generate program, just an ordinary generate-and-test one. – Glyptodont

Also, your requirements seem contradictory: "If "decline" is a valid response for Input=15, then the second goal should not be considered anymore" means that "all possible answers" should be just [decline], right? – Glyptodont

Well, not quite, it should be as follows: Result=decline if Input in 11..sup and Result=offer if Input in 0..10 – Finned

Answer 1

There are several issues here, let's start first with the most obvious:

Modeling problems

You have a relation (result/2 is maybe not the best name), and this relation is supposed to model when decline and when offer should be true. Before reading your program, I prefer to ask Prolog:

?- result(X, decline), result(X, offer).
   X in 11..20
;  false.

So for the values from 11 up to 20, your relation is ambiguous. If you want to make a decision, then fix this relation first. Actually, I would start with

• a better name for the relation that makes clear it is a relation
• no imperative verbiage (like Input or imperatives)
• a more compact formulation, you don't need so many (=)/2 goals in your program. Instead, you can write it like:

heigth_decision(I, decline) :-
   I #< 10.

Answers and success vs. solutions in CLP

And then there is another problem which is more fundamental. This is actually much more serious, since all the SO-answers given so far ignore this aspect entirely. It is about the notion of answers and success and on the other hand the notion of solutions.

When you ask a query in Prolog - what you get back is an answer. Such an answer might contain solutions, like the answer L = [_,_] which contains infinitely many solutions. Or an answer may contain exactly one solution like Decision = decline. But there is much more in between if you are using constraints like library(clpfd).

You can now get finitely many solutions:

?- abs(X) #< 3.
   X in -2..2.

Or infinitely many:

?- X #> Y.
   Y#=<X+ -1.

But you can get also exactly one solution, which does not look like one:

?- 2^X #= 1.
   2^X#=1.

So, just to restate this: We have here exactly one solution in the integers, but for Prolog this is way too complex. What we got back was an answer that states: Yes that is all true, provided _{all this fine print is true}.

Worse, sometimes we get answers back that do not contain any solution.

?- X^X#=0.
   X^X#=0.

If Prolog would be smart enough, it would answer false. But it cannot be always that smart, simply because you can easily formulate undecidable problems. Such an answer is sometimes called inconsistency. The German notion Scheinlösung (~fake solution, but with less negative connotation) conveys the idea a bit better.

So an answer may contain solutions, but some answers do not contain solutions at all. For this reason, the success of a goal cannot be taken as the existence of a solution! That is, all SO-answers suggesting some kind of commit as (;)/2 – if-then-else, once/1, or !/0 are all incorrect, if they take the success as a solution. To see this, try them with:

?- X^X#=0, result(X,decline).
   X in 11..sup, X^X#=0
;  false.
?- X^X#=0, result(X,offer).
   X in 0..20, X^X#=0.

So how can you now be sure of anything?

• You can rely on the failure of a goal.

• You can try labeling/2, but this only works on finite domains.

• You can use call_residue_vars/2 and copy_term/3 to determine if there are constraints "hanging around"

• Unfortunately, you cannot entirely rely on SWI's toplevel which hides constraints that are unrelated to the variables in an answer. Only SICStus does display them correctly.

Guanajuato

Wow, again thank you for providing me with so much background information. I really appreciate it and you have totally understood my problem here. Success is indeed not always a solution here. – Finned

Answer 2

The part that puzzles me is when you say "the other way round would not work". Why do you want to go the other way round?

This is a clear case of deterministic search and the way to do it in Prolog is with a cut. If the first rule is satisfied don't keep the other branches open. Alternatively you can make the ranges you check mutually exclusive.

If you are not just messing around and you are trying to implement something serious I recommend a read on rules with priority and teleo-reactive rules. You should be able to find frameworks built on top of Prolog that can be used to solve your problem without reinventing the wheel.

Discomfiture

Well, I think that I will need a predicate that takes an input and gives the correct answer. That's where the cut comes in and it works for that way. But what I would like to have is to be able to query: ?-result(Input,Ouput) and it should return to me the following: Result=decline, Input in 11..sup and Result=offer,Input in 0..10 – Finned

Ok, this is how I would do it. I would redefine your problem. You want to assign a result based on the most retstrictive condition. So first define an order, for example decline >> offer. Then use finite constraints on result as well, say that Result is a variable with domain {decline,offer}. Process result through the constraints and get in the end the most restrictive. – Discomfiture

What I do now is to make the following: Input #> 10, decline; #\ Input #>10, Input in 0..20, Result=offer. It then gives me the expected result: decline in 11..sup, offer in 0..10. What I was hoping was that there is a more elegant way to do this than to negate every condition in every goal. – Finned

Your advice on using cuts is incorrect. Whether or not the first rule succeeds (how do you ensure it is "satisfied"?) has not necessarily anything to with what is described at all. – Guanajuato

@Guanajuato you are right. My immediate response was based on the sample query provided result(15,B). In that case the constraints are rendered useless. In the more general case a cut there is bad. – Discomfiture

Even in the case result(15,B) your conclusion could be wrong. You would need to inspect the source or inspect the affected variables. Imagine that the rule has a goal X^X#=0 with X a fresh variable. – Guanajuato

I'm sure you can find many cases where that solution doesn't work. But it's fine for those two rules and that type of queries. – Discomfiture

Answer 3

Predicate order it's an essential part of Prolog programs. That's because the proof search proceeds in a strictly defined order, applying SLD resolution.

Your predicate gives reasonable results:

?- result(X,Y).
Y = decline,
X in 11..sup ;
Y = offer,
X in 0..20.

Instead of a cut in result/2, you could use once/1 when calling it, retaining the proper definition for general use.

?- once(result(X,Y)).
Y = decline,
X in 11..sup.

Harmonious

But ?- once(result(X, offer)) gives you a different answer. Your code can only be understood procedurally. – Guanajuato

Answer 4

Some ideas from constructive negation could help here.

Theory

There is a simple way to a have a logical cut. Especially for constraints, since constraints are usually negation complete. So if you have a constraint C you can usally find a constraint C' with the following property:

C' <=> ~C

To impose a preference among two clauses that read as follows:

p :- C, q.
p :- r

Just do the following:

p :- C, q.
p :- C', r.

If your constraint solver provides a reified negation, such as (#\)/1 you could even defined an operator for that:

:- op(1050,xfy,#?).
:- op(1100,xfy,#:).
(A #? B #: C) :- (A, B); (#\ A, C).

And then write the following:

p :- C #? q #: r.

Lets apply this strategy to your example:

Example

Your code currently reads as follows:

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input in 0..20,
    Result = offer.

Then do the following:

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input #=< 10, Input in 0..20,
    Result = offer.

Here is an example run:

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

And now using (#?)/2 which is for example possible in SWI-Prolog, since the CLP(FD) library there supports reification. Assuming we have consulted the CLP(FD) library and then defined (#:)/2 as above:

 result(Input, Result) :-
    Input #> 10 
    #? 
       Result = decline 
    #: 
       Input in 0..20,
       Result = offer.

Here is an example run:

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

Disclaimer

The later syntax of (#?)/2 and (#:)/2 is inspired by the Java if-then-else operators (?)/2 and (:)/2. A more Prolog inspired syntax is not possible, since we cannot override or extend the definition (;)/2.

For more information on reification see for example here section A.8.4 Reification. What we didn't do was reifying the conjunction and disjunction in our definition of a CLP(FD) if-then-else, since then then and else part might contain other goals then CLP(FD) constraints.

Bye

Cleavable