Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Dealing with variables in bagof/3 #614

Closed
Jean-Luc-Picard-2021 opened this issue Oct 30, 2024 · 25 comments
Closed

Dealing with variables in bagof/3 #614

Jean-Luc-Picard-2021 opened this issue Oct 30, 2024 · 25 comments

Comments

@Jean-Luc-Picard-2021
Copy link

I stepped over this test case:

q(A, _, A).
q(_, A, A).
q(A, _, A).

I got a discrepancy between SWI-Prolog and Trealla Prolog:

/* SWI-Prolog 9.3.13 */
?- bagof(none, q(X,Y,Z), L).
X = Z,
L = [none, none] ;
Y = Z,
L = [none].

/* Trealla Prolog 2.58.8-20 */
?- bagof(none, q(X,Y,Z), L).
   Z = X, L = [none]
;  Z = Y, L = [none]
;  Z = X, L = [none].

I am afraid that SWI-Prolog would be the ISO behaviour.

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented Oct 30, 2024

I suspect that SWI-Prolog is the ISO behaviour, since
I get the same behaviour with a pure Prolog implementation:

/* Dogelog Player 1.2.4 */
?- ensure_loaded(library(aggregate)).
true.

?- bagof(none, q(X,Y,Z), L).
X = Z, L = [none, none];
Y = Z, L = [none].

Which is derived from some folklore implementation of bagof/3,
via keysort/2. It uses ISO term_variables/3 to align variables.

Source code:

bags.p.log

@infradig
Copy link
Contributor

infradig commented Oct 30, 2024

Just sayin':

~/trealla (devel) $ cat x.pl
q(A, _, A).
q(_, A, A).
q(A, _, A).

/trealla (devel) $ tpl x.pl
?- bagof(none, q(X,Y,Z), L).
   Z = X, L = [none]
;  Z = Y, L = [none]
;  Z = X, L = [none].
 
~/trealla (devel) $ scryer-prolog
?- 
~/trealla (devel) $ scryer-prolog x.pl
?- bagof(none, q(X,Y,Z), L).
   X = Z, L = [none]
;  Y = Z, L = [none]
;  X = Z, L = [none]. 

@infradig
Copy link
Contributor

infradig commented Oct 30, 2024

Eclipse agrees with SWI, as does Ciao.

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented Oct 30, 2024

Did you try GNU Prolog? It gives me the same as SWI-Prolog:

/* GNU Prolog 1.5.0  */
?- bagof(none, q(X,Y,Z), L).

L = [none,none]
Z = X ? ;

L = [none]
Z = Y

I have two issues related to variable handling in Scryer Prolog:

Dealing with variables in bagof/3
aarroyoc/scryer-playground#39

Dealing with variables in library(tabling)
aarroyoc/scryer-playground#37

The Problem also shows in tabling.

@infradig
Copy link
Contributor

~/trealla (devel) $ cxprolog
main ?- [x].
% File 'x.pl' consulted, 9.2e-05 sec 2112 bytes
yes
main ?- bagof(none, q(X,Y,Z), L).
X = _G17 
Y = _G17 
Z = _G17 
L = [none,none,none] 
main ?- 
% CxProlog halted.

~/trealla (devel) $ bp
B-Prolog Version 8.1, All rights reserved, (C) Afany Software 1994-2014.
| ?- [x].
consulting::x.pl
yes
| ?- bagof(none, q(X,Y,Z), L).
X = Z
Y = Z
L = [none,none,none]
yes
| ?- 
~/trealla (devel) $ 

@infradig
Copy link
Contributor

~/trealla (devel) $ yap
YAP 7.5.0-4530233e (compiled  2024-05-28T12:37:36@andrew-E6430)
database loaded from /usr/local/lib/startup.yss

?- [x].
   % loading x...
   % /home/andrew/trealla/x.pl consulted in module user, 1 msec 0 bytes
yes
?- bagof(none, q(X,Y,Z), L).
X=X,
L=[none] ;
Y=Y,
L=[none] ;
X=X,
L=[none]
?- 

@Jean-Luc-Picard-2021
Copy link
Author

You probably find a ISO test case, one of the examples
from the ISO core standard document, which would be

informative what is the desired behaviour. The test case
I am using, I didn't pick it from the ISO core document.

@infradig
Copy link
Contributor

~/trealla (devel) $ xsb
[xsb_configuration loaded, cpu time used: 0.001 seconds]
[sysinitrc loaded]
[xsbbrat loaded]

XSB Version 5.0.0 (Green Tea) of May 15, 2022
[x86_64-pc-linux-gnu 64 bits; mode: optimal; engine: slg-wam; scheduling: local]
[Build date: 2024-03-01]

| ?- [x].
[x loaded]

yes
| ?- bagof(none, q(X,Y,Z), L).

X = _h417
Y = _h459
Z = _h417
L = [none];

X = _h417
Y = _h459
Z = _h459
L = [none];

X = _h417
Y = _h459
Z = _h417
L = [none];

no
| ?- 
End XSB (cputime 0.03 secs, elapsetime 10.78 secs)

@infradig
Copy link
Contributor

I don't have Sicstus or other.... maybe @pmoura

@infradig
Copy link
Contributor

For what it's worth, the Trealla bagof/3 is basically the old O'Keefe code.

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented Oct 30, 2024

Then your builtins.p has maybe a bug somewhere,
or there are different versions of O'Keefes code?
Doesn't for example SICStus Prolog use O'Keefes code?

/* SICStus Prolog 4.9.0 */
bagof(none, q(X,Y,Z), L).
Z = X,
L = [none,none] ? ;
Z = Y,
L = [none] ? ;
no

SICStus Prolog uses maybe some 1980's Quintus O'Keefes code?
Well I don't know exactly. I only inspected their aggregate/3
and aggregate_all/3 recently. But SICStus would be authorative

what the Quintus branch of Prolog systems does?

@infradig
Copy link
Contributor

Using your bags.pl:

~/trealla (devel) $ tpl bags.pl x.pl
?- xbagof(none, q(X,Y,Z), L).
   Z = X, L = [none,none]
;  Z = Y, L = [none].
?- 

I just changed term_variables/3 to term_variables/2 since the 3rd arg wasn't used & changed bagof/3 to xbagof/3.

If this is definitive I will try using this version as a replacement to the existing implementation and see how other tests go.

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented Oct 30, 2024

It needs term_variables/3 because different solutions, might have
different number of variables. Take this example:

p(_,_).
p(a,b).
p(_,_).

It should still give:

/* SWI-Prolog 9.3.13 */
?- bagof(none, p(X,Y), L).
L = [none, none] ;
X = a,
Y = b,
L = [none].

Its currently correct in Trealla Prolog.

@infradig
Copy link
Contributor

ok, well Trealla doesn't have term_variables/3

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented Oct 30, 2024

Yeah, same here. I first had also only term_variables/2.
I even don't remember where I saw the solution with
term_variables/3 ? Maybe in SWI-Prolog itself?

Yes, its from here:

%!  bind_bagof_keys(+VarsTemplPairs, -SharedVars)
%
%   Establish a canonical binding  of   the  _vars_ structures. This
%   code   was   added    by    Ulrich     Neumerkel    in    commit
%   1bf9e87900b3bbd61308e80a784224c856854745.

bind_bagof_keys([], _).
bind_bagof_keys([W-_|WTs], Vars) :-
    term_variables(W, Vars, _),
    bind_bagof_keys(WTs, Vars).

https://github.com/SWI-Prolog/swipl-devel/blob/master/boot/bags.pl

@infradig
Copy link
Contributor

Ok, going on this defn:

term_variables(P1, P2, P3) :-
	term_variables(P1, P4),
	append(P4, P3, P2).

I get:

~/trealla (devel) $ tpl x2.pl
?- bagof(none, p(X,Y), L).
   L = [none,none]
;  X = a, Y = b, L = [none].
?- 

@infradig
Copy link
Contributor

Just testing with Logtalk now.

infradig added a commit that referenced this issue Oct 30, 2024
@infradig
Copy link
Contributor

Fixed now. You should file an issue with Scryer Prolog as well.

@pmoura
Copy link

pmoura commented Oct 30, 2024

I don't have Sicstus or other.... maybe @pmoura

$ sicstus
SICStus 4.9.0 (x86_64-darwin-21.6.0): Fri Dec 15 11:09:06 CET 2023
Licensed to Paulo Moura
% consulting /Users/pmoura/.sicstusrc...
% consulted /Users/pmoura/.sicstusrc in module user, 4 msec 50272 bytes
| ?- [user].
% compiling user...
| q(A, _, A).
| q(_, A, A).
| q(A, _, A).
| 
% compiled user in module user, 43 msec 517872 bytes
yes
| ?- bagof(none, q(X,Y,Z), L).
Z = X,
L = [none,none] ? ;
Z = Y,
L = [none] ? ;
no

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented Oct 30, 2024

SWI-Prolog has a special ordering behaviour, although
SICStus Prolog gives me the same answer:

/* SWI-Prolog 9.3.13 and SICStus Prolog 4.9.0 */
?- bagof(X, q(X,Y,Z), L).
Y = Z,
L = [_] ;
L = [Z, Z].

?- bagof(Y, q(X,Y,Z), L).
X = Z,
L = [_, _] ;
L = [Z].

Its sometimes difficult to reproduce these query results. It has to do
with a last minute change in SWI-Prolog which changed the implementation
of bagof/3 and added the extra predicate call alloc_bind_key_list/2:

?- '$free_variable_set'(X^q(X,Y,Z), H, W), findall(W-X, H, L), '$bags':bind_bagof_keys(L, _), keysort(L, R).
H = q(X, Y, Z),
W = v(Y, Z),
L = [v(_A, _B)-_B, v(_A, _A)-_C, v(_A, _B)-_B],
R = [v(_A, _B)-_B, v(_A, _B)-_B, v(_A, _A)-_C].

?- '$free_variable_set'(X^q(X,Y,Z), H, W), '$bags':alloc_bind_key_list(W, U), findall(W-X, H, L), '$bags':bind_bagof_keys(L, U), keysort(L, R).
H = q(X, Y, Z),
W = v(Y, Z),
U = [_A, _B|_],
L = [v(_A, _B)-_B, v(_A, _A)-_C, v(_A, _B)-_B],
R = [v(_A, _A)-_C, v(_A, _B)-_B, v(_A, _B)-_B].

Note the different R's. Is it possible to get the SWI-Prolog ordering
without alloc_bind_key_list/2 somehow? I don't know yet.

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented Oct 30, 2024

Looks quite bright now, the ticket can be closed now?
I was running a long variable instantiation chain test.

test2 :-
   between(1,1000,_), bagof(none, N^(between(1,1000,N), X=X), _), fail; true.

In SWI-Prolog the above did explode in the past, when alloc_bind_key_list/2
wasn't deployed. But it can be also fixed by a fortunate term_variables/3
unification of the second argument. Mostlikely Trealla Prolog has hit the right spot:

/* Trealla Prolog 2.59.1-22 */
?- time(test2).
% Time elapsed 2.076s, 12046004 Inferences, 5.802 MLips

If long variable instantiation chain happen, the above might need 8 seconds or
something. It can happen in this step:

% sys_same_vars(+Pairs, +List)
sys_same_vars([K-_|L], V) :-
   term_variables(K, V, _),
   sys_same_vars(L, V).
sys_same_vars([], _).

When the carried around V points to longer and longer instantiation chains.
It can be avoided if instantiations are only done from the term_variables/3
result to the carried around V, and not vice versa.

But mostlikely your are not bugged with this issue now. Here you see
what can go wrong, testing Scryer Prolog:

/* Scryer Prolog 0.9.4-201 */
?- time(test2).
   % CPU time: 12.610s, 25_103_021 inferences

@pmoura
Copy link

pmoura commented Oct 31, 2024

P.S. Added 6 new bagof/3 tests to Logtalk for checking correct variable handling by this predicate.

@infradig
Copy link
Contributor

P.S. Added 6 new bagof/3 tests to Logtalk for checking correct variable handling by this predicate.

Thanks.

@Jean-Luc-Picard-2021
Copy link
Author

It might be desireable to test setof/3 and aggregate/3
as well, and not only bagof/3. I made some test cases:

newtests.p.log

@Jean-Luc-Picard-2021
Copy link
Author

The bagof/3 choker:

test :-
   bagof(X, N^(between(1,300,X), between(1,300,N), 
      length(_,N)), _), fail; true.

I get:

/* Trealla Prolog 2.59.17 */
?- time(test).
% Time elapsed 13.280s, 16158649 Inferences, 1.217 MLips
   true

/* SWI-Prolog 9.3.14 */
?- time(test).
Action (h for help) ? abort
% 468,739 inferences, 52.016 CPU in 53.069 seconds (98% CPU, 9012 Lips)
% Execution Aborted

Goody, goody!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants