|- Up -||Next >>|
When working with knowledge base KB4 in the previous chapter, we introduced the term matching. We said, e.g. that Prolog matches
woman(mia), thereby instantiating the variable
mia. We will now have a close look at what matching means.
Recall that there are three types of term:
Constants. These can either be atoms (such as
vincent) or numbers (such as
Complex terms. These have the form:
We are now going to define when two terms match. The basic idea is this:
Two terms match, if they are equal or if they contain variables that can be
instantiated in such a way that the resulting terms are equal.
That means that the terms
mia match, because they are the same atom. Similarly, the terms
42 match, because they are the same number, the terms
X match, because they are the same variable, and the terms
woman(mia) match, because they are the same complex term. The terms
woman(vincent), however, do not match, as they are not the same (and neither of them contains a variable that could be instantiated to make them the same).
Now, what about the terms
X? They are not the same. However, the variable
X can be instantiated to
mia which makes them equal. So, by the second part of the above definition,
X match. Similarly, the terms
woman(mia) match, because they can be made equal by instantiating
mia. How about
loves(X,mia)? It is impossible to find an instantiation of
X that makes the two terms equal, and therefore they don't match. Do you see why? Instantiating
vincent would give us the terms
loves(vincent,mia), which are obviously not equal. However, instantiating
X to mia, would yield the terms
loves(mia,mia), which aren't equal either.
Usually, we are not only interested in the fact that two terms match, but we also want to know in what way the variables have to be instantiated to make them equal. And Prolog gives us this information. In fact, when Prolog matches two terms it performs all the necessary instantiations, so that the terms really are equal afterwards. This functionality together with the fact that we are allowed to build complex terms (that is, recursively structured terms) makes matching a quite powerful mechanism. And as we said in the previous chapter: matching is one of the fundamental ideas in Prolog.
Here's a more precise definition for matching which not only tells us when two terms match, but one which also tells us what we have to do to the variables to make the terms equal.
term2 are constants, then
term2 match if and only if they are the same atom, or the same number.
term1 is a variable and
term2 is any type of term, then
term2 match, and
term1 is instantiated to
term2. Similarly, if
term2 is a variable and
term1 is any type of term, then
term2 match, and
term2 is instantiated to
term1. (So if they are both variables, they're both instantiated to each other, and we say that they share values.)
term2 are complex terms, then they match if and only if:
They have the same functor and arity.
All their corresponding arguments match
and the variable instantiations are compatible. (I.e. it is not possible to instantiate variable
mia, when matching one pair of arguments, and to then instantiate
vincent, when matching another pair of arguments.)
Two terms match if and only if it follows from the previous three clauses that they match.
Note the form of this definition. The first clause tells us when two constants match. The second term clause tells us when two terms, one of which is a variable, match: such terms will always match (variables match with anything). Just as importantly, this clause also tells what instantiations we have to perform to make the two terms the same. Finally, the third clause tells us when two complex terms match.
The fourth clause is also very important: it tells us that the first three clauses completely define when two terms match. If two terms can't be shown to match using Clauses 1-3, then they don't match. For example,
batman does not match with
daughter(ink). Why not? Well, the first term is a constant, the second is a complex term. But none of the first three clauses tell us how to match two such terms, hence (by clause 4) they don't match.
|- Up -||Next >>|