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. ------