12.3 What is backtracking? (Ad)

The question

What happens when a subgoal cannot be satisfied? The answer is that Prolog starts the process called backtracking. The questions then becomes:

What is backtracking?

The answer

Backtracking is a process. When a subgoal fails, the Prolog system traces its steps backwards to the previous goal and tries to resatisfy it.

This means that all variables that were bound to a value when that goal was satisfied are now made free again. Then the Prolog system tries to resatisfy that goal by matching with the next clause starting at the clause just after the one that matched the subgoal.

This continues until either the subgoal is satisfied, or until the program database has been exhausted, at which point Prolog backtracks yet again to the subgoal that was before the current subgoal.

All of this probably requires an example, and we will provide such an example right away.

An example

Consider the following program:

son(Ishmael, Abraham, mother_is_slave).
son(Isaac, Abraham, mother_is_free).
patriarch(Abraham).
freeborn(P,S) :- patriarch(P), 
                 son(S,P,F),
                 eq(F,mother_is_free).

It is available in the AAU sample directory as "Abraham1.plgCG".

The eq/2 structure is a primitive goal in Prolog+CG. It attempts to match the two arguments. If the matching succeeds, the eq/2 goal succeeds. If the matching fails, the eq/2 goal fails.

Let us see what happens when we issue the query:

?- freeborn(X,Y).

First, Prolog tries to match this subgoal with the first clause in the program database (which is

son(Ishmael, Abraham, mother_is_slave)

). This does not succeed because the two structures do not have the same functor. Of course, only the fourth clause (the rule) matches. X gets bound to P, and Y to S, but since these are both free variables at the time, none of the four variables are bound to any value.

Then Prolog attempts to satisfy the subgoals in the body of the rule for freeborn/2. The first subgoal is

patriarch(P)

and the only clause that matches is the fact

patriarch(Abraham)

so P gets bound to the value "Abraham", and the subgoal succeeds.

The next subgoal is

son(S,P,F)

Prolog tries to match against the first clause, which happens to be

son(Ishmael,Abraham,mother_is_slave)

Since the two functors are the same, and the arities are the same, Prolog attempts to match the arguments from left to right. S is a free variable at this point, so S matches Ishmael and is bound to this value. P is already bound to "Abraham", and this value matches "Abraham" in the head of the fact. F is a free variable, so F matches "mother_is_slave" and is bound to this value. So the subgoal succeeds, with S having been bound to the value "Ishmael" and F having been bound to "mother_is_slave".

Prolog then goes on to the next subgoal and tries to satisfy this. The subgoal is:

eq(F,mother_is_free)

It will be remembered that this subgoal succeeds if the two arguments can be matched; otherwise it fails. F is now bound to "mother_is_slave", which does not match with "mother_is_free" (see Rule 1 on the list of rules for matching).

So the "eq(F,mother_is_free)" subgoal fails.

Prolog now starts the process of backtracking. It retraces its steps backwards to the previous subgoal, which was

son(S,P,F)

and undoes any variable bindings that were made at this point. This means that S and F are now free variables again.

Since this subgoal was matched against "son(Ishmael, Abraham, mother_is_slave)", Prolog starts at the next clause after this. This happens to be

son(Isaac, Abraham, mother_is_free)

which does match with the subgoal. S gets bound to "Isaac", F gets bound to "mother_is_free", and the subgoal succeeds.

Prolog now goes on to the next subgoal in the rule, which is

eq(F,mother_is_free)

Since F is now bound to "mother_is_free", the subgoal succeeds.

Since this subgoal was the last in the body of the rule:

freeborn(P,S) :- patriarch(P), 
                 son(S,P,F),
                 eq(F,mother_is_free).

the rule succeeds. Recall that the subgoal in the query which we tried to match against this rule was:

freeborn(X,Y)

and that X was bound to P and Y was bound to S. Since P is now bound to "Abraham" and S to "Isaac", we get these variable bindings:

{X = Abraham, Y = Isaac}

Summary

When a subgoal cannot be satisfied, Prolog starts the process of backtracking. It goes back to the previous subgoal, undoes any variable bindings that took place at this point, and tries to resatisfy this subgoal. It does so by attempting to match against the head of the next clause in the program database after the clause that last resulted in a match.

Next

There is actually more to say about backtracking, because at this point, Prolog does some more backtracking, but we will save that for the next page.


Prev: 12.2 In what order does matching occur? (Ad)
Up: 12 Prolog's solution strategy (Ad)
Next: 12.4 How are all solutions found? (Ad)