Equivalence relation in prolog

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 )).

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top