Programming Without Problems III: Adding More Predicates

Aggregating

So far we have written five "unique" predicates: dleft_only/1, dright_only/1, dwalk/3, ddomain/2 and delems_dwalk/3. I will rename delems_dwalk/3 to something more descriptive: dreaches/3. It indicates that the result are the reachable elements. The name delems_dwalk came to be because it was a version of delems that used dwalk in its definition. The name delems might imply the result is all the elements in d, conflicting with ddomain. Hence, I decided to change it to dreaches/3. So, if dreaches(A,V,C) is true, we know there is a dwalk from A to C that avoids the elements in V, that is, A reaches B. I feel I biased its development with a left-to-right description. Thinking that A and C are given or at least A is given, but what about if C is given and A is unknown? This defines dreachedf where the f stands for from.

         dreachedf(B,Acc,E):-
         	dwalk(A,[A],B),
         	\+ member(A, Acc),
         	dreachedf(B,[A|Acc],E).
         dreachedf(B,E,E):-
         	forall(member(A,E),dwalk(A,[A],B)),
         	\+((dwalk(A,[A],B),
         	   \+member(A,E))).
      

When dreachedf(B,Acc,E) is true, E contains all elements for which there is a dwalk from them to B. The first part of the second clause makes sure that all elements in E reach B. The second part, checks no member is missing.

We can also easily create a list of all the d/2 facts in the database:

         dfacts(Acc,Df):-
         	d(A,B),
         	\+ member(d(A,B),Acc),
         	dfacts([d(A,B)|Acc],Df).
         dfacts(Df,Df):-
         	forall(member(d(A,B),Df),d(A,B)),
         	forall(d(A,B),member(d(A,B),Df)).
         
         dfacts(Df):-
         	dfacts([],Df).
      

Just as we defined ddomain/1 that unifies with all individual elements in d/2, we can define ddomain_left/2 and ddomain_right/2 and their respective /1 versions that unify with all the individual elements that appear on the left (right) of d/2 facts.

         ddomain_left(Acc,LD):-
         	d(A,_),
         	\+member(A,Acc),
         	ddomain_left([A|Acc],LD).
         ddomain_left(LD,LD):-
         	forall(member(B,LD),d(B,_)),
         	forall(d(B,_),member(B,LD)).
         
         ddomain_left(LD):-
         	ddomain_left([],LD).
         
         ddomain_right(Acc,RD):-
         	d(_,A),
         	\+member(A,Acc),
         	ddomain_right([A|Acc],RD).
         ddomain_right(RD,RD):-
         	forall(member(B,RD),d(_,B)),
         	forall(d(_,B),member(B,RD)).
         
         ddomain_right(RD):-
         	ddomain_right([],RD).
      

The exclusion list V of dwalk/3 excludes elements in the domain of d/2 from being considered in the search of the dwalk between A and C. We can also write a version that excludes facts instead of elements:

         dwalk_dexc(A,E,C):-
         	d(A,C),
         	\+ member(d(A,C),E)
         	;
         	d(A,B),
         	\+ member(d(A,B),E),
         	dwalk_dexc(B,[d(A,B)|E],C).
      

It turns out that dwalk_dexc/3 allows us to detect when a d/2 fact is redundant with respect to dwalks: a d(a,b) fact is redundant if there exists an a-b dwalk that does not contain d(a,b). Hence if dwalk_dexc(A,[d(A,C)],C) succeeds, d(A,C) is redundant. We can build a list of redundant facts, that is, facts that can be removed and their removal preserves dwalk connectivity:

         dredundant(Acc,Dr):-
         	d(A,B),
         	\+ member(d(A,B),Acc),
         	dwalk_dexc(A,[d(A,B)|Acc],B),
         	dredundant([d(A,B)|Acc],Dr).
         dredundant(Dr,Dr):-
         	forall(member(d(A,B),Dr),d(A,B)),
         	forall(member(d(A,B),Dr),dwalk_dexc(A,Dr,B)),
         	forall(d(A,B), (\+ member(d(A,B),Dr) ->
         			   \+ dwalk_dexc(A,[d(A,B)|Dr],B);true)).
         
         dredundant(Dr):-
         	dredundant([],Dr).
      

The -> predicate is Prolog's syntactic sugar for if-then-else. The first part of the second clause makes sure all elements in Dr are d/2 facts. The second part that the removal of Dr preserves connectivity. The third part checks Dr is complete; for each d/2 fact in the database that is not in Dr, its removal breaks the connectivity. Based on redundancy, we can define essential facts as those that are not redundant:

         rmember(Dr,D):-
         	member(D,Dr).
         dessential(De):-
         	dredundant([],Dr),
         	dfacts([],Df),
         	exclude(rmember(Dr),Df,De).
      

Finally we can ask about the underlying structure of d/2 facts, the most elemental might be if d/2 facts represent a function or a map (invertible function). To implement them we can make use of the derived dleft_degree/2, dright_degree/2 and ddegree/2 predicates.

         dfunction:-
         	ddomain_left([],LD),
         	forall(member(X,LD),dleft_degree(X,1)).
         
         dmap:-
         	dfunction,
         	ddomain_right([],RD),
         	forall(member(Y,RD),dright_degree(Y,1)).
      

The cut

We implemented dfunction/0 quite straightforward. However, if we execute this simple program with the database: d(a,b). d(b,c). d(c,a). d(c,f). d(f,b). d(e,f). d(e,a). d(b,e). d(f,i).d(i,c). d(a,i). d(a,h). d(h,c). d(f,h). it would take a long time to finish. Why? Because of backtrack. Once the first dleft_degree/2 fails, the forall/2 fails and backtrack falls back to ddomain_left/1 which is defined in terms of ddomain_left/2. While ddomain_left/2 is functionally correct, that is the second argument always will unify with all members of the domain that appear on the left-hand side of a d/2 fact, it has the performance drawback that when backtrack is triggered it calculates a permutation of the elements. This fact was evident from some of the proofs. It is clear we need to solve this limitation if we plan to use whatever we create with databases containing more than a handful facts.

In the previous entry of Programming Without Problems, I briefly mentioned a possible fix using the cut operator (!). The cut, prunes the search tree to prevent backtracking. It must be used with care, because if a cut prevents Prolog from proving something, we are in trouble. Clearly, to comply with our specifications we should not use any cut inside ddomain_left/2 because the specification ensures that V is a prefix of LD so if we use a cut, we might prevent Prolog from finding the correct permutation. ddomain_left/1 give us more room to maneuver, it sounds tempting to define it as: ddomain_left([],LD),!. That is, once ddomain_left([],LD) succeeds we don't backtrack. This semantics is focused on finding a solution rather than find a solution and be prepare to find more . However, there is nothing in the predicate's definition (at the language level) that makes this evident. If we adopt this solution we would be relying solely on a convention. However, we have an advantage as the specification would laid out this fact, because ddomain_left/1 is specified by its code.

Most predicates we have implemented so far are similar in its structure to ddomain_left/2. First a calculation is made, and then it is checked. This seems redundant, why check something that we know (proved) to be correct? First we must recall this was the result of hardening our specifications, we not only require to calculate a solution but also to be able to verify any solution. Second, we can see this as a weird form of test driven development. If we change the first clause of ddomain_left/2 to anything else, the second clause will make sure the first calculates a correct solution, more over since both clauses can be interchanged, the check can be performed during the construction of the solution. These checks come with a cost. If we swap the order of ddomain_left/2 predicates, we would perform a quadratic number of checks (on the number of elements in the solution).

We will discuss more about performance later, for the moment, we summarize all predicates and their specifications:

Copyright Alfredo Cruz-Carlon, 2025