bagof/3 in 5.8.0

[Bart Demoen-2]

I am about to explain bagof/3 to a bunch of students, and while
preparing myself by constructing some examples, I came across this in
SWI Version 5.8.0

?- Given = [f(X,1),f(2,Z)], bagof(A,member(f(A,B),Given),Out).
Given = [f(X, 1), f(2, B)],
Z = B,
Out = [2] ;
Given = [f(X, 1), f(2, 1)],
Z = 1,
B = 1,
Out = [X].

That second answer binds Z. That's a bug, isn't it ?
It certainly is different from the answer in SICStus and Yap.

Cheers

Bart Demoen

ps. I usually avoid bagof/3 like the plague :-)

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

>I am about to explain bagof/3 to a bunch of students, and while
>preparing myself by constructing some examples, I came across this in
>SWI Version 5.8.0
>
>?- Given = [f(X,1),f(2,Z)], bagof(A,member(f(A,B),Given),Out).
>Given = [f(X, 1), f(2, B)],
>Z = B,
>Out = [2] ;
>Given = [f(X, 1), f(2, 1)],
>Z = 1,
>B = 1,
>Out = [X].
>
>That second answer binds Z. That's a bug, isn't it ?
>It certainly is different from the answer in SICStus and Yap.

First there is no difference between setof/3 and bagof/3 for solution
lists of length 1.

The predicates are nice as long as the solutions found are ground in
the "relevant" variables.  In your example you have no always variable
bindings - I never rely on that behavior, nor have I ever explained
that.  So given that, let me rewrite the example:

?- bagof(A,( f(A,B)=f(X,1) ; f(A,B) = f(2,Z) ),Out).

The variable A will be used to describe elements of Out (this is
called Template).  The other variables do not contribute to Out.  They
are part of the "Free variables set" or the witness set.  So now let
us find the solutions:

findall(wit(B,X,Z)+A, ( f(A,B)=f(X,1) ; f(A,B) = f(2,Z) ), Ws).

%  wit(B,           X,      Z)+A

   wit(1,      _G2381, _G2385)+_G2381,
   wit(_G2373, _G2374, _G2373)+2

From the point of view of wit we have two independent solutions
(binding B to 1 and not binding B at all - how irritating!).

Once B = 1 and Out = [X]
the other  B = Z and Out = [a].

So SWI is not right.  In any case, I would never rely on that kind of
behavior.  And just looking at it:

   setof(t,(A=B;B=C;C=A),_).

should yield three solutions since all three variables are in the
witness set.
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ceyhun Ciper]

Why do you avoid bagof/3 like the plague?

 

Just asking to be illuminated by a Professor of logical reasoning & coding like yourself; I really don't know where and/or when I should or shouldn't use it after your post-scriptum; I hope it won't go by the way of Fermat's last assertion on a margin in a post-analytical-and-intellectual age ;-).

 

Best Regards,

Ceyhun Ciper

On Tue, Nov 3, 2009 at 8:59 PM, Bart Demoen <bart.demoen@...> wrote:

I am about to explain bagof/3 to a bunch of students, and while
preparing myself by constructing some examples, I came across this in
SWI Version 5.8.0

?- Given = [f(X,1),f(2,Z)], bagof(A,member(f(A,B),Given),Out).
Given = [f(X, 1), f(2, B)],
Z = B,
Out = [2] ;
Given = [f(X, 1), f(2, 1)],
Z = 1,
B = 1,
Out = [X].

That second answer binds Z. That's a bug, isn't it ?
It certainly is different from the answer in SICStus and Yap.

Cheers

Bart Demoen

ps. I usually avoid bagof/3 like the plague :-)

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

The following tentative patch might solve this problem.
Nevertheless - these variables cause me some headache...

http://www.complang.tuwien.ac.at/ulrich/swi-prolog/git/0003-FIXED-setof-3-bagof-3-free-variables-generation.-Bar.patch

Probably Jan will find a better way
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Jan Wielemaker-3]

Hi Ulrich,

On Wednesday 04 November 2009 04:40:17 pm Ulrich Neumerkel wrote:
> The following tentative patch might solve this problem.
> Nevertheless - these variables cause me some headache...
>
> http://www.complang.tuwien.ac.at/ulrich/swi-prolog/git/0003-FIXED-setof-3-b
>agof-3-free-variables-generation.-Bar.patch
>
> Probably Jan will find a better way

Hmmm.  Your patch seems to tackle two issues: the variable binding and
possible differences that may result from using =@=/2.  Is that right?

Now, I'm trying to get my head around this, but this is a bit hard after
traveling and a short night :-(  So, I'll share my observations and hope
all gets clear ...

I think your variable patch is the same as using this in bagof/3:

        ;   findall(Vars-Templ, Goal, Answers),
            copy_term(Vars, Vars1), % <<< added
            '$bind_bagof_keys'(Vars1, Answers),
            keysort(Answers, Sorted),
            pick(Sorted, Vars, List, _)

If we agree on that, I think it is worthwhile to do a bit of timing to
see which code is faster. The code above could be simplifed a bit
because the only reason for copying the term is because
'$bind_bagof_keys'/2 needs its arity, so using functor/3 suffices.
Optimizing bagof with the lowest-level primitives available cannot be a
bad thing :-)  term_variables/2 is relatively expensive on small terms
due to all its safety measures (I think, but measuring is the only way
to know).

Second is the change =@= --> ==. The use of =@= here has been around for
a long time. If I understand it correctly however, this is unneeded for
bagof/setof because the rebinding of the variables already ensures that
variants are now equal. Right? Or am I too sleepy?

If that is the case, the comments about re-sorting can also go and your
now unconditional sort call (replacing re_sort) can go. Right?

        Cheers --- Jan

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

>Hmmm.  Your patch seems to tackle two issues: the variable binding and
>possible differences that may result from using =@=/2.  Is that right?

The problem was that '$bind_bagof_keys'/2 together with pick unified
independent witnesses together.

>I think your variable patch is the same as using this in bagof/3:
>
> ;   findall(Vars-Templ, Goal, Answers),
>    copy_term(Vars, Vars1), % <<< added
>    '$bind_bagof_keys'(Vars1, Answers),
>    keysort(Answers, Sorted),
>    pick(Sorted, Vars, List, _)

How can you be sure that the lexicographic ordering used by keysort/2
for the witness will guarantee that variants are found next to each
other in Sorted?  Your approach could at best make all Vars1 the same
for all Answers.  But then, there are also other variables needing
canonization!  We need to make them related as well.  You will at best
relate the Vars1.

With bind_bagof_keys/1 it is guaranteed that all variables in the
witness in all solutions are the same.  Thus all witness variants are
==.

It does not matter that variables are now reused in other Answers,
since these are different anyway.  Provided there are no
constraints...  Not sure if it really makes sense to handle
constraints in setof/3.  If you insist, we would need a further key:
In stead of Witness-Solution now, it would be
RenamedWitness-(Witness-Solution).  But in any case the constraint
free case should be clearly defined first.

>If we agree on that, I think it is worthwhile to do a bit of timing to
>see which code is faster. The code above could be simplified a bit
>because the only reason for copying the term is because
>'$bind_bagof_keys'/2 needs its arity, so using functor/3 suffices.

Thus no agreement.

But I agree with the original version to use within setof/3 the sort/2
instead of keysort.  In this manner redundant solutions are
immediately removed - that's useful for ground solutions, think of the
setof(t, Goal, _).

If you want speed improvements, why not =.. the Template - much like
Vars?  And why not avoid the v, if not needed, as in cases like:

?- '$e_free_variables'(but(Goal), Vars).
Vars = v(Goal).

>Second is the change =@= --> ==. The use of =@= here has been around for
>a long time. If I understand it correctly however, this is unneeded for
>bagof/setof because the rebinding of the variables already ensures that
>variants are now equal. Right?

Right.

What I am not sure was the removal of

-pick_same([H|T0], Vars, Bag1, [H|Bag], true) :-
- arg(1, H, Key),
- \+ Vars \= Key, !,
- pick_same(T0, Vars, Bag1, Bag, _).

Why was it there in the first place?  Is this a constraint thing?

>If that is the case, the comments about re-sorting can also go and your
>now unconditional sort call (replacing re_sort) can go. Right?

The comments are no longer valid.  Also the extra argument for
resorting.  There are cases, were avoiding resorting is still of
interest!  For example, if there is a single witness and the witness
does not share variables with the solution part.  For example when the
witness is ground.

Not sure how to formulate this more generally, that's why I left it
out.  There is space for improvement.

It would require to reforumlate pick more radically.  I left this for
the moment - too many steps at the same time...

In general, avoiding resorting is unsafe if the witnessset has shared
variables with the solution part.

PS: The complex variable quantification of setof/3 can sometimes be
avoided with library(lambda).  This could permit to remove setof/3's
analysis step. See

http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#setof

PPS: Did you look at the subsumes/2 thread?  I believe you wanted this
January 2008.
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

Concerning constraints and setof/3 - definitely a problematic
alliance - the tentative patch is just as incorrect as
the current version of setof/3.  Consider

?- setof(t, (X in 1..3 ; X in 2..5 ), _).
X in 2..3.


If the two answers are merged into one, it should
be X in 1..5.

I doubt that a general scheme will emerge here.
Ideally some error would be issued.  On the
other hand, the current behaviour is often
good enough.  Maybe cases could be identified that
are "not problematic"...
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Jan Wielemaker-3]

On Thu, 2009-11-05 at 14:40 +0100, Ulrich Neumerkel wrote:

> Thus no agreement.

Seems you are right.  I applied the patches and did some further
simplification.  It almost looks readable now :-)

> But I agree with the original version to use within setof/3 the sort/2
> instead of keysort.  In this manner redundant solutions are
> immediately removed - that's useful for ground solutions, think of the
> setof(t, Goal, _).
>
> If you want speed improvements, why not =.. the Template - much like
> Vars?  And why not avoid the v, if not needed, as in cases like:
>
> ?- '$e_free_variables'(but(Goal), Vars).
> Vars = v(Goal).

Seems I'm still a bit too sleepy to see where you are after, but maybe
you can send a patch.  Saving space in these predicates is certainly
worthwile.

> >Second is the change =@= --> ==. The use of =@= here has been around for
> >a long time. If I understand it correctly however, this is unneeded for
> >bagof/setof because the rebinding of the variables already ensures that
> >variants are now equal. Right?
>
> Right.
>
> What I am not sure was the removal of
>
> -pick_same([H|T0], Vars, Bag1, [H|Bag], true) :-
> - arg(1, H, Key),
> - \+ Vars \= Key, !,
> - pick_same(T0, Vars, Bag1, Bag, _).
>
> Why was it there in the first place?  Is this a constraint thing?

Thats old stuff related to =@=, from older implementations ...
Forget it.

> >If that is the case, the comments about re-sorting can also go and your
> >now unconditional sort call (replacing re_sort) can go. Right?
>
> The comments are no longer valid.  Also the extra argument for
> resorting.  There are cases, were avoiding resorting is still of
> interest!  For example, if there is a single witness and the witness
> does not share variables with the solution part.  For example when the
> witness is ground.
>
> Not sure how to formulate this more generally, that's why I left it
> out.  There is space for improvement.

I removed the reordering argument.  If I understand things correctly
whether or not reordering is needed will be a decision for all bags,
not something to be done on bag-by-bag basis.

> It would require to reforumlate pick more radically.  I left this for
> the moment - too many steps at the same time...

Makes sense.  This seems to be correct and simple now.  The
stack-shifter branch is almost ready for release.  The plan is this:

     * Merge master of development on stable --> 5.8.1
     * Merge shift branch in devel into master --> 5.9.1

>From there on things will only go from devel to stable by cherry-picking
really important patches.  

> In general, avoiding resorting is unsafe if the witnessset has shared
> variables with the solution part.
>
> PS: The complex variable quantification of setof/3 can sometimes be
> avoided with library(lambda).  This could permit to remove setof/3's
> analysis step. See
>
> http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#setof
>
> PPS: Did you look at the subsumes/2 thread?  I believe you wanted this
> January 2008.

I agree that in the ideal world current subsumes_chk/2 should have been
called subsumes/2.  I don't think we can change that anymore.  I'm
happy to drop subsumes/2 from a standard proposal.  I'm also happy
do drop the interaction with the occurs-check (I'll have a look at
that now).  Otherwise, in normally I follow standardization.

Oh, and I very much welcome a standardization forum disconnected from
vendor/personal pages.  Its good that there is a lot of discussion here,
but it would be better that if the topic is not specific to SWI-Prolog
that it is discussed in a place where other vendors listen and can feel
`at home'.

        Cheers --- Jan

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Bart Demoen-2]

Ceyhun Ciper wrote:

> Why do you avoid bagof/3 like the plague?

It is crucial to use bagof/3 only when you know exactly which
variables it contains - also deep inside its second argument. If you
are not sure, or if things change, you will end up writing stuff with
^ in the goal, just for your protection, even when not necessary
initially.

Suppose you use bagof/3 on a ADT for trees, and for some reason the
implementation of the ADT suddenly uses a different internal
representation introducing variables (that could be bound meaningfully
as well, for instance the extra slot in a node indicates the depth of
the subtree, but as long as it has not been computed, it is variable;
once computed it is a fixed integer) you are probably in deep problems.

Unless you wrote all your bagof/3 calls like

       bagof(Something,Tree^computesomething(Tree,Something),Somethings)

in which case you could have used findall/3 (followed by a test Somethings==[])

I am sure you can see some flaw in what I wrote, but most human
programmers don't off hand - you will need some thought. Well, that's
enough for me :-) Because my main objection against bagof/3 is that it
is just too complicated to be used in programs, especially in programs
that others need to read.

Also, consider that SWI's implementation of bagof/3 is (was by now)
buggy, and that this went unnoticed for many years. Something about
bagof/3, some feature of bagof/3 must be unsuited to programmers: this
feature is not used, or the bug would not have remained unnoticed for
so long. This feature is related to variables.

Note that Ulrich wrote
> (binding B to 1 and not binding B at all - how irritating!).
I usually misunderstand Ulrich, but this time, I feel confident that
he is not making a nice comment towards the spec of bagof/3.

Finally, my programming experience is limited like everyone's, but I
get away with findall/3 almost always. In the few cases I need
something like a findall/3 that retains the identity of variables
(something that bagof/3 can be used for), I prefer to write my own
bagging predicate.


Ceyhun Ciper writes:

> I really don't know where and/or when I should or shouldn't use it

This sounds like you use bagof/3 at least sometimes - why don't you
tell us why you have used it, why you thought that was the best you
could do, whether you ever doubted that, and whether you have changed
your opinion ?

Cheers

Bart Demoen


ps. ever seen bagof/3 goals with an underscore (explicit anonymous
    variable) in the second argument ? in other contexts, _ means "I am
    not interested in that part of the answer" - in bagof/3 it means

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ceyhun Ciper]

Thank you very much for the crystal clear explanation, professor; I wish Jan could include this post of yours (somewhat edited, of course) in the documentation of bagof; you see, the problem with swip documentation is that it pre-supposes that everyone understands the semantics of every predicate published thereof. SWIP is one of the best software on the planet and contributions like yours could make it better understood (as it is a logical reasoning environment, on top of a logical language).

 

Here are some facts:

• I used bagof too many times without caring that much about the 2nd argument
• When in doubt, I marked unimportant(!) data as free variables
• And then, when the code changed, I debugged (and debugged); and most of the hard stuff revealed themselves to be there
• And of course, like everybody else, I used underscores in the 2nd argument quite a few times (as it was obvious to me what I meant)

Now, to your questions:

 

Why have I used it? Because it happened to be there and seemed to be what both it's name and (scant) documentation indicated.

 

Why I thought that was the best that I could do? Because it happened to be there ... and I did not think I could do any better myself.

 

Have I ever doubted that? Nope, I doubted myself.

 

Have I changed my opinion? Now that you mention it, yes, effectively.

 

But not thoroughly, as your "ps" leaves something to be desired à la Fermat.

 

Regards,

Ceyhun

 

 

On Thu, Nov 5, 2009 at 10:21 PM, Bart Demoen <bart.demoen@...> wrote:

Ceyhun Ciper wrote:

> Why do you avoid bagof/3 like the plague?

It is crucial to use bagof/3 only when you know exactly which
variables it contains - also deep inside its second argument. If you
are not sure, or if things change, you will end up writing stuff with
^ in the goal, just for your protection, even when not necessary
initially.

Suppose you use bagof/3 on a ADT for trees, and for some reason the
implementation of the ADT suddenly uses a different internal
representation introducing variables (that could be bound meaningfully
as well, for instance the extra slot in a node indicates the depth of
the subtree, but as long as it has not been computed, it is variable;
once computed it is a fixed integer) you are probably in deep problems.

Unless you wrote all your bagof/3 calls like

      bagof(Something,Tree^computesomething(Tree,Something),Somethings)

in which case you could have used findall/3 (followed by a test Somethings==[])

I am sure you can see some flaw in what I wrote, but most human
programmers don't off hand - you will need some thought. Well, that's
enough for me :-) Because my main objection against bagof/3 is that it
is just too complicated to be used in programs, especially in programs
that others need to read.

Also, consider that SWI's implementation of bagof/3 is (was by now)
buggy, and that this went unnoticed for many years. Something about
bagof/3, some feature of bagof/3 must be unsuited to programmers: this
feature is not used, or the bug would not have remained unnoticed for
so long. This feature is related to variables.

Note that Ulrich wrote
> (binding B to 1 and not binding B at all - how irritating!).
I usually misunderstand Ulrich, but this time, I feel confident that
he is not making a nice comment towards the spec of bagof/3.

Finally, my programming experience is limited like everyone's, but I
get away with findall/3 almost always. In the few cases I need
something like a findall/3 that retains the identity of variables
(something that bagof/3 can be used for), I prefer to write my own
bagging predicate.


Ceyhun Ciper writes:

> I really don't know where and/or when I should or shouldn't use it

This sounds like you use bagof/3 at least sometimes - why don't you
tell us why you have used it, why you thought that was the best you
could do, whether you ever doubted that, and whether you have changed
your opinion ?

Cheers

Bart Demoen


ps. ever seen bagof/3 goals with an underscore (explicit anonymous
   variable) in the second argument ? in other contexts, _ means "I am
   not interested in that part of the answer" - in bagof/3 it means

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

[Ulrich Neumerkel]

Bart Demoen:
>ps. ever seen bagof/3 goals with an underscore (explicit anonymous
>    variable) in the second argument ? in other contexts, _ means "I am
>    not interested in that part of the answer" - in bagof/3 it means

To finish your sentence: in both setof/3 and bagof/3 anonymous
variables will cause to enumerate alternate (and thus invisible)
solutions.  This is not intuitive to Prolog programmers.  In fact, I
would like to see one case where an _ is used for good within setof/3
or bagof/3.  I mean in the second argument, indeed.  The idiom
setof(t, Goal, _) is very useful.

There is one remedy to this: library(lambda)!  With it, _ gets its
meaning back!  See the last example at:

http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#setof

In the long term lambdas should be compiled much like
library(apply_macros).  At least I made sure that they can be compiled
- for the meaningful cases.  Then, there would be no overhead at all.


(Sorry for this advertisement, but every time I post this I get some
response form people who have not seen it.)
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

Jan Wielemaker:
>I removed the reordering argument.  If I understand things correctly
>whether or not reordering is needed will be a decision for all bags,
>not something to be done on bag-by-bag basis.

There is need for resorting, if the findall found free variables
shared between the Witness and the Solution and those variables are of
relevance in the sort/2 such that when binding the free variables to
one instance, the list is no longer sorted.  So this is a very complex
dynamic property.  The easiest way to find out that property is to see
if resorting will change anything :-).

The patch I sent you (got it per mail?) should fix the (in my opinion)
only reasonable case, which is where the free variables are all
ground.

http://www.complang.tuwien.ac.at/ulrich/swi-prolog/git/0002-ENHANCED-Avoid-double-sorting-in-setof-3-for-the-com.patch

> '$e_free_variables'(Templ^Goal, Vars),
> (   Vars == v

I could have sworn that '$e_free_variables'/2 produces []!  How
suggestive code can be.
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

Jan Wielemaker:
>I agree that in the ideal world current subsumes_chk/2 should have been
>called subsumes/2.  I don't think we can change that anymore.  I'm
>happy to drop subsumes/2 from a standard proposal.  I'm also happy
>do drop the interaction with the occurs-check (I'll have a look at
>that now).

So we (both) agree to consider subsumes_chk/2 now.  We also agree that
subsumes_chk/2 should not consider constraints?  And that

?- freeze(X, nimporte), subsumes_chk(_,X).

succeeds instead trying to execute nimporte?  Idem

?- freeze(X, nimporte), subsumes_chk(X,X).

>            Otherwise, in normally I follow standardization.

Please note that there is nothing definitive about these predicates at
all.  We had one discussion about core (N208) so far in one meeting.
It would not be the first time that seemingly consistent proposals
then are reconsidered again and again.  And - always - this has been
for good.

The only thing definitive is the ballot (when it is passed, or fails
too often...).

>Oh, and I very much welcome a standardization forum disconnected from
>vendor/personal pages.  Its good that there is a lot of discussion here,
>but it would be better that if the topic is not specific to SWI-Prolog
>that it is discussed in a place where other vendors listen and can feel
>`at home'.

Prior to going out into the large, it is helpful to discuss things in
the small - and SWI users are very constructive.  It does not make
much sense to discuss things within WG17 if SWI people find all kinds
of holes.  After all, good quality of a proposal helps a lot.  Think
of number_codes/2 ...

And so far, I got two (2) constructive replies from the standard
mailing list when collecting informations about the current practice
of evaluable functors and built-in predicates and one (1) complaint.
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Bart Demoen-2]

Have you looked at the bagof/setof implementation in XSB ?

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Jan Wielemaker-3]

On Tue, 2009-11-10 at 08:59 +0100, Bart Demoen wrote:
> Have you looked at the bagof/setof implementation in XSB ?

No.  The previous rewrite was modeled after YAP, with
introduction of some more complexity and bugs :-)  Before
we all try to analyse how XSB's work while I guess you already
did so, it might be wise to add a few words how it is done
differently and what advantage that can bring :-)

        Cheers --- Jan

> Bart Demoen
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

>On Tue, 2009-11-10 at 08:59 +0100, Bart Demoen wrote:
>> Have you looked at the bagof/setof implementation in XSB ?
>
>No.  The previous rewrite was modeled after YAP, with
>introduction of some more complexity and bugs :-)  Before
>we all try to analyse how XSB's work while I guess you already
>did so, it might be wise to add a few words how it is done
>differently and what advantage that can bring :-)

Let me guess:  Maybe duplicates are better handled?

?- catch(setof(t,repeat,[t]),Pat,true).
Pat = error(resource_error(stack), global).

This resource error could be replaced by a "clean" infinite loop that
does not consume memory.  Or take \between(1,1000000,_) to get a
finite case.

What is XSB doing there?


On the other hand, I doubt how much that would improve performance in
general.

What is VERY nice of the current SWI implementation is that it removes
the duplicates immediately after sorting.  In this manner, pick does
not have all the baggage of redundant solutions - or should I rather
say redundant answers?

Of course, a nice factorizing GC could improve things - just in case
there is not enough memory.
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

Bart Demoen:
>My feeling has always been that the keysort could be a sort and that
>the second sort is never needed.
>
>I would like to be liberated from that uncertainty :-) So hence my
>question now: have you found an example where the second sorting is
>needed ?

Yes indeed, there are such cases.  Not that I like them.

They happen if the variables in witness will be sorted in some manner
(prior to calling setof/3).  And then will be copied by the findall/3
into a new existence with different order.

The simplest is probably sets(setof-3), i.e. sets(setof-3001) and
sets(setof-3002).  See src/test.pl

The second sort is not needed, if the witnesses are all ground.
That's probably the case you thought about - in fact the only case I
can easily imagine.

http://www.complang.tuwien.ac.at/ulrich/swi-prolog/git/0002-ENHANCED-Avoid-double-sorting-in-setof-3-for-the-com.patch

There is also another case that could be optimized which is the
setof(t,Goal,_) for nonground solutions.  But is this really worth the
effort?

BTW, I more and more like 8.10.3 for the ugly cases. It maintains
equivalence of setof(t,Goal,_) and Goal modulo termination and order
of answers.  It only removes really redundant answers.  Nice.

In any case: this is a beautiful example where the test cases helped
to locate the problem!  And once again a good illustrative point why
7.2.1 in 13211-1 clearly states:

_ If X and Y are variables which are not identical then
_ X term_precedes Y shall be implementation dependent
_ except that during the creation of a sorted list (7.1.6.5,
_ 8.10.3.1 j) the ordering shall remain constant.

>> ?- catch(setof(t,repeat,[t]),Pat,true).
>> Pat = error(resource_error(stack), global).
>>
>> This resource error could be replaced by a "clean" infinite loop that
>> does not consume memory.
>
>... not all resource errors can be replaced by clean infinite loops
>moreover, the SwI doc says (about findall):
>
>    Creates a list of the instantiations Template gets successively on
>    backtracking over Goal and unifies the result with Bag.
>
>this seems to promise that findall creates the list of all answers, so
>that ?- findall(t,repeat,[t]). must indeed report a resource_error
>instead of a clean loop.

That might be true within SWI.  But it is not true within ISO.  Where
do you read that the creation of that list has to consume space at
all?

As long as there are no side effects, you can replace
findall(t,Goal,Ts) by (Goal, false ; true), findall(t,Goal,Ts).  And
if Goal, false does never terminate, a program may execute all this
as (Goal, false).

I do not see how you can get any promises about resource errors out of
8.10.1 or the entire standard.  It only permits processors to issue a
resource error (7.12.2) "at any stage of execution".  No more no less.

>> Of course, a nice factorizing GC could improve things - just in case
>> there is not enough memory.
>
>My "factorizer" works in hProlog - ...
>I think Jan will want it in SWI :-)
!!! Hopefully so.

>But I fail to see how it would help in general with resource errors
>when the template contains variables ...

Currently that would be impossible - and probably that isn't worth the
trouble anyway.

There is just one problem with factorizing and that is setarg - that's
why it is so important to get rid of such uses - or at least to
civilize them.  And by helping to improve the global variables
proposal things would become more robust!

Please see and read and comment on the latest version of globals!
Don't let people alone on this:

http://www.sju.edu/~jhodgson/wg17/Drafts -> pdtr10.pdf

Jan has also provided a reference implementation! -> reference.pl
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Bart Demoen-2]

> The simplest is probably sets(setof-3), i.e. sets(setof-3001) and
> sets(setof-3002).  See src/test.pl

not in the stable release - so please be more specific if you expect
people to work on this ! where is it ? or please send it to me in
plain asci - I do not want to guess which release (stable or not) I
need to download to work on this !

> That's probably the case you thought about
No. Unless I have seen the test cases, I think that the second sort is
not needed :-)

> There is also another case that could be optimized which is the
> setof(t,Goal,_) for nonground solutions.  But is this really worth the
> effort?

OR COURSE NOT !

> Where do you read that the creation of that list has to consume
> space at all?

If you have a general way of representing infinite lists of solutions
finitely, please publish.

> As long as there are no side effects, you can replace
> findall(t,Goal,Ts) by (Goal, false ; true), findall(t,Goal,Ts).  And
> if Goal, false does never terminate, a program may execute all this
> as (Goal, false).

I thought you were into optimizing stuff, not pessimizing :-)

> I do not see how you can get any promises about resource errors out
> of 8.10.1 or the entire standard.

That's why I did not refer to the standard.

> >But I fail to see how it would help in general with resource errors
> >when the template contains variables ...
>
> Currently that would be impossible - and probably that isn't worth the
> trouble anyway.

You suggested that a factorizing gc would help - now you say it
wouldn't "currently" - what do you mean ?

> There is just one problem with factorizing and that is setarg

No, not really. Just wait a little and read our report on
representation sharing for Prolog.
> or at least to civilize them
Indeed, that's the approach.

> And by helping to improve the global variables
> proposal things would become more robust!

Global variables don't come in at all.

Cheers

Bart Demoen

ps1. don't forget to send the setof-3001 setof-3002 problematic cases
(setof-3 already turns out not to be a problem)

ps2. can we have less rethoric/adds and more work ?

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Bart Demoen-2]

> _ If X and Y are variables which are not identical then
> _ X term_precedes Y shall be implementation dependent
> _ except that during the creation of a sorted list (7.1.6.5,
> _ 8.10.3.1 j) the ordering shall remain constant.


meaning that

        ?- L = [X,Y], sort(L,L1), sort(L,L2), L1 == L2.

is allowed to fail, right ?

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

>> _ If X and Y are variables which are not identical then
>> _ X term_precedes Y shall be implementation dependent
>> _ except that during the creation of a sorted list (7.1.6.5,
>> _ 8.10.3.1 j) the ordering shall remain constant.
>
>
>meaning that
>
> ?- L = [X,Y], sort(L,L1), sort(L,L2), L1 == L2.
>
>is allowed to fail, right ?

The notion of implementation dependence 3.91 is what is central here.
The case is not undefined, but implementation dependent.  That is, an
implementer is free to define it (not even as an extension!).

In fact, you might consider defining exactly what we can rely on in
SWI.  Would be interesting to see your definition.  Expansions like
library(apply_macros) should still be permitted, indeed.

BTW, in the following example, SWI - like most other systems - behaves
differently on a case very similar to yours above.

The second clause corresponds to what a meta-interpreter using
clause/2 would do.  Or - seen it the other way round- the first clause
could be considered an optimization of the second.

p(Xs1) :-
        Xs3 = [_],
        Xs1 = [_|Xs2],
        Xs2 = [_|Xs3].

variableorder_paradoxon(1) :-
        p(L),
        sort(L, LS1),
    L = [_,_|_],
    sort(L,LS2),
    LS1 \== LS2.
variableorder_paradoxon(2) :-
        call((
                p(L),
                sort(L, LS1),
    L = [_,_|_],
    sort(L,LS2),
    LS1 \== LS2
        )).
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog