52 349 Logic Programming
Chapter 9 - Essentially Procedural Facilities
Previous Reading:
Using System Procedures
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.
Operators have already been briefly referred to in §.8.4
- They are not covered in these notes, other than to comment
- Prolog's pattern matching remains unaltered
- Precedence can be freely adjusted
- Essentially for human convenience
- See, for example, Clocksin & Mellish
A program manipulating the variable Shape for various geometric shapes
triangle(Base, Height)
|
square(Side)
|
circle(Radius)
|
might need to calculate areas.
This seems easy ... but the obvious code does not work!
- The problem is that Shape is not an atom and so cannot be a functor
- whence Area as we have it is essentially a predicate of a predicate, something not permitted in FOPL
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],
|
call(Goal).
|
'call' and '=..' give us the flexibility of variable goals
- but sometimes we want to ensure success or failure, for which we have the constant functors true and fail
- fail we consider shortly in conjunction with the cut, but note one use of the apparently redundant true, to bypass information which may be missing or which would otherwise fail on back-tacking ... for example
(write('something'); true), ...
repeat/0 is a nice oddity
- it always succeeds, but is non-deterministic, so that whenever it is reached on back tracking a new execution branch of the computational tree is explored
- for example (and for now simply reading the goal "!" as succeeding but preventing back tracking)
square:-
|
| repeat,
|
| read(X),
|
| (X = end,!;
|
| Y is X * X,
|
| write(Y),
|
| fail).
|
which contrasts with the earlier form of the square program in §8.3.2.
And what of retaining solutions?
- every time we back track we lose our previous collection of instantiations
- whereas we may need to assemble a full set of the valid possibilities
- bagof/3 meets this need.
bagof(Object, Goal, Object_list)
- fails if there is no Object satisfying Goal
- otherwise succeeds, with Object_list as a list of all the Objects satisfying Goal
- Object_list (when ultimately instantiated) can include multiple occurrences of an object, corresponding to different solution paths leading to the same instantiations.
For example
index(People_list):-
|
| bagof(Person, lived(Person, Born, Died), People_list).
|
|
|
index([]).
|
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.
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)
then pass the first test
and fail
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
- from the earliest days of the language, in Marseilles
- it is a beneficial addition ...
- ... but also a potentially dangerous one!
The cut is a pseudo-goal
- remember how in §6.1.1 we noted ! accepted as an atom?
- and so as a term?
- ... so that it could be a functor of arity zero
- which immediately succeeds, when forward tracking
- but which on back tracking
- fails itself
- cause the parent goal to fail
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
|
no
|
Clause (3) will match the head of (1b)
then pass the first test
pass the cut, thus removing the markers which would normally allow access to clause (2a)
and fail
clause (2a) not now being available, the whole procedure fails
... just what we wanted!
The cut has the effect of "committing the system":
- it removes the search markers from the parent goal and from sub-goals between the cut and the clause head
- what it is doing, is pruning the computational tree (if in doubt, re-study the material of §5.1)
- by eliminating those branches the programmer knows must lead to failure
- thus improving efficiency and easing correctness
Great! Except that, as we might have guessed, there is a price to pay, this time in software engineering terms.
The cut
- always changes the procedural semantics of a program
- may also change the declarative semantics
- Thus it increases the chance of error (as well as making the code harder to read)
- and, because it reduces generality, it frequently leads to a loss of
re-usability of code
Van Emden (an early Prolog worker) introduced the idea of green cuts and red cuts
- with the aim of encouraging green use and of discouraging the red
- Green cuts are good
- all they do is aid efficiency, by pruning unwanted search paths
- Red cuts are bad
- their alteration of the procedural semantics also serves to separate the declarative meaning of a program from its "obviously intended" meaning
- Note that both variations are legal!
- Note also that on occasions experienced Prolog programmers may deliberately use a red cut to force a separation between true and apparent declarative meaning ... but for your part leave such endeavours well alone!
Use the cut
- but use it with care
- stick to the green version
- and never try to cure a faulty program by filling it with cuts!
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
- forward tracking occurs as usual
- but, if C fails, then on back tracking the cut in f makes it fail
- whence other solutions can only emerge if B can be resatisfied
- after which forward tracking through f takes place as usual
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.
|
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
|
- which we can code using our mutual exclusion ideas as
good(X) :- late(X), !, fail.
|
good(X).
|
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
- excludes respectively lateness or spiders
- and excludes also use of the second clause in those cases
- but allows the second clause (used only when lateness or spider fails) to give the required generality.
Extending this idea further brings us to the unary predicate "not":
not(P):-
|
| P, !, fail;
|
| true.
| | |
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
- What is the likely response to the following, asked of an empty fact base?
?- not students(third_year).
- Surely, no? Or perhaps that should be, yes?
- Go and start Prolog and try it!
- The difficulty is that
students(third_year) is failing in the first clause, before we reach the cut ... which causes not to succeed, against its second clause.
- whereas all we should be able to deduce is that there is insufficient data for a correct response
- we are back in the "closed world" of logical models
Normally, we do not expect failure to prove P to imply (as here) the falseness of P
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.
- for example, we can at least in principle use member/2 as a list generator
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?
Which, since 2 is not the maximum of the pair {2,5}, is to say the least disappointing.
- Our program only works when used in its design context
- that is, when the third parameter is not instantiated
- Used without a guard on the previous instantiation of its variables, it is a false logic program.
There are three morals to be drawn
- firstly, the correct solution is
max(X, Y, X):-
|
|
| X > Y, !.
|
max(X, Y, Y):-
|
|
| X <= Y, !.
|
or, closer to our original but inelegant,
max(X, Y, Max):-
|
|
| (X > Y, !, Max = X);
|
|
| Max = Y.
|
- secondly, and more generally, excising conditions is likely to be unwise
- thirdly, since Prolog cannot enforce "correct" (that is, as intended) use of code, then programmers must take steps to do so.
To meet the last point, a commenting convention is adopted to facilitate re-use of code
- against each procedure is a comment about the intended pre-instantiation of the variables
- for example
% max(+, +, -) where
- variables intended to be instantiated before use are marked +
- intended uninstantiated ones are marked -
- don't care ones are marked ?