12.2 In what order does matching occur? (Ad)

The question

Now that we know that goals are satisfied by means of the process of matching, another question which we need to answer is:

In what order does matching occur?

Why is this important?

To really see why this is important, we need some information which is only presented later, in the chapter on recursivity. But for now, we can at least note that if we have the following program:

father(Abraham,Isaac).
father(Abraham,Ishmael).

and we ask the following query:

father(Abraham,X).

we get the following two answers, in the following order:

{X = Isaac}
{X = Ishmael}

It might be important to us that we get the answers in this order, and then it will be important to know in what order Prolog is going to give them to us.

So now we are ready for the answer to the question: In what order does matching occur?

The answer

The answer must be given in three stages.

The first stage involves the order in which subgoals are matched against clauses in the program database.

The second stage involves the order in which arguments of a subgoal are matched against the arguments of the head of a clause.

The third stage involves the order in which subgoals in the body of a rule are satisfied.

Subgoals and clauses

When Prolog tries to satisfy a subgoal, it tries to match the subgoal with the first clause (i.e., fact or rule) in the program. If this does not satisfy the subgoal, Prolog goes on to the next clause, and the next, and the next, etc., in the written top-to-bottom order of the program, until either the goal is satisfied or there are no more clauses in the program.

Arguments of subgoals

As already noted in the chapter on matching, when Prolog tries to match the arguments of two structures with the same functor and the same arity, the matching occurs left-to-right. This is important because a variable might get bound to a value in the process of matching. If this variable occurs again in one of the later arguments (i.e., an argument more to the right), then the variable will already be bound to a value, and this value will be used in place of the variable.

For example, when matching the following subgoal:

1) foo(Abraham, N)

with the following subgoal:

2) foo(X,X)

N will be bound to the value "Abraham".

The reason is that when matching the first argument of the subgoals, X gets bound to the value "Abraham". When matching the second argument of the subgoals, N gets bound to X, which already has the value "Abraham", so N also gets the value "Abraham".

Subgoals in the body of a rule

Recall that when matching a subgoal with the head of a fact, the subgoal is satisfied if the matching succeeds. Recall also that when matching a subgoal with the head of a rule, the subgoal is satisfied only if all of the subgoals in the body of the rule are satisfied. Then it is important to know: In what order are the subgoals in the body of the rule satisfied?

The answer is that again, Prolog attempts to satisfy them in the left-to-right, top-to-bottom order in which they are written. If the first subgoal is satisfied, Prolog goes on to the next subgoal, and the next, etc., until all of the subgoals have been satisfied.

This is actually a slightly simplified answer, but we shall mend matters shortly on the next page.

Summary

Matching generally occurs top-to-bottom, left-to-right.

Subgoals are matched against heads of clauses in a top-to-bottom order.

Arguments of subgoals are matched against arguments of the heads of clauses in a left-to-right, top-to-bottom order.

Subgoals in the body of a rule are matched in a left-to-right, top-to-bottom order.

Next

When a subgoal is not satisfied, Prolog starts the process of bactracking. The next page discusses this process. Backtracking, among other useful results, is the reason why we can get more than one answer from a given query.


Prev: 12.1 How is a subgoal satisfied? (Ad)
Up: 12 Prolog's solution strategy (Ad)
Next: 12.3 What is backtracking? (Ad)