Prolog Tutorial 8a: More Control Features

James Power, 1997.


The cut predicate has a number of associated predicates, all of which deal with changing the way Prolog goes about solving goals. Use these sparingly!


Kinds of cut

While using the cut can make programs shorter or more efficient, it also makes them more difficult to understand, and less "logical" in nature. In general we distinguish two types of cut:
Green cuts
These are cuts which are introduced simply to make the program more efficient by eliminating what the programmer knows to be useless computations. They do not remove any extra solutions! Running a program without green cuts should still give the same answer, even though it may take a little longer to do so.
Red cuts
These cuts are introduced to make the program run in a different way; they do this by eliminating some of the possibilities that might be considered. Thus they change the logical meaning of the program.
Green cuts are useful for speeding up computations; red cuts should be avoided where possible.


Negation as Failure

If we ask Prolog to satisfy some goal P, and Prolog responds no, we take this as meaning that P cannot be satisfied.

In certain situations we will want to define predicates in terms of the negation of other predicates.

We can do this using a combination of cut and another built-in predicate, fail, which always fails.

Thus to say "q is true if p isn't", we might write:

  q :- p, !, fail.
  q.
Note that if we left out the cut here then Q would always be satisfied, since the second case would be reached after the first failed.

Prolog has a built-in shorthand for this: the meta-predicate "\+"; thus we might write:

  q :- \+(p).    % Q is true whenever P fails...
An example of using this would be the following predicate which will be satisfied if X and Y cannot be unified.
  different(X,Y) :- X=Y, !, fail.
  different(X,Y).

Warning!

This way of implementing what is effectively the predicate "not" is called negation as failure; it is not proper negation. As with any Prolog program involving the cut, you should be very careful when using it!

An example of where negation as failure can give unexpected results is the following predicate:

  home(X) :- \+(out(X)).
  out(sue).
Now, work out what is the logically correct answer to the following queries, and then try them in Prolog: The apparent contradiction is caused by Prolog's closed-world assumption; that is, Prolog assumes it always has all relevant information: hence, if something can't be proved true, it must be false.


If-then-else in Prolog

One common use of the cut predicate is to mimic the "if-then-else" construct found in imperative languages.

Suppose we want to define some predicate S which should be of the form: "if P then Q else R" We can define this in Prolog as:

  s :- p, !, q.
  s :- r.
Prolog has a shorthand for this built-in; we need only write:
  s :- p -> q ; r.
For example, suppose we wanted to write a predicate to add an element to a list; we might just write: add(Elem,List,[Elem|List]).

Suppose now that we want to change this predicate so that no duplicates are added to the list; we might write:

  % add(Elem, List, NewList) is true if adding Elem to List is NewList
  %                          Elem is not added if it's there already.
  add(X,L1,L2) :- member(X,L1), !, L2 = L1.
  add(X,L1,L2) :- L2 = [X|L1].
Using the if-then-else notation, we could simply write this as:
  add(X,L1,L2) :- member(X,L1) -> L2 = L1 ; L2 = [X|L1].


The repeat predicate

If a particular clause can be satisfied more than once, we know that Prolog will go back and try and find all of those solutions (assuming there is no cut). However, in certain circumstances it can be useful to get "all the backtracking done" on a particular part of the program, before moving on to process the rest of the goal. This sort of situation arises when we want to perform iterative operations like reading from a file, or some kind of "control loop" such as displaying a menu.

Prolog has a built-in predicate called repeat, which can be satisfied arbitrarily many times.

[Aside: the predicate is defined as:

  repeat.
  repeat :- repeat.
]

the predicate is generally used on the right-hand-side of some clause in the format:

  ..... :- repeat,
           ( "Stuff to be iterated" ),
           ( "Termination Condition" ),
           !.
When the goal is processed, the repeat command is satisfied, and the "body" is processed. If the termination condition is true, then the execution of this block is finished - the cut ensures that we don't backtrack over it again. If it is false then backtracking occurs. Since the repeat will always be re-satisfied, control moves forward again from this point, and the process starts over.

An common example might involve a structure like:

  main_loop :- repeat,              % Start of iteration
                 display_menu,        % Print out the menu
                 get_option(N),       % Get input from user
                 validate_option(N),  % Check that it's valid
                 process_option(N),   % Carry out appropriate action
               is_quit_option(N),   % Termination Condition
               !.                   % Don't go back on any of this!
Here we assume that is_quit_option(N) returns true whenever N is the menu option corresponding to "Quit program"...

The control predicates are described in section 7.18 of the GNU Prolog manual.


Written by James Power
Released under the GNU Free Documentation License
Last revised: 7th October 1998