Let me demonstrate how this works in a particular case. Imagine you are an administrator of a youth hostel with several bedrooms, each of which contains some bunks and/or beds. Each day you have the difficult problem of working out who should sleep where. Residents of the hostel usually have special requirements (e.g. cannot use a top bunk) and special attributes (e.g. heavy snoring). To come up with a successful allocation of people to beds all these things need to be taken into account. What you would like is a program that produces optimal bed-allocations automatically.((This problem scenario was first described to me by Sue Greenop.))
The requirement, then, is for a program that performs `optimal bed-allocation'. How can we produce such a program? At first sight it seems as if the problem is very complex. It is not at all obvious where we should begin trying to write the code. This is where stepwise refinement comes in.
To use the technique we should first try to decompose the main problem into some independent subproblems. If these subproblems are going to involve operating on some form of data-structure then we have to decide exactly what the form of these data-structures will be. With most problems, there will be many equally good decompositions. It does not really matter which decomposition we come up with, as long as we come up with one.
The problem we are intested in is `bed allocation'. That is to say, we need a program that can allocate one person to one bed taking into account preferences, constraints etc. We might decompose this problem into two subproblems, namely `obtaining the personal details of the person in question' and `finding a suitable bed allocation for that person'. One of the attractions of this particular decomposition is that it produces one subproblem (that of obtaining the personal details) that looks as if it will be relatively easy to implement. Once we have decided what details we want, all we have to do is write a procedure that prints out questions, and uses `readline' to read in the answers.
With these assumptions in mind, we might decide to record personal details in the form of lists, each of which has four elements. The first element is the name of the person in question. The second list contains the person's personal attributes (with the word `gives' tacked on the front for clarity). The second element lists the desired room/bed attributes (with the word `wants' tacked on the front). And the third element lists the room/bed attributes that are not wanted (with the word `hates' tacked on the front). An example of such a list is
[richard [gives snoring] [wants window locker] [hates stairs cat_owner] ]Once we have decided how to store personal details we can construct a procedure to interactively discover someone's personal details very easily. Assuming that all personal-details lists will be stored in a big list called `current_residents' the definition of the procedure (called `add_new_resident') would look like this.
vars current_residents;
[] -> current_residents;
define add_new_resident -> name;
vars name gives wants hates;
[Name?] ==>
readline() -> name;
[Attributes?] ==>
readline() -> gives;
[Positive requirements?] ==>
readline() -> wants;
[Negative requirements?] ==>
readline() -> hates;
[[^name
[gives ^^gives]
[wants ^^wants]
[hates ^^hates]
] ^^current_residents] -> current_residents;
enddefine;
This procedure has no input variables but it does have an output
variable. The value returned in this output variable is just the name of
the resident whose details are obtained by the procedure. (This is
useful as we will see later on.) The procedure works in a very
straightforward way. It prints out a request for information and then
uses `readline' to read in the response. (Of course we are assuming here
that the user will type in the correct labels for the various
attributes. This is somewhat unrealistic.)With this procedure, we have effectively solved one of the two subproblems that we produced in our initial decomposition. The other subproblem was `finding a suitable bed allocation for a given person' (i.e., a person whose details have already been recorded). This turns out to be a somewhat more complex subproblem. Again it is not obvious how to go about implementing it. This tells us that we should try to decompose into some further subproblems (i.e., some `subsubproblems').
Clearly, each bed is potentially going to have properties that are fully as complex as the properties of residents. This tells us that beds will have to be represented by data-structures; and that before we can work out how to implement the subproblem, we must decide what these data-structures will look like.
A simple approach is to say that beds can be represented in exactly the same way as residents, i.e., in terms of a name, a list of properties, a list of desired properties and a list of non-desired properties. Of course, the idea that a bed will have `requirements' of its own is rather weird. However, as soon as a resident has been allocated to a bed, then we can think in terms of the resident's requirements becoming the bed's requirements. This way, we can measure the suitability of allocating a particular resident to a particular bed by testing the degree of compatibility between the resident's properties and those of all the beds in the same room.
Let us assume then that the data-structure for a bed will have the same form as the data-structure that we use to represent residents. Initially it will have empty `wants' and `hates' lists. An example would be
[[B 2] [gives window locker][wants][hates]]The sublist [B 3] is functioning as the `name' of a bed here, the assumption being that `B' is the name of a room and `3' is the number of a bed in that room. When we allocate a resident to a bed, then the resident's properties (wants, hates etc.) fill out the relevant lists in the bed representation. Thus allocating `fred' represented by
[fred [gives smoker][wants window][hates cat_owner]]to bed [B 2] would produce
[[B 2] [gives smoker window locker][wants window][hates cat_owner]]Within this general scheme we can record the allocation of a particular bed to a particular resident by placing a sublist in the relevant `gives' list. Thus if we allocate bed [B 2] to `richard' then we would modify the above list as follows.
[[B 2] [gives [occupant richard] smoker window locker] [wants window] [hates cat_owner] ]
In deciding whether a particular bed ([B 2] say) is suitable for a particular resident we have to decide how much compatibility there is between the properties of the resident, the properties of the bed, and the properties of the other beds in the same room. Each property of the resident that is in the `wants' list of one of the other beds in the room (and vice versa) produces an increase in compatibility. (If the bed is unoccupied then the `wants' list of the bed in question must be empty.) Each property of the resident that is in the `hates' list of one of the other beds in the room (and vice versa) produces a decrease in compatibility. So, one way to measure compatibility is to tot up the number of compatibility increases and decreases. If we end up with a negative number then the compatibility is poor. If we end up with a positive number then the compatibility is good. (In fact we might want to take a stricter approach and say that if there is any property that is both `given' and `hated' then the compatibility is unacceptably poor.)
Although this method of measuring compatibility looks feasible, it seems as if it may involve writing a lot of code. The indication is that we will have to write code that will work laboriously through all the relevant pairs of lists testing for clashes and either adding to, or subtracting from the compatibility total. Can we decompose the problem again?
Note that all the shared elements between a `gives' and a `wants' list increment the compatibility total. Similarly all the shared elements between a `gives' and a `hates' list decrement it. Thus we can decompose the compatibility-measuring problem into two subproblems. Measuring the number of shared elements in a list. And adding or subtracting these values to form a final compatibility total.
The problem of measuring the number of shared elements in two lists is a fairly straightforward sort of list-processing operation that we can implement directly. The definition of `get_overlap' shown below is one possibility. This uses a single `for' command to work through each element of `list1'. In each case it tests whether the element is a member of `list2' and increments the `overlap' variable accordingly. The final value of `overlap' (the output variable) is thus the number of shared elements.
define get_overlap(list1, list2) -> overlap;
vars i;
0 -> overlap;
for i from 1 to length(list1) do
if member(list1(i), list2) then
overlap + 1 -> overlap
endif;
endfor;
enddefine;
Using the `get_overlap' procedure we can now implement our compatibility
measure. The definition below defines a procedure called
`compatibility'. This takes 6 input arguments (2 `gives' lists, 2
`wants' lists and 2 `hates' lists) and computes a sum that is the total
of the combined gives/wants overlaps less the total of the combined
gives/hates overlaps.
define compatibility(gives1, wants1, hates1,
gives2, wants2, hates2) -> level;
vars attribute;
(get_overlap(gives1, wants2)
+ get_overlap(gives2, wants1)
- get_overlap(gives1, hates2)
- get_overlap(gives2, hates1)) -> level;
enddefine;
Once this procedure has been constructed, things begin to fall into
place. To work out the suitability of allocating a resident to a
particular bed in a particular room we have to work through all the
lists for all the beds in the given room, adding in the level of
compatibility in each case. The `suitability_of' procedure defined below
does exactly this. It takes a bed-number and a set of gives/wants/hates
lists as input arguments. It then works through all the beds in the
specified room testing the compatibility between the given
gives/wants/hates and the corresponding lists associated with the
relevant bed. The beds are assumed to be defined by the `current_beds'
list. Each element of this is assumed to be a `bed' list, as described
above. (Note that to run these procedures as a program you need to
initialise the `current_beds' variable appropriately.)
define suitability_of(bed1, gives1, wants1, hates1) -> suitability;
vars i, room1, bed_num1 bed2, gives2, wants2, hates2, comp, room2;
0 -> suitability;
bed1 --> [?room1 ?bed_num1];
for i from 1 to length(current_beds) do
current_beds(i) --> [[?room2 =][= ??gives2][= ??wants2][= ??hates2]];
if room1 = room2 then
compatibility(gives1, wants1, hates1, gives2, wants2, hates2)
-> comp;
suitability + comp -> suitability;
endif;
endfor;
enddefine;
Given the availability of the `suitability_of' procedure we can write a
procedure to produce a choice of suitable beds straightforwardly. This
procedure must iterate over all the available beds and then return a
list of all the beds associated with a reasonable value of the
`suitability_of' procedure. The following definition of `possible_beds'
does this.
define possible_beds(resident) -> beds;
vars i, attributes, gives1, wants1, hates1, level;
[] -> beds;
if [^resident [= ??gives1][= ??wants1][= ??hates1]]
isin current_residents
then
for i from 1 to length(current_beds) do
if not([occupant =] isin current_beds(i)(2)) then
suitability_of(current_beds(i)(1), gives1, wants1, hates1) -> level;
if level > -1 then [^(current_beds(i)(1)) ^^beds] -> beds; endif;
endif;
endfor;
endif;
enddefine;
The `possible_beds' procedure implements one of the subproblems we are
currently focussing on, namely that of offering a choice of beds. What
of the other subproblem? This involved actually implementing a particular
choice, i.e., updating the data-structures so as to show that the choice
has been made. When we allocate a particular bed to a resident we have
to add the data from the resident's gives/wants/hates lists to the
corresponding lists in the bed representation. This can be achieved by
finding the right bed representation, digging out the gives/wants/hates
lists and joining them to the corresponding lists for the resident using
list constructions containing double-hats. Once we have formed the
joined lists we can assign them back to the relevant position in the bed
representation. The definition of `allocate_bed' performs this operation
making use of the `isin' command and the `it' variable.
define allocate_bed(bed, resident);
vars room, bed_num, gives1, wants1, hates1, gives2, wants2, hates2, bed_entry;
bed --> [?room ?bed_num];
if [^bed [= ??gives1][= ??wants1][= ??hates1]] isin current_beds then
it -> bed_entry;
if [^resident [= ??gives2][= ??wants2][= ??hates2]]
isin current_residents then
[gives [occupant ^resident] ^^gives1 ^^gives2] -> bed_entry(2);
[wants ^^wants1 ^^wants2] -> bed_entry(3);
[hates ^^hates1 ^^hates2] -> bed_entry(4);
[we have allocated bed ^bed to ^name] ==>
else
[There is no resident called ^resident registered] ==>
endif;
else
[Bed ^bed is not available] ==>
endif;
enddefine;
This procedure implements the one remaining subproblem. Thus to produce
a program that performs the original problem, all that remains is to
write a procedure that orchestrates the various procedures we have
written. The definition of `interact' shown below uses a `for' command
with a very big number to `endlessly' loop through a given interaction.
Within this interaction it calls the `add_new_resident' procedure to
read in the details of a new resident. The value returned by this
procedure (the name of the new resident) is then assigned to the `name'
variable. A list of possible beds is obtained (using the `possible_beds'
procedure) and presented as a menu to the user. The user's choice is
then read in (using `readline') and implemented using the `allocate_bed'
procedure.
define interact;
vars i name, beds;
for i from 1 to 99999999 do
add_new_resident() -> name;
possible_beds(name) -> beds;
if beds = [] then
[Sorry we cannot accommodate you at the moment] ==>
else
[Please choose a bed from the following ^beds] ==>
readline() -> bed;
allocate_bed(bed, name);
endif;
endfor;
enddefine;
Obviously, there are many problems with the program we have written
here. However, it does implement the problem that we originally
envisaged. The point to note is that we wrote the program by
decomposing the problems---working out the shape of data-structures
where necessary---until the point at which we had subproblems that could
be implemented straightforwardly. If you stick to this methodology you
should be able to tackle almost any programming problem.
Another important thing to remember is to use comments wherever possible to explain what the program is doing. Comments are just bits of text that appear between the special markers `/*' and `*/'. POP-11 ignores everything between these markers so you can write whatever you like. A fully commented version of the `interact' procedure might be as follows.
define interact; /* top-level procedure that `talks to' the user */
vars i name, beds;
for i from 1 to 99999999 do /* set up an `endless' loop */
add_new_resident() -> name; /* get person's name and details */
possible_beds(name) -> beds; /* work out possible beds */
if beds = [] then /* print out an apology */
[Sorry we cannot accommodate you at the moment] ==>
else /* print list of possible beds */
[Please choose a bed from the following ^beds] ==>
readline() -> bed; /* read in the choice */
allocate_bed(bed, name); /* allocate the bed */
endif;
endfor;
enddefine;
phone_service(); ** HELLO, THIS IS THE PHONE BOOKING/ACCOUNTING SERVICE ? 15 minutes at 0.15 ** WHAT IS YOUR NAME? ? chris ** OK, I HAVE RECORDED THAT IN THE DATABASE ? how much have I spent so far ** YOU HAVE ACCUMULATED COSTS OF 3.29 ? can I book a call for Monday 1200 ** BOOKED ? how much has fred spent so far ** fred HAS ACCUMULATED COSTS OF 8.92 ? who has spent the most ** jill HAS ACCUMULATED COSTS OF 15.23 ? print statistics ** [[jill 15.23] [fred 8.92] [jack 7.02] [chris 3.29] [julie 0.34]] ? print bookings ** [[chris Monday 1200][jill Thursday 1900][jill Friday 1900]] ? bye ** BYE chrisIn doing this exercise you should first make notes showing how the main problem can be decomposed into subproblems. These notes should show at what point it becomes essential to work out the form of the main data-structures. They should also give the arguments in favour of the data-structures you actually use. Once you have these notes you can proceed to the second part of the exercise which is to actually write and test the program. (The notes should be submitted along with the program.)