I talked earlier about a trader that might, using
begin at a random point on the board and make his way to a particularly
favourable region before starting to trade. In order to do this, we need
some means of finding a route between two squares. In fact, it ought not
to be a route; it ought to be the shortest route.
Supplement 2 asked you to write
on_route_to for the caves world. If
you were happy with recursion, you may have succeeded in producing
something logically correct. However, your predicate probably had
Traveller itself defines such a predicate:
It is true if Route is the shortest
route between Square1 and Square2. To see how it represents routes, load
TRAVELLER, and then ask the question
route( 66, 11, R ).You may notice a slight pause before the answer.
For the route between squares 66 and 11,
route will give the answer
[28, 25, 26, 35, 34, 23, 24, 17, 33, 5, 6, 7, 29, 30, 31, 32, 11]Tracing the sequence out on the board should convince you that it is the shortest route. It is represented as a new type of Prolog object, one you have not met before. In A.I., we frequently need to deal with sequences: sequences of words making up a sentence, sequences of actions making up a plan, sequences of points making up a path. This need was realised in the early days of A.I. computing, round about 1958, and gave rise to programming languages, the most famous of which is Lisp, with facilities for handling lists. Prolog also implements lists, and this is what
Lists are particularly valuable because they can vary in length. When I
I said that if your action was
move, the next
argument had to be
dummy. This is because
act has a
fixed number of
arguments, and so an argument
that's not needed by some action still has to be
there. With lists we would not have this problem: we could represent
[ move, 18 ] [ buy, coal, 20 ] [ sell, peaches, 5 ]where we only use as many places as we need.
Another situation in which lists would make sense is the noughts-and-crosses game of Supplement 2. In this, we had facts like
o_moves_to( bbbbxbbbb, obbbxbbbb ). o_moves_to( bbbbxbbbb, bobbxbbbb ).where positions on the board are represented as atoms. This is not a good way to represent them, though it's all that was available at the time. For example, if we were printing out the result of a move, we would need to produce a diagram of the board. To do this, we must, for each square on the board, be able to determine whether it contains an O or an X. Now, although we can see that the 5th letter (corresponding to the middle square, say) of
x, there's no way to discover this from within a program. Atoms are indivisible: that's why they're called atoms. However, if we represent board positions as lists
[ b,b,b,b,x,b,b,b,b ]then it is possible to write a recursive predicate that returns the Nth item of any list. We do in fact have a stock list-handling predicates, including a ``find Nth element'' one, if you need them later.
Lists are also good for representing sentences.
Later on in the course, you will see how to use lists of words in
building your own Eliza; to tell it for instance that
the response to any list
[my,R,hates,me] where R names a relative (e.g. sister) is
[tell,me,more,about,your,R], while that to
[i,like,A] where A
names an action (e.g. sailing) is
[you,say,you,like,A].It is possible
to write general rules or templates that recognise certain kinds of list
and transform them into other lists, and this gives Prolog a lot of the
flexibility you need for A.I.