CODEWITHSUNDEEP
functional-programmingprologlogicpurely-functional
bp99
bp99

Reputation: 348

Equivalence relation in prolog

I would like to implement a simple if and only if relation in my Prolog code. Here is a simple example of what I would like to have:

?- a_iff_b(a, b).
true.

?- a_iff_b(x, x).
true.

?- a_iff_b(a, x).
false.

?- a_iff_b(x, b).
false.

You get the point—the predicate should be true if either the first argument is a and the second argument is b or if neither is the first argument a nor is the second b. I hope that makes sense. Mathematically speaking, X = a <==> Y = b.

Here is my attempt:

a_iff_b(X, Y) :-
        X = a, Y = b;
        X \= a, Y \= b.

But this code introduces a choice point:

?- a_iff_b(a, b).
true ;
false.

Why? It seems that the following works, I mean it does not introduce the choice point:

a_iff_b(X, Y) :- (X = a -> Y = b; Y \= b).

However, I find this a little less readable, especially because in my actual predicate, the two sides of the equivalence are more complex (the are also predicates).

Upvotes: 0

Views: 411

Answers (1)

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

Your code introduces a choice point because it contains a choice introduced by the ; operator. You might think of this as a "logical or" operator, and somewhat informally it is. But procedurally it is an "introduce a choice point here, and on backtracking, explore the second branch as well" operator.

It's true that a Sufficiently Powerful Prolog Compiler™ might be able to recognize that the two branches here are mutually exclusive, but it appears that your Prolog system isn't that powerful. I would be at least mildly surprised if any Prolog you can get for free would be able to do this without a choice point. Especially if your actual conditions are more complex, as you say.

If you want this to be more readable, some tips:

  • In general, never use ; at the end of a line as if it were just a variant of ,. It's too easy to miss it, since the general expectation is that lines end in ,. Try to format your code in some way that really makes the ; stick out (see examples below).

  • In general, if you want to use ; (not _ -> _ ; _), especially as the single top-level goal in a clause, consider using separate clauses instead:

      a_iff_b(a, b).
  a_iff_b(X, Y) :-
      X \= a,
      Y \= b.

In any case, all of the following are possible ways of cutting away the choice:

a_iff_b_1(a, b) :-
    !.
a_iff_b_1(X, Y) :-
    X \= a,
    Y \= b.

a_iff_b_2(X, Y) :-
    (   X = a, Y = b
    ->  true
    ;   X \= a, Y \= b ).

a_iff_b_3(X, Y) :-
    (   X = a, Y = b,
        !
    ;   X \= a, Y \= b ).

a_iff_b_4(X, Y) :-
    (   X = a, Y = b
    ;   X \= a, Y \= b ),
    !.

a_iff_b_5(X, Y) :-
    once(( X = a, Y = b
         ; X \= a, Y \= b )).

Upvotes: 3

Related Questions