4

I'm making a Prolog program that finds a subset of a set of lists. This subset must match some specific conditions, an aspect of which is that the subset's lists cannot be identical. What's confusing me is that when I try to find a match for a variable, X, it generates results that return false if I plug them into the query in place of X. For example:

?- containsSet(2, [[3],[7],[7]], X).
X = [[3], [7]] ;
X = [[3], [7]] ;
X = [[7], [7]] ;
false.

?- containsSet(2, [[3],[7],[7]], [[7],[7]]).
false.

How could it possibly match X to [[7], [7]] if, when plugged in directly, it returns false?

The idea of containsSet is to find a length-N (in this case 2) subset of lists that has no matching elements in matching positions (i.e. no two lists in the subset have the same first element, or the same second element, etc). In the example above, the first (and only) elements of [7] and [7] match, so it returns false.

false
  • 10,264
  • 13
  • 101
  • 209
vestlen
  • 1,103
  • 11
  • 17
  • 4
    Very good observation! This clearly violates commutativity of conjunction, and therefore runs counter to what we expect from pure logical relations. Very likely, you are using non-monotonic and impure constructs like `(\+)/1`, `!/0` or if-then-else in your code. You should eliminate these impurities by using constraints like `dif/2` to express that two terms are different. This will make your program pure, and usable in more directions. See [tag:prolog-dif] and [tag:logical-purity]. Also, `please_use_more_readable_names` `insteadOfNamesNoOneCanReadProperly`. – mat Oct 14 '15 at 09:58
  • 2
    Ah! I am using `(\+)/1` a couple times in the line `set_is_compatible(SET) :- \+ (select(X,SET,R), \+ list_compatible_with_set(X,R))`. I'll try to figure out how to rewrite this. Thank you! – vestlen Oct 14 '15 at 10:12
  • 4
    Yes, I highly recommend using a pure predicate like `dif/2` instead. The `(\+)/1` version will create endless declarative problems for you. Consider for example: `?- \+ select(X, [a,b,c], Rest), X = d.`, yielding `false`, **but**, if we just exchange these two goals by (desirable!) commutativity of conjunction, we get instead: `X = d`. `(\+)/1` is sound if its argument is ground, but in general, you cannot rely on such non-monotonic predicates to get truly general and declarative solutions. You better stay in the pure and monotonic subset of Prolog to retain these nice properties. – mat Oct 14 '15 at 10:24

1 Answers1

3

First, congratulations for one of the most declarative and justified observations I have seen in questions by beginners!

On the one hand, it is one of the most basic and well-known properties that conjunction is commutative in logic. On the other hand, many Prolog beginners fail to realize that using one of the non-monotonic predicates like (\+)/1 almost invariably destroys such basic invariants. You noticed that something very unexpected is going on here, and you are right to expect more correct behaviour from Prolog. Luckily, declarative solutions for such problems are now more widely spread than ever before among Prolog systems.

First, consider some problems that soon arise if you use (\+)/1 in your programs:

?- X = d, \+ member(X, [a,b,c]).
X = d.

yet, if we simply exchange the goals by commutativity of conjunction, we get the different answer:

?-  \+ member(X, [a,b,c]), X = d.
false.

This shows that (\+)/1 is not monotonic: It can cause a more general query to fail although a more specific query yields solutions:

?-  \+ member(X, [a,b,c]).
false.

?- \+ member(d, [a,b,c]).
true.

Thus, non-monotonic predicates cause all kinds of impurities and violate declarative semantics. Declaratively, knowing that there are solutions, we certainly expect the more general query to succeed, but it fails.

In this concrete, to specify that a term is different from all other terms in a list, use the constraint dif/2. dif/2 works in all directions, and yields correct answers also if its arguments are variables. For example:

not_member(X, Ls) :- maplist(dif(X), Ls).

This definition preserves commutativity of conjunction, as we deeply desire and in fact expect from pure logical relations:

?- not_member(X, [a,b,c]), X = d.
X = d.

?- X = d, not_member(X, [a,b,c]).
X = d.

Since not_member/2 uses only pure predicates, you have ensured — already by construction — that it gives only declaratively correct answers.

For reasoning declaratively about your code, which I applaud in your approach, I recommend you stay in the pure monotonic subset of Prolog. See and for more information.

mat
  • 40,498
  • 3
  • 51
  • 78
  • 1
    Thanks for these examples! This was really enlightening. I think I'm starting to grasp how Prolog works in this way a little better – vestlen Oct 18 '15 at 09:31