12.4 How are all solutions found? (Ad)

The question

We now know what backtracking is. We also know that backtracking occurs when a subgoal fails. But there is one other case in which backtracking occurs. This has to do with the following question:

How are all solutions found?

The answer

The answer is that when all the subgoals in a query have been satisfied, and the query therefore succeeds, Prolog starts the process of backtracking in order to find all solutions. The process continues until all possibilities have been exhausted. We will spell this out in an example.

Example

Consider the following program:

professor(Alfred).
professor(Albert).
student(name(Lisa), course(MA301), prof(Alfred)).
student(name(Martin), course(MA302), prof(Alfred)).
student(name(Lisa), course(PH307), prof(Albert)).
student_of(S,P) :- professor(P),
                   student(name(S), C, prof(P)).

The program links students, courses, and professors with each other. The program is available in the AAU sample directory as "Students5.plgCG".

Let us see what happens if we ask the question

?- student_of(Lisa, X).

The answers are:

{X = Alfred}
{X = Albert}

as expected. But how did Prolog obtain these answers?

Firstly, the only clause that matches the subgoal in the query is the rule:

student_of(S,P) :- professor(P),
                   student(name(S), C, prof(P)).

S gets bound to "Lisa", and X is bound to the free variable P, so it gets no value at this point.

Prolog proceeds with trying to satisfy the subgoals in the body of the rule.

professor(P) first matches professor(Alfred) (the first clause in the program), and P gets bound to "Alfred". The next subgoal to satisfy is "student(name(S), C, prof(P))", and the first matching that succeeds is the third line. C gets bound to the value "course(MA301)", and the subgoal succeeds. (The variable C is not used for anything later, but it needs to be there in order to match against the student/3 facts).

Since this subgoal was the last in the rule, the overall rule succeeds. Since X was bound to P, and since P is now bound to the value "Alfred", X now has the value "Alfred". Since the subgoal

student_of(Lisa, X)

was the last in the query, we now have one answer. Prolog+CG prints the following:

{X = Alfred}

Now the fun begins. Prolog backtracks to the previous goal that succeeded, which is still

student_of(Lisa, X)

The variable X is now made free again, since it was bound at that point, and Prolog starts at the last subgoal that succeeded. This was

student(name(S), C, prof(P))

in the rule:

student_of(S,P) :- professor(P),
                   student(name(S), C, prof(P)).

P still has the value "Alfred", and C is still bound to the value "course(MA301)". Prolog tries to satisfy the subgoal (with values substituted for variables):

student(name(Lisa), course(MA301), prof(Alfred))

Prolog starts at the next clause after the one that matched last time. This means that the subgoal is matched against:

student(name(Martin), course(MA302), prof(Alfred)).

This, of course, fails. So Prolog goes on to match the subgoal against all of rest of the clauses in the program, which fails.

Prolog now backtracks once more. It first undoes the variable binding

{C = course(MA302)}

since the subgoal failed. It goes back to the previous goal, which was

professor(P)

Since P was bound to the value "Alfred" at this point, P is now made free, and Prolog tries to satisfy the subgoal by going on to the next clause after the clause that satisfied the subgoal. This is:

professor(Albert)

which satisfies the subgoal, and P is bound to the value "Albert". Prolog now attempts to satisfy the subgoal

student(name(Lisa), C, prof(Albert))

The process starts at the top of the program, and succeeds with the fifth line of the program:

student(name(Lisa), course(PH307), prof(Albert)).

This of couse satisfies the last goal of the rule. Prolog+CG prints out:

{X = Albert}

Prolog now backtracks. It tries to resatisfy the subgoal

student(name(S), C, prof(P))

with variable bindings

{S = Lisa, C = course(PH307), P = Albert}

Prolog goes on after the clause that matched this, which is the fifth line, but fails all the way to the bottom of the program. Prolog now backtracks again. It undoes the variable binding {C = course(PH307)} and goes back to the previous subgoal that succeeded. This was

professor(P)

with the variable binding

{P = Albert}

this binding gets undone so that P is now a free variable, and Prolog tries to resatisfy the goal. This fails. Since this was the first subgoal of the rule, the overall rule fails.

Prolog now backtracks for the last time. The subgoal that last succeeded was the query-subgoal

student_of(Lisa, X)

Prolog now tries to match this subgoal against the next clause after the clause that satisfied it. But since there is no such clause, the backtracking fails. Since this subgoal was the top-level subgoal in the query (there was no subgoal before it in the query), backtracking stops at this point, and the process is done. Prolog shows the query-prompt again, ready to answer another question.

The answers which we got along the way were:

{X = Alfred}
{X = Albert}

Summary

Backtracking is used to find all solutions.

Next

This was a large and difficult chapter. We end it by giving a summary of the main points.


Prev: 12.3 What is backtracking? (Ad)
Up: 12 Prolog's solution strategy (Ad)
Next: 12.5 Summary (Ad)