bagof/3 is unpredictable

Question

I am baffled by the following results. I am using SWI-Prolog.

?- bagof(Q, (Q=A, (A=[a,_] ; A=[_,b])), X).
A = [_G16898, b],
X = [[_G16898, b]] ;
A = [a, _G16892],
X = [[a, _G16892]].

Notice that [a,_] and [_,b] are not unified to produce an answer A = [a,b], X=[[a,b],[a,b]].

Now, lets try the same with arithmetic constraints:

?- bagof(Q, (Q=A, (A in 1..5 ; A in 3..8)), X).
X = [A, A],
A in 3..5.

Strangely, this time the arithmetic constraints are taken together but there are no answers A in 1..5, X=[A] and A in 3..8, X=[A].

Now lets try this in yet another way:

?- bagof(Q, (Q=A, ((1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8))), X).
X = [A],
A in 3..5 ;
X = [A],
A in 3..5.

The arithmetic constraints are combined like before, but we have two answers instead of one.

How can all this be explained?

EDIT: Some more strange results. Compare this:

?- A=[_,_], bagof(Q, K1^K2^(Q=A, (A=[a,K1] ; A=[K2,b])), X).
A = [_G16886, b],
X = [[_G16886, b]] ;
A = [a, _G16889],
X = [[a, _G16889]].

with this:

?- A=[a,b], bagof(Q, K1^K2^(Q=A, (A=[a,K1] ; A=[K2,b])), X).
A = [a, b],
X = [[a, b], [a, b]].

I think you meant this semicolon to be a comma: `(A=[a,_] , A=[_,b])`. With the semicolon you are saying A is a two-item list that either starts with a or ends with b, not both. I don't know why/how clpfd is able to combine these constraints. — Daniel Lyons, Mar 01 '19 at 17:03
No, I mean semicolon. I know, it looks strange... This code isn't from a real program. I am just trying to understand how this predicate is supposed to work. — A. Zinoviev, Mar 01 '19 at 17:11
Your first result makes sense. So does your last one comparing the `A=[_,_]` constraint behavior with `A=[a,b]`. What would you expect in those cases? In your last one, you constrained, `A=[a,b]`, so the results are necessarily, `A=[a,b]` and `A = [[a,b], [a,b]]` (there were only two distinct alternatives for the `bagof`). The CLP(FD) examples are interesting and the only ones that surprise me at first glance, and I'd need to think about it. At least the behavior of `in/2` and `#=2` with `#>=/2` are consistent with each other. — lurker, Mar 01 '19 at 17:33
I played with the CLP(FD) case in both SWI Prolog and Gnu Prolog and got different results. In SWI, I get the result you show. In Gnu Prolog, the result depends upon the order of arguments in `;/2`! So if I query, `bagof(A, (Q=A, ((1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8))), X).` I will get `X = [_#2098023(1..5),_#2098023(1..5)]`. If I query, `bagof(A, (Q=A, ((1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8))), X).` I get, `X = [_#2098023(3..8),_#2098023(3..8)]`! Something tells me that CLP(FD) and `bagof/3` don't mix well here. — lurker, Mar 01 '19 at 17:44
@lurker. With SICStus yet different results... Both `?- bagof(Q, (Q=A, (A in 1..5 ; A in 3..8)), X).` and `?- bagof(Q, (Q=A, ((1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8))), X).` give the answer `X = [A,A] ? ; no`. — repeat, Mar 01 '19 at 17:56
@GuyCoder not sure that will help with the `bagof/3` internal behavior. — lurker, Mar 01 '19 at 18:17
It seems the implementation of `bagof/3` in SWI-prolog ignores the changes of the attributes of the variables. With `?- bagof(Q, (Q=1 ; Q=2, dif(A,a)), X).` the result will be `X=[1,2],dif(A,a).` Also `?- bagof(Q, (Q=1 ; Q=2, A in 1..2), X).` gives `X=[1,2],A in 1..2`, however `?- bagof(Q, (Q=1 ; Q=2, A in 1..1), X).` produces two answers `X=[1]` and `X=[2]`. — A. Zinoviev, Mar 01 '19 at 19:15
Your `bagof` using `dif` result makes perfect sense to me. What about it doesn't make sense to you? As @false mentioned, mixing the CLP(FD) constraints is evidently not a good idea. It seems to me that, of all your examples, only the CLP(FD) cases produce rather... um... interesting results. — lurker, Mar 01 '19 at 21:41
@lurker My `bagof` using `dif` shows that mixing bagof with any attributed variables (and in particular any constraints, not just CLP(FD)) doesn't work properly. For example `?- bagof(Q, (Q=1,dif(A,1) ; Q=2,dif(A,0)),X).` combines the two constraints (just as it does with clpfd) and it shouldn't. — A. Zinoviev, Mar 02 '19 at 14:32
Maybe the question should be, `What is the equivalent of bagof for constraints?` While too much for a SO question, a better question would be `When does Prolog and Constraints play well together and when do the not?` — Guy Coder, Mar 02 '19 at 14:34
@A.Zinoviev Yes, I see what you mean. The result for `X` is correct, though, in that case. In that kind of query, I'd perhaps more likely write, `bagof(Q, A^(Q=1,dif(A,1) ; Q=2,dif(A,0)),X).` which simply yields, `X = [1,2]`. It would be interesting to find an example in which the 'side-effect' constraint caused an incorrect result list for the `bagof/3`. I tried, `bagof(Q, (member(Q, [1,2,3,4]), dif(Q,1) ; member(Q, [1,2,3,4]), dif(Q,4)), X).` and it gave me `X = [2, 3, 4, 1, 2, 3]` which tells me `bagof/3` did not actually combine the `dif` constraints. — lurker, Mar 02 '19 at 14:41

score 0 · Answer 1 · 2019-08-19T18:37:07.377

Thats an artefact of SWI-Prolog, which also does copy attributed variables while taking findall/3 copies. findall/3 copies are used inside bagof/3 before doing keysort/2. But the effect can already be explained by means of findall/3:

SWI-Prolog, findall/3 copies attributed variables conditions:

?- findall(A, A in 1..5, L).
L = [_3464],
_3464 in 1..5.

?- findall(A, (A in 1..5, (true; true)), L).
L = [_3762, _3768],
_3762 in 1..5,
_3768 in 1..5

Jekejeke Prolog, findall/3 does not copy attributed variables conditions:

?- findall(A, A in 1..5, L).
L = [_A]

?- findall(A, (A in 1..5, (true; true)), L).
L = [_A, _B]

Inside bagof/3, there is not only a keysort/2 step, but also step where variables are restored. In this step for SWI-Prolog, constraints might be joined, since constraints will be present.

This explains the first result in the question of the OP. The second result in the question of the OP can be explained in that SWI-Prolog does goal expansion and introduce new variables in the case of (#=<)/2. You can check yourself:

?- [user].
test(A) :- A in 1..5 ; A in 3..8.
test(A) :- (1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8).

?- listing(test/1).
test(A) :-
    (   (   integer(A)
        ->  between(1, 5, A)
        ;   clpfd:clpfd_in(A, 1..5)
        )
    ;   integer(A)
    ->  between(3, 8, A)
    ;   clpfd:clpfd_in(A, 3..8)
    ).
test(A) :-
    (   (   integer(A)
        ->  A>=1
        ;   B=1,
            clpfd:clpfd_geq(A, B)
        ),
        (   integer(A)
        ->  5>=A
        ;   C=5,
            clpfd:clpfd_geq(C, A)
        )
    ;   (   integer(A)
        ->  A>=3
        ;   D=3,
            clpfd:clpfd_geq(A, D)
        ),
        (   integer(A)
        ->  8>=A
        ;   E=8,
            clpfd:clpfd_geq(E, A)
        )
    ).

There are no fresh variables in the expansion of (in)/2. But I guess the fresh variables inside the (#=<)/2 expansion, then causes bagof/3 to see two solutions, instead of only one.

Edit 19.08.2019:
Now I wonder how tabling with CLP(FD) solves the problem...

bagof/3 is unpredictable

1 Answers1