The Prolog Tutorial:

Tutorial 3

At this stage in the tutorial you should be able to construct simple facts. You should be able to store these in a file and load these into the database. You should also know how to query the database about these facts.

The aims of this tutorial

• To be bale to construct rules.
• To realise that we use recursion to repeatedly do something in Prolog.
• To write recursive rules.
• To have a rough understanding what's going on behind the scenes

So far we have used facts to describe the information that we wish to put into in the database. We are now going to examine information on a family tree to show we can use facts and rules.

Create a new file called 'family_tree.pl' and place the following facts in it:

Load this file using consult or the short-cut mentioned above. One of the powerful features is that it allows us to define rules. For example, look at the example above, what exactly is a child in this context. Well, if someone, say a person A, is the parent of another person, person B, then person B is the child of person A. Prolog allows us to capture this relationship as follows:

This means that A is a child of B if B is the parent of A. The above rule has the following form:

The Head is true if the Body is true. So if the facts in the Body are true then the head is true. Note how close this is to conditionals in other languages. Up until this point we have only developed facts. Facts are always true. Rules are only true if the body is true.

 Place this rule ( child ) in the 'family_tree.pl', save it and then consult it again. Now try the following interactions:

Let us examine closely what's going on in each of these queries. Remember earlier on when you were carrying out some simple matching? Well, when Prolog is presented with a query such as child( ann, bob ) it tries to match it with the information it has in the database. So the rule we have constructed is -

Initially the variable A is instantiated the value 'ann' and is instantiated variable B is assigned the value 'bob'. These values are then placed in the parent relation. So we get parent( bob, ann ). Prolog then tries to see if such a fact exists in its in knowledge base. As it does the final response to the query is 'yes'.

What you should now do is type trace. This is lets you see what the Prolog system is attempting to match.

Then re-enter all the previous interactions that involve the child relation ( i.e. child( ann, bob ) and so on ). You will probably have to hit return a number of times to keep the trace moving.

This is a trace of 'child( ann, X )':

Note that although we have called the variables A and B in our file Prolog gives them a different name this name is usually an underscore followed by a number. So when you see this it's just a variable.

To switch the trace off type:

The form of Prolog programs as you will see in later tutorials is to group various procedures into the form of rules. So if you are not sure what was going on in the last section. Please re-read it. It is vital that you understand how rules work and how we can define them. It also important to get feel for how Prolog attempts to match your query with information in the database.

In a language such as Java if we wished to carry out an action a number of times we would use a for loop, or a while loop and so on. Remember that these control structures are not built into Prolog.

The main method to carry out repetition in Prolog is to use recursion. It is not difficult to use recursion in Prolog. In Prolog, recursion involves a rule calling itself .

We are going to use a family tree example. Open the file family_tree.pl and add these new facts -

This done we are going to construct an ancestor rule. You should see that I've just given Bob and Mary parents. Now what we want to define is a rule where the first argument is the ancestor and second is the descendant.

So ancestor( X, Y ) should return true if X is ancestor of Y. The simplest case of someone being an ancestor of someone else is where they are a person's parent.

This rule says that a person X is an ancestor of person Y if person X is a parent of person Y. Okay now what happens if the person X is actually, say, a grandparent of person Y. Then the rule above would return false. To get around this we define the following-

What we have defined here is a recursive rule, a rule that calls itself. Consider the two rules together.

These two rules form what is known as a procedure. What the second rule does in simple terms is to check and see is there another person, Z, who may be the parent of Y.

The first rule we defined is the base case. The second rule attempts to move towards this base case. If this base succeeds the procedure succeeds. The second rule is known as the recursive case.

This section is quite complicated. To understand it you have to remember that programming in Prolog is largely declarative and that the Prolog system consists of a search mechanism and a database. Knowing how Prolog responds to our queries involves knowing how the search mechanism works behind the scenes.

Place the ancestor/2 procedure in the file 'family_tree.pl' and consider the following interactions. What happens when I ask?

The system responds with yes. We'll now see why it does. The following procedure is in the database* -

* You can check by using listing with the procedure name as an argument e.g. listing( ancestor ).

When we enter the query "ancestor( bob, pat )" Prolog attempts to match it with the information it has in the database. ( Remember how in the last tutorial we looked at some simple matching. Prolog uses this mechanism to check your query against information in the database ). It should match with -

When it matches it instantiates the variables. Thus, X gets the value bob and Y gets the value pat. The Prolog system then attempts to find the existence of parent( bob, pat ) in the database. As it exists it returns true.

[ When we say it attempts to find the existence of parent( bob, pat ) - it looks at the first parent/2 structure in the database and attempts a match. If this succeeds it stops. If it does not it checks the next parent/2 structure in the database. It will continue to do this until it finds a match or has checked all the parent/2 structures. If no match is found the rule will fail.

Remember that a rule has 2 parts a head and body. The head is only true is the body is true.]

Now what happens when I ask?

Again, it attempts to match the query we have given it with information it has in the database. It is first matched with the

...rule. X is instantiated to cathal and Y is instantiated to pat. Then the database is checked to see if there exists a fact - parent( cathal, pat ). There is not. So this fails. At this stage Prolog does not stop. It attempts to resatisfy the query you gave it. It does this by moving onto the next ancestor rule. ( If this rule was not here the query would fail at this stage and 'no' would be returned ). This is the recursive rule -

Again Prolog instantiates the variables. So X is instantiated to cathal and Y is instantiated to pat. Now what is interesting here is that Prolog will now attempt to instantiate Z. It tries to match parent( cathal, Z ) with other parent structures in the database. The first match it should make is with parent( cathal, bob ) so Z is instantiated to bob. This is then passed to ancestor( Z, Y ) so the following is called ancestor( cathal, bob ).

What does Prolog do now? It attempts to match ancestor( cathal, bob ) with a structure in the database. It first attempts to match it with

Thus X is instantiated to cathal and Y is instantiated to bob. Putting these values in the parent structure we get parent( cathal, bob ). Prolog again attempts to match this with information in the database. As the facts parent( cathal, bob ) exists it returns true for the match. This results in the original query - if you can remember that far back at this stage - in succeeding and printing a trite 'yes'.

You do not have to understand exactly what is going on but you should at this junction realise that Prolog does a huge amount of work behind the scenes.

After that rather turgid section you should try the following queries:

The first query is equivalent to saying 'can you get me an ancestor of pat?'. If you want to see how many ancestors Prolog can retrieve for pat type a semicolon instead of a return after every answer Prolog gives you. ( Try it now! ). The second query is equivalent to saying 'does cathal have any descendants'. This is to do with the relationship between having an being a descendent. If you have an ancestor - you are that ancestor's descendant.

To make this more clear you could define a rule 'desecendant/2' which uses 'ancestor/2' - 

This means we don't have to define a whole new recursive procedure for descendant we can just define it in terms of its relationship with ancestor.

Here is an example of how we use recursion to repeatedly carry out an action. Place the following in a file and load it into SICStus.

There a few things in this example that will be new to you. Firstly though lets examine what's familiar. We have a procedure and it's recursive, as it calls itself. You should notice that it has two cases: the base case and the recursive case.

What is new is the '_' underscore symbol. This is known as the anonymous variable. We put this in when we aren't interested in returning the value of variable but still wish to use a variable.

'read/1' is another built in predicate it reads in an input and assigns it to the argument. Before you use 'read/1' there are a few things you should note- it will only read in Prolog data objects. You must finish your input with a full stop before you hit return.

This procedure will prompt the user for input. When the user types 'end' the loop will stop. The procedure will keep prompting you for a response until you type end or make a mistake and forget to put in a full stop at the end of your input - you'll get an error if something goes wrong.

To run the procedure type -

It doesn't really matter what you type where 'go' is just as long as its an atom. If you type a variable in here instead of an atom Prolog matches it with the base case and returns true. So you are never actually prompted. Try it if you want...

Exercises Tutorial 3

1. Write a procedure that asks the user to enter a word and

What you should have learned from this tutorial -

One of the best ways to understand how Prolog works is too use trace. This will give you a rough idea what Prolog is attempting to match and how control passes down through a procedure.

Author - Jer Hayes - 2000