Previous | Table of Contents | Next |
6.3.1.1. Computing with Negations
Prolog computes negated literals by the negation as failure method. For instance, \+ member([b,c], a) is computed by first computing member([b,c], a); because that query fails (is not evaluated as true), the negated literal succeeds (is evaluated as true). \+ member([b,c], b) is similarly computed by first computing member([b,c], b), but here, because that query succeeds, the negated literal fails.
Negation is also useful in predicate definitions. Negations can appear in queries and in predicate bodies, but not in predicate heads; the head always has to be a simple atom. Consider the following (faulty) code for the delete predicate:
% delete(L1, X, L2): L2 is the result of deleting all % occurrences of X from L1. delete([X|Tail1], X, L2) :- delete(Tail1, X, L2). delete([Y|Tail1], X, [Y|L2]) :- delete(Tail1, X, L2).
Why is this code faulty? The first solution that this code returns is correct; for instance, delete([a,b,c], b, L) returns L = [a,c]. But if we then ask for more solutions, it returns L = [a,b,c]. The problem is that although in the second clause, we named X and Y differently, in fact Prolog is happy to use that clause on backtracking even when the head of the first argument is the same as the second argument. What we really need is for the second clause to be
delete([Y|Tail1], X, [Y|L2]) :- \+ X = Y, delete(Tail1, X, L2).
This guarantees that the second clause is used only when X and Y are distinct.
As another example, Listing 6.2 contains some code involving negation that might be found in a game-playing program. The predicate best_move_for is intended to compute the best move for player P given the current state of the game. Note that each negated condition is the negation of some condition that actually appeared in an earlier clause. This is a common pattern, and we will soon see how it can be done more efficiently.
Listing 6.2. Code from a game program that involves negation.
% best_move_for(P, State, Move): The best move for player P, % given the state of the game in State, is Move. best_move_for(P, State, Move) :- winning_move_for(P, State, Move). best_move_for(P, State, Move) :- \+ winning_move_for(P, State, Some_move), drawing_move_for(P, State, Move). best_move_for(P, State, Move) :- \+ winning_move_for(P, State, Some_move), \+ drawing_move_for(P, State, Some_other_move), move_for(P, State, Move).
6.3.1.2. Negation and Unsoundness
One caution must be followed when using negation. Consider the query X=a, \+ X=b. It will succeed, as you might expect, with the substitution X=a. But now consider the query \+ X=b, X=a. The two queries are the same except that the order of the literals has been switched, but the second query fails! Prolog has succeeded in binding X to b in the computation of the first literal, so X=b succeeds and \+ X=b fails.
This is not in line with correct logical behavior; rather, it is a consequence of the negation as failure strategy, as implemented in most Prologs. However, there are ways of ensuring that the negations you use are logically sound. The rule of thumb is avoid situations where you have an uninstantiated variable inside a negation that also appears outside the negation. Thus the previous delete predicate is sound if the first two arguments (the list and the element to be deleted) are instantiated whenever it is used. Similarly, the best_move_for predicate is sound whenever the P and State arguments are instantiated whenever they are called (as presumably they would usually be); the local variables Some_move and Some_other_move in the second and third clauses, while uninstantiated, are not referred to outside the negation.
Some variants of Prolog, such as constraint logic programming systems, could deal with negations such as \+ X=b in a more intelligent manner, by remembering the fact that X is not supposed to be equal to b. But such features are not implemented in the most widely available Prologs.
Previous | Table of Contents | Next |