Simple rule writing

We have created a representation of the network and we have seen some queries that might be used to find routes between two points. When the query involved finding a route via one or more intermediate nodes, it became somewhat tedious having to specify all the intermediate nodes in a series of goals in the query. In practice, it may not be feasible to specify all the intermediate nodes because the network may be so very large that we cannot reasonably list them all or because we may not know what the intermediate nodes are. For instance, if I wish to make a rail journey from Sunderland to Birmingham University station, I don't know the route and how many changes I would have to make on the way, but I could search the British Rail timetable and try to find one.

Once we start to write our knowledge about how to find a route, we are starting to write the rule part of a Prolog program.

Looking back to the queries we tried above, what do we know about finding a route between one point and another? It seems to me that there are two main things (which are true of this network, of motorway driving or train journeys):

• Either the two points are directly linked (eg they are on the same motorway; they are on the same railway line; they are two nodes connected by one arc);
• or the points are indirectly linked (eg they are on different motorways and you have to find where the two motorways intersect; they are on two different railway lines and you have to change at a station that is served by both lines; they are connected by travelling through one or more intermediate nodes).

The first case is easily represented. Suppose we want to travel from node a to node 1. We know that a fact (path(a, 1).) exists that represents this. We have to write a rule that uses this fact. The rule must be absolutely general, which is to say that it applies to all path/2 facts in the Prolog database.

This is the point at which we introduce the syntax of the Prolog rule.

A rule has two parts: the head and the body and they are joined by the ' :- ' symbol (which can be thought to mean "if" or "is implied by").

The head can either be an atom (eg start) or a complex object (eg mammal(Animal)).

The body consists of one or more goals, like the goals we have been using in the previous examples of queries.

The rule for finding a route between two points would be:

     route(Start, End) :-
          path(Start, End).

We can read this as "it is true that there is a route from Start to End if it is true that there is a path from Start to End".

Notice that the variables have been given meaningful names. We could have written:

     route(X, Y) :-
          path(X, Y).

and obtain the same solutions. When we came to review the program in a few months time (eg when we find a bug in its working) or when someone else comes to look at the program (eg the workshop demonstrator), it would not be very obvious what the variables where intended to stand for. Always use meaningful variable names.

The second case is more involved. It says that to find the route between two points that are not directly linked, there must be an intermediate node from which there is a route to the final node. (If you want to think of it in terms of a process: find a node which is directly linked to the starting node, then find a route from the new node to the end node.)

We start by having (in this example) exactly the same rule head as with the first case:

     route(Start, End) :-
          ...

From here we have to write two parts:

• find a node directly linked to the start. This is easy as we have already done this in the first case. We cannot copy the goal of the previous rule exactly, but have to change one variable name:

       path(Start, Via),
  
  

  Don't forget the comma which (as we saw in the queries with more than one goal in the previous modules) represents "and".

• find a route from Via to End. If Via and End are directly connected, the previous rule we wrote will be true; if Via and End are not directly connected, our method is to find another intermediate node between Via and End that will get us nearer, which is what the second rule we are writing will do. Therefore the second (and final) goal is:

            route(Via, End).
  

  (Not forgetting the final full-stop.)

Putting the two parts together we have:

     route(Start, End) :-
          path(Start, End).

     route(Start, End) :-
          path(Start, Via),
          route(Via, End).

In Prolog, groups of rules and/or facts that have the same functor and arity are known as a procedure. This is the procedure called route/2. To those used to languages like Pascal, C, C++ and others, the definition above will have one outstanding peculiarity. Most computer languages will not allow you to have two different definitions with the same name. For instance, Pascal would not allow you to have two procedures with the same name and number of arguments. Prolog is not fussy, indeed it tends not to have fixed, authoritarian rules but prefers as much freedom as it can get away with - perhaps to the point of anarchy.

One final point: we shall adopt the convention of labelling the individual clauses by their position in the procedure. We will introduce each label by the symbol used for a single line comment: '%'. This can either be used at the start of a line, or as the last item in a line. For instance, the following are correct:

     % 1
     route(Start, End) :-
          path(Start, End).

and

     route(Start, End) :-          % 1
          path(Start, End).

But the following would not work as we wanted:

     route(Start, End) :-
     % 1     path(Start, End).