bagof/3 непредсказуем

Я озадачен следующими результатами. Я использую SWI-Пролог.

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

Обратите внимание, что [a,_] и [_,b] не объединены для получения ответа A = [a,b], X=[[a,b],[a,b]].

Теперь давайте попробуем то же самое с арифметическими ограничениями:

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

Странно, но на этот раз арифметические ограничения взяты вместе, а ответов A in 1..5, X=[A] и A in 3..8, X=[A] нет.

Теперь давайте попробуем это еще одним способом:

?- 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.

Арифметические ограничения объединены, как и раньше, но у нас есть два ответа вместо одного.

Как все это можно объяснить?

РЕДАКТИРОВАТЬ: еще несколько странных результатов. Сравните это:

?- 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]].

с этим:

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

prolog prolog-setof
person A. Zinoviev    schedule 01.03.2019    source источник
comment
Я думаю, вы имели в виду эту точку с запятой как запятую: (A=[a,_] , A=[_,b]). С помощью точки с запятой вы говорите, что A - это список из двух элементов, который либо начинается с a, либо заканчивается на b, а не на то и другое. Я не знаю, почему/как clpfd может сочетать эти ограничения.   -  person Daniel Lyons    schedule 01.03.2019
comment
Нет, я имею в виду точку с запятой. Я знаю, это выглядит странно... Этот код не из реальной программы. Я просто пытаюсь понять, как этот предикат должен работать.   -  person A. Zinoviev    schedule 01.03.2019
comment
Ваш первый результат имеет смысл. Как и ваш последний, сравнивающий поведение ограничения A=[_,_] с A=[a,b]. Чего ожидать в таких случаях? В вашем последнем вы ограничили A=[a,b], поэтому результаты обязательно будут A=[a,b] и A = [[a,b], [a,b]] (для bagof было только две разные альтернативы). Примеры CLP(FD) интересны и единственные, которые меня удивляют на первый взгляд, и мне нужно подумать над этим. По крайней мере, поведение in/2 и #=</2 с #>=/2 согласуется друг с другом.   -  person lurker    schedule 01.03.2019
comment
Я играл со случаем CLP(FD) как в SWI Prolog, так и в Gnu Prolog и получил разные результаты. В SWI я получаю результат, который вы показываете. В Gnu Prolog результат зависит от порядка аргументов в ;/2! Итак, если я сделаю запрос, bagof(A, (Q=A, ((1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8))), X). я получу X = [_#2098023(1..5),_#2098023(1..5)]. Если я запрошу, bagof(A, (Q=A, ((1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8))), X). я получу X = [_#2098023(3..8),_#2098023(3..8)]! Что-то мне подсказывает, что CLP(FD) и bagof/3 здесь плохо сочетаются.   -  person lurker    schedule 01.03.2019
comment
@скрытень. С SICStus еще разные результаты... И ?- bagof(Q, (Q=A, (A in 1..5 ; A in 3..8)), X)., и ?- bagof(Q, (Q=A, ((1 #=< A, A #=< 5) ; (3 #=< A, A #=< 8))), X). дают ответ X = [A,A] ? ; no.   -  person repeat    schedule 01.03.2019
comment
@GuyCoder не уверен, что это поможет с внутренним поведением bagof/3.   -  person lurker    schedule 01.03.2019
comment
@GuyCoder да, я понимаю. Это может дать некоторые подсказки.   -  person lurker    schedule 01.03.2019
comment
Кажется, что реализация bagof/3 в SWI-прологе игнорирует изменения атрибутов переменных. С ?- bagof(Q, (Q=1 ; Q=2, dif(A,a)), X). результат будет X=[1,2],dif(A,a). Также ?- bagof(Q, (Q=1 ; Q=2, A in 1..2), X). дает X=[1,2],A in 1..2, однако ?- bagof(Q, (Q=1 ; Q=2, A in 1..1), X). дает два ответа X=[1] и X=[2].   -  person A. Zinoviev    schedule 01.03.2019
comment
Ни в коем случае не смешивайте ограничения и bagof/setof/3.   -  person false    schedule 01.03.2019
comment
Ваш результат bagof с использованием dif имеет для меня смысл. А что тебе непонятно? Как уже упоминалось @false, смешивание ограничений CLP(FD), очевидно, не очень хорошая идея. Мне кажется, что из всех ваших примеров только случаи CLP(FD) дают довольно... гм... интересные результаты.   -  person lurker    schedule 02.03.2019
comment
@lurker Мое bagof с использованием dif показывает, что смешивание bagof с любыми переменными с атрибутами (и, в частности, с любыми ограничениями, а не только с CLP (FD)) не работает должным образом. Например, ?- bagof(Q, (Q=1,dif(A,1) ; Q=2,dif(A,0)),X). сочетает в себе два ограничения (так же, как и с clpfd), а этого не должно быть.   -  person A. Zinoviev    schedule 02.03.2019
comment
Может быть, вопрос должен быть таким: What is the equivalent of bagof for constraints? Хотя это слишком много для SO-вопроса, лучше было бы When does Prolog and Constraints play well together and when do the not?   -  person Guy Coder    schedule 02.03.2019
comment
@ А.Зиновьев Да, я понимаю, что вы имеете в виду. Однако в этом случае результат для X правильный. В таком запросе я бы скорее написал bagof(Q, A^(Q=1,dif(A,1) ; Q=2,dif(A,0)),X)., что просто дает X = [1,2]. Было бы интересно найти пример, в котором ограничение «побочный эффект» вызывало неправильный список результатов для bagof/3. Я попробовал bagof(Q, (member(Q, [1,2,3,4]), dif(Q,1) ; member(Q, [1,2,3,4]), dif(Q,4)), X)., и он дал мне X = [2, 3, 4, 1, 2, 3], что говорит мне о том, что bagof/3 на самом деле не сочетает ограничения dif.   -  person lurker    schedule 02.03.2019

Ответы (1)


arrow_upward
1
arrow_downward

Это артефакт SWI-Prolog, который также копирует переменные с атрибутами, делая копии findall/3. Копии findall/3 используются внутри bagof/3 перед выполнением keyort/2. Но эффект уже можно объяснить с помощью findall/3:

SWI-Prolog, findall/3 копирует условия атрибутированных переменных:

?- 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 не копирует условия переменных с атрибутами:

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

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

Внутри bagof/3 есть не только шаг keyort/2, но и шаг, на котором восстанавливаются переменные. На этом шаге для SWI-Prolog ограничения могут быть объединены, так как ограничения будут присутствовать.

Это объясняет первый результат в вопросе об ОП. Второй результат в вопросе ОП можно объяснить тем, что SWI-Prolog выполняет расширение цели и вводит новые переменные в случае (#=‹)/2. Вы можете проверить себя:

?- [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)
        )
    ).

В разложении (in)/2 нет свежих переменных. Но я предполагаю, что новые переменные внутри расширения (#=‹)/2 заставляют bagof/3 видеть два решения вместо одного.

Редактировать 19.08.2019:
Теперь мне интересно, как таблица с CLP(FD) решает проблему...

person Mostowski Collapse    schedule 19.08.2019