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.
The predicate rel is called a second-order predicate, because it takes a (first-order) predicate as an argument[1]. We can now define the parents predicate as
parents(Ps,Cs):-rel(parent,Ps,Cs).
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 findall, bagof, and setof. For instance, we could use the following program and query:
children(Parent,Children):-
findall(C,parent(Parent,C),Children).
?-children(john,Children).
Children = [peter,paul,mary]
In general, the query
?-findall(X,Goal,ListofX).
generates all the possible solutions of the query ?-Goal, recording the substitutions for X for each of these solutions in the list ListofX (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 assert and 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.
The bagof predicate acts similarly. However, its behaviour is different when the goal contains free variables. Consider the query
?-bagof(C,parent(P,C),L).
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 P^:
?-bagof(C,P^parent(P,C),L).
C = _957
P = _958
L = [peter,paul,mary,davy,dee,dozy]
The query
?-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.