The Prolog Tutorial:

Lists & Arithmetic

At this stage in the tutorial you should be able to construct simple facts and rules. You also should be able to write simple recursive procedures. 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 and rules.

The aims of this tutorial:

• To introduce lists.
• To introduce simple list processing.
• To introduce some of the Prolog arithmetic operators.

In Prolog we can represent lists in two ways. The first which is rarely used and is not mentioned after this point is to use the dot functor '.'. The second takes this same structure but displays it in a more helpful way. A list is made up of a number of elements between the characters '[' and ']'. This is merely cosmetic. Internally lists are still built using the dot functor but we don't have to worry about this except that we must remember lists are structured objects. The following are lists -

The last is known as the empty list. Don't confuse this with an array - there are no arrays in Prolog. Note, that we can build a list from any of the data type objects. Also, as mentioned above a list is really a structured object. So we can have a list in another list - as structured objects can be made up of other structured objects.

All list manipulation in Prolog is done by using the separator operator which is a vertical line, |. This will separate a list into an element and another list or several elements and another list. Enter the following and see what response you get.

In last input you entered you should realise that a list with apparently one element is really on element plus the empty list.

When processing a list we generally want to examine each element in the list one at a time. The general form of this is -

Where the procedure 'process _element/1' would be defined by the user. This is of course a recursive procedure.

To check if something is in a list we will a procedure with 2 arguments one for the item we are looking for and the list itself. The simplest case of something being a member of a list is if it is the head of a list -

Clearly this would only work if the item was the first element in the list. So we define a recursive rule the removes the head each time it is called and calls the procedure again with just the tail.

Thus a viable membership procedure would be the following -

In this case we want the procedure to stop when the item is found in the list. The procedure will fail if the list becomes empty and the item has not been found. This is what we want as this signifies the item was not in the list.

Remember that the last element of every list is an empty list so to check that something is a list we really just have to check that it's last element is a list this is done as follows -

At this point you should open a new file, call it something like "my_lists.pl" enter the procedures member/2 and is_list/2 and test using SICStus, e.g.

 Lets take a short brake from lists for a moment to see how Prolog deals with arithmetic. Remember that the equals sign is used for matching. So the following -

just results in X being instantiated to 1 + 2. To get Prolog to carry out arithmetic we use 'is'

This should print out X = 3

Here are some of the pre-defined operators in Prolog

Try some of the following - be wary of the first one! :

( This doesn't actually work. SICStus does not have a predicate div. Different versions of Prolog may or may not have this command. The SICStus equivalent is // ).

If we want to compare the values of numbers we use the following comparison operators.

Try some of the following:

We can use some of these operators to define some interesting list procedures.

Suppose we wished to calculate the length of a list. We can do this by counting the number of items in a list. So lets define a procedure my_length/2 that will take an input of a list and return a number - the length of the list. If the list is empty the number returned should be zero and if the list is not empty then we can calculate it by saying that is the length of the tail of the list + 1. So we get:

Put this procedure into the file 'lists.pl' and test it. Use trace to see what Prolog is doing behind the scenes.

Exercises

1. Write a procedure sum_list/2 that takes a list and returns and sums the elements in the list. Test it by giving it a list of integers. ( Hint: Adapt the my_length procedure ).

| ?- sum_list( [ 1, 2, 3], N ).

N = 6

Sometimes we may wish to write an auxiliary procedure that actually does most of the work . This is generally true when we have one procedure with two arguments but our solution needs a procedure with three arguments. For example look at this definition of reverse/2 which takes a list and reverses the order of the elements.

Here we could really just use aux_reverse/3 to reverse the list as this is the procedure which actually does the work. For the sake of neatness though we often end up creating 'wrappers' around these procedures turning them in auxiliary procedures. The wrappers generally do nothing but gather a tidier number of arguments and pass them into other procedures.

Generally when we are carrying out list processing we are only interested in the top-level of the list. When we have a list within a list we have two levels. When we use the template for list processing that was outlined in the opening section of this tutorial we are only dealing with the top level. Sometimes we may wish to examine below the top-level. For example consider a procedure called sum_all/2 that would sum not only a list of integers but would also sum a sublist of integers. So it would generate a response like -

| ?- sum_all( [ 1, [2, 3], 4, [ 5 ] ] , N ).

N = 15.

How would we define this. Lets consider this abstractly, the template in the first section was

We need to add something to this. When we get to the point process_element. We could define to versions of this one for lists and one for non-lists.

If you haven't attempted Exercise 1. Please attempt it now before going any further.

The procedure we developed in this exercise was sum_list/2. It was defined as -

To process a sub_list in this case we need to define a new case. One that checks to see if something is a list and then processes it. This case is a separate rule. We would define sum_all as

Load this into the lists.pl file and test it along with sum_list. Try some of the following inputs:

Often when processing lists we only wish to perform actions on certain elements. Consider the procedure sum_list/2 which adds up a list of integers ( at the top level ). Now for this to work properly we have to make sure we pass in only integers. It would be handier if the procedure would only add those elements that were integers and did nothing to the other elements.

This is actually like the sum_all/2 procedure in a way because what we want to do is add a new case. Here though the new case will do nothing ( that is, will not add anything ) when the element is not an integer. We can write this as -

The last rule is the skip case. It merely moves the list onto the next element. The test as to whether something is an integer or not is performed by integer/1, another built-in predicate.

Exercises Tutorial 4

1. Write a procedure that will take a list and print out any integers in the top level of the list ( i.e. ignores integers in embedded lists ). This procedure will be called read_int/1. It should work like this:

read_int( [ a, b, 1, 2, [ 3, 4], 5 ] ).

1

2

5

2. Write a procedure, read_int2/1, which does print out integers in embedded lists. So it should work like this:

Answers

The aims of this tutorial:

• To introduce lists.
• To introduce simple list processing -

• To introduce some of the Prolog arithmetic operators.

The built-in predicates that were introduced in this tutorial were:

integer/1,

Author - Jer Hayes - 2000