Prolog Programming for AI - Chapter 5 Notes and Exercises (5.1 ~ 5.2)

Preventing backtracking

Prolog will automatically backtrack if this is necessary for satisfying a goal.

Now, consider a double-step function. The relation between X and Y can be specified by three rules:

Rule 1: if X < 3 then Y = 0

Rule 2: if 3 <= X and X < 6 then Y = 2

Rule 3: if 6 <= X then Y = 3

This can be written in Prolog as a binary relation f(X, Y) as follows:

1
2
3

f(X, 0) :- X < 3.         % Rule 1
f(X, 2) : 3 =< X, X < 6.  % Rule 2
f(X, 3) : 6 =< X.         % Rule 3

This program assumes that before f(X, Y) is executed X is already instantiated to a number as this is required by the comparison operators.

Experiment 1

What if…

1	?- f(1, Y), 2 < Y.

When executing the first goal, f(1, Y), Y becomes instantiated to 0. So the second goal becomes *2 < 0 which fails, and so does the whole goal list. This is straightforward, but before admitting that the goal list is not satisfiable through backtracking.

f(1, Y), 2 < Y.
-> rule 1 1 < 3, 2 < 0 -> 2 < 0 (no) (backtracking)
-> rule 2 3 <= 1, 1 < 6, 2 < 2 (no) (backtracking)
-> rule 3 6 <= 1, 2 < 4 (no) (backtracking)

Now, our program can be rewritten with cut as follows:

1
2
3

f(X, 0) :- X < 3, !.
f(X, 2) :- 3 =< X, X < 6, !.
f(X, 3) :- 6 =< X.

If we now ask

1	?- f(1, Y), 2 < Y.

Prolog will produce the same left-hand branch. This branch will fail at the goal 2 < 0. Now Prolog will try to backtrack, but not beyond the point marked ! in the program. The alternative braches that correspond to ‘rule 2’ and ‘rule 3’ will not be generated.

Experiment 2

Suppose we ask:

1 2	?- f(7, Y). Y = 4

All three rules were tried before the answer was obtained. This produced the following sequence of goals:

Try rule 1: 7 < 3 fails, backtrack and try rule 2 (cut was not reached)

Try rule 2: 3 <= 7 succeeds, but then 7 < 6 fails, backtrack and try rule 3 (cut was not reached)

Try rule 3: 6 <= 7 succeeds

This trace reveals another source of inefficiency. Because…

First it is established that X < 3 is not true.

The next goal is bound to succeed as it is the negation of the first.

Therefore the second test is redundant and the corresponding goal can be ommited.

The same is true about the goal 6=< X in rule 3. This leads to the following, more economical formulation of the three rules:

if X < 3 then Y = 0,

otherwise if X < 6 then Y = 2,

Otherwise Y = 4.

Now, our program can be written as follows:

1
2
3

f(X, 0) :-  X < 3, !.
f(X, 2) :- X < 6, !.
f(X, 4).

We can not remove the cuts. If we remove the cuts, this may produce multiple solutions some of which are not correct.

What is the meaning of the cut mechanism?

A more precise meaning is as follows:

Let us call the parent goal the goal that matched the head of the clause containing the cut. When the cut is encountered as a goal it succeeds immediately, but it commits the system to all choices made between the time the parent goal was invoked and the time the cut was encountered. All the remaining alternatives between the parent goal and the cut are discarded.

To clarify this definition consider a clause of the form:

1	H :- B1, B2, ..., Bm, !, ..., Bn.

Let us assume that this clause was invoked by a goal G that matched H. Then G is the parent goal. At the moment that the cut is encountered, the system has already found some solution of the goals B1, …, Bm. When the cut is executed, this (current) solution of B1, …, Bm becomes frozen and all possible remaining alternatives are discarded. Also, the goal G now becomes committed to this clause: any attempt to match G with the head of some other clause is precluded.

Examples using cut

Computing maximum

1 2	max(X, Y, X) :- X >= Y, !. max(X, Y, Y).

These two rules are mutually exclusive. If the first one succeeds then the second one will fail. If the first one fails then the second must succeed. Therefore a more economical formulation, with otherwise , is possible: If X >= Y then Max = X, otherwise Max = Y.

Single-solution membership

1 2	member(X, [X \| L]) :- !. member(X, [Y \| L]) :- member(X, L).

Adding an element to a list without duplication

1
2
3

add(X, L, L) :-
    member(X, L), !.
add(X, L, [X, L]).

Classification into categories

Assume we have a database of results of tennis games played by members of a club. The results are in the program represented as facts like:

1
2
3

beat(tom, jim).
beat(ann, tom).
beat(pat, jim).

We want to define a relation

1	class(Player, Category)

that ranks the players into categories.

We have just three categories:

winner: every player who won all his or her games is a winner

fighter: any player that won some games and lost some

sportsman: any player who lost all his or her games

It is easy to specify the rule for a fighter:

X is a fighter if

there is some Y such that X beat Y and

there is some Z such that Z beat X.
Now a rule for a winner:

X is a winner if

X beat some Y and

X was not beaten by anybody.

This formulation contains not which cannot be directly expressed with our present Prolog facilities. The same problem occurs with sportsman.

The problem can be circumvented by combining the definition of winner with that of fighter, and using the otherwise connective. Such a formulation is:

If X beat somebody and X was beaten by somebody

then X is a fighter

otherwise if X beat somebody

then X is a winner

otherwise if X got beaten by somebody

then X is a sportman.

This mutual exclusion of the three alternative categories is indicated by the cuts:
1
2
3
4
5
6
7
8
9
class(X, fighter) :-
beat(X, _),
beat(_, X),
!.
class(X, winner) :-
beat(X, _),
!.
class(X, sportman) :-
beat(_, X).

Exercises

Let a program be:

1
2
3

p(1).
p(2) :- !.
p(3).

write all Prolog’s answers to the following questions:

(a)

1
2
3

?- p(X).
X = 1;
X = 2.

(b)

?- p(X), p(Y).
X = 1, Y = 1;
X = 1, Y = 2;
X = 2, Y = 1;
X = 2, Y = 2.

(c)

1
2
3

?- p(X), !, p(Y).
X = 1, Y = 1;
X = 1, Y = 2.

The following relation classifies numbers into three classes: positive, zero and negative:

1
2
3

class(Number, positive) :- Number > 0.
class(0, zero).
class(Number, negative) :- Number < 0.

Define this procedure in a more efficient way using cuts.

1
2
3

class(Number, positive) :- Number > 0, !.
class(Number, negative) :- Number < 0, !.
class(0, zero).

Define the procedure split(Numbers, Positives, Negatives) which splits a list of numbers into two lists: positive ones (including zero) and negative ones. For example, split([3, -1, 0, 5, -2], [3, 0, 5], [-1, -2])

Propose two versions: one with a cut and one without.
1
2
3
4
5
6
7
split([], [], []).
split([X|L], [X|L1], L2) :-
X >= 0,
!,
split(L, L1, L2).
split([X|L], L1, [X|L2]) :-
split(L, L1, L2).