"Science, Faculty of"@en . "Computer Science, Department of"@en . "DSpace"@en . "UBCV"@en . "McRae, Robert Norman"@en . "2011-04-11T17:05:33Z"@en . "1972"@en . "Master of Science - MSc"@en . "University of British Columbia"@en . "The problem treated in this thesis is to create a system to monitor multiple interacting simulators. The problem is encountered in an attempt to simulate urban growth. The resulting system has a supervisor which controls all of the components of the system, namely the I/O routines, the graphics routine, the command routines, and the simulators. The main task of the supervisor is to display whichever data values the user desires. This involves executing some simulators, and extracting the data values from the data base. The extraction process first finds an association path between the files in the data base in order to relate the variables being displayed. Then using the association path the physical values are extracted from the data base. The data values are then passed to the graphics routine to be displayed for the user."@en . "https://circle.library.ubc.ca/rest/handle/2429/33489?expand=metadata"@en . "A SUPERVISOR TO MONITOR MULTIPLE SIMULATORS by ROBERT NORMAN McRAE B . S C , Un ive rs i t y of B r i t i s h Columbia, 1970 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF M.Sc, i n the Department of Computer Science We accept th i s thes is as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA March 1972 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the r equ i r ements f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h Co lumb ia , I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s tudy . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y purposes may be g r an t ed by the Head o f my Department or by h i s r e p r e s e n t a t i v e s . I t i s unde r s tood t h a t c o p y i n g or p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l no t be a l l owed w i t hou t my w r i t t e n p e r m i s s i o n . Department o f Computer Science The U n i v e r s i t y o f B r i t i s h Co lumbia Vancouver 8, Canada Date A p r i l 13, 1972 ABSTRACT The problem t reated i n th i s thes is i s to create a system to monitor mu l t ip l e i n t e r a c t i ng s imula tors . The problem i s encountered i n an attempt to s imulate urban growth. The r e s u l t i n g system has a superv isor which cont ro ls a l l of the components of the system, namely the I/Oo; rou t ines , the graphics rou t i ne , the command rou t ines , and the : s imu la to rs . The main task of the superv isor i s to d i sp lay whichever data values the user des i r e s . This involves executing some s imula tors , and ex t rac t ing the data values from the data base. The ex t rac t i on process f i r s t f inds an assoc i a t i on path between the f i l e s i n the data base i n order to r e l a t e the va r i ab les being d i sp layed . Then using the a s soc i a t i on path the phys i ca l values are extracted from the data base. The data values are then passed.to the graphics rout ine to be d isp layed fo r the user . i i \" T A B L E \" OF C O N T E N T S chapter contents page I THE PROJECTSANfiOVERVIEW . . . . . . . . . . . 1 A in t roduc t ion . . . . . . . . . . . . . . . 1 B comparison with other systems . . . . . . . 4 C o v e r a l l system; . . . . . . . . . . . . . . . . 7 D implementation; . . . . . . . . . . . . . . ^ II THE SUPERVISOR - AN OVERVIEW . . . . . . . . . . 15 A the ro l e of the superv isor . . . . . . . . 15 B design of the present superv isor . . . . . 15 III THE- SUPERVISOR IN DETAIL . . . . . . . . . . . . 18 A organ iza t ion of the superv i sor . . . . . . . 18 B i n i t i a l stage - loading tables fo r , - ,) . superv isor . . . . . . . . . . . . . . . 18 C externa l in te r faces . . . . . . . . . . . . 26 a>V user commands . . . . . . . . . . . . 27 b, data base' ... c-.'^ . \u00E2\u0080\u00A2'*.'\u00E2\u0080\u00A2\u00E2\u0080\u00A2<. ^ .'Ivov/V VJ> 27 -co. s imulators . 28 \u00E2\u0080\u00A2d'.^ g raph ica l output . . . . . . . . . . . 29 i i i chapter contents page D i n t e r n a l workings of the superv isor by command . . . . . . . . . . . . . . . . . 31 a \ the DISPLAY command . . . . . . . . . . 3^ 1. general phi losophy . . . . . . . . . 32 2. pars ing of a command s t r i n g . . . . 34 3. bu i l d i ng a tree of va r i ab l e r e l a t i ons 35 4 . generating data . 40 5. ex t rac t ing data 43 6. prepar ing data fo r g raph ica l output . . . . . . . . . . 59 b' the CHANGE command . \u00E2\u0080\u009E . . . . . . . . . . . 61 c.\ the other commands . . . . . . . . . . 62 IV FUTURE EXTENSIONS TO THE SYSTEM . . . . . . . . . 6 3 A in t roduc ing a complex data base . . . . . . ^ 3 a ) consequences fo r the present system . . . B removing the r e s t r i c t i o n that s imulators run by time only . . . . . . . . 69 C in t roduc ing an ar i thmet ic expression in the DISPLAY command . . . . . . . . . . . . 70 D i n t e r rup t i ng the DISPLAY command . . . . . . 71 i v chapter .\" contents P a S e REFERENCES 73 APPENDIX . . . . . . . . . . . . . . . . . . 74 A l i s t of commands and the i r syntax . . . . . 74 B sample r u n w i t h graph ica l output . . . . . 78 V TABLE OF FIGURES number desc r i p t i on page 1 representat ion of system . . . . . . . . . . 3 2 problem domain . . . . . . . . . . . . . . . 3 : 3 example of c losed cyc le of requests . .. . . . , H 4 format of a f i l e i n the data base . . . . . . H 5 flow char t ,o f^superv i sor . . . . . . . . . . 19 6 f i l e desc r ip t i on table 22 7 s imulator desc r i p t i on table . . . . . . . . . 23 8 p o l i c y vector tab le . . . . . . . . . . . . 25 9 informat ion s t ruc ture fo r graph ics . . . . . . 30 10 example of pairwise r e l a t i o n a l l i nks between f^-l^S. . . -. \u00E2\u0080\u00A2 . . ^ . . . . . . . . . . . . *}6 11 flow chart fo r b u i l d i n g of r e l a t i onsh ips between d i sp lay va r i ab les 33 12 examples of r e l a t i onsh ips between d isp lay v a r i a b l e s . . . . . .^)., 41 13 flow chart fo r generat ion of data 43 14 example of recurs ive s imulator c a l l s . . . . 45 152, f low chart f o r ex t rac t ion of data . . . . . 52 16 example of a data base . 55 17 values extracted from the data base. . . . . 56 18 example of complex data s t ruc ture . . . . . . . 63 19 example of l o g i c a l t ree . . . . . . . . . . 68 20 equivalent sequent ia l f i l e . . . . . . . . . 68 v i ACKNOWLEDGEMENTS I am deeply indebted to Dr . J . L . Parker fo r h i s able ass is tance and d i r e c t i o n i n he lp ing : me to complete th is t h e s i s \" a n d fo r spending generous por t ions of h i s time d i scuss ing i t s development. I would a lso l i k e to take th i s opportunity to commend Br ian J e r v i s , Doug Ash, Zafar Rashid and Joe l Yan fo r t he i r f i ne programming e f f o r t i n var ious sect ions of the o v e r a l l system. I would a lso l i k e to thank Dr . F. Nake fo r h i s const ruc t i ve c r i t i c i s m s . 1. CHAPTER I THE PROJECT - AN OVERVIEW \u00C2\u00A7 A. i n t roduc t ion The problem treated i n th i s thes is i s to create a system to monitor mu l t ip l e s imula tors . The systemwis given a set of s imulators {s^,. . ,s }, where s imu la t ion i s def ined as fo l l ows : A s imula t ion of a system i s the operat ion of a model or s imulator which i s a representat ion of the system. The model i s amenable to manipulations which would be imposs ib le , too expensive, or imprac t i ca l to perform on the en t i t y i t por t rays . The operat ion o f . t h e model can be studied and, from i t , p roper t ies concerning the behaviour of the .ac tua l , system can be in fe red [12, p .2 ] . The need for such a system-'arose out of the des i re to s imulate urban growth. Hence the involvement with the I n t e r- Ins t i t u t i ona l Po l i c y Simulator (hereafter re fered to as HPS ) group. The HPS group cons is ts of representat ives from the C i t y of Vancouver, the Vancouver Regional D i s t r i c t , and the Un i ve rs i t y of B r i t i s h Columbia. There i s a lso some p a r t i c i p a t i o n from the Munic ipa l A f f a i r s Department i n V i c t o r i a , and the Urban Planning Department i n Ottawa; The goal of the pro jec t i s to create a s imula t ion model of the Vancouver Lower Mainland. The t o t a l model has been s p l i t in to var ious submodels, namely popula t ion and demographic, economic, t r anspor ta t ion , land u t i l i z a t i o n , hea l th systems, p o l l u t i o n , human ecology, resources and. pub l i c s e r v i c e s . Each of these submodels are capable of fo recas t ing c e r t a i n r e su l t s given the appropr iate data from previous years . The d i r e c to r of the HPS pro jec t states i t s goal i n these words: I ts i n i t i a l aim was to develop a s imula t ion model of man/environ-v . / i ment i n t e r a c t i o n i n the Lower Mainland of B r i t i s h Columbia, and th i s was hope fu l l y to be only one of a se r i es of steps lead ing to more responsive dec is ions a f f e c t i n g the qua l i t y of l i f e i n an urban region [6] . The fo l lowing desc r i p t i on ind ica tes the approach to the problem taken i n th i s t h e s i s . The model of urban growth was d iv ided in to i n t e r a c t i ng submodels. In order to make the s imulators eas ie r to monitor they are forced to use common rout ines fo r communication with a user , the data base management, and output generat ion. At i the heart of the system there i s a cen t r a l c o n t r o l l e r - the superv isor -which decides when to execute the var ious components i n the system. Thesys tem i s represented schemat ica l ly i n f i gu re 1. The components of the system were designed so that they possessed the fo l low ing a t t r i b u t e s . The execut ion of the system can be under-. stoqd;ltby; persons who may not be f a m i l i a r with computing equipment, a n d ' i t i s poss ib l e to exp la in to a user i n a short time per iod how to operate the bas i c fpa r t s of the system. The system has a set of very e a s i l y understood commands by which the user corresponds with the system. The data management rout ines permit the s imulators to reference the data base with ease. The graph ica l output rout ine i s device independent, and i s capable of d i sp l ay ing var ious types of graphs. The user need not worry about running the s imulators to create the appropr iate data before-Re wants some graph ica l output -he merely ind ica tes the des i red graph. The superv i sor , through the DISPLAY command, does a l l of the work i n order to generate the data values to pa;is to the graph ica l output rou t ines . This means that the s imulators are e f f e c t i v e l y hidden from the user . The system allows ce r t a i n v a r i a b l e s , c a l l e d p o l i c y v a r i a b l e s , to act as p a r a -meters to the s imula tors , f o r example i n t e res t ra te or popula t ion growth The values of a l l of the p o l i c y va r i ab les are kept i n the p o l i c y vec tor , graphics user supervisor data base simulators figure 1; representation of system problem space: consisting of r e a l world problems, eg urban planning tables to define system \u00E2\u0080\u00A2Input from: system programmer simulation model 1 system^ programmer simulation model n model writers... solution space: computer system to answer problem output to user through use of system command language graphical representation of answer to problem figure 2: problem domain 4. which i s passed to the s imulators when they are loaded. The system allows the p o l i c y va r i ab les to be changed at any time by the user . The system i s tab le dr iven so that i t i s independent of which s imulators i t i s execut ing. These tables descr ibe the state, of the en t i re system, and are 'very easy to input . F igure 2 sums up the, domain of the problem. My con t r ibu t ion to the system inc ludes design and implementation of the , superv i so r . The most powerful command i n the system i s the DISPLAY command; hence the bulk of th i s thes is i s devoted to i t s d e s c r i p t i o n . The most d i f f i c u l t a lgor i thm i n the superv isor i s the genera l ized ex t rac t i on process that i s respons ib le fo r r e t r i e v i n g the cor rec t output of the s imulators to pass to the graphics super-, v i s o r (the rout ine to monitor the graph ica l output ) . The r es t of CHAPTER I has a desc r i p t i on of the o v e r a l l system into which the superv isor f i t s . CHAPTER II has an overview of the superv i sor . CHAPTER III descr ibes the superv isor i n d e t a i l . I t descr ibes the algorithms developed i n order to implement the superv isor -e s p e c i a l l y those used i n the (DISPLAY rou t i ne . CHAPTER IV has some suggestions fo r fu r ther extensions to the system. \u00C2\u00A7 B. comparison with other systems , In 1968 an urban model c a l l e d BASS [5 ] , of a s i m i l a r nature to H P S , was developed fo r the computer (IBM 7094). I ts ob jec t i ve i s ' s ta ted as fo l l ows : The BASS Model i s designed to serve as an a n a l y t i c a l t oo l fo r exp lor ing poss ib l e a l t e rna t i v e impacts of major pub l i c and p r i va t e investment dec is ions upon land u t i l i z a t i o n [5, p .24] . BASS used some of the same design c r i t e r i a as our system. The BASS 5. report s tates that the system should be f l e x i b l e : \"the program should be easy to run with d i f f e r e n t values fo r the var ious c o e f f i c i e n t s and parameters . . . and i t should be easy to make future.changes i n the var ious submodel programs. . . i n p a r t i c u l a r , changing a submodel should no t requ i r f ea major redesign of the en t i r e s imula t ion program \" [5 , p.418], Since the s imulators could not a l l f i t into core at once they were sect ioned using the OVERLAY f a c i l i t y . Our system makes use of the advanced computer technology which allows dynamic loading of programs from d i s c f i l e s to memory.- The BASS s imula t ion s tored i n a COMMON area data that needed to be passed between s imula tors . There were no common I/O rout ines and no graph ica l output c a p a b i l i t y . The BASS s imula t ion d id not have a superv isor - there i s a l i n e a r sequence of c a l l s to s imulators which are a l l arranged i n a s p e c i f i c order . There was no attempt at c rea t ing a general framework in to which any set of s imulators may operate . Ingram [7] descr ibes a system s i m i l a r i n s t ruc ture to the BASS system. I t does not make use of a superv isor to con t ro l the s imula tors , but has forced a l l of the s imulators to act as in-core subroutines to a main program. This De t ro i t system only allows fo r the output of t ab l es . The paper by Myers [11] on general informat ion management systems descr ibes design features that should be encorporated into any informat ion management system. The data base d e f i n i t i o n and data base content should be f l e x i b l e and easy, to modify. The system must ' ' l o g i c a l l y def ine data so that i t can be processed and used i n a common way , . and . . . s tore data based on th i s d e f i n i t i o n \" [11, p.299], The phys i c a l storage of data should have key values fo r r e t r i e v a l . Our system encorporates a l l of these . i d e a s . L ipner advocates i n [10] some des i red proper t ies of computer-based urban informat ion systems based on experience with the Boston C i t i e s Model developed at M.I.T. He states that \"any r e a l l y use fu l urban informat ion system must produce graph ica l as we l l as tabular outputV'[10j p .525] . He advocates the use of common. I/O rou t ines , and the use of man-machine communication capable of being used by people who are not computer-oriented. Some' of the features of CODAS [4] are s i m i l a r to those i n our system. The-CODAS system i s in te res ted i n \" r e t r i e v i n g data from f i l e s , performing; some bas i c operat ions on them, and d i sp l ay ing them i n any of severa l output formats\" [4 , p .67] , Our system has the added compl icat ion that i t i s s imulators which produce the data f i l e s . The CODAS system has a command language that cons is ts of s e t t i ng up parameters and keywords into a ' request pa cke t ' . The data f i l e s have a r e s t r i c t e d format: one key value fol lowed by only two add i t i ona l f i e l d s . There was no attempt to genera l ize t he i r system. LISTAR [ 1] i s an \"on- l ine i n t e r a c t i v e system which permits a user to de f ine , search, modify, and cross assoc ia te data f i l e s 1 1 [1, p.313]. LISTAR has a l o g i c a l desc r i p t i on of i t s f i l e s . LISTAR permits the user to create an assoc i a t i on between any two f i l e s , whereas i n our system the r e t r i e v a l rout ine i s respons ib le fo r s e t t i ng up the a s s o c i a -t i o n . LISTAR makes use of a superv isor i n very much the same way\" as our system. The LISTAR superv isor accepts commands i n format-free s t ruc ture and passes the parameters to subroutines that correspond to the command names. LISTAR stores the data base i n an aux i l a ry s torage. The LISTAR f i l e s may be simple ( l inear ) or complex ( h i e r a r c h i c a l ) , whereas i n our system the s t ruc ture of the f i l e s may only be s imple . LISTAR shares many features i n common with our system. But our system need not worry about modifying the f i l e s t ruc ture .dynamica l l y s ince i t i s the s imulators that ouput into the f i l e s . Kidd [8] proposes a language fo r r e t r i e v i n g values from a complex data s t ruc tu re . This s t ruc ture i s s i m i l a r to the one proposed i n CHAPTER IV as an extension to our present system. There has been some c r i t i c i s m by Levy, [9] of ; the \" p o l i t i c a l and educative func t ion of the model\" [9 , p .7 ] . He be l ieves that the model w i l l be l im i t ed i n use to groups already possessing extensive resources and i n f l uence . He points out that the models are based on the status quo; but a more de t a i l ed design of the models could al low fo r more r a d i c a l p o l i c i e s . He states that \"the in t roduc t ion of the s imula t ion i n to the p o l i t i c a l sphere w i l l v i r t u a l l y force dec is ions to be channel led through the model\" [9 , p .15] . I be l i e ve the model w i l l be used to i nd i ca te trends caused by p o l i c y dec i s ions . Our system i s unique i n the fac t that i t presents an informat ion management system where the data generat ion i s through s imu la t ion . \u00C2\u00A7 C. the o v e r a l l system HPS needed quite a soph i s t i ca ted computer system to monitor the s imula tors . The opportunity was r i pe fo r the development of a s imu-l a t o r superv isor and graph ica l output package. Although the system was designed with the HPS pro jec t i n mind, i t i s by no means depend-ent upon the s p e c i f i c nature of t he i r s imu la tors ; i t was designed with the express des i re f o r genera l i t y and f l e x i b i l i t y , although th i s i s S; only v e r i f i e d a f t e r .extensive use. The system i s d iv ided in to var ious na tura l we l l-def ined components, namely the user commands, the 8. superv i sor , the s imu la to rs , the f i l e maintenance, and\"the graphics . The in te r faces between these components were wel l-def ined during the design phase. D i v i d ing a system into separate components has many advantages: the problem becomes much c l e a r e r , and the coding becomes eas i e r . This p r i n c i p l e was used whenever poss ib l e during the design of the system. \u00C2\u00A7 C . l the user commands The user communicates with the res t of the system through a command language; th i s sor t of procedure i s standard i n any large user or iented computer system. The command language was designed with var ious c r i t e r i a i n mind: s i m p l i c i t y , b r e v i t y , un i fo rmi ty , and ease of understanding.\"'\" The commands are simple i n . t h e i r s t ruc tu re . ' The words chosen fo r the language are s h o r t . i n l eng th , but c l ea r i n meaning, and d i s t i ngu i shab le from each o ther . The syntax i s such that parameters which are not e s sen t i a l are op t iona l and they de fau l t to the most common va lue . And abbrev iat ions may be used whenever des i red to shorten the communication t ime ; . f r equent l y used phrases or whole commands may be stored away fo r r e c a l l l a t e r through a user def ined name. The ease of understanding a. command has not been s a c r i f i c e d fo r the sake of b rev i t y or s i m p l i c i t y . As the user becomes more soph i s t i c a ted room must be provided fo r him to express h i s i n d i v i d u a l i t y w i th in the command s t ruc tu re . He must be able t \u00C2\u00B0 modify var ious de fau l t options and use more complicated opt ions of the commands as he becomes more exper ienced. A l l of the commands have the same o v e r a l l s t ruc tu re : an a lphabet ic command name fol lowed ^ The MTS command language was used as a model. 9. by parameter- f ie lds/ The p r e f i x character @ i s used to prompt-for a. command to be entered. The command, language s a t i s f i e s the design law of l e as t astonishment, which states that a command should do what i t l o g i c a l l y appears to do'; ['3]. By disengaging the command language from the s imulator con t ro l we now have a uniform language common to a l l s imu la tors . \u00C2\u00A7 C.2 the superv isor . The superv isor cont ro ls the ac t i on of the whole system. I ts func t ion w i l l be explored i n great d e t a i l i n l a t e r chapters . At th i s stage i t s r e l a t i o n to the res t of the system w i l l be b r i e f l y shown. The superv isor i n te rp re t s the commands and executes the appropr iate rout ines - hence upon i t s shoulders res t the communication between the user and the var ious parts of the system. Through the DISPLAY command the s imulators are run to produce any data that i s miss ing from a des i red graph; the f i l e maintenance and data ex t r ac -t i on rout ines are c a l l e d ; and the graphics rout ines are a c t i v a t ed . Passage through the superv isor i s necessary before the modules of the system are executed. \u00C2\u00A7 C. 3 the s ii i iulatbrs The s imulators are run only at the request of the superv isor through a DISPLAY command. This removes from the user the r e spons i -b i l i t y of running the. s imulators and generat ing the cor rec t data fo r a graph before asking fo r a d i sp l a y . This i s a powerful f ea tu re . The user does not have to worry, about which s imulators are necessary to produce the data and.whether or not the data i s already present . The data which i s used fo r input may be o r i g i n a l data or output data from 10. a previous s imulator run. O r i g i n a l data i s not t reated s p e c i a l l y so i t may be modif ied dur ing a l a t e r s imula t ion run . Simulators are forced to produce only the data that i s requi red for the graph. The simulators, are run by year - i n other words given a year as input the s imulator generates r e su l t s fo r that year . Hence a l l output from the s imulators i s l i nked to a year . A s imulator i s j u s t considered as a subroutine to the system so as input i t needs a l l parameters nece-ssary to def ine the s ta te of the s imula tor . A l l of the input and output.is s tored i n d i s c f i l e s . The s imula tors ' only access to the world i s through the data base and the p o l i c y vec to r . I t i s permiss ib le fo r a s imulator to demand as input the output from another s imulator as long as there i s no c losed cyc le of requests . An example of a simple c losed cyc le of requests would be a s imulator S^ us ing input 1^ that i s the output 0^ from s imulator S 2 . But uses as input which i s the output 0^ of S^. This i s shown in f i gu re 3. Simulators may be added or removed from the system extremely e a s i l y (but care must be taken to make sure that output from a removed s imulator i s not used as input to a remaining s imu la to r ) . Of course, the s imulators must conform to the standard read-write rout ines provided fo r f i l e maintenance; and the s imulators cannot provide any externa l output. Hence, the s imu-l a to rs and the user .a re completely separated: the user does not know the d e t a i l s of funning the s imu la to rs , and the s imulators do not know about the existence of users . \u00C2\u00A7 C .4 the f i l e maintenance The f i l e maintenance routines.-wefeldeyelbp'ed- i n ; order .to \u00E2\u0080\u00A2pr,esfint.aj standard package to 'the s imulator coders; A -uniform approach is.- required s ince the s imulators i n te rac t . and the superv isor must read the i r output. 11. f igure 3; example of c losed cyc le of requests k e y l i s t f o r f i l e i K l l hrx. L l K 21 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 K 2 n . L 2 contents of f i l e i K l l \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 * . r . . F l m K 21 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 \u00C2\u00AB K 2 n F 21 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 a F 2m where: K. i s a key value F. i s a f i e l d value L. i s an MTS l i n e number f igure 4: format of a f i l e , with i t s k e y l i s t , i n the data base All'wof the data handled i n the system i s s tored i n d i sc f i l e s . . The e n t r i e s , c a l l e d records , i n the f i l e each must begin with a set of keys that i d e n t i f y the record fo r s o r t i n g . The format of a f i l e with i t s k e y l f s t i s shown i n f i gu re 4. These keys need not be unique, but t he i r va lue and a l l the l i n e numbers of t he i r assoc ia ted records are kept i n a tab le c a l l e d a key l i s t . Whenever a record i s added or de leted some adjustment must be made to the key l i s t s . The reason fo r the key l i s t s being kept i s that they provide fo r quick random access to records which otherwise could not be obtained without a sequent ia l search. Depending upon i t s needs, the s imulator may use sequent ia l access or use random access s ince both are a v a i l a b l e . The f i l e main-tenance rout ines i n conjunct ion with the command language and the graphics rout ines remove much of the unnecessary drudgery i n s imulator w r i t i n g . \u00C2\u00A7 C.5 the graphics At present the graphics package i s the only form of v i s u a l output fo r the s imula tors . The s imulators always output t h e i r data in to f i l e s from which the DISPLAY rout ine ; r e t r i e ves the data values that i t passes to the graphics superv isor j which i s respons ib le fo r graphics output. The graphics package can only be ac t i va ted through the DISPLAY command, hence a l l ou tput \" i s con t ro l l ed by the superv i sor . I f i t i s to s a t i s f y the needs of a l l poss ib l e s imulators i t must be capable of qui te a va r i e t y of graphs. The graphs may be shown on a va r i e t y of d i f f e r e n t types of dev i ces , namely a remote p r i n t e r , the source te rmina l , a.\ t e l e t ype , a p l o t t e r , a re f resh d i sp lay screen (Adage AGT-10), or a storage.tube (Tekt ron ix ) . Each device may be d iv ided up into separate 13. areas each of which may conta in i t s own graph. This should enhance v i s u a l comparison of graphs. The fo l lowing types of graphs may be shown on any of the above dev ices : ba r , l i n e , dot, contour, or map. Any graph may be superimposed upon another graph fo r ease of comparison. The order of d i sp l ay ing the graph may be a l t e red by choosing any one of the va r i ab les i n the DISPLAY,command to sequence the graph. Since output devices have only a two dimensional graph surface some t r i c k s must be employed to v i s u a l i z e any graphs i n three-dimensions: two-, dimensional s l i c e s are given of the graph i n three-dimensions. The rate at which these graph s l i c e s are shown can be con t ro l l ed through a parameter i n the DISPLAY command. Before the ac tua l graph i s p l o t t e d , the s c a l i ng of the values has to be done, and the t i t l e s to the axes have to be added. Each graph that i s d isp layed on an area of a device i s s tored i n a push down stack with a de fau l t l e v e l of four . This . feature enables a previous graph to be reshown on a device without having\u00E2\u0080\u00A2to r e ca l cu l a t e the,graph va lues . This completes the b r i e f desc r ip t i on of a l l the parts i n the system. It i s hoped that with the a v a i l a b i l i t y of making p o l i c y changes, and d i sp l ay ing a l l r e l a ted va r i ab les by means of the extensive graphics package that the user can tes t h i s ideas . I t i s a lso hoped that 'the*-*-user^sCimia^ into th ink ing of new hypotheses to test,whose r esu l t s can be compared with the pred ic ted or des i red r e s u l t s . \u00C2\u00A7 D. implementation This system i s wr i t t en to operate under the Un i ve rs i t y of B r i t i s h Columbia's IBM 360r67 duplex. The Un i ve rs i t y uses the Michigan Terminal 14. System (MTS). Whenever poss ib l e we have used features provided under MTS and by the UBC Computing Centre; hence the system i s i n s t a l l a t i o n ' dependent. MTS o f f e r s exce l l en t remote terminal support and i t i s intended that most of the usage of th i s system w i l l be from a remote . t e rmina l . The implementation of the :sys tem; i s i n IBM-360 assembler language and FORTRAN-IV. At th i s po in t a hearty thanks should be given to UBC's Computing Centre which has provided an exce l l en t computing and debugging environment, without which the -system,/- would have never proceeded so fa r so f a s t . 15. < CHAPTER II THE SUPERVISOR -.AN OVERVIEW \u00C2\u00A7 A. the ro l e of the superv isor S ince, the superv isor i s the heart of th i s system, a t t en t ion i s focused on i t i n a general way before examining i t i n d e t a i l . Because the s imula t ion task is, s p l i t up into independent sub tasks , a super -v i s o r i s necessary which w i l l oversee the execut ion of the,system. The superv isor must i n t e rp re t the des i res of the user and take the cor rec t sequence of steps to produce the des i red r e s u l t s . The ro l e of the superv isor can be best exposed through\u00E2\u0080\u00A2examining the consequences of the user i s su ing a simple DISPLAY command. When a user issues a command the superv isor branches to the sec t i on of code wr i t t en fo r that s p e c i f i c command. A DISPLAY command may necess i ta te the generat ion of data which i s requi red for a graph but not yet present i n the data base. I f we need to generate data , the superv isor must run the s imulators which produce the data . The data may be i n a s t a t i c f i l e so i t does not have to be generated. When a l l of(&the necessary data i s present i n the data base the DISPLAY rout ine extracts from the data base the data fo r the graph. These values are then sorted and passed to the graphics superv i sor . A f t e r the code fo r the DISPLAY command i s f i n i shed con t ro l i s returned to the superv isor which then returns con t ro l to the user , who may enter another command. The supe rv i so r ' s ro l e as the heart of the system i s presented i n f i gu re 1. \u00C2\u00A7 B. the design of the superv isor The superv isor was designed so that i t would perform the fo l low ing func t ions : 16. 1. I n i t i a l i z e the system by loading t ab les . As much s p e c i f i c informat ion as poss ib l e i s read i n as i n i t i a l data so that i t i s very easy to add, de le te , or modify fo r example, f i e l d s i n a f i l e , f i l e s o r s imula tors . A desc r ip t i on of the fo l low ing i s read i n : each f i l e and the f i e l d s contained w i th in i t ; each' s imulator and the input and output f i l e s assoc iated with i t ; each device name fo r g raph ica l output ; each class.name and the f i l e s assoc iated with i t ; and each p o l i c y vector name and the f i l e s assoc ia ted with i t . The superv isor must in ter- , face with the SCANNER, which replaces each text s t r i n g i n . the command with an in teger equ iva lent . 2. Interpret a l l of the commands issued by the user , ( the commands are issued by a user e i t he r i n t e r a c t i v e l y fromaa remote terminal or from a batch s t a t i o n ) . 3. Know when to c a l l a s imula tor , and which one to c a l l i n order to generate the cor rec t data . 4. Load the s imulator and pass contro l ; t o ' i t ' i V 5. Ext rac t from the data base the values needed fo r a graph, and pass the appropr iate array to the graphics superv i sor . 6. Make p o l i c y vector changes and i nva l i da t e the appropr iate data due to the po l i c y change. 7. Respond to er rors and re turn i n t e l l i g e n t ' e r r o r messages. 8. E s t ab l i sh l o g i c a l area numbers on dev ices . 9. L i s t the p o l i c y names, c l ass n a m e s H e names, s imulator names, f i e l d names w i th in a f i l e , f i l e names w i th in a c l a s s , J ; data values fo r f i e l d s or f i l e s . 10. Return to MTS mode and then l a t e r to r e s t a r t the program (.,. from where i t was i n t e r rup ted . 11. Save ca l cu la ted data i n a permanent f i l e , and to res tore th i s data at a l a t e r time i n the same run , or i n another run of the system. 12. Def ine .a text s t r i n g by ' a symbol ,,,-aritf .then replace . tlie;;:text ' stririg.jwhenever the 'symbol''is' mentionedT'\"\" l\" \" 13. Exp la in the syntax arid meaning of the commands to an un fami l i a r or f o r g e t f u l user . 14. Restore a graph prev ious ly shown oh an a rea , or erase the present contents of an area . 15. Set c e r t a i n run time parameters. With a system which performs such a wide va r i e t y of tasks , i t i s obvious that a c l ea r and concise command language i s necessary. 17. At present the superv isor performs a l l of the above funct ions and a lso some less important functions,? Each func t ion i s wr i t t en as a separate un i t so that adding more funct ions to the superv isor i s very easy. Some of the extensions that are planned fo r the superv isor are d iscussed i n CHAPTER T V . 18. CHAPTER III THE SUPERVISOR IN DETAIL \u00C2\u00A7 A. o rgan iza t ion of the superv isor The superv isor i s organized i n a h i e r a r c h i c a l s t ruc ture i n which each component i s se l f-conta ined except for parameter pass ing . This i s v i s u a l i z e d by the flow chart i n f i gu re 5. The SCANNER rout ine converts the alphanumeric s t r i ngs i n to integers so that va r i ab l e length s t r ings may be t reated as , in tegers w i th in the program. The main program i s respons ib le fo r t r ans f e r r i ng to the cor rec t rout ines -so we must look at the c a l l ed rout ines, i n order to extract the de t a i l s of opera t ion . \u00C2\u00A7 B. load ing tables fo r the superv isor The Idea of loading tables' of in format ion . that-def ine the state of the system i s important. This means that there are few s p e c i f i c d e t a i l s programmed in to the system - most of the de t a i l s come from the input t ab les . In order to change the number of f i e l d s i n a f i l e , or change the number of input f i l e s to a s imulator , or change the name of a s imulator or any other change i n the input data i s a t r i v i a l task. Of course, most of the changes invo lve a l t e r i n g some code w i th in a s imula tor . Now i t should be c l ea r why f t was s t rongly stated that th i s system', i s not dependent on the HPS p ro j ec t : any s imulator may be used that has modif ied i t s input-output to comply with the convent ions. The aim has been to s a t i s f y the computer lawFthat \"one man's constant i s another man's\u00E2\u0080\u00A2var iab le-\" : [3] . The program for loading the tables i s s i m i l a r i n s t ruc ture to the main program j u s t desc r ibed . I t i n i t i a l i z e s some v a r i a b l e s ; I t then reads i n a keyword table which i s used by the SCANNER when i t assigns load tables that def ine the system c a l l program to read i n command determine which command was issued * and t rans fe r con t ro l to that command rout ine read i n command c a l l SCANNER check v a l i d i t y of command ^returny * command names are l i s t e d i n the appendix. f i gure 5; flow chart of superv isor 20. in tegers to alphanumeric s t r i n g s . The keyword table a lso ind ica tes whether the s t r i n g i s a s p e c i a l character , keyword, b lank, in teger , or an ord inary s t r i n g . Then the program reads i n an input l i n e i n character format, and has i t t rans la ted in to integers by c a l l i n g the SGANNER. Some of the input l i nes conta in command words which ind i ca te the type of informat ion that fo l l ows . When the program'encounters a command word i t branches' to the appropr iate rout ine to handle the se t t ing .up of the t ab l e . The l a s t l e v e l has now been reached: the rout ines \u00E2\u0080\u00A2 that create desc r i p t i on tab les 1 fo r f i l e s , s imula tors , the p o l i c y vec to r , c lasses and dev ices . Just before the s t ruc ture and contents of the var ious tables are desc r ibed , i t would be i n s t r u c t i v e to exp la in how they have beena implemented. For t ran arrays are not very adaptable>for dea l ing with a vary ing number of f i e l d s . But the assembler DSECT provides the i d e a l t oo l fo r handl ing the table in format ion . Blocks of informat ion can repeat an i n d e f i n i t e number of- t imes, each f i e l d w i th in the bo lck can have a name, and po inters from a. main s t ruc ture to a substructure fo r vary ing number of en t r i es w i t h i n a f i xed s t ruc ture can be used. Choosing to handle the tables with the assembler DSECT had imp l i ca t ions throughout the res t of the superv i so r : i t forced most of the coding to be done i n assembler language. \u00C2\u00A7 B. l the f i l e desc r i p t i on table The f i l e desc r i p t i on table cons i s t s of a l o g i c a l des c r i p t i on of each value f i l e ( f i l e which contains the data values) i n the data base. Remember that the data base cons is ts of many value f i l e s each of which i s assoc iated with a s p e c i f i c s imula tor . \u00E2\u0080\u00A2\u00E2\u0080\u00A2Each, f i l e ] *desc r ip t ion has a po in te r to a de c r i p t i on of a l l fiel'ds/'wl.th\"i'n.s the f i l e . .'Each of the records i n the value f i l e contains a l i s t of data va lues . The reason fo r the l o g i c a l desc r i p t i on i s to. assoc ia te a name with each f i l e and i t s f ie lds,- and to provide more informat ion about each which w i l l be needed when ce r t a i n dec is ions are to be made. F igure 6 shows how the f i l e desc r i p t i on i s s to red . When the s imulators wish to re fe rence .a f i l e they need only use the l o g i c a l f i l e number. The system f i l e may be a temporary f i l e by de fau l t or a permanent f i l e by request . I f any i n i t i a l data fo r a f i l e i s to be modi f ied then the data i s copied in to a system f i l e . I t i s i n s t r u c t i v e to understand the need fo r a l l of these d i f f e r e n t names: due\", to t he i r independence.. lithe s imula tor , the user , and the system may a l l use d i f f e r e n t names to reference the same f i l e . The table contains the address of the key l i s t i f the f i l e i s cu r ren t l y being re ferenced. The entry po int name i s to be used when con t ro l i s passed to the s imula tor . Each entry i n the f i l e table contains a po in te r to the des c r i p t i on of the f i e l d s w i th in the f i l e . The f i e l d des c r i p t i on cannot appear w i th in the f i l e de s c r i p t i on table because there are a vary ing number of f i e l d s w i th in a f i l e . \u00C2\u00A7 B.2 the s imulator tab le The s t ruc ture of the s imulator tab le i s very s i m i l a r to the f i l e t ab le . Each main s t ruc ture (a DSECT over lay) has the s imulator name . and- fac ts about i t ; the- substructures- have a vary ing l i s v t . o f , input and output f i l e s , F i g u r e ;7 shows how the s imulator t a b l e ' i s scored . \u00C2\u00A7 B. 3 the p o l i c y vector tab le The s t ruc ture of the p o l i c y vector tab le i s s i m i l a r to the simu-l a t o r t ab l e . The tab le i s necessary fo r the i n c l u s i o n of p o l i c y vector 22. f i l e desc r i p t i on f- . f i e l d f i e l d i desc r i p t i on desc r i p t i on I^m-i 1 f i l e desc r i p t i on f n f i e l d desc r i p t i on f 1 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 f i e l d desc r i p t i on . f n l f i l e desc r ip t i on table conta ins : 1. l o g i c a l f i l e number 2. user name fo r f i l e 3. name of permanent f i l e f o r i n i t i a l data ' 4 . \u00E2\u0080\u009E name of system f i l e fo r data 5. address of k e y l i s t 6. number of keys 7. number of f i e l d s 8. format of a l l values i n f i l e 9. l o c a t i on of object module of s imulator that produced data 10. entry point i n s imulator 11. po in te r to f i e l d desc r i p t i on f i e l d desc r ip t i on table conta ins : 1. user f i e l d name 2. un i ts fo r name 3. i n d i c a t i o n of whether f i e l d name i s a key or not f i gu re 6: f i l e desc r i p t i on table 23. '\u00C2\u00AB\u00E2\u0080\u00A2 s imulator * , . input f i l e j . . desc r i p t i on s^ output. f i l e \u00E2\u0080\u00A2' \u00E2\u0080\u00A2 s imulator tab le conta ins : 1. s imulator name 2. name of object f i l e fo r s imulator 3. f l a g to ind i ca te i f i t i s i n core A. loader address of object module 5. po in te r to input table 6. number of input f i l e s 7. po in te r to output tab le 8. number of output f i l e s . input table conta ins : 1. l o g i c a l f i l e number. 2. f l a g to i nd i ca te whether or not input values are fo r current year or previous year output table conta ins : 1. l o g i c a l f i l e number f igure 7: s imulator desc r i p t i on table 24. i n te r ven t ion by the user . The range of the p o l i c y va r i ab l e and i t s values may be changed1 dynamical ly through the CHANGE command. The p o l i c y tab le has a header, which does not repeat f o r each hew d e s c r i p t i o n , that contains the number of p o l i c y des c r i p t i ons , the defau l t year f o r begin year (the f i r s t year f o r which s imulators produce data) and end year (the l a s t year fo r which s imulators produce data) . The s t ruc ture of the p o l i c y vector tab le i s shown i n f igure 8. The order i n which the p o l i c y va r i ab les are stored needs the establ ishment of a communication convention because the s imulators which need access to vajjuest of ^the' p o l i c y vector need not use the same names as the user . Therefore , the convention was es tab l i shed that-the order i n which the p o l i c y va r i ab les appear i n the p o l i c y vec tor desc r i p t i on would be the same as i n the C0MM0N array- thatAcontains the va lues . Both the superv isor and the s imulator use the same C0MM0N b lock name hence t rans fe r of data\"values i s t r i v i a l . The f i r s t few pos i t i ons of the p o l i c y vector are reserved fo r the superv isor to pass informat ion to the s imula tor . For ins tance , the convention was es tab l i shed that the f i r s t p o s i t i o n would be the p ro j ec t i on year (the year f o r which the s imulator i s to produce data ) , the second p o s i t i o n would be the end year (the l a s t year of s imu la t i on ) , the t h i r d p o s i t i o n would be the current year (usual ly the begin year ) , and the fourth p o s i t i o n would be fo r the year increment va lue , de fau l t i ng to one. \u00C2\u00A7 B.4 device taa ie Knowledge of the l a s t two t ab l e s , the device table and c lass t ab l e , i s not e s s e n t i a l fo r an understanding of the superv i so r , but i t - i s inc luded fo r the sake.of completeness. The s t ruc ture of the device table 25. header poMcy-yarrapTe description p^ affected f i l e j value range Ik1. policy vector table contains: 1. name of policy variable (user name for element in policy vector) 2. minimum increment size 3. units of policy variable 4. number of files affected by policy change 5. pointer to a l i s t of files 6. number of value ranges 7. pointer to l i s t of value ranges 8. base year (first year the user] n n l n2 n3 n NEW SUPERIMP0SED [0N AREA a] where: v^ . . i i s theOi'.'th d i sp lay va r i ab l e v \u00E2\u0080\u009E , a , r _ ^ are the values assoc iated with the preceding parameters (may be r e a l or integer) t can be ' b a r ' , ' l i n e ' , ' d o t ' , ' c o n t o u r ' , or 'map' n i s the number of d i sp lay va r i ab les (from 2 to 4) [] i nd i ca te op t iona l port ions The method of at tack i s as fo l lows . The output of the SCANNER i s a s t r i n g of i n tege rs , and a s t r i n g of f l ags i nd i c a t i ng the s i g n i f i -cance of the corresponding in teger . These s t r ings are passed i n a COMMON area to the DISPLAY rou t ine . Since a DISPLAY command may be issued to graph only the values of a p o l i c y va r i ab l e or a l l of the p o l i c y vector (syntax not shown) a check fo r th i s s i t u a t i o n i s made immediately. I t i s inconvenient to search the command each time some informat ion from the command i s needed. Therefore as informat ion 3 5 . about each d i sp lay v a r i ab l e i s discovered i t i s p laced i n a sec t ion of storage which i s ove r l a i d by the display, DSECT. Stor ing the informat ion i n th i s d i sp lay DSECT has the advantage that any change to the syntax of the DISPLAY command only a f f e c t s the i n i t i a l part of the program. The d i sp lay DSECT contains the d isp lay name, the values of ariy.'FR0M', 'T0', or 'BY' mod i f i e r s , \"the value of the rate if. s p e c i f i e d , and a f l a g to i nd i ca te whether or not th i s f i e l d i s \"to be iised to sequence the d i sp l a y . I t contains more informat ion which i s descr ibed l a t e r because i t i s not f i l l e d i n u n t i l l a t e r stages of the DISPLAY rou t i ne . The d isp lay DSECT i s i n C0MM0N and i s used to store informat ion discovered i n one ' sec t i on of code but not used u n t i l another s e c t i o n . \u00C2\u00A7 3 . b u i l d i n g a tree of va r i ab l e r e l a t i onsh ips The second stage of the DISPLAY subroutine involves bu i l d i ng a tree s t ruc ture to,show the r e l a t i onsh ip between the d isp lay va r i ab les (v^'s) used i n the command. This stage i s necessary fo r severa l reasons. The consistency of the DISPLAY command must be checked. Each of the va r i ab les mentioned i n the DISPLAY command i s compared with en t r i es i n a f i e l d . d e s c r i p t i o n table assoc ia ted with some f i l e desc r i p t i on t ab l e . I f the d isp lay va r i ab l e i s not found i n any f i e l d desc r i p t i on table then each name w i th in the po l i c y vector i s compared to the d i sp lay v a r i a b l e . I f the d i sp lay va r i ab l e i s not found among the po l i c y va r i ab les then the DISPLAY command cannot be processed. The f i e l d names mentioned i n the DISPLAY command need not appear i n the same f i l e . There must be some method o f - r e l a t i ng the f i l e s which conta in the appropr iate d i sp lay v a r i a b l e s . The obvious method to make ce r t a i n that the f i e l d names i n two separate f i l e s are l i nked i s to i n s i s t that there ex i s t 36. at l e a s t one common key between the f i l e s . I f there are more than two d isp lay va r i ab les then the l inkage between the f i l e s need only be pa i rw ise , i n other wordSj i t i s not necessary to.have a common key among a l l f i l e s that conta in d i sp lay v a r i ab l e s . For example consider the l o g i c a l f i l e desc r i p t i on of the keys i n fo l lowing three f i l e s . f l i e 1 f i l e 2 f i l e 3 A B C B C D D E \"i= =rt r f i gu re 10: example of pairwise l i nks between f i l e s . Then f i l e 1 i s r e l a t ed to f i l e 2 v i a keys BC, and f i l e 2 i s r e l a t ed to f i l e 3 v i a key D. With the simple add i t i on i n each f i l e of a spec i a l sequence of f i e l d s , c a l l e d keys, the c a p a b i l i t y of the DISPLAY command has been extended tremendously by a l lowing c r o s s - f i l e d i sp l a y s . I t i s at th i s stage that the DISPLAY command i s examined fo r consistency i n the use of r e l a t i n g f i e l d s through common keys. This informat ion i s necessary fo r the ex t rac t i on process . \u00C2\u00A7 3.1 method of at tack Why i s i t necessary to b u i l d the r e l a t i onsh ip in to a tree structure? There are severa l other more s t ra ight fo rward , methods of approach. One method could be to jus t look fo r a l e f t-tor?right l inkage i n the d i sp lay va r i ab les (v^ -> v^ ->- v^) . Another method would be to p i ck any one of the d i sp lay va r i ab les as a s t a r t i n g p o s i t i o n and then look fo r any -sequence of pa i rwise l i nk s such that every va r i ab l e i s i n the chain (v., -> v. \u00E2\u0080\u009E \u00E2\u0080\u00A2+ v.. \u00E2\u0080\u009E -\u00C2\u00BBv., ) . The o r i g i n a l order ing has been scrambled so i i x2 x3 i4 that a l inkage between the va r i ab les may be es t ab l i shed . Nei ther o f , these methods were used. A more general method was developed that 37. encompasses these two methods as spec i a l cases. The general method involves b u i l d i n g a tree s t ruc ture of the r e l a t i onsh ips between the d i sp lay v a r i ab l e s . I t i s qui te easy to see how th i s encompasses the f i r s t two methods. One of the extensions planned fo r the system i s to al low a more complex s t ruc ture f o r the data base. Whenever poss ib l e th i s extension has been kept i n mind when the algorithms were developed. I f the complex data base has a tree s t ruc tu re then th i s a lgor i thm can be used to d iscover the l inkages between the v a r i ab l e s . Now to exp la in how th i s a lgor i thm works. The a lgor i thm i s d i v ided in to two pa r t s : the f i r s t part checks every d i sp lay va r i ab l e to make c e r t a i n that i t i s contained i n a desc r i p t i on t ab l e ; the second par t bu i l d s the t r ee . The operat ion can be v i s u a l i z e d by examining the flow chart i n f i gu re 11. The f i r s t sec t i on searches through a l l of the f i e l d desc r ip t ions comparing each f i e l d name with a d isp lay v a r i a b l e . The f lag\u00C2\u00A9 that i s set w i th in the d i sp lay DSECT to i nd i ca te a po l i c y v a r i ab l e i s checked during the second phase because a p o l i c y va r i ab l e has no key and therefore cannot be ; l inked to any of the non-pol icy d i sp lay v a r i ab l e s . When one of the non-pol icy d i sp lay va r i ab les i s found the fo l lowing informat ion i s added { to the d i sp lay DSECT. The p o s i t i o n of the f i e l d i n the f i l e i s s tored fo r use when the data, value i s to be extracted from the f i l e . The t o t a l number of keys assoc ia ted with the f i l e i s recorded. The name of the f i l e which contains the f i e l d i s s to red . A f l a g i s set to i nd i ca te the f i e l d has been found. A lso data i s i n i t i a l i z e d w i th in the d i sp lay DSECT fo r the second phase; th i s i s done because a l l of the tree po inters are stored w i th in the d i sp lay DSECT. stage one: po inter to f i r s t d isp lay va r i ab l e t \u00E2\u0080\u00A2 yes add informat ion to d i sp lay DSECT 38. i s d isp lay va r i ab l e containedX no^ i n a f i l e as f i e l d name? / i s d i sp lay va r i ab l e contained as p o l i c y va r iab le ? . 1 , yes \u00E2\u0080\u00A2 set f l a g i n e r ror d i sp lay DSECT message no ^ any more d i sp lay v a r i a b l e s ? ^ no ^return^ yes update po inter to next d i sp lay va r i ab le stage two: ass ign f i r s t d i sp lay va r i ab l e as parent ^return^-*^ no 4) i s there another d i sp l ay\ yes va r i ab l e not i n tree? / \ no pop up one l e v e l i n stack of parents r any more d i sp lay va r i ab les not i n tree? set po inter to the next d i sp lay va r i ab le t yes i s i t a po l i c y var iab le? / yes update po inter to next c h i l d not already i n tree yes no no/ is th i s d i sp lay va r i ab l e a c h i l d , i e . is t h e i r a set of common key with parent?. yes update informat ion i n parent and c h i l d d i sp lay DSECT n 0 / past the \ ^a c h i l d i s po l i c y va r i ab le ?^\u00E2\u0080\u0094 f i r s t pa r en t ? / T yes no make the c h i l d the parent ; keep push down stack of previous parents e r ror message \u00C2\u00A9 \u00C2\u00A9 ^return^ f i gu re 11: flow chart fo r bu i l d i ng of r e l a t i onsh ip between d isp lay va r i ab les 39. The second phase of the a lgor i thm assigns the f i r s t v a r i ab l e i n the DISPLAY command to be the parent ( i t i s assumed that >the parent-ch i ld terminology used i n d i scuss ing nodes of a tree i s f a m i l i a r to the reader ) . The program then searches fo r a c h i l d of the parent . A c h i l d i s any va r i ab l e which i s r e l a ted to the parent by a set of common keys. The program f i r s t t r i e s the second d isp lay va r i ab l e as a prospect ive c h i l d . I f no common keys ex i s t with the parent then the program t r i e s to match each of the remaining d i sp lay va r i ab les i n turn to the parent v i a common keys. I f no match i s found then the DISPLAY command must be re jec ted because there ex i s t s a va r i ab l e which cannot be l i nked to any other v a r i a b l e . Whenever a match can be made a search i s made fo r the maximal set of common keys-. The maximal set of common keys i s des i red it f o r gene ra l i t y . The keys are used extens ive ly during the ex t rac t i on process . When a c h i l d to the parent i s found, informat ion w i th in the pa ren t ' s arid c h i l d ' s d i sp lay DSECT must be updated. The fo l lowing are added to the c h i l d ' s d i sp lay DSECT: the address of the f i r s t key i n the f i l e , the s t a r t i n g p o s i t i o n of the matching keys with the parent , the number of consecutive matching keys, a po in te r to the d isp lay DSECT of the parent , a f l a g to i nd i ca te the va r i ab l e has been placed i n the t r ee . The fo l lowing are added to the parent ' s d i sp lay DSECT: s t a r t i n g p o s i t i o n of the f i r s t matching key, an update of the number of c h i l d r e n , and a po in te r to the d i sp lay DSECT of the c h i l d . A push down stack i s kept of a l l previous parents . The newly found c h i l d i s now given the r o l e of parent and the rout ine proceeds to search through a l l of the unclaimed d isp lay va r i ab les (those not already i n the tree) to f i n d a su i t ab l e , c h i l d . I f a c h i l d cannot be found then the l a s t parent i s obtained 40. from the push down stack and a search i s made fo r another c h i l d of the parent . Of course, i t i s assumed that a po l i c y v a r i ab l e cannot be l i nked in to the t ree . I t should be noted that because the f i r s t element i n the DISPLAY command i s chosen as the f i r s t parent that i t i s the root of the t r ee . Hence the lef t-tor-r ight order ing i n the d i sp lay va r i ab les i s found i f i t i s present , otherwise any cons is tent order ing i s detected. \u00C2\u00A7 3.2 examples Suppose the fo l low ing type^ of DISPLAY command i s i s s u e d : . DISPLAY v, BY v_ BY v \u00E2\u0080\u009E BY v,< 1 2 3 *4 where v^ ( i = l , . . . , 4 ) are a l l non-pol icy d i sp lay v a r i a b l e s . The examples i n f igure 12 give a l l poss ib l e non-isomorphic trees that r e su l t from the above DISPLAY command. I f a d i sp lay v a r i ab l e v^ ex i s t s which i s not r e l a ted to any other f i e l d then d i s j o i n t trees r e s u l t , and hence the DISPLAY i s inva l id . / , If i ;any of the d i sp lay va r i ab les i s a p o l i c y va r i ab l e then i t does not appear i n the t r ee . The a lgor i thm i s independent of the number of d i sp lay v a r i ab l e s . \u00C2\u00A7 4. generat ion o f fda ta A f t e r the tree of va r i ab l e r e l a t i ons i s b u i l t , the data assoc ia ted with the d i sp lay va r i ab les must be generated. I f a po l i c y v a r i ab l e i s present i n the DISPLAY command then a spec i a l sequence of code must be executed. Each time the value of the p o l i c y va r i ab l e changes the CHANGE rout ine must be c a l l e d , and qui te poss ib l y a l l of the values assoc ia ted with each d i sp lay va r i ab l e must be re-generated. The data fo r a f i l e i s generated by a recurs i ve rou t ine , c a l l e d FILL, that c a l l s the s imu la to rs . Once a l l of the data has been generated then the 41. 42. per t inent data i s ex t rac ted . One may ask why the data i s not extracted as soon as i t i s generated, but i t turns out that s p l i t t i n g the data generat ion and data ex t rac t ion in to two separate algorithms makes each one eas ie r to code and eas ie r to conceptual ize s ince they are d i s t i n c t processes. This i s the general framework in to which the fo l low ing d e t a i l s of operat ion f i t . The a lgor i thm i s v i s u a l i z e d through the flow chart i n f i gu re 13. \u00C2\u00A7 4.1 method of operat ion i f rib po l i c y va r i ab l e The f i r s t step the program takes i s to e s t ab l i sh l i m i t s fo r the time i n t e r v a l when i t c a l l s the s imula tors . Remember that s imulators are c a l l e d by time. That i s the key they use to know what data to generate. F i r s t the program checks the d isp lay DSECT to see i f time i s mentioned ins the DISPLAY command. I f so then.a check i s made to see whether a 'FR0M' or;.: 'T0' mod i f i e r i s mentioned. I f so then the 'FROM' time i s copied in to a s p e c i a l v a r i ab l e ho ld ing the begin year ( f i r s t year to produce data ) , and the 'T0' time i s copied into a s p e c i a l va r i ab l e ho ld ing the end year ( l as t year to produce data ) . I f there are not 'FR0M' or 'T0' f i e l d s assoc ia ted with time, or i f there i s no time f i e l d mentioned i n the DISPLAY command then the program extracts the de fau l t values fo r begin year and end year from the p o l i c y vec to r . Throughout th i s sec t ion i t i s assumed that no p o l i c y va r i ab l e i s present i n the DISPLAY command. Once the f i l e that contains the d i sp lay va r i ab l e has been loca ted , each of the key f i e l d s i s compared with the keyword ' t i m e ' . I f the key ' t ime ' i s not present i n the f i l e then the assumption i s made that the f i l e i s s t a t i c and that a l l of the i n f o r -mation i s already i n the f i l e . Iri other words the contents of the f i l e are time independent and must be suppl ied as i n i t i a l data fo r the f i l e because i t cannot be generated by a s imula tor . es tab l i sh time i n t e r v a l f o r c a l l to s imulators (begin year and end year) 43. i s any d isp lay va r i ab l e a po l i c y var iab le? , yes set f l a g on no set f l a g o f f po in ter to f i r s t d i sp lay va r i ab l e ^ i s the d isp lay va r i ab le a po l i c y v a r i a b l e ? ^ no yes f i nd f i l e that has the d isp lay va r i ab l e i n i t \u00C2\u00A9 ass ign large arrays fo r each d i sp lay va r i ab l e into which i t puts extracted data set up character s t r i n g fo r CHANGE command ^ i s ' t ime ' a k ey ?^ no yes CALL SCANNER CALL CHANGE c a l l s imulators to generate\"data fo r th is f i l e from begin year to end year s t a t i c f i l e so do not generate data.. ^ l a s t d isp lay v a r i ab l e ?^ \u00C2\u00BB\u00E2\u0080\u0094^is f l a g on?^ yes 1 no update po inter to next d isp lay va r i ab le no c a l l ex t rac t ion a lgor i thm c a l l ex t rac t ion a lgor i thm no / i s i t the same f i l e as the \ l a s t d isp lay var iab le? (return] yes no yes copy returned arrays in to large arrays and put i n p o l i c y value i ~ ^ts r e su l t T^0 modifier?^-*\u00E2\u0080\u0094 add increment to modi f ie r of po l i c y vector (c) (return) f igure 13: flow chart fo r generat ion of data 44. The rout ine FILL i s c a l l e d when the s imulators are to generate the data . The rout ine FILL- i s descr ibed i n sec t ion 4.3 I t i s worth mentioning that when a s imulator generates data fo r a f i l e i t generates data fo r every f i e l d w i th in the f i l e , not j u s t the f i e l d mentioned i n the DISPLAY command. Hence a check i s made before the procedure i s r es ta r ted to see i f the next d i sp lay va r i ab l e and the l a s t d i sp lay v a r i ab l e are i n the same f i l e . I f they are then the data has already been generated. A f t e r a l l of the data i s generated f o r a d i sp lay v a r i -able then the s imulators are dynamical ly unloaded (they were dynamical ly loaded i n the f i r s t c a l l to the rout ine F ILL ) , and the key l i s t s of the input and output f i l e s assoc ia ted with the s imulators are re leased from core s torage. A f t e r a l l of the data has been generated fo r a l l of the d i sp lay va r i ab les then a c a l l i s made to a rout ine that ext racts the per t inent data. \u00C2\u00A7 4.2 method of operat ion i f a po l i c y va r i ab l e i s present Before the program l o g i c i s descr ibed i n d e t a i l some general i n f o r -mation about the p o l i c y vector and changes i n p o l i c y va r i ab les should be known. Suppose that a l l of the data has been generated with the p o l i c y value f i x e d . When the p o l i c y value i s a l t e red fo r the next i t e r a t i o n some data i s going to be n u l l i f i e d - poss ib l y some of the data that was prev ious ly generated. So before the p o l i c y value i s changed the prev ious ly generated data must be saved i n a storage l o c a t i o n . But datascan only be stored a f t e r i t i s extracted from the data base', hence the ex t rac t i on a lgor i thm must be invoked before the p o l i c y value i s changed. I t i s use fu l to know that the data ex t rac t i on rout ine returns n arrays(where n i s the number of non-pol icy d i sp lay 45. var iables ) each conta in ing a l i s t of the data values fo r a d i sp lay v a r i a b l e . The fo l low ing program l o g i c t reats the p o l i c y v a r i a b l e s . Suppose that a p o l i c y va r i ab l e i s found. Large storage areas are assigned dynamical ly to each d i sp lay v a r i a b l e . A po inter to the storage i s p laced i n the d isp lay DSECT. A check i s made to make c e r t a i n that the program does not t ry to generate data fo r a p o l i c y v a r i a b l e . A l l of the other d isp lay va r i ab les have data generated exact ly as descr ibed i n the l a s t s e c t i o n . In the l a s t sec t ion a f t e r a l l of the data i s generated the s imu-l a t o r s are unloaded and the ex t rac t ion process i s c a l l e d . ' But now i f the f l a g i s on then the s imulators are not unloaded because i t i s poss ib l e they w i l l have to generate more data a f t e r the p o l i c y value i s changed. The ex t rac t ion process i s c a l l e d . The arrays of data values in to which the ex t rac t ion process places i t s r e su l t s are copied into the l a rger arrays that were created as soon as i t was discovered that a p o l i c y va r i ab l e was present . These large arrays can be extended dynamical ly i f they are not la rge enough to hold the copied va lues . The ex t r ac t i on process does not re turn an array fo r the p o l i c y v a r i a b l e . But i t i s necessary to have the present p o l i c y va lue-assoc iated with each of the extracted values when the values are passed to the graphics superv i sor . Therefore i n the large array set aside f o r the p o l i c y va r i ab l e the p o l i c y value i s repeated the same number of times as there are values i n the arrays returned from the ex t rac t ion process . A f t e r the smal l arrays are copied in to the large arrays the space reserved f o r the smal l arrays i s re l eased . Then the increment modi f i e r i s added 46. to the current p o l i c y va lue . When a l l of the p o l i c y value changes have been made then the s imulators are unloaded, the key l i s t s r e -l eased , and the data values are sorted and'then passed to the graphics superv i so r . . \u00C2\u00A7 4.3 desc r i p t i on of the subroutine that c a l l s the s imulators When data fo r a f i l e has to be generated fo r a s p e c i f i c time then the rout ine FILL i s c a l l e d . The rout ine FILL i s recurs ive because the input data f i l e s of ..the s imulator that has to produce the des i red output f i l e may not have enough data . Hence the s imulator which produces data fo r these f i l e s must be loaded, but once again the input f i l e s fo r th i s s imulator may not have enough data. I t i s assumed that a f i l e cari be wr i t t en by only one s imula tor , but a s imulator can wr i te many f i l e s , and read many f i l e s . The s t ruc ture of the s imulator i n t e r- re l a t i onsh ips may be shown i n the fo l lowing example: r f 11 r f 12 where: rf. . S. x out by the s imulator i s a s imulator x i s a f i l e wr i t t en i s a f i l e read i n the s imulator S. wf 31 wf 32 f igure 14: example of recurs i ve s imulator c a l l s . 47. In the above example i f data i s requi red from f i l e w f ^ then rf^^ must have enough data i f i s to be run; but suppose i t does not have enough data . S i n c e ' r f ^ . == w f ^ t n e n the program must check a l l of the input data fo r S^- Suppose that the input f i l e r r 2 2 does not have enough data but the input f i l e r^2\ ^ o e s n a v e enough data , then the knowledge that rf-22 = W^12 '*'S u s e \u00C2\u00A3 i a n d FILL looks at the input f i l e s fo r S^. Now suppose that a n ^ r ^ i 2 koth n a v e enough data so that FILL can s t a r t poping up from the recurs i ve c a l l s , and f i n a l l y generate data fo r wf^* Now the de t a i l s of operat ion w i l l be exp la ined. The f i r s t opera -t i on i s to tes t the f i l e to see i f i t i s a s t a t i c f i l e or not . This i s done by comparing the name of the s imulator that generated the data to the s p e c i a l name ' n o s i m ' . I f the f i l e i s s t a t i c then i t i s assumed that a l l of the data i s present so a re turn i s made from FILL. I f the f i l e i s not s t a t i c than a tes t i s made to see i f there i s any data fo r the current year (the year fo r which the s imulator i s to produce data ) . This i s done qui te convenient ly by c a l l i n g the rout ine SFIND. I f the data i s present fo r the current year then a re turn i s made from FILL. I f there i s not enough data then the object module of the s imulator that produces the data must be loaded. This i s done by using the name of the s imula tor , which i s i n the f i l e desc r i p t i on t ab l e , to f i n d the cor rec t entry i n the s imulator desc r i p t i on tab le , which has a l l of the informat ion about each s imula tor . I f the s imulator i s not i n core then the object module i s loaded. A f t e r i t i s loaded the loader 'address i s p laced i n the s imulator desc r i p t i on t ab le . Now each of the input f i l e s of the s imulator must be examined to make c e r t a i n that they have enough 48. data . In each f i l e a check i s made to see whether the s imulator wishes to have data fo r the current year or from the previous year . I t i s assumed fo r s i m p l i c i t y that a .s imulator may use input data from only one previous year . This i s an assumption that should be re laxed i n a more general system. I f the previous year ' s data i s requi red then the increment i s subtracted from the current year . The recurs i ve loop i s entered by c a l l i n g FILL to d iscover i f there i s data fo r the current year . This procedure must be c a r r i ed out fo r a l l of the input f i l e s used by the s imula tor . A f t e r a ,s ta te i s reached such that a l l of the input f i l e s have enough data then before con t ro l i s passed to the s imulator the p o l i c y vector must be f i l l e d . I t must be f i l l e d with the cor rec t p o l i c y values fo r the current year ; and th i s must be done fo r each c a l l to a s imulator because the p o l i c y values can vary over t ime. This i s done by p i ck ing the co r rec t values from the po l i c y vec tor desc r i p t i on table and p l ac ing them i n ; a common array which the s imulators re ference . The current time i s p laced as the f i r s t value i n the p o l i c y vector so that the s imulators know for which year to produce data . Contro l i s then t rans fe r red to the s imulator so that i t can generate data , and one recurs i ve l e v e l i s then d imin ished. The s imulators remain loaded so that they may be used i n the generat ion of other data . They are un-loaded when a l l of the data i s generated. \u00C2\u00A7 5 . ex t rac t ion of data The problem of data ex t rac t ion f a l l s under the category of i n f o r -mation r e t r i e v a l . The problem i s e s s e n t i a l l y to r e t r i e ve some informa-t i on from a large data base. The a lgor i thm to extract the data i s 49. qui te general even though the data base used i n the system i s qu i te . s imple . Each f i l e i n the data base cons is ts of records with only one format . ' In order to genera l ize th i s s t ruc ture each f i l e should be allowed a tree s t ruc ture of i t s elements. With th is type of data base the r e l a t i onsh ip of the d i sp lay va r i ab les i s a tree s t ruc tu r e . A more de ta i l ed d i s cuss ion of th i s extension i s i n CHAPTER IV, but i t i s Mentioned now t o ' i l l u s t r a t e the sense of using the general a lgor i thm to b u i l d a tree of va r i ab l e r e l a t i ons i n sec t ion 3. But even with the simple data s t ruc ture the data ex t rac t i on i s qui te compl icated. In f ac t most of the problems of data ex t rac t ion that would a r i s e with a more complex data base a lso a r i s e with the simple data base. The reason i s that the bu i l d i ng of the tree s t ruc ture of r e l a t i onsh ips that i s used when the data ex t rac t ion i s t r y i ng to mark keys so that i t knows which data value to extract becomes more d i f f i c u l t with the complex data base not the ex t rac t ion process . Before the data i s extracted i t i s assumed that there ex i s t s-a tree s t ruc ture fo r the r e l a t i onsh ip between the d i sp lay v a r i ab l e s . Once the data i s generated and placed i n the data base the only means of i d e n t i f y i n g i t at a l a t e r stage i s by using the keys which are assoc ia ted with the data va lue . I t has been s ta ted that ex t rac t ing data from even a simple data base i s d i f f i c u l t . Here are some of the reasons. Remember that more, than one d i sp lay va r i ab l e ex i s t s so a whole set of dataCvalues must be extracted such that each d i sp lay va r i ab l e has a data value assigned to i t . These data.values must be cons i s ten t , i n other words they must a l l be l i nked through key values using the tree s t ruc ture to show which 50. keys are to be used. But the necess i ty of having to extract a cons is tent set of data values causes some problems. Suppose a f i l e has three keys and the rout ine i s t r y i ng to match key-values on the second and t h i r d key. There may ex i s t more than one set of common key values that are the same but that have d i f f e r e n t data va lues . This i s true because the f i r s t key may vary whi le the second and t h i r d keys remain the same. Therefore the match process may f i n d n (n > 1) key values matching with 1 key value (or 1 key value matching with n key values) which i s reason-ab le , and i t i s taken care of by dup l i c a t i ng the data value assoc ia ted with the one key value n-1 t imes. I f the program matches n (n > 1) key values to n other key values then each of the corresponding data values are matched. I f the program matches n (n ^ l)*-key values to m (m > i l , m ^ n) key values then nothing reasonable can be done and the data ex t rac t ion process must terminate with an er ror message that the DISPLAY command i s i n v a l i d . A l l of these problems are a lso encountered i f the data base i s more complex. But most of the add i t i ona l problems are encountered i n the s e t t i ng up of the tree of r e l a t i o n s h i p s . Now i t should be c l ea r why the data generat ion and data ex t rac t i on are broken up in to independent modules. \u00C2\u00A7 5.1 method of operat ion The ex t r ac t i on operat ion involves two subrout ines : EXTRACT and REXTRACT. EXTRACT i s the d r i ve r fo r the recurs i ve ex t rac t i on rout ine REXTRACT. The general idea i s that the d r i ve r does some i n i t i a l i z a t i o n , ' and then sets a po in te r to the key values i n a record assoc iated with the dominant parent (the root of the t r ee ) . I t then c a l l s REXTRACT which t r i e s to match key values beginning from the l ea f s of the t r ee . 51. By beginning at the l ea f s of the tree data values may be dupl i ca ted at the lowest l e v e l f i r s t i f i t i s discovered at the next h igher l e v e l that an,n to. 1- match has. occured . \"''The 'aigorithm is recursive-' s ince the procedure i s the same fo r every parent i n the t r ee . When a l l matches have occured the rout ine returns to EXTRACT which then .updates the po in te r i n the root of the tree and c a l l s REXTRACT aga in . This gives a very crude idea of the main operat ions of the ex t rac t ion process . To get a be t t e r idea of how the ex t rac t ion process works more de t a i l s are given i n the flow chart i n f i gu re 15. I f any of the d i sp lay va r i ab les i s a p o l i c y va r i ab l e then no ex t rac t i on i s done. A copy i s made of the k e y l i s t fo r the f i l e assoc ia ted with each d i sp lay v a r i a b l e , and i t s l o c a t i on i s placed i h d i sp lay DSECT. This may seem i n e f f i c i e n t i f more than one of the d i sp lay va r i ab les occur i n one f i l e , but i t i s eas ie r to do th i s than to handle s p e c i a l cases w i th in the recurs i ve code. Now fo r each unique set of keys i n the dominant parent the rout ine REXTRACT i s c a l l e d . By set of keys i t i s meant the complete set of \u00E2\u0080\u00A2 keys , not j u s t the common keys with one of i t s c h i l d r e n . The rout ine REXTRACT i s given a po in te r to the set of keys upon which a match i s sought, and a po inter to the d i sp lay DSECT of the parent . The reason REXTRACT i s c a l l e d only with the unique keys i s that i f two keys are the same then the program avoids dup l i c a t i ng the set of va lues . When a l l of the key values have been examined then the k e y l i s t s are f reed and the code returns from EXTRACT. Therefore EXTRACT i s nothing more than a d r i ve r fo r REXTRACT. A l l of the work of ex t rac t ing the sets of data values f a l l s on the shoulders of REXTRACT. REXTRACT i n i t i a l i z e s some parameters then makes 52. EXTRACT set a po inter to key value i n dominant parent create storage fo r the data values of each d isp lay va r i ab l e 1. \u00E2\u0080\u00A2c^ are the keys unique?^ yes c a l l REXTRACT no update the po in te r to the key values \"t^end of key l i s t ?^\u00E2\u0080\u0094\u00E2\u0080\u0094*\u00E2\u0080\u0094( re tu rn } no REXTRACT *-< delete or ext ract values? 0 p ext rac t set po inter to key values ^ de lete delete values n-1 ? ^ {return f i nd a match with parent? yes no yes no update po inter i n k e y l i s t p lace data value i n array ^ f l l e have any children?^-no ^end of key l i s t ?^-delete values, by s e t t i ng f l a g and c a l l i n g REXTRACT (re turn to\ EXTRACT J no yes yes ^atiy dupl i ca te key values?^-^^-freturn to ^ \ parent J r ecu rs i ve l y c a l l REXTRACT 1 put value i n array fo r d isp lay va r i ab l e update po inter i n k e y l i s t , I /any common keys to match? ? 1 yes lno \u00C2\u00A9 \u00C2\u00A9 update po inter i n k e y l i s t ^ i s match n to n ? ^ no yes -\u00C2\u00BB~^is match 1 to n?^-1 yes generate n-i no match must be n to m more values e r ro r message (return^ f ig'ure 15: flow chart fo r ex t rac t ion of data 53. a check to see whether or not the c a l l i s to delete data values or to ext ract data va lues . The reason data values may be deleted i s that i n a c h i l d i t may be discovered that there i s no common key value that corresponds to. the common-\"key value i n the parent . Hence a l l data values recorded fo r that match i n the parent and i n every r e l a t i o n back to the dominant parent have to be de le ted . Otherwise the rout ine begins examining the f i r s t set of key values i n i t s k e y l i s t . A po inter i s set to the current set of keys, and a match i s sought between these keys and.the,keys passed to REXTRACT, The match i s tested only on the common keys. The p o s i t i o n of the f i r s t common.key and the number of common keys i s a lready i n the d i sp lay DSECT. I f the l i n e number assoc -i a ted with the key l i s t i s zero then i t i s assumed that the key values have already been matched. I f REXTRACT f inds a match with key values that have a non-zero l i n e number then the number of points returned i s inc reased , and the data value i s p laced i n the data array fo r the v a r i -ab le . This i s done by. c a l l i n g a rout ine which returns a data record/, given a l i n e number and a l o g i c a l f i l e number. Then the data value f o r the appropr iate f i e l d i n the data record i s extracted and placed i n the data array fo r the d i sp lay v a r i a b l e . I f there i s no more room i n the data array then more space i s obta ined. Thentthe l i n e number assoc iated with the matched key value i s zeroed out . The res t of the key l i s t i s searched fo r a dup l i ca te match of a l l keys unless the f i l e has no c h i l d r e n . This i s done to catch a l l dup l i ca t ions at the h igher l e v e l so that the lower l e v e l i s not c a l l e d with the same key va lues . Whenever a dup l i ca te match i s found the data value i s placed i n the array f o r the d i sp lay v a r i a b l e . I f the f i l e has no ch i l d r en then REXTRACT looks fo r more 54. common keys because i t i s at the lowest l e v e l and i t wants to search fo r a l l of the common key values before re turn ing to the parent . I f a match i s not made a f t e r comparing the key values then REXTRACT must move the po in te r i n the key l i s t down1one record to examine the next set of key va lues . The key l i s t s are sorted i n such a manner that the l a s t key i s sorted w i th in the l a s t ' - l key , . . . ,- the second key i s sor ted w i th in the f i r s t key. T h e r e f o r e , i f a match i s sought with a set of keys beginning with the f i r s t then the search fo r fu r ther matches a f t e r one i s found may terminate with the f i r s t f a i l u r e . I f a match i s sought with a set of keys such that the f i r s t key i s not inc luded then a sequent ia l search has to be made of the whole key l i s t when look ing fo r matches. When the k e y l i s t i s exhausted a f t e r looking fo r a l l dup l i ca t ions the search moves on to the c h i l d ; that i s i f there i s another c h i l d . I f not then a re turn i s made to the parent . I f there are more ch i l d r en then the parameters must be set up f o r the recurs ive c a l l to REXTRACT A po in te r must be set to the d i sp lay DSECT of the parent , and a po in te r to the key values i n the parent that must be matched i n the c h i l d . A f t e r the program returns from the recurs ive c a l l the type of match must be determined. In other words i s the match an n to 1, n to n, or n to m match? When the code returns from the recurs ive c a l l the number of key values matched i n the current f i l e i s compared to the number of matches returned. I f the match i s 1 to 1 then REXTRACT looks fo r the next match of the common keys with the parent . I f only one match i s r e t u rn -ed but the current f i l e has n matches then the program i s made to 55. repeat the recurs ive loop with the same key' values n-1 t imes; and hence generate the same value n-1 more t imes. Then REXTRACT looks fo r the next match of common keys with the parent . I f the recurs ion f a i l e d to produce any match then a l l of the data values extracted from d isp lay va r i ab les h igher i n the tree (those already c a l l e d i n the tree s t ructure ) must be .de l e t ed . This i s done by moving the po in te r i n the data array back over the cor rec t number of data e n t r i e s . REXTRACT then returns to EXTRACT to get a new set of keys to search fo r i n the f i r s t f i l e . I f n values are matched and the current f i l e has only.one value then th i s value i s dup l i ca ted n-1 t imes. I f an n to n match occurs then another match of common keys i s sought with the parent . I f an n to m match occurs then an er ror message i s g iven. \u00C2\u00A7 5.:2 example j With an a lgor i thm th i s complex an example should prove h e l p f u l . Suppose the fo l lowing data base e x i s t s : f i l e 1 f i l e 2 f i l e 3 a c . VI' a c b v 2 d b v 3 1 I 100 1 1 3 200 1 3 300 1 2 101 1 1 4 201 1 4 301 2 1 102 1 2 4 202 2 4 302 2 .2 103 . 1 2 4 202 2 5 303 2 2 103 2 1 2 3 203 2 2 5 204 f igure 16: example of a data base Where a c are the keys fo r f i l e 1; act b are the keys fo r f i l e 2; and d b are the keys f o r f i l e 3; and v^ i s the value fo r the i ' t h d i sp lay va r i ab l e which i s assoc iated with the record . Of course, each f i l e may have more keys other than those s p e c i f i e d ; and each f i l e may have 56. more value f i e l d s (maybe even a key) other than the one mentioned. But only one f i e l d value i s extracted from a f i l e . Remember that even i f a l l the values wanted are i n the same f i l e the ex t rac t i on process t reats each value as being i n a separate f i l e . Three f i l e s have been chosen f o r s i m p l i c i t y but the a lgor i thm i s independent of the number of f i l e s . The a lgor i thm to generate a tree s t ruc tu re of r e l a t i onsh ips generates the fo l lowing cha in : f i l e 1 i s re l a ted to f i l e 2 through keys a c; and f i l e 2 i s r e l a ted to f i l e 3 through key b. Now everything i s set up fo r the ex t rac t ion process . The fo l lowing set of data values i s extracted from the data base i n the example. A po in te r to the data values fo r each d i sp lay v a r i -able i s s tored i n the d i sp lay DSECT assoc ia ted with the d i sp lay v a r i a b l e . v 2 v 3 100 200 300 100 201 301 100 201 302 ioi 202 301 101 202 302 102 none 103 203 300 103 204 303 f i gu re 17: values extracted from the data base. L e t ' s examine how the data values are ex t rac ted . The rout ine EXTRACT sets a po in te r to the key values 11 i n the f i l e 1 and to the d i sp lay DSECT fo r f i l e 1. The rout ine REXTRACT i s t h e n ' c a l l e d . REXTRACT s t a r t s at the beginning of f i l e 1 looking fo r a match to 11. When i t f inds the match the data value 100 i s p laced i n the data array fo r d i sp lay va r i ab l e v.. . The res t of f i l e 1 i s searched fo r another 57. occurance of the key values 11. The search i s terminated when the key values 12 are found because the key values a r e . so r t ed . REXTRACT then c a l l s i t s e l f r e cu rs i ve l y look ing f o r a match i n f i l e 2 to the common key 11. In f i l e 2 the key values 113 match the parent . Hence the data value 200 issadded to the data array fo r d i sp lay va r i ab l e v^. F i l e 2 i s then searched fo r any fu r ther occurance of the complete key values 113. None i s found so REXTRACT i s again c a l l e d r e cu r s i ve l y look ing fo r a match i n f i l e 3 with the common key value 3. The key values 13 are found i n f i l e 3 which match the common key with the parent.. Thentthe data value 300 i s p laced i n the data array fo r the d i sp l ay va r i ab l e v^. F i l e 3 i s searched fo r any fu r ther occurence of the key value 13. Since the recurs ion cannot be continued by c a l l i n g ch i l d r en of the parent f i l e REXTRACT then looks fo r any fu r ther occur -ence of j u s t the common key 3. None i s found. Note that the whole k e y l i s t must be searched because the key l i s t i s not sorted on the key b, therefore the value 3 may appear anywhere. A f t e r the end of the key l i s t i s reached REXTRACT pops up one l e v e l of recurs ion to f i l e 2. Now the type of match between the parent and the c h i l d i s examined. I t i s a 1 to 1 match hence nothing s p e c i a l i s done. Now another occurence o f . t he common key value 11 with the parent i s searched fo r i n f i l e 2. The key values 114 are found hence the data value 201 i s added to the data array fo r v^. Another occurence of 114 i s searched fo r i n f i l e 2. None i s found. REXTRACT c a l l s i t s e l f looking i n f i l e 3 fo r the common key 4. The key values 14 are found, and hence the data value 301 i s added to the data array fo r v^\u00C2\u00AB There are no fu r ther occurences of 14. But the current f i l e has no ch i l d r en so REXTRACT searches for' any fu r ther occurence of the common key value 4. Another record 24 i s found, hence 58. the data value 3,02 i s added to the data array f o r V y There are no fur ther occurences o f ' t h e common key hence we pop up one l e v e l i n the r e cu r s i on . REXTRACT then examines the type of match. I t i s a 1 to n (n=2) match so that the data,va lue 201 must be copied n-1 times i n the data array fo r v^. There are no fu r ther occurences of the common key 11 so REXTRACT pops up one l e v e l to f i l e 1. I t not ices that there was a 1 to n (n=3) match between f i l e 1 and f i l e 2 so that the data value 100 must be copied n-1 times i n the data&array f o r v^. There are no more occurences of the common key 11 so REXTRACT returns to EXTRACT'. EXTRACT then updates the k e y l i s t po in te r so that i t po ints to the key values 12, and i t c a l l s REXTRACT aga in . The desc r i p t i on of REXTRACT w i l l be shor ter th i s t ime. REXTRACT f inds the key value 12 i n f i l e 1 so the value 101 i s added to the data array fo r v ^ REXTRACT c a l l s i t s e l f to look fo r the common, key 12 with f i l e 2. The key value 124 i s found i n f i l e 2 so the data value 202 i s added to the data array f o r v^. Now a dup l i ca te key value 124 i s > found, so the value 202 i s added to the data array fo r v 2 > But REXTRACT i s only c a l l e d fo r the f i r s t key value 124. REXTRACT c a l l s i t s e l f looking fo r the common key,4 with f i l e 3. The key values 14 are found i n f i l e 3, hence the data value 301 i s added to the data array fo r v^. Since f i l e 3 has no ch i l d r en REXTRACT looks fo r another occurence of the common key 4 and f inds 24, hence the data value 302 i s added to the data array fo r v^. REXTRACT pops.up one l e v e l and f inds n t o n (n=2) match so i t does nothing s p e c i a l . Since no other occurence of the common key 12 i s found i n f i l e 2 REXTRACT pops, up one more l e v e l to f i l e 1 and f inds a 1 to n (n=2) match. REXTRACT then copies n-1 times the data value 101. 59. Since there are no fu r ther occurences of the key value 12..RKXTKACT returns to EXTRACT. EXTRACT updates the po inter i n the key l i s t to point to the key value 21. When REXTRACT i s \u00E2\u0080\u00A2 c a l l e d i t i f i n d s the key-value 21 i n f i l e 1 so i t adds the data value 102\u00E2\u0080\u00A2\u00E2\u0080\u00A2to the data array fo r v^. REXTRACT then c a l l s i t s e l f to look fo r the common key 21 with f i l e 2. But no match i s found, hence REXTRACT pops up to f i l e 1 and removes the data value 102 from the data array fo r v .. REXTRACT then returns to EXTRACT. I t should now be qui te c l ea r how to extract the data values f o r the key value 22 i n f i l e 1. \u00C2\u00A7 6 . prepar ing data fo r g raph ica l output The graphics superv isor expects i t s input to be i n a standard format which i s used, to handle the requests fo r a l l of the var ious types of graphs. A l l of the data has now been extracted in to n data ar rays . But th i s data must be massaged before the graphics superv isor i s c a l l e d . The n arrays of data must be copied into one array for so r t i ng purposes. An array i s dynamical ly created which i s la rge enough to ho ld a l l data po in t s . But now some of the data values must be re jec ted because they are not i n the range s p e c i f i e d i n the DISPLAY command. The 'FR0M' and 'T0' modi f ie rs must be checked when the data i s being cop ied . I f the modi f iers are present then they are s tored- in the d i sp lay DSECT. The program examines the corresponding values i n each of the data arrays to make c e r t a i n they are i n the cor rec t range. I f a l l of the data values are i n the cor rec t range then the set of data values i s added to the new s ing l e ar ray . I f any one of the data values i n the set i s out of range then the set i s re jec ted and the next set i s examined. 60\". Then theas.torage f o r a l l of the p r e v i o u s a r r a y s . i s r e l e a s e d . Then a r o u t i n e c a l l e d PREPL0T i s c a l l e d , and then the DISPLAY r o u t i n e r e t u r n s to the s u p e r v i s o r to accept a new command. The r o u t i n e PREPL0T e s s e n t i a l l y s o r t s the a r r a y i n t o the o r d e r demanded by the graphics s u p e r v i s o r , and f i l l s up the i n f o r m a t i o n DSECTS used b y - t h e g r a p h i c s s u p e r v i s o r . PREPL0T f i r s t s o r t s the a r r a y o f data v a l u e s . Suppose tha t the f o l l o w i n g s k e l e t o n of the DISPLAY. command e x i s t s : DISPLAY v.. BY v\u00E2\u0080\u009E BY v~ BY v . . Then the data v a l u e s 1 2 3 4 are s o r t e d i n v 4 ~ v 3 ~ v 2 o r ^ e r , i n o ther words the a r r a y i s f i r s t s o r t e d by v 2 > then by v ^ , then by v ^ . The s o r t i n g i s done by c a l l i n g a system s o r t r o u t i n e . Remember tha t the g r a p h i c s s u p e r v i s o r wants the data f o r each d i s p l a y v a r i a b l e c o n t a i n e d w i t h i n a s t r i n g DSECT. Hence now tha t the data a r r a y i s s o r t e d i t must be s p l i t up i n t o separate a r r a y s each of which c o n t a i n s o n l y p o i n t s f o r one d i s p l a y v a r i a b l e . v'The l o c a t i o n of these a r r a y s i s s t o r e d w i t h i n the d i s p l a y DSECT, and s torage f o r the o l d a r r a y i s f r e e d . Now the program must f i l l i n the p i c t u r e , -graph, and s t r i n g DSECTS which were e x p l a i n e d i n s e c t i o n B o f t h i s c h a p t e r . Most of the i n f o r m a t i o n d e s i r e d by the p i c t u r e , graph and s t r i n g DSECTS i s conta ined w i t h i n the d i s p l a y DSECT, the f i l e d e s c r i p t i o n t a b l e , the p o l i c y d e s c r i p t i o n t a b l e , the DISPLAY command, or e a s i l y c a l c u l a t e d . The o n l y t r i c k l y c a l c u l a t i o n i s the ' graph t i t l e . I t i s c r e a t e d by c o n c a t e n a t i n g the f i e l d names toge ther i n t e r s p a c e d w i t h the word ' b y ' ; f o r example the t i t l e ' p o p u l a t i o n by t i m e ' i s c r e a t e d from the f i e l d ' p o p u l a t i o n ' and ' t i m e ' . S ince these t a b l e s are easy to f i l l a d e t a i l e d d e s c r i p t i o n i s not g i v e n . \u00C2\u00A7 b. the CHANGE command The CHANGE command i s necessary i n order to a l t e r the po l i c y vec to r , and hence al low p o l i c y in te rven t ion by the user . The syntax of the CHANGE command i s : CHANGE pol icy-variable-name [T0] valueH[F0R] : i n t e r va l ] where pol icy-variable-name i s any va r i ab l e i n the p o l i c y vec to r , value i s the new value f o r the po l i c y v a r i a b l e , and the i n t e r v a l i s the range over which the p o l i c y change i s to take a f f e c t . The range must be over t ime, which i s a current l i m i t a t i o n of the system. The. i n t e r v a l i s expressed as: low-valueC!|T0\u00C2\u00A7' r(thigh-value] \u00E2\u0080\u00A2\u00E2\u0080\u00A2where high-value may be ommitted i n which case the de fau l t value i s the end year . The CHANGE command executes two major func t ions : i t i nva l ida tes por t ions of the key l i s t s fo r a l l f i l e s a f fec ted by the p o l i c y v a r i a b l e ; and i t changes the value ranges i n the p o l i c y vector t ab le . In order to change the entry i n the p o l i c y vector tab le the program must i nd i ca te there i s another value range, and i n se r t the new value range i n the appropr iate spot i n the value range t ab l e . I f the i n t e r v a l i s miss ing i n the command th i s impl ies the value range s t a r t s at the base year + 1 and ends at the end year . 1 I f the i n t e r v a l range f a l l s outs ide these de fau l t l i m i t s then i t i s ignored and the de fau l t l i m i t s used. The l i s t of f i l e s a f f ec ted by a p o l i c y va r i ab l e i s contained w i th in the po l i c y vector t ab le . The key l i s t f o r each of these f i l e s i s a l t e red so that the i nva l i da ted records?\" cannot be re ferenced. A l l the records from the base year + 1 or from the low range i i i the i n t e r v a l s p e c i f i e d i n the command, which ever i s grea tes t , to the end year are i n v a l i d a t e d . 62. \u00C2\u00A7 c. the other commands The other commands i n the superv isor d e f i n i t e l y play second f i d d l e to the DISPLAY and CHANGE command. These other commands provide the user with funct ions necessary to complete the system. The implementa-t i o n of these commands i s qu i te s t ra ight forward and i s therefore not d iscussed . The syntax of these other commands i s contained i i i the appendix. Also some of these commands are used i n the example ^contained\".., i n the appendix. 63. CHAPTER TV ' FUTURE EXTENSIONS * TO''THE^ SYSTEM The present system provides a very powerful too l to a id the develop-, ment of mu l t ip l e i n t e r a c t i ng s imula tors . But l i k e any other lar.ge computer system i t should never remain s t a t i c : there are many changes that could make the system even more powerful and u s e f u l . The ideas f o r some of these changes have been lu rk ing i n the background ever s ince the design of the system; the res t of them evolved through the experience of running the HPS models. Here are a few of the major extensions that would be u s e f u l . \u00C2\u00A7 A. i n t rbduc t ing a complex data base The l a rges t major change to the system would be the in t roduc t ion of a complex data base. This change was kept i n mind during the design of the system. What form w i l l the complex data base take? The f i e l d s i n the data base w i l l be r e l a t ed i n a tree s t ruc ture f a sh ion . The data base w i l l s t i l l be d i v ided in to f i l e s ; but now the r e l a t i onsh ip between the f i e l d s w i th in each f i l e would be r e f l e c t e d by a tree s t ruc tu re . At present they are r e l a ted s equen t i a l l y . For example, the s t ruc ture of the data base may look as fo l l ows : universe f 1 where f i s the k ' th f i e l d at l e v e l j i n f i l e i r 41 J k f i gu re 18: example of complex data s t ruc ture 64. What advantages are there i n adapting th i s more complex data st ructure? Often one would l i k e to i nd i ca te that c e r t a i n f i e l d s are r e l a ted to each other . For th i s purpose a tree s t ruc ture i s general enough (a graph i s more general but i t i s not necessary, and i t i s hard to implement). Within the 'da ta s t ructures used at present there i s no way to i nd i ca te that f i e l d s are r e l a t ed because each record i s sequent ia l i n nature . This complex data s t ruc ture i s not intended to be of use to the s imulators - they, do not need to know the s t ruc ture of the data because they read and wr i te sequent ia l records . But the complex' data base w i l l al low the user to ask a great v a r i e t y of quest ions. He w i l l have an informat ion r e t r i e v a l system at h i s f i n g e r t i p s to . examine the output of the s imula tors . \u00C2\u00A7 a. consequences fo r the present system Natura l l y the i n t roduc t i on of a complex data s t ruc ture w i l l force changes1 throughout var ious parts of the system. These changes w i l l be f e l t most by the data management i n t e r f ace (hereafter re fered to as I/O i n t e r f a c e ) . The changes to other sect ions of ,the system w i l l be minimal due to the modular izat ion of the code during the des ign . \u00C2\u00A7 a . l the changes to the major sect ions of the system and the i r ; in te r faces with the superv isor The changes to. each sec t ion of the system and the changes to each of the in te r faces with the superv isor w i l l be examined. The present user commands w i l l not be a l t e red at a l l ; nor w i l l i t s i n t e r f a ce with the superv i so r . The only change w i l l be the add i t i on of new informat ion r e t r i e v a l commands to u t i l i z e the add i t i ona l knowledge that f i e l d s a r e . r e l a t e d . The superv isor has been designed so that the add i t i on 65. of new commands i s t r i v i a l . These new commands w i l l invo lve implement-ing tree tour ing algorithms to extract wanted in format ion . Hence there w i l l be a great r e l i ance on the new I/O i n t e r f a c e . The s imulators need not change at a l l . This impl ies that the I/O in te r f ace w i l l accept a g rea t ,dea l of r e s p o n s i b i l i t y . ' The s imulator w i l l expect, as i t does now, i t s I/O to be sequent ia l i n nature . Hence i f the s imulators do not have to bother ad jus t ing to the new complex \u00C2\u00A3 data s t ruc ture then the I/O in te r f ace must transform the complex data record in to a sequent ia l record during a s imulator read and transform a sequent ia l record into a complex data record during a s imulator w r i t e . There are many ways to implement such a t ransformat ion. This i s no t r i v i a l task, but at l eas t a l l of the add i t i ona l work w i l l be i s o l a t e d i n one sec t i on of code. I f the I/O in te r f ace were not a separate module then most of the system would have to change. The graphics superv isor need not change, and ne i ther should the graphics i n t e r f a c e . I f the r esu l t s of the informat ion r e t r i e v a l commands a re . to be graphed then they should be massaged to f i t the current graphics package - i t i s general enough. Probably most of the output from the new commands w i l l be i n tabular form. Obviously the data base and the I/O in te r f ace w i l l be completely changed. The changes to the data base w i l l be twofold: the l o g i c a l des c r i p t i on w i l l change and the data value s t ruc ture w i l l change. The l o g i c a l des c r i p t i on i s contained i n the f i l e desc r ip t i on t ab le . Hence i t must be changed so that each element i n the table w i l l have a po in te r to i t s s i s t e r f i e l d , i t s f i r s t c h i l d , and a back po in te r to i t s parent 66. ( i t i s assumed that the binary tree representat ion fo r a gene ra l : t r e e w i l l be used fo r storage e f f i c i e n c y reasons) . The value t ree w i l l a l so have to incorporate po inters w i th in i t s s t ruc tu re . In the most general case i t w i l l have to al low fo r vary ing number of r epe t i t i ons at any l e v e l w i th in the value tree s t r u c tu r e . But the f ac t that the s imulators produce the ent r ies i n the data base makes some aspects of data management easy: a l l the records are of f i xed length and no dynamic de l e t i on or i n s e r t i o n of f i e l d s or records w i l l be allowed because the s imulator output cannot ,a l t e r during run t ime. The s implest method of approach i s to s t i pu l a t e that the s imulators produce data fo r a sequent ia l record that contains a l l f i e l d s ' i n the t r ee . This change can be'made with the minimum of e f f o r t . A more general change would be to al low the s imulator produce data fo r a l l of the ch i l d r en of a f i e l d ( in other words a subtree w i th in the data base)\ But th i s impl ies changes to the s imulators so that they w i l l accept any key as data generat ion parameter. The simple change mentioned above assumes that the s imulators are s t i l l c a l l e d by time, hence time i s the universe element i n f igure 18. The I/O rout ine i s respons ib le fo r reading and wr i t i ng from the data base. When reading from the data base the I/O must be able to transform the value tree in to a sequent ia l r e co rd . The s imulators w i l l want to read the whole t r ee ; but the superv isor may jus t want to read a subtree so the I/O rout ine should be soph i s t i ca ted enough to handle th is case. When w r i t i ng in to the data base from^a\u00C2\u00BB ! simulator the I/O rout ine must p lace the f i e l d s i n the sequent ia l record in to the proper places i n the value t r ee . Hence the I/O in te r f ace w i l l bear the brunt of changing the data s t ruc tu re . 67. \u00C2\u00A7 a.2 the changes to the DISPLAY command D iscuss ion of the DISPLAY command occupied much of th i s tj iesis therefore the e f f e c t s on i t of changing the data base w i l l be examined. F i r s t i t should be noted that the only changes to the superv isor h ie rarchy invo lve adding more commands, and modifying the rout ine to load the f i l e desc r i p t i on t ab le . The f i r s t i s t r i v i a l , and the second i s qui te easy to change. The other command subroutines (CHANGE, LIST, SAVE.arid REST0RE) that r e f e r to the data base need not be a l t e r ed because they only r e f e r to the data base through the I/O i n t e r f a c e . Within the DISPLAY command the pars ing of the command s t r i n g w i l l not change #1 The b u i l d i n g of a t ree of va r i ab l e r e l a t i ons between the d i sp lay va r i ab les w i l l be s l i g h t l y d i f f e r e n t . The DISPLAY command w i l l s t i l l a l low c r o s s - f i l e re ferences , but the check fo r consistency w i l l be d i f f e r e n t . The program w i l l s t i l l look fo r a common f i e l d i n both f i l e s , but th i s common f i e l d must be the parent of the d i sp lay v a r i a b l e . For genera l i t y the maximal number of previous common parent r e l a t i ons w i l l be sought. This impl ies that the code which searches through the f i l e desc r i p t i on table must be changed, but otherwise the a lgor i thm remains the same. The a lgor i thm to generate data does not have to change at a l l . This i s because the data i s generated by c a l l i n g the s imula tor , so there i s no d i r e c t reference to the data base. The ex t r ac t i on process w i l l have to change a l i t t l e with the in t roduc t ion of a complex data base. I t w i l l be assumed that, the chain of parents from the root of the tree down to the parent of the wanted f i e l d are a l l keys. In th i s way a sor t of sequent ia l 68. record can be formed from the cahih of parents and the wanted f i e l d . Once again there are no major changes s ince the ex t rac t i on rout ine re fe rs to the data base through the key l i s t s and the I/O i n t e r f a ce . For example,' supposei'the fo l lowing skeleton of the DISPLAY command were g iven : DISPLAY v.^ BY BY v^. Suppose that the fo l low ing l o g i c tree e x i s t s : universe = time K 1 | L JT f i le . l f .K .-Vfile 2 f i l e 3 where: K,. are keys J are d i sp lay va r i ab les f i gu re 19: example of l o g i c a l tree This i s equiva lent to the fo l lowing sequent ia l f i l e s t ruc tu re : f i l e 1 time k^^ k ^ f i l e 2 time k 21 f i l e 3 time f igure 20: equivalent sequent ia l f i l e Now i n order that the DISPLAY command be cons is tent the fo l low ing must be t rue : ^21 = ^12* there w i l l be a l i n k between f i l e 1 and f i l e 2, and f i l e 2 and f i l e 3. Hence the add i t i ona l d i f f i c u l t i e s created i n the ex t rac t i on process by the in t roduc t ion of a complex data base are absorb-ed by the 1/0 \" in te r face and the b u i l d i n g of the tree of va r i ab l e r e l a t i o n s , The so r t i ng of the extracted data, and the prepar ing of data fo r graph ica l output w i l l not change. 69. S B. removing the r e s t r i c t i o n that s imulators run by time only At present the s imulators must be passed the key value fo r time i n order that they know for which year to produce data. But the concept of c a l l i n g a s imulator by time should be genera l ized so that i t i s hot dependent on t ime. One form of gene ra l i za t i on would invo lve c a l l i n g a s imulator with a va r i e t y of keys. But th i s involves major changes to the s imu la to rs , i n fac t i t may invo lve adding more s imula t ion code i f the s imulator does not' produce data over that key. For example, i f the populat ion\"model were asked to produce data fo r reg ion instead o f f f o r time and no data cur rent l y ex i s t s fo r region then the s imulator must be modif ied so that i t produces these r e s u l t s . Whichever keys were chosen as candidates fo r the s imulator parameter they would have to be common to a l l the s imulators cu r ren t l y under the con t ro l of the superv isor because a l l data generated fo r a DISPLAY command must be with respect to the same key fo r cons is tency . I f s imulators could be c a l l ed with a va r i e t y of parameters, then the one chosen by the superv isor wouldibe any one that appeared i n the DISPLAY command, or e l se one that was chosen by de fau l t . I f one of the keys were i n the DISPLAY command then the DISPLAY rout ine could generate the data points more e f f i c i e n t l y . The syntax of the DISPLAY command could be changed so that the user could spec i f y which key w i l l be used as the s imulator parameter. This i s of some importance to him because even though the key may not appear i n the DISPLAY command a l l of the data w i l l be i n d i r e c t l y generated using values of that key. But the overhead i n changing the system i s qui te h igh , and probably not worth implementing. A simple method of gene ra l i za t i on would be 70. to only al low one key with which to c a l l the s imu la to rs , but read i n th i s key ( in the present case ' t ime ' ) as part of the i n i t i a l i z a t i o n t ab les . Since every set of s imulators must have at l eas t one such key, but not necessa r i l y time, the system would then no longer be dependent on the HPS models. \u00C2\u00A7 C. in t roduc ing an ar i thmet ic expression i n the DISPLAY command There w i l l be many times when a user i s not i n te res ted i n the data values of the va r i ab les which he i s allowed, to d i sp l a y . He would ra ther examine some ar i thmet ic combination of the v a r i ab l e s . This i s not poss ib l e at the present time.- It i s des i rab le that each d i sp lay va r i ab l e be allowed to conta in an ar i thmet ic express ion . For example: DISPLAY (iv\u00C2\u00B1 + v 2 + 3)/v4> BY v 5 BY v g * v ? . This w i l l imply changes i n the DISPLAY rou t i ne , but not very many. The rout ine that parses the DISPLAY command must be changed s i g n i f i c a n t l y so that i t can recognize any ar i thmet ic express ion. I t would probably be a c lever idea to s tore the d e f i n i t i o n of the ar i thmet ic expressions as a tree s t ruc ture fo r l a t e r re fe rence . The general idea w i l l be to consider the DISPLAY, command to cons is t of a l l simple v^'s (d isp lay va r i ab les ) with i = l , . . . , n where n i s the t o t a l number of d i sp lay v a r i -ables mentioned i n the command \" ( inc luding a l l d i sp lay va r i ab les i n the ar i thmet ic express ions ) . Hence the program is made to have n elements i n the d i sp lay DSECT (prev iously n had been assumed to be a maximum of fou r , but th i s l i m i t was never used e x p l i c i t l y ) . The DISPLAY rout ine then proceeds through the b u i l d i n g of a va r i ab l e tree of r e l a t i o n s , the generat ing of data , and the ex t rac t ing 71. of data without any changes necessary. Immediately a f t e r the data ex t rac t i on a sec t ion of code must be inser ted to ca l cu l a t e the value of the ar i thmet ic express ion f o r each occurence of the data set i n the ex t rac t i on process . This w i l l requi re the use of the s t ruc ture fo r the ar i thmet ic express ion s tored prev ious ly during the pars ing of the command. Hence there w i l l now once again be a maximum of four data values i n each extracted set of values that have to be examined by the graphics superv i sor . The preparat ion fo r g raph ica l output may proceed exact l y as i t d id be fore . Once again an extension can be made without d i s tu rb ing the present system very much. \u00C2\u00A7 D. i n t e r rup t i ng the DISPLAY command At present when a DISPLAY command i s issued a l l of the points 'irirthe graph are ca l cu la ted and then the graph i s d i sp layed . But i t could happen that when a user examines the graph as i t i s being out-putted -he w i l l want to in te r rup t the process fo r a va r i e t y of reasons. I t may be that he has typed i n the wrong v a r i a b l e , or he decides that he does not want to see the graph fo r the whole i n t e r v a l o r i g i n a l l y s p e c i f i e d . I t may a lso occur that the user becomes aware that the DISPLAY command he has issued takes a l o t of CPU time, and he does not want to incure the expense. Th i s w i l l be true e spec i a l l y i f a p o l i c y va r i ab l e i s i n the DISPLAY command. But at present there i s no way of i n t e r rup t ing the process and p r i n t i n g out the graph to date. A f a c i l i t y i s needed so that a user may examine the graph as i t i s being c a l cu l a t ed . But th i s impl ies looping through the l a s t s eq -uence of rout ines w i th in the DISPLAY subrout ine . The data generat ion 72. of a l l va r i ab les fo r one time frame would have to be fol lowed by the data ex t r ac t i on of a l l va lues , fol lowed by the graphics preparat ion of the data , and then fol lowed by the graph ica l output. This impl ies a great deal of overhead i n the execut ion of the DISPLAY -.(routine, hence th i s opt ion i f a va i l ab l e should not be used very o f t en . The process should probably be executed under another command name, with the opt ion of l e t t i n g the user ind i ca te how many cyc les the program i s to execute; fo r example at the end of each cyc le the user could type i n ' C0NTINUE'.;' 73. REFERENCES [I] Armenti , A . , Ga l l ey , S. , Goldberg, R., Nolan, J . , S h o l l , A. \"LISTAR-Lincoln Information Storage and Assoc ia t i ve Re t r i e va l <- System\", AFIPS, Vo l 36, 1970 (Spring Jo int Computer Conference) [2] Ash, D., Rashid, Z. \"Command Language for H P S \" , unpublished document, Department of Computer Sc ience, Un i ve rs i t y of B r i t i s h Columbia, 1971 C31 Boettner, D.W. \"Command . (Job Control ) languages fo r general purpose computing systems\", unpublished paper, Un i ve r s i t y of Michigan Computing Centre, 1969 [4]. Day, R i H . , Mans f i e ld , M.K., E l l i s , M.E. \"C0DAS: A Data D isp lay System\", CACM, Volume.12, Number 2 (Feb. 1969) [5] Goldberg, M.A., Wendt, P .F . , Walter , G.R; \" Jobs, People and Land -Bay Area S imulat ion Study (BASS)\", Un i ve rs i t y of C a l i f o r n i a P r i n t i n g Department, 1968 [6] H o l l i n g , C . S . , Goldberg, M.A., K e l l y , R. \"Vancouver reg iona l s imula t ion study 1970^1971\", unpublished paper, Resource Science Centre, Un ive rs i t y of B r i t i s h Columbia, 1971 [7] Ingram, G.K. , Ka in , J . F . , Ginn, J .R . \"The De t ro i t Prototype of the NBER Urban S imulat ion Mode l \" , pre l iminary r epor t , Nat iona l Bureau of Economic Research (NBER), Madison, New York, 1972 [83 K idd , S.W. \" Incorporat ing Complex data s t ructures in to a language fo r s o c i a l sc ience r esea rch \" , AFIPS, V o l . 35, 1969 ( F a l l Jo in t Computer Conference) [9] Levy, E. \"Simulated Progress? The Vancouver Regional S imulat ion P ro j e c t \" , unpublished paper, Department of Phi losophy, Universi ty, of B r i t i s h Columbia, 1971 [101 L ipner , S.B. \"Requirements f o r . t he development of computer-based urban in fo rmat ion \" , AFIPS, Vo l 34, 1969 (Spring Jo in t Computer Conference) [ I I ] Myers, J . E . , Choo l j i an , S.K. \"An approach to the development of an a'dvanced informat ion management system 1 ' , AFIPS, V o l . 36, 1970 (Spring Jo in t Computer Conference) [12] Nay lor , T . H . , B a l i n t f y , J . L . , Burdick, D.S. , Chu, K. \"Computer S imulat ion Techniques' ' , John Wiley & Sons, Inc . , 1966 [13] Parker , J . L . \"A graphics and informat ion r e t r i e v a l superv isor fo r s imu la to r s \" , AFIPS, V o l . 40, 1972 (Spring Jo in t Computer Conference) 74. APPENDIX \u00C2\u00A7 A . syntax of the command language [2] The f o l l o w i n g d e s c r i p t i o n g i v e s a b r i e f o u t l i n e o f the command s y n t a x . The t e x t i n upper case represents key words which must appear w i t h o u t change unless an a b r e v i a t i o n i s a l l o w e d . The t e x t i n lower case w i t h i n quotes i s to be r e p l a c e d by the a p p r o p r i a t e symbol by the u s e r . The t e x t w i t h i n b r a c k e t s i s o p t i o n a l ; hence i f the user does not s p e c i f y i t , the enc losed parameters are ass igned d e f a u l t v a l u e s by the sys tem. \u00C2\u00A7 A . l C0PY C0PY FR0M ' f i l e n a m e ' T0 ' f i l e n a m e ' This command copies one f i l e to another , l i k e the MTS copy command. \u00C2\u00A7 A . 2 EMPTY EMPTY ' f i l e n a m e ' This command empties the contents of a f i l e , l i k e the MTS empty command. \u00C2\u00A7 A . 3 CHANGE CHANGE ' p o l i c y v a r i a b l e ' I T01 ' v a l u e '.C [ F0R]/ . ' i n t e r v a l ' ] T h i s command a l l o w s the user to change the v a l u e of a p o l i c y v a r i a b l e . The syntax of ' i n t e r v a l ' i s : va lue^C[T0] v a l u e ^ f f B Y ] value^Jv where v a l u e / '. may be r e a l or i n t e g e r . \u00C2\u00A7 A . 4 DEFINE DEFINE 'name' AS ' s t r i n g ' ' This command a l l o w s the user to r e f e r to ' s t r i n g ' through the use of the a b b r e v i a t i o n 'name' i n a command. The 'name' and i t s replacement ' s t r i n g ' are p l a c e d i n a d e f i n i t i o n t a b l e . 75. \u00C2\u00A7 A.5 DR0P DR0P, 'name' This command removes a prev ious ly def ined 'name' from the d e f i n i t i o n t ab l e . \u00C2\u00A7 A.6 ESTABLISH ESTABLISH AREAS ' 'n^ 'OTT'0] ; , n 2 ' ] ON 'dev ice name' This command d iv ides up the 'dev ice name' in to n 2 - + 1 areas and numbers them n^ through n 2 f o r l a t e r re fe rence . A-;.'device name' may only .be d iv ided in to 1, 2, or 4 areas. \u00C2\u00A7 A.7 DISPLAY DISPLAY [AS 'name'![SEQUENCED BY] ' v ^ [SEQUENCED] BY ,'v ' [SEQUENCED] BY ' v ' [SEQUENCED] BY- 'v^ TYPE = 't, 1 * [NEW|.SUPERIMP0SE] E0N AREAt'n'][WITH N0 AXES]. T h i s command allows the user to d i sp lay graphs that are of i n t e r es t to him. The AS 'name' s p e c i f i c a t i o n allows the use of abbrev ia t ion (without us ing the DEFINE command) and the a b i l i t y to name a graph.\u00E2\u0080\u00A2 Each of the v^'s may have range mod i f i e r s , f o r example v_j[FR0M]value^ [T0] v a l u e 2 [BY/ value.j'l;and may have a rate s p e c i f i e d , fo r example v^ [AT] RATE v a l u e 1 . Only one d i sp lay va r i ab l e may have SEQUENCED or AT RATE assoc ia ted with i t . The d i sp lay va r i ab l e v^ may be replaced by a p o l i c y va r i ab l e i n which case a bar graph of the p o l i c y values i s d i sp layed , or by the key word P0LICY VECT0R i n which case bar graphs are d isp layed fo r every p o l i c y v a r i a b l e . The 1: ' c an be one of the fo l l ow ing : BAR,D0T,LINE,C0NT0UR, or MAP \u00C2\u00A7 A.8 H0LD HOLD [AS 'name'][SEQUENCED BY] ^ ' [SEQUENCED] BY \u00C2\u00BBv ' [SEQUENCED] BY ' v ^ [SEQUENCED]BY 'v^ ' TYPE = [NEW| SUPERIMP0SE][0N AREA *n'][WITH N0 AXES] 76. This command allows the user:to produce an image but not to display i t immediately. I t allows a user to create separate images, and then concatenate them together for only one output graph (using the SH0W command). This i s convenient for a l i n e printer since i t cannot be rewound. The H0LD command has the same syntax as the DISPLAY command. \u00C2\u00A7 A.9 SH0W SH0W (AREAS' n^ T0 | 'device name') This command allows the user to output on one graph the specified areas where graphs are being held (by using H0LD command). I f 'device name' i s specified then a l l of the areas associated with the device are outputted. \u00C2\u00A7 A.10 ERASE ERASE (AREA 'n' | 'device name') This command allows the; user to erase the area 'n', or a l l of the areas on 'device name'. \u00C2\u00A7 A.11 LIST LIST (FIELD-NAMES | FILE_ NAMES)[F0R 'class'] or LIST (CLASS^NAMES | USERJSfAMES) or LIST P0LICY_VARIABLES [F0Rc.- 'year^][F0R\"class'] . or LIST.DATA_VALUES [FOR 'data variable'][F0R 'interval'] IN ' f i l e ' This command allows the user to examinevcthe^contents ^6f;some system tables. \u00C2\u00A7 A.12 G0 F0RWARD, and G0 BACK G0/F0RWARD ' or 'n'tGRAPHS]0N AREA 'm' [SH0W 0N AREA 'k'][AT RATE 's'] G0 BACK 77. The G0 BACK command al lows the.user to d i sp lay a prev ious ly c a l c u -l a t ed graph that has been overwr i t ten by another graph. The G0 F0RWARD command allows the user to step forward through o ld graphs once the 60 BACK command i s i s sued . The show opt ion allows the user to copy the o ld graph to a new area. \u00C2\u00A7 A.13 EXPLAIN EXPLAIN (SYSTEM | 'command' | ' e r r o r message number' | 'name') This command allows the user to. ask fo r a short exp la ina t ion of var ious parts of the system. Name i s any entry i n the d e f i n i t i o n table or the p o l i c y vec tor . \u00C2\u00A7 A.14 HELP This command i s intended to help a d i so r i en ted user . \u00C2\u00A7 A.15 MTS MTS This command returns the user to MTS mode, during which a $RESTART returns him to the:system. ;\u00E2\u0080\u00A2 \u00C2\u00A7 A.16 SAVE SAVE (USER_NAMES | SYSTEM | P0LICY_VECTpR | DATA | ' c l a s s name' f ' f i l e name'.). IN ' m y f i l e ' This command allows the user to save the s p e c i f i e d sect ions of the current run i n the predef ined MTS f i l e 'myf i l e ' . . \u00C2\u00A7 A.17-- REST0RE MIN_AGE_S.ECOND 14.000000 \u00C2\u00A9MIM_AGE_:THIRD 15.000000 80. MIH_AGE_FOUBTH SMIN_AGE_FIFTH SMIN_AGE_SIXTH M.OW_AGE_SIXTH 3>HIGH_AGESIXTH jdM AX_CHILDR EN SBBALE_SURVIVORSHIP_PV a>FEMALE_SURVIVORSHIP_PV \u00C2\u00BB H A T I O _ H A L E S : F E H A L E S _ A T _ B I B T H IVING_BISTH_RATEAT_BIRTH 3>MALE_MIGR ATION_I8CREMENT_PV \u00C2\u00A7 F E M A L E _ M I G R A T I O N _ I B C R E MENT_PV ^MALE_MIGRATION_WAVE_PVMENT_PV ^FEMALE_MISRATION_WAVE_PVNT_PV |BMALE_HIGRATIOH_PVWAVE_PVMT_PV 3FEMALE MIGRATION PVVE PVNT PV 16.000000 17.000000 18.000000 1.000000 100.000000 6.000000 0.0 0.0 0.500000 0.990000 0.0 0.0 0.0 0.0 0.0 0.0 (EXPLAIN CHANGE ) CHANGE 'POLICY VARIABLE' TO 'VALUE * FROM HI TO F2 \" PROVIDES A METHOD OF CHANGING A POLICY VALUE WITH COMPARATIVE EASE. THIS CHANGE WILL NOT PRODUCE ANY DISPLAYS. THAT CAN ONLY BE DONE WITH A LIST , SHOW OR DISPLAY COMMAND. POLICY VARIABLE IS ONE OF THE ENTRIES IN THE POLICY VECTOR. EXAMPLE: CHANGE POPULATION_GROWTH TO 4 THE POPULATION GROWTH IS CHANGED TO 4 1 FROM CURRENT YEAR TO END YEAS. EX. CHANGE MOSGAGE RATE TO 8 BETWEEN 1950 AND 1953 $ BETWEEN THE YEARS 1950 AND 1953 THE MORGAGE RATE IS CHANGED TO 8 % . 3COM : THE VALUE OF ONE OF THE POLICY VARIABLES IS CHANGED ^CHANGE MIN_AGE FIRST TO 25 FROM 1967 TO 1969 DON E COM : THE POLICY VARIABLES ARE LISTED AGAIN TO DEMONSTATE THE CHAN3E LIS T POLICY VARIABLES FOR POPULATION FOR 1958 MIN_AGE_FIRST MIN~AGE_SECOND MIN_AGI_THIR D DMIN_AGE_FOUBTH DM IN_ AGE_FI FTH iiDM IN_AGE_S I XT H \u00C2\u00A7 L O W _ A G E _ S I X T H 2>HIGH_AGE5I XTH 3>M AX_CHILDR EN SMALE SURVIVORSHIP_PV SFEMALE_SUSVIVORSHIP_PV \u00C2\u00AE R A T I O _ M A L E S : F E M A L E S _ A T _ B I R T H \u00C2\u00AE S U R V I V I N G _ B I R T H _ R A T E A T _ B I R T H aSMALE_MIGR ATI ON_INC SEME NT_PV jDFEM ALE_ MIGRATION _ IN CRE ME NT_PV JMALE_MIGRATION_WAVE_PVMENT_PV 55FEM ALE_MIGR ATION_W A VE_P VNT_PV 8>MALE MIGRATION_PVWAVE_PVNT_PV SFEMALE MIGRATION PVVE PVNT PV 2 5. 14. 15. 16. 17. 18. 1 . 100. 6. 0. 0 . 0. 0. 0. 0. 0. 0. 0. 0. 000000 000000 000000 000000 000000 000000 000000 000000 000000 0 0 500000 990000 0 0 0 0 0 0 a 3COM : THE FOLLOWING COMMAND INDICATES THE COST TO DATE FOR THE RUN \u00C2\u00A9COST \u00C2\u00A9WAIT MEMORY=30.39 PASE-HOUR, COST=$12.76 \u00C2\u00A9ACTIVE MEMORY=29U.56 P AGE-MIN , COST=$6.87 JSELAPSED TIME =19 MIN 15 SEC, COST=$1.34 \u00C2\u00A9CPU TIME USED=171.76 SEC, COST=$16.69 \u00C2\u00A9TOTAL COST SINCE SIGNON=$37.68 \u00C2\u00A9 1.4 \u00C2\u00A9COM : THE CALCOMP IS AGAIN ASSIGNED AS AREA 1 ONLY \u00C2\u00A9EST AREA 1 ON CALCOMP \u00C2\u00A9COM : THE RESULT OF THE FOLLOWING DISPLAY IS SHOWN IN GRAPH 8 \u00C2\u00A9COM : THE LOCAL GOVERNMENT MODEL , WHICH IS RUN TO PRODUCE THE FOLLOWING \u00C2\u00A9COM : DISPLAY , CALLS THE POPULATION MODEL FOR SOME OF ITS INPUT &DIS TRANS_TO_FED_GOVT BY TIME FROM 1966 TO 1976 BY DATA_ITEH FROM 25 TO 25 >^COM : THE FOLLOWING COMMAND ALLOWS THE USER TO RETURN TO MTS MODE \u00C2\u00A9MTS SCOM : A PERMANENT FILE IS CREATED fCREATE SAVE f FILE \"SAVE\" HAS BEEN CREATED. j&COM : ONE OF THE DATA FILES (WITH ITS KEILIST) IS SAVED JfCOPY -POP_INFO (-99999) TO SAVE #COM : THE FOLLOWING ALLOWS THE USER TO RETURN TO THE SYSTEM #RESTART \u00C2\u00A9COM : THE USER TERMINATES THE EXECUTION OF THE SYSTEM \u00C2\u00A9STOP ^PLOTTING WILL TAKE APPROX. 36 MIN 3 SEC \u00C2\u00A9SUCCESSFUL PLOT. ^PLOT IN SYSTEM, PLOT TIME 36 MINUTES 3 SECONDS ^ STOP 0 tEXECDTION TERMINATED t graph 1 graph 2 i 0.0 50.0 I POPULATIONJ-1RLES (X101 ) 100.0 150.D 200.D 25D.D 300.0 350.0 400.0 _i L J i i , - i : i 84. 450.0 _J 500.0 ZD CI m CD -< TJ a ID UJ m graph 3 85. 86. PQPULRTION_MRL.ES CX101 ) O.D 50.0 100.D 150.0 200.0 250.0 30D.0 35D.0 430.D 450.0 500.0 \u00C2\u00B0.J I I I I L I I I I I I D C D m CD -< a d _ D CD -< m graph 5 graph 6 88. "@en . "Thesis/Dissertation"@en . "10.14288/1.0051196"@en . "eng"@en . "Computer Science"@en . "Vancouver : University of British Columbia Library"@en . "University of British Columbia"@en . "For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."@en . "Graduate"@en . "A supervisor to monitor multiple simulators"@en . "Text"@en . "http://hdl.handle.net/2429/33489"@en .