- 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

`=(mia,mia).`

Prolog will respond `yes', and if we pose the query

`=(mia,vincent).`

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.`

yes

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`

and `mia`

are the same atom, matching succeeds.

A similar argument explains the following responses:

`2 = 2.`

yes

mia = vincent.

no

Once again, clause 1 is relevant here (after all, `2`

, `mia`

, and `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.`

yes

What's going here? Why do these two terms match? Well, as far as Prolog is concerned, `'mia'`

and `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

yes

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.`

yes

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, `X`

and `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 `X`

and `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 `_5075`

, or `_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 `X`

to `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)

yes

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, `shoot(gun)`

and `X`

, match? By Clause 2, yes, and we instantiate `X`

to `shoot(gun)`

. So do the second arguments, `Y`

and `stab(knife)`

, match? Again by Clause 2, yes, and we instantiate `Y`

to `kill(stab)`

.

Here's another example with complex terms:

`kill(shoot(gun), stab(knife)) = kill(X,stab(Y)).`

X = shoot(gun)

Y = knife

yes

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 `X`

with `marcellus`

and matching the second arguments would instantiate `X`

with `mia`

.

- Up - | Next >> |

Patrick Blackburn, Johan Bos and Kristina Striegnitz

Version 1.2.5 (20030212)