Why doesn't this clpfd query terminate until I add a redundant constraint?

Question

I've written some predicates which take the length of a list and attaches some constraints to it (is this the right vocabulary to be using?):

clp_length([], 0).
clp_length([_Head|Rest], Length) :-
  Length #>= 0, Length #= Length1 + 1,
  clp_length(Rest, Length1).

clp_length2([], 0).
clp_length2([_Head|Rest], Length) :-
  Length #= Length1 + 1,
  clp_length2(Rest, Length1).

The first terminates on this simple query, but the second doesn't:

?- Small in 1..2, clp_length(Little, Small).
Small = 1,
Little = [_1348] ;
Small = 2,
Little = [_1348, _2174] ;
false.

?- Small in 1..2, clp_length2(Little, Small).
Small = 1,
Little = [_1346] ;
Small = 2,
Little = [_1346, _2046] ;
% OOPS %

This is strange to me, because Length is pretty clearly greater than 0. To figure that out you could either search, find the zero, and deduce that adding from zero can only increase the number, or you could propagate the in 1..2 constraint down. It feels like the extra clause is redundant! That it isn't means my mental model of clpfd is pretty wrong.

So I think I have two questions (would appreciate answers to the second as comments)

Specifically, why does this additional constraint cause the query to work correctly?
Generally, is there a resource I can use to learn about how clpfd is implemented, instead of just seeing some examples of how it can be used? I'd prefer not to have to read Markus Triska's thesis but that's the only source I can find. Is that my only option if I want to be able to answer questions like this one?

Related: this answer stackoverflow.com/a/32501766/2353967 discusses a length-constraint and contains a link to an implementation — jschimpf
I don't understand your suggestion, if I use Small = 1 it also fails to terminate. list_lengthfd(List, 1) doesn't terminate after producing the first result. The same redundant clauses fixes this though, so I still have the same question! — num1

false false · Accepted Answer · 2018-06-23T20:06:11

1mo, there is the issue with naming. Please refer to previous answers by mat and me recommending relational names. You won't go far using inappropriate names. So list_length/2 or list_fdlength/2 would be an appropriate name. Thus we have list_fdlength/2 and list_fdlength2/2.

2do, consider the rule of list_fdlength2/2. Nothing suggests that 0 is of relevance to you. So that rule will be exactly the same if you are using 0 or 1 or -1 or whatever as base case. So how should this poor rule ever realize that 0 is the end to you? Better, consider a generalization:

list_fdlength2(fake(N), N) :-  % Extension to permit fake lists
   N #< 0.
list_fdlength2([], 0).
list_fdlength2([_Head|Rest], Length) :-
   Length #= Length1 + 1,
   list_fdlength2(Rest, Length1).

This generalization shows all real answers plus fake answers. Note that I have not changed the rule, I added this alternative fact only. Thus the fake solutions are actually caused by the rule:

?- list_fdlength2(L, 1).
      L = [_A]
   ;  L = [_A, _B|fake(-1)]
   ;  L = [_A, _B, _C|fake(-2)]
   ;  ...

?- list_fdlength2(L, 0).
      L = []
   ;  L = [_A|fake(-1)]
   ;  L = [_A, _B|fake(-2)]
   ;  ...

Each clause tries to contribute to the solutions just in the scope of the clause. But there is no way to derive (by the built-in Prolog execution mechanism) that some rules are no longer of relevance. You have to state that explicitly with redundant constraints as you did.

Now, back to your original solution containing the redundant constraint Length #>= 0. There should not be any such fake solution at all.

list_fdlength(fake(N), N) :-
   N #< 0.
list_fdlength([], 0).
list_fdlength([_Head|Rest], Length) :-
   Length #>= 0,
   Length #= Length1 + 1,
   list_fdlength(Rest, Length1).

?- list_fdlength(L, 1).
      L = [_A]
   ;  L = [_A, _B|fake(-1)]   % totally unexpected
   ;  false.

?- list_fdlength(L, 0).
      L = []
   ;  L = [_A|fake(-1)]       % eek
   ;  false.

There are fake answers, too! How ugly! At least, they are finite in number. But, you could have done it better by using Length #>= 1 in place of Length #>=0. With this little change, there are no longer any fake solutions when N is non-negative and thus also your original program will be better.

Why doesn't this clpfd query terminate until I add a redundant constraint?

1 Answers