\documentstyle[a4,alltt]{article}
 
 
\topmargin 0.9 in         %   Nominal distance from top of paper
                          %   to top of page - 1in
\textheight 7.3 in        %   Height of body of page
\textwidth  5.25 in       %   Width of text area
\oddsidemargin  0.5 in    %   (Left margin on odd-numbered pages-1in)
\evensidemargin 0.5 in    %   (Left margin on even-numbered pages-1in)
\marginparwidth 1 in      %   Width of marginal notes.
\parindent 0.25 in        %   Amount of indent on first line of para
 
\begin{document}
 
\newcommand{\idx}[1]{}
 
\title{Supplement 2}
\author{Jocelyn Ireson-Paine}
\maketitle
 
 
\section{Introduction}
 
    These exercises start off with a mini-world of connected caves
inhabited by various creatures, rather like a computer Adventure game.
 
    If an exercise asks you to define and test a predicate, please save
the definition in a file for me to look at. Do ask for help if you have
trouble. Don't be afraid to ask; programming is an execllent way of
demonstrating that you have to make mistakes in order to learn.
 
    To test your answers, you can start the Tutor by typing
\verb#LOGIC LESSON2#.
 
 
\section{An Adventure world (PP,PE)}
 
\idx{caves world|(ee}
 
  The file DD contains the following facts, which define the world of
this game:
 
\begin{alltt}
    a is_a cave.  b is_a cave.  c is_a cave.  d is_a cave. \idx{is\_a/2@\verb#is_a/2#|ee}
    e is_a cave.  f is_a cave.  g is_a cave.  h is_a cave.
    i is_a cave.  j is_a cave.  k is_a cave.
 
    b meets a.    b meets c. \idx{meets/2@\verb#meets/2#|ee}
    d meets a.    d meets c.    d meets e.
    e meets g.    e meets f.
    i meets j.
    c meets h.
\end{alltt}
 
  These describe 11 caves called a to k, some of which are
connected. I write \verb#b meets a# to mean that there is a passage directly
connecting
b and a; so you can get from b to a, and also from a to b.
 
  Please draw a map of all the caves and their connections.
 
 
\subsection{The Wumpus}\idx{Wumpus|ee}
 
    It is possible to write an entire Adventure game in Prolog. An
important part of such a game is the map,
which we now know how to write.
In a
real game, we would also need to describe the caves or rooms in more
detail, saying for instance that room a was ``a long low
room half-a-meter long full of mud'' and that room b contained ``the
magic infra-red radio-therapeutic healing portal''. Prolog makes it
beautifully easy to do this, and you might consider it as your project:
building a complete game from the skeletal version presented here.
 
To provide that essential element of fear, most Adventure games contain,
as well as the player, a number of adversaries simulated by the game
program. A game called Wumpus\idx{Wumpus|ee}, once
popular at Cambridge, involved a world of caves and pits inhabited by
you (the player) and a Wumpus\idx{Wumpus|ee}, who would eat you if you got into the
same cave. As well as Wumpuses, we can borrow from Tolkien (why not?
everyone else does) and populate our world with dragons, orcs, narcs and
other menaces.
 
One thing we must do is to keep track of everyone's
location. This is simple;
in DD, you will find the facts
\begin{verbatim}
    dragon is_at b.
    fred is_at a.
    wumpus is_at c.
\end{verbatim}
One difference
between these facts and the ones making up the map is that in a real
game, the map stays the same, but the contents of the room can change.
In a few turns' time, the dragon, player and Wumpus\idx{Wumpus|ee} might have moved:
\begin{verbatim}
    dragon is_at f.
    fred is_at c.
    wumpus is_at g.
\end{verbatim}
It is perfectly possible to write programs that change facts in this
way. You don't yet know how: so far, the only way a fact can be changed
is if you replace or delete it. But such changes can be made under
program control, and you will eventually find out how in Lesson 7.
 
In the game of Wumpus\idx{Wumpus|ee}, the Wumpus was simulated by the computer, which
therefore needed some representation of how it would behave towards
the other inhabitants. In Logic, this is easy to state using rules.
Let's
assume that the  player, who we have called \verb#fred#, will
be eaten if he's in  the same cave as
the Wumpus. Can  you translate that statement into Logic?  That is, can
you concoct a fact that begins something like
\begin{verbatim}
    fred will_be eaten if
\end{verbatim}
and continues with a translation of ``fred is in the same cave as the
Wumpus''?\idx{Wumpus|ee}
 
This on its own might not seem very exciting. However,
combining it with techniques from Lessons 7 and 8, we could write a
Wumpus-simulator that would repeatedly move the Wumpus from one cave to
another, calling \verb#fred will_be eaten# after each move. If this call ever
succeeded, the simulator could output a suitable message, display a few flowers and
a tombstone, and then quit the game.
 
In outline, such a program would be something like this:
\begin{verbatim}
    To run the game:
        Do one game step.
        Run the game.
 
    To do one game step:
        A is the player's next action.
        Perform A, and update the world accordingly.
 
    To perform A, and update the world accordingly:
        If A is 'move to X'
        Then
        Remove the old fact about the player's location.
        Replace it by one saying he's at X.
        Check the dangers.
 
    To check the dangers:
        If the player will be eaten
        Then
        Say so, and quit.
 
    To check the dangers:
        If the player will be burnt alive (see next section)
        Then
        Say so, and quit.
\end{verbatim}
 
In this outline sketch, the predicates concerned with writing out
messages, removing and replacing facts, and quitting, are called
``command predicates''. They don't make inferences, but actually change
things. Lesson 7 shows you how to write these. The other predicates ---
getting the player's next action, and checking whether he'll be eaten or
burnt alive --- do make inferences, and you can write them with what you
now know.
 
Most Prolog programs follow this kind of pattern. On the outside sit
anumber of ``command predicates'' which perform various actions. Which
action they select is decided by the result of inference-making
predicates, such as \verb/will_be/.
 
 
\subsection{The dragon}
 
    Now, I said nothing about the dragon  in the last exercise.
Let's suppose that it's
more
deadly than  the wumpus,  because it can  shoot flame  from one  cave to
another --- but it can't shoot  further than that.
Can you translate
into Logic, ``the player (\verb#fred#) will be burnt alive if he is
in a cave that is next to the one the dragon is in''.
Start with
\begin{verbatim}
    fred will_be burnt_alive if
\end{verbatim}
 
    Test your answer by moving the player and dragon to various caves, and
asking
\begin{verbatim}
    fred will_be burnt_alive?
\end{verbatim}
 
You may have a
problem to do with unidirectionality (I won't say more than that because
it may let the game out of the bag). When you think you have tested
your new fact adequately, and you are either satisfied, or you have got
something wrong and can't see how to continue, please go to the next
section. But try this one first. To help you
not look at the next section by accident I've made sure it starts on the
next page, by interpolating some extraneous text before it.
 
%sann
%{\it In the course handout, I padded the rest of this page with a
%completely irrelevant but amusing poem, thus forcing the following
%section onto the start of the next left-hand page. To reduce printing
%costs, I have omitted this here. }
 
 
\subsection{Logic is not logic}
 
    The problem you  may have met is  that you had written a  fact such as
this:
\begin{alltt}
    fred will_be burnt_alive if
        fred is_at P and
        dragon is_at D and
        P meets D.\idx{meets/2@\verb#meets/2#|ee}
\end{alltt}
 
    Now, suppose you also had
\begin{verbatim}
    fred is_at b.
    dragon is_at a.
\end{verbatim}
then the question
\begin{verbatim}
    fred will_be burnt_alive?
\end{verbatim}
would give the answer ``Yes''.
 
    But if you had had
\begin{verbatim}
    dragon is_at b.
    fred is_at a.
\end{verbatim}
then the same question would have been answered ``No'', despite the
fact that the two caves are connected. This is because the Tutor doesn't
know that \verb#meets#\idx{meets/2@\verb#meets/2#|ee} is two-way: as explained at the end of Lesson 1, it
doesn't know that, if A meets B, then
B necessarily meets A.
 
    To get round this, you might think of adding the fact
\begin{alltt}
    A meets B if B meets A.\idx{meets/2@\verb#meets/2#|ee}
\end{alltt}
This is certainly correct, logically speaking. Unfortunately, Logic is
not a complete implementation of logic, and you can't expect that, just
because a program makes logical sense, the Tutor
will necessarily be able to run it. In fact, as some of you have already
found, adding a fact like this is likely to get the Tutor into
an infinite
loop\idx{loops!in logically correct predicates|ee}.
If you wonder why this should be, the stuff on
execution\idx{Prolog execution|ee}
order in
Lesson 5 will give you a clue. Should you now be worrying that you
now can't
rely on Logic at all, relax! Most of the exercises I set will run quite
happily, and when I think they might not, I'll give you ample warning.
 
    The standard way round the difficulty above
is to define a new predicate
called \verb#joins#\idx{joins/2@\verb#joins/2# (caves world)|(ee}, or some other suitable
name:
\begin{alltt}
    Cave1 joins Cave2 if Cave1 meets Cave2.\idx{meets/2@\verb#meets/2#|ee}
    Cave1 joins Cave2 if Cave2 meets Cave1.
\end{alltt}
Then, whenever you want to talk about one cave joining another, use
\verb#joins# and not \verb#meets#:
\begin{verbatim}
    fred will_be burnt_alive if
        fred is_at P and
        dragon is_at D and
        P joins D.
\end{verbatim}
Always using \verb#joins# in your other definitions will get rid of the
problem, and provide you with a safely symmetrical version of
\verb#meets#\idx{meets/2@\verb#meets/2#|ee}.
If you hadn't done something like that already, try it now.
\idx{joins/2@\verb#joins/2# (caves world)|)ee}
 
    Incidentally, don't be thrown by my use of multi-letter variables\idx{variables!names for|ee}
\verb#Cave1# and \verb#Cave2# in the two facts for \verb#joins#. Variables can have any
number of letters, as long as they start with an upper-case one. I just
wanted something more meaningful than \verb#X# and \verb#Y#.
 
 
\subsection{More connection predicates}
 
    Now define a predicate that begins
\begin{verbatim}
    Cave1 is_two_from Cave2 if ...
\end{verbatim}
and which is true if there is one cave between Cave1 and Cave2, thus:
\begin{verbatim}
     -------     ------     -------
     !Cave1!-----!    !-----!Cave2!
     -------     ------     -------
\end{verbatim}
 
    Does your definition allow a cave to be two from itself? Why?
What needs to be done to stop it happening?
 
    Now, do the same for
\begin{verbatim}
    Cave1 is_three_from Cave2 if ...
\end{verbatim}
There are two  ways of doing this. One uses  \verb#is_two_from# after the if;
one does not. Try them both.
 
%sann
%{\it  It is
%worth making the point that there is usually more than one way to
%define a predicate,
%and that already-defined predicates can be
%called to simplify matters. For students who have programmed before, you
%can compare auxiliary predicates with auxiliary procedures. }
 
    Finally, define a predicate
\begin{verbatim}
    Cave1 is_near Cave2 if ...
\end{verbatim}
which is true if  the caves are adjacent, {\it or}
two  apart, {\it or} three apart. You will certainly need
more than one clause for
this.
 
 
\subsection{Recursion}
 
\idx{recursion|(ee}
 
This exercise is more difficult, but worth trying. Can you write a
predicate \idx{on\_route\_to/2@\verb#on_route_to/2#|(ee}
\begin{verbatim}
    Cave1 on_route_to Cave 2 if ...
\end{verbatim}
which is true  if Cave1 is connected  to Cave2 by a path  of any length.
(If  you look  at your  map, you  will see  that not  all the  caves are
connected: i and j are joined to each other, but to no other caves. k is
joined to no others at all.)
 
    When trying this, some people say ``there are only eleven caves, so
I only need a finite number of facts: I'll just enumerate all possible
connections''. That is not what I want. I want a general rule that will
work no matter what the map.
 
  This is harder, and I don't expect everyone will manage it; but if you
were able to do the \verb#is_ancestor_of#\idx{is\_ancestor\_of/2@\verb#is_ancestor_of/2#|ee} example in Lesson 2, you should be
able to cope with this, and then you'll be well on the way to
understanding recursion. There was another example of recursion in the
\verb#flows_to#\idx{flows\_to/2@\verb#flows_to/2#|ee} predicate of Supplement 1. In the Traveller\idx{Traveller|ee} trading game of Supplement
4, you will see a use for such a predicate.
 
%sann
%{\it  Most students need a more painstaking introduction to recursion,
%and one that can't be taught without individual help. I do not insist
%that students learn to write recursive definitions at this stage: they
%aren't needed in the following sessions with the Tutor, and can be
%taught formally later. However, it's nice if some do manage to
%grasp the idea, so I try to show recursion occurring in a number of
%different contexts: even if two examples are structurally isomorphic,
%one may work for the student when another does not.}
%
%sann
%{\it  An approach that worked with one student (after introducing
%Prolog) was
%to present a
%number of \verb#is_a# and \verb#property# facts, as in a
%frame system: }
%\begin{alltt}
%    is_a( sparrow, bird ).\idx{is\_a/2@\verb#is_a/2#}
%    is_a( canary, bird ).
%    is_a( bird, animal ).
%    is_a( mammal, animal ).
%    is_a( cat, mammal ).
%
%    property( bird, legs, 2 ).\idx{property/3@\verb#property/3#}
%    property( mammal, legs, 4 ).
%\end{alltt}
%sann
%{\it and ask the student to define a predicate
%\verb#value(Class,Property,Value)# which is true if Class or any sub-class
%thereof has the given value for Property. Thus \verb#value(bird,legs,2)#
%and \verb#value(canary,legs,2)# would both be true. After I had talked a
%bit about this problem, recursion suddenly ``clicked'' for her, and she
%had no more trouble with it.
%
%Because the cave network is cyclic, students' answers to
%\verb#on_route_to#
%are likely to get caught in
%loops\idx{loops!in logically correct predicates}.
%This will also happen
%if they are left-recursive\idx{recursion!left-}.
%Again, an understanding of why this
%happens requires some knowledge of Prolog
%execution\idx{Prolog execution!knowledge of, needed to prevent loops}.
%Students will not
%be required to write such a predicate again (the trading game\idx{Traveller} comes
%with a built-in route-finder\idx{route-finding|ee} that doesn't get trapped), and so
%the problems with \verb#on_route_to#
%can be presented as just another example
%of the kind of thing that happened with \verb#meets#,
%without discussion of
%how to avoid them. \verb#on_route_to#
%is still worthwhile as an exercise in
%logic.}
 
\idx{on\_route\_to/2@\verb#on_route_to/2#|)ee}
\idx{caves world|)ee}
\idx{recursion|)ee}
 
 
\section{Representing information spatially (AI)}
 
    The following exercises demonstrate that different kinds of
information can be represented in the same way, and that methods devised
for handling one can be transferred to the others. In particular, they
emphasise the way in which methods of representing ``spatial'' things
like maps and networks can be used for more abstract kinds of data. This
is worth knowing, because we are very good at visualising things
laid out in space, and it will help greatly if we can learn to visualise
other problems in the same way.
 
    The caves world\idx{caves world|ee} uses facts like
\begin{verbatim}
    a is_a cave.    b is_a cave.
\end{verbatim}
to identify caves, and
\begin{alltt}
    b meets a.      b meets c.\idx{meets/2@\verb#meets/2#|ee}
\end{alltt}
to describe their connections.
 
  Here are three more sets of facts, each representing a different kind
of knowledge. Compare them with the clauses for \verb#is_a# and
\verb#meets#\idx{meets/2@\verb#meets/2#|ee}.
 
\subsubsection*{1}
 
\begin{verbatim}
    budget_needs_more_money      is_a  event.
    exports_decrease             is_a  event.
    production_decreases         is_a  event.
    workers_incentives_decrease  is_a  event.
    real_wages_decrease          is_a  event.
    tax_increases                is_a  event.
    exports_decrease             is_a  event.
 
    budget_needs_more_money     causes  tax_increases.
    budget_needs_more_money     causes  real_wages_decrease.
    tax_increases               causes  workers_incentives_decrease.
    real_wages_decrease         causes  workers_incentives_decrease.
    workers_incentives_decrease causes  production_decreases.
    production_decreases        causes  exports_decrease.
    exports_decrease            causes  budget_needs_more_money.
\end{verbatim}
 
\subsubsection*{2}
 
\begin{verbatim}
    composite           is_a  class.
    dicotelydon         is_a  class.
    flowering_plant     is_a  class.
    plant               is_a  class.
    life                is_a  class.
    animal              is_a  class.
    vertebrates         is_a  class.
    fish                is_a  class.
    bony_fish           is_a  class.
    daisy               is_a  class.
    crucifer            is_a  class.
    monocotelydon       is_a  class.
    mammal              is_a  class.
    cartilaginous_fish  is_a  class.
    shark               is_a  class.
 
    bony_fish           includes  shark.
    fish                includes  bony_fish.
    fish                includes  cartilaginous_fish.
    cartilaginous_fish  includes  herring.
    vertebrates         includes  fish.
    vertebrates         includes  mammal.
    animal              includes  vertebrates.
    living_thing        includes  animal.
    living_thing        includes  plant.
    plant               includes  flowering_plant.
    flowering_plant     includes  dicotelydon.
    flowering_plant     includes  monocotelydon.
    dicotelydon         includes  composite.
    dicotelydon         includes  crucifer.
    composite           includes  daisy.
    composite           includes  dandelion.
    crucifer            includes  wallflower.
\end{verbatim}
 
\subsubsection*{3}
 
\idx{noughts-and-crosses|ee}
\begin{verbatim}
    bbbbxbbbb  is_a  position.
    obbbxbbbb  is_a  position.
    bobbxbbbb  is_a  position.
    xobbxbbbb  is_a  position.
    oxbbxbbbb  is_a  position.
    xobbxbbbx  is_a  position.
    xobbxbobb  is_a  position.
 
    bbbbxbbbb  o_moves_to   obbbxbbbb.
    bbbbxbbbb  o_moves_to   bobbxbbbb.
    bobbxbbbb  x_moves_to   xobbxbbbb.
    obbbxbbbb  x_moves_to   oxbbxbbbb.
    xobbxbbbb  o_moves_to   xobbxbbob.
    xobbxbbob  x_moves_to   xobbxbbbx.
\end{verbatim}
\idx{noughts-and-crosses|ee}
 
\begin{sloppypar}
    The first example describes a small portion of what economists call
macro-economics: the relations between inflation, unemployment, etc. The
relations are not at all esoteric, in fact they are taken from
{\it There's
a Hole in My Budget} by Flanders and Swann, in which there is a
``dialogue between the Prime Minister and Chancellor, who wander round
the room in a slow inflationary spiral''. The same form could be used to
describe other economies, as well as numerous non-economic phenomena (I
have such a translation of {\it The Gasman Cometh} if anyone wants it.)
\end{sloppypar}
 
%sann
%{\it See \cite{fands}}
 
    The second example classifies living  things.
 
\idx{noughts-and-crosses|ee}
    The third example shows a subset of the possible moves and board
states in the game of noughts and crosses --- note that if extended to
be complete, it would show all possible moves, not just those in one
particular game. Board states are represented as names made up of the
latters \verb#b# for an empty square, \verb#x# for an X, and \verb#o# for an O. This
representation is not very wieldy --- later, you will
learn better ways to
represent such things. In fact, {\it lists}\idx{lists|ee}, mentioned in Supplement 6
in connection with route-finding, would be ideal for this purpose.
\idx{noughts-and-crosses|ee}
 
 
\subsection{Parents, siblings, and routes}
 
    For the first exercise, can you refer to the \verb#on_route_to#\idx{on\_route\_to/2@\verb#on_route_to/2#|ee} fact
which you were asked to write in the exercises on caves\idx{caves world|ee}. You may have
found it too difficult to write, but you can appreciate what it means.
So what would its analogue mean in each of the three examples above?
 
    Secondly, refer back to Lesson 2. In the three examples above, what
are the analogues of
(a) X being Y's parent;\idx{is\_parent\_of/2@\verb#is_parent_of/2#|ee}
(b) X and Y being siblings;\idx{is\_sister\_of/2@\verb#is_sister_of/2#|ee}
(b) X being Y's ancestor?\idx{is\_ancestor\_of/2@\verb#is_ancestor_of/2#|ee}
 
 
\subsection{Representing a neural network} \idx{neural network|(ee}
 
Now consider a neural network. You can either think about real
biological neurons in the body, or about
an artificial neural network. What predicates might you choose to
describe such a network? Sketch part of it, and write out a few facts
describing your sketch.
 
Here are some suggestions that might help:
Each
neuron has one or more inputs from other neurons and one or more
outputs. The inputs may be excitatory, or inhibitory. Each neuron has a
current activation level. And so on.
 
Incidentally, Prolog is not a good language for running connectionist
networks --- its arithmetic is too slow. However, it is an excellent
language for describing their structure.
Charles Benett, one of our past students, wrote a program called
Neuroguide, which contained part of a neuroanatomy atlas, and allowed
you to interrogate it and follow around the connections.
 
 
\subsection{Your own project?}
 
  Think of any other subject where knowledge might be represented in the
same way  --- perhaps  one you want  to work on  for your  project. What
predicates would be useful?
 
 
\subsection{Types of space}
 
\idx{spaces!types of|(ee}
    The four descriptions above are analogous to the caves one\idx{caves world|ee}. The
caves world\idx{caves world|ee} and the neural net\idx{neural network|ee}
represent {\it physical} space: by analogy, the other three descriptions
can be said to represent an {\it abstract} space, which contains {\it
points} (the events, classes, or board states), and their {\it
connections} (the causal links, taxonomic connection, or moves). When
used in applications like game-playing\idx{games!representation of states in|ee}, or other problem-solving, the
space is often called a {\it state space}\idx{state space|ee}, because
each point marks a different state of the problem.
 
    If the caves world\idx{caves world|ee} were part of this universe, each connection would
have a length. We don't represent these lengths in our exercises,
because all we are concerned with is the structure of the network. Using
mathematical terminology, we can say that we are only interested in the
{\it topological properties} --- those to which distance is irrelevent
--- and not the {\it metric properties} --- those concerned with
distance. Like the people who make London Underground maps, we ignore
distance.
 
    In some types of space, we don't just ignore distance; it has no
meaning in the first place. You can see that this is true of the
classification example, for instance; it makes no sense to say that
one of the \verb#includes# is longer than another.
\begin{verbatim}
    dicotelydon includes crucifer.
    composite includes daisy.
\end{verbatim}
So watch out when you use Logic to represent such structures in the way
that I have done. If your predicates don't say anything about distance,
is it because it has no meaning, or because you have ignored it? The
same can be asked of other properties, of course. If your program
doesn't mention some property of a situation, is it because the property
doesn't exist, or because you have ignored it?
 
    The caves world\idx{caves world|ee} and these four examples differ in other ways. The
caves world and economic model are potentially {\it cyclic} or looped,
because one point can be linked through a chain of paths or causes back
to itself. The classification and
noughts-and-crosses\idx{noughts-and-crosses|ee}
are {\it acyclic}
or unlooped. We can also say that they are {\it tree-structured},
because there is a natural way to draw them as a tree. When writing
Prolog programs, watch out for cyclic spaces: you will need
to use special techniques to write route-finders and other predicates,
otherwise they may get into an infinite loop.
 
    In the economic model, classification, neural net\idx{neural network|ee},
and
noughts-and-crosses\idx{noughts-and-crosses|ee},
the links are {\it directed}: one end is somehow
different from the other. To traverse a causal link backwards is not the
same as following it forwards. The caves world\idx{caves world|ee} is not directed. If you
are writing a predicate that describes a directed space, then take care
that you get its arguments the right way round:
\begin{verbatim}
    dicotelydon includes crucifer.
\end{verbatim}
does not mean the same as
\begin{verbatim}
    crucifer includes dicotelydon.
\end{verbatim}
 
    Finally, in the classification and
noughts-and-crosses\idx{noughts-and-crosses|ee}, the points
themselves can be {\it ordered}: it is natural to say of one class of
animals that it includes another; it is natural to say of one state of
the noughts-and-crosses game that it is later in the game than another.
There is no analogue of this with the other examples. In general, spaces
which are both acyclic and directed can be ordered in this way.
Intuitively, there is one overriding direction, and once you've followed
it, you can't get back.
 
    You will not be expected to remember these terms in the rest of the
course. The point of this section, apart from trying to make you
visualise abstract problems, and to show how they can be represented by
Logic, was to give a taste of the considerations that A.I. people face
when representing knowledge. A rich vocabulary has been developed for
describing information structures; the examples above are but a small part of
it.
\idx{spaces!types of|)ee}
 
\end{document}
