Example: here is the definition of the built-in Prolog predicate
member(X, [X | Rest]). % X is a member if its the first element member(X, [Y | Rest]) :- member(X, Rest). % otherwise, check if X is in the RestYou may not think of
memberas a backtracking predicate, but backtracking is built into Prolog, so in suitable circumstances,
?- member(X, [a, b, c]). X = a ; X = b ; X = c ; false.Here
memberbacktracks to find every possible solution to the query given to it. Consider also:
?- member(X, [a, a, a]). X = a ; X = a ; X = a ; false.Here
memberbacktracks even though it keeps on finding the same answer. What about
?- member(a, [a, a, a]). true ; true ; true ; false.This is because prolog has three ways of proving that
ais a member of
[a, a, a].
The term backtracking also applies to seeking several sets of variable bindings to satisfy a single goal.
In some circumstances, it may be desirable to inhibit backtracking, as when only a single solution is required. The Prolog cut goal allows this.
Tracing the execution of a piece of Prolog
code that backtracks can be a good way to figure out what
happens during backtracking. If you wanted to experiment with
backtracking by tracing
you could achieve this by copying the code for
given above, changing the name from
member to say
mem in the three places where it appears, and then