12.1 How is a subgoal satisfied? (Ad)

The Question

Remember that the way you get answers from Prolog is by asking queries. A query is made up of one or more subgoals. The whole of the query is satisfied if each of the subgoals can be satisfied in turn. So the first question to answer is:

How is a subgoal satisfied?

The Answer

The answer is this:

A subgoal can be satisfied in two ways:

  1. By matching with a fact. If the matching occurs, the subgoal is satisfied.
  2. By matching with the head of a rule. If matching occurs, the subgoal is only satisfied if all of the subgoals of the body of the rule can also be satisfied.

Matching

Remember that when we say "match", we are referring to the process of matching previously discussed, and that this matching takes place according to some specific rules.

Matching vs. satisfying

Note that there is a difference between 'matching' and 'satisfying'.

'Matching' is a process that applies to terms. It is the process whereby it is decided whether two terms match or not.

'Satisfying', on the other hand, is a higher-level process, and applies to subgoals. Subgoals are satisfied by means of matching, but as we saw, there is something more involved:

A subgoal that matches the head of a rule is satisfied only if all of the subgoals of the body of the rule can be satisfied.

Example

For example, take the familiar example program:

student(name(Lisa), semester(5)).
student(name(Martin), semester(3)).
student(name(John), semester(3)).
student(name(Edward), semester(7)).

same_semester(A,B) :- student(A,S), 
                      student(B,S).

If we ask the query:

?- same_semester(name(Martin), name(John)).

the only subgoal in the query is satisfied by matching with the head of the rule:

same_semester(A,B) :- student(A,S), 
                      student(B,S).

However, it is only satisfied because both of the subgoals in the body of the rule can also be satisfied.

These subgoals, in turn, are satisfied by matching with the heads of facts.

Next

So a goal is satisfied by the process of matching, plus the requirement that the subgoals in the body of a rule must also be satisfied. This leaves us with a number of new questions, one of which is: In what order does matching occur? We treat this question next.


Prev: 12 Prolog's solution strategy (Ad)
Up: 12 Prolog's solution strategy (Ad)
Next: 12.2 In what order does matching occur? (Ad)