Subject: Re: Pointers

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 8 Mar 2000 12:22:42 +1300 (NZDT)

From: Fraser Mathieson {Students} <[email-masked]>

	I am trying to write a Prolog program which consist of a train timetable, in
	the form:
	
		train(['Stirling',849,'Glasgow',935]).
		train(['Stirling',905,'Edinburgh',958]).
		train(['Aberdeen',705,'Dundee',825,'Perth',847,'Stirling',
		919,'Glasgow',950]).
		train(['Stirling',935,'Edinburgh',1028]).
	
This looks _awfully_ like a homework problem.
I note a couple of problems with the data structure.

(1) Presumably 849 is *supposed* to mean "49 minutes past 8 am".
    But what it *does* mean is "eight hundred and forty-nine".
(2) There are pairs in these lists, and it matters that they are
    pairs, but they are not written as pairs.
(3) Real train routes have _names_ that individuate them, but these do not.
(4) The sequence of stops for a train _should_ be encoded solely in the
    times, but it is secondarily encoded in the order of the elements in
    the lists.  IT IS NOT CLEAR WHETHER THAT IS ACCIDENTAL OR ESSENTIAL.
    I suspect from the problems below that it is actually an essential
    property of the data.

Good (null-free) relational data base design is so often good Prolog design.

	Two programs I have came across are:
	
	1. Displaying the next train from one town to the other.
           Here, the user must type in the goal:
	
			?- nextTrain(City,TimeNow,DepTime,NextStop).
	
Two things.  First, good Prolog style uses MultiWordVariableNames
but multi_word_predicate_names.  "nextTrain" is just _so_ ugly.
Second, you should not be talking about what the user does, but what
the predicate MEANS.  And you have not explained what this predicate
MEANS.  In particular, which City is it?  

		e.g. the next train from Stirling to Edinburgh be at 0905.
	
But this is not an example until you have shown us how this is encoded
as a goal.  I shall assume that

	next_train(FromCity, TimeNow, DepartureTime, ToCity)

is to be true if and only if
    - FromCity is a city name,
    - ToCity is a city name,
    - TimeNow is a number representing a time,
    - DepartureTime is a number representing a time,
    - TimeNow < DepartureTime (should that be =< ?)
    - there is a train that leaves from FromCity at DepartureTime for ToCity
    - there is no T such that TimeNow < T < DepartureTime such that
      a train leaves FromCity for ToCity at T,
    - and importantly, this is talking about _direct_ routes, involving
      no connections.

This would be so much simpler if we had a predicate

	departure_arrival(DCity, DTime, ACity, ATime)

meaning that a train departs from DCity at DTime and arrives at
ACity at ATime.  (I told you the initial design was poor.)  We can
convert to this form quite easily:

	departure_arrival(DCity, DTime, ACity, ATime) :-
	    train(BadlyDesignedList),
	    append(_DontCare, [DCity,DTime,ACity,ATime], BadlyDesignedList).

Now do you see why it is important to know whether the ordering of the
elements in the lists is accidental or essential?  If the ordering is
essential, so that we can rely on it, this code will work.  But if it
is accidental, so another data set might use a different order, then
we'll have to fix the ordering in this predicate, typically by sorting.

Now the problem is quite simple:

	next_train(DCity, NTime, DTime, ACity) :-
	    departure_arrival(DCity, DTime, ACity, _Atime),
	    NTime < DTime,
	    \+ DTime2^ATime2^(  % ^ is existential quantifier, \+ is fail_if
		departure_arrival(Dcity, DTime2, ACity, ATime2),
		NTime < DTime2, DTime2 < Dtime
	    ).

This is a direct transcription of the meaning of the predicate.

There are two key insights here.
One is that we _can_ directly transcribe the meaning of the predicate into
Prolog code, once we _say_ clearly and explicitly what the meaning _is_.
The other is that we have to be willing to do that in terms of a predicate
or predicates that don't exist yet; we may need to translate from a poor
representation into a better one, or otherwise "digest" the raw data to
make the top level easier.

	2.	Showing the next train.  Here the user must type in the goal:
		
			?- showNextTrain(City1,City2,TimeNow).
	
		where it show the next direct train from City1 to City2.  Also
	showing the departure 
		time and place, and arrival time and place.  Also the predicate
	should not fail, and 	the train doesn't need to originate at the first
	city, nor terminate at the second.
	
	Could anyone out there give me some hints.
	
The single biggest hint is that you have NOT said EXACTLY what this
predicate MEANS.  What does 'show' mean?  Is City1 the departure place?
If not, is City2 the departure place?  If not, what _is_?  Same questions
about arrival place.  We are told that the predicate is not to fail, but
what if there _is_ no next direct train from City1 to City2?  What if the
next direct train from City1 to City2 is not unique?

Whatever the programming language, whatever the problem,
ALWAYS start by spelling out in some detail what you think it means.