|
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 Central to Hong Kong Polytechnic
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 MTR or KMB
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".
** Note: may use different connective symbol to represent "and"
by other Prolog interpreter.
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).
because Prolog would assume that you wished everything after the '%'
sign until you press the "return" key to be a comment (and thus ignored).[+]
In this case, Prolog would stop and give you an error message somewhere
because you have said there would be a body to this rule (by typing
":-") but haven't included a full-stop at the end.
So the complete procedure is:
% 1
route(Start, End) :-
path(Start, End).
% 2
route(Start, End) :-
path(Start, Via),
route(Via, End).
|
