The Prolog Tutorial:

Unification and Instantiation

This is the second tutorial in the course. As this stage you should be able to run SICStus, assert facts into the database and query the database about these facts.

Aims of the second tutorial:

• To introduce the Data Objects in Prolog.
• To be able load facts from a file into the database.
• To have a rough idea of how Prolog attempts to solve our queries.

In the first tutorial we came across one type of Data Object: the atom. We will now list the other data types:

We will now examine each of these.

Remember the facts we asserted in tutorial one? Assert these into the database again:

You can check that these facts are in the database by using the 'listing' predicate. This done now try the following interaction -

How does the system respond? You should see something like:

Now hit return. You have just used a variable. In Prolog a variable begins with an uppercase letter. When you query the database in this way, Prolog attempts to give the variable a value, in this case 'harry'. But why not 'tony'? Lets now examine why. Instead of typing return, type ';' and then hit return. As in the following

What Prolog attempts to do is match X with a value. In the database the facts are in the order that we asserted. We asserted the fact 'boy( harry )' before 'boy( tony )'. Note though what the semicolon effectively does. It basically asks the system can X have another value. The 'no' response at the end means that there are no more possible values for X.

In prolog there are two types of constants: atoms and numbers. We have already looked at atoms. Please recheck the first tutorial if you are unsure what they are. In the above example 'harry', 'tony', 'rachel', 'eunice' are all atoms.

Numbers in Prolog include integral numbers and real numbers. Numbers are generally used to keep count or increase a counter in a program. Prolog is not used for number crunching as it's primary use is in symbolic computation.

Structures ( also known as structured objects ) are objects that have several components. So in the example above 'boy( harry )' is a structure. In a structure we always have functor and arguments, e.g.

In the structure 'boy( harry )', 'boy' is the functor and 'harry' is the argument. Notice that the functor is always an atom. You can't have a variable as a functor. However the arguments can be anything from other structures to numbers to atoms. Please bear this in mind.

Matching is one of the powerful mechanisms that is available to Prolog. The matching operator is '=' which you have already come across. Be wary not to treat this as an assignment operator - it is not one and doesn't act as one.

In the first tutorial you did some matching with just atoms. Now we'll try it with variables. Enter the following:

How did the system respond? Check that Prolog prints out the value of the variable. In these cases we are 'instantiating' the variable to a particular value. Prolog prints out this value. Note also that 'Harry' is a variable ( because it begins with an uppercase letter ) and that variables can be instantiated to other variables. In the last query you should see that the two variables are matched and that when one of these variables receives a value so does the other.

We examine how matching works in more detail later.

The very last input that you should have typed in contains a comma, ',', you can use this to run queries together. This is the logical equivalent to an 'and'. Prolog will only return 'yes' if all the queries you submit together are true.

Which of the following will be true?

| ?- boy( harry ), girl( eunice ).

| ?- boy( X ), girl( eunice ).

| ?- boy( X ), boy( Y ) girl( eunice ).

| ?- boy( X ), girl( catherine ).

Enter the above and see what response you get. The first will be true as both facts are in the database. The second will be true because if Prolog can succeed in finding a value for the variable it will return, yes. We know the other query will also return 'yes' so the whole query together will.

The final query will not succeed as the fact 'girl( catherine )' is not in the database.

The way that a user generally interacts with the Prolog system is too first place the information that the user wishes to be loaded into the database in a file. Why? Well this file can be easily modified and then the information can be reloaded into the database.

For this next part of the tutorial please open a text editor. I recommend you use emacs as it is relatively user friendly and quite powerful.

Create a new file and place in the following information.

Remember to put in the full stops. Save the file as 'test.pl'. The '.pl' extension is one that SICStus recognises as being a Prolog file. This file can be easily loaded by using the built-in predicate consult. Try the following:

What happens?* Try using the 'listing' predicate. A further shortcut is to use this

Which will do the same thing as consult.

• If you are having problems you may have to give the explicit location of the file. To do this place the address in single quotation marks e.g. '/users/user_name/test.pl'. So you'd get: consult( '/users/user_name/test.pl' ).

Suppose we have the following facts in a database:

What exactly does Prolog do when we pose the query:

| ?- likes( john, X ).

( This the equivalent of saying - "What does John like?" ). Well, Prolog looks for a match in the database. If there is a variable as an argument Prolog will match with an argument in the same position if we find a similar fact. So in this case likes( john, X ) is matched with likes( john, prolog ). So X = prolog.

As this match has succeeded Prolog will print out the match, X = prolog and wait for a response. If we hit return 'yes' will be printed out and the user will be prompted for another So we get -

| ?-

Prolog searches through the database in the order in which it was typed in - top to bottom.

Lets go back to the point where Prolog made the match. Internally when the match is made Prolog marks this place in the database. It points out the value of the objects it has instantiated and waits for a response.

If you type a semicolon ( ;) followed by return Prolog continues searching. It continues searching through the database from the point where it placed the marker.

By typing ; you are in effect asking Prolog to provide another solution. The next matching fact will be - likes( john, football ) so X is instantiated to Football. A marker is placed beside this fact in the database. The value of the object is printed out and again we are asked for a response -

If we type ; we will get the following response

X = mary ?

And if we type ; yet again we find that no more solutions can be provided and Prolog answers 'no' and prompts us for another query.

This should give you a rough idea of how the Prolog search mechanism works.

Lets add another fact to the database.

So we now have in this order:

Now what happens when I ask Prolog the following -

( Note the conjunction ). This the equivalent of saying - "Is there something that both John and Mary like?". Well, first of all Prolog takes the first part of the query and attempts to find a match for it in the database. It will first match with - likes( john, prolog ) and X will be instantiated to prolog. A place marker will be put here after this has succeeded. As X is also in the next query it is given the value prolog. Prolog will now attempt to match -

likes( mary, prolog ).

As this fact does not exist in the database. It will fail. Now this is important - the whole query does not fail at this point. Prolog goes back to the point where it placed the place marker and attempts to find another solution to - likes( john, X ). This is known as 'backtracking' - where Prolog attempts to re-solve goals.

It looks for the next match and finds - likes( john, football ) so X is given the value - football. Again a marker is placed at this point in the database. Prolog now attempts to find a match for - likes( mary, football ) - which it finds and whole query succeeds.

Prolog would solve the above query faster if it was adjusted slightly to -

This will succeed without any backtracking. Here is a copy of the trace to prove this point.

That is the trace for the first query now look at the trace for the second query. Prolog has less work to do behind the scenes.

 Exercises - Tutorial 2

1. Create a new file 'likes.pl' and enter the likes/2 facts mentioned above. Load these into the database and query the database. Carry out the queries using trace.

2. Will these match?

Test them using SICStus

Since we have started creating files to store our Prolog programs. It will be useful to place comments in the files. We can do this in two ways:

The percentage comment is the equivalent of the '//' in Java. It's always useful to comment files but do so with restraint.

What you should know after the second tutorial:

• The Data Objects in Prolog:

• To be able load facts from a file into the database:

• To have a rough understanding of the work that Prolog does behind the scenes:

These are the built-in predicates that are introduced in tutorial 2:

trace, consult

Author - Jer Hayes - 2000