Module 1, part 1

Module 1

Simple matching

Let us suppose that you are sitting in front of a Prolog system, which you have invoked. ("Invoked" is jargon for "starting Prolog running so that you get the initial prompt, which probably looks something like '| ?-'".) What you see is the visible part of what is known as the "Prolog interpreter". When you type instructions into the interpreter, Prolog will attempt to process each instruction in turn.

Before you type your first instruction into the Prolog interpreter, you must know one thing. Everything you type into the interpreter must end in a full stop. Think of it as instructing a robot using a normal sentence of a language like English. So you might say:

turn twice clockwise,
pick-up the cup,
then wash the cup.

The full stop at the end of the sentence is the signal for the robot to stop listening and to start its actions. So it is with the Prolog interpreter: until you enter a full stop, it will think you have something else that you want to add.

As a first exercise, enter any single word you like, making sure that your word starts with a lower-case letter (and don't forget the full stop).

You have now entered a Prolog "query" or "goal". What did Prolog reply with? For almost all words you could enter, Prolog will reply "no". If you hit upon one of the very few words that Prolog reserves for its own use, you may have got the reply "yes". Here is what happened when I tried a few words (I've put what I entered in italics: everything else is Prolog's):

| ?- hkpolyu. {EXISTENCE ERROR: hkpolyu: procedure user:hkpolyu/0 does not exist} | ?- happy. {EXISTENCE ERROR: happy: procedure user:happy/0 does not exist} | ?- true. yes

"true" is one of Prolog's "built-in predicates". A built-in predicate is a word that has some special significance for Prolog. There are a very small number of these (compared to other languages like LISP) and many of them will be introduced to you during this course.

Matching with " ="

The first built-in predicate that we will introduce at length is "=". Matching is an activity we do all the time. For instance, you might match a road number (eg M40) printed in an atlas with the number given on a road sign. We intuitively think of the kind of matching we do as differing in complexity. Children find it easier to place circular bricks than polygons into a shape sorter. We think of "comparing" dates on historical inscriptions but talk of "recognising" a face, suggesting that we know this to be a complicated process that involves matching many aspects of what we see with our "stored picture" of that face.

If we try an example like:

     | ?- car = lorry.

     no

Prolog will reply "no". This seems very reasonable to us because we assume that "=" means "is equivalent to", and we know that a lorry is not a car. It is important to realise that Prolog does not know anything about cars and lorries. All it has done is to look at the two words and seen if they are equivalent. If you want a simple model, think of Prolog looking at each letter of each word, comparing them one at a time: eg

     c a r

!= l o r r y

The following examples might seem less obvious to those new to computing:

     | ?- lorry = lorries.

     no
     | ?- scammell = lorry.

     no
     | ?- scammell = lorry.

     no

(Scammell was (and may still be) a UK manufacturer of large lorries.)

If Prolog understood about objects in the real world, then you might expect it to answer "yes" to one or more of the queries above. Prolog treats all these queries just as it did the one before them and compares the two words, letter by letter:

        l       o       r       r       y
        =       =       =       =       !=
        l       o       r       r       i       e       s

        s       c       a       m       m       e       l       l
        !=
        l       o       r       r       y

As a final example on this topic, take the queries:

     | ?- lorry = truck.

     no
     | ?- lorry = lorry.

     yes

"lorry" and "truck" are absolute synonyms in English (as nearly as any two words can be) but Prolog doesn't know this: it merely compares letter by letter, which explains why it replies "yes" to the last example.

All the examples so far have used words that begin with lower case letters. What happens if we abandon this restriction?

     | ?- Lorry = scammell.

     Lorry = scammell ?

Our new query has been successful. (We can tell that because the Prolog interpreter has not replied "no".) The only difference between the successful and the unsuccessful queries is that we have changed "lorry" to "Lorry". Prolog distinguishes between variables and "atoms" (words that are constant or literal) on the basis of how the word begins. A good rule is that an atom starts with a lower case letter. A variable in Prolog usually starts with an upper case letter.

Take time to work through the Self-Test 1

Matching atoms and variables with =

In the example above:

| ?- Lorry = scammell. Lorry = scammell ?

the message that Prolog returns shows that the variable "Lorry" has acquired the value "scammell". If you are used to other programming languages like Pascal you will be reminded of constructs like:

     Lorry := scammell;

In Pascal, the variable has to be on the left-hand side of the ":=", but look at this Prolog example:

     | ?- scammell = Lorry.

     Lorry = scammell ?

The variable doesn't have to be on the left-hand side of "=".You may now be wondering what happens if both sides of "=" are variables? In some programming languages, the notion of trying to equate two variables without value will cause an instant failure message - usually something like "Undefined scalar value". Prolog is far more tolerant than most languages. Try an example, eg:

     | ?- Lorry = Truck.
     
     Truck = Lorry ?
     
     yes
     | ?- write(Truck).
     _70
     true ?

The example you try might well look generally the same, but the replies might look different. What does "_70" mean? Prolog does some neat work keeping track of what variables you use and what values they have. To do this, one tactic used is for Prolog to have its own internal variables. It makes these by starting them with an underscore character ("_") and then appending a unique integer to it. So we now know that variables may start either with an upper case letter or an underscore character.

In the following example, Prolog has given Lorry and Truck different internal variables. The last part of the query (Lorry=Truck) essentially ensures that these two variables point to the same internal variable, but this implementation of Prolog hides the detail from us by using the names we've given to the variables. Theinternal variable doesn't yet have a value itself, but when it does, Lorry and Truck will also get this value.

     | ?-  write(Truck), write(Lorry), Lorry=Truck.
     _70_100
     Truck = Lorry ?

As a point of good practice, always use an upper case letter to start your variables and try not to start them with an underscore followed by other letters or numbers. If you start calling your variables things like "_123" or "_65398" you will find that you will muddle your own variables with Prolog's internal variables.

So far, our repertoire of Prolog is a bit limited. We'll extend it further by allowing more than one goal in our queries. To have more than one goal, we have to indicate how we want the goals connected. For the time being we will use the "and" relation which in Prolog is written as ",". We'll run two previous examples together:

     | ?- Lorry = Truck, Lorry = scammell.

     Lorry = scammell,
     Truck = scammell ?

Lorry certainly will get the value "scammell", but so also does Truck. Prolog does this by setting Truck to whatever value Lorry has (or vice versa). If Lorry or Truck doesn't have a value, then Prolog simply waits until (if ever) one of the two variables gets a value. When one of the variables gets a value, then the other variable also gets the value. (Prolog manages to do this in part by simply making both variables have the same value as the internal variable; once one of the variables gets a value, Prolog gives that value to the internal variable, and so any other variables that point to the internal variable also get the value.)

We will give another example, this time using a new built-in predicate called "write": what it does is fairly obvious.

     | ?- Lorry = Truck, Lorry = scammell, write(Truck).
     scammell
     Lorry = scammell,
     Truck = scammell ?

Here Truck has the same value as Lorry. The Prolog interpreter works its way through each of the goals in the query, starting from the left and working to the right. So with the query:

      | ?- write(Lorry), nl, scammell = Lorry, write(Lorry).
      _70
      scammell
      Lorry = scammell ?

in the first write, Lorry doesn't yet have a value, but by the second write, it has acquired a value. (nl simply makes sure that any output after it starts on a new line.)

There remains one more part to this topic. What happens if there is a contradiction in the query?

As a simple example, consider the following example:

     | ?- car = nova.

     no

Clearly the two atoms are not the same. An example with a conjunction is only slightly more complicated:

     | ?- Car = nova, fiesta = Car.

     no

This makes an important point that in Prolog a variable can only have one value during the execution of a query. So once Car has the value "nova", it cannot reset the variable's value to something else, eg "fiesta". This is completely unlike many languages where you can assign different values to a variable at will. This next example shows that Prolog doesn't remember the values of variables between queries:

     | ?- nova = Car.

     Car = nova ?
     | ?- Car = fiesta.

     Car = fiesta ?

The effects of the query last only as long as the processing of the current query. Put briefly, all the information in variables is lost to Prolog after it has processed the final full stop of a query.

Take time to work through the Self-Test 2

Back | Top of this Module | Next