3.7. Second-order predicates#
Suppose we need a program to determine, given two lists of persons of equal length, whether a person in the first list is the parent of the corresponding person in the second list. The following program will do the job:
parents(,). parents([P|Ps],[C|Cs]):- parent(P,C), parents(Ps,Cs).
We can generalise this program by including the relation which must hold between corresponding elements of the two lists as a parameter:
rel(R,,). rel(R,[X|Xs],[Y|Ys]):- R(X,Y), rel(R,Xs,Ys).
A term like
R(X,Y) is allowed at the position of an atom in the body of a clause, as long as it is correctly instantiated at the time it is called.
Some Prolog interpreters don’t allow this, in which case you must explicitly construct the literal by means of the built-in predicate ‘
=..’ (sometimes called univ). It is a fully declarative predicate, which can both be used to construct a term from a list of arguments preceded by a functor, or to decompose a term into its constituents:
?-Term =.. [parent,X,peter]. Term = parent(X,peter) ?-parent(maria,Y) =.. List. List = [parent,maria,Y]
=..’ is declared as an infix operator in Prolog.
rel is called a second-order predicate, because it takes a (first-order) predicate as an argument1. We can now define the
parents predicate as
Suppose now you have the following facts in your program, and you want to collect all the children of a particular parent in a list:
parent(john,peter). parent(john,paul). parent(john,mary). parent(mick,davy). parent(mick,dee). parent(mick,dozy).
Of course, it is easy to generate all the children upon backtracking; the problem is to collect them in a global list. To this end, Prolog provides the second-order predicates
setof. For instance, we could use the following program and query:
?-children(john,Children). Children = [peter,paul,mary]
In general, the query
generates all the possible solutions of the query
?-Goal, recording the substitutions for
X for each of these solutions in the list
Goal must be instantiated to a term representing a Prolog goal).
Global datastructures in Prolog#
Since Prolog variables do not have a scope outside the clause in which they occur (Section 2.2), pure Prolog does not provide any support for global datastructures. However, Prolog provides access to its internal database where it stores the program clauses, by means of the built-in predicates
retract. The query
?-assert(Clause) results in the addition of
Clause (which must be instantiated to a valid Prolog clause) to your program; the query
?-retract(Clause) removes the first clause which unifies with
Clause from your program. These predicates are fairly low-level, and should be used with care.
bagof predicate acts similarly. However, its behaviour is different when the goal contains free variables. Consider the query
in which the variable
P is unbound. This query has two possible interpretations: ‘find a parent and a list of his children’, and ‘find the list of children that have a parent’. In the first case, we get a possible value for
P and a list of
P’s children, which means that there are two solutions:
?-bagof(C,parent(P,C),L). C = _951 P = john L = [peter,paul,mary]; C = _951 P = mick L = [davy,dee,dozy]
In the second case, the goal to prove is ‘there exists a
P such that
parent(P,C) is true’, which means that the variable
P is existentially quantified. This is signalled by prefixing the goal with
?-bagof(C,P^parent(P,C),L). C = _957 P = _958 L = [peter,paul,mary,davy,dee,dozy]
?-findall(C,parent(P,C),L) (without existential quantification) can only generate this second solution.
Finally, Prolog provides the predicate
setof, which acts just like
bagof, except that the resulting list is sorted and does not contain duplicates. Thus,
setof is slightly less efficient than
bagof, and the latter is preferred in cases where the list of solutions is known not to contain duplicates.