TEACH PROPOSALS                                    Aaron Sloman Nov 1988
                                         Modified Aaron Sloman, Nov 2000

                 Guidance on producing project proposals
                 ---------------------------------------

These notes are intended primarily for people who are on their first
programming course, but they may be useful for others.

The examples given assume you have read TEACH * RIVER, which describes
the problem a farmer has in getting fox, chicken and grain across a
river in a boat that carries only two objects.

CONTENTS (In VED use "ENTER g" to access required sections.)

 -- Introduction
 -- Selecting a topic
 -- Defining objectives: ontology
 -- -- Contents of the ontology
 -- -- The specification of the ontology
 -- -- Internal and external semantics
 -- Defining objectives: the desired behaviour (scenario)
 -- A behavioural specification
 -- Working out a design
 -- -- Choosing a programming language
 -- -- Choosing representations
 -- -- Deciding which procedures are required
 -- Producing a first draft plan
 -- Producing a first draft design
 -- Design test programs
 -- Possible projects described in TEACH files
 -- Further reading

-- Introduction -------------------------------------------------------

A programming project has a number of different stages which can be
roughly characterised as follows

    - selecting a topic area
    - reading relevant literature
    - defining what the program is to do, i.e. the high level goals
    - producing a written specification
    - working out a design
    - implementing the design (i.e. writing the program)
    - testing the program
    - modifying the design in the light of experience
    - modifying the specification and high level goals in the light
        of experience
    - evaluation (assuming the program works)
    - writing up the project

The different stages need not occur in that order - they can often be
interleaved. In fact, it is often necessary to do some exploratory
programming to work out what the high level goals should be. Sometimes
the final stages of a design are not worked out until the implementation
is nearly finished and you have learnt what is practically feasible.

This file elaborates on some of the earlier parts of this process. Other
teach files referred to below give guidance on later work.


-- Selecting a topic --------------------------------------------------

You can find some suggestions for project topics in

    TEACH POP11_PROJECT

There are also some old teach files from Sussex university giving lists
of topics chosen by students in previous years, and some others that
were suggested as possible, but may not have been chosen.

See the files
    TEACH PROJECTS,  TEACH OLDPROJECTS,

Some of the project topics listed are suitable for elementary courses,
and some for more advanced courses. You may need the advice from your
tutor or a demonstrator on avoiding topics that are too ambitious.

It can be a good idea to choose a topic by starting from a programming
exercise that you did during the course, and then extending it.

The topic should be related to the content of your course. That may mean
simply using the techniques taught in the course.

For an AI course it is not appropriate to chose a project that is not
concerned with AI techniques. For example, a program that simply applies
standard statistical to a set of numbers would be less appropriate than
a program that attempted to teach elementary statistics, or a program
that attempts to find patterns that humans can see when the numbers are
displayed as a graph.

-- Defining objectives: ontology --------------------------------------

At a very early stage you need to be clear about what your program is to
do. This means being clear about the kinds of objects it is concerned
with (the ontology) and the kind of things it will do with them
(possible scenarios).

For example, if you were planning the design of a program something like
LIB RIVER, described in TEACH RIVER and TEACH RIVER2, you would need
to include in its ontology the following objects that the program
is concerned with:

    man, fox, chicken, grain, boat, river, left bank, right bank.

You'd also need to say more about each of these to describe their
properties, relationships and events in which they can occur.

E.g. relations could include "at", "inside", "same side". Events could
include getting into the boat, getting out, crossing the river, eating.

-- -- Contents of the ontology

At an early stage you should try writing down a brief summary of the
ontology of your program, covering the following topics.

    What kinds of objects your program is concerned with
        E.g. a river, a boat, farmer, fox, chicken, grain, etc.

    What kinds of properties the objects can have
        E.g. chicken would like to eat grain, boat holds only two
            things, only farmer can row the boat, etc.

    What kinds of relationships can exist between objects
        E.g. The boat can be a left or right bank. The farmer can be
        at left or right bank or in the boat. etc.

    What kinds of changes or processes can occur (usually changing
        properties or relationships).
        E.g. the farmer can put an object into the boat, so that
            it is no longer on the bank, but in the boat. The
            farmer can get in, so that he is no longer on the
            bank but in the boat. The boat can be made to move
            from left to right bank, or vice versa.

    What the PRECONDITIONS are for the various processes.
        E.g. the boat can't move unless the farmer is in it. The
        farmer can't put something in the boat unless it is empty
        and he is on the river bank on the same side of the river
        as the boat, etc.

    What the consequences of various processes are.
        E.g. if the chicken is left alone with the grain it eats it.

    What GOAL states there are (if it is a puzzle solving program)
        E.g. the problem is solved if everything is on the right
        bank of the river.

The description of the ontology should be INDEPENDENT of how your
program is going to work. That is, it should not assume any particular
programming language or choice of data-structures, variable names,
procedures, etc.

In other words the OBJECTS in the ontology are NOT objects in the
program itself, but in the domain to which the program is applied.
(The objects in the program could be lists, words, numbers, etc.)

-- -- The specification of the ontology

The specification should be a document that could be read by someone
who might then choose a different implementation from yours. So for
example in defining the ontology you should not say that you are going
to use the Pop-11 database or lists, since in another program a
different mechanism could be used to represent relationships. Similarly,
the description of the ontology should not mention names of procedures
or variables you are going to use. These are IMPLEMENTATION details.

You should try to write your aims down in such a way that someone who
has not done the same course as you will understand them. Try out your
description of the ontology, and the scenario (see below) on a friend
who is not taking the same course as you.

-- -- Internal and external semantics

Note: the ontology is concerned with things in the world outside the
computer, things that you are simulating or interacting with. (This
could be called the "external semantics" of the program.)

You will later need to think about things IN the computer that
represent the things in your ontology. The things in the computer might
be lists, words, strings, numbers, procedures, etc. These objects and
the operations on them will constitute the "internal semantics" of your
program.


-- Defining objectives: the desired behaviour (scenario) --------------

It is not enough to say which objects the program is going to be
concerned with. You also need to say what its BEHAVIOUR will be, i.e.
what it can do.

You will need a clear set of behavioural objectives before you start
designing the program, though you can modify the objectives in the light
of the design and implementation if necessary.

E.g. In the case of LIB RIVER there is a set of commands available to
the user, including one to set up the initial state, and other commands
to make the state change. After each command the program checks the
consequences, and, if necessary, prints out an indication of what has
happened, including an error message if an illegal state has been
produced. These commands and the actions they produce define the
behavioural capabilities of the program.

A SCENARIO is a brief sketch of an imaginary interaction with the
program. You should produce at least one scenario before you start
writing the program. Include "interesting" episodes in the scenario,
including for example an example description of how your program will
deal with mistakes made by the user. For example a scenario for the
river world might describe a user setting up the world, giving some
commands, being told that some commands are illegal, asking questions
and being given answers, etc. (An example scenario for a project
proposal can be found in TEACH TRAIN_CLERK)

In your scenario description make it clear what is typed as input, what
the program does with it, and what sort of output it produces. Do not
describe the scenario in terms of any particular implementation.

    E.g. don't say that it will remove something from the Pop-11
    database: instead say that it changes the representation of the
    situation so that the animal is no longer on the left bank,
    but is now in the boat.


-- A behavioural specification ----------------------------------------

Each scenario describes only one possible behaviour for the program.
Ideally it would be useful to find a general description for all
possible behaviours. This is often very difficult, and one area of
research in computer science and software engineering is finding
suitable languages for precisely describing required behaviours.

(If we have a precise specification of the required behaviour of program
then it may be possible to have programs that automatically create
software to match the specifications, or to check whether programs
written by people do match their specifications. But that is a long term
research goal.)

For an introductory programming course it is not expected that you
should be able to give a precise and general specification of the class
of possible behaviours. That makes it all the more important that you
have one or two scenarios illustrating what the program is supposed to
be able to do.

In some cases you can specify required behaviour by giving some sort of
grammar. E.g. you can say that the program will accept commands typed in
according to a particular grammar (see TEACH GRAMMAR), or you can
describe the possible actions of the program by giving a grammar for the
actions. The first section of TEACH MSBLOCKS shows the grammar used
by the "pop11 +msblocks" and "pop11 +gblocks" demonstration programs.

In addition give enough information to specify how varied the required
behaviour is and what it is NOT supposed to be able to do (where the
reader might otherwise form wrong expectations).

In other words, try to make clear the LIMITS of your program's intended
abilities.


-- Working out a design -----------------------------------------------

Once you are clear about the objectives of your program as described
above you can start designing it.

-- -- Choosing a programming language

Some aspects of the design will be independent of the programming
language used: e.g. how the program is broken down into modules, which
information is used by each module, what sort of communication occurs
between modules.

Some aspects of the design will be specific to the programming language
used, e.g whether lists are used or arrays, or some other type of
data-structure.

Which programming language you should use may be determined by the
course you are doing. E.g. for a Pop-11 course the project will have to
use Pop-11, for a Prolog course it will have to use Prolog. But for some
projects you may be free to choose the language, though in general an AI
language is required for AI projects. Your design should indicate which
language you are going to use, and why. If in doubt consult your tutor.

-- -- Choosing representations

Your ontology will specify what the program is about, but not how the
objects, their properties, relationships, and changes are to be
represented in the program.

First decide how to represent objects, properties and relationships.

Often it is useful to use the Pop-11 DATABASE and its associated
procedures (ADD, REMOVE, PRESENT, etc) for this purpose, as illustrated
in TEACH RIVER2. However, for some purposes you may need to use other
structures, such as lists, strings, vectors, arrays, etc. (Prolog also
includes a database, but uses a very different syntax.)

In some cases it may be appropriate to use global variables to represent
some aspect of the situation, but it is normally best to use a uniform
representation if possible, instead of having some things in the
database and some in global variables.

Global variables tend to lead to obscure programs and bugs that are hard
to track down, though they can be used if you are careful. (E.g
"database" is a global variable used in conjunction with the Pop-11
DATABASE library.)

So, for example, if you are representing the locations of the man, fox
chicken and grain by assertions in the database, such as

    [man at left] [fox at left] [chicken at right]

or, perhaps this:

    [at man left] [at fox left] [at chicken right]

don't then represent the location of the boat in a totally different
way, e.g. by a global variable "boat_at_left" that can be true or false:
instead use the database for that too.

Then the same procedures can be used for checking or changing that state
as for all the others.

-- -- Deciding which procedures are required

When you have chosen the structures in the computer that will be used to
represent things in your ontology, you can start designing the
procedures that operate on those structures. There are many different
kinds of operations that you may have to consider, including

    Setting up an initial representation
    Interrogating the database to find the answer to some question
        (e.g. on which bank is the man?)
    Removing something
    Adding something
    Checking for consistency
    Checking pre-conditions of actions
    Working out consequences of actions
    Displaying the current state on the screen

and so on.

In addition if it is an interactive program, you will have to design

    A controlling program (see TEACH RESPOND, TEACH RIVERCHAT)
    A program which
        a. reads in the user's questions, commands, etc. and
        b. checks that it is acceptable input
        c. works out what is to be done in response
    Programs to communicate information to the user, including
    describing consequences of action, answering questions, etc.

You may also  have to design various additional programs to help you
with debugging and tracing if POP11's built in TRACE facility does not
provide enough information. (See TEACH TRACE)

Note that sometimes the advice you are given to make a program more
clear and uniform in its structure will also make it less efficient.

Efficiency is important in a practical program, but in a project you
should never abandon clarity unless it is absolutely essential, e.g. if
the inefficiency is making your program run for hours instead of
seconds.

If there is any interaction with a user in your program, you should
take account of the needs of the user. E.g.

1. Make sure that any instructions are printed out in a readable format.
2. Make sure that the user does not have to do a lot of redundant
   typing
3. Make sure that any output produced by the program is clear and
   easy to interpret. If necessary use graphical output (diagrams,
   pictures, etc. See TEACH FACES for an introduction to graphics
   using POp-11).


-- Producing a first draft plan ---------------------------------------

Before you start working on the program make sure you produce a "high
level" plan (a "requirements specification") for the program, describing
the purpose of the program, the ontology of the program and one or two
scenarios that give an indication of the intended behaviour of the
program.

You should discuss the initial plan with your tutor (or demonstrators,
or fellow students). This will help you to assess whether your
objectives are realistic or not: a common problem is being too ambitious
for the time available. You may also get some useful suggestions.


-- Producing a first draft design -------------------------------------

Once you have a plan (the requirements specification) you can move on to
produce a design specification, which indicates which internal
structures and procedures will be used for the program, and which
procedures you are going to use.

In some cases you will not know exactly what is needed until you have
done some preliminary exploration trying out different techniques, or
finding out exactly what the problems are. The first draft design plan
need not commit you as regards the final design. But unless you have
some sort of clear plan initially you will not know how to begin writing
the program.


-- Design test programs -----------------------------------------------

When you have decided what you want your program to do, and have got a
design for it and have started implementing it, you should build up a
collection of test procedures, adding new tests as you add new
procedures to your program.

For example, suppose your program is going to include a procedure that
takes in a sentence asking a question then creates a list of words as
its reply your test file could include things like this:

    unless
        answer_question([where is the red block]) = [on the table]
    then
        'error in answer_question([where is the red block])' =>
    endunless;

Each time you make a significant change to your program you should run
all your tests (you can set up a file to do this) and check that they
all produce the required results. That way if something goes wrong after
a change you will discover it quickly, instead of waiting till you next
run the whole program, by which time the bug may have interacted with so
many different things that it will be hard to track down.

Designing good tests is not easy, however, and you should always examine
your programs very carefully and try to work through the logic of what
they do, so as to check that you have not made subtle errors.


-- Possible projects described in TEACH files -------------------------

Browse through teach files looking for ideas. E.g.

TEACH * POP11_PROJECT
    Lists possible topics in some detail.

TEACH *DATATHINK
    Describes a project concerned with a program that stores information
    in the database then draws new conclusions from it. (Fairly trivial)

TEACH *RIVER2
    Describes a project to implement your own version of LIB RIVER
    (Fairly trivial)

TEACH *RIVERCHAT
    Describes a project to extend an Eliza-like program so that you
    can give commands like "Put the fox into the boat" instead if
    having to type in Pop-11 commands. Potentially hard if you extend
    it to use a grammar rather than the pattern matcher.

TEACH *TRAIN_CLERK
    Explains what is involved in designing a project and writing
    a proposal, using the example of a mini-project to simulate a
    very simple-minded railway station clerk.

TEACH *LONDON
    Shows how to use the database to represent London Underground route
    information in such a way that it can be used by a tourist guide.

TEACH *BLOCKS
    Describes a project to design a program that represents a collection
    of blocks on a table top by means of the Pop-11 database and allows
    you to give instructions to move blocks around.

TEACH * GRAMMAR
    Introduces ideas relevant to natural language processing. Some
    relatively easy projects involve designing a grammar and a lexicon
    to generate sensible sentences about something. If you want to do
    something more ambitious try TEACH * WHYSYNTAX, * ISASENT.

TEACH *SEEPICTURE
    Assumes that you have worked through TEACH TURTLE or TEACH VTURTLE
    and know how to use the Pop-11 "turtle" to create pictures. It goes
    on to show how you can use the library programs FINDLINES and
    FINDJUNCS to analyse certain pictures and store information about
    them in the Pop-11 database. A possible project would involve
    drawing a picture, then using these library programs to store the
    information, and writing an interactive program to answer questions
    about the picture, by examining the database.

TEACH * PROJECTS
    This has a list of possible programming projects for first or second
    year students doing AI courses, along with an abbreviated version of
    the advice in this file.

TEACH * OLDPROJECTS
    This is a partial list of project topics that have been attempted in
    the past. It is not kept up to date so will not include recent
    projects.

TEACH * RULEBASE
    Gives an introduction to rule-based programming

TEACH OOP, TEACH OBJECTCLASS_EXAMPLE
    Gives an introduction to object-oriented programming

TEACH FACES, TEACH RC_GRAPHIC, TEACH RCLIB_DEMO.P
    Introductions to graphics and graphical interfaces in Pop-11

-- Further reading ----------------------------------------------------

TEACH * REPORTS
    This gives information on how to write up programming assignments
    given during a course. It provides a framework for reports on
    mini-projects.

TEACH * PSTYLE
    This may be useful if you are working on a more advanced project
    rather than a mini-project for an introductory course. It includes
    suggestions about the format and contents of the report.

TEACH * PGUIDE
    General advice by Tom Khabaza on planning and doing an AI project

TEACH * PROGSTYLE
    This is a long file which gives lots of hints on programming style,
    some of them specific to Pop-11, others more general. This is
    probably not worth reading if this is your first experience of
    programming.


The COMPUTERS AND THOUGHT book by Mike Sharples et. al. describes a
number of topics that could be a basis for projects.

The book by Burton and Shadbolt, POP11 Programming For AI (published
by Addison Wesley) has more examples.

Standard textbooks on AI include many more examples, some of them
described in terms of other languages. See, for instance:

Patrick H Winston,
    Artificial Intelligence
    Reading, Mass: Addison-Wesley.
    Third edition 1992.

Elaine Rich and Kevin Knight.
    Artificial Intelligence
    Second Edition, 1991.
    New York: McGraw-Hill.

Eugene Charniak & Drew McDermott,
    Introduction to Artificial Intelligence
    Addison Wesley, 1985

George F Luger, and W.A. Stubblefield,
    Artificial Intelligence: Structures and Strategies for Complex
        Problem Solving
    The Benjamin/Cummings Publishing Company Inc.
    Second Edition, 1992.

Nils J. Nilsson,
    Artificial Intelligence: A New Synthesis,
    Morgan Kaufmann, San Francisco. 1998

Stuart Russell & Peter Norvig
    Artificial Intelligence, A Modern Approach.
    Prentice Hall, 1995

You may also have been given additional references in handouts.


--- $poplocal/local/teach/proposals
--- University of Sussex 1988. University of Birmingham 1998

--- $poplocal/local/teach/proposals
--- Copyright University of Birmingham 2000. All rights reserved. ------
