Advanced · Lesson 40 of 43

Solving goals as terms

call, once and not, building goals with univ, findall, filter and the disjunction operator.

Solving goals

The basic predicates:

predicate	meaning
`call(+G)`	solves the goal
`once(+G)`	solves the goal with at most one solution
`not(+G)`	solves the goal and gives the opposite result, without binding
`true`	always succeeds
`fail`	always fails

Note that G above is actually a term, with all the possible syntax: if G is (G1, ..., Gn) it is handled as a resolvent. An example application: higher-order predicates, achieved by passing a predicate name.

?- G = member(X, [a, b]), call(G)

?- G = (member(X, [1, 2, 3]), X > 1), once(G)

?- not(member(z, [a, b]))

?- not(member(X, [a, b]))

Notice that not(member(X, [a, b])) fails: not/1 succeeds only if the goal has no solution, and it never binds variables.

map/3 with =.. and once/1

File map.pl. A higher-order predicate: map(+L, +P, LO) applies the predicate named P to every element. The goal is built with =.. and solved with once:

% map(+L, +P, LO)
map([], _, []).
map([H|T], P, [H2|T2]) :-
    G =.. [P, H, H2], once(G), map(T, P, T2).

inc(N, N2) :- N2 is N+1.

?- map([10, 20, 30], inc, L)

G =.. [P, H, H2] turns the name inc and the two arguments into the goal inc(10, H2); once(G) solves it. The same predicate can also be written with call/N:

map2([], _, []).
map2([H|T], P, [H2|T2]) :-
    once(call(P, H, H2)), map2(T, P, T2).

?- map2([10, 20, 30], inc, L)

Gathering solutions in lists: findall/3

File findall-filter.pl. findall(+Res, +Goal, -List) solves the goal many times and gathers the results in a list. (bagof and setof are variations, less used.) It often simplifies the definition of certain algorithms, and sometimes you need to get all results upfront, to have a broad view on them.

?- findall([X, Y], (member(X, [1, 2, 3]), member(Y, [1, 2, 3])), L)

Note the use of X and P in the next predicate as a sort of lambda: X is the variable that the goal P talks about.

% filter(+L, X, P, LO)
filter(L, X, P, LO) :- findall(X, (member(X, L), once(P)), LO).

?- filter([10, 21, 30, 40, 50], X, X > 25, LO)

?- filter([a, 1, b, 2], X, integer(X), LO)

The operator ";"

File disjunction.pl. Disjunction of two goals: at any point of a rule's body, you can indicate a disjunction between two goals (or resolvents):

H :- G1, G2, ..., Gk, (G ; G'), G1', ..., Gk'

Informal meaning: "either G or G' (or both)" should be solvable. The "formal" semantics: extract two new clauses C(X1,..,Xn) :- G and C(X1,..,Xn) :- G', where X1,..,Xn are all the variables used in G and G', and replace (G ; G') with C(X1,..,Xn). Hence note that ; may introduce a branch.

neighbour(X, Y1, X, Y2) :- Y1 is Y2+1 ; Y1 is Y2-1.
neighbour(X1, Y, X2, Y) :- X1 is X2+1 ; X1 is X2-1.

?- neighbour(X, Y, 5, 5)

Each clause body is a disjunction of two arithmetic goals, so each clause yields two answers, four in total: the neighbours of the cell (5, 5) on the four sides.

Exercise: Apply a named predicate to a pair

Write apply_twice(P, X, Z) where P is the name of a predicate of arity 2 (like inc, given). It must apply P to X and then apply P again to the result: apply_twice(inc, 1, Z) gives Z = 3. Build the goals with =...