Previous | Table of Contents | Next |
In the definition of the best_move_for predicate, the second clause started out with a literal that negated the first clause. Essentially we were saying If there is no winning move for P, then the best move is a drawing move. It is so common to want to take a predicate call appearing in one clause and negate it in a later clause that Prolog supplies a construct that is primarily used for this: the cut literal, !. Cut can appear in a rule body wherever any other literal can appear.
6.3.2.1. Using the Cut Literal to Simplify Code
Consider the following version of the best_move_for predicate:
best_move_for(P, Board, Move) :- winning_move_for(P, Board, Move), !. best_move_for(P, Board, Move) :- drawing_move_for(P, Board, Move), !. best_move_for(P, Board, Move) :- move_for(P, Board, Move).
This version computes the same thing as the original version but is more concise. The way it works is this. When Prolog gets to a cut literal !, it commits itself to the clause it has selected and refuses to use the remaining clauses for that predicate. Thus if there is a winning move for P, it never tries to claim a non-winning move as the best move; it is as if there is an automatic negation of winning_move_for before the other two clauses. Similarly, the cut in the second clause is like an automatic negation of drawing_move_for in the last clause. The name comes from the fact that it is in a sense cutting away a part of Prologs potential search tree.
The main advantage of using the cut here is efficiency. In the first version of best_move_for, the first clause causes winning_move_for to be called; if it does not succeed, the second clause causes it to be called again (inside the negation). With the cut, winning_move_for is called only once. This can be a big timesaver. Similarly, the delete predicate is often expressed as
delete([X|Tail1], X, L2) :- !, delete(Tail1, X, L2). delete([Y|Tail1], X, [Y|L2]) :- delete(Tail1, X, L2).
This guarantees that if the head of the first argument is the same as the second argument, the second clause is not used.
Because it has to do with negation, cut can also lead to unsound computations. You will often see dire warnings in Prolog texts about the dangers of using the non-logical cut feature. However, most of the uses of cut are to achieve exactly what we have been doing in this section: an efficient negation of some earlier condition. We just have to follow a similar rule of thumb to that which we use for negation. Avoid situations where a head variable is instantiated before a cut and the predicate then fails, because this pattern can cause an unsound negation. A call to the delete predicate is safe in this sense if the first two arguments are instantiated and the last one is uninstantiated at the time of the call because in that case, delete cannot fail.
Another useful rule of thumb for cut, as expressed by OKeefe (1990), is to place a cut exactly where you first know that the clause being used is the right one. For instance, in best_move_for, as soon as we know there is a winning move, we know we can discard the other clauses; and in delete, as soon as we know the head of the first clause has been matched (that is, that the second argument is the same as the head of the first argument), we know we can discard the other clause. Placing the cuts earlier or later may result in unwanted failures or solutions.
6.3.2.2. Finding the First Solution
A secondary effect of cut is that it not only throws away alternatives to the current clause, but all the alternatives that have been built up since the predicate was called. This means that it can be used to find the first solution to a query. A predicate body that starts with
grandparent(X, Y), rich(Y), !,
finds the first rich grandparent of X.
This can be useful if it is sufficient for us to find just one rich grandparent. It can also be useful if all we want to establish is that some grandparent of X is rich because with the cut, if there is a later failure we will not go on finding other rich grandparents and retrying whatever comes after the cut. These uses of the cut are not as common but do arise occasionally.
Here we look briefly at defining predicates that have more than one arity. Such predicates are useful chiefly in situations where we want to have default arguments.
Consider the following code:
ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Parent), ancestor(Parent, Y). ancestor(Y) :- ancestor(me, Y).
This is just the definition of the ancestor relation with a new clause tacked onto the end. The different thing about the new clause is that the atom in its head has only one argument, as opposed to two for all other occurrences of ancestor, including the one in the body of the new clause.
Most Prologs do not raise an error message on such definitions but simply consider the last clause to be defining a new predicateancestor with one argumentin terms of an old predicateancestor with two arguments. In Prolog parlance, the one-argument predicate is referred to as ancestor/1 and the two-argument predicate as ancestor/2. ancestor/1 here is useful if we expect to be calling the ancestor predicate a lot with the first argument me, and we want to save some typing. Two clauses are actually considered to be defining the same predicate only if both the predicate names are the same and the arities of the head atoms are the same.
In fact, expressions of the form predicate-name/arity are often used in Prolog reference material when talking about predicates, even if the predicates are not multi-arity. The arity serves to remind us of the format of the predicate call; thus we use append/3 to refer to the standard append predicate or write/1 and nl/0 for those output predicates.
Previous | Table of Contents | Next |