Control and Cut

Rule Ordering
Cut

Rule Ordering

When Prolog is given a goal the interpreter searches for a fact or rules to satisfy the goal. Now although prolog programs can be read ``declaratively'' as logical statements as well as ``procedurally'' the order in which prolog searches for goals does matter. Depending on how rules are written the order they are written in might matter. Consider:

  factorial(0,1).  
  factorial(N,F):- 
      NP is N-1, factorial(NP,FP), F is FP*N.

which describes the relationship between a number (positive integer) and its factorial, ie. if the number is 0 the factorial is 1. For other non-negative integers N the factorial is N multiplied by the factorial of the previous number. The second rule does not check that N is greater than 0, in simple cases this does not matter because Prolog will try the clauses in order and never try the second rule with N=0. BUT it does mean that the order of the rules cannot be reversed, putting factorial(0,1). second will cause prolog to loop forever.

It is nearly always possible to avoid problems of order by putting additional predicates at the beginning of the ``more general'' rule, so:

  factorial(N,F):- 
      N > 0, NP is N-1, factorial(NP,FP), F is FP*N.
  factorial(0,1).

will work successfully. However this sometimes requires lots of additional checks.

Cut

Prolog will re-try and search all possibilities whenever it fails, in this lies the source for its power, but sometimes this can be unnecessary and very expensive. Consider the following rules:

    search([A|_],A) :- isit_answer(A).
    search([_|T],A) :- search(T,A).

Assume that (i) it is very expensive to test the candidate solutions in the list with isit_answer and (ii) it is known that there is at most one possible solution. Then if it is called in another context:

    ... search(PosAns,A), use(A,R)...

where the subsequent goal, (use fails Prolog will backtrack into search and pointlessly apply isit_answer to lots of other candidate solutions (it is pointless because it is known there is at most one solution).

This behaviour can be prevented by the use of cut which is written as ``!''. It is a goal, it will always succeed, but if it is ever re-tried it will fail, and fail the goal in which it occurs. Now in this situation the rules for search can be written:

    search([A|_],A) :- isit_answer(A), !.
    search([_|T],A) :- search(T,A).

which means that for a given invocation of search with a particular list when a solution is found by isit_answer the next goal is ``!'' which succeeds and search succeeds with A as the answer. If for any reason a later goal fails (for example use) when search is re-tried the backtracking will re-try ``!'' and immediately fail. The cut commits search to a single solution.

There are different ways cut can be used:

to speed up programs by preventing ``unnecessary'' backtracking (as above),
to simplify programs by allowing the dropping of various tests in subsequent rules, and
to force a goal to fail once it gets into a particular state.

However cut should be used with extreme caution because it changes the simple logical meaning of Prolog programs and can produce programs that are hard to follow.

An example, max gives the larger of 2 numbers, so:

      | ?- max(10,3,M).
      X = 10

This can be written as 2 simple rules:

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

Or by using cut the second condition can be omitted:

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

Once max finds the predicate X>=Y true and crosses the cut it is committed, if it subsequently backtracks it will not decide Y is the maximum by using the second rule because the cut will prevent it. That was just to demonstrate the behaviour of cut, the first version without it was much better.

This is just one example of its use, it is not a justification as it would in this case (as in many others) be best not to use it.

Next: Input and Output Up: A goal directed programming Previous: An Example

Page generated: 2002-11-04 by Bob Dickerson

Disclaimer