Expressing numerical constraints using Prolog without CLP(FD)

user_2898138 0
Viewed 56
ordering(A, B, C) :-
    integer(A),
    integer(B),
    integer(C),
    A > B,
    B > C,
    A > 0,
    10 > C.

is satisfied by ordering(3,2,1).. But when I leave one or more as variables ordering(3,X,1). it evaluates to false.

What am I missing?

Update: thanks for all the extensive answers. I’ve learned something from all of them.

prolog
3 Answers

integer/1 fails if the argument is not an integer, for example if you pass an unbound variable. I believe you should use CLP(FD) for these kind of tasks. Otherwise you may manually bind/test variables in some integer range, using between/3 to set that range.

E.g.:

ordering(A, B, C) :-
   between(0, 100, A),  % A is an integer in the range [0,100]
   between(0, 100, B),  % same for B
   between(0, 100, C),  % and C
   A > B,
   B > C,
   A > 0,
   10 > C.

Sample run:

?- ordering(3,X,1).
X = 2 ;
false.
user_4632430

This is not surprising.

Evidently integer(X) with X unbound will immediately fail. It is very "imperative" in that regard.

Additionally, the predicate will fail with C unbound because of 10 > C.

At best you could write a predicate can_be/2 so that can_be(integer,X) succeeds when the unbound variable X "can still become an integer" and fails otherwise.

By extension there would be a can_be_ordered(A, B, C), which fails if it is sure that [A,B,C] can never be ordered due to the values they already denote, or succeeds if [A,B,C] can still be ordered depending on what values any unbound variables therein take on in the future.

It would be even better to reify the truth value:

ordering(List,Result)

where Result is

  • true: Yup, ordered and will stay ordered.
  • false: Definitely not ordered, and that won't change.
  • unknown/maybe: There is no clear evidence that it is unordered or ordered.

Then you can also attach ordering(List,Result) to the unbound variables that re-checks the ordering whenever one of the variables becomes bound, using freeze/2. That's basically doing the work of CLP(FD).

user_8844630

You could delay the comparison until the variables are initialized:

ordering(A, B, C) :-
    greater(A, B),
    greater(B, C).

greater(X, Y) :-
    when((nonvar(X), nonvar(Y)), X > Y).

Tests:

?- greater(3, 2).
true.

?- ordering(3, 2, 1).
true.

?- ordering(3, 2, 2).
false.

?- ordering(3, X, 1).
when(nonvar(X), 3>X),
when(nonvar(X), X>1).
user_19371970
Related