TEACH TRAIN_CLERK Aaron Sloman Nov 1996 A TUTORIAL ON AN EXAMPLE MINI-PROJECT CONTENTS - (Use g to access required sections) -- Introduction -- Project specification -- -- More detailed behavioural specification -- -- Other bits of behaviour -- Knowledge required by the program -- Representation issues -- How many procedures will be needed? -- Scenario -- Towards a working implementation -- -- Defining the top level procedure -- -- Testing your top level control procedure -- -- Defining setup_train_data() -- -- Preparing to access the information in the database -- -- Using present present(list) -> boolean -- -- Iteration over the database -- -- Defining trains_departing_for(town) -> list -- -- A further exercise using foreach -- -- Recognising the form of the query -- -- Getting information from the database -- Put it all together and test it -- Limitations of this project -- Possible extensions -- Introduction ------------------------------------------------------- Here are some steps you could go through in working on a mini-project, whose goal is to design and implement a simulated railway ticket clerk. Students who are having trouble programming may find this a suitable mini-project. Or they may wish to use the ideas developed here and include them in a different project, since many of the ideas are applicable to a variety of projects involving a program that interacts with a user and answers questions based on an internal database of information about some portion of the world. For example you could use the ideas developed here to create a simulated shop-owner, or a hotel manager who accepts bookings and answers questions about which guests are where, or a lecture room manager who keeps track of who is lecturing where and arranges time table changes, etc. Many of the ideas used here are introduced at greater length in one or more of: TEACH RESPOND TEACH DIARY TEACH RIVER2 TEACH RIVERCHAT Revision teach files are TEACH STACK TEACH ARROW TEACH LISTSUMMARY HELP READLINE TEACH DATABASE TEACH FOREACH HELP IF Also the Pop-11 Primer, chapters 1, 3, 4, 6, 7. This file can be thought of as providing revision, as well as additional practice relevant to designing a project. As you work through this file you can gradually build up two files of your own. The first should be a specification of the train clerk program. Put that into a file called train_clerk The second file should contain the procedures needed for the project. You should put them into a file called train_clerk.p Later you will need to produce a report on your project. For instructions and advice on this see TEACH REPORTS. When you have started work on a file, especially a program file do ENTER fileheader to get Pop-11 to produce a header for the file. You can then edit the header to fill in missing details. Also just above each procedure that you define, you can insert a procedure heading, if you do put the cursor into the middle of the procedure definition and do: ENTER procheader -- Project specification ---------------------------------------------- LET'S DESIGN A SIMULATED TRAIN TICKET CLERK In order to do that you need to have a very clear idea of what you want the program to do. Here is a first draft specification for the program It should accept queries about where trains go to, when they go, cost of tickets, and give sensible answers. What else could be included? That is still a very vague and general specification. Can you make it more precise? You will HAVE to make it more precise in order that you have some idea regarding what to put in the program. Before reading on you can try to decide what additional information would be required for a detailed specification of WHAT the program is to do (not HOW it does it). -- -- More detailed behavioural specification In order to design a program providing some sort of interactive service to users, you must further specify answers to the following question. (a) In what formats should it accept queries? Let's assume all the queries are typed in. (A different program could use a menu of options, so that you type a number to select an option, or might use a graphical menu, allowing the selection to be made with the mouse. We ignore those possibilities for now.) Write down some formats for queries that you think a ticket clerk should be able to handle, e.g. When is the next train to london? How much is a day return to glasgow? others ...???? Write down AT LEAST five other sorts of questions you think a good program should be able to handle. (b) In what formats should it give responses? Write down some formats for answers to questions, e.g. The next train to london leaves at 1130 A day return to glasgow costs 63 pounds Sorry, there are no trains to moscow What should the program say if it cannot understand the input? What should it say if it understands the question but does not have any information to answer it? How much is a single ticket to timbuctu? What should the reply to that be? -- -- Other bits of behaviour (a) How should the program start up? Should the program produce some sort of greeting when it starts up, or print some instructions? Should it remind the user of the permitted formats for queries? (b) Should the user be able to terminate the program? How should it tell that you have finished? How should it respond when you have finished? (c) How should the program indicate that it is waiting for the user to type something? Should it always use the same prompt, e.g Please type something: Should it vary the prompt according to what has already been discussed? (d) How should the program help users who have forgotten what to do? Should you be able to ask it for help about available information or about available formats? How? E.g. what should happen if the user types "help", or just types a query symbol: "?" NB if you use readline these will come into the program as one word lists: [help] or [?] -- Knowledge required by the program ---------------------------------- In order to provide answers to questions, the program will need some information on which to base the answers. An interactive information proving program will have to have some sort of ONTOLOGY, i.e. a set of objects, properties, relations, actions, events, etc. that it knows about. (For examples of ontologies see TEACH RIVER2, TEACH RIVERCHAT. See also TEACH PROPOSALS, concerning the role of ontologies in defining objectives.) WHAT SORT OF ONTOLOGY WILL THE TRAIN CLERK PROGRAM NEED? It will need to know about stations, times, .... What else will be needed? What sorts of objects? What sorts of properties or attributes of the objects? What sorts of relations between the objects? (E.g. it depends whether all questions are about departing from here, or whether you can ask about starting anywhere.) -- Representation issues ---------------------------------------------- Information about the ontology, i.e. about the world, has to be represented in the program in a useful form. How should should a train clerk program represent the information it uses? Contrast: 1. eliza-like, with a pattern for every possible type of query 2. information in an extendable database, with fixed rules for using the information What format for database entries? Should the database have separate lists for each item of information about station, like this: [depart london 1030] [depart london 1130] [depart london 1230] or one list [depart london 1030 1130 1230] (Answer: it depends how you want to use the information. It takes practice before you can choose a good format. Meanwhile use trial and error, and learn from what goes wrong.) (Question: what other information would the program need to have about london?) -- How many procedures will be needed? -------------------------------- With a lot of experience you will be able to break the task down into a certain number of procedures, each of which has a specialised task. If you have not had a lot of practice you may find this difficult. Separate procedures, or well defined portions of procedures might be useful for various sub-tasks performed by the clerk. What are the sub-tasks? Try to write down at least four sub-tasks before you read on. (If you have done TEACH DIARY, or TEACH RIVERCHAT you should be able to get some ideas from looking back at that.) Here are some suggestions for sub-tasks. Compare these with what you wrote down. Sub-tasks: setting up the initial database of information top level control of the conversation telling the user to type in next query reading in the query recognising the form of the query getting information from database providing the answer to each type of query if the information is available if presuppositions are incorrect if question format not recognised Can you give examples of each of these? deciding whether to stop the program finishing the conversation with some sort of farewell message Later we'll suggest ways to write bits of Pop-11 to handle each of these sub-tasks. You could start thinking about what the procedures for these tasks should look like. Sketch out the main instructions, and think about how to put them together. Use TEACH DIARY or TEACH RIVERCHAT as your guide. -- Scenario ----------------------------------------------------------- Make sure you develop a scenario, that is, a sample hypothetical interaction with your program. Doing that helps to specify precisely what you want your program to do. If you don't have a scenario, you probably don't have a clear idea of what you are aiming to do. Here is part of a possible scenario. If you don't like it, think of ways in which you would prefer the interaction to be improved. Then later you can think about how you would design a program to produce the improved version. Think about the information the program needs to be able to produce this interaction. Think about how the processes are controlled. ** [Welcome to the ticket clerk .] ** [You can ask about departure times , or single , return , or dayreturn ticket prices] ** [please type your request] ? are there trains to leeds ** [Sorry please try another format] ** [please type your request] ? is there a train to leeds ** [yes there are trains to leeds] ** [please type your request] ? when are trains to leeds ** [trains to leeds depart at these times : 1030 1130] ** [please type your request] ? how much is a single to leeds ** [The cost of a single to leeds is 21 pounds] ** [please type your request] ? is there a train to glasgow ** [no there are no trains to glasgow] ** [please type your request] ? how much is a single to oxford ** [Sorry there are no trains to oxford] ** [please type your request] ? when are trains to reading ** [Sorry there are no trains to reading] ** [please type your request] ? bye ** [Thank you . Have a good journey] What other input and output formats should be supported? Make a list of some possible forms of input and output not included here. -- Towards a working implementation ----------------------------------- For each of the sub-tasks defined above we can now plan an implementation in Pop-11. -- -- Defining the top level procedure We'll assume that the top level procedure is called train_clerk. It could take this general form: define train_clerk(); 1. Invoke a procedure called setup_train_data that creates the initial database. setup_train_data(); Later on think about how to define it. setup_train_data(); This could either assign a complete list to database, or assign the empty list to database and then make use of a succession of calls to add or alladd See HELP DATABASE 2. Print a welcoming message, possibly giving a reminder of formats the user can type in. You could just print a list of words, or maybe use a string. 3. Use a repeat ... endrepeat loop to control the conversation until the user types "bye". 3.1. Use readline() to get the user's query in the form of a list of words. E.g. you could do something like lvars request; readline() -> request; What does readline() do? See HELP READLINE for a summary or TEACH READLINE for a long reminder. 3.2. Check whether to stop, using quitif or quitloop See HELP QUITIF, HELP QUITLOOP If you use the variable request to store what the user typed in, you can use the test request = [bye] or something like that, to recognise end of conversation. 3.3. If not quitting, give the request (a list of words) to a procedure to handle it. Call the procedure answer_travel_query It should take a list of words as input and do what has to be done. 4. Print out a farewell message. enddefine; Try replacing all that text with Pop-11 instructions, and put it into your file 'train_clerk.p' Assume that you will define the procedure answer_travel_query(list) at some later time. -- -- Testing your top level control procedure To test the top level procedure after you have defined it you can give the other procedures temporary "dummy" definitions, and then fill them out properly later on. E.g. Define the procedure setup_train_data(); so that it does nothing except print out a message saying that it is setting up the database. Similarly define the procedure define answer_travel_query(request); ... enddefine; so that all it does print out the request list, request => or maybe something like this: [I cannot yet answer the query: ^^request] => Note what that does: it creates a new list containing the words I cannot yet answer the query: followed by the words in the list request. If you are not familiar with the use of "^^" and "^" to replace the value of a variable in a list you will need to revise TEACH ARROW TEACH LISTSUMMARY Chapter 6 of the Pop-11 Primer. Having created those two "dummy" procedure definitions in your 'train_clerk.p' file, you can test your definition of the procedure train_clerk to make sure that everything is working OK at that level, thus: /* ;;; test train_clerk train_clerk(): */ Put that test inside a comment so that it will not be run every time you compile (load) the whole file. -- -- Defining setup_train_data() Before you can define the procedure to process answers, you MUST have a database set up. So the next thing to do is defining the procedure to create the database entries. To this must MUST first have a clear idea of (a) the ontology of the program (explained above) (b) the format in which you wish to represent the information using that ontology. You can start by defining a subset of the information, and then later when the rest of the program is working, come back and add more. For example your procedure can take this sort of form, for a subset of the information needed: define setup_train_data(); [ [depart london 1015] [depart london 1045] [depart london 1115] .... [depart leeds 1030] [depart leeds 1130] .... [price london 27 single] [price london 40 dayreturn] [price leeds 21 single] [price leeds 35 dayreturn] .... ] -> database; enddefine; Put a completed version of that procedure definition in your file called 'train_clerk.p'. If you use a different format for the database items you will have to change some of the examples below to make them work with your format. Replace occurrences of "...." with more items of information for your train clerk program to use. This version of the start-up procedure assigns a complete list of lists to database, as shown above. An alternative would be to assign the empty list to database and then make use of a succession of calls to add() or alladd(). adding different things. Note the use of the angle bracket format "< >" in the previous lines to indicate the TYPE of thing that needs to be given as argument to a procedure. If you don't remember anything about the database and the procedures and syntax forms associated with it, then you may find it useful to look at TEACH DATABASE, and read Chapter 7 of the Pop-11 primer. When you have defined the procedure give it a quick test as follows: ;;; Empty the database [] -> database; ;;; Test the procedure setup_train_data(); database ==> -- -- Preparing to access the information in the database Having defined a procedure to set up the database the next step is to plan the procedure that will answer requests by finding information in the database. In order to do that you must know how to use the database procedures such as present(pattern) -> boolean lookup(pattern) (See HELP PRESENT, HELP LOOKUP, or TEACH DATABASE, Primer Chapter 7) -- -- Using present present(list) -> boolean For example, here are ways of using the procedure present. How would you decide whether there is any information about trains to glasgow? Try these setup_train_data(); present([depart london ==]) => ** it => ** [depart london 1015] present([depart glasgow ==]) => ** Define a procedure called trains_go_to, which takes a town, represented by a word, as input and returns true or false depending whether there is at least one train to the town. define trains_go_to(town) -> boolean; present( ) -> boolean; enddefine; Replace an appropriate pattern containing town. HINT: you will have to use ^town Then test it setup_train_data(); trains_go_to("london") => trains_go_to("berlin") => Put the definition of the procedure in your file 'train_clerk.p' You could use that procedure to answer questions about whether there are any trains to some town, as illustrated below. -- -- Iteration over the database Sometimes answering a question requires getting different items of information from the database and making a list of them, then using that list in the answer. To do this you will also need to know how to use syntax forms for "looping over the elements of the database". This is one of the most common forms: foreach ! do ... endforeach forevery ! do ... endforevery For information on those two see TEACH FOREACH TEACH FOREVERY You'll also need to know how you can build a list of things found in the database, using "decorated list brackets" in forms like this: [% foreach ! do ... endforeach %] And for some more advanced cases, forms like this: [% forevery ! do ... endforevery %] For example, try this after defining the above setup procedure: setup_train_data(); vars time; [% foreach ! [depart london ?time] do time endforeach %] => This should get a list of times for trains departing to london, e.g. something like this, perhaps with more times: ** [1015 1045 1115] Try changing it to produce a list of times for trains departing to leeds. -- -- Defining trains_departing_for(town) -> list Using the ideas from the previous section, can you define a procedure that takes a name of a town as input and returns a list of all the times of trains that depart for that town: define trains_departing_for(town) -> list; lvars time; [% foreach ! do .... endforeach %] -> list; enddefine; HINT 1: in the pattern you will have to USE the value of the variable "town". You can use this format inside the pattern: ^town to use the value that "town" already has when the procedure is run. HINT 2: the pattern will have to use a pattern element to SET the value of the variable time. You can do that by including this at the appropriate place inside the pattern: ?time HINT 3: as in the previous examples, between "do" and "endforeach" you will have to use the value of the variable time, i.e. leave the value on the Pop-11 stack, to be included in the list built up by the brackets: time Look back at the previous examples to see how they worked. Complete that definition in your file train_clerk.p then test it. trains_departing_for("london") => ** [1015 1045 1115] trains_departing_for("leeds") => ** [1030 1130] trains_departing_for("moscow") => ** [] If you cannot define that procedure you will have to ask a demonstrator or tutor for help. -- -- A further exercise using foreach As a further exercise, try the following format to make a list of information about prices to london. vars info; [% foreach ! [price london ??info] do info endforeach %] => Try changing that to make a list of information about all the "day return" prices. -- -- Recognising the form of the query You should now have some idea how to use present and foreach to get information from the database that might be needed to answer a query. If so, you are ready to start planning the definition of the procedure to answer a query. It will need to have a number of tests to decide on the type of the query. These tests will have to be related to the formats you have decided to allow for queries. For that you can use the pattern matcher repeatedly in a multi-branch conditional expression, just as in TEACH RESPOND, or TEACH DIARY. You can use this format for testing for a collection of cases: if request matches ! then .... elseif request matches ! then .... .... else .... endif; You must plan carefully how many such cases you need to deal with, and construct a pattern for each case, to be used in the test conditions of the form request matches ! The final case, following "else" is the default case and that might simply include an action saying something like [Sorry: not understood -- please try another format] => Examples of conditions might be things like these: request matches ! [is there a train to ?x] request matches ! [when are trains to ?x] request matches ! [how much is a single to ?x] Write down some additional conditions corresponding to the forms of input from the user that you would like to handle, and use them to produce a skeleton definition for this procedure in your file train_clerk.p define answer_travel_query(request); if ... then .... elseif ... then .... elseif ... then .... else .... endif enddefine; At this stage you may not know what to put in the "then ...." sections corresponding to the different query formats. So leave them blank initially, or put in [information not yet available] => as a temporary action for each format. Then gradually you can replace these with proper actions to answer the different requests. Note that for each request you may have to prepare two types of answer: o The answer when the information is available in the database o The answer when there is no information available. When a question is ambiguous, the action may involve having a dialogue with the user to remove the ambiguity, but that's probably too complex for a first draft of this procedure. -- -- Getting information from the database For each request format detected by one of your conditions, think carefully about (a) How the information required to answer the question can be found in the database, using facilities like present and foreach, as explained above. (b) How the information should be presented to the user. This will generally require constructing a list to print out, where some of the components of the list are items from the database, or items from the request. These items can be inserted into the list using "^" or "^^". (c) How to respond if there's no information. An example of one of the conditions and the corresponding response might be something like this, using the procedure trains_departing_for defined above. elseif request matches ! [when are trains to ?x] then ;;; get a list of train times trains_departing_for(x) -> list; if list == [] then [Sorry there are no trains to ^x] => else [trains to ^x depart at these times: ^^ list] => endif elseif .... Try adding that, and other cases to your definition of the procedure answer_travel_query(request); then when you have two or three cases, plus the default case after "else" for unrecognised inputs, have a go at testing your complete program. I.e. first make sure it handles a few simple cases properly to ensure that your general format works. Then you can start thinking about adding more cases. -- Put it all together and test it ------------------------------------ Put all the various pieces of your program together in the file train_clerk.p and test them all out, making sure they work together. Make sure you have comments explaining what each procedure is meant to do, and possibly extra comments explaining HOW they were. -- Limitations of this project ---------------------------------------- This mini_project involves a number of ideas relevant to AI programming including o Use of a store of information represented internally o The importance of clarifying the ontology used by a program o The importance of choosing a good representation for information o Design of programs that interrogate the store of information o Design of programs that interact with a user in a fashion that approximates to a subset of English o Use of list processing techniques The program as described so far does not include o Modification of the internal database (Compare TEACH RIVERCHAT, TEACH RIVER2) o Searching for solutions to a complex problem (Compare TEACH TOWER, TEACH SEARCHING, TEACH ROUTE) o Making plans o Learning -- Possible extensions ------------------------------------------------ The above scenario is very limited. Try to think of a number of extensions, and then think about how they might be implemented in a modified version of the program. Try writing down at least four extensions to the program before reading on. Here are some suggested extensions. 1. Make the program find out the current time of day, and use it in answering some questions. To find the time, use the library procedure date() -> list It returns a list of six items as described in HELP DATE date() => ** [27 Nov 1996 9 47 20] 2. Check the day of the week and allow the database to include different train times for weekdays, Saturdays and Sundays. Working out the day of the week is not easy. However the procedure sysdaytime() produces a string as its result, and the first three letters will indicate the day of the week. sysdaytime() => ** Thu Nov 28 02:44:20 GMT 1996 This is how you can get a string composed of the first three characters (see HELP SUBSTRING): substring(1, 3, sysdaytime()) => ** Thu 3. Answer questions about arrival times for trains from other places to here. E.g. when do trains from London get here 4. Accept information about delays in departure times, or arrival times. 5. Accept information about permanent changes to time table. Allow the station controller to type in changes about trains that no longer run, or different start and arrival times for existing trains, or new train services. This could involve using the database procedures add, remove, delete. Think about the formats for such changes. If there are permanent changes typed in and you want to have them stored in a file you can use the procedure storedata. See HELP STOREDATA 6. Could you introduce some security check to ensure that the person giving you new timetable information is allowed to do so? 7. Try adding route finding capabilities, perhaps of the kind described in TEACH ROUTE. This might include searching in a space of possible combinations of journeys. --- $poplocal/local/teach/train_clerk --- Copyright University of Birmingham 1996. All rights reserved. ------