Justification for Equality / Inequality

Question

Pure Prolog programs that distinguish between equality and inequality of terms in their pure form suffer from inefficiencies in execution; even when all conditions of relevance are justified.

A recent example of SO is this answer . All answers and all failures are correct in this definition. Consider:

?- Es = [E1,E2], occurrences(E, Es, Fs). Es = Fs, Fs = [E, E], E1 = E2, E2 = E ; Es = [E, E2], E1 = E, Fs = [E], dif(E, E2) ; Es = [E1, E], E2 = E, Fs = [E], dif(E, E1) ; Es = [E1, E2], Fs = [], dif(E, E1), dif(E, E2). 

While the program is flawless from a declarative point of view, its direct execution on current systems such as B, SICStus, SWI, YAP is unnecessarily inefficient. For the next purpose, the selection point remains open for each item in the list.

  ? - occurrences (a, [a, a, a, a, a], M).
 M = [a, a, a, a, a] ; 
  false

This can be observed using a sufficiently large list a as follows. You may need to adapt I so that the list can be represented; in swi this would mean that

1mo I should be small enough to prevent a resource error for the global stack, as shown below:

  ? - 24 = I, N is 2 ^ I, length (L, N), maplist (= (a), L).
 ERROR: Out of global stack 

2do I must be large enough to cause a resource error for the local stack:

  ? - 22 = I, N is 2 ^ I, length (L, N), maplist (= (a), L), (Length = ok; occurrences (a, L, M)).
 I = 22,
 N = 4194304,
 L = [a, a, a, a, a, a, a, a, a | ...],
 Length = ok;
 ERROR: Out of local stack 

To overcome this problem and still maintain good declarative properties, a predicate of comparison is necessary.

---

How should this predicate be compared?

---

Here is a possible definition:

 equality_reified (X, X, true).
 equality_reified (X, Y, false): -
    dif (X, Y).

Edit: Perhaps the order of the arguments should be reversed, like the ISO built-in compare/3 (link only to draft).

An effective implementation of it would first handle quickly certain cases:

 equality_reified (X, Y, R): - X == Y,!, R = true.
 equality_reified (X, Y, R): -? = (X, Y),!, R = false.  % syntactically different
 equality_reified (X, Y, R): - X \ = Y,!, R = false.  % semantically different
 equality_reified (X, X, true).
 equality_reified (X, Y, false): -
    dif (X, Y).

Edit: I don't understand if X \= Y defender in the presence of restrictions. Without limitation, ?=(X, Y) or X \= Y coincide.

---

Example

As shown in [user1638891], here is an example of how to use such a primitive. The source code of the mats was:

 occurrences_mats(_, [], []). occurrences_mats(X, [X|Ls], [X|Rest]) :- occurrences_mats(X, Ls, Rest). occurrences_mats(X, [L|Ls], Rest) :- dif(X, L), occurrences_mats(X, Ls, Rest). 

What can be rewritten to something like:

 occurrences(_, [], []). occurrences(E, [X|Xs], Ys0) :- reified_equality(Bool, E, X), ( Bool == true -> Ys0 = [X|Ys] ; Ys0 = Ys ), % ( Bool = true, Ys0 = [X|Ys] ; Bool = true, Ys0 = Ys ), occurrences(E, Xs, Ys). reified_equality(R, X, Y) :- X == Y, !, R = true. reified_equality(R, X, Y) :- ?=(X, Y), !, R = false. reified_equality(true, X, X). reified_equality(false, X, Y) :- dif(X, Y). 

Please note that index indexing of the second SWI index is activated, after a query of type occurrences(_,[],_) is entered. In addition, SWI needs an inherently non-monotone if-then-else, since it is not indexed by (;)/2 - disjunctions. SICStus does this, but has only the first indexing argument. Thus, it leaves one (1) point-to-point open (at the end of [] ).

Answer 1

Well, firstly, the name should be more declarative, e.g. equality_truth/2 .

Answer 2

The following code is based on if_/3 and (=)/3 (aka equal_truth/3 ), as implemented by @false in the Prolog union for AUBUC :

 =(X, Y, R) :- X == Y, !, R = true. =(X, Y, R) :- ?=(X, Y), !, R = false. % syntactically different =(X, Y, R) :- X \= Y, !, R = false. % semantically different =(X, Y, R) :- R == true, !, X = Y. =(X, X, true). =(X, Y, false) :- dif(X, Y). if_(C_1, Then_0, Else_0) :- call(C_1, Truth), functor(Truth,_,0), % safety check ( Truth == true -> Then_0 ; Truth == false, Else_0 ). 

Compared to occurrences/3 auxiliary occurrences_aux/3 uses a different order of arguments, which passes the list Es as the first argument, which may include indexing the first argument:

 occurrences_aux([], _, []). occurrences_aux([X|Xs], E, Ys0) :- if_(E = X, Ys0 = [X|Ys], Ys0 = Ys), occurrences_aux(Xs, E, Ys). 

As @migfilg pointed out, the target Fs=[1,2], occurrences_aux(Es,E,Fs) should fail because it is logically false: occurrences_aux(_,E,Fs) indicates that all elements from Fs are equal to E However, occurrences_aux/3 does not end in such cases.

We can use the helper predicate allEqual_to__lazy/2 to improve completion behavior:

 allEqual_to__lazy(Xs,E) :- freeze(Xs, allEqual_to__lazy_aux(Xs,E)). allEqual_to__lazy_aux([],_). allEqual_to__lazy_aux([E|Es],E) :- allEqual_to__lazy(Es,E). 

With all the auxiliary predicates in place, define occurrences/3 :

 occurrences(E,Es,Fs) :- allEqual_to__lazy(Fs,E), % enforce redundant equality constraint lazily occurrences_aux(Es,E,Fs). % flip args to enable first argument indexing 

Suppose there are several requests:

 ?- occurrences(E,Es,Fs). % first, the most general query Es = Fs, Fs = [] ; Es = Fs, Fs = [E] ; Es = Fs, Fs = [E,E] ; Es = Fs, Fs = [E,E,E] ; Es = Fs, Fs = [E,E,E,E] ... % will never terminate universally, but ... % that ok: solution set size is infinite ?- Fs = [1,2], occurrences(E,Es,Fs). false. % terminates thanks to allEqual_to__lazy/2 ?- occurrences(E,[1,2,3,1,2,3,1],Fs). Fs = [1,1,1], E=1 ; Fs = [2,2], E=2 ; Fs = [3,3], E=3 ; Fs = [], dif(E,1), dif(E,2), dif(E,3). ?- occurrences(1,[1,2,3,1,2,3,1],Fs). Fs = [1,1,1]. % succeeds deterministically ?- Es = [E1,E2], occurrences(E,Es,Fs). Es = [E, E], Fs = [E,E], E1=E , E2=E ; Es = [E, E2], Fs = [E], E1=E , dif(E2,E) ; Es = [E1, E], Fs = [E], dif(E1,E), E2=E ; Es = [E1,E2], Fs = [], dif(E1,E), dif(E2,E). ?- occurrences(1,[E1,1,2,1,E2],Fs). E1=1 , E2=1 , Fs = [1,1,1,1] ; E1=1 , dif(E2,1), Fs = [1,1,1] ; dif(E1,1), E2=1 , Fs = [1,1,1] ; dif(E1,1), dif(E2,1), Fs = [1,1]. 

---

Edit 2015-04-27

Several requests for testing if the universal termination of occurrences/3 completes in certain cases:

 ?- occurrences(1,L,[1,2]). false. ?- L = [_|_],occurrences(1,L,[1,2]). false. ?- L = [X|X],occurrences(1,L,[1,2]). false. ?- L = [L|L],occurrences(1,L,[1,2]). false. 

Answer 3

It seems best to call this predicate the same arguments (=)/3 . Thus, conditions like if_/3 are now more readable. And use _t instead of _truth instead of the _truth :

 memberd_t(_X, [], false). memberd_t(X, [Y|Ys], Truth) :- if_( X = Y, Truth=true, memberd_t(X, Ys, Truth) ). 

Before:

 memberd_truth(_X, [], false). memberd_truth(X, [Y|Ys], Truth) :- if_( equal_truth(X, Y), Truth=true, memberd_truth(X, Ys, Truth) ). 

Answer 4

UPDATE: This answer was replaced by mine on April 18th. I do not suggest deleting it because of the comments below.

My previous answer was wrong. The following goes against the test case in question, and the implementation has the desired feature, avoiding unnecessary points of choice. I assume that the top predicate mode is ?, + ,? although other modes can be easily implemented.

The program has 4 sentences: the list in the second argument is visited, and for each member there are two possibilities: it either combines with the 1st argument of the upper predicate, or differs from it, and in this case a dif is applied:

 occurrences(X, L, Os) :- occs(L, X, Os). occs([],_,[]). occs([X|R], X, [X|ROs]) :- occs(R, X, ROs). occs([X|R], Y, ROs) :- dif(Y, X), occs(R, Y, ROs). 

Startup examples using YAP:

 ?- occurrences(1,[E1,1,2,1,E2],Fs). E1 = E2 = 1, Fs = [1,1,1,1] ? ; E1 = 1, Fs = [1,1,1], dif(1,E2) ? ; E2 = 1, Fs = [1,1,1], dif(1,E1) ? ; Fs = [1,1], dif(1,E1), dif(1,E2) ? ; no ?- occurrences(E,[E1,E2],Fs). E = E1 = E2, Fs = [E,E] ? ; E = E1, Fs = [E], dif(E,E2) ? ; E = E2, Fs = [E], dif(E,E1) ? ; Fs = [], dif(E,E1), dif(E,E2) ? ; no 

Answer 5

Here is an even shorter logically pure implementation occurrences/3 .

We will build it on meta-predicate tfilter/3 , the equality predicate (=)/3 and the coroutine allEqual_to__lazy/2 (defined in my previous answer to this question):

 occurrences(E,Xs,Es) :- allEqual_to__lazy(Es,E), tfilter(=(E),Xs,Es). 

Done! To facilitate comparison, we re-run the same queries as in the previous answer:

 ?- Fs = [1,2], occurrences(E,Es,Fs). false. ?- occurrences(E,[1,2,3,1,2,3,1],Fs). Fs = [1,1,1], E=1 ; Fs = [2,2], E=2 ; Fs = [3,3], E=3 ; Fs = [], dif(E,1), dif(E,2), dif(E,3). ?- occurrences(1,[1,2,3,1,2,3,1],Fs). Fs = [1,1,1]. ?- Es = [E1,E2], occurrences(E,Es,Fs). Es = [E, E ], Fs = [E,E], E1=E , E2=E ; Es = [E, E2], Fs = [E], E1=E , dif(E2,E) ; Es = [E1,E ], Fs = [E], dif(E1,E), E2=E ; Es = [E1,E2], Fs = [], dif(E1,E), dif(E2,E). ?- occurrences(1,[E1,1,2,1,E2],Fs). E1=1 , E2=1 , Fs = [1,1,1,1] ; E1=1 , dif(E2,1), Fs = [1,1,1] ; dif(E1,1), E2=1 , Fs = [1,1,1] ; dif(E1,1), dif(E2,1), Fs = [1,1]. ?- occurrences(1,L,[1,2]). false. ?- L = [_|_],occurrences(1,L,[1,2]). false. ?- L = [X|X],occurrences(1,L,[1,2]). false. ?- L = [L|L],occurrences(1,L,[1,2]). false. 

Finally, the most common query:

 ?- occurrences(E,Es,Fs). Es = Fs, Fs = [] ; Es = Fs, Fs = [E] ; Es = Fs, Fs = [E,E] ; Es = Fs, Fs = [E,E,E] % ... and so on ad infinitum ... 

We get the same answers.

Answer 6

The implementation of occurrences/3 below is based on my previous answers, namely on making profit from the mechanism for indexing offers on the 1st argument, in order to avoid some points of choice and eliminates all the problems that have arisen.

In addition, he copes with the problem in all subordinate implementations so far, including the one in question, namely, that they all enter an infinite loop when the request has the first 2 arguments for free, and the third with different ground elements. Of course, the correct behavior is failure.

Using a comparison predicate

I think that in order to avoid unused selection points and maintaining a good degree of declarative implementation, there is no need for the comparison predicate proposed in the question, but I agree that this can be a matter of taste or inclination.

Implementation

Three exceptional cases are considered in this order: if argument 2 is argumentative, then it is visited recursively; otherwise, if the third argument is grounded, it is checked and then visited recursively; otherwise, matching lists are created for the 2nd and 3rd arguments.

 occurrences(X, L, Os) :- ( nonvar(L) -> occs(L, X, Os) ; ( nonvar(Os) -> check(Os, X), glist(Os, X, L) ; v_occs(L, X, Os) ) ). 

When visiting the earth, the 2nd argument has three cases when the list is not empty: if its head and X above are rude and unified, X is at the beginning of the resulting list of entries, and there is no other alternative; otherwise, there are two alternatives: X differs from or combines with the head:

 occs([],_,[]). occs([X|R], Y, ROs) :- ( X==Y -> ROs=[X|Rr] ; foccs(X, Y, ROs, Rr) ), occs(R, Y, Rr). foccs(X, Y, ROs, ROs) :- dif(X, Y). foccs(X, X, [X|ROs], ROs). 

Testing the main argument is to make sure that all its members are combined with X In principle, this check can be performed using glist/3 , but in this way unused selection points are avoided.

 check([], _). check([X|R], X) :- check(R, X). 

A visit to the main 3rd argument with a free 2nd argument should end by adding variables other than X to the generated list. At each stage of the recursion, there are two alternatives: the current chapter of the generated list is the current heading of the visited list, which must be unified with X or is a free variable other than X This is a theoretical description, because in fact there are an infinite number of solutions, and the 3rd sentence will never be reached when the head of the list is variable. Therefore, the third sentence below is to avoid unacceptable points of choice.

 glist([], X, L) :- gdlist(L,X). glist([X|R], X, [X|Rr]) :- glist(R, X, Rr). %% glist([X|R], Y, [Y|Rr]) :- dif(X, Y), glist([X|R], Y, Rr). gdlist([], _). gdlist([Y|R], X) :- dif(X, Y), gdlist(R, X). 

Finally, the case where all arguments are free is considered in the same way as the previous case, and has a similar problem that some decision templates are not created in practice:

 v_occs([], _, []). v_occs([X|R], X, [X|ROs]) :- v_occs(R, X, ROs). %% v_occs([X|R], Y, ROs) :- dif(Y, X), v_occs(R, Y, ROs). % never used 

Test examples

 ?- occurrences(1,[E1,1,2,1,E2],Fs). Fs = [1,1], dif(E1,1), dif(E2,1) ? ; E2 = 1, Fs = [1,1,1], dif(E1,1) ? ; E1 = 1, Fs = [1,1,1], dif(E2,1) ? ; E1 = E2 = 1, Fs = [1,1,1,1] ? ; no ?- occurrences(1,L,[1,2]). no ?- occurrences(1,L,[1,E,1]). E = 1, L = [1,1,1] ? ; E = 1, L = [1,1,1,_A], dif(1,_A) ? ; E = 1, L = [1,1,1,_A,_B], dif(1,_A), dif(1,_B) ? ; ...