Download Introduction to Prolog Programming

Chapter 5
Backtracking, Cuts and Negation
In this chapter you will learn a bit more on how Prolog resolves queries. We will also
introduce a control mechanism (cuts) that allows for more efficient implementations.
Furthermore, some extensions to the syntax of Prolog programs will be discussed. Besides
conjunction (remember, a comma separating two subgoals in a rule-body represents a
conjunction) we shall introduce negation and disjunction.
5.1
Backtracking and Cuts
In Chapter 1 the term “backtracking” has been mentioned already. Next we are going
to examine backtracking in some more detail, note some of its useful applications as well
as problems, and discuss a way of overcoming such problems (by using so-called cuts).
5.1.1
Backtracking Revisited
During proof search, Prolog keeps track of choicepoints, i.e., situations where there is
more than one possible match. Whenever the chosen path ultimately turns out to be a
failure (or if the user asks for alternative solutions), the system can jump back to the last
choicepoint and try the next alternative. This is process is known as backtracking. It is
a crucial feature of Prolog and facilitates the concise implementation of many problem
solutions.
Let’s consider a concrete example. We want to write a predicate to compute all
possible permutations of a given list. The following implementation uses the built-in
predicate select/3, which takes a list as its second argument and matches the first
argument with an element from that list. The variable in the third argument position
will then be matched with the rest of the list after having removed the chosen element.
Here’s a very simple recursive definition of the predicate permutation/2:
permutation([], []).
permutation(List, [Element | Permutation]) :45