# Programming cooperation

Example of `bagof` vs `findall`:

``````list_pair([H|T], H-E2) :-
member(E2, T).

list_pair([_, H2|T], Pair) :-
list_pair([H2|T], Pair).
``````
``````?- L = [A, B, C], bagof(P, list_pair(L, P), Pairs).
Pairs = [A-B,A-C,B-C].

?- L = [A, B, C], findall(P, list_pair(L, P), Pairs).
Pairs = [_-_,_-_,_-_].
``````

For the basic predicates listed on Finding all Solutions to a Goal, i.e. findall/3,bagof/3 and setof/3 which follow the form of

``````functor(+Template, :Goal, -List)
``````

here is what I consider and think of when using them.

If one has the need to convert facts or results from predicates into a list for further processing then these are most likely the predicates that will be used. More advanced predicates fulfilling the same need are in

library(aggregate): Aggregation operators on backtrackable predicates

but it is easier to start with the first three before learning the aggregate predicates.

If you already have a list then

library(apply): Apply predicates on a list

is probably what you need.

In understanding the predicates one needs to understand the instantiation patterns of the predicate. (ref)

pattern Description
+ Argument is fully instantiated at call-time, to a term that satisfies the type. This is not necessarily ground, e.g., the term `[_]` is a list, although its only member is unbound.
: Argument is a meta-argument. Implies `+`.
- Argument is an output argument. It may be unbound at call-time, or it may be bound to a term. In the latter case, the predicate behaves as if the argument was unbound, and then unified with that term after the goal succeeds. For example, the goal `findall(X, Goal, [T])` is good style and equivalent to `findall(X, Goal, Xs), Xs = [T]` 3 Determinism declarations assume that the argument is a free variable at call-time. For the case where the argument is bound or involved in constraints, `det` effectively becomes `semidet`, and `multi` effectively becomes `nondet`.

That is a bit to take in at first so will explain it more for the three predicates as each is covered.

Normally arguments follow the pattern of input, then output so that when using the arguments one would think about them simply from left to right.

Here that is not the case as the argument that I consider the input argument to be the second argument, Goal which is a predication. Think of this as the name of the fact, predicate or Goal you would query from the top level to repetitively show the values or results of the Goal. The pattern : just informs me that the argument may/can include the module name, e.g. <module>:<predication>.

The next argument I consider is the first one, Template, and think of it as what the result should look like. For example if the Goal is `person(Name,Address,Phone)` and only the Name values are needed then the template would be Name. If more then on one value is needed to be collected then I usually put them in a compound term with a functor, e.g. `item(Name,Address)`.

When first learning these three predicates the point which was not obvious to me but crucial to understanding the predicates and until understood will make these predicates very frustrating to use is noted in the documentation as

findall/3 is equivalent to bagof/3 with all free variables appearing in Goal scoped to the Goal with an existential (caret) operator (`^` ), except that bagof/3 fails when Goal has no solutions.

I have even asked questions about the existential operator over the years in trying to understand it.

Basically this is how I think about it while I type in code.

``````1. Do I need unique and sorted values?
a. Yes - use setof/3
b.  No
Is an empty list as the result allowed?
a. Yes - use findall/3 which will not fail and return empty list if no solutions.
b. No - use bagof/3 which will fail if no solutions.
``````

Note: If you need sorted with duplicates then setof/3 can not be used as it will remove duplicates when sorting.

With that out of the way then if findall/3 is used there is no need to think about the existential operator. For the other two the existential operator is needed otherwise one can get multiple results on backtracking which is hard to debug. (ref)

Note: When noting the existential operator (^)/2 I strive to use the words existential operator as most search engines can not find anything using just ^/2. The only one that gets a hit is the SWI-Prolog documentation search, i.e. ^/2

The next thing I have learned over the years about the existential operator is that depending upon ones background the understanding about it they bring when asking about it has a lot to do with understanding how they discuss it. Those with a math background and use to proofs talk one way, while those with a logic background seem to use another and those who are talking about it for the first time when asking a question seem to be totally confused, which was me for a while.

So as I code the Goal argument as needed if the existential operator is needed I do this.

1. Write the Goal with the functor and all of the arguments as unique named variables, no singleton variables, e.g. `_A`. Do not add the existential operator just yet.
2. Write the `Template` using the names of the variables that are to be collected and leaving out the names of the variables that are not needed.
3. Finish the `Goal`.
a. Add `^` before Goal, thinking of `^` as a binary operator used as an infix.
b. Add `[]` before `^` which is the one of the two arguments to the `^` binary operator and can be a list. For single values it does not have to be in a list, e.g. `A^person(Name,A)`.
c. Account for all of the variables in `Goal`, if they are not used in the Template then add them to the list for the existential operator.

Note: I tend to change the names of the variables used with the existential operator from the user friendly names to an alphabetical list, e.g. `[A,B,C,D]` as it makes it easier to identify the arguments to be collected and the arguments to be discarded but also easier to ensure all of the variables are accounted, e.g. `bagof(item(Name,Location),[A,B]^person(Name,A,Location,B),Items)`

The last argument is `List` which is just a name for the list. If template is just a single variable then I just use the plural of the name, e.g. for a Template of `Name` the List would be `Names`. If Template is a compound, then I often use a functor of `item` and for `Name` use `Items`.

I know that is a lot of details and seems like a lot to take in when typing code but once you learn these three you find that you are using them so often you don’t know why you didn’t learn to use them sooner.

HTH

1 Like

this basic step-plan for the use of findall , bagof and setof is perfect, gives me a lot more understanding also. up until now i have allways chosen to use findall because the other 2 were completely unclear to me. When i use findall, then after the findall i would adjust a list processing or/and any sorting for the specific task.

can i ask this question: can it be said that in the case of the name : Bagof / bagof the name of the predicate could have also or would have instead better have been : findall_pairs ? because the meaning of Bag in Bagof is zero?

Personally I ask myself that question often for more than just those predicates, e.g.

For this use of concurrent_forall instead of `concurrent_forall(:Generate, :Test)` I think of it as `concurrent_forall(:Generate unique threads values, :Call thread with unique values)`.

(ref)

For such cases where it was a revelation to think of it differently I will often add a comment in my code or note it when writing about it. In some cases I will even add a wrapper predicate with the new name so that the reading of other predicates using it is more natural. Yes I know that will slow down the code but if code can not be understood then it is likely to be tossed by those maintaining it.

So yes, don’t beholden to the name as given.

dear Eric,

thankyou for this information, i understand bagof it better with it,

so then because this is used in the first argument:
item(Name,Location)

the result list in Items will be a list of this predicate?:

so Items will be in this format ?:

[ item(‘rene’, ‘netherlands’), item(‘eric’, ‘cloud_location’) ]

thnky

Personally I would not call them predicates, I would refer to them as facts.

While Prolog does have an official standard and the standard does include terminology, as the standard is copyright it can not be handed out freely for those of us that have a copy. However in answering certain questions such as you ask, this StackOverflow answer includes the related terminology.

The definition I go with for Prolog fact most of the time is that it is a clause with only a head and the parameters are all ground.

That is what I would expect.

My current favorite technique for understanding code methods/functions/predicates is to download Git repositories that contain code I trust to be done correctly. All of the repositories are kept in a separate directory with a name like `SWI-Prolog (Reference code for searching)` and then using a command line tool such as grep or an IDE with a good search engine and visual summary such as NotePad++ I search for the method/function/predicate name and then look at the results.

Here is a list of Git Repositories containing Prolog code that you can trust will be done correctly.

My current set in `SWI-Prolog (Reference code for searching)` (Click triangle to expand)

Beekeeper-66d7712ab5e457471d890c109ff78e1745e2a8e0
bench-master
bornhackgame-main
ClioPatria-master
clpqr-examples-master
contrib-protobufs-master
docker-swipl-linux-ci-master
ecCausaSnipper-master
LudumDare-master
LudumDare48-66de13f79e278dd7cd361db20328e227d24e56a4
packages-archive-master
packages-bdb-master
packages-chr-master
packages-clib-master
packages-clpqr-master
packages-cppproxy-master
packages-cql-master
packages-http-master
packages-inclpr-master
packages-jpl-master
packages-ltx2htm-master
packages-mqi-master
packages-odbc-master
packages-pcre-master
packages-pengines-master
packages-pldoc-master
packages-plunit-master
packages-prosqlite-master
packages-RDF-master
packages-real-master
packages-redis-master
packages-semweb-master
packages-sgml-master
packages-ssl-master
packages-utf8proc-master
packages-windows-master
packages-xpce-master
packages-yaml-master
packages-zlib-master
pengines-master
plweb-blog-master
plweb-examples-master
plweb-master
plweb-www-master
prolog-f28911d86e82b29c52078a2da498c82d39a0b07e
rclswi-master
sCASP-swipl
swipl-devel-master
swipl-master
swipl-server-js-client-master
swiplwebtut-master
swish-master
transhavengame-eb2b92a98e2274111fce4699f554554227dcf312
webstat-master

yes correct i should have said : facts instead of using the word predicates

Neither do I really since `->` is identical to `, !,` making it pure language clutter.

I’m guessing the history of `->` is since programming languages invariably have something along the lines of `IF some_test(A, B) THEN do_this(A, B) ELSE do_that(A,B)`, so it became a prolog convention to imitate this with

``````(    some_test(A, B)
->   do_this(A, B)
;    do_that(A, B)
),
``````

In my opinion, a clearer way to write that is

``````my_rule(A, B) :-
some_test(A, B), !,
do_this(A, B).

my_rule(A, B) :-
do_that(A, B).
``````

Reasons I don’t like the `->` syntactic sugar for `, !,` is it’s confusingly similar to DCG’s `-->` operator and classical logic’s implies operator → (which confuses nearly everyone, I’ve put some notes on my interpretation here).

Synonyms are a pet hate of mine because whenever you have more than one way to say exactly the same thing, some pedant will come along and invent rules on why one way is better than another, as I’ve done above.

could it also be said that as soon as you make Use of this arrow operator, you switch from declarative to procedural programming?

I don’t think so. Some Prolog purists consider cut harmful because it limits your query to only one result, which can be dangerous when doing database-type stuff. Prolog-inspired SQL-alternative Datalog specifically excludes the ! operator to avoid losing rows which might otherwise match.

A newby mistake I made, and I suspect is quite common, was writing extremely convoluted `if ... then ... else if ... ` code which got completely unreadable when I started nesting `if .. then ...` within outer then/else blocks. I’ve found writing a separate stanza for each or branch made my code way easier to maintain and debug.

A rule of thumb I have is whenever I find myself using the `;` operator, I ask myself I this should be split into a separate stanza of a rule. A big selling point of Prolog is you can do that easily, whereas in other programing languages you end up with lots of cases in a switch block or worse yet nested `if.. then ... else...` spaghetti.

prolog code is extremely well suited to modify or enhance after the main code was already written.

where as with other languages you write it once and never touch it again

No, (->)/2 and !/0 are very different, e.g. there is no “else” in a cut, and (->)/2 does not prevent backtracking into another predicate with the same name & arity.

Let me illustrate with a working example:

``````ifthen1(A, B) :-
(    A == B
->   format('A == B')
;    format('A \== B')
).

ifthen2(A, B) :-
(    A == B
, !, format('A == B')
;    format('A \== B')
).
``````

These two work identically. To be clear, I’m not saying the arrow operator is the same as cut. It’s the same as comma cut comma.

To show the difference:

``````mintest(X, Y, Min) :-
(   X @=< Y, !,
Min = X
;   Min = Y
).

mintest(_X, _Y, strawberries_and_cream).
``````
``````?- mintest(1, 2, Min).
Min = 1.
``````

Vs:

``````mintest(X, Y, Min) :-
(   X @=< Y ->
Min = X
;   Min = Y
).

mintest(_X, _Y, strawberries_and_cream).
``````
``````?- mintest(1, 2, Min).
Min = 1 ;
Min = strawberries_and_cream.
``````
4 Likes

Usually, this would be written
`setof(C, A^B^(my_module:my_goal(A,B,C)), Set)`.

It’s easy to get the “exists” items wrong (and even easier if there are anonymous variables, or “joining” variables), so I would suggest:

``````my_goal(C) :- my_module:my_goal(_A,_B,C)
... setof(C, my_goal(C), Set)
``````

(also, if you import `my_goal`, then you don’t need `my_module:...`)

As to differences between findall/3 and bagof/3 (besides the existential variables), here are examples where findall/3 breaks “pure logic” (e.g., you can define not/1 or var/1 using findall/3):

This doesn’t mean that findall/3 shouldn’t be used, but you need to be aware of the same kinds of things that cause problems with “not” or negation-as failure. I prefer to use this instead of findall:
`( findall(C, my_goal(C), set) -> true ; C = [] )`

Your experience is very different from mine … every place I’ve worked, there’s been lots of cooperation between programmers, sometimes even with competitors (e.g., setting industry standards). [There have been some nasty people who took advantage of the cooperation, but that happens outside of commercial contexts also.]

Thanks for introducing me to a subtlety of the arrow operator I wasn’t aware of @brebs.

The same thing can easily be done without the arrow operator as follows:

``````mintest(X, Y, X) :-
X @=< Y.

mintest(X, Y, Y) :-
X @> Y.

mintest(_X, _Y, strawberries_and_cream).

``````

So my prejudice that `->` is pointless remains.

The thing is: in your example, you need two tests, one for smaller than, another one for larger than, which can become computationally expensive if the test ist more complicated.

The simple way to avoid a second computation is to cut:

``````mintest(X, Y, X) :-
X @=< Y, !.

mintest(_X, Y, Y).
``````

The example @brebs gave explained that `->` doesn’t cut (as I had wrongly thought), but rather leaves the way open to further options. I maintain a stanza per option is better style, and ideally each option should have its own clearly defined guard as Edsger Dijkstra proposed.

Ah, of course, sorry. Your example referred to ->, not cut. I missed that point.

Another thing: I think the unification should be postponed after the cut,

``````mintest(X, Y, Min) :-
X @=< Y,
!, Min = X.

mintest(_X, Y, Y).
``````

I don’t remember exactly why, but O’Keefe explained it in his book.

Which brings us to SSU:

``````mintest(X, Y, Min),
X @=< Y
=> Min = X.

mintest(_X, Y, Min)
=> Min = Y.
``````

aka. Prolog for Turbo Pascal