Logic and Control in Prolog

CMPT 383 Lecture Notes
Robert D. Cameron
March 15-17, 2000

Declarative and Procedural Interpretations

PROLOG clauses can be interpreted on two levels:

Declarative:

logic only.

The clause is read as if all the arguments are given and we simply have to determine whether a call on the predicate is true by virtue of this clause.
Allows the correctness of a clause to be verified without considering its efficiency.

Procedural:

logic and control.

The clause is read in a sequential fashion to see how a goal is satisfied.
This requires knowledge of Prolog's left-to-right, depth-first theorem proving strategy. (N.B., this is Prolog-specific; other logic programming systems could potentially use different strategies.)
Reading of the clause depends on which arguments to the predicate are given (inputs) and which are variable (outputs).
The efficiency of how a goal is satisfied becomes apparent.

Predicates are Multipurpose

Prolog predicates can be used in many ways depending on which arguments are given and which are variable. For example, consider the predicate append(A,B,AB) which is true if AB is the list resulting from appending lists A and B together.

append([], B, B).
append([A1 | MoreAs], B, [A1 | X]) :-
  append(MoreAs, B, X).

This can be used in eight different ways.

Verifying that two lists append to be a third list.

| ?- append([a, b], [1, [e]], [a, b, 1, [e]]).

yes

Computing the result of appending two lists.

| ?- append([a, b], [1, [e]], X).

X = [a,b,1,[e]]

Determining which list appended to a given one yields a third list.
```
| ?- append([a, b], X, [a, b, 1, [e]]).

X = [1,[e]] 
```
Determining the list to which a given one msut be appended to yield a third list.
```
| ?- append(X, [1, [e]], [a, b, 1, [e]]).
X = [a,b] 
```

Determining which pairs of list can be appended to yield a third list.

| ?- append(X, Y, [a, b, 1, [e]]).
X = []
Y = [a,b,1,[e]] ? ;

X = [a]
Y = [b,1,[e]] ? ;

X = [a,b]
Y = [1,[e]] ? ;

X = [a,b,1]
Y = [[e]] ? ;

X = [a,b,1,[e]]
Y = [] ? ;

no

Determining lists which can be appended to a given one and what the result would be.
```
| ?- append([a, b], X, Y).
Y = [a,b|X]
```

Determining a list to which a given one can be appended and what the result would be.

| ?- append(X, [1,[e]], Y).
X = []
Y = [1,[e]] ? ;

X = [_A]
Y = [_A,1,[e]] ? ;

X = [_A,_B]
Y = [_A,_B,1,[e]]

Determining three lists such that the third is the result of appending the first two.

| ?- append(X, Y, Z).
X = [],
Z = Y ? ;

X = [_A],
Z = [_A|Y] ? ;

X = [_A,_B],
Z = [_A,_B|Y] ? ;

X = [_A,_B,_C],
Z = [_A,_B,_C|Y]

Arithmetic in Pure Logic: Successor Notation

Let zero denote 0.
Let succ(N) denote $N + 1$.

sum(M, zero, M).
sum(M, succ(N), succ(S)) :- sum(M, N, S).

| ?- sum(succ(succ(zero)), succ(succ(succ(zero))), N).
N = succ(succ(succ(succ(succ(zero)))))

product(M, zero, zero).
product(M, succ(N), P) :-
  sum(P1, M, P), product(M, N, P1).

| ?- product(succ(succ(zero)), succ(succ(succ(zero))), N).
N = succ(succ(succ(succ(succ(succ(zero)))))) ? ;

Neat, multipurpose, very inefficient.

sum(A, 7, 14): Solve A+7=14, i.e., subtract.
product(A, 2, 4): Solve A*2=4, i.e., divide.
sum(A, B, 4): Solve A+B = 4. Can generate all possibilities.
product(A, B, 4): Solve A*B = 4. Can generate all possibilities.

Arithmetic in Prolog

A built-in expression evaluator used with the is predicate.

sqr(X, Z) :- Z is X * X.

| ?- sqr(3, Y).
Y = 9

Limitation: All variables on RHS of is must have values.

?- sqr(Z, 49).


{INSTANTIATION ERROR: _36 is _34*_34 - arg 2}

Controlling the Search: The Cut

! is a special PROLOG facility called the cut.

Cuts may be inserted anywhere within a clause to prevent backtracking to previous subgoals, e.g,

p(X) :- b(X), c(X), !, d(X), e(X).

Suppose that this clause has been invoked with a goal matching p(X) and the subgoals b(X) and c(X) have been satisfied. On encountering the cut:

The cut will succeed and PROLOG will try to satisfy subgoals d(X) and e(X).
If these subgoals do succeed then the entire goal succeeds.
If d(X) and e(X) do not succeed and backtracking returns to the cut, then the backtracking process will immediately terminate and the goal which matched p(X) fails.

In essence, the cut freezes the decisions made in satisfying the parent goal:

The choice of this clause, and
The ways that b(X) and c(X) are first satisfied.

That is, there will be no backtracking to resatisfy b(X) or c(X) and no attempt to use any other clause to satisfy p(X).

Avoiding Useless Searches

The cut can be used to mean "succeed with this; there aren't any other alternatives." For example, the member function:

member(X,[X|Y]).

member(X,[Y|Z]) :- member(X, Z).

Consider the goal

X is 4 + 1, member(X, [5, 9, 24, 17, 5, 2]), X < 4.

member(5, [5, 9, 24, ..., 5, 2]) succeeds, but then 5 < 4 fails.
Backtracking now tries with member(5, [9, 24, ..., 5, 2]), working down the list.
Eventually, we get member(5, [5, 2]) which succeeds again, but 5 < 4 still fails.
Finally, we get to member(5, []), which fails because there is no appropriate clause.

The repeated backtracking can be avoided with the cut:

member(X,[X|Y]) :- !.

member(X,[Y|Z]) :- member(X, Z).

Negation in PROLOG

PROLOG works under the Closed World Assumption:

everything that is true is derivable from its facts and rules.
if a goal cannot be proven, it is assumed to be false (negation by failure).

This can cause problems if the fact and rule database is incomplete, especially when trying to define negative rules.

can_marry(X, Y) :- 
  X \== Y, nonsibling(X, Y), noncousin(X, Y).
nonsibling(X, Y) :- X == Y.
nonsibling(X, Y) :- 
  mother(M1, X), mother(M2, Y), M1 \== M2.
nonsibling(X, Y) :- 
  father(F1, X), father(F2, Y), F1 \== F2.

Now consider the queries:

| ?- sibling(albert,alice).
no
| ?- nonsibling(albert, alice).
no

The problem is that our database doesn't have information about the parents of albert and alice, so PROLOG can't prove that they are siblings and it can't that they aren't.

Negation Using `fail` and `not`

How can we force nonsibling(X, Y) to be the logical opposite of sibling(X, Y), i.e., so that it succeeds when sibling fails and vice versa?

The built-in fail predicate can be used to force failure. Thus we can use the cut-fail combination as follows.

nonsibling(X, Y) :- sibling(X, Y), !, fail.
nonsibling(X, Y).

In a call to nonsibling:

If sibling succeeds, the cut prevents backtracking and fail forces nonsibling to fail.
If sibling fails, then the next clause is taken which allows nonsibling to succeed immediately.

Cut-fail combinations cannot be read as normal logical statements; their semantics depends fundamentally on the PROLOG's execution order.

The cut-fail combination is so common that PROLOG provides a special not meta-predicate as a shorthand.

nonsibling(X, Y) :- not(sibling(X, Y)).

Keep in mind, however, that not is not logical negation, but means "failure to prove."