(apx:a.2)= # A library of utility predicates # What follows is a small collection of predicates that are used by various programs throughout the book. ## Lists and sets ## We start with a couple of simple list predicates. ```Prolog % element(X,Ys) <- X is an element of the list Ys element(X,[X|Ys]). element(X,[Y|Ys]):- element(X,Ys). % append(Xs,Ys,Zs) <- list Zs is Xs followed by Ys append([],Ys,Ys). append([X|Xs],Ys,[X|Zs]):- append(Xs,Ys,Zs). % remove_one(X,Ys,Zs) <- Zs is list Ys minus % one occurrence of X remove_one(X,[X|Ys],Ys). remove_one(X,[Y|Ys],[Y|Zs]):- remove_one(X,Ys,Zs). ``` The difference between lists and sets is that the order of elements in a set is not important. Thus, a *subset* is different from a *sublist*. The predicate `proper_subset/2` works only if the first argument is a list without duplicates! ```Prolog % subset(Xs,Ys) <- every element of Xs occurs in Ys subset([],Ys). subset([X|Xs],Ys):- element(X,Ys), subset(Xs,Ys). % proper_subset(Xs,Ys) <- Xs is a subset of Ys, and Ys % has more elements than Xs proper_subset([],Ys):- Ys \= []. proper_subset([X|Xs],Ys):- remove_one(X,Ys,Ys1), proper_subset(Xs,Ys1). ``` The following three predicates use syntactic identity rather than unification, which is useful for lists containing variables. ```Prolog var_element(X,[Y|Ys]):- X == Y. % syntactic identity var_element(X,[Y|Ys]):- var_element(X,Ys). var_remove_one(X,[Y|Ys],Ys):- X == Y. % syntactic identity var_remove_one(X,[Y|Ys],[Y|Zs]):- var_remove_one(X,Ys,Zs). var_proper_subset([],Ys):- Ys \= []. var_proper_subset([X|Xs],Ys):- var_remove_one(X,Ys,Zs), var_proper_subset(Xs,Zs). ``` ## Conjunctions and disjunctions ## Conjunctions and disjunctions are recursive datastructures, just like lists. However, whereas a single-element list such `[1]` is a complex term `.(1,[])`, a single-element conjunction or disjunction is a simple term. Therefore, each of the following predicates needs an extra clause for the single-element case. Note that `true` is the empty conjunction, while `false` represents the empty disjunction. ```Prolog disj_element(X,X):- % single-element disjunction not X=false, not X=(One;TheOther). disj_element(X,(X;Ys)). disj_element(X,(Y;Ys)):- disj_element(X,Ys). conj_append(true,Ys,Ys). conj_append(X,Ys,(X,Ys)):- % single-element conjunction not X=true, not X=(One,TheOther). conj_append((X,Xs),Ys,(X,Zs)):- conj_append(Xs,Ys,Zs). disj_append(false,Ys,Ys). disj_append(X,Ys,(X;Ys)):- % single-element disjunction not X=false, not X=(One;TheOther). disj_append((X;Xs),Ys,(X;Zs)):- disj_append(Xs,Ys,Zs). conj_remove_one(X,X,true):- % single-element conjunction not X=true, not X=(One,TheOther). conj_remove_one(X,(X,Ys),Ys). conj_remove_one(X,(Y,Ys),(Y,Zs)):- conj_remove_one(X,Ys,Zs). ``` ## Preventing variables from getting instantiated ## Whenever Prolog reads a clause from its internal database, fresh copies of the variables in the clause are created. When a meta-interpreter uses an internal list of clauses, this is desirable as well. The predicate `copy_term/2` uses the internal database to create a fresh copy of any term. `copy_element/2` uses `copy_term/2` to create a fresh copy of an item in a list. ```Prolog % copy_term(Old,New) <- New is a copy of Old % with new variables copy_term(Old,New):- asserta('$copy'(Old)), retract('$copy'(New)),!. copy_term(Old,New):- % in case Old and New don't unify retract('$copy'(Old)), !,fail. % copy_element(X,L) <- X is an element of L % with new variables copy_element(X,Ys):- element(X1,Ys), copy_term(X1,X). ``` `try/1` is a meta-predicate which tests whether a goal succeeds, without returning an answer-substitution. This is achieved by taking advantage of the difference between negation as failure and logical negation. ```Prolog % try(Goal) <- Goal succeeds, but variables % don't get instantiated try(Goal):- not not Goal. ``` ## Various ## The remaining predicates speak for themselves. ```Prolog % variant of setof/3 which succeeds with the empty list % if no solutions can be found setof0(X,G,L):- setof(X,G,L),!. setof0(X,G,[]). % same_predicate(L1,L2) <- literals L1 and L2 have % the same predicate and arity same_predicate(L1,L2):- functor(L1,P,N), functor(L2,P,N). ```