|- Up -||Next >>|
We'll now look at lots of examples to make this definition clear. In these examples we'll make use of an important built-in Prolog predicate, the
=/2 predicate (recall that the
/2 at the end is to indicate that this predicate takes two arguments).
Quite simply, the
=/2 predicate tests whether its two arguments match. For example, if we pose the query
Prolog will respond `yes', and if we pose the query
Prolog will respond `no'.
But we usually wouldn't pose these queries in quite this way. Let's face it, the notation
=(mia,mia) is rather unnatural. It would be much nicer if we could use infix notation (that is, put the
= functor between its arguments) and write things like:
mia = mia .
And in fact, Prolog lets us do this. So in the examples that follow we'll use the (much nicer) infix notation.
Let's return to this example:
mia = mia.
Why does Prolog say `yes'? This may seem like a silly question: surely it's obvious that the terms match! That's true, but how does this follow from the definition given above? It is very important that you learn to think systematically about matching (it is utterly fundamental to Prolog), and `thinking systematically' means relating the examples to the definition of matching given above. So let's think this example through.
The definition has three clauses. Clause 2 is for when one argument is a variable, and clause 3 is for when both arguments are complex terms, so these are no use here. However clause 1 is relevant to our example. This tells us that two constants unify if and only if they are are exactly the same object. As
mia are the same atom, matching succeeds.
A similar argument explains the following responses:
2 = 2.
mia = vincent.
Once again, clause 1 is relevant here (after all,
vincent are all constants). And as
2 is the same number as
2, and as
mia is not the same atom as
vincent, Prolog responds `yes' to the first query and `no' to the second.
However clause 1 does hold one small surprise for us. Consider the following query:
'mia' = mia.
What's going here? Why do these two terms match? Well, as far as Prolog is concerned,
mia are the same atom. In fact, for Prolog, any atom of the form
'symbols' is considered the same entity as the atom of the form
symbols. This can be a useful feature in certain kinds of programs, so don't forget it.
On the other hand, to the the query
'2' = 2.
Prolog will respond `no'. And if you think about the definitions given in Lecture 1, you will see that this has to be the way things work. After all,
2 is a number, but
'2' is an atom. They simply cannot be the same.
Let's try an example with a variable:
mia = X.
X = mia
Again, this in an easy example: clearly the variable
X can be matched with the constant
mia, and Prolog does so, and tells us that it has made this matching. Fine, but how does this follow from our definition?
The relevant clause here is clause 2. This tells us what happens when at least one of the arguments is a variable. In our example it is the second term which is the variable. The definition tells us unification is possible, and also says that the variable is instantiated to the first argument, namely
mia. And this, of course, is exactly what Prolog does.
Now for an important example: what happens with the following query?
X = Y.
Well, depending on your Prolog implementation, you may just get back the output
X = Y.
Prolog is simply agreeing that the two terms unify (after all, variables unify with anything, so certainly with each other) and making a note that from now on,
Y denote the same object. That is, if ever
X is instantiated,
Y will be instantiated too, and to the same thing.
On the other hand, you may get the following output:
X = _5071
Y = _5071
Here, both arguments are variables. What does this mean?
Well, the first thing to realize is that the symbol
_5071 is a variable (recall from Lecture 1 that strings of letters and numbers that start with a
_ are variables). Now look at clause 2 of the definition. This tells us that when two variables are matched, they share values. So what Prolog is doing here is to create a new variable (namely
_5071 ) and saying that, from now on, both
Y share the value of this variable. That is, in effect, Prolog is creating a common variable name for the two original variables. Incidentally, there's nothing magic about the number
5071. Prolog just needs to generate a brand new variable name, and using numbers is a handy way to do this. It might just as well generate
_6189, or whatever.
Here is another example involving only atoms and variables. How do you think will Prolog respond?
X = mia, X = vincent.
Prolog will respond 'no'. This query involves two goals,
X = mia and
X = vincent. Taken seperately, Prolog would succeed for both of them, instantiating
mia in the first case and to
vincent in the second. And that's exactly the problem here: once Prolog has worked through the first query,
X is instantiated, and therefore equal, to
mia, so that that it doesn't match with
vincent anymore and the second goal fails.
Now, let's look at an example involving complex terms:
kill(shoot(gun),Y) = kill(X,stab(knife)).
X = shoot(gun)
Y = stab(knife)
Clearly the two complex terms match if the stated variable instantiations are carried out. But how does this follow from the definition? Well, first of all, Clause 3 has to be used here because we are trying to match two complex terms. So the first thing we need to do is check that both complex terms have the same functor (that is: they use the same atom as the functor name and have the same number of arguments). And they do. Clause 3 also tells us that we have to match the corresponding arguments in each complex term. So do the first arguments,
X, match? By Clause 2, yes, and we instantiate
shoot(gun). So do the second arguments,
stab(knife), match? Again by Clause 2, yes, and we instantiate
Here's another example with complex terms:
kill(shoot(gun), stab(knife)) = kill(X,stab(Y)).
X = shoot(gun)
Y = knife
It should be clear that the two terms match if these instantiations are carried out. But can you explain, step by step, how this relates to the definition?
Here is a last example:
loves(X,X) = loves(marcellus,mia).
Do these terms match? No, they don't. They are both complex terms and have the same functor and arity. So, up to there it's ok. But then, Clause 3 of the definition says that all corresponding arguments have to match and that the variable instantiations have to be compatible, and that is not the case here. Matching the first arguments would instantiate
marcellus and matching the second arguments would instantiate
|- Up -||Next >>|