52 349 Logic Programming

Chapter 9 - Essentially Procedural Facilities

§9.0 Introduction §9.4.1 Mutual Exclusion
§9.1 Operators §9.4.2 Cut-Fail Combination
§9.2 Predicates to Lists: =.. §9.4.3 Negation
§9.3 Flow of Control §9.5 Reversed Use of Procedures
§9.4 The Cut

Previous Reading: Using System Procedures

§9.0 Introduction

In this chapter we consider several more sophisticated possibilities - and especially the cut - which serve to add flexibility to our programs ... but at the expense of straining the ease of understanding or of re-use.

§9.1 Operators

Operators have already been briefly referred to in §.8.4

§9.2 The Functor =..

A program manipulating the variable Shape for various geometric shapes

triangle(Base, Height)
might need to calculate areas.

This seems easy ... but the obvious code does not work!

False code for areas

The system predicate =.. can help us:

Term =.. List is true if List contains the principal functor of Term, followed by the arguments of Term, in order. Thus

?- f(a, b) =.. L.
L = [f, a, b]

Like functor/3 and arg/3 of §8.4, =.. allows us to manipulate compound terms.

Let's try area/2 again, using =..

area(Shape, Value):-
Shape =.. [Variety |Parameters],
Value is ...

Note that for realistic use, we will also need to give each instance of a shape some identifier of its own.

What we have done is, in effect, to move into an object oriented world!

=.. also gets us round the problem of wanting a variable as a goal, by use of call/1:

% Preceding code.
Goal =.. [Functor |Argument_list],

§9.3 Flow of Control & Multiple Solutions

'call' and '=..' give us the flexibility of variable goals

(write('something'); true), ...

repeat/0 is a nice oddity

(X = end,!;
Y is X * X,

And what of retaining solutions?

bagof(Object, Goal, Object_list)

For example

bagof(Person, lived(Person, Born, Died), People_list).
where the second clause guarantees success even if lived/3 never succeeds.

setof/3 is very similar to bagof, but produces an ordered list without any duplicates

Sometimes we also have findall/3, which is the same as bagof except that if Goal has no solutions 'findall' succeeds and instantiates an empty Object_list.

§9.4 The Cut

Consider two clauses for some functor f/2:-

f(x,y) :- x > y, ... % 1
f(x,y) :- y > x, ... % 2

Since Prolog works top-down, it would appear that we can obviously save time and space, by simplifying it to:-

f(x,y) :- x > y, ... % 1 [unaltered]
f(x,y) :- ... % 2a

Can we? Not knowing "..."? Consider:

f(x,y) :- x > y, fail,... % 1a
f(x,y) :- ... % 2a [unaltered]
?- f(5,1). % 3

Clause (3) will match the head of (1a)

Whence (3) will match the head of (2a)

If we want freedom to simplify, we must control undesired backtracking!

The cut (!) was introduced for this very purpose of control of backtracking

The cut is a pseudo-goal

Consider its use in the previous procedure for f/2:-

f(x,y) :- x > y, !, fail,... % 1b
f(x,y) :- ... % 2a [unaltered]
?- f(5,1). % 3

Clause (3) will match the head of (1b)

The cut has the effect of "committing the system":

Great! Except that, as we might have guessed, there is a price to pay, this time in software engineering terms.

The cut

Van Emden (an early Prolog worker) introduced the idea of green cuts and red cuts

Use the cut

Before considering the principal uses of the cut, note a point of detail which often confuses (even though it is wholly covered by and consistent with the explanations given):-

A(X, Y):- B, f(X, Y), C. % Where f/2 is in its last given version

§9.4.1 Mutual Exclusion

Mutual exclusion - "otherwise" - clauses can be coded very precisely (and efficiently) using the cut. Thus

A is true if B is true
otherwise if C is true
otherwise if D is true

can beneficially be coded as

A:- B, !.
A:- C, !.
A:- D.

Why "beneficially"? What does use of the cut give?

Usually, of course, there would be further goals between the cut and the clause end.

Question: do you ever want a cut (!) after D?
Answer: not for mutual exclusion; but you might on occasion wish
not to resatisfy D on backtracking from other procedures.

§9.4.2 Cut-Fail Combination

Frequently (especially in the context of lectures?) we face something like

X is good if X is not late.

(X is good) is false if X is late
otherwise (X is good) is true

good(X) :- late(X), !, fail.

Or, more complicatedly, we face something like

Judy likes all creatures except spiders.

(Judy likes X) is false if (X is a spider) is true
otherwise (Judy likes the creature X) is true

likes(judy,X):- spider(X), !, fail.
likes(judy,X):- creature(X).

The cut-fail combination here

§9.4.3 Negation

Extending this idea further brings us to the unary predicate "not":

P, !, fail;

In practice, "not" is usually defined as a built in prefix functor, or operator, enabling us to write simply

not P.

This idea has dangers of its own, reaching right back to our starting point of studying formal logic

Normally, we do not expect failure to prove P to imply (as here) the falseness of P

§9.5 Reversed Use of Procedures

It is both a strength of Prolog and a trap for the unwary that we can re-use code, back to front as it were, for other than its intended purpose.

As an example (involving use of the cut) let us develop code to determine the greater of the two integers X an Y.

Stage 1

max(X, Y, Max):-
X > Y, Max = X.
max(X, Y, Max):-
X <= Y, Max = Y.

Stage 2

The explicit unification of Max is ugly, so let's remove it:

max(X, Y, X):-
X > Y.
max(X, Y, Y):-
X <= Y.

Stage 3

The second test is, really, superfluous. We can remove it, apparently safely, by using the cut in a mutual exclusion context:

max(X, Y, X):-
X > Y, !.
max(X, Y, Y).

So far, so good.

But, having the procedure, how about using it as a test?

?- max(5, 2, 2).

Which, since 2 is not the maximum of the pair {2,5}, is to say the least disappointing.

There are three morals to be drawn

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

max(X, Y, Max):-
(X > Y, !, Max = X);
Max = Y.

To meet the last point, a commenting convention is adopted to facilitate re-use of code

© Paul Goldfinch 1997 Next Chapter Return to 52 349 Menu