UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A program development facility DuMont, Mark Aurele Louis 1974

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1974_A6_7 D84.pdf [ 7.78MB ]
Metadata
JSON: 831-1.0051760.json
JSON-LD: 831-1.0051760-ld.json
RDF/XML (Pretty): 831-1.0051760-rdf.xml
RDF/JSON: 831-1.0051760-rdf.json
Turtle: 831-1.0051760-turtle.txt
N-Triples: 831-1.0051760-rdf-ntriples.txt
Original Record: 831-1.0051760-source.json
Full Text
831-1.0051760-fulltext.txt
Citation
831-1.0051760.ris

Full Text

A PROGRAM DEVELOPMENT FACILITY by MARK AU RELE LOUIS DuMONT B . S c , U n i v e r s i t y cf B r i t i s h Columbia, 1973 A THESIS SUBMITTED IN PARTIAL FULFILMENT CF THE REQUIREMENTS FOR THE DEGREE OF MASTER CF SCISNCF i n the Department of Computer Sciance We accept t h i s t h e s i s as conforming to the r e q u i r e d standard The U n i v e r s i t y of B r i t i s h Columbia September, 1974 In p resent ing t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that 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 re ference and study. I f u r t h e r agree t h a t permiss ion fo r e x t e n s i v e copying 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 granted by the Head of 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 understood that copying 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 ga in s h a l l not be a l lowed without my w r i t t e n p e r m i s s i o n . Department of Ci/n in!/ { e.\r Sc. i CInc. £• The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada D a t e S&^^etmhe.^ *>o. ICJ-JH-A P r o g r a m L e v e l o p m e n t F a c i l i t y i A b s t r a c t The i m p l e m e n t a t i o n c f a u n i f i e d f a c i l i t y f o r program development and maintenance i s d e s c r i b e d . The p r o t o t y p e (named "Eighty-One") p r o v i d e s f c r the e n t r y , e d i t i n g and c o m p i l a t i o n of program t e x t w i t h i n a u n i f i e d system i n which s o u r c e t e x t i s i m m e d i a t e l y t r a n s f o r m e d i n t o an i n t e r m e d i a t e t r e e s t r u c t u r e d r e p r e s e n t a t i o n f o r s t o r a g e . The i m p l i c a t i o n s of the u n i f i c a t i o n of t hese f a c i l i t i e s under t h i s r e p r e s e n t a t i o n a r e d i s c u s s e d from t h e v i e w p o i n t s of user c o n v e n i e n c e and system e f f i c i e n c y . T e c h n i c a l problems posed by the i m p l e m e n t a t i o n are a l s o d i s c u s s e d . F i n a l l y , some comments are made upon the nature of t h e user i n t e r f a c e t o systems of t h i s t y p e . A Program Development F a c i l i t y i i Table of Contents PAST 1 — I n t r o d u c t i o n ..1 1.1. Why a Program Development F a c i l i t y ? 2 1.2. P r o j e c t Goals 6 1.3. Some Personal P r e j u d i c e s . ..9 1.4. Advantages . ..12 1.5. Previous Work . .....13 1.5.1. INTEELISP 1** 1.5.2. The SUE System language 15 1.5.3. Emily 16 1.5.4. VERS 16 PART 2 — User's Guide 18 . 2.1. The Language ..18 2.1.1. Tokens of the Language ....19 2.1.2. Compilation U n i t s 21 2.1.3. D e c l a r a t i o n s 22 2.1.4. Expressions 23 2.1.5. P r i m a r i e s 25 2.1.6. B u i l t - i n Functions and Pseudo-Variables 28 2.2. The Numbering Scheme 29 2.3. System E x t e r n a l s 31 2.3.1. The Di s p l a y 31 2.3.2. E r r o r Handling 32 2.3.3. E n t e r i n g Text 33 2.4. The Command Language .34 2.4.1; The Down Command 35 A Program Development F a c i l i t y i i i 2.4.2. The Up Command 35 2.4.3. The PRINT Command ...36 2.4.4. The EDIT Command 36 2.4.5. The HARDCOPY Command 36 2.4.6. The INSERT Command 37 2.4.7. The REPLACE Command 38 2.4.8. The SAVE Command 39 2.4.9. The GET Command ...39 2.4.10. The COMPILE Command 40 2.4.11. The MTS Command 41 2.4.12. The QUIT Command 41 2.5. The L o a d e r - I n t e r p r e t e r 42 PART 3 -- System D e s c r i p t i o n 43 3.1. Data S t r u c t u r e s 44 3.1.1. The Program Tree ..........45 3.1.2. Program Tree A l l o c a t i o n 47 3.1.3. S t r i n g D e s c r i p t o r Management .49 3.1.4. D i s p l a y Screen S t r u c t u r e s .50 3.1.5. Compiler S t r u c t u r e s • 51 3.1.6. Checkpoint F i l e S t r u c t u r e 54 3.1.7. Recompilation Table S t r u c t u r e ....55 3.1.8. Object F i l e S t r u c t u r e 56 3.1.9. The S t r u c t u r e of the I n t e r p r e t e r 56 3.1.9.1. Data Addressing S t r u c t u r e 57 3.1.9.2. Array D e s c r i p t o r S t r u c t u r e ..58 3.1.9.3. Program Addressing Scheme 58 3.1.9.4. Some A d d i t i o n a l Stacks 60 3.2. Algorithms 62 A Program Development F a c i l i t y i v 3.2.1. The Scanner 62 3.2.2. The Paragrapher 64 3.2.3. CHECKPOINT/RESTORE Command Implementation 66 3.2.4. REPLACE Command Implementation .......67 3.2.5. The Parser 71 3.2.6. The Compiler .....75 3.2.7. The Command Scanner ....77 3.2.8. The Interpreter 79 PART 4 -- Conclusions ......80 4.1. System Externals 81 4.2. System Internals 85 4.3. Language Design Considerations 93 4.4. A User's Comments on SUE 94 4.5. Suggestions for Future Work ........97 APPENDIX 1 — A Sample Session 104 APPENDIX 2 — Interpreter Instruction Set 150 APPENDIX 3 -- SUE Program List i n g s 157 A Program Development F a c i l i t y Table of Fig__ures FIGURE 1 — A Program Tree Segment .... FIGURE 2 — The Symbol Stack FIGURE 3 -- G l o b a l Addressing S t r u c t u r e FIGURE 4 — L o c a l Addressing S t r u c t u r e A Program Development F a c i l i t y v i l£jS£°™l^dcje m e r i t s A number of persons have c o n t r i b u t e d to the p r e p a r a t i o n of t h i s t h e s i s and the development and programming e f f o r t which preceded i t . F i r s t , my s u p e r v i s o r s A.J. E a l l a r d , R. R e i t e r and J.E.H. Dempster have provided both encouragement and support. In a d d i t i o n , Alan B a l l a r d and Paul Whaley have put i n a great d e a l of e f f o r t t o make the SUE System Language (used to implement the prototype) usable under MTS. Going tack a t r i f l e f u r t h e r , I should a l s o l i k e to thank J.E.L. Peck who s t a r t e d my i n t e r e s t i n programming languages and W.J. Hansen who s t a r t e d my i n t e r e s t i n t h e i r implementation. Thanks a l s o go t c Henk B r u s s e l who proved i n t h i s day of s t r u c t u r e d programming and understandable systems a person can s t i l l read an IBM system d e s c r i p t i o n manual. The f i n a n c i a l a s s i s t a n c e of the N a t i o n a l Research C o u n c i l of Canada i s a l s o g r a t e f u l l y acknowledged. A Program Development F a c i l i t y 1 1 P a r t 1 — I n t r o d u c t i o n I In r e c e n t y e a r s , a g r e a t d e a l o f e f f o r t has been a p p l i e d t o t h e p r o b l e m s o f programming l a n g u a g e d e s i g n , w h i l e l i t t l e c o n s i d e r a t i o n has been g i v e n t o t h e p r o c e s s by which u s e r s m a n i p u l a t e b o t h t h e i n p u t and o u t p u t o f l a n g u a g e c o m p i l e r s . T h i s t h e s i s p r e s e n t s a s y s t e m which b r i n g s t o g e t h e r a number o f t h e f u n c t i o n s a s s o c i a t e d w i t h program d e v e l o p m e n t i n a way which i s , b o t h c o n v e n i e n t f o r t h e u s e r and e f f i c i e n t f o r t h e s y s t e m . T h i s i n t r o d u c t o r y s e c t i o n g i v e s a b r i e f o u t l i n e of why such f a c i l i t i e s o u ght to e x i s t , what s e r v i c e s t h e y s h o u l d p r o v i d e , t h e g o a l s o f t h e p r o j e c t u n d e r t a k e n h e r e , and some p r e v i o u s work t o w a r d s u n i f i e d s y s t e m s f o r program d e v e l o p m e n t . In t h e words o f an o l d s a y i n g , " I f n e c e s s i t y i s the mother a o f i n v e n t i o n t h e n l a z i n e s s i s c e r t a i n l y i t s f a t h e r . " T h i s s a y i n g sums up r a t h e r w e l l my m o t i v a t i o n f o r a t t e m p t i n g a p r o j e c t i n t h i s a r e a , s i n c e e x p e r i e n c e w i t h l a r g e p r o g r a m s w r i t t e n i n a v a r i e t y o f l a n g u a g e s has shown t h a t one o f t e n s p e n d s a g r e a t d e a l o f t i m e i n p e r f o r m i n g c l e r i c a l t a s k s a s s o c i a t e d w i t h managing s o u r c e and o b j e c t f i l e s , backup and a r c h i v e t a p e s , program d o c u m e n t a t i o n , and o t h e r i n f o r m a t i o n r e l a t e d t o l a r g e s c a l e s y s t e m s . F u r t h e r m o r e , a number of A Program Development F a c i l i t y 2 t r a g e d i e s brought on by i n a t t e n t i o n to t h i n g s l i k e changes to i n f o r m a t i o n common to a number of modules has added to my f r u s t r a t i o n with t r a d i t i o n a l methods of m a n i p u l a t i n g program t e x t . While the system d e s c r i b e d here dees not s o l v e a l l the problems i n v o l v e d , i t c e r t a i n l y s u g g e s t s what seems to be a f r u i t f u l d i r e c t i o n f o r f u t u r e work as w e l l as s o l v i n g a t l e a s t a few of the more t roublesome problems a s s o c i a t e d with the c o m p o s i t i o n and maintenance of l a r g e programs. 1.1. Why_ a Program Development F a c i l i t y ? Before d e s c r i b i n g the c a p a b i l i t i e s which a program development f a c i l i t y s h o u l d p r o v i d e , i t i s perhaps b e s t to g i v e some h i s t o r i c a l p e r s p e c t i v e on p r e v i o u s methods of m a n i p u l a t i n g program t e x t . The most p r i m i t i v e i d e n t i f i a b l e form cf program maintenance f a c i l i t y i s , of c o u r s e , a box of blank c a r d s and a handy keypunch. A l t h o u g h o f t e n t e d i o u s , t h i s system p r o v i d e s t h e a b i l i t y to do updates i n p l a c e on source d e c k s , a l l o w s s e p a r a t e programs t o be combined e a s i l y and p r o v i d e s i n f o r m a t i o n which can be manipula ted by u n i t r e c o r d machines. Indeed, i n many data p r o c e s s i n g s h o p s , c a r d s s t i l l form the backbone of program development f a c i l i t i e s . As an example, c a r d decks of source language f i l e d e f i n i t i o n s are kept around so that they can be i n c l u d e d with p r o c e s s i n g programs which o p e r a t e upon those f i l e s . Thus , a l t h o u g h many s o p h i s t i c a t e d computer users may c o n s i d e r c a r d s as an o b s o l e t e method o f h a n d l i n g d a t a , they do p r o v i d e a f u n c t i o n a l l y complete s e t of e d i t i n g p r i m i t i v e s a t a low c o s t i n s o f t w a r e and t e r m i n a l s u p p o r t f a c i l i t i e s . ft Program Development F a c i l i t y 3 Going a step beyond manual card deck m a n i p u l a t i o n ; one f i n d s the f i l e update programs used t o manage source f i l e s on some form of mass st o r a g e . In t h i s scheme, the user types program t e x t cards which are i n p u t to the e d i t o r along with v a r i o u s c o n t r o l cards which l o c a t e t e x t which i s to be i n s e r t e d , d e l e t e d , moved or r e p l a c e d . The update program i t s e l f need only f o l l o w the c l a s s i c "read o l d master... make updates... write new master" format of b u s i n e s s data p r o c e s s i n g . Under' t h i s scheme of making e d i t changes, the computer does the work of card s h u f f l i n g which i s performed manually i n the completely c a r d - o r i e n t e d system. When combined with a few f i l e h a ndling p r i m i t i v e s which enable the user to concatenate v a r i o u s f i l e s , a system of t h i s type should p r o v i d e i t s users with a l l the f e a t u r e s of the card system, a l b e i t with only a s l i g h t i n c r e a s e i n convenience. The t h i r d major step i n the development of program e d i t i n g f a c i l i t i e s was the i n t r o d u c t i o n of i n t e r a c t i v e text e d i t o r s . While such e d i t o r s vary widely i n both e x t e r n a l appearance and i n t e r n a l o r g a n i z a t i o n , they a l l e s s e n t i a l l y present the user with methods of i n t e r a c t i v e l y examining, a l t e r i n g , i n s e r t i n g and d e l e t i n g t e x t , u s u a l l y from some form of random access f i l e . These programs represent a major advance i n convenience over the update e d i t o r s i n t h a t changes can be made immediately and hence mistakes can o f t e n be caught and c o r r e c t e d without having to repeat the process of t y p i n g more cards and s u b m i t t i n g new runs. In a d d i t i o n , the user can g e n e r a l l y d e a l with a r b i t r a r i l y s m a l l p i e c e s of t e x t r a t h e r than having to r e - e n t e r e n t i r e l i n e s . As a bonus, many of these i n t e r a c t i v e e d i t i n g systems c o n t a i n s m a l l A Program Development F a c i l i t y 4 t e x t manipulation languages which allow the user to write programs to a u t o m a t i c a l l y perform e d i t i n g t a s k s over the e n t i r e f i l e . In terms of the f u n c t i o n a l c a p a b i l i t i e s of the systems i n v o l v e d , however, n e i t h e r the f i l e update programs nor the i n t e r a c t i v e e d i t o r s provide f e a t u r e s which cannot be managed by a p a t i e n t user with cards and a keypunch. T h i s does not imply t h a t e d i t i n g systems are of no value, but i t does suggest t h a t the b a s i c needs of a systems programmer have not changed since the e a r l i e s t days of computing. I maintain t h a t t h i s i s not the case, l a r g e l y because the s i z e and complexity of both systems and the languages used t c implement them have i n c r e a s e d g r e a t l y i n r e c e n t years. A s m a l l program (say up to 1000 l i n e s of your f a v o u r i t e programming language) can g e n e r a l l y be managed by any of the methods d e s c r i b e d above. A card deck c o n t a i n i n g i t i s s t i l l a manageable s i z e , and l i s t i n g s and computing c o s t s are sma l l enough t h a t the program may be compiled as a s i n g l e u n i t . When programs grow beyond t h i s s i z e , however, l i m i t a t i o n s such as the number of cards that w i l l f i t i n t o a card box, the number of pages i n l i s t i n g t h a t can be comfortably c a r r i e d , the s i z e of the compiler symbol t a b l e s and the amount of money one i s w i l l i n g t o pay to recompile a program a f t e r having made a t r i v i a l change a l l f o r c e the user to break h i s program i n t o s m a l l e r modules. R e a l i z i n g t h i s f a c t , language d e s i g n e r s have added a wide v a r i e t y of f e a t u r e s such as FORTRAN COMMON blocks, PL/I EXTERNAL and ENTRY v a r i a b l e s . Assembly language DSECTs and A Program Development F a c i l i t y 5 BCPL g l o b a l v e c t o r e n t r i e s to allow at l e a s t seme form of program segmentation. A common c h a r a c t e r i s t i c of these systems i s t h e i r i n a b i l i t y to check the correspondence of d e c l a r a t i o n s i n v a r i o u s modules as programs are compiled. T h i s leaves the user with the problem of maintaining l a r g e numbers of program segments each of which may access common v a r i a b l e s whose d e f i n i t i o n s are not checked f o r c o n s i s t e n c y by the compiling system. As anyone who has had t r o u b l e with mismatched FORTRAN COMMON bl o c k s knows, i t can be a f r u s t r a t i n g experience. In f a c t , the problem of c o m p i l i n g very l a r g e s c a l e programs can grow i n t o a very complex task, as i n the case of g e n e r a t i n g a l a r g e o p e r a t i n g system, 0 In the SUE System Language [ATWO], one can see at l e a s t the s t a r t of more secure methods of managing separate c o m p i l a t i o n s . By making a d i s t i n c t i o n between g l o b a l data open to a number of separate procedures and l o c a l data whose access i s r e s t r i c t e d to the body of a s i n g l e procedure, the designers of the language have managed to implement a system i n which 'the v a l i d i t y of accesses to common data may be checked even though se p a r a t e c o m p i l a t i o n s are p o s s i b l e . The only way i n which t h i s can be managed i s through an e d i t i n g system which notes changes, a l l o w i n g the compiler to i n c l u d e some i n f o r m a t i o n regarding the date on which a procedure was l a s t changed with i t s output o b j e c t module. The loader can then check the v a l i d i t y of a group of procedures combined i n t o a program. T h i s s t i l l l eaves the user with the problem of r e c o m p i l i n g the c o r r e c t b l o c k s a f t e r a g l o b a l d e f i n i t i o n has been changed even though the system c o u l d e v e n t u a l l y i n d i c a t e h i s mistake should he f a i l to & Program Development F a c i l i t y 6 do s o . I n t e r e s t i n g l y enough, the c u r r e n t implementation of the language [CLAR] makes no e f f o r t to c o r r e c t l y maintain t h i s i n f o r m a t i o n , l e a v i n g the r e s p o n s i b i l i t y f o r c o r r e c t l y combining programs with the user. we now come to the e s s e n t i a l f e a t u r e missing from the methods of developing and ma i n t a i n i n g source t e x t used to t h i s date, that of u n i f i c a t i o n of the f u n c t i o n s of the system. While the above d i s c u s s i o n has concerned i t s e l f mainly with the e d i t i n g and com p i l i n g f u n c t i o n s of program development, once these f e a t u r e s have been brought together i t seems a ra t h e r obvious e x t e n s i o n to i n c l u d e systems capable of other simple c l e r i c a l f u n c t i o n s such as the management of documentation and tape backups. \ 1 . 2 . P r o j e c t Goals Now t h a t the e s s e n t i a l i d e a of u n i f y i n g the f u n c t i o n s of a number of separate programs used to develop other, programs has been presented, i t would be wise to l i s t some of the more important f u n c t i o n s i n v o l v e d . The main f u n c t i o n s of e d i t i n g and co m p i l i n g source t e x t have a l r e a d y been presented and c l e a r l y must form the b a s i s f o r any such system. In a d d i t i o n to these we have the f u n c t i o n s of paragraphing source t e x t i n t o a c a n o n i c a l format, c r o s s r e f e r e n c i n g i d e n t i f i e r s w ithin source t e x t , and p r o v i d i n g runtime support f o r generated o b j e c t modules i n c l u d i n g e r r o r monitors, i n t e r a c t i v e debugging f e a t u r e s , and program t r a c e and p r o f i l e f a c i l i t i e s . Before attempting a p r o j e c t of t h i s type, one i s forc e d to A Program Development F a c i l i t y 7 r e a l i z e the d i f f i c u l t i e s imposed by the sheer s i z e of a programming system of t h i s type. Even though the system mainly attempts to b r i n g together a number of well-understood program manipulation f a c i l i t i e s through a common data s t r u c t u r e , the e n t i r e system becomes a major e f f o r t . The problem of breadth versus depth, or the d i f f e r e n c e between a l i m i t e d system implemented f o r a t r u l y u s e f u l language and a f u l l y operative system implemented f o r a t r i v i a l language must a l s o be considered i n planning a p r o j e c t of t h i s nature. In view of the f a c t that the l i m i t e d time a v a i l a b l e would force the c r e a t i o n of what i s at best a small prototype, i t was decided that e f f o r t should be expended upon p r o v i d i n g more system fe a t u r e s rather than on p r o v i d i n g more language f e a t u r e s . In r e t r o s p e c t i t would be r e l a t i v e l y easy t o extend the basic s t r u c t u r e of the system to cover a much l a r g e r language, and that such an extension would be approximately l i n e a r with the s i z e cf such a language. Indeed, the f i n a l s t r u c t u r e chosen f o r the system would make an extension l a r g e l y a matter of r e w r i t i n g a number of case statements located i n s t r a t e g i c places i n the code. In the f i n a l design, the main emphasis was placed on c o n s t r u c t i o n of the e d i t i n g , paragraphing and compiling f u n c t i o n s of the system, s i n c e these c l e a r l y placed the most severe demands upon the main data s t r u c t u r e s i n v o l v e d . The programming language a l s o provided an opportunity to reduce the scope of the p r o j e c t . The language f i n a l l y designed was a simple, s t r o n g l y typed one based on the v a r i a b l e d e c l a r a t i o n s t r u c t u r e of the SUE System Language. Though the e l i m i n a t i o n of types from t h i s language would c e r t a i n l y s i m p l i f y i t s A Program Development F a c i l i t y 8 implementation, i t would a l s o make major d i f f e r e n c e s i n the compiler o r g a n i z a t i o n . As i t i s , the system shews that type in f o r m a t i o n poses no p a r t i c u l a r d i f f i c u l t y provided that i t i s kept independent of s y n t a c t i c information and that type and other semantic checks are i s o l a t e d i n the compiling phase. As i s often the case with l a r g e - s c a l e systems, the problems ass o c i a t e d with the implementation are c l e a r l y those of data s t r u c t u r e . Such a u n i f i e d system must represent program text i n a manner which can be e a s i l y e d i t e d , compiled and transformed back to a source r e p r e s e n t a t i o n f o r the use of the programmer. C l e a r l y such a data s t r u c t u r e could use one of a number of formats, many of which would cater to p a r t i c u l a r portions cf the system. As an example, the system could use the standard character r e p r e s e n t a t i o n of the program, leav i n g the e d i t o r with a r e l a t i v e l y simple task of pushing program t e x t about i n the appropriate fashion while f o r c i n g the compiler to scan, parse and synthesize the e n t i r e c o m p i l a t i o n u n i t when transformation i n t o object code becomes necessary. On the other extreme, t e x t could be represented as object code and a number of t a b l e s g i v i n g i n f o r m a t i o n which would allow r e c o n s t r u c t i o n cf the o r i g i n a l t e x t through a decompilation procedure. Using t h i s r e p r e s e n t a t i o n , the e d i t o r would be forced to decompile and recompile source text as each change was made, while the compiler would be l e f t with l i t t l e or nothing to do. The data s t r u c t u r e chosen to represent the source program i s that of a parse t r e e . This r e p r e s e n t a t i o n has provided an e x c e l l e n t common ground f o r the modules of the system which act A Program Development F a c i l i t y 9 upon i t and has not f o r c e d any module to do a p a r t i c u l a r l y l a r g e amount of work. While other forms of t e x t r e p r e s e n t a t i o n are p o s s i b l e , the t r e e r e p r e s e n t a t i o n seems to be most s a t i s f a c t o r y . The f i n a l r e s u l t of the p r o j e c t i s an e d i t o r - c o m p i l e r o p e r a t i n g through an IBM 3270 d i s p l a y . The system provides the a b i l i t y to enter, d i s p l a y , a l t e r and compile programs, as w e l l as the a b i l i t y t o checkpoint and r e s t o r e the e n t i r e system workspace c o n t a i n i n g an i n t e r n a l r e p r e s e n t a t i o n of the program t e x t . A separate i n t e r p r e t e r i s provided f o r the pseudo machine code generated by the compiler. Although the system must be regarded as a prototype, i t does provide the user with a wide range of f a c i l i t i e s under a s i n g l e system. The f o l l o w i n g c h a p t e r s c o n t a i n d e t a i l e d d e s c r i p t i o n s of the system from both e x t e r n a l and i n t e r n a l viewpoints, and a sample run showing the system i n a c t i o n i s i n c l u d e d as an appendix. 1.3. Some Persona 1 P r e j u d i c e s Since a system of t h i s type must i n t e r a c t q u i t e c l o s e l y with i t s u s e r s , i t i s o f t e n d i f f i c u l t to d i s t i n g u i s h between i t s cosmetic appearance and i t s i n t r i n s i c l i m i t a t i o n s . As i s o f t e n the case with prototype systems, the Eighty-One system s u f f e r s i t s share of cosmetic d e f e c t s and p e c u l i a r i t i e s . While these w i l l be d i s c u s s e d l a t e r i n t h i s r e p o r t , i t i s hoped that the reader w i l l be able to make the d i s t i n c t i o n between sma l l design mistakes and l i m i t a t i o n s imposed by the paradigm under which the system operates. Experience with other i n t e r a c t i v e systems and programming A Program Development F a c i l i t y 10 p r o j e c t s has infl u e n c e d my own views on the human engineering of systems of t h i s type, and thus i n f l u e n c e d the design of many of the e x t e r n a l features of t h i s system. In a l l systems there must be some notion of s i m p l i c i t y . This view lead to the c r e a t i o n of a command language c o n t a i n i n g a small number of commands which are f u n c t i o n a l l y complete and easy to use. At the same time, however, the underlying s t r u c t u r e cf a syntax d i r e c t e d e d i t o r f o r c e s the user to have a f a i r idea of the syntax of the language which he i s e d i t i n g . Should t h i s complexity enhance ease of use, i t can be j u s t i f i e d on the grounds that the i n t e r n a l s t r u c t u r e obeys a set of simple r u l e s . In my op i n i o n , i t i s qu i t e acceptable to require a f a i r b i t of knowledge of the system p r o v i d i n g t h a t t h i s knowledge r e s t s on a s u f f i c i e n t l y s m a l l base. This philosophy a l s o r e s u l t s i n a choice of commands which could be abbreviated uniquely to s i n g l e l e t t e r s , even though the mnemonics may seem strange. In t h i s case, the convenience of s i n g l e l e t t e r a b b r e v i a t i o n s outweighs the problem of l e a r n i n g a few odd command names. A major design d e c i s i o n i n the implementation of the system i s that of separating the e d i t o r - c o m p i l e r from the runtime monitor of the system. This i s i n sharp c o n t r a s t t c most LISP based program manipulation f a c i l i t i e s i n which a l l work i s done under the auspices of EVAL, which i s the i n t e r p r e t e r i t s e l f . Again, personal prejudice r a t h e r than t e c h n i c a l d i f f i c u l t i e s are res p o n s i b l e f o r t h i s d e c i s i o n . In my opin i o n , l e a v i n g the i n t e r p r e t e r e a s i l y a c c e s s i b l e often leads to a sloppy " l e t s - t r y -i t - a n d - s e e - i f - i t - w o r k s " form of debugging i n which system convenience i s used to replace c a r e f u l thought. I n t e r e s t i n g l y A Program Development F a c i l i t y 11 enough, a system of t h i s type c o u l d be modified t o enforce a " p e r i o d of r e f l e c t i o n " between c o m p i l a t i o n s by r e f u s i n g to compile any program which had produced a runtime e r r o r w i t h i n the l a s t h a l f - h o u r of r e a l time. Further checks could be a p p l i e d i n order to enforce other programming r u l e s such as " a l l n e w l y - a l t e r e d programs must be run on a s e t of t e s t data." T h i s design a l s o demonstrates t h a t the system c o u l d be adapted to languages r e q u i r i n g l i t t l e or no run time support such as those intended to be run on bare o b j e c t machines. A f i n a l p e r s o n a l p r e j u d i c e concerns the type of device r e q u i r e d f o r communication with the user. In order tc p r o p e r l y implement a system of t h i s type, i t i s a b s o l u t e l y necessary to use a device which i s f a s t enough to keep the piece cf program t e x t being e d i t e d b e f o r e the user. In the prototype system, the IBM 3270 d i s p l a y [IBM] serves t h i s purpose q u i t e w e l l , although any number of s i m i l a r CRT d e v i c e s s e r v i c e d by s u f f i c i e n t l y f a s t l i n e s would be e q u a l l y s u i t a b l e . I d e a l l y , the screen should be r e f r e s h e d i n about one second, which would r e q u i r e a l i n e speed of 16000 baud to s e r v i c e a 2000 c h a r a c t e r screen. An average screen d i s p l a y e d by the system i s r a r e l y more than h a l f f u l l , however, thus making a r a t e of 8000 baud q u i t e a c c e p t a b l e . My experience suggests that i t i s too dangerous to make e d i t i n g changess without immediate v e r i f i c a t i o n c f the changes j u s t as l i f e i s too s h o r t to wait f o r such v e r i f i c a t i o n on a hardcopy d e v i c e o p e r a t i n g at f i f t e e n c h a r a c t e r s per second. A Program Development F a c i l i t y 12 1.4. Advantages While the primary advantage of the system i s i t s a b i l i t y to e l i m i n a t e much of the c l e r i c a l work and associated e r r o r s i n program development, a number of other advantages of t h i s type of system are also apparent. To begin with, the t e x t input to the e d i t o r i s subjected to l e x i c a l and s y n t a c t i c a n a l y s i s only once, thus p r o v i d i n g a considerable saving i n scanning and parsing time. Further m o d i f i c a t i o n to pieces of program t e x t r e q u i r e only the p a r s i n g of that t e x t which i s i n s e r t e d . The f a c t that the system i t s e l f keeps track of those procedures r e g u i r i n g r e c o m p i l a t i o n a l s o adds to system e f f i c i e n c y by a l l o w i n g the compiler to re-compile only those procedures which have been a l t e r e d s i n c e they were l a s t compiled. Such a s t r u c t u r e i s p a r t i c u l a r l y appealing to those who have teen forced to recompile l a r g e programs on account of a s i n g l e changed i d e n t i f i e r . Although a user himself could, given a s u i t a b l e language and implementation, perform s i m i l a r a c t i o n s , the problems of maintaining s u i t a b l e f i l e s and sequences to be input to the system are r a t h e r awful. As has been pointed out, the system also provides a secure base on which to b u i l d more s o p h i s t i c a t e d f e a t u r e s . As an example, a u n i f i e d system of t h i s type would allow a language designer to monitor what types of language c o n s t r u c t s are most often changed by the user, and hence gain i n s i g h t i n t o e r r o r prone c o n s t r u c t s i n the language. The f i n a l advantages of the design come i n the area of user input and system output. As Hansen points cut i n h i s A Program Development F a c i l i t y 13 d e s c r i p t i o n of Emily [HANS], t e x t e d i t o r s with some knowledge of the s t r u c t u r e of the t e x t they are e d i t i n g can be more convenient to use than those which t r e a t t e x t as an unstructured s t r i n g of characters. There i s a l s o a c l e a r p r a c t i c a l and p s y c h o l o g i c a l advantage i n using a system which refuses to accept s t r i n g s which are not s y n t a c t i c a l l y c o r r e c t and a l l o w s the user to c o r r e c t h i s mistakes immediately. Thus, the s t r u c t u r e d t e x t e d i t o r forced by the i n t e r n a l tree r e p r e s e n t a t i o n i s a valuable a d d i t i o n to a programming system. In the area of output, work on the SUE System Language has suggested that enforcing a c a n o n i c a l output format f o r program l i s t i n g s i s a valuable a i d , p a r t i c u l a r l y cn large p r o j e c t s . As i t becomes more obvious that programs are read by people as much as by machines, the p r o v i s i o n of properly s t r u c t u r e d l i s t i n g s w i l l become a n e c e s s i t y . 1. 5. Previous Work As has been suggested, the main purpose cf t h i s project i s t o u n i f y a number of e x i s t i n g f u n c t i o n s under a s i n g l e data s t r u c t u r e . In view of t h i s f a c t , i t would be w e l l to examine a number of approaches to problems such as syntax-directed e d i t i n g and s e l e c t i v e r e c o m p i l a t i o n . A Program Development F a c i l i t y 14 1 . 5 . 1 . INTERLISP The system which comes c l o s e s t to p r o v i d i n g a complete programming environment u n i f i e d under a s i n g l e data s t r u c t u r e i s INTERLISP [TEIT ]. In t h i s case, the i n t e r n a l data s t r u c t u r e i s the obvious and simple one suggested by the t r i v i a l syntax of LISP, thus s e t t l i n g the problem of i n t e r n a l r e p r e s e n t a t i o n of program t e x t . The system provides a complete s e t of program e d i t i n g f a c i l i t i e s as w e l l as a runtime system {DwTPf - Do What I Mean) designed to catch and c o r r e c t many common programming e r r o r s . While many of the f e a t u r e s of t h i s runtime system go a g a i n s t my personal i d e a s on how a monitor should behave, the system has many s a t i s f i e d users. Since INTERLISP i s b a s i c a l l y i n t e r p r e t i v e , the guestions a s s o c i a t e d with separate c o m p i l a t i o n s of languages with more complex scope r u l e s do not appear. The compiler can be used to compile i n d i v i d u a l LISP f u n c t i o n s or group of f u n c t i o n s , but a l l b i n d i n g of v a r i a b l e s used i n these programs i s done a t ex e c u t i o n time. In a system of t h i s t ype, the i n t e r p r e t e r r a t h e r than the compiler i s r e s p o n s i b l e f o r management cf the symbcl t a b l e . T h i s approach c e r t a i n l y does have some advantages i n an environment i n which programs may be changing as they are executed, but t h i s f l e x i b i l i t y i s gained only at c o n s i d e r a b l e c o s t i n runtime e f f i c i e n c y . A f u r t h e r c o n s i d e r a t i o n i s that v a r i a b l e type i n f o r m a t i o n i s a l s o maintained dynamically by the i n t e r p r e t e r , a l l o w i n g the system to detec t many type e r r o r s as execution proceeds but preventing i t from announcing such e r r o r s a t compile time. A Program Development F a c i l i t y 15 1.5.2. The SUE System Language The SUE System Language implementation [CLAE] a l s o makes some attempt to u t i l i z e an in t e r m e d i a t e t e x t r e p r e s e n t a t i o n f o r program t e x t . In c o m p i l i n g a SUE program, the f i r s t phase ( c a l l e d SCRUNCH) converts source t e x t i n t o a token stream format which i s output to a d i s k f i l e . T h i s phase of the compiler a l s o c o n t a i n s an update e d i t o r which w i l l allow changes to token f i l e s p r e v i o u s l y generated by SCRUNCH. In order to maintain the i n t e g r i t y of the scope r u l e s enforced by the language i t s e l f , the e d i t i n g system a t t a c h e s a unique date to each f i l e which i t produces. The second phase of the compiler reads the compressed token f i l e and produces a paragraphed source l i s t i n g of the program along with an o b j e c t module f o r that prcgram which c o n t a i n s the date on which the source t e x t was l a s t a l t e r e d . The f i n a l phase of the system, the program lo a d e r , can decide from the dates of the f i l e s s u p p l i e d whether or not a p a r t i c u l a r combination of o b j e c t modules i s v a l i d . The s e p a r a t i o n of g l o b a l and l o c a l data which allows independent r e c o m p i l a t i o n of v a r i o u s programs i s c e r t a i n l y one of the major i n n o v a t i o n s of the language. The e d i t i n g f a c i l i t i e s s u p p l i e d leave something to be d e s i r e d , however, and hence the v e r s i o n of the compiler running under MTS has had these f a c i l i t i e s removed. T h i s change a l s o prevents the compiler from c o r r e c t l y checking that the data b l o c k s used f o r v a r i o u s c o m p i l a t i o n s are compatible, hence l e a v i n g t c the user the job of ensuring that the c o r r e c t modules are recompiled a f t e r e d i t i n g changes. Even under the OS v e r s i o n the user i s A Program Development F a c i l i t y 16 required to s p e c i f y which programs he t h i n k s r e q u i r e r e c o m p i l a t i o n and then wait u n t i l the program i s tc be run to f i n d whether the system approves of h i s choices. 1.5 . 3 . Emiljy. The Emily t e x t e d i t i n g system [H AN A ], developed t c operate upon data which conforms t c BNF d e s c r i p t i o n s , i s an example of a syntax d i r e c t e d e d i t o r f o r st r u c t u r e d t e x t such as that of most programming languages. In t h i s system, the programmer uses a graphics t e r m i n a l ( i n t h i s case an IBM 2250) to both compose and e d i t h i s programs. Programs themselves are parsed as they are entered and converted i n t o a tree s t r u c t u r e which i s stored on disk. The f i n a l output of the system i s a paragraphed l i s t i n g f o r i n p u t to e x i s t i n g compilers and thus no attempt i s made to un i f y the e d i t o r i n t o a more complete programming system. 1.5.4. VERS The VERS language [ESC], designed as an experiment with incremental compilation of b l o c k - s t r u c t u r e d languages, also attempts to address some of the problems approached here. I t d i f f e r s from the Eighty-One system i n that e d i t i n g i s done by a conventional t e x t e d i t o r with the i n t e r n a l object program r e p r e s e n t a t i o n t i e d to the e x t e r n a l t e x t . Decisions on what po r t i o n s of programs are i n need of rec o m p i l a t i o n are made on the basis of information supplied by the e d i t o r t o the c o n t r o l l i n g p o r t i o n s of the program. However, such a s t r u c t u r e f o r c e s the compiler to do a complete scan and parse of any part A Program Development F a c i l i t y 17 of the source t e x t which i s to be recompiled and thus seems to make too many concessions to the e x t e r n a l r e p r e s e n t a t i o n . One of the major features of the system i s that i t i s capable of reco m p i l i n g programs s t r i c t l y on the basis of information which i t maintains by i t s e l f , without any i n t e r v e n t i o n by the user. A Program Development F a c i l i t y 18 Pa r t 2 — User's Guide | I .j 2.1. The Language The language used by the system i s a mixture c f s y n t a c t i c and semantic f e a t u r e s borrowed from a number cf e x i s t i n g languages, notably TOY [HORN], the SUE System Language [ATWO], and ALGOL 68 [VANW], In order to keep the coding r e g u i r e d to implement the system t o a minimum, the language was kept as simple as p o s s i b l e while s t i l l l e a v i n g i t capable cf t a c k l i n g s e r i o u s problems. The end r e s u l t i s a language which, although i t i s c l e a r l y not a s e r i o u s p r o d u c t i o n t o o l , i s q u i t e a t t r a c t i v e because of i t s very s i m p l i c i t y . The Eighty-One language i s both e x p r e s s i o n o r i e n t e d * i m p l y i n g that a l l major s t r u c t u r e s of the language d e l i v e r v a l u e s , and s t r o n g l y typed, i m p l y i n g t h a t the types cf these v a l u e s may be computed a t compile time. The types allowed are INTEGER, a 32 b i t signed i n t e g e r value, and CHARACTER, a s t r i n g c o n s i s t i n g of from 0 to 255 c o n s e c u t i v e c h a r a c t e r s . The language supports a r r a y s of both b a s i c types. While t h i s set of data s t r u c t u r i n g p r i m i t i v e s may not seem too impressive i n the A Program Development F a c i l i t y 19 face of more complex languages, i t should be pointed out t h a t these f e a t u r e s are almost as powerful as those provided by FORTRAN (the Eighty-One language does not supply the data type REAL), while g i v i n g the user the a d d i t i o n a l a b i l i t y to manipulate character s t r i n g s i n a reasonable f a s h i o n . The language i s c u r r e n t l y implemented through an i n t e r p r e t e r which executes code f o r a simple stack machine designed f o r the language, but there would be l i t t l e d i f f i c u l t y i n generating d i r e c t l y executable S/360 code from the language. The remainder of t h i s s e c t i o n w i l l deal with the s y n t a c t i c and semantic s t r u c t u r e of the language and describe the b u i l t - i n f u n c t i o n s and pseudc-variables which are a v a i l a b l e . 2.1.1. Tokens of the Language In g e n e r a l , the tokens of the Eighty-One language are q u i t e s i m i l a r t c those used by implementations cf s i m i l a r languages. In the BNF d e f i n i t i o n of the language which f o l l o w s , the nonterminal <IDENTIFIER> represents a sequence of characters beginning with a l e t t e r and followed by zero or more l e t t e r s or d i g i t s , up to a maximum length of 255 charac t e r s . The set of l e t t e r s i n c l u d e s the alph a b e t i c characters "A" - "Z" as w e l l as the s p e c i a l characters "$" and "_". C e r t a i n s t r i n g s cf l e t t e r s which f i t the syntax of <IDENTIFIER> are used by the compiler as reserved words. These words appear without angle brackets i n the BNF d e f i n i t i o n and may not be used as i d e n t i f i e r s . The reserved words are "BEGIN", "CHARACTER", "CODE", "DATA", "DO", "ELSE", "END", "EXIT", " F I " , " I F " , "INTEGER", "OD", "PROCEDURE", "THEN" and "WITH". A Program Development F a c i l i t y 20 The nonterminal <NUMBER> r e p r e s e n t s a decimal number in the standard n o t a t i o n i n the range - 2 3 1 to 2 3 1 - 1 . The nonterminal <STRING> r e p r e s e n t s a seguence of a r b i t r a r y c h a r a c t e r s enclosed i n quotes ("), with any quote w i t h i n the s t r i n g represented by two quotes. <STRING>s, l i k e <IDENTIFIEE>s, have a maximum le n g t h of 255 c h a r a c t e r s . The nonterminal <OPERATOR> repr e s e n t s one of the s t r i n g s of s p e c i a l symbols » + ", ••-», ••*««, ''/", "S", n | n f i . = t i f «-.=•» r ii<« , »>«t f •»<=«, »>=« and ":=". In a d d i t i o n , a number of s p e c i a l symbols (such as *»;") which appear d i r e c t l y i n the BUF d e f i n i t i o n are r e q u i r e d by the syntax. The scanner r e s o l v e s a m b i g u i t i e s i n s p e c i a l symbols by matching the l o n g e s t p o s s i b l e sequence of symbols not i n c l u d i n g blanks. Thus, the s t r i n g "-• =" i s a "->" symbol followed by a symbol while the s t r i n g »-.=" i s a s i n g l e «-•=" symbol. Comments may be i n t r o d u c e d i n t o the t e x t by the symbol "0" f o l l o w e d by an a r b i t r a r y s t r i n g of t e x t up to the end of the c u r r e n t l i n e . The t e x t of these comments i s saved by the system and i s p r i n t e d along with l i s t i n g s and screen d i s p l a y s , but such t e x t i s ignored by the semantic phases of the compiler. The user should note t h a t any comment which i s the only t h i n g on a p a r t i c u l a r l i n e w i l l be placed on a separate l i n e by the paragrapher r e g a r d l e s s of i t s c o n t e x t . A Program Development F a c i l i t y 21 2 . 1 . 2 . C ompilation Units 1. COMPILATION UNIT> ::= PROCEDURE <ICENTIFIER> <FORMAL PARAMET ERS> DATA <DECLARATION SEQUENCE> CODE EXPRESSION SEQU.ENCE> 2. <FORMAL PARAMETERS> ::= ( <ID LIST> ) 3. | <EMPTY> 4. <ID LIST> ::= <IDENTIFIER> 5 . | <ID LIST> , <IDENTIFIER> The <COMPILATION UNIT>, which i s analogous tc the procedure d e f i n i t i o n of most other A l g o l - l i k e languages, allows the user to d e f i n e procedures. In a d d i t i o n , i t d e f i n e s the l e v e l a t which the compiler can break the c o m p i l a t i o n of a l a r g e program i n t o a number of separate u n i t s . The <FORMAL PARAMETERS> cf the u n i t correspond to the types of the parameters d e c l a r e d i n the d e c l a r a t i o n of the procedure of the same name. Since the top-l e v e l procedure of a program cannot be d e c l a r e d , that procedure may not have any parameters. The < DECLARATION SEQUENCE> which f o l l o w s the re s e r v e d word DATA d e c l a r e s v a r i a b l e s and procedures which are g l o b a l t c both the e x p r e s s i o n s of the <EXPRESSION SEQUENCE> and the expressions contained i n a l l nested procedures. A procedure P i s said tc be nested i n a procedure Q should procedure E be d e c l a r e d i n the data segment of procedure Q, or. s h o u l d procedure P be d e c l a r e d i n the data segment of some other procedure nested i n procedure Q. In terms of the system r e c o m p i l a t i o n s t r a t e g y , the v a r i a b l e s d e c l a r e d i n the data segment of ..a <CCMPILATION UNIT> are the only ones which must be considered i n re c o m p i l i n g procedures nested w i t h i n t h a t u n i t . A Program Development F a c i l i t y 22 The EXPRESSION SEQUENCE> of the u n i t i s a s e r i e s of ex p r e s s i o n s which perform computations f o r the u n i t . The value of the <EXPRESSION SEQUENCE> y i e l d s the value r e s u l t i n g from a c a l l on the procedure, and the type of t h i s value must agree with the d e c l a r a t i o n of the procedure. At the top l e v e l , both the value returned and i t s type are ignored. 2. 1.3. D e c l a r a t i o n s 6. DECLARATION SEQUENCE> : := DECLARATION SEQUENCER ; < DECLAR ATION> 7. | DMPTY> 8. <DECLARATION> : := DECLARATION TYPE> <PAHAMETERS> <ID LIST> 9. | DECLARATION TYPE> PROCEDURE <IDENTIFIIR> <ACCEPTS TYPE OPTION> 10. <DECLARATION TY.PE> : := INTEGER 11. | CHARACTER 12. XACCEPTS TYPE OPTION> :: = ( <TYPE LIST> ) 13. | <EMPTY> 14. <TYPE LIST> ::= <TYPE LIST> , <TYPE> 15. | <TYPE> 16. <TYPE> ::= DECLARATION TYPE> DCUND LIST OPTION> 17. <B0UND LIST OPTION> ::= { <BOUND LIST> ) 18. | <EMPTY> 19. <BOUND LIST> ::= <BOUND LIST> , <BOUND> 20. | <B0UND> 21. <BOUND> ::= <EMPTY> As i n d i c a t e d by the grammar, a DECLAR AT ION SEQUENCER i s a p o s s i b l y empty l i s t of DECLARATIONS separated by semicolons. Each <DECLARATION> i s e i t h e r a v a r i a b l e d e c l a r a t i o n or a procedure d e c l a r a t i o n . The v a r i a b l e d e c l a r a t i o n , which i s d e s c r i b e d by the f i r s t p roduction of <DECLARATION>, r e s e r v e s A Program Development F a c i l i t y 23 s t o r a g e f o r v a r i a b l e s named by the i d e n t i f i e r s i n i t s <ID LIST>. Should the <PARAMETERS> of a p a r t i c u l a r d e c l a r a t i o n be empty, the v a r i a b l e s d e c l a r e d w i t h i n i t are simple v a r i a b l e s . Should the parameters be present, they must be i n t e g e r - v a l u e d e x p r e s s i o n s and each of the i d e n t i f i e r s i n the <II LIST> of the d e c l a r a t i o n becomes an ar r a y with s u b s c r i p t s v a r y i n g from 0 to the v a l u e of the corresponding e x p r e s s i o n . Note that the values of the <PARAMETERS> need not be known at compile time and t h a t any i n t e g e r - v a l u e d e x p r e s s i o n w i l l s u f f i c e . The procedure d e c l a r a t i o n d e s c r i b e d by the second pr o d u c t i o n f o r <DECLARATION> allows the user to d e c l a r e a procedure which w i l l be d e f i n e d by a subsequent c o m p i l a t i o n block. The DECLARATION TYPE> of t h i s procedure must correspond to the type returned by the procedure, as must the type of the v a r i o u s parameters ( i f any) i n d i c a t e d i n the <ACCEPTS TYPE 0PTI0N>. Procedures a c c e p t i n g a r r a y parameters are i n d i c a t e d by d e c l a r i n g the v a r i a b l e s which they accept with empty bounds. 2. 1.4. Expres s i o n s 22. EXPRESSION SEQUENCE> ::= <EXPRESSION> 23. | EXPRESSION SEQUENCE> ; <EXPRESSION> 24. <EXPRESSION> ::= <PRIMARY> 25. | <PRIMARY> <OPERATOR> <EXPRESSICN> 26. | EXIT WITH <EXPRESSION> As i n d i c a t e d by the f i r s t p roduction r u l e , an EXPRESSION SEQDENCE> i s a non-empty seguence of EXPRESSION>s separated by semicolons. Each of these e x p r e s s i o n s may d e l i v e r a value of any type, but the type and value d e l i v e r e d by the o v e r a l l A Program Development F a c i l i t y 24 sequence are those r e t u r n e d by the l a s t element of the sequence. The v a l u e s of any members of the sequence ether than the l a s t a re d i s c a r d e d . The main p r o d u c t i o n of <EXPRESSION> allows the c r e a t i o n of a r i t h m e t i c expressions which r e t u r n new valu e s . The l i s t of accepted <OPERATOB>s i s given i n the s e c t i o n on symbols of the language. A l l of these o p e r a t o r s are de f i n e d f o r i n t e g e r operands with the expected meanings, but only the r e l a t i o n a l o p e r a t o r s , the assignment operator and the operator . '» + " (concatenation) are d e f i n e d over operands of type c h a r a c t e r . R e l a t i o n a l o p e r a t o r s such as "<" d e l i v e r i n t e g e r values of 0 and 1 r e g a r d l e s s of the type of t h e i r arguments with 0 corresponding to a f a l s e r e s u l t and 1 corresponding to a true one. Comparisons of s t r i n g s which are not of equal l e n g t h proceed as though the s h o r t e r of the two s t r i n g s i s padded with blanks to the length of the longer one. Thus, the ex p r e s s i o n "ABC" < "XYZ" has the value 1 while the e x p r e s s i o n "ABCD" < "ABC" has the value 0 . The user should note t h a t assignment i s considered as an operator which r e t u r n s the value of t h i s e x p r e s s i o n and, as a s i d e e f f e c t , a s s i g n s i t s right-hand s i d e value to i t s l e f t - h a n d s i d e v a r i a b l e . In t h i s case, there i s the semantic r e s t r i c t i o n t h a t the l e f t - h a n d s i d e of an assignment must be e i t h e r a simple v a r i a b l e name or the name of an array v a r i a b l e followed by a p p r o p r i a t e i n t e g e r s u b s c r i p t s . Thus, the language does not support any form o f r e f e r e n c e v a l u e s . A f u r t h e r p c i n t shown by the grammar i s t h a t a l l op e r a t o r s ( i n c l u d i n g , of course. A Program Development F a c i l i t y 2 5 assignment) have equal precedence and t h a t standard a s s o c i a t i o n i s from r i g h t to l e f t , i . e . , the e x p r e s s i o n s A := E * C + D and (A := (B * (C + D)) ) are e q u i v a l e n t . The EXIT WITH e x p r e s s i o n causes a branch to the end of the ne a r e s t e n c l o s i n g DO - OD block and s p e c i f i e s the value which t h a t block i s to r e t u r n . I t s f u n c t i o n w i l l be d e s c r i b e d more c a r e f u l l y i n the s e c t i o n d e a l i n g with DO - OD b l o c k s . 2 . 1 . 5 . P r i m a r i e s 2 7 . <PRIMABI> ::= <NUMBER> 2 8 . | <STRING> These productions allow f o r the use of i n t e g e r and s t r i n g c o n s t a n t s w i t h i n e x p r e s s i o n s . 2 9 . <PRIMARI> ::= ( <EXPRESSION> ) T h i s r u l e a l l o w s p a r e n t h e s i z e d expressions which change the order of e v a l u a t i o n . 30. <PRIMARY> ::= BEGIN DECLARATION SEQUENCE > EXPRESSION SEQUEUCE> END T h i s r u l e d e f i n e s a block s i m i l a r to that cf A l g o l 60. Since both the DECLARATION SEQUEUCE> and EXPRESSION SEQU1NCE> have alr e a d y been d e s c r i b e d , there i s l i t t l e t c say about the block except that i t s DECLARATION SEQUENCE> may not c o n t a i n any procedure d e c l a r a t i o n s . T h i s r e s t r i c t i o n f o r c e s the user to s p e c i f y g l o b a l data i n the DATA segment of a COMPILATION UNIT>, A Program Development F a c i l i t y 26 and hence l i m i t s access t o data d e c l a r e d w i t h i n the block to the procedure i n which the block e x i s t s . As one would expect, the block r e t u r n s the type and value of the EXPRESSION SEQUENCER, t h a t i s , the type and value of the l a s t member of the sequence. 31. <PRIMARY> ::= IF EXPRESSION THIN EXPRESSION SEQUENCE> ELSE EXPRESSION SEQUENCE> FI E v a l u a t i o n of an IF expre s s i o n proceeds by f i r s t e v a l u a t i n g the <EXPRESSION> f o l l o w i n g the IF. I f the value of t h i s <EXPRESSI0N> (which must be of type INTEGER) i s 0, then the value returned by the IF e x p r e s s i o n w i l l be the r e s u l t of e v a l u a t i n g the EXPRESSION SEQUENCE> f o l l o w i n g the ELSE. Otherwise, the r e s u l t returned w i l l be t h a t o f e v a l u a t i n g the EXPRESSION SEQUENCE> f o l l o w i n g the THEN. Since the type cf the IF e x p r e s s i o n must be known a t compile time, both the THEN and ELSE a l t e r n a t i v e s must be of the same type. The user should note t h a t the "S" and "|" o p e r a t o r s , which operate on the i n t e r n a l i n t e g e r r e p r e s e n t a t i o n of numbers, w i l l give the expected r e s u l t s f o r l o g i c a l e x p r e s s i o n s when used to produce the r e s u l t i n the c o n t r o l of an <IF EXPRESSIONS 32. <PRIMARY> ::= DO EXPRESSION SEQUENCE> OD The DO e x p r e s s i o n , s i m i l a r t o the CYCLE compound of the SUE System Language, p r o v i d e s the b a s i c means of r e p e t i t i o n . E v a l u a t i o n of the EXPRESSION SEQUENCER i s repeated u n t i l the e v a l u a t i o n of an EXIT WITH e x p r e s s i o n within that sequence takes p l a c e . At t h i s p o i n t , the value of the CO e x p r e s s i o n becomes the value of the EXIT WITH expre s s i o n , and e v a l u a t i o n proceeds A Program Development F a c i l i t y 27 with the e x p r e s s i o n f o l l o w i n g the DC e x p r e s s i o n . L i k e the IF e x p r e s s i o n , the type of the DO e x p r e s s i o n must be known at compile time, and hence the types of the e x i t s of a p a r t i c u l a r DO e x p r e s s i o n must be the same. A l s o , s i n c e a DO e x p r e s s i o n which does not c o n t a i n an EXIT WITH expression w i l l go i n t o an i n f i n i t e loop, the semantics of the language r e g u i r e that each DO e x p r e s s i o n c o n t a i n a t l e a s t one EXIT WITH e x p r e s s i o n . 33. <PRIMARY> ::= <IDENTIFIER> <PARAMETERS> 34. <PARAMETERS> : := ( EXPRESSION LIST> ) 35. | <EMPTY> 36. EXPRESSION LIST> : := <EXPRESSION> 37. | EXPRESSION LIST> , <EXPRESSIGN> T h i s p r o d u c t i o n of <PRIMARY> d e s c r i b e s the syntax of simple i d e n t i f i e r s , a r r a y i d e n t i f i e r s and procedure c a l l s . An i d e n t i f i e r s t a n d i n g alone ( i . e . , followed by an empty <PARAMETERS>) has as i t s value the c u r r e n t value of t h a t i d e n t i f i e r , unless, of course, i t i s on the l e f t - h a n d s i d e of an assignment o p e r a t o r , i n which case i t i n d i c a t e s a l o c a t i o n i n which the r i g h t - h a n d s i d e value i s to be s t o r e d . S u b s c r i p t e d array i d e n t i f i e r s behave s i m i l a r l y , with the semantic r e s t r i c t i o n s t h a t s u b s c r i p t i n g e x p r e s s i o n s must be i n t e g e r valued and that the number of s u b s c r i p t i n g e x p r e s s i o n s must be the same as the number of bounds i n the array d e c l a r a t i o n . When the <IDENTIFIER> has been de f i n e d as a procedure i d e n t i f i e r , i t s occurrence i n i t i a t e s a procedure c a l l with the s e t of parameters s p e c i f i e d . Simple v a r i a b l e s passed to procedures are passed by value, and must agree i n type with the A Program Development F a c i l i t y 28 d e c l a r a t i o n of the procedure. Array parameters are passer] by i n d i c a t i n g the name of the array i n the parameters l i s t . Both the type and number of bounds of the array must agree with the procedure d e c l a r a t i o n , but the values of the array bounds are i r r e l e v a n t . The values contained w i t h i n the array are passed to the procedure by reference, and hence any changes t c members of an array parameter w i t h i n a procedure are permanent. 2. 1.6. B u i l t - i n Functions and Pseudo-Variables In order to supply the user with a number of semantic a c t i o n s not a v a i l a b l e w i t h i n the language i t s e l f , the f o l l o w i n g f u n c t i o n s are a v a i l a b l e : a) STRING - which takes as argument a s i n g l e expression of type INTEGER and returns a character s t r i n g r e p r e s e n t a t i o n of that number. The number has no lea d i n g zeroes or t r a i l i n g blanks. As examples, STRING (0) = "0" while STRING(0 - 47) = "-47". b) SUBSTRING - which takes as arguments an expression of type CHARACTER and e i t h e r one or two expressions of type INTEGER. SUBSTRING re t u r n s a s t r i n g made up of the characters of i t s f i r s t argument s t a r t i n g with the character i n the p o s i t i o n i n d i c a t e d by i t s second argument and with length i n d i c a t e d by i t s t h i r d argument. The p o s i t i o n s of the s t r i n g are numbered from zero, and should the t h i r d argument be omitted, the e n t i r e remaining p o r t i o n of the s t r i n g i s returned. As examples, SUBSTRING("ABC",1,1) = " B " , SUBSTRING("ABC",1) = "BC" and SUBSTRING ("ABC",3) = A l l instances of SUBSTRING are checked at run time to ensure that the second parameter i s l e s s than or egual to the length of the s t r i n g and that the t h i r d argument A Program Development F a c i l i t y 29 ( i f i n cluded) s p e c i f i e s a length l e s s than or equal to the remaining l e n g t h of the s t r i n g . c) LENGTH - which takes as argument a s i n g l e e x p r e s s i o n of type CHARACTER and which r e t u r n s the i n t e g e r number of c h a r a c t e r s i n t h a t s t r i n g . The f o l l o w i n g p s e u d o - v a r i a b l e s are a l s o a v a i l a b l e : a) INPUT - which has as i t s value a c h a r a c t e r s t r i n g which i s the next l i n e of input (read from MTS u n i t SCARES). Thus, the e x p r e s s i o n "FOO := INPUT" w i l l a s s i g n the next l i n e of i n p u t to the c h a r a c t e r v a r i a b l e FOO and r e t u r n that c h a r a c t e r s t r i n g as i t s value. Assignments t o the v a r i a b l e INPUT are p r o h i b i t e d . b) OUTPUT - which may be assigned a value to be p r i n t e d as the next l i n e of output (on MTS l o g i c a l u n i t SPRINT). The l i n e i s t r a n s m i t t e d d i r e c t l y , and thus the v a r i o u s c a r r i a g e c o n t r o l s recognized by MTS have the d e s i r e d e f f e c t s . The v a r i a b l e OUTPUT has no value, and thus i t may only appear on the l e f t - h a n d s i d e of an assignment operator. 2.2. The Numbering Scheme In order to p r o v i d e both the user and the system with some method of r e f e r r i n g to s p e c i f i c l o c a t i o n s i n the program t r e e , a simple numbering scheme g e n e r a l l y r e f e r r e d to as "Eewey decimal n o t a t i o n " [KNUT] i s adopted. I f one imagines o n e s e l f a t a p a r t i c u l a r node of the program t r e e , a s e r i e s of numbers naming the branches to be taken at any subsequent node of the tree w i l l allow the user to "name" any subnode of t h a t t r e e . Since the parse node s t r u c t u r e of the t r e e f o l l o w s the BNF d e f i n i t i o n of A Program Development F a c i l i t y 30 the language, t h i s scheme i s r e l a t i v e l y s t r a i g h t f o r w a r d . If one c o n s i d e r s the IF e x p r e s s i o n , f o r example, which i s d e s c r i b e d by the p r o d u c t i o n <PRIMARY> ::= IF <EXPRESSION> THEN EXPRESSION SEQUENCE> ELSE EXPRESSION SEQUENCE> FI the s t r u c t u r e of the parse node r e p r e s e n t i n g t h i s statement i s q u i t e obvious. Such a node would c o n s i s t of three p o i n t e r s , the f i r s t r e f e r r i n g t o the <EXPRESSION> and the remaining two p o i n t e r s r e f e r r i n g to the EXPRESSION SEQUFNCE>s. Thus, when one i s at the IF e x p r e s s i o n node, the f i r s t EXPRESS ICN> can be r e f e r r e d t o by the number 1 while the two EXPRESSION SEQUENCE>s are r e f e r r e d t o by the numbers 2 and 3. Sequences of these numbers may be chained together to l o c a t e a r b i t r a r y subncdes i n r e l a t i o n t o a p a r t i c u l a r node of the program t r e e . For most r u l e s of the language grammar, the numbering scheme ' i s q u i t e s i m i l a r . In the case of sequences or l i s t s of items, however, the scheme changes somewhat. While the grammar would suggest that the s t r u c t u r e of a l i s t of items should te a b i n a r y t r e e with the number 1 i n d i c a t i n g the c u r r e n t member of the l i s t and the number 2 r e p r e s e n t i n g the remaining p o r t i o n of the l i s t (much l i k e the CAR and CDR of LISP), the system t r e a t s the l i s t as a l i n e a r s t r u c t u r e i n which the members of the l i s t are r e f e r r e d to by t h e i r p o s i t i o n numbers i n the l i s t . Thus, i n the EXPRESSION LIST> "A,B,c,D" the element "A" i s r e f e r r e d to by the number 1, while the element "D" i s r e f e r r e d to by the number 4. T h i s system prevents the user from " t a l k i n g about" c e r t a i n s y n t a c t i c tokens such as keywords and punctuation symbols. A Program Development F a c i l i t y 31 Thus, the user i s f o r c e d to make changes to the t r e e which are reasonable i n terms of the i n t e r n a l t r e e s t r u c t u r e . As with other s t r u c t u r e e d i t o r s of t h i s type, however, t h i s r e s t r i c t i o n may make t h i n g s d i f f i c u l t f o r a user who wishes t o make an ap p a r e n t l y simple t e x t u a l change to h i s program which would r e q u i r e major m o d i f i c a t i o n s of the underlying t r e e s t r u c t u r e . 2. 3. System E x t e r n a l s . 2.3.1. The Disp_lay Since the system e f f e c t i v e l y takes c o n t r o l of the 3270 from the standard Device S e r v i c e Routine s u p p l i e d by MTS [OST], the e x t e r n a l appearance of the system i s q u i t e d i f f e r e n t from t h a t of most programs which operate on the 3270. To begin with, the system d i v i d e s the 3270 screen i n t o three separate areas. The f i r s t of these areas, which w i l l be r e f e r r e d to as the d i s p l a y area, i s made up of the top s i x t e e n l i n e s of the screen. One of the more important f e a t u r e s o f the e d i t o r i s the c u r r e n t program t r e e p o i n t e r which giv e s the user the a b i l i t y to move about the program t r e e and hence c o n t r o l the context of h i s commands. T h i s p o i n t e r (which i s i n i t i a l l y n u l l s i n c e no program t e x t has been entered) i s a l s o used by the system as the o r i g i n of the paragraphed program t e x t shown i n the d i s p l a y area. Since the s i z e of the area i s l i m i t e d , the program w i l l only d i s p l a y t e x t t o a c e r t a i n l e v e l of d e t a i l , and, should the depth of the t r e e segment being e d i t e d exceed t h i s l e v e l , the program w i l l d i s p l a y the name of the nonterminal node at that l o c a t i o n between octothorpes (#). S i m i l a r l y , should the len g t h of the program A Program Development F a c i l i t y 32 segment exceed the s i x t e e n l i n e s a l l o t t e d t c i t , the l a s t l i n e w i l l c o n t a i n an e l l i p s i s at i t s extreme r i g h t end. The second p o r t i o n of the d i s p l a y s c r e e n , which i s r e f e r r e d to as the entry area, takes up the e i g h t e e n t h through twenty-t h i r d l i n e s of the screen and i s separated from the d i s p l a y area by a row of dashes at the seventeenth l i n e . The entry area c o n t a i n s the previous f i v e l i n e s of i n p u t typed at the system as w e l l as an empty l i n e on which new input i s entered. As new i input i s typed, p r e v i o u s l i n e s disappear i n a f i r s t i n - f i r s t out f a s h i o n . The f i n a l area used by the system i s the twenty-fourth and l a s t l i n e of the screen. While t h i s l i n e i s blank i n the course of normal o p e r a t i o n , i t i s used to d i s p l a y e r r o r messages and requests f o r i n f o r m a t i o n . 2.3.2. E r r o r Hand lino. Throughout the system, whenever an erroneous piece of i n p u t data i s d e t e c t e d , the system w i l l d i s p l a y an a p p r o p r i a t e message on the e r r o r message l i n e and do a r e a l - t i m e wait of approximately f i v e seconds. Should the user cause an i n t e r r u p t by p r e s s i n g an a p p r o p r i a t e key on the 3270 keyboard, i t w i l l be t r e a t e d by MTS as a standard a t t e n t i o n i n t e r r u p t and c o n t r o l w i l l r e t u r n to the MTS command processor. One can, cf course, r e - e n t e r the system v i a a RESTART command. Should the system he l e f t u n i n t e r r u p t e d , however, the e r r o r message l i n e w i l l be removed from the screen and the o f f e n d i n g p i e c e of input and any f o l l o w i n g c h a r a c t e r s w i l l be removed from the i n p u t a r e a . At A Program Development F a c i l i t y 33 t h i s p o i n t , the system w i l l be i n the state at which i t was before the offending piece of t e x t was entered, and the user may continue from t h a t p o i n t . 2.3.3. Entering Text The method of en t e r i n g t e x t w i t h i n the system i s g u i t e s i m i l a r to th a t of en t e r i n g t e x t on a 3270 c o n t r o l l e d by the normal MTS Device S e r v i c e Boutine. The screen i s divided i n t o twenty-four f i e l d s which correspond to the twenty-four l i n e s of the screen. When the program wishes to read some input from the user, the cursor i s p o s i t i o n e d at the bottom of the entry area and the program waits f o r an i n t e r r u p t . At t h i s p o i n t , the user may simply type t e x t onto the screen or he may choose to move the cursor to some other l i n e and modify and enter the t e x t which i t contains by pressing the ENTER key. L i k e the MTS Device S e r v i c e Routine, the system w i l l accept the f i r s t l i n e of input from the screen which has been modified or, should no l i n e be modified, the l i n e under which the cursor i s p o s i t i o n e d when the ENTER key i s pressed. The system w i l l not accept input generated by moving the cursor to the d i v i d i n g l i n e between the d i s p l a y and entry areas or to the e r r o r message l i n e and pressi n g the ENTER key. In t h i s case, the cursor i s returned to the blank l i n e at the end of the entry area and the read i s re-attempted . I f during a read the user presses the CLEAR key, the screen i s returned to i t s s t a t e before the read was s t a r t e d , the cursor i s returned to i t s o r i g i n a l p o s i t i o n at the end of the entry A Program Development F a c i l i t y 34 area, and the read i s re-attempted. Should the user press the CNCL key during a read, the system w i l l abort any a c t i o n s p e c i f i e d by the current command, p r i n t the message "COMMAND CANCELLED" i n the manner described above, and retu r n t c the top l e v e l of the command processor. Pressing any of the other i n t e r r u p t - c a u s i n g keys (such as the program f u n c t i o n keys) during a read operation w i l l leave the screen unaltered but w i l l r e t u r n the cursor t o i t s p o s i t i o n at the end of the entry area. 2.4. The Command Language The system uses a ra t h e r simple command s t r u c t u r e which a l l o w s the user to i n s e r t , examine and a l t e r program t e x t . The syntax of the command language i s such that l i n e boundaries have no e f f e c t on the s t r i n g of commands being entered, and thus more than one command may be entered on a s i n g l e l i n e . The user should note, however, that a l i n e i s not processed by the system u n t i l the ENTER key i s pressed. A l l named commands may be abbreviated to t h e i r f i r s t c h a r a c t e r s , but a r b i t r a r i l y long words s t a r t i n g with these l e t t e r s are accepted by the command analyzer. Since both commands and program te x t are scanned by the same mechanism, command words must f i t the syntax of <IDEHTIFIER> described e a r l i e r . S i m i l a r l y , r e s t r i c t i o n s on the l o c a t i o n of blanks and the syntax of other e n t r i e s such as numbers f o l l o w those of the language. As mentioned e a r l i e r , the system maintains a pointer i n t o the program tr e e (which i s i n i t i a l l y n u l l since no program t e x t has been entered) and w i l l f i l l the d i s p l a y area with program A Program Development F a c i l i t y 35 t e x t s t a r t i n g from t h i s p o s i t i o n . In a d d i t i o n , t h i s prcgram t r e e p o i n t e r serves as-an o r i g i n f o r any changes made tc the program i t s e l f . For d e t a i l e d examples of the use of these commands and the system responses to them, the reader i s r e f e r r e d t o the sample runs included as an appendix. 2.4.1. The Down Command This command, which i s made up of a s i n g l e <NUMEER> n, i n d i c a t e s that the program t r e e p o i n t e r i s to be moved tc the nth subtree r e l a t i v e to the current program po i n t e r . Thus, should the program po i n t e r point to the t e x t fragment "IF A THEN 3 ELSE 5 F I " the command "2" would change the program pointer to point to the expression sequence co n t a i n i n g the number 3 as i t s f i r s t and only entry while the command "4" would cause an e r r o r . 2.4.2. The U£ Command This command, which c o n s i s t s of a "|" followed by an i n t e g e r n, moves the program tree pointer up n l e v e l s i n the program t r e e . Thus, when the user types a s i n g l e number at the system ( i n d i c a t i n g a down command), typing "|1" w i l l reverse the e f f e c t of the down command and retur n the program tr e e pointer to i t s o r i g i n a l p o s i t i o n . Should the i n t e g e r s p e c i f i e d be l a r g e r than the number of l e v e l s down the current procedure segment that the prcgram tree p o i n t e r has been moved, the system returns the pointer to the top of the current segment without complaint. A Program Development F a c i l i t y 36 2.4.3. The PRINT Commana •—. T h i s command, which c o n s i s t s of the command word PRINT f o l l o w e d by a <NUMBER> n, w i l l cause the system to d i s p l a y t e x t beginning at the program tree pointer to a depth of n, r a t h e r than to the d e f a u l t system depth of s i x l e v e l s . T h i s command i s u s e f u l should the user wish to examine the deeper s t r u c t u r e cf a piece of program t e x t . 2.4.4. The EDIT Command The EDIT command a l l o w s the user to change the system's a t t e n t i o n from one COMPILATION UNIT> to another. I t c o n s i s t s of the command word EDIT f o l l o w e d by the name of the COMPILATION UNIT> which i s to be e d i t e d . The command causes the system to set i t s program t r e e p o i n t e r to the t o p - l e v e l of the named COMPILATION UNIT>, and hence t o d i s p l a y t e x t s t a r t i n g at t h a t point of the procedure. N a t u r a l l y , the system w i l l complain i f the named u n i t has not been d e f i n e d , 2.4.5. The HARDCOPY Command This command, which c o n s i s t s of the command word HARDCOPY, causes a l i s t i n g of the procedure t e x t s t a r t i n g a t the c u r r e n t program p o i n t e r to be produced on the system l i s t i n g f i l e (the MTS s c r a t c h f i l e "-LIST"). There i s no l i m i t on the depth of the l i s t i n g produced. A Program Development F a c i l i t y 37 2.4.6. The INSERT Command The INSERT command c o n s i s t s of the command word INSERT followed by a piece of program t e x t forming a s y n t a c t i c a l l y v a l i d COMPILATION ONIT> followed by a period. This text i s then attached to i t s procedure name, and the program tr e e p o i n t e r i s set to the COMPILATION UNIT> node of t h i s procedure. Since the system must have some way of determining which of the COMPILATION UNIT>s s u p p l i e d to i t i s the t o p - l e v e l procedure, i t simply takes the f i r s t u n i t supplied to i t . Thus, the user must be c a r e f u l to i n s e r t h i s t o p - l e v e l procedure before i n s e r t i n g any subsequent ones. The order of the subsequent procedures i s immaterial s i n c e l i n k s from higher l e v e l s are made v i a the d e c l a r a t i o n s of lower l e v e l procedures. In order to e l i m i n a t e confusion f o r both the system and the user, a procedure name must be unique w i t h i n a program and thus the system w i l l complain should a procedure be m u l t i p l y d e f i n e d , even though i t s d e f i n i t i o n i s c o r r e c t i n the sense of A l g o l scope r u l e s . Since procedures may be r e l a t i v e l y l o ng, the user may f i n d i t u s e f u l to enter h i s programs with "stubs", or simple expressions which w i l l l a t e r be expanded i n t o more complex ones. T h i s s t r a t e g y may prove t o be of use tc those who f i n d d i f f i c u l t y with the curren t e r r o r processing scheme since i t enables the user to enter t e x t i n r e l a t i v e l y s m a ll chunks. At the same time, however, experience with the system has shown that procedures of a reasonable s i z e can be entered guite conveniently i n s i n g l e INSERT commands. A Program Development F a c i l i t y 38 2.4.7. The REPLACE Command The REPLACE command i s the command used to a l t e r program t e x t . I t c o n s i s t s of the command word REPLACE fo l l o w e d by a % s i g n f o l l o w e d by a non-empty sequence of numbers followed by a second % s i g n f o l l o w e d by the pi e c e of program t e x t to be s u b s t i t u t e d f o l l o w e d by a p e r i o d . The sequence cf numbers between the % s i g n s l o c a t e s the p o r t i o n of the program t r e e which i s to be r e p l a c e d r e l a t i v e to the c u r r e n t prcgram tr e e p o i n t e r . The program t e x t i s then handed to the parser which attempts to c r e a t e a p o r t i o n of t r e e which can be used to r e p l a c e the i n d i c a t e d p o r t i o n . N a t u r a l l y , the pars e r w i l l r e s t r i c t the type o f replacement which can be done to prcgram elements which are v a l i d i n a p a r t i c u l a r context, e.g., a DECLARATION SEQUENCE> may only be r e p l a c e d by another DECLARATION SEQuENCE>. An exc e p t i o n to t h i s r u l e occurs i n the case of l i s t s and sequences of program elements, i n which case a p a r t i c u l a r element of a l i s t or sequence may be r e p l a c e d by an e n t i r e l i s t or sequence which i s s p l i c e d i n t o the e x i s t i n g sequence. Thus, i n the EXPRESSION SEOUENCE> "A, E + 81,C,E" one could use the command "REPLACE %3% I,J,K." to prcduce the EXPRESSION SEQUENCE> "A ,B + 81,I,J,K,D". Within p i e c e s of program t e x t , the user i s a l s o allowed to use "subtree d e n o t a t i o n s " which c o n s i s t of a % s i g n followed by a p o s s i b l y empty l i s t of <NUMBER>s f o l l o w e d by a second % s i g n . T h i s denotation r e f e r s t o the p o r t i o n of the parse tr e e named by the sequence of i n t e g e r s r e l a t i v e to the c u r r e n t parse t r e e p o i n t e r . The pars e r w i l l simply copy that t r e e p o r t i o n i n t o the A Program Development F a c i l i t y 39 t r e e which i t i s c r e a t i n g ( p r o v i d i n g , of course, i t i s s y n t a c t i c a l l y v a l i d ) and thus allow the user to manipulate program t e x t i n more complex f a s h i o n s . As an example, when e d i t i n g the <EXPRESSION> "A (81) := B * C" the command "REPLACE %3% %3% + D." w i l l generate the tre e "A (81) := E * C + D". 2.4.8. The SAVE Command Thi s command allows the user t o checkpoint h i s program on an MTS s e q u e n t i a l f i l e . The command word SAVE fo l l o w e d by an <IDENTIFIER> which i s the name of an MTS s e q u e n t i a l f i l e w i l l cause the system to empty that f i l e and write the contents of the system workspace i n t o i t . The system w i l l make a p p r o p r i a t e complaints should the f i l e be non-existent or of the i n c o r r e c t type. The SAVE command a f f e c t s n e i t h e r the d i s p l a y ncr the c u r r e n t program t r e e . 2.4 . 9 . The GET Command The o p p o s i t e o f the SAVE command, the GET ccmmand allows the user to r e s t o r e the system to a p r e v i o u s l y s p e c i f i e d s t a t e . I t c o n s i s t s of the command word GET f o l l o w e d by an i d e n t i f i e r naming an MTS f i l e used i n a pre v i o u s SAVE command. The system checks the e x i s t e n c e and type of the f i l e as well as a p a r t i c u l a r key attached to the f i l e by the SAVE command. If any of these checks suggest i n c o n s i s t e n c i e s , the command i s aborted with a simple e r r o r message. A f t e r s u c c e s s f u l l y r e a d i n g a c o n t r o l r e c o r d from the f i l e , the program w i l l d i s p l a y the date on which the workspace" was saved on the e r r o r message l i n e . A Program Development F a c i l i t y 40 Since the GET command operates upon s e n s i t i v e data s t r u c t u r e s w i t h i n the system, any i n c o n s i s t e n c y i n the checkpoint f i l e c ould have u n p r e d i c t a b l e r e s u l t s . Thus, i f the system d e t e c t s any e r r o r s i n the course of reading the f i l e , an a p p r o p r i a t e message i s p r i n t e d and system execution t e r m i n a t e s . F o l l o w i n g a s u c c e s s f u l GET command, the system i s returned to the s t a t e preceding the SAVE command which created the checkpoint f i l e , except t h a t the program tr e e p o i n t e r i s s e t to the COMPILATION 0NIT> node of the t o p - l e v e l procedure. 2.4.10. The COMPILE Command Thi s command, which c o n s i s t s of the command COMPILE, i n s t r u c t s the system to do any necessary c o m p i l a t i o n s r e g u i r e d by e r r o r s i n previous c o m p i l a t i o n s or by e d i t i n g changes made by the user. On the f i r s t use of t h i s command f o r a p a r t i c u l a r program, the system w i l l prompt the user f o r the name of an MTS l i n e f i l e i n t o which the o b j e c t module i s to be generated. T h i s f i l e must be i n i t i a l l y empty. As with SAVE and RESTORE, the compiler w i l l complain a p p r o p r i a t e l y should the f i l e be non-e x i s t e n t or of the i n c o r r e c t type. Since the compiler w i l l save pr e v i o u s c o m p i l a t i o n s of r o u t i n e s which need not be redone, the user must leav e the o b j e c t f i l e s t r i c t l y alone between c o m p i l a t i o n s and allow the system to manage the f i l e by i t s e l f . In the course of c o m p i l a t i o n the system w i l l produce complete l i s t i n g s o f those r o u t i n e s which are compiled along with any semantic e r r o r messages generated and a l i s t i n g of the pseudo-machine code on the MTS s c r a t c h f i l e "-LIST". P r e s e n t l y A Program Development F a c i l i t y 41 the system does not output any e r r o r messages on the t e r m i n a l , even though a b r i e f message g i v i n g a count of e r r o r s detected would be h e l p f u l . The f i n a l item produced by the compiler i s a t r e e - s t r u c t u r e d l i s t i n g of a l l procedures involved i n the program. This l i s t i n g i s u s e f u l as a cross-reference and as an assurance that a l l procedures defined are c o r r e c t l y declared and used. 2.4.11. The MTS Command The command word MTS causes a re t u r n to the MTS command i n t e r p r e t e r . A f t e r t h i s command, the MTS Device Service Routine takes c o n t r o l of the d i s p l a y , and the screen i s refreshed from the MTS c o n v e r s a t i o n a l b u f f e r . Any MTS commands which do not cause unloading of the program may be issued before resuming with a RESTART command which w i l l r e f r e s h the screen i n the standard Eighty-One format. 2.4.12. The QUIT Command The command word O.UIT causes the system to stop execution and r e t u r n to MTS. I t should be used c a u t i o u s l y since there i s no p r o v i s i o n f o r checkpointing the user's workspace a u t o m a t i c a l l y , and hence a program could e a s i l y be l e s t . A Program Development F a c i l i t y 42 2 . 5 . The L o a d e r - I n t e r p r e t e r The l o a d e r - i n t e r p r e t e r p o r t i o n of the system implements the pseudo-machine f o r which the e d i t o r - c o m p i l e r generates code. The i n t e r p r e t e r i s run with MTS l o g i c a l u n i t 0 assigned to the o b j e c t f i l e which r e s u l t s from the c o m p i l a t i o n of a prcgram. The i n t e r p r e t e r w i l l s t e a d f a s t l y r e f u s e to execute a program should the f i l e format be i n c o r r e c t or should the compiler have dete c t e d semantic e r r o r s i n the c o m p i l a t i o n . Once loaded, the program i s i n t e r p r e t e d u n t i l i t reaches completion or a runtime e r r o r i s detected. A runtime e r r o r (such as a s u b s c r i p t out of range) i s accompanied by a backtrace, of a c t i v e procedures c o n t a i n i n g the l o c a t i o n ( i n the standard c o - o r d i n a t e scheme) at which the e r r o r o c c u r r e d as w e l l as the procedure names and l o c a t i o n s from which that procedure was invoked. E r r o r messages generated by the i n t e r p r e t e r are output on MTS l o g i c a l u n i t SERCOM, while the INPUT and OUTPUT pseudo-v a r i a b l e s of the language r e f e r to u n i t s SCARDS and SPRINT r e s p e c t i v e l y . A Program Development F a c i l i t y 43 I I | Part 3 — System D e s c r i p t i o n | I I T h i s s e c t i o n of the document d e s c r i b e s the prototype implementation of the Eighty-One system i n some d e t a i l . The system i s w r i t t e n i n the SDE System Language [ATWO] running under MTS with a s m a l l S/360 assembly language i n t e r f a c e [BRUS] which handles d i r e c t communication and i n t e r r u p t handling f o r the 3270 d i s p l a y . Although t h i s d e s c r i p t i o n assumes some f a m i l i a r i t y with the SUE language, such knowledge i s only r e g u i r e d to understand the more e s o t e r i c d e t a i l s of the implementation. The s i z e of the e n t i r e system (paragraphed SUE l i s t i n g s f o r the e d i t o r - c o m p i l e r p o r t i o n of the system run to 180 pages) prevents t h i s d e s c r i p t i o n from going i n t o a g r e a t d e a l of d e t a i l , but h o p e f u l l y t h i s s e c t i o n w i l l adequately d e s c r i b e the i n t e r n a l s t r u c t u r e of the system as well as some of the more i n t e r e s t i n g data s t r u c t u r e s and a l g o r i t h m s which i t u t i l i z e s . More p r e c i s e d e t a i l s of the important data s t r u c t u r e s used may be obtained from SUE type d e f i n i t i o n s and v a r i a b l e d e c l a r a t i o n s which are i n c l u d e d as an appendix. The i d e n t i f i e r names used i n these p o r t i o n s of code correspond q u i t e c l o s e l y to the terminology used here, and thus l i t t l e e x p l a n a t i o n of the program segments w i l l be g i v e n . A Program Development F a c i l i t y The remainder of t h i s s e c t i o n i s broken i n t o d i s c u s s i o n s of two major areas: the data s t r u c t u r e s of the system and the algorithms which operate upon them. This o r g a n i z a t i o n should provide a c l e a r p i c t u r e of how the system operates even though the obvious i n t e r a c t i o n of these t o p i c s may become apparent. 3.1. Data St r u c t u r e s Since Eighty-One i s intended as a prototype of a more p r a c t i c a l program development f a c i l i t y , a number of s i m p l i f i c a t i o n s were made i n the design of i t s data s t r u c t u r e s . To begin w i t h , no attempt was made to i n t e g r a t e the intermediate t e x t r e p r e s e n t a t i o n with some form of mass storage. Thus, while the system does provide f i l e - b a s e d checkpoint and r e s t o r e f a c i l i t i e s f o r the programs which i t handles, a l l program segments are kept i n v i r t u a l memory during system execution. Although such methods are probably inadequate f o r a production v e r s i o n of the system, the complications i n v o l v e d i n designing a s u i t a b l e d i s c f i l e r e p r e s e n t a t i o n f o r the prcgram tree are not d i r e c t l y r e l a t e d to the goals of the p r o j e c t . Indeed, one could argue that such a system would only f u n c t i o n as a paging system, and hence the s i m p l i f i c a t i o n of l e a v i n g such tasks t o the operating system i s a reasonable one. As a second s i m p l i f i c a t i o n , no attempt was made to l i n k the program t r e e r e p r e s e n t a t i o n to the object code generated i n order to supply the user with source language t e x t causing runtime e r r o r s . While t h i s l i n k a g e could c l e a r l y be put tc good use i n supplying the user with meaningful d i a g n o s t i c s as w e l l as A Program Development F a c i l i t y 45 trace and p r o f i l e i n formation, an execution monitor of t h i s complexity also f a l l s outside the scope of the current p r o j e c t . As a compromise, the Eighty-One system provides source co-o r d i n a t e information i n the Dewey decimal format with a l l runtime messages. 3.1.1. The Program Tree The main re p r e s e n t a t i o n of program t e x t w i t h i n the system, and hence the main data s t r u c t u r e required by i t , i s the program tre e which represents a parse according to the language grammar. In the terminology of Ahc and Ullman [ASU], t h e r e p r e s e n t a t i o n i s t h a t of a syntax t r e e r a t h e r than that of a d e r i v a t i o n t r e e . This d i f f e r e n c e i s rather minor, however, and only i m p l i e s that meaningless nonterminals have been removed from the t r e e . Since each node of the parse tree contains a type f i e l d which s p e c i f i e s the s y n t a c t i c u n i t represented, the nonterminals can be e a s i l y reconstructed i n order to produce a l i s t i n g of the o r i g i n a l source t e x t . Construction of t h i s type cf t r e e i s s t r a i g h t f o r w a r d from the output of the LB parse of the language. While the e d i t o r t r e a t s c e r t a i n sequences and l i s t s of items as though they have a l i n e a r s t r u c t u r e , the i n t e r n a l r e p r e s e n t a t i o n of these l i s t s f o l l o w s the syntax tree r e p r e s e n t a t i o n of a s e r i e s of nodes l i n k e d by p o i n t e r s . One of the major reasons f o r t h i s r e p r e s e n t a t i o n i s the s t a t i c nature of SUE record d e c l a r a t i o n s which makes i t r e l a t i v e l y d i f f i c u l t to d e c l a r e a record c o n t a i n i n g an array whose bounds cannot be determined at compile time. Such a s t r u c t u r e would perhaps be A Program Development F a c i l i t y 46 p r e f e r a b l e i n a production system since i t would make more e f f i c i e n t use of storage. In order to f a c i l i t a t e moving about the parse t r e e , each node contains a backward l i n k which j o i n s that node to i t s immediate ancestor. As described e a r l i e r , the d e f i n i t i o n of l i s t and seguence s t r u c t u r e s w i t h i n the e d i t o r i s d i f f e r e n t from t h e i r d e s c r i p t i o n i n the grammar. Consequently, each member of such a l i s t i s l i n k e d to the ancestor of the f i r s t element of the l i s t r a ther than to i t s predecessor i n the l i s t . These l i n k s make the implementation of the Up command a matter of f o l l o w i n g the req u i r e d number of backward l i n k s , and hence moving up through a l i s t s t r u c t u r e has the expected e f f e c t . The backward l i n k s also serve a purpose i n deciding how an e d i t i n g change has a l t e r e d the need f o r recompiling various portions of the parse tree. Since the Eighty-One language f o l l o w s the standard p r a c t i c e of A l g o l - l i k e languages i n a l l o w i n g comments between any two tokens of the language, the implementation should handle comments i n a way which preserves t h e i r p o s i t i o n i n the source t e x t . The only obvious way of accomplishing t h i s o b j e c t i v e i s to attach a l i n k e d l i s t of comments which f o l l o w a p a r t i c u l a r token to the p o s i t i o n which that token occupies i n the parse t r e e . Figure 1 should help to c l a r i f y the s t r u c t u r e of a t y p i c a l piece of program t r e e . A Program Development F a c i l i t y 47 Program Text: IF A THEN B 0 ELSE 0 FI •= c. • Program Tree: IF I IF~T • |node) I A V f ["ID T .~T~ T~ID } |node| | • |comment| THEN T~ELSE T~ J FI ] |comment| • |comment| • |comment| • |comment| r ^ A | A _ _ J | | L _ > n A « i n symbol t a b l e —• I r i r I V I fsT L I S T ! I ; T /] J node | | • |comment|/ | I J L (. L I J |A I - — J i 1 — r — T 1 1 S T L IST | • | i | node I I • I L _ I J . | I I A comment) • | | | I r T — r ~ i T 1 -, | | NUMBER | • | 0 | NUM EER | | | | node | | |comment| I I L L I JJ 1 I v I i 1—H—i (FORMULA| • | | node | | 1 S T LIST| | node | /I I OP | |comment| .j j _| j j V I | ID | • | | ID ] |node| | • |comment| I I I | L J I L_> «B« i n symbol table I • I •+- J ! A I I I I V 1 — • |comment|/ -+-J •L— t A - J I r I V I [NUMBEBT"* T OTNUMEER "J I node | | |comment| L I L L I | ID | • | | ID | |node| 1*1commen 11 I L_> « c " i n symbol t a b l e Figure 1 — A Program Tree Segment 3.1.2. Program Tree A l l o c a t i o n A Program Development F a c i l i t y 48 The a l l o c a t i o n of nodes f o r the program t r e e i s handled by m a i n t a i n i n g a l i s t of f r e e nodes l i n k e d through t h e i r backward l i n k f i e l d s . A l l o c a t i o n of a node i s accomplished by removing the f i r s t node from the f r e e l i s t and moving the f r e e l i s t p o i n t e r to the next a v a i l a b l e element. S i m i l a r l y , a node no l o n g e r i n use i s r e t u r n e d to a v a i l a b l e storage by a t t a c h i n g i t t o the head of the f r e e l i s t . The space f o r the array of nodes of the i n i t i a l f r e e l i s t i s a l l o c a t e d by means of the MTS system s u b r o u t i n e GFTSPACE. Should t h i s area overflow, i . e . , should the f r e e l i s t become empty, a new, l a r g e r area i s a l l o c a t e d and the c u r r e n t a c t i v e p o r t i o n i s copied i n t o i t . A f t e r t h i s , the o l d area i s f r e e d and the new area becomes a c t i v e . T h i s s t r a t e g y , which i s necessary because p o i n t e r s are represented as i n d i c e s i n t o a contiguous a r r a y , a l l o w s the system's space requirements to grow with those of the program t r e e which i t manages. Although t h i s f r e e l i s t s t r u c t u r e does e l i m i n a t e the need f o r garbage c o l l e c t i o n , i t r e q u i r e s some c a u t i o n tc ensure that nodes are not " l o s t " by the system. In t h i s s t r u c t u r e , any parse node with no p o i n t e r r e f e r e n c i n g i t i s garbage which cannot be r e c l a i m e d . The problems of m a i n t a i n i n g p o i n t e r s to a l l nodes whether they be on the f r e e l i s t cr i n some p o r t i o n of parse t r e e are e v i d e n t i n the replacement and e r r o r recovery a l g o r i t h m s which w i l l be d e s c r i b e d l a t e r . A Program Development F a c i l i t y 49 3. 1.3. S t r i n g D e s c r i p t o r Management S t r i n g d e s c r i p t o r s w i t h i n the system break down i n t o three types: d e s c r i p t o r s of s t r i n g s i n source t e x t , d e s c r i p t o r s of comments i n source t e x t , and d e s c r i p t o r s of i d e n t i f i e r s i n source t e x t . A l l of these character s t r i n g s are represented by p o i n t e r s i n t o a s i n g l e s t r i n g area which i s an array of characters a l l o c a t e d through MTS. - Both language s t r i n g d e s c r i p t o r s and comment s t r i n g d e s c r i p t o r s are a l l o c a t e d v i a records con t a i n i n g the length of the s t r i n g and a pointer i n t o the s t r i n g area. In a d d i t i o n , these records contain f l a g s used i n garbage c o l l e c t i o n which i n d i c a t e whether cr net they are c u r r e n t l y i n use. Both types of records are managed v i a free l i s t s s i m i l a r to those used f o r parse nodes. I d e n t i f i e r d e s c r i p t o r s , on the other hand, are represented by e n t r i e s i n a hash t a b l e which give the length of the i d e n t i f i e r as well as a p o i n t e r to i t s f i r s t c h aracter i n the s t r i n g area. E n t r i e s i n t h i s hash t a b l e a l s o contain f l a g s i n d i c a t i n g whether or net a p a r t i c u l a r d e s c r i p t o r i s a c t i v e . Like parse nodes, both program character s t r i n g s and program comment nodes must be e x p l i c i t l y f r e e d . No e f f o r t i s made to f r e e the characters t o which these nodes point when a node i s f r e e d , however, due to the d i f f i c u l t i e s of space fragmentation which would occur. When the current array of c h a r a c t e r s i s exhausted, a d u p l i c a t e of the array i s a l l o c a t e d from the operating system and the arrays cf program character s t r i n g s , comments, and symbols are toured to copy a l l a c t i v e s t r i n g s i n t o the new area. This procedure w i l l compact a c t i v e A Program Development F a c i l i t y 50 s t r i n g s i n t o the lower p o r t i o n of the new area l e a v i n g the upper parts of the area f o r subsequent a l l o c a t i o n . In a d d i t i o n , the s i z e of the s t r i n g area can be increased f o r subsequent a l l o c a t i o n s . I t should be noted that the hash table i s maintained l i k e a LISP OBLIST i n that even i f a l l references to an i d e n t i f i e r should disappear, that i d e n t i f i e r w i l l remain permanently i n the hash t a b l e . In the normal course of program e d i t i n g t h i s i s probably a reasonable s t r a t e g y , but i t could lead to an unreasonable amount of "symbol t a b l e c l u t t e r " r e s u l t i n g from unused i d e n t i f i e r s a f t e r an extended period of maintaining a large program. 3. 1.4. Display Screen Structures In order to manage the 3270 d i s p l a y , the program keeps a s t r a i g h t f o r w a r d r e p r e s e n t a t i o n of the screen contents i n i n t e r n a l b u f f e r s . The d i s p l a y area i s kept as an array of l i n e s c l o s e l y r e l a t e d to the format i n which they appear cn the screen. In order to provide s c r o l l i n g of the input l i n e s , the entry area i s represented by means of an array of the l i n e s i n the area and a p a i r of p o i n t e r s forming a c i r c u l a r b u f fer. As new l i n e s are i n p u t , the end-of-buffer pointer i s advanced, p o s s i b l y o v e r w r i t i n g the f i r s t l i n e of the area and hence removing i t from the screen. The f i n a l d i s p l a y f i e l d of the screen, the e r r o r message l i n e , i s kept as a s i n g l e l i n e w i t h i n the system. This format allows the system to r e f r e s h the screen q u i c k l y at any time with p r a c t i c a l l y no e f f o r t . i A Program Development F a c i l i t y 51 3. 1.5. Compiler S t r u c t u r e s While the program tree provides the system with a complete s y n t a c t i c d e s c r i p t i o n of the source program, other semantic in f o r m a t i o n i s not represented. One of the most important pieces of information l e f t out of the tree i s the connection between the a p p l i e d occurrence of an i d e n t i f i e r and i t s d e f i n i t i o n . Since such connections are r e l a t i v e l y d i f f i c u l t to maintain within the changing environment of a program undergoing ed i t i ng changes, t h e i r r e s o l u t i o n i s l e f t to the compilation phase. Thus, while the e d i t o r w i l l not allow the user to create a program which i s s y n t a c t i c a l l y i n c o r r e c t , i t does not attempt to detect or prevent semantic e r r o r s such as undefined i d e n t i f i e r s or v i o l a t i o n s of type r u l e s at the time program t e x t i s entered or a l t e r e d . Before d i s c u s s i n g the s t r u c t u r e s required ty the compiler to maintain c e r t a i n pieces of semantic information, i t would be w e l l to examine some of the semantic requirements and r e s t r i c t i o n s of the language i t s e l f . Since compilations of i n d i v i d u a l blocks of the language must be separate, there i s a d e f i n i t e d i s t i n c t i o n between g l o b a l v a r i a b l e s declared i n the DATA segments of co m p i l a t i o n u n i t s and l o c a l v a r i a b l e s declared i n the d e c l a r a t i o n sequences of blocks* Since access to l o c a l v a r i a b l e s i s l i m i t e d to the procedures i n which they occur, t h e i r e x i s t e n c e i s of no concern to the comp i l a t i o n of procedures at lower l e v e l s . At the same time, however, access to g l o b a l v a r i a b l e s must be maintained f o r a l l procedures compiled at lower l e v e l s . This d i s t i n c t i o n between l o c a l and A Program Development F a c i l i t y 52 g l o b a l data i s r e f l e c t e d throughout the . s t r u c t u r e of the compiler. The problem of a s s o c i a t i n g i d e n t i f i e r s with t h e i r d e f i n i t i o n s i s solved i n a s t r a i g h t f o r w a r d manner by maintaining during compilation a stack of symbol t a b l e e n t r i e s r e f l e c t i n g the current d e f i n i t i o n s of various a c c e s s i b l e i d e n t i f i e r s . The i n d i c e s i n t o the symbol t a b l e which represent i d e n t i f i e r s can als o be used as i n d i c e s i n t o a ta b l e of p o i n t e r s i n t o the symbol stack termed the symbol t a b l e l i n k area. Thus, at any time, the semantic information associated with an i d e n t i f i e r may te obtained by accessing the data i n the symbol stack entry l i n k e d to the i d e n t i f i e r index, as i s shown i n Figure 2. The symbol stack i t s e l f as w e l l as the symbol t a b l e l i n k area must be changed as com p i l a t i o n proceeds to r e f l e c t the current l e v e l of the block s t r u c t u r e of the program being compiled. This s t r u c t u r e i s maintained by stacks c o n t a i n i n g p o i n t e r s to g l o b a l and l o c a l contexts on the symbol stack which are used tc provide a binding scheme s i m i l a r t c the "shallow b i n d i n g " of many LISP i n t e r p r e t e r s [B£W]. Two a d d i t i o n a l stacks are req u i r e d by the compiler to handle DO-OD and EXIT WITH expressions. The f i r s t cf these s t a c k s , termed the do stack , records the type of the most c l o s e l y e n c l o s i n g DO expression as w e l l as a pointer i n t o the second of these s t a c k s , the e x i t stack. On entry to a CO-OD expression, the compiler pushes the current e x i t stack pointer onto the do stack along with an undefined type entry. Upon reaching an EXIT WITH expression w i t h i n the DO-OD expression. A Program Development F a c i l i t y 53 I d e n t i f i e r r - > Hash Function -1< •+ n -4 I —I-L > Semantic | • I i n f o r m a t i o n ! | y L -L -I i T J I Binding -» l i n k s Previous symbol stack entry Symbol t a b l e l i n k area Symbol stack Figure 2 — The Symbol Stack the type entry at the top of the do stack i s checked. I f that entry i s undefined, the type of the EXIT WITH expression r e p l a c e s i t . I f , on the other hand, the do stack entry has already been defined, the type of the EXIT WITH expression must match that type or an e r r o r message i s generated. F i n a l l y , an entry c o n t a i n i n g the l o c a t i o n of the branch address of the EXIT i n s t r u c t i o n i s pushed onto the e x i t stack. When the compiler reaches the end of the DO-OD expression, i t need only check the type at the top of the do stack to ensure that at l e a s t one v a l i d EXIT WITH has occurred w i t h i n the body of that expression and f i x up a l l branch l o c a t i o n s between the current e x i t stack p o i n t e r and the e x i t stack p o i n t e r at the top cf the do stack to point to the end of the DO-OD code j u s t compiled. While the above d e s c r i p t i o n covers most of the major data A Program Development F a c i l i t y 54 s t r u c t u r e s used by the compiler, the SUE runtime stack i t s e l f forms an important part of the compiler data s t r u c t u r e . Since the compiler i s implemented as a r e c u r s i v e procedure, many l o c a l v a r i a b l e s (such as p o i n t e r s to branch i n s t r u c t i o n s within IF expressions) are declared as l o c a l v a r i a b l e s w i t h i n the SUE procedures. Thus, the runtime stack i s made tc provide a number of separate stacks w i t h i n the compiler. 3.1.6. Checkpoint F i l e S t ructure The checkpoint-restore feature of the system i s implemented using an MTS s e q u e n t i a l f i l e . The f i r s t record w r i t t e n t c t h i s f i l e contains the values of c e r t a i n g l o b a l v a r i a b l e s such as the s i z e of various arrays a l l o c a t e d i n storage obtained d i r e c t l y from the operating system. This record a l s o contains a 32 b i t " i d e n t i f i c a t i o n mark" which helps the restore module to a u t h e n t i c a t e a f i l e as one a c t u a l l y generated by the system. In an environment which allows the user to construct or a l t e r f i l e s o u t s i d e the system, however, i t i s impossible to ensure that a checkpoint f i l e was o r i g i n a l l y generated by the system and has not s i n c e been tampered with. Since a l l the record handling w i t h i n the system i s done v i a i n d i c e s i n t o a r r a y s , there i s no problem with the r e l o c a t i o n of p o i n t e r s , and the second through s i x t h records of the checkpoint f i l e contain arrays such as the symbol t a b l e , the language s t r i n g d e s c r i p t o r s , the language comment d e s c r i p t o r s and the c h a r a c t e r s of the s t r i n g s i n the system. Beginning with the seventh record of the f i l e , the array of parse nodes a l l o c a t e d A Program Development F a c i l i t y 55 from system storage i s saved. Should the length of t h i s array exceed the length of an MTS s e q u e n t i a l f i l e r e c o r d, the a r r a y may be d i v i d e d over a number of l i n e s i n the f i l e . This s t r u c t u r e s u p p l i e s a l l the information necessary tc save the e n t i r e s t a t e of the system. 3 . 1 . 7 . Recompilation Table Structure A c e r t a i n amount of data s t r u c t u r e i s required by the system i n order to manage information concerning which procedures w i t h i n a program are i n need of r e c o m p i l a t i o n at a p a r t i c u l a r time. As described e a r l i e r , the Eighty-One language semantics r e g u i r e t h a t each procedure name w i t h i n a program he unique, thus e l i m i n a t i n g the need f o r scope information a s s o c i a t e d with procedure d e f i n i t i o n s . A t a b l e running p a r a l l e l to the hash t a b l e termed the r e c o m p i l a t i o n t a b l e i s used to s t o r e a l i n k to the parse tree corresponding to the t o p - l e v e l node of a procedure d e f i n i t i o n , thus al l o w i n g the EDIT command to f i n d procedure code. In a d d i t i o n , t h i s array contains a f l a g i n d i c a t i n g whether or not code has been generated f o r the corresponding procedure. The f i n a l part of the record i s a case on a number of p o s s i b l e c o n d i t i o n s caused by e d i t i n g changes to the program or by previous compilations. In the case of a c o r r e c t l y compiled procedure, t h i s area contains l i n k s tc the f a t h e r , son and brother of the procedure i n the hierarchy. These l i n k s are used by the e d i t o r to f i n d u n i t s which must be marked as r e q u i r i n g r e c o m p i l a t i o n at a l a t e r date, as w e l l as ty the compiler c o n t r o l procedures. The algorithms used by the e d i t o r f o r t h i s purpose as w e l l as those used by the compiler to A Program Development F a c i l i t y 56 analyze t h i s information w i l l be described i n more d e t a i l l a t e r i n the chapter. 3.1.8. Object F i l e S t r u c t u r e L i k e the rec o m p i l a t i o n t a b l e , the object f i l e o r g a n i z a t i o n makes use of the f a c t that each procedure must correspond to a unique symbol t a b l e index. Since various procedures wit h i n a program may need to be recompiled, t h i s object f i l e i s based on the random access s t r u c t u r e s u p p l i e d by the MTS l i n e f i l e . L i k e the checkpoint f i l e , the object f i l e contains a record g i v i n g c e r t a i n g l o b a l information about the program. Subseguent i n t e g r a l l i n e numbers corresponding to the i n d i c e s of procedures defined i n the language contain a header record g i v i n g the s i z e of the procedure code. Should t h i s l i n e be numbered n, l i n e n.001 w i l l contain the name of tha t procedure i n character form f o r use by the d i a g n o s t i c r o u t i n e s w i t h i n the i n t e r p r e t e r , while a number of l i n e s beginning at l i n e n.002 w i l l c o n t ain the code f o r the procedure. Since the code generated by the compiler i s r e l o c a t a b l e , there i s no need to store any r e l o c a t i o n i n f o r m a t i o n i n the object f i l e . 3.1.9. The S t r u c t u r e of the I n t e r p r e t e r The i n t e r p r e t e r f o r the Eighty-One machine i s e s s e n t i a l l y a s t a c k - o r i e n t e d s i n g l e address machine t a i l o r e d to the needs of the Eighty-One language. Since the CHARACTER data type of the language r e q u i r e s garbage c o l l e c t i o n , the .machine has two main s t a c k s , an i n t e g e r stack which contains a l l values of type A Program Development F a c i l i t y 57 INTEGER as w e l l as a l l array d e s c r i p t o r s and a s t r i n g stack which contains a l l values c f type CHARACTER. In a d d i t i o n to these data s t a c k s , there are a number of other stacks and d i s p l a y s which contain c o n t r o l information such as stack p o i n t e r s and program counters. Since the Eighty-One language i s s t r o n g l y typed, a l l type checking i s done at compile time, thus e l i m i n a t i n g the need f o r dynamic type information. 3. 1.9. 1. Data Addressing Structure A data address f o r the machine i s made up of four f i e l d s : a type f i e l d , an access f i e l d , a d i s p l a y index f i e l d and an o f f s e t f i e l d . The type f i e l d of the address, which takes up a s i n g l e b i t , i n d i c a t e s whether the address r e f e r s t c the intege r stack or the s t r i n g stack. The access f i e l d , which a l s o occupies a s i n g l e b i t , i n d i c a t e s whether the v a r i a b l e i s g l o b a l cr l o c a l , t hat i s whether i t i s declared i n the data segment of a procedure or declared w i t h i n a block. The meaning of the s i x -b i t d i s p l a y index f i e l d depends upon the value of the access f i e l d as w e l l as on two c o n t r o l stacks w i t h i n the machine. I f the access f i e l d i s g l o b a l , the value of the d i s p l a y f i e l d forms an index i n t o a g l o b a l d i s p l a y which contains an entry f o r each s t a t i c l e v e l of procedure c a l l . Among other t h i n g s , the g l o b a l d i s p l a y contains a stack frame base which i s used as the base f o r the address computation. I f , on the other hand, the access f i e l d i s l o c a l , the value of the d i s p l a y index f i e l d i s added to the l o c a l stack p o i n t e r f o r the cu r r e n t procedure i n v o c a t i o n . This provides an index i n t o the l o c a l stack which contains a base p o i n t i n g i n t o the data stack s e l e c t e d by the type b i t . The A Program Development F a c i l i t y 58 f i n a l f i e l d , the e i g h t - b i t o f f s e t f i e l d , gives a displacement which i s added to the stack frame base c a l c u l a t e d from the f i r s t three f i e l d s to give the a c t u a l stack l o c a t i o n required. Figures 3 and 4 should help to e x p l a i n these addressing s t r u c t u r e s . 3 . 1 . 9 . 2 . Array, D e s c r i c t o r Structure Since the Eighty-One language supports arrays with bounds which can be c a l c u l a t e d at run time, some form of d e s c r i p t o r mechanism i s necessary t o manage these a r r a y s . This mechanism operates by p l a c i n g on the i n t e g e r stack a s e r i e s of e n t r i e s g i v i n g the number of bounds of the array, the stack address a t which the f i r s t of the array members i s placed, and a s e r i e s of i n t e g e r s g i v i n g the bound values. Since the number of bounds of a p a r t i c u l a r array i s known a t compile time, the s i z e of these d e s c r i p t o r s as w e l l as t h e i r stack l o c a t i o n s can be determined by the compiler and described by the standard data addressing scheme. Array storage i s a l l o c a t e d by pushing the appropriate stack the required amount when the array d e c l a r a t i o n i s processed. Thus, array data i s stored above the d i r e c t l y addressable p o r t i o n of the stack frame. 3 . 1 . 9 . 3 . Program Addressing Scheme A program address w i t h i n the Eighty-One machine i s an o f f s e t from i t s procedure base. This s t r u c t u r e takes advantage of the f a c t that any branches w i t h i n a code segment w i l l be to other p o r t i o n s of t h a t same segment. Thus, each procedure has A Program Development F a c i l i t y 59 r—T—T 1—r J S 1 1 1 * 1 I L H - r - L T L T J I | | "--offset b i t s | | •-—global d i s p l a y b i t s I «-_access b i t (global) •—type b i t L 1 data stack Figure 3 — Global Addressing Structure l o c a l >| stack base | \ l o c a l stack target r 1 I L I I I I I I | | " — o f f s e t b i t s | | "—-local d i s p l a y b i t s | "—access b i t ( l o c a l ) •—type b i t stack base data stack Figure 4 — L o c a l Addressing Structure an S / 3 6 0 address which represents i t s entry p o i n t , with a l l A Program Development F a c i l i t y 60 f e t c h e s from the program area based on t h i s p o i n t e r . References to other procedures are made v i a the symbol t a b l e i n d i c e s of t h e i r names, which index i n t o a t a b l e c o n t a i n i n g the base addresses of a l l procedures. T h i s s t r u c t u r e s u c c e s s f u l l y e l i m i n a t e s any need f o r r e l o c a t i o n of procedure segments, s i n c e the r e l o c a t i o n e f f e c t i v e l y takes place through the procedure base addresses themselves. 3.1.9.4. Some A d d i t i o n a l Stacks In a d d i t i o n to the i n t e g e r and s t r i n g s t a c k s d e s c r i b e d e a r l i e r , other stacks are used to manage stack p o i n t e r s , program counters, and s i m i l a r c o n t r o l values. The f i r s t c f these stacks i s the g l o b a l s t a c k , which records information at procedure entry time. This stack saves g l o b a l i n f o r m a t i o n such as the symbol t a b l e index of the c a l l i n g procedure as w e l l as the previous p o i n t e r s to the data st a c k s at t h i s l e v e l . Such i n f o r m a t i o n enables the system to maintain the g l o b a l environment of the language. The g l o b a l d i s p l a y , which pro v i d e s a major l i n k i n the data a d d r e s s i n g scheme d e s c r i b e d e a r l i e r , c o n t a i n s an entry f c r each of the 64 p o s s i b l e s t a t i c l e v e l s i n the program. On procedure e n t r y , the g l o b a l d i s p l a y entry corresponding t c the l e v e l of t h a t procedure i s updated to provide the c o r r e c t g l o b a l environment across the c a l l , while on procedure e x i t that e n t r y i s r e s t o r e d to i t s previous value. The l o c a l d i s p l a y p r o v i d e s a s i m i l a r f u n c t i o n f c r l c c a l v a r i a b l e s but s i n c e access to these v a r i a b l e s i s l i m i t e d to the A Program Development F a c i l i t y 61 scope of the e n c l o s i n g procedure, the s t a c k i n g o f values forming the c u r r e n t environment at procedure e n t r y time can be managed by pushing new data s t a c k bases d i r e c t l y onto the l o c a l stack. L o c a l data used w i t h i n t h a t procedure i s then r e f e r e n c e d using the l o c a l d i s p l a y base f o r t h a t procedure as a s t a r t i n g p o i n t . On entry to a new b l o c k , a f u r t h e r e n t r y g i v i n g t hat block's stack base i s pushed onto the l o c a l d i s p l a y s tack. Procedure e x i t r e t u r n s the l o c a l d i s p l a y base to i t s previous l e v e l , hence r e s t o r i n g the l o c a l environment of the c a l l i n g procedure. The d i f f e r e n t treatment of l o c a l and g l o b a l addresses i s not s t r i c t l y necessary w i t h i n the machine. As i n more t r a d i t i o n a l stack implementations, e n t r y to a block c o n t a i n i n g l o c a l v a r i a b l e s c o u l d be t r e a t e d i n a manner i d e n t i c a l to procedure e n t r y , with the c o r r e c t d i s p l a y e n try saved and r e s e t as a base f o r the l o c a l storage r e q u i r e d . T h i s scheme would perhaps s i m p l i f y the machine i n s t r u c t i o n s e t , but only at the expense of the s e p a r a t i o n of the twc c l a s s e s of v a r i a b l e s o b tained here. I f the language allowed parametric procedures (the c u r r e n t grammar i s not s u f f i c i e n t l y r e c u r s i v e t c a l l o w t h e i r d e f i n i t i o n ) , t h i s d i s t i n c t i o n might a l s o prove u s e f u l i n t h a t o n l y those g l o b a l environments which were a c t u a l l y a c c e s s i b l e to the parametric procedures would need to be saved and subsequently r e s t o r e d . The f i n a l major stack i n the machine i s concerned with the p r e s e r v a t i o n of environments across EXIT WITH statements. Since such statements may e x i t both complex e x p r e s s i o n s and EEGIN-END b l o c k s , the l o c a l s t a c k p o i n t e r must be r e s t o r e d tc i t s c o r r e c t A Program Development F a c i l i t y 62 value on e x i t . The do stack i s thus pushed on entry t c a DO-OD expression and appropriate stack p o i n t e r s are made. Subseguent e v a l u a t i o n of an EXIT WITH expression r e q u i r e s that the do stack be popped and the associated stack p o i n t e r s be re-adjusted a c c o r d i n g l y . 3. 2. Algorithms In order to l i m i t t h i s d e s c r i p t i o n of the major algorithms used to relev e n t d e t a i l s , parts of the system which deal with w e l l understood problems i n a s t r a i g h t f o r w a r d fashion have been given only l i m i t e d a t t e n t i o n . Some parts cf the system (such as those dealing with recompilation) deal with problems which have not been p r e v i o u s l y s t u d i e d , however, and are deserving cf more complete d e s c r i p t i o n . While the system could be described on the basis of the commands which i t accepts, such a d e s c r i p t i o n i s u n s a t i s f a c t o r y i n that the amount of work required to implement the b a s i c commands v a r i e s widely. In a d d i t i o n , many of the commands c a l l common system r o u t i n e s with d i f f e r e n t parameters. In view of t h i s s i t u a t i o n , i t was decided that the system could best te described i n terms of the modules which i t contains. 3.2 .1. The Scanner The.system scanner module forms a l i n k between the raw character s t r i n g s returned from the 3270 by the support r o u t i n e s and a l l higher l eve ls of the system. This form of o r g a n i z a t i o n has the advantage of presenting the user with a c o n s i s t e n t token A Program Development F a c i l i t y 63 syntax throughout the system, but the disadvantage of f o r c i n g a l l p o r t i o n s of the system to conform to t h i s token s t r u c t u r e . As an example of t h i s d i f f i c u l t y , the CHECKPOINT and RESTORE commands may only reference f i l e s whose names f o l l o w the syntax of i d e n t i f i e r s w i t h i n the language. Of course, t h i s d i f f i c u l t y could be removed by a l l o w i n g f i l e names to be s p e c i f i e d as character s t r i n g s as w e l l as by i d e n t i f i e r s . A l l i n a l l , the advantages of t h i s approach i n u n i f y i n g input s t r a t e g y seem to outweigh the minor disadvantages. The l i n e s input by the 3270 are f i r s t broken down i n t o s i n g l e character format f o r processing by the scanner. The r o u t i n e which performs t h i s a c t i o n must keep track of both the p o s i t i o n i n the c i r c u l a r b u f f e r f o r the device and the p o s i t i o n on the p a r t i c u l a r l i n e of that character. At t h i s l e v e l p r o v i s i o n s f o r removing erroneous input from the d i s p l a y are implemented. Before scanning a token, the system records the p o s i t i o n of the next character p o i n t e r i n the c i r c u l a r input b u f f e r and i n the l i n e cf that b u f f e r and thus possesses s u f f i c i e n t i n f o r m a t i o n to remove characters from the d i s p l a y beginning with the offending one. In order to avoid the problem of attempting to remove input which has already been s c r o l l e d o f f the screen, the system keeps i t s b u f f e r pointer as a 32 b i t i n t e g e r which i s accessed modulus the number cf l i n e s i n the b u f f e r . Thus, should the pointer to a l o c a t i o n from which input i s to be erased be smaller than the pointer t c the f i r s t a c t i v e l i n e of the b u f f e r , the e n t i r e b u f f e r i s blanked before the next read i s attempted. k Program Development F a c i l i t y 64 The scanner i t s e l f i s quite s i m i l a r tc many ether token analyzers and i s roughly based on a f i n i t e acceptor fcr tokens of the language. I t should be noted that a l l entries recognized by the language including comments and net just these which are mentioned in the syntax are handled by the scanner. The re s u l t of a c a l l to the scanner i s a SUE case record giving the type of the token as well as any other necessary information (such as the length and characters of an i d e n t i f i e r token), Since the scanner i s called by many d i f f e r e n t routines within the compiler, a l l information returned by i t i s kept within the record, and no changes to the global structures for storing s t r i n g s , i d e n t i f i e r s or comments are made. This leaves the r e s p o n s i b i l i t y for making entries i n such structures up to routines c a l l i n g the scanner, and alsc frees other routines which do not wish such entries made to operate independently of these structures. 3.2.2. The Pa ragrapher Given the parse tree representation of a user's program, the work of the paragrapher i s simple. The main control structure of the paragrapher i s a case statement cn the type of the node passed as a parameter and most of the remaining code deals with nasty exceptions such as i d e n t i f i e r s which must be s p l i t over several l i n e s . The driving procedure i t s e l f takes as parameters a pointer to the portion of parse tree to be paragraphed, an integer i n d i c a t i n g the maximum depth of the paragraphing, and a f l a g A Program Development F a c i l i t y 65 i n d i c a t i n g whether the output i s to be d i r e c t e d to the i n t e r n a l d i s p l a y b u f f e r or t c the hardcopy s c r a t c h f i l e opened by the system. The depth parameter a l l o w s the system t o l i m i t the amount of d e t a i l i n c l u d e d i n a paragraphed l i s t i n g while the output type f l a g c o n t r o l s the width and format o f the l i s t i n g as w e l l as i t s e v e n t u a l d e s t i n a t i o n . In order to provide c o - o r d i n a t e i n f o r m a t i o n t o the user, the system maintains a stack of the numbers of the nodes as they are v i s i t e d i n the r e c u r s i v e descent of the parse t r e e . T h i s stack i s i n i t i a l i z e d by the main procedure before the fo r m a t t i n g procedure i s c a l l e d to p r i n t the program segment. The s t a c k p r o v i d e s the system with the Dewey decimal numbering of any node i n r e l a t i o n to the root of the parse t r e e segment passed to the paragrapher. Each l i n e output by the paragrapher t c e i t h e r the screen or the l i s t i n g f i l e begins with the index of the f i r s t s t r u c t u r e p r i n t e d on t h a t l i n e . In order to keep the amount of i n f o r m a t i o n to a reasonable l e v e l , any l i s t i n g of a Dewey decimal index i s l i m i t e d i n i t s t o t a l number of c h a r a c t e r s , and any index exceeding t h i s l ength i s terminated by an e l l i p s i s . Before l e a v i n g the paragrapher, some o b s e r v a t i o n s cn i t s ge n e r a l c l e a n l i n e s s are i n order. S i n c e the problem of f o r m a t t i n g source l i s t i n g s i s admittedly a d i f f i c u l t cne, i t i s i n t e r e s t i n g to note t h a t a s i d e from problems i n v o l v e d with s p e c i a l cases such as i d e n t i f i e r s too long f c r l i n e s , the paragrapher i s s u r p r i s i n g l y c l e a n . Many of the problems common to other paragraphing methods disappear when the s y n t a c t i c i n f o r m a t i o n a v a i l a b l e to the paragrapher i s considered. As an A Program Development F a c i l i t y 6 6 example, the Eighty-One paragrapher separates the formal parameters from the procedure name i n a procedure d e c l a r a t i o n , but does not make t h i s s e p a r a t i o n between a procedure name and i t s a c t u a l parameters i n a r o u t i n e c a l l . In a keyword d i r e c t e d paragrapher such as t h a t used i n the SUE System Language compiler, a d i s t i n c t i o n such as t h i s i s d i f f i c u l t to make s i n c e both c o n s t r u c t s c o n s i s t of an i d e n t i f i e r f o l l o w ed by a r i g h t p a r e n t h e s i s . To allow f o r such a c o n s t r u c t , the SUE paragrapher i s f o r c e d to maintain a number of f l a g s which r e c c r d e x t r a c o n t e x t u a l i n f o r m a t i o n , an approach which i s both more ugly and e r r o r prone than the syntax d i r e c t e d methods used here. 3 . 2.3. CHECKPOINT/RESTORE Command Implementation There i s l i t t l e to say about the implementation of the CHECKPOINT and RESTORE commands which i s not i m p l i c i t from the f i l e s t r u c t u r e s which they use. I t i s i n t e r e s t i n g tc note that the use of a r r a y s u b s c r i p t s i n place of p o i n t e r s w i t h i n data s t r u c t u r e s makes the implementation of such a system t r i v i a l . A s e r i o u s disadvantage of t h i s s t r u c t u r e within the SUI language i s t h a t a l l " p o i n t e r s " w i t h i n the system are subranges cf the i n t e g e r type, and hence are assignment compatible with each other. T h i s s t r u c t u r e might l e a d to e r r o r s which c c u l d e a s i l y be d e t e c t e d a t compile time but which are ignored by the compiler. A Program Development F a c i l i t y 67 3 . 2 . 4 . REPLACE Command Implementation The implementation of the REPLACE command, which i s c e r t a i n l y the most complex command cf the system, i s quite simple given the p r i m i t i v e s supplied. In order to perform a r e p l a c e , the system must decide upon the subtree t c r e p l a c e , i d e n t i f y the s y n t a c t i c type of the subtree which i s to r e p l a c e i t , parse a subtree of that type from the user's in p u t , make the replacement, and f i n a l l y decide what i m p l i c a t i o n s the replacement has on r e c o m p i l a t i o n information. The u s e r - s u p p l i e d Dewey decimal index of the t r e e to be replaced r e l a t i v e to the current o r i g i n makes the f i r s t of these goals easy to a t t a i n . The system need only make the appropriate s e t of moves i n the t r e e to f i n d the node i n which the replacement i s to be made and use the f i n a l i n t e g e r of the replacement l o c a t i o n sequence to i d e n t i f y the subtree which i s to be changed. S i m i l a r l y , the system need only know for each type of subnode the s y n t a c t i c e n t i t y needed to replace i t i n order to s a t i s f y the second goal. The t h i r d a c t i o n r e q u i r e d of the system, that of parsing the s t r i n g input by the user to the required s y n t a c t i c u n i t , i s handled by the parser module of the system and w i l l be described l a t e r . Given the type of s y n t a c t i c u n i t r e q u i r e d , the parser w i l l r e t u r n a pointer t o a t r e e segment representing the user's replacement s t r i n g . The f o u r t h f u n c t i o n , that of performing the a c t u a l replacement, seems to be rather t r i v i a l . There are, however. A Program Development F a c i l i t y 68 some i m p l i c a t i o n s i n th a t both forward and backward l i n k s through the t r e e must be maintained. In view of the a b i l i t y of the e d i t o r to r e p l a c e a s i n g l e member cf a l i s t or seguence with a complete l i s t or sequence, the replace command processor must be capable of g r a f t i n g l i s t s i n t o other l i s t s as .well as at t a c h i n g simple subtrees. A somewhat more i n t e r e s t i n g problem i s the one of de c i d i n g upon the i m p l i c a t i o n s of a change i n terms of the r e c o m p i l a t i o n i n f o r m a t i o n maintained by the system. As has been pointed cut, the only data elements a c c e s s i b l e to procedures nested w i t h i n a given procedure are those declared i n the data block of that procedure. This f a c t i m p l i e s that any changes to the cede block of a procedure w i l l have no e f f e c t on the procedures nested w i t h i n i t , while changes to the data block could r e q u i r e changes to a l l nested procedures. The prototype system described here does not attempt to c l a s s i f y changes according to the changes themselves, but only i n r e l a t i o n t o the places i n which they take place. Thus, a command which a l t e r s a piece of program t e x t back to the same t e x t (such as "REPLACE %WL %\%.") w i l l have the same e f f e c t on the recompilation i n f o r m a t i o n as a command which does change program t e x t . Since a more s o p h i s t i c a t e d algorithm would be v a s t l y more complex and e r r o r prone and si n c e i t would only serve to optimize a number- of ra t h e r u n l i k e l y occurrences, t h i s s i m p l i f i c a t i o n i s q u i t e reasonable. At t h i s p o i n t , an example of the i m p l i c a t i o n s of v a r i a b l e scope r u l e s might prove h e l p f u l . Consider the f o l l o w i n g set of A P r o g r a m Development F a c i l i t y 69 p r o c e d u r e d e c l a r a t i o n s : PROCEDURE A PROCEDURE B PROCEDURE C PROCEDURE D I n t h i s c a s e , a l t e r i n g t h e d a t a b l o c k c f p r o c e d u r e A w i l l r e q u i r e r e c o m p i l a t i o n o f p r o c e d u r e s A, B, C and D; a l t e r i n g t h e d a t a b l o c k o f p r o c e d u r e B w i l l r e q u i r e r e c o m p i l a t i o n of p r o c e d u r e s B and C; and a l t e r i n g t h e d a t a b l o c k o f p r o c e d u r e D w i l l o n l y r e q u i r e t h e r e c o m p i l a t i o n o f p r o c e d u r e D. A l t e r i n g any c o d e b l o c k r e q u i r e s r e c o m p i l a t i o n o f t h a t p r o c e d u r e o n l y . The r e p r e s e n t a t i o n c h o s e n f o r t h e v a r i o u s s t a t e s i n which a p r o c e d u r e b l o c k c a n e x i s t i s d e s c r i b e d by a SUE r e c o r d f o r t h e r e c o m p i l a t i o n t a b l e e n t r i e s . The f l a g d e s c r i b i n g the s t a t e c f a p a r t i c u l a r e n t r y i n t h i s t a b l e a s s i g n s one o f f o u r p o s s i b l e s t a t e s t o t h a t e n t r y . B e f o r e d i s c u s s i n g t h e s e s t a t e s , i t i s n e c e s s a r y t o m e n t i o n t h a t i n o r d e r t o r e c o m p i l e a p a r t i c u l a r c o d e b l o c k i t i s n e c e s s a r y t o t o u r t h e d a t a b l o c k s f c r a l l e n c l o s i n g p r o c e d u r e s . U s i n g o n l y the i n f o r m a t i o n s u p p l i e d i n t h e s o u r c e c o d e , i t i s i m p o s s i b l e t o f i n d p r o c e d u r e s i n need of r e c o m p i l a t i o n w i t h o u t t o u r i n g a l l t h e d a t a b l o c k s i n a program. The f o u r c l a s s e s d e s c r i b e d below e l i m i n a t e t h e n e c e s s i t y of t o u r i n g a l l d a t a b l o c k s by f o r m i n g a c h a i n w h i c h l i n k s t h e t o p -l e v e l p r o c e d u r e t o a l l n e s t e d p r o c e d u r e s n e e d i n g a t t e n t i o n . Thus, t h e s y s t e m c a n move d i r e c t l y t o t h o s e p r o c e d u r e s r e g u i r i n g a t t e n t i o n i g n o r i n g c o m p l e t e b r a n c h e s o f t h e t r e e which do n o t r e q u i r e e x a m i n a t i o n . The f i r s t o f t h e f o u r s t a t e s i s t h a t o f an u n a l t e r e d p r o c e d u r e whose n e s t e d p r o c e d u r e s a r e a l l u n a l t e r e d . C l e a r l y A Program Development F a c i l i t y 70 the compiler can ignore such a node as wel l as the nodes f o r any nested procedures. The second of the four s t a t e s i s used f o r procedures which have not been a l t e r e d themselves but which c o n t a i n procedures which have been a l t e r e d . A node of t h i s type, which j o i n s the t o p - l e v e l procedure to nested procedures which r e q u i r e a t t e n t i o n , r e q u i r e s that the compiler process the data block and proceed to examine a l l nested nodes. The t h i r d s t a t e of a r e c o m p i l a t i o n node i m p l i e s that the program block of the associated procedure d e c l a r a t i o n has been a l t e r e d . In t h i s case, the compiler must a c t u a l l y compile both the data and procedure blocks (since d e c l a r a t i o n s may generate cede) and go on to examine subsequent procedures. The f i n a l type of f l a g i n d i c a t e s that the data block of a procedure d e c l a r a t i o n has been a l t e r e d . This s t a t e , which i s a l s o used f o r newly-created program b l o c k s , r e q u i r e s that the compiler compile both the data and program blocks as w e l l as a l l nested data and program blocks si n c e such nested blocks may contain references to modified v a r i a b l e s . While t o u r i n g the program tree i n the course of compiling procedures, the compiler uses the d e c l a r a t i o n s cf various procedures to b u i l d a separate tree representing the s t r u c t u r e of the set of procedures making up the prcgram. This leaves a t r e e s t r u c t u r e which may be toured by the e d i t o r i n the f o l l o w i n g f a shion to set r e c o m p i l a t i o n f l a g s . The procedure begins at the node of the parse tree i n which the replacement i s made knowing nothing of the context of the change. In order to discover t h i s context, the system traces backward l i n k s to the COMPILATION UNIT> node which l i e s at the root of the procedure A Program Development F a c i l i t y 71 d e f i n i t i o n , and then d e c i d e s whether the change was made to the d a t a or code segment of the procedure by n o t i n g whether the c h a i n passed through i t s data or code l i n k . I f the change was made to the data segment, the f l a g i s examined a n d , i f i t does not a l r e a d y i n d i c a t e t h a t the d a t a b l o c k has been a l t e r e d , i t i s s e t a p p r o p r i a t e l y . S i m i l a r l y , i f the change i s made tc the code segment, the f l a g i s examined and changed a c c o r d i n g l y . If e i t h e r of these changes a l t e r s a r e c o m p i l a t i o n f l a g , backward l i n k s w i t h i n the r e c o m p i l a t i o n t r e e s t r u c t u r e are f o l l o w e d i n o r d e r to make the changes " v i s i b l e " from the t o p - l e v e l p r o c e d u r e . T h i s p r o c e s s c o n s i s t s l a r g e l y i n moving up t h e t r e e and a l t e r i n g a l l " c o r r e c t l y c o m p i l e d " f l a g s t c "needs e x a m i n a t i o n " f l a g s . Should the t r a v e r s e of these l i n k s f i n d a node which does not i n d i c a t e c o r r e c t c o m p i l a t i o n , the process i s s t o p p e d s i n c e a p r e v i o u s c a l l of the p r o c e d u r e would have e n s u r e d the e x i s t e n c e of the c o r r e c t l i n k s . 3 . 2 . 5 . The P a r s e r A l t h o u g h much of the i m p l e m e n t a t i o n of the p a r s e r i s s t r a i g h t f o r w a r d , the s t r u c t u r e imposed by the e d i t o r p l a c e s some demands upon the p a r s e r which are net present i n more c o n v e n t i o n a l c o m p i l e r i m p l e m e n t a t i o n s . The f i r s t of t h e s e demands i s the a b i l i t y t o parse t o s p e c i f i c n o n t e r m i n a l s . While t h e LR (k) p a r s i n g paradigm used c o u l d be m o d i f i e d to accept as a parameter the name of the n o n t e r m i n a l to which i t i s t c p a r s e , t h e r e are a number of d i f f i c u l t i e s , i n c l u d i n g the c o m p l e t i o n c o n d i t i o n of the p a r s e . The second r e q u i r e m e n t i s the a b i l i t y t o a c c e p t as symbols of the i n p u t stream the n o n t e r m i n a l s A Program Development F a c i l i t y 72 represented by the subtree denotations. As an example of t h i s requirement, the parser must be able to ensure t h a t a p a r t i c u l a r t r e e p o r t i o n " f i t s i n " to the t r e e s t r u c t u r e which i t i s b u i l d i n g , i . e . , that a user does not t r y to replace a member of a d e c l a r a t i o n sequence with an expression. Again, s u i t a b l e m o d i f i c a t i o n s to the parsing paradigm i n v o l v i n g s k i p p i n g the s t a t e s a s sociated with the parse of these nonterminals could e a s i l y be worked out. Since an e x c e l l e n t parser generating system was already a v a i l a b l e [RAME], i t was decided that such a system could te used with appropriate m o d i f i c a t i o n s t c the grammar rather than making the e f f o r t to reformulate the d e f i n i t i o n of the LR (k) parser and w r i t e the appropriate parser generating system or s p e c i a l purpose parser. The r e s u l t of t h i s d e c i s i o n i s two pieces of "BNF programming" which solved the prcblems rather w e l l while e l i m i n a t i n g a s i z a b l e piece of software development. In order to solve the problem of being able to parse to a r b i t r a r y nonterminals of the grammar, a number of new t e r m i n a l symbols corresponding to the re g u i r e d t a r g e t nonterminals are added to the parser grammar. These- termina l s cannot be generated by the scanner, and hence the system cannct be upset by erroneous input. In a d d i t i o n to these t e r m i n a l s , new productions of the form <GOAL> ::= SEXPRESSION <EXPRESSICN> are added to the grammar, where <GOAL> i s the sentence symbol of the parser and $EXPRESSICN i s the newly created t e r m i n a l corresponding to the nonterminal <EXPRESSION>. The target of A Program Development F a c i l i t y 73 the parse> which i s passed to the parser as an argument, i s t r a n s l a t e d i n t o i t s corresponding t e r m i n a l symbol and placed on the input stream as the f i r s t item seen by the parser. The parse then proceeds normally, with subseguent input symbols drawn from the user input stream v i a the scanner. I f one t h i n k s of the parser as a program, t h i s technigue e f f e c t i v e l y serves to ••start" the parse i n the r i g h t d i r e c t i o n by supplying a symbol which d i r e c t s the parser to the c o r r e c t i n i t i a l s t a t e . The o v e r a l l e f f e c t i s q u i t e s i m i l a r to that of having a separate parser f o r each nonterminal of the language and deciding cn which of these parsers to use by means of the target symbol. The problem of accepting nonterminals i n the input stream i s handled by c r e a t i n g another c l a s s of te r m i n a l symbols which cannot be generated by the scanner. These nonterminals are used i n productions of the form <EXPRESSION> ::= *EXPRESSION which allow the system to parse the subtree denotations by p l a c i n g a symbol c o n t a i n i n g a po i n t e r to the subtree on the input and g i v i n g i t the nonterminal corresponding to the s t r u c t u r e which i t represents. This s t r u c t u r e gives the i n t e r f a c e between the parser and scanner a f a i r b i t of work to do. Since the scanner dees not change the data s t r u c t u r e s used to s t o r e s t r i n g s such as i d e n t i f i e r s , the scanner-parser i n t e r f a c e must handle such d e t a i l s . In a d d i t i o n , comments f o l l o w i n g i n p u t symbols must be entered i n t o the comment t a b l e and chained together t c form the u n i t s required i n the i n t e r n a l r e p r e s e n t a t i o n . The f i n a l duty A Program Development F a c i l i t y 74 of the scanner-parser i n t e r f a c e i s the handling of subtree denotations w i t h i n the source t e x t . When the i n t e r f a c e reads a s i g n i n the input stream, i t must use the f o l l o w i n g sequence of numbers to index i n t o the parse tr e e s t a r t i n g with the curr e n t parse t r e e p o i n t e r . Upon f i n d i n g the desired ncde, the i n t e r f a c e decides upon the nonterminal i t represents and passes back the appropriate t e r m i n a l symbol along with the p c r t i c n of parse t r e e . In order avoid problems r e s u l t i n g from d u p l i c a t e p o i n t e r s to a s i n g l e p o r t i o n of parse t r e e , the i n t e r f a c e always copies any subtree before r e t u r n i n g i t to the parser. This s t r a t e g y a l s o allows the system to a u t o m a t i c a l l y free the tree p o r t i o n which i s to be replaced without worry of destroying nodes s t i l l connected to v a l i d data s t r u c t u r e s . Construction cf the parse tree proceeds normally, with a s i n g l e semantic stack maintaining p o i n t e r s t c the various p o r t i o n s of the tree under- c o n s t r u c t i o n . The end r e s u l t i s s i m i l a r to the Pushdown Processor of Ahc and Ullman [ASU] extended to allow portions of the parse tree on the processor input. The e r r o r recovery algorithm used by the parser i s q u i t e simple and yet has proven t o be rather e f f e c t i v e . When the parser reaches a st a t e from which the parse may not continue, the system removes the current symbol on the input from the screen along with a l l the symbols which f o l l o w i t . The er r o r recovery r o u t i n e s then attempt to re-read the input symbol and r e s t a r t the parse. This technique i s based upon the theory of the LR(k) parser, which s t a t e s t h a t should the s t r i n g cf symbols A Program Development F a c i l i t y 75 x be a p r e f i x of some sentence of the language while the s t r i n g xa i s not a v a l i d p r e f i x of some such sentence, the parser w i l l announce e r r o r with the symbol a on i t s input. The key phrase i n t h i s d e s c r i p t i o n i s "some sentence of the language". I f the user manages to enter a symbol which i s i n c o r r e c t but s t i l l a p r e f i x of some v a l i d sentence, he w i l l be forced tc cancel the command and begin again. Although t h i s s i t u a t i o n could be remedied by a more complicated and f l e x i b l e e r r o r recovery system, experience with the prototype suggests that such a system might not r e a l l y be necessary. 3.2.6. The Compiler The compiler p o r t i o n cf the system i s quite c l o s e l y r e l a t e d to other types of systems which t r a n s l a t e syntax t r e e s i n t o o b j ect code. Since the Eighty-one machine was d e l i b e r a t e l y designed to provide the semantics of the language, many po r t i o n s of the compiler are almost t r i v i a l . There are, of course, the standard problems of symbol t a b l e management, branch address f i x u p s and so on, but the methods used to solve these problems should be c l e a r given the e a r l i e r d e s c r i p t i o n s of the data s t r u c t u r e s used. The re c o m p i l a t i o n algorithm used by the system has already been described. I t i s i n t e r e s t i n g to ncte, however, that the f u n c t i o n of examining a procedure data block i n order t o make the appropriate symbol t a b l e e n t r i e s i s handled by a separate procedure from the compiler i t s e l f . Examination of a data block takes place only i f the code associated with that procedure i s i A Program Development F a c i l i t y 76 s t i l l v a l i d ( i . e . , n e i t h e r the program nor the data block of the procedure has been changed) and many cf the checks f o r e r r o r c o n d i t i o n s such as run stack overflow and i n c o r r e c t dimension types can be removed. In order t o maintain the i n t e g r i t y cf the r e c o m p i l a t i o n i n f o r m a t i o n , the system f l a g s a l l procedures c o n t a i n i n g e r r o r s as r e q u i r i n g r e c o m p i l a t i c n and a l s c f l a g s the corresponding object module as i n v a l i d . One area of compilation which has been l a r g e l y ignored to t h i s point i s that of a l l o w i n g the i n t e r p r e t e r to output e r r o r messages which contain source co-ordinates. As the tcur cf the parse t r e e proceeds, the compiler maintains a stack recording the Dewey decimal index of the parse node being examined. Since the desired e f f e c t i s to be able to r e c o n s t r u c t t h i s stack w i t h i n the i n t e r p r e t e r as code execution proceeds, i n s t r u c t i o n s to push a value onto the runtime l o c a t i o n stack, replace the top value of the runtime l o c a t i o n stack, and pop the top value of the runtime l o c a t i o n stack are provided. Whenever the l o c a t i o n stack i s a l t e r e d w i t h i n the compiler, the appropriate i n s t r u c t i o n may a l s o be emitted i n t o the object code stream. This technique turns out to be i n e f f i c i e n t , however, since a number of i n s t r u c t i o n s to push values onto the stack followed by a number to pop them o f f again are often generated with nc ether machine i n s t r u c t i o n s i n t e r v e n i n g . In order to reduce t h i s waste of code space, the compiler maintains a stack c o n t a i n i n g the l o c a t i o n s at which the l a s t push l o c a t i o n or r e p l a c e l o c a t i o n i n s t r u c t i o n was emitted f o r t h a t l e v e l of the l o c a t i o n stack. I n s t r u c t i o n s to push the l o c a t i o n stack are emitted as before, with the appropriate entry made to the stack of i n s t r u c t i o n A Program Development F a c i l i t y 77 l o c a t i o n s . Replace l o c a t i o n i n s t r u c t i o n s cause the compiler to examine the stack of i n s t r u c t i o n l o c a t i o n s . I f no i n s t r u c t i o n s have been emitted s i n c e the l a s t push or r e p l a c e l o c a t i o n i n s t r u c t i o n , the argument of t h a t i n s t r u c t i o n i s replaced by the argument of the push l o c a t i o n i n s t r u c t i o n . T h i s t r a n s f o r m a t i o n w i l l thus change the code sequence "PUSHLOC 1 ; REPLLOC 2 ; " to "PUSHLOC 2 ; " . On e m i t t i n g a pop l o c a t i o n i n s t r u c t i o n , the compiler examines the stack of i n s t r u c t i o n l o c a t i o n s to see i f any code has been generated s i n c e the l a s t such i n s t r u c t i o n . If no code has been generated, the compiler w i l l examine the pr e v i o u s i n s t r u c t i o n op code. I f i t i s a push l o c a t i o n o p e r a t i o n , i t i s removed and the pop l o c a t i o n i n s t r u c t i o n i s not generated, while i f i t i s a r e p l a c e l o c a t i o n o p e r a t i o n , i t i s removed and the pop i n s t r u c t i o n i s generated. T h i s o p t i m i z a t i o n a l l o w s the compiler to remove the sequence "PUSHLOC 1 ; POPLOC;" or to change the sequence "REPLLOC 1; POPLOC;" tc "POPLOC;". Note the stack i s necessary to opt i m i z e longer sequences of i n s t r u c t i o n s , such as removing "PUSHLOC 1; PUSHLOC 1; POPLOC; POPLOC;". T h i s a l g o r i t h m i s s t i l l not optimal i n the sense that a l l i n s t r u c t i o n s are t r e a t e d as though they could cause runtime e r r o r s although t h i s assumption i s not s t r i c t l y t r u e . 3 . 2.7. The Command Scanner The command scanner loop reads the next token from the input stream and performs the a p p r o p r i a t e a c t i c n . The f a c t that commands are token o r i e n t e d r a t h e r than l i n e o r i e n t e d c r e a t e s a s l i g h t problem i n t h a t the scree n i s r e f r e s h e d a f t e r completing each- command which might change the parse t r e e p o i n t e r . As an ft Program Development F a c i l i t y 78 example, the user may enter three i n t e g e r Down commands cn a l i n e , but the system w i l l paragraph the appropriate source t e x t and r e f r e s h the d i s p l a y three separate times, even though two of these are immediately re-done. This problem i s more one of e f f i c i e n c y than of user convenience, however. One complex feature of the command scanner i s the a b i l i t y to abort a command at any read w i t h i n that command. While not as d i f f i c u l t as the problem of f i e l d i n g a t t e n t i o n i n t e r r u p t s which might take place at any point i n the program's execution, t h i s system does present some problems. Data s t r u c t u r e s b u i l t up i n the course of executing the f i r s t part of the command may have to be freed when a command i s ca n c e l l e d . The only commands i n which t h i s becomes a s e r i o u s problem are those which c a l l the parser, since a cancel command may take place i n the middle of a parser read. Here p r o v i s i o n must be made to f r e e any portions of t r e e which have already been created by the parser and stored on the semantic stack. This i s accomplished by maintaining a f l a g which i n d i c a t e s whether the parser i s a c t i v e , thus a l l o w i n g a clean up r o u t i n e to tour the semantic stack and input symbols i f they contain v a l i d s t r u c t u r e s . Again, the f a c t that subtree denotations create copies of the o r i g i n a l parse tree ensures that t h i s i s a safe approach. A Program Development F a c i l i t y 79 3.2.8. The I n t e r p r e t e r The algorithms used i n the i n t e r p r e t e r are q u i t e s i m i l a r to those used i n other stack machines f o r block s t r u c t u r e d languages. A f u l l l i s t i n g of the operations provided by the machine and the a c t i o n s which they perform i s sup p l i e d as an appendix. One problem posed by the s t r i n g handling f a c i l i t i e s of the language i s that of garbage c o l l e c t i n g the fre e s t r i n g area. This problem i s handled by the C08PACTIFY algorithm used i n the XPL run time o r g a n i z a t i o n [MH6W]. The separation of the i n t e g e r and s t r i n g stacks w i t h i n the machine s i m p l i f i e s the main task of garbage c o l l e c t i o n , that of f i n d i n g a l l references t c s t r i n g items, since a l l s t r i n g v a r i a b l e s and temporary r e s u l t s are stored on the s t r i n g stack. A Program Development F a c i l i t y 80 P a r t 4 — Conclusions I I .j Now that the e x t e r n a l and i n t e r n a l features of the system have been described, i t i s time to comment upon the success of the e n t i r e p r o j e c t and make some suggestions f o r future work i n the area. Within the r e s t r i c t i o n s set out f c r a prototype system, the current implementation has proven to be r a t h e r s u c c e s s f u l . The main modules of the system, the e d i t o r , paragrapher and compiler a l l work according to t h e i r proposed d e s c r i p t i o n s and operate upon the program tree data s t r u c t u r e with l i t t l e d i f f i c u l t y . In a d d i t i o n , with the exception of a few flaws i n e x t e r n a l design, the u n i f i e d system cf prcgram development seems to s a t i s f y the user's needs i n a reasonable f a s h i o n . The f u l l i m p l i c a t i o n s of the system s t r u c t u r e are d i f f i c u l t to estimate because the system has not yet teen a p p l i e d to a l a r g e s c a l e programming task and may never be due to i t s o v e r s i m p l i f i e d language. While t h i s i s a se r i o u s problem with the d e c i s i o n to implement a s i m p l i f i e d prototype, the present implementation has solved many of the t e c h n i c a l problems associated with the proposed system as w e l l as suggesting i t s o v e r a l l usefulness without the expense of a l a r g e programming e f f o r t . Given the current implementation, i t should be much simpler to create a usable production system e l i m i n a t i n g the A Program Development F a c i l i t y 81 r e s t r i c t i o n s and i n f e l i c i t i e s which now e x i s t . The remainder of t h i s chapter w i l l attempt to b u i l d a foundation f o r a f u t u r e implementation by po i n t i n g cut both the strengths and weaknesses of the prototype. In a d d i t i o n , some e f f o r t w i l l be made to d i s t i n g u i s h between problems inherent i n the system design and those r e s u l t i n g from bad design d e c i s i o n s and a lack of programmer time. 4 . 1 . System Externa Is Since the i n t e r n a l t r e e s t r u c t u r e maintained by the system f o r c e s the i n c o r p o r a t i o n of a s t r u c t u r e d t e x t e d i t o r , the u s a b i l i t y of the system hinges upon t h i s form of e d i t i n g . While s t r u c t u r e e d i t o r s f o r LISP have e x i s t e d f o r many years, the reguirements f o r an e d i t o r operating upon te x t with a more complex underlying grammar are somewhat d i f f e r e n t . The INTERLISP e d i t o r mentioned e a r l i e r r e l i e s upon a huge number of commands which can perform e x o t i c changes r e q u i r i n g d r a s t i c a l t e r a t i o n s to the s t r u c t u r e of the S-expression being e d i t e d . The Eighty-One e d i t o r , on the other hand, manages to e x i s t with only a s i n g l e command which a l t e r s the program t r e e . In view of t h i s c o n t r a s t , i t i s i n t e r e s t i n g to compare the r e l a t i v e ease of use of the two systems. In the Eighty-One e d i t o r , many changes such as a l t e r i n g keywords w i t h i n source t e x t are disallowed by the very nature of the mechanism used to l o c a t e items to be changed. S i m i l a r l y , changes to brackets and dots can only be performed i n r e l a t i o n to the underlying s t r u c t u r e s of a LISP e d i t o r . The LISP e d i t o r s w i l l , however, allow the user to A Program Development F a c i l i t y 82 manipulate parentheses while the Eighty-One e d i t o r w i l l not e x p l i c i t l y move bracketing tokens such as BEGIN and END w i t h i n the program t e x t . In my l i m i t e d experience with the Eighty-One e d i t o r , i t would seem that such commands would add l i t t l e to i t s usef u l n e s s . In LISP, a major source of t e x t u a l e r r o r s i s misplaced parentheses, e f f e c t i v e l y a s y n t a c t i c e r r c r which cannot be caught by the simple parser of the language. In a system which allows a r i c h e r set cf bracketing and s y n t a c t i c s t r u c t u r e s , on the other hand, mismatched sets of bracketing tokens u s u a l l y cause s y n t a c t i c e r r o r s which are caught immediately by the parser and hence cannot be entered as program t e x t . I f one wishes to a l t e r t e x t i n a way which corresponds c l o s e l y to the s t r u c t u r e of the program t r e e such as adding a new l e v e l of BEGIN-END bracketing, the Eighty-One e d i t o r can perform t h i s a c t i o n at l e a s t as c l e a n l y as most character or l i n e o r i e n t e d t e x t e d i t o r s . In general, the v a l i d i t y cf the s i m p l i f i c a t i o n s used i n the e d i t o r hinge upon the b e l i e f that once s y n t a c t i c a l l y c o r r e c t programs have been entered, the changes reguired i n them such as i n s e r t i n g and d e l e t i n g p o r t i o n s of t e x t have obvious r e l a t i o n s to the prcgram t r e e . A second e s s e n t i a l feature of the prototype system i s the i n s i s t e n c e that program t e x t always be s y n t a c t i c a l l y v a l i d . Again, t h i s r e s t r i c t i o n seems quite easy to l i v e with, and even the simple e r r o r recovery scheme implemented here makes the e n t e r i n g of s y n t a c t i c a l l y c o r r e c t programs a p a i n l e s s task. The question of whether or not the e d i t i n g system should fo r c e programs to be s e m a n t i c a l l y c o r r e c t as well i s also of some importance to the user. In my opi n i o n , a s t r u c t u r e capable of A Program Development F a c i l i t y 83 dynamically recording and checking type information presents some s e r i o u s t e c h n i c a l d i f f i c u l t i e s while adding l i t t l e or nothing to the usefulness cf the system. As an example, a user who wishes to change a p a r t i c u l a r i d e n t i f i e r from type i n t e g e r to type character would f i n d i t d i f f i c u l t to do so. Changing an occurrence of the i d e n t i f i e r would render i t s d e c l a r a t i o n i n v a l i d while changing i t s d e c l a r a t i o n would render i t s occurrences i n v a l i d . The only s o l u t i o n would be tc f i r s t delete a l l occurrences of the i d e n t i f i e r , change the d e c l a r a t i o n , and replace the occurrences, a formidable task indeed since one must a l s o maintain the s y n t a c t i c v a l i d i t y of the program t r e e . A c h a r a c t e r i s t i c of many such syntax d i r e c t e d e d i t o r s i n c l u d i n g those f o r LISP i s the requirement that the user as we l l as the system have at l e a s t some knowledge of the i n t e r n a l r e p r e s e n t a t i o n and the syntax on which i t was based. As s t a t e d i n the i n t r o d u c t i o n , I am of the opinion that a user should be prepared to spend some time to l e a r n a system which he plans to use on a regular b a s i s . Likewise a user should be well acquainted with the syntax of a programming language he wishes to use. The s t r u c t u r e of the system thus tends to enforce a " f o r experts only" r e s t r i c t i o n on i t s use. Again, t h i s i s a reasonable l i m i t a t i o n s i n c e , as I have pointed cut, the merits of the system do not become apparent u n t i l l a r g e p r o j e c t s are t a c k l e d . He now come to twc major problems with the user i n t e r f a c e of the system. The f i r s t and foremost of these i s the e x c l u s i v e use of Dewey decimal numbering as the method of i d e n t i f y i n g A Program Development F a c i l i t y 84 program t e x t . More than any other feature of the system t h i s choice f o r c e s the user t o understand e x p l i c i t l y the i n t e r n a l program tr e e format. I f the user i s w i l l i n g tc move to a p o s i t i o n which i s s u i t a b l y c l o s e to the target p o s i t i o n , the length of the l i s t of numbers s p e c i f y i n g change l o c a t i o n s i s r e l a t i v e l y s h o r t , but at t h i s point the user a l s o begins t o los e the context i n which such changes are made. The cnly advantage of the numbering system i s that i t f o r c e s the user t o keep h i s programs to a manageable s i z e i n order to e d i t them. Fo r t u n a t e l y , t h i s problem could be remedied i n the design of a new system, although i t i s important enough i n the cu r r e n t implementation that a major re w r i t e would be necessary to remove i t . One p o s s i b l e s o l u t i o n of the problem would be an extension of the notion of " l o c a t o r " , the object which i d e n t i f i e s subtrees of a p a r t i c u l a r s t r u c t u r e . Instead of a sequence of Dewey decimal i n d i c e s , t h i s item could i n c l u d e keywords, punctuation marks or i d e n t i f i e r s of the language. S p e c i f y i n g a keyword such as IF would cause the e d i t o r to search the program t e x t i n p r i n t order f o r the f i r s t <IF STATEMENT> node. Meanings f o r other keywords and punctuation marks could be s u p p l i e d , thus g i v i n g the user the a b i l i t y to r e f e r to t e x t p o s i t i o n s i n a f a r more n a t u r a l manner. When combined with Dewey decimal i n d i c e s used to i d e n t i f y t h i n g s such as members of sequences or l i s t s , t h i s s t r u c t u r e would be much pr e f e r a b l e to that c u r r e n t l y i n use. Such a method would a l s o allow the e l i m i n a t i o n of the numbers which are c u r r e n t l y included with the l i s t i n g . A second major flaw i n the implementation of the e d i t o r i s A Program Development F a c i l i t y 85 the omission of some form of UNDO command. Since powerful t e x t e d i t o r s allow users t o make l a r g e mistakes, i t i s e s s e n t i a l t h a t the user be able to recover p a r t s of. h i s program which are scrambled or l o s t . The s y n t a c t i c checks performed by the system before changes are made do reduce the chances cf making c a t a s t r o p h i c e r r o r s , but they most c e r t a i n l y do not e l i m i n a t e them. A s u i t a b l e UNDO command i s a l s o v a l u a b l e as a t r a i n i n g a i d , f o r i t a l l o w s a user to experiment with the system without f e a r of d e s t r o y i n g h i s work. The s o p h i s t i c a t e d UNDO f a c i l i t i e s of INTERLISP suggest a s u i t a b l e s e t of commands. A d i f f e r e n t form of undo f a c i l i t y which should a l s o be provided i s the a b i l i t y to s t o r e c o n v e r s a t i o n and move about the c o n v e r s a t i o n a l b u f f e r , as can be done under the MTS Device S e r v i c e Routine f o r the 3270. 4.2. System I n t e r n a l s Within the l i m i t a t i o n s imposed by the time a v a i l a b l e f o r t h e i r implementation, most data s t r u c t u r e s of the compiler have proven q u i t e s a t i s f a c t o r y . As mentioned e a r l i e r , the que s t i o n of i n t e g r a t i n g the main t r e e s t r u c t u r e with some form c f mass st o r a g e has no d e f i n i t e answer which i s independent of the type of machine and o p e r a t i n g system i n v o l v e d . On a minicomputer one would c e r t a i n l y wish t o maintain much of the s t r u c t u r e on d i s k i n order to save primary memory f o r other t h i n g s s i n c e t r a n s f e r s between these two forms of storage are r e l a t i v e l y cheap. On a l a r g e s c a l e v i r t u a l memory system, on the other hand, i t i s more reasonable to maintain the e n t i r e s t r u c t u r e being operated upon i n core (as do a l l LISP e d i t i n g systems) l e a v i n g problems of A Program Development F a c i l i t y 86 paging to the operating system which can probably perform them more e f f i c i e n t l y . In e i t h e r case, the problem cf l o c a l i z i n g references comes i n t o question. Any form of disk r e p r e s e n t a t i o n of program nodes would have to deal with blocks cf these nodes, and should t r y to ensure that references do not cross boundaries between these blocks. S i m i l a r l y , references to other nodes w i t h i n an in-core r e p r e s e n t a t i o n should f a l l w i t h i n the same page of v i r t u a l memory i n order to minimize working set s i z e . An obvious way of c r e a t i n g such a s i t u a t i o n i s by a l l o c a t i n g nodes i n separate blocks f o r separate procedures. The system e d i t i n g strategy would then force a l l references to be contained wi t h i n that s i n g l e block. A number of other techniques designed to reduce off-page references i n l i s t processing systems could a l s o be employed to improve system e f f i c i e n c y i n t h i s area [ B O S H ] . At t h i s point some j u s t i f i c a t i o n f o r the choice cf the t r e e - s t r u c t u r e d representation of the intermediate t e x t i s perhaps necessary. The method of maintaining text i n o r i g i n a l c haracter format has been already discussed and r e j e c t e d as favouring the e d i t i n g f u n c t i o n of the system at the expense of the compiling and paragraphing f u n c t i o n s . P o l i s h code r e p r e s e n t a t i o n would seem t o be another l i k e l y candidate, since i t i s often used as an i n t e r n a l r e p r e s e n t a t i o n i n other programming systems which maintain program t e x t [MANI ]. Those who have had experience with such systems point out that while P o l i s h code i s an e x c e l l e n t r e p r e s e n t a t i o n f o r s t r u c t u r e s cf the same order of complexity as a r i t h m e t i c expressions, i t becomes d i f f i c u l t to re c o n s t r u c t the source t e x t of more complex A Program Development F a c i l i t y 87 languages [C&H]. The u s e f u l n e s s of t h i s r e p r e s e n t a t i o n i s thus l i m i t e d t o languages such as LOGO, BASIC and APL i n which programs are e s s e n t i a l l y l i s t s of a r i t h m e t i c e x p r e s s i o n s . A t h i r d p o s s i b l e i n t e r m e d i a t e r e p r e s e n t a t i o n , that of an i n t e r m e d i a t e machine code and a s s o c i a t e d t a b l e s a l l o w i n g r e c o n s t r u c t i o n of the o r i g i n a l t e x t was a l s o r e j e c t e d cn the grounds that i t tended to favour the compiling f u n c t i o n at the expense of the e d i t o r and paragrapher. Now that the g e n e r a l concept of a t r e e s t r u c t u r e has been j u s t i f i e d , some of the p a r t i c u l a r f e a t u r e s cf the tree used here should be d i s c u s s e d . The major d e c i s i o n to add backward l i n k s to the t r e e seems t o have been q u i t e s u c c e s s f u l . Such l i n k s are not s t r i c t l y necessary, f o r LISP e d i t o r s manage without them by m a i n t a i n i n g a stack of p o i n t e r s to nodes which they have crossed i n descending the t r e e . In t h i s case, an Dp command simply means "pop the l o c a t i o n s t a c k " and a Down command r e q u i r e s t h a t „ the c u r r e n t node p o i n t e r be pushed on the stack before the a p p r o p r i a t e successor i s s e l e c t e d . The l i n k s provided i n the t r e e s t r u c t u r e b u i l t here do seem to c l e a n up the implementation, however, and the e d i t o r always "knows where i t i s " i n the parse t r e e . N a t u r a l l y , t h i s i s not obtained without c o s t , s i n c e both the e d i t o r and the parser must maintain the c o r r e c t backward l i n k s and provide the storage i n parse nodes f o r them. I t should a l s o be noted t h a t t h i s implementation of the parse t r e e prevents more than one ancestor from p o i n t i n g to a p a r t i c u l a r s ubtree s i n c e such a s t r u c t u r e would r e q u i r e an ambiguous backward l i n k from the subtree. T h i s s t r u c t u r e would c e r t a i n l y cause other problems f o r the storage management A Program Development F a c i l i t y 88 f a c i l i t i e s which would have t o maintain seme form c f r e f e r e n c e count on the nodes to allow the e d i t o r to detec t m o d i f i c a t i o n s to a s i n g l e i n s t a n c e of a d u p l i c a t e d subtree. S i n c e d u p l i c a t e s u b t r e e s would r a r e l y be crea t e d i n the course cf e d i t i n g a program, the only s e r i o u s purpose of such a s t r u c t u r e would be the i d e n t i f i c a t i o n of common subexpressions f c r code o p t i m i z a t i o n . In d e s i g n i n g a t r e e s t r u c t u r e c f t h i s type, an obvious trade o f f between storage e f f i c i e n c y and c o n s i s t e n c y of the o v e r a l l s t r u c t u r e becomes apparent. Consider, f c r example, the s t r u c t u r e of a formal parameter l i s t . I t would be p o s s i b l e to re p r e s e n t t h i s s t r u c t u r e as an i d e n t i f i e r l i s t attached to a COMPILATION UNIT> node, and thus have the brackets surrounding the l i s t i m p l i c i t from i t s context. T h i s presents problems f o r handling the comments which may be a s s o c i a t e d with the parentheses, however, s i n c e the parser can enly e a s i l y a t t a c h them t o a node c r e a t e d a t the time the r e d u c t i o n producing the parameter l i s t i s performed. In order to keep t h i s type of c o m p l i c a t i o n to a minimum, the s t r u c t u r e of the parse nodes f o l l o w s the grammar q u i t e c l o s e l y . T h i s type of s t r u c t u r e l e a d s to system code which c o n t a i n s case statements on a l l p o s s i b l e node types, thus making the e f f o r t r e q u i r e d to extend the system to more complex grammars e s s e n t i a l l y l i n e a r i n the s i z e of those grammars. As a f u r t h e r b e n e f i t , the i n t e r n a l s t r u c t u r e and hence the e d i t i n g commands can be understood i n terms of the language syntax presented to the user. The question of i n c l u d i n g semantic i n f o r m a t i o n i n the t r e e A Program Development F a c i l i t y 89 s t r u c t u r e should a l s o be examined here at greater length. As mentioned above, r e q u i r i n g semantic as w e l l as s y n t a c t i c correctness of user input could cause severe problems f o r the user. Although the problems of maintaining semantic correctness as program e d i t i n g continues are rat h e r horrendous, i t would be p o s s i b l e to maintain semantic i n f o r m a t i o n between c a l l s of the compiler thus e l i m i n a t i n g the pass which t c u r s the data blocks of procedures already c o r r e c t l y compiled. In t h i s scheme, the "data block a l t e r e d " f l a g would s t i l l r equire complete r e c o m p i l a t i o n and r e c o n s t r u c t i o n of the symbol t a b l e along with the semantic checks which such a procedure i m p l i e s . One method of maintaining the semantic information would l i n k i d e n t i f i e r nodes wit h i n the t r e e t o t h e i r d e f i n i n g occurrences. The d e c l a r a t i o n nodes would a l s o store semantic information concerning v a r i a b l e type, run stack l o c a t i o n and d i s p l a y l e v e l thus making t h i s information a v a i l a b l e to the compiler. As i s often the case, the choice between keeping the symbol table across compilations and regenerating i t as required i s a tr a d e o f f between storage requirements and computing requirements. In a language as simple as Eighty-One, there i s l i t t l e advantage gained i n saving the symbol t a b l e , although t h i s might not be the case i n a system a l l o w i n g more complex type d e f i n i t i o n s . The question of storage management al s o plays an important r o l e i n the design of* systems of t h i s type, and hence merits some d i s c u s s i o n . Although the system of f r e e l i s t s and e x p l i c i t c o n t r o l over node a l l o c a t i o n and d e a l l o c a t i o n has been adequate i n the prototype system, a more advanced system may r e q u i r e more A Program Development F a c i l i t y 90 complex techniques. The problems of maintaining storage encountered i n the prototype were l a r g e l y concerned with keeping track of a l l nodes i n the system r a t h e r than dealing with nodes referenced by more than one p o i n t e r . A system maintaining s t r u c t u r e s such as undo l i s t s f o r command backups might be forced to use a f u l l garbage c o l l e c t i o n scheme l i k e that c f a LISP system i n order to keep t r a c k of a l l storage. Here the question i s not that of keeping track of a l l p o i n t e r s , s i n c e t h i s i s c l e a r l y p o s s i b l e , but rather the issue of ensuring that a l l p o i n t e r s are always handled ( i . e . , a l l o c a t e d and freed) c o r r e c t l y . As system complexity grows, such a question becomes more d i f f i c u l t , while a proof of a garbage c o l l e c t i o n system should be v a l i d r egardless of the complexity cf the programs i n v o l v e d . As an a d d i t i o n a l b e n e f i t , garbage c o l l e c t i o n systems are a l s o capable of compacting storage and hence cf l o c a l i z i n g references [HANB] . A data s t r u c t u r e which has been ignored up to t h i s point i s the object code f o r the system i t s e l f . C u r r e n t l y , the system i s a s i n g l e program which i s loaded d i r e c t l y and executed with no attempt to overlay storage. This s t r u c t u r e could c l e a r l y te improved by l o a d i n g the compiler dynamically when i t i s requested by the user. The other main por t i o n s of the system, the p a r s e r , the e d i t o r and the paragrapher, could net reasonably be loaded dynamically since they are required by almost a l l commands. The question of passing information between the compiler and i n t e r p r e t e r i s a l s o an important one. The f i r s t p c i n t tc be A Program Development F a c i l i t y 91 made i s that the i n t e r p r e t e r i s a device to reduce the e f f o r t necessary to generate code f o r the language rather than a necessary part of the , system. There would be l i t t l e or no problem to generate S/360 machine code f o r the language, but some run-time support f o r character s t r i n g s would be necessary. Although no attempt was made to in t e g r a t e the i n t e r p r e t e r with the i n t e r n a l r e p resentation of the source program, the i n s t r u c t i o n s i n c l u d e d i n the object code which maintain Dewey decimal i n d i c e s i n t o the program tree are s u f f i c i e n t to pi n p o i n t l o c a t i o n s w i t h i n that t r e e . Thus, i t would be quite simple to add to the monitor the a b i l i t y to p r i n t out the l o c a t i o n of a run-time e r r o r i n paragraphed source form. Other features such as t r a c e and p r o f i l e f a c i l i t i e s could also be e a s i l y i n t e g r a t e d i n t o the system using t h i s method cf f i n d i n g parse tree l o c a t i o n s . The p r o v i s i o n of good e r r o r d i a g n o s t i c s could also be f a c i l i t a t e d by l e a v i n g the compiler symbol t a b l e i n the tree between compilations as described e a r l i e r . Such information would enable the i n t e r p r e t e r to provide d e t a i l e d dumps of program v a r i a b l e s such as those provided by the load and go ALGOL W runtime system [SATT] or i n t e r a c t i v e debugging f e a t u r e s l i k e these provided f o r LISP [TEIT] or various assembly languages [SDS]. A d e f i n i t e problem with t h i s method of communication between the compiler and i n t e r p r e t e r i s the bulk of the code generated. C l e a r l y the amount of information t r a n s m i t t e d , which i s enough to locate an i n d i v i d u a l token i n the source code, i s more than that r e q u i r e d by the user. In order to reduce the bulk of t h i s code, a st r a t e g y as simple as r e f u s i n g to push the A Program Development F a c i l i t y 92 l o c a t i o n stack beyond a p a r t i c u l a r l e v e l could be adopted. P r o v i d i n g the user would net l e t h i s programs grow too deep, such a s t r a t e g y could be q u i t e e f f e c t i v e . A more s a t i s f a c t o r y answer would i n v o l v e more knowledge on the part of the compiler of " s t r a t e g i c " s e c t i o n s w i t h i n the code which ccul d locate e r r o r prone p o i n t s . In a statement-oriented language such points are easy to i d e n t i f y (as i n the co-ordinate count maintained by ALGOL W) but i n more r e c u r s i v e expression o r i e n t e d languages such as Eighty-One t h e i r d e t e c t i o n becomes more d i f f i c u l t . An a l t e r n a t i v e method would reguire that the compiler emit d i r e c t i n d i c e s or p o i n t e r s i n t o the parse t r e e i n the object cede, thus a l l o w i n g the run-time system to d i r e c t l y reference p o r t i o n s of the source program t r e e . While such linkage schemes would s u r e l y add to the s i z e of compiled programs, they have the advantage that they could e a s i l y be removed from any production system with no change i n language semantics or run-time e r r o r d e t e c t i o n . Should an e r r o r occur i n a production run, cne c c u l d repeat that run with a version of the program cont a i n i n g run-time l o c a t o r s and hence p r o v i d i n g proper d i a g n o s t i c s . The most s a t i s f a c t o r y answer would perhaps i n v o l v e a separate t a b l e mapping object code l o c a t i o n s i n t o parse tree segments, thus a l l o w i n g a run-time monitor to operate at no cost t c the user u n t i l an e r r o r a c t u a l l y occurs. A f i n a l c o n s i d e r a t i o n , one which f a l l s midway between the c a t e g o r i e s of i n t e r n a l and e x t e r n a l , i s t h a t cf the s i z e of r e c o m p i l a t i o n u n i t s . The u n i t chosen here, that of an i n d i v i d u a l procedure, i s both reasonable and n a t u r a l i n terms of the language s t r u c t u r e chosen. Should the user keep his A Program Development F a c i l i t y 93 i procedures to a reasonable s i z e (say f i f t y l i n e s of source code) t h i s s t r u c t u r e should a l s o be r e l a t i v e l y e f f i c i e n t . There does come a point at which the e f f o r t reguired t c maintain complex r e c o m p i l a t i o n information and to scan la r g e amounts of program t e x t to compile very s m a l l portions of t e x t becomes l a r g e r than the e f f o r t reguired to compile a block of a more reasonable s i z e . A f u r t h e r complication of decreasing the s i z e of c o m p i l a t i o n u n i t s i s that cf c r e a t i n g a s u i t a b l y f l e x i b l e object code format. Since machine code i s g e n e r a l l y a l i n e a r l i s t of i n s t r u c t i o n s j o i n e d by numerous p o i n t e r s (branch addresses), i n s e r t i o n and d e l e t i o n of p a r t i c u l a r segments poses s i z a b l e problems. In t h i s case, one must be c a r e f u l not to s a c r i f i c e run time e f f i c i e n c y i n order to gain some s l i g h t advantage at the compile stage. 4.3. Language Design Considerations As one would expect, the design of the system has a number of i m p l i c a t i o n s f o r the language which i s implemented. The Eighty-One language purposely i n c l u d e s strong type r u l e s i n order to examine t h e i r e f f e c t s upon the implementation. In r e t r o s p e c t , however, the scope r u l e s and s y n t a c t i c s t r u c t u r e of the language are f a r more important than the types which i t r e q u i r e s or supports. An e a r l i e r version of the Eighty-One language used scope r u l e s and a d e c l a r a t i o n syntax s i m i l a r to that of A l g o l 60, with procedure d e c l a r a t i o n s allowed at the head of any block w i t h i n the code. While such a scheme cculd be implemented, i t was changed to the present SUE l i k e v e r s i o n for three reasons. F i r s t , the d i s t i n c t i o n between g l o b a l and l o c a l A Program Development F a c i l i t y 94 data emphasizes the d i f f e r e n c e s between v a r i a b l e s used i n many procedures and those l o c a l to a p a r t i c u l a r procedure. Second, the compiler may e a s i l y access g l o b a l v a r i a b l e d e c l a r a t i o n s i n order to enter them i n t o the symbol t a b l e . The ccm p i l e r i s not f o r c e d to tour an e n t i r e procedure c o n t a i n i n g d e c l a r a t i o n s i n a r b i t r a r y p l a c e s to compile more deeply nested r o u t i n e s . F i n a l l y , the s t r u c t u r e used here allows the user to e d i t separate procedures by name, r a t h e r than having to f i n d them w i t h i n a l a r g e r block of cede. T h i s d i s t i n c t i o n i s a l s o used by the compiler to l i s t only those procedures which are recompiled at any one c a l l of the compiler r a t h e r than l i s t i n g a l l the source of a l a r g e program. The technigues developed here could e a s i l y be a p p l i e d to any other language using A l g o l l i k e scope r u l e s . I t wculd a l s o be p o s s i b l e to r e s t r i c t the no t i o n s contained here to a s i n g l e l e v e l of r e c o m p i l a t i o n and hence handle FORTRAN and Assembler programs c o n t a i n i n g COMMON b l o c k s and CSECTs r e s p e c t i v e l y . Other n o t i o n s of v a r i a b l e scope, such as these used i n SIMULA c l a s s e s could a l s o be i n t e g r a t e d i n t o the system with only minor changes i n the al g o r i t h m s and data s t r u c t u r e s c o n t r o l l i n g r e c o m p i l a t i o n of programs. 4.4. A User^s Comments on SUE As i s customary at the end of a large programming p r o j e c t , t h i s s e c t i o n i n c l u d e s some remarks on the language used i n i t s implementation. As should always be the case, SUE was chosen because i t seemed t o be the best a v a i l a b l e t o o l f c r the j c b . On A Program Development F a c i l i t y 95 a system such as MTS where a l a r g e and widely v a r i e d s e l e c t i o n of languages i s a v a i l a b l e [PECK], t h i s i s sometimes a d i f f i c u l t d e c i s i o n to make, but a f t e r completing the p r o j e c t I see no reason to doubt the o r i g i n a l one. The most e s s e n t i a l f e a t u r e s of a language used to implement a system of t h i s complexity are those concerned with data s t r u c t u r i n g . As the program segments i n c l u d e d as an appendix show, many of these f e a t u r e s were used e x t e n s i v e l y i n d e f i n i n g the major s t r u c t u r e s used by the system. SUE a l s o p r o v i d e s good segmentation of programs, a f e a t u r e which i s i n my o p i n i o n r e g u i r e d f o r any la r g e p r o j e c t . A f u r t h e r f e a t u r e s u p p l i e d i s access to most of the hardware of the t a r g e t machine, as we l l as the f a c i l i t i e s of the o p e r a t i n g system. In the Eighty-One system, these a b i l i t i e s are o f t e n used to good advantage. A major c o n s i d e r a t i o n i n any c h o i c e of language must he the a b i l i t y of that language t o handle a program c f the proposed s i z e . Although some problems with compiler t a b l e s i z e s did occur, these were e a s i l y c o r r e c t e d . I t should be noted that some systems, notably the Stanfo r d implementation of ALGOL W, are simply i n c a p a b l e of handling a program cf t h i s s i z e , l a r g e l y because they must t r e a t i t as a s i n g l e chunk. The f i n a l c o n c r e t e reason f o r chosing SUE was the e f f i c i e n c y of the o b j e c t code generated. Since Eighty-One i s a prototype system, t h i s c o n s i d e r a t i o n i s r e l a t i v e l y minor, but i t i s nice to know t h a t a l l t a s k s i n v o l v e d can be completed i n very reasonable amounts of time. For those concerned with e f f i c i e n c y , e xecution p r o f i l e s of the system show that i t was spending about 80% of i t s time i n the assembly language i n t e r f a c e with the 3270 screen A Program Development F a c i l i t y 96 before t h a t r o u t i n e was r e - w r i t t e n i n SUE. Now, the system spends approximately f i v e percent of i t s time i n the same r o u t i n e . So much f o r the standard t h e o r i e s on the e f f i c i e n c y of assembler language. In r e t r o s p e c t , a number of other advantages of the SUE language have become apparent. To begin with, debugging time with the language i s d r a s t i c a l l y reduced, although p o s s i b l y at the c o s t of some time i n producing a program which i s acceptable t o the compiler. The run-time range check f a c i l i t y serves to give reasonable e r r o r messages f o r problems o c c u r r i n g a t run time, and a l s o helps ensure that a s s e r t i o n s about the range of v a r i a b l e s are a c t u a l l y v a l i d . Indeed, many cf the s e r i o u s problems i n the implementation of Eighty-One were caused by bugs i n the SUE compiler. T h i s i s not a complaint cn the SUE compiler, but r a t h e r an i n d i c a t i o n of the s m a l l number of d i f f i c u l t bugs which occurred i n the Eighty-One implementation. In a d d i t i o n , the s t r u c t u r e of the SUE compiler was such t h a t even a person with o n l y a very g e n e r a l knowledge cf i t s i n t e r n a l workings could make changes or f i n d and c o r r e c t bugs, an i m p o s s i b l e task f o r a compiler of t h i s s i z e and complexity w r i t t e n i n assembly language. A l l i s not p e r f e c t , however. The s t r i c t s t a t i c nature of a l l data s t r u c t u r e s i n the SUE language does o f t e n prevent the user from implementing t h i n g s i n the most n a t u r a l f a s h i o n . Such s t r u c t u r e s as records c o n t a i n i n g a r r a y s of undetermined length can be implemented, but only by s u b v e r t i n g many cf the p r i n c i p l e s of the language. My f i n a l complaint i s r a t h e r i l l -A Program Development F a c i l i t y 97 formed, but w i l l be included anyway. I t concerns a personal f e e l i n g that SUE i s a d i f f i c u l t language to w r i t e , even when compared to languages such as assembler. I t i s p o s s i b l e that programming c o r r e c t l y i s net a simple a c t i v i t y , and hence SUE only gives a c o r r e c t impression of the d i f f i c u l t y i n v o l v e d . Despite my personal f e e l i n g s i t would be a mistake to c r i t i c i z e the design of a language which e s s e n t i a l l y made the implementation of the system p o s s i b l e with so l i t t l e g r i e f . 4.5. Suggestions f o r Future Work As u s u a l , the main body of t h i s document cl o s e s «ith the expected t i t l e . While e a r l i e r p o r t i o n s of t h i s chapter d e a l with improvements of the i n t e r n a l and e x t e r n a l d e t a i l s of the system reguired to create a t r u l y u s e f u l prcgram development f a c i l i t y , l i t t l e has been sai d of other f e a t u r e s which could be b u i l t upon the general base o u t l i n e d here. This e n t i r e document has attempted to show tha t the major purpose of systems of t h i s type i s the c r e a t i o n of a s o l i d base upon which more s o p h i s t i c a t e d systems could be b u i l t . The obvious and w e l l -defined f e a t u r e s have already been enumerated: automatic backup of source t e x t on mass storage, s t a t i s t i c s gathering f o r the use of those i n t e r e s t e d i n the ergonomic aspects cf programming language and system design, and management of documentation and development information associated with programs. Such f e a t u r e s could e a s i l y be added i n obvious ways given the base suppli e d by the u n i f i e d system. Some of the more i n t e r e s t i n g questions r a i s e d by the system A Program Development F a c i l i t y 98 are i n the i l l - d e f i n e d area of how a program ought t c i n t e r a c t with i t s users. While o r i g i n a l thoughts on t h i s question s t a t e d that a programming system should behave as a mute servant which would always do i t s utmost to serve i t s master's w i l l , I b e l i e v e t h a t current understanding of s t r u c t u r e d programming suggests a d i f f e r e n t philosophy. A large amount of e f f o r t should not be expended to make bad guesses about what a user meant when an er r o r occurs. Instead, a system should be prepared t c give a c l e a r d e s c r i p t i o n of the e r r o r and prompt the user f o r h i s c o r r e c t i o n . No e f f o r t should be made to keep t h i s process e i t h e r automatic or p a i n l e s s , s i n c e such e f f o r t may become an open i n v i t a t i o n to programming e r r o r s . The key to understanding t h i s philosophy i s D i j k s t r a ' s statement that while debugging may be used as a method of showing e r r o r s i n a program, i t cannot be used to show t h e i r absence. This comment cas t s s e r i c u s doubts on many systems which attempt to make debugging the c e n t r a l part of program c o n s t r u c t i o n . A f u r t h e r point i n t h i s area of man-machine dialogue i s made by the e r r o r recovery of the Eighty-One system. In most systems, i n t e r a c t i v e e r r o r messages are displayed with user t e x t , and hence do not disappear a f t e r an amount cf r e a l time. Here, on the other hand, the user may turn away from the screen and a c t u a l l y miss an e r r o r message. Although t h i s may seem ra t h e r dangerous to a new user of the system, i t does force the user to keep h i s mind on h i s conversation with the system. I f nothing e l s e , the process of entering program t e x t forces a programmer to re-read h i s code at l e a s t once, and t h i s type of system e r r o r strategy could help keep h i s mind on what he i s A Program Development F a c i l i t y 99 doing. As mentioned e a r l i e r , systems of t h i s type could' a l s o enforce c e r t a i n r u l e s regarding the execution of programs and e d i t i n g changes which f o l l o w . A f u r t h e r example wculd be a system which keeps track of e r r o r t o t a l s and, i f the percentage of e r r o r s r i s e s above a c e r t a i n t h r e s h o l d , refuses to allow the user to continue. Again, r u l e s of t h i s s o r t might slow a programmer down and help to increase the r e l i a b i l i t y cf the software which he produces. I t i s i n t e r e s t i n g t o note that the l i s t of f u n c t i o n s cf a l a r g e r v e r s i o n of the prototype implemented here corresponds c l o s e l y to t h a t of the programming secretary i n the Chief Programmer Team described by Baker and K i l l s [EA&MJ. While management p r i n c i p l e s do suggest that c l e r i c a l tasks such as source t e x t entry and m o d i f i c a t i o n should be assigned to c l e r i c a l personnel, the " f o r experts only" previse cf the proposed system would re q u i r e that the programmer himself be r e s p o n s i b l e f o r h i s source code. In the system, however,, the bulk of the t r u l y tedious c l e r i c a l work such as the maintenance of various logs would be e n t i r e l y the r e s p o n s i b i l i t y of the system, l e a v i n g the programmer f r e e to concentrate upon h i s t e x t " j u s t one more time." In c l o s i n g , a few words about the success of the prototype system are i n order. Since the system deals with a t r i v i a l language i n a somewhat s u p e r f i c i a l f a s h i o n , i t i s d i f f i c u l t to assess the i m p l i c a t i o n s of the s t r u c t u r e f o r a user who wishes to construct l a r g e programs. The prototype does show that the system i s at l e a s t t e c h n i c a l l y p o s s i b l e , and has managed t c show A Program Development F a c i l i t y 100 at l e a s t a few of the areas of user i n t e r a c t i o n which need a t t e n t i o n . In order to properly evaluate the system, i t w i l l be necessary to construct a f u l l s c ale system dealing with a f u l l s c a le systems implementation language and f i n d a w i l l i n g group of competent programmers to use i t f o r s i z a b l e programming p r o j e c t s . Even i f t h i s i s done, however, the e x t e r n a l aspects of a badly done system might outweigh the advantages r e s u l t i n g from i t s i n t e r n a l s t r u c t u r e . I would guess that t h i s i s not the case, and that the design proposed here could form a s o l i d foundation f o r a program development f a c i l i t y which would help the user towards the c r e a t i o n of c o r r e c t programs. , A Program Development F a c i l i t y 101 B i b l i o g r a D h y [A£U] Aho, A.V. and Oilman, J.D., The Theory cf P a r s i n g , l a t i o n , and Compiling Volume I I : Compiling, P r e n t i c e - H a l l , " 1 9 7 3 . ~ ~ ~~ [ATWO] Atwood, J.w. (ed), P r o j e c t SUE Status Report, T e c h n i c a l Report CSRG 11, Computer Systems Research Grcup, U n i v e r s i t y of Toronto, A p r i l 1972. [BA&M ] Baker, F.T. and M i l l s , H.D., "Chief Programmer Teams", £§tamatJLon, December 1973. [BOSM] Bobrow, D.G. and Murphy, D.L., " S t r u c t u r e of a LISP System Using Two-Level Storage", Communications of the ACM, Volume 10, Number 3, March 19677 [BSW ] Bobrow, D.G. and Wegbreit, E., A Model and Stack I l E i§2§B£stion 2J HlJlillilS l^^i£5i!£!Si]*J» Report Number 23347~Bolt~Beranek and Newman, March/ 1972. [BRUS] B r u s s e l , H. , Indexed Reading and W r i t i n g on the 3270, Department of Commerce, U n i v e r s i t y of B r i t i s h Columbia, 1973. [CSH] C h a r l t o n , C.C. and Hibbard, P.G., "A Note on Recreating Source Code from the Reverse P o l i s h Form", Software P r a c t i c e and E x p e r i e n c e , Volume 3, Number 2, A p r i l - J u n e 1973. [CLAR] C l a r k , B.L., The SUE System Language User^s Guide iS§Xi§§^lr Department of Computer Scie n c e , U n i v e r s i t y of B r i t i s h Columbia, A p r i l 1974. [ESC] E a r l e y , J. and P. Caizergues, "A Method f o r Incrementally Compiling Languages with Nested Statement S t r u c t u r e " , Communications of the ACM, Volume 15, Number 12, December"972. [HANA ] Hansen, W.J., The Graphic E d i t i n g of S t r u c t u r e d Text, T e c h n i c a l Memorandum Number 190, Ap p l i e d Mathematics D i v i s i o n , Argonne N a t i o n a l Laboratory, January 1970. A Program Development F a c i l i t y 102 [HANB] , The Impact of Storage Management on Plex l£2£sssing Language IJS£l§I§ntaticn, Te c h n i c a l Report C s T l 3 , Computer Science Department, Stanford U n i v e r s i t y , J u l y 1969. [HORN] Horning, J . J . , TOY V UserJ_s Manual, Computer Science Department, U n i v e r s i t y of Toronto, 1971. [IBM] IBM 3270 D i s p l a j Sjjstem Component D e s c r i p t i o n , IBM Form Number~GA27-27U9-0, March"19727 [ K N U T ] K n u t h , D.E., T h e A r t o f C o m p u t e r P r o g r a m m i n g V o l u m e J A d d i s o n - W e s l e y , 1968. [MANI ] M a n i s , V . S . , A M a c h i n e I n d e p e n d e n t I m p l e m e n t a t i o n o f LOGO, M.Sc. T h e s i s , D e p a r t m e n t o f C o m p u t e r S c i e n c e J U n i v e r s i t y o f B r i t i s h C o l u m b i a , A u g u s t 1973. [MHSW] McKeeman, W.M., Horning, J . J . and Wortman, D.B., A Compiler Generator, P r e n t i c e - H a l l , 1970. [OST] Osborne, E.J. and Twyver, D.A., UBC TERMINALS: The MTS Terminal User^s Guide, Computing Centre, U n i v e r s i t y of B r i t i s h Columbia, A p r i l 1974. [PECK] Peck, J.E.L., "Comparison of Languages", Programming Teaching Technigues, IFIP TC2 Working Conference on Programming Teaching, Zakopane, Poland, 1972. [RAME ] Ramer, D.R., Construction of LRJkl Parsers With AE£lication t o ALGOL 68, M.Sc. Thesis, Department of Computer Science, U n i v e r s i t y of B r i t i s h Columbia, August 1973. [SATT] S a t t e r t h w a i t e , E. , "Debugging Tcols f o r High L e v e l Languages", Software P r a c t i c e and Experience, Volume 2, 1972. [ SDS] SIC DEBUG: The Symbolic Debugging System, Computing Centre, U n i v e r s i t y of B r i t i s h Columbia, January 1973. A Program Development F a c i l i t y 103 [TEIT] Teitelman, W., INTERLISP Reference Manual, XEROX Palo A l t o Research Center, December 1973. [VANW] van Wijngaarden, A., M a i l l o u x , B.J., Peck, J.F.L. and Koster, C. H. A., "Report on the A l g o r i t h m i c Language ALGOL 68", Numerische Mathematic, Number 14, 1969., A Program Development F a c i l i t y 104 | Appendix 1 — A Sample Session This appendix contains a small example of how the system might be used. The "screens" shown here were a c t u a l l y produced i n a dialogue with the system, and were siphoned o f f i n t o a f i l e f o r use here. In order to f i t the l i n e s i n t o t h i s document, the l i m i t on the width of output l i n e s was reduced from the standard of 79 columns to 64 columns, producing cramped d i s p l a y s of program t e x t . In a d d i t i o n , a number of screens have been removed i n places where the screen format i s obvious. The large number of screens o r i g i n a l l y produced (64) i n a session which l a s t e d approximately f i v e minutes shows the tremendous t r a n s f e r r a t e p o s s i b l e with a device of t h i s type and a l s o points out the inadequacy of slower-speed t e r m i n a l s f o r t h i s a p p l i c a t i o n . A Program Development F a c i l i t y 105 r- T This i s the user's i n i t i a l view of the system with no procedures yet defined and no input i n the entry area. The "_" i n the upper l e f t - h a n d corner of the entry area represents the cursor p o s i t i o n . A Program Development F a c i l i t y 106 INSERT PROCEDURE MAIN DATA INTEGER PROCEDURE HANOI(INTEGER,INTEGER,CHARACTER, CHARACTER); CODE HANOI(4,"SOURCE","INTERMEDIATE","DESTINATION") Here, the user i s p r e s e n t i n g h i s main procedure to the system v i a the INSERT command. Since t h i s i s the f i r s t procedure d e f i n e d , i t w i l l be assumed t o be at the r o o t of the procedure t r e e . Three screens have passed i n the course of e n t e r i n g these l i n e s of t e x t . a Program Development F a c i l i t y 107 | PROCEDURE MaiN | DATa 3 I INTEGER PROCEDURE HANOI (INTEGER,INTEGER, 3 . 1 . 3 . 1 ...| CHARACTER,CHARACTER); | CODE 4 | HANOI (4 ,"SOURCE", "INTERMEDIATE", "DESTINATION") INSERT PROCEDURE MAIN DATA INTEGER PROCEDURE HANOI(INTEGER,INTEGER,CHARACTER, CHARACTER); CODE HANOI (4,"SOURCE","INTERMEDIATE","DESTINATION") i The system has a c c e p t e d the procedure which becomes the o b j e c t o f t h e e d i t o r ' s a t t e n t i o n and i s d i s p l a y e d i n paragraphed form on the s c r e e n . T h i s i s the end of the f i r s t command. A Program Development F a c i l i t y 108 1 |PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,INTEGER, 3. 1 .3. 1 ... | CHARACTER,CHARACTER); | CODE 4 | HANOI (4 ,"SOURCE","INTERMEDIATE", "DESTINATION") CHARACTER) ; CODE HANOI (4,"SOURCE","INTERMEDIATE","DESTINATION") . INSERT PROCEDURE H ANOI (N , S ,1 ,D) DATA CODE IF 11 > 0 THEN HANOI (N- 1 , S, D, I) OUTPUT := " MOVE PIECE " + STRING (N) + " FROM "_ • The user has begun to i n s e r t procedure HANGI, and i s about t o e n t e r the l i n e at t h e bottom of the e n t r y a r e a . He has made a sy n t a x e r r o r , however, f o r g e t t i n g the s e m i c o l o n f o l l o w i n g the c a l l of procedure HANOI. Note t h a t the end of the e n t r y a r e a has been reached and t h a t o u t p u t i s b e i n g s c r o l l e d o f f the s c r e e n . A Program Development F a c i l i t y 109 | PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,INTEGER, 3 . 1 . 3 . 1 . . . | CHARACTER,CHARACTER); | CODE 4 | HANOI(4,"SOURCE","INTERMEDIATE","DESTINATION") CHARACTER) ; CODE HANOI (4,"SOURCE","INTERMEDIATE","DESTINATION") INSERT PROCEDURE H ANOI (N, S, I , D) DATA CODE IF N > 0 THEN HANOI (N-1 ,S ,D ,1) OUTPUT := " MOVE PIECE " + STRING (N) + " FROM " *** ERROR: SYNTAX ERROR. The p a r s e r d i s c o v e r s the s y n t a x e r r o r and o u t p u t s the a p p r o p r i a t e message. T h i s message i s d i s p l a y e d f o r a t o u t f i v e seconds o f r e a l t i me d u r i n g which no i n p u t w i l l be a c c e p t e d . D u r i n g p e r i o d s such as t h e s e , the c u r s o r r e t u r n s to the upper l e f t - h a n d c o r n e r of t h e s c r e e n as shown. A Program Development F a c i l i t y 110 i ' | PROCEDURE MAIN | DATA 3 | INTEGER PROCEDORE HANOI (INTEGER,INTEGER, 3.1.3.1...| CHARACTER,CHARACTER); | CODE 4 | HANOI(4,"SOURCE","INTERMEDIATE","DESTINATION") CHARACTER) ; CODE HANOI(4,"SOURCE","INTERMEDIATE","BESTINAT ION") . INSERT PROCEDURE H A NO I (N, S, I , D) DATA CODE IF N > 0 THEN HANOI (N—1 ,S,D,I) The system has removed i n p u t b e g i n n i n g w i t h the o f f e n d i n g symbol (the i d e n t i f i e r OUTPUT) and now i s w i l l i n g t o resume from t h a t p o i n t . A Program Development F a c i l i t y 1 1 1 r~ | PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,INTEGER, 3.1 .3.1...| CHARACTER,CHARACTER); | CODE U | HANOI (4 ,"SOURCE" /'INTERMEDIATE","DESTINATION") CHARACTER) ; CODE HANOI(4,"SOURCE","INTERMEDIATE","DESTINATION") INSERT PROCEDURE HANOI(N,S,I,D) DATA CODE IF N > 0 THEN HANOI (N-1 ,S,D,I) i The user now e n t e r s the s e m i c o l o n which i s a c c e p t e d by the p a r s e r w i t h o u t c o m p l a i n t . A Program Development F a c i l i t y 112 r-| PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,INTEGER, 3 . 1 . 3 . 1 . . . | CHARACTER,CHARACTER); | CODE U | HANOI (4 ,"SOURCE","INTERMEDIATE","DESTINATION") INSERT PROCEDURE HANOI (N,S ,1,D) DATA CODE IF N > 0 THEN HANOI (N-1, S, D, I) 'OUTPUT := " MOVE PIECE " • STRING (N) + " FROM " + S + " TO " D;_ The u s e r c o n t i n u e s t c e n t e r the t e x t of the p r o c e d u r e , t u t a l a s , he has o m i t t e d the c o n c a t e n a t i o n o p e r a t o r ("+") p r e c e d i n g t h e i d e n t i f i e r "D". A Program Development F a c i l i t y 113 |PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI {INTEGER,INTEGER, 3 . 1 . 3 . 1 . ..| CHARACTER,CHARACTER); | CODE 4 | HANOI (4 ,"SOURCE","INTERMEDIATE", "DESTINATION") INSERT PROCEDURE HANOI (N,S,I,D) DATA CODE I F N > 0 THEN HANOI (N- 1, S, D, I) OUTPUT := " MOVE PIECE " + STRING (N) + " FROM " + S + " TO " D; *** ERROR: SYNTAX ERROR. Again, the system d i s p l a y s i t s message... A Program Development F a c i l i t y 114 i : •• 1 1 |PROCEDURE MAIN | | |DATA I |3 | INTEGER PROCEDURE HANOI (INTEGER,INTEGER, | 1 3 . 1 . 3 . 1 . . . | CHARACTER,CHARACTER); | | |CODE I | 4 | HANOI (4 ,"SOURCE","INTERMEDIATE", "DESTINATION") | INSERT PROCEDURE HANOI (N, S , 1 ,D) DATA CODE IF N > 0 THEN HANOI (N-1, S, D, I) 'OUTPUT := " MOVE PIECE " + STRING (N) + " FROM " + S + " TO " ...and removes the er r o n e o u s i n p u t . Note t h a t the e r r o r message has d i s a p p e a r e d from t h e e r r o r message l i n e . A Program Development F a c i l i t y 1 1 5 r PROCEDURE HANOI (N, S, I, D) DATA CODE IF N > 0 4 4 . 1 . 2 4 . 1 . 2 . 2 4 . 1 . 2 . 3 4 . 1 . 3 THEN HANOI(#EXPR LIST#) ; ELSE 0 OUTPUT := #STRING# '+ #FORM ULA# ; HANOI (#EXPR LIST*) FI OUTPUT := MOVE PIECE " + STRING (N) + " FROM " + S + " TO " + D; HANOI (N -1,I,S,D) ELSE 0 FI. The user completes the entry of h i s procedure which i s accepted by the system. T h i s procedure now becomes the ob j e c t of the e d i t o r ' s a t t e n t i o n and i s d i s p l a y e d i n the d i s p l a y a r e a . We see here f o r the f i r s t time examples of the e d i t o r ' s attempt to l i m i t the depth of the l i s t i n g by d i s p l a y i n g nonterminal nodes such as "#EXPR LIST#" d i r e c t l y . J A Program Development F a c i l i t y 1 1 6 PROCEDURE HANOI(N,S,I,D) DATA CODE 4 4.1.2 4.1.2.2 4.1.2.3 4.1.3 IF N > 0 THEN HANOI(#EXPR L I S T f ) ; OUTPUT := #STRING# + #FORMU L A#; HANOI(#EXPR LIST*) ELSE 0 FI S + " TO " • D; HANOI (N-1 ,1, S,D) ELSE 0 FI. ED MAIN The user now remembers t h a t he has made an e r r o r i n e n t e r i n g the t e x t o f MAIN, and so he i s s u e s an EDIT command to s h i f t a t t e n t i o n back to that procedure. A Program Development F a c i l i t y 117 r - |PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,INTEGER, 3.1.3.1...| CHARACTER,CHARACTER); | CODE 4 | HANOI (4 , "SOURCE", "INTERMEDIATE", " EEST IN AT ION") S + " TO " + D; HANOI(N-1,1,S,D) ELSE 0 F I . ED MAIN The system responds by changing i t s a t t e n t i o n and d i s p l a y i n g p r o c e d u r e MAIN "from the t o p " . \ A Program Development F a c i l i t y 118 | PROCEDURE MAIN |DATA / 3 | INTEGER PROCEDURE HANOI (INTEGER,INTEGER, 3 . 1 . 3 . 1 . . . | CHARACTER,CHARACTER); | CODE 4 | HANOI(4,"SOURCE","INTERMEDIATE"/'DESTINATION") • D; HANOI (N -1 ,I,S,D) ELSE 0 F I . ED MAIN 3 1 The o b j e c t o f t h e u s e r ' s i n t e r e s t i s the d e c l a r a t i o n c f the second parameter to the procedure HANOI which s h o u l d te CHARACTER r a t h e r than INTEGER. He t h e r e f o r e i s s u e s twc Down commands, the f i r s t of which w i l l t ake him to the < DECL ARAT ION SEQUENCE> o f t h e pr o c e d u r e . A Program Development F a c i l i t y 119 | INTEGER PROCEDURE HANOI (INTEGER , INTEGER,CHA R ACTER,"* | CHARACTER); .+ D; HANOI (N-1 ,I,S,D) ELSE 0 FI. ED MAIN 3 1 A f t e r the execution of the f i r s t of the Down commands, the screen l o o k s l i k e t h i s . In a c t u a l use of the system t h i s screen would f l a s h by so q u i c k l y that the user would not n o t i c e i t . A Program Development F a c i l i t y 120 | INTEGER PROCEDURE HANOI (INTEGER , INTEGER, CH AR ACT ER, | CHARACTER) + D; HANOI(N-1,I,S,D) ELSE 0 F I . ED HAIN 3 1 T h i s i s the screen a f t e r the execution of the second Down command, which p i c k s the f i r s t <DECIARATICN> of the DECLARATION SEQUENCE)*. The onl y change i n the e x t e r n a l r e p r e s e n t a t i o n of the program t e x t i s the removal of the semicolon f o l l o w i n g the d e c l a r a t i o n . A Program Development F a c i l i t y 121 i | INTEGER PROCEDURE HANOI (INTEGER , INTEGER f CHARACTER,"* | CHARACTER) HANOI (N-1 , I, S , D) ELSE 0 F I . ED MAIN 3 1 3 1 L . 1 The user chooses to enter two more Down commands, the f i r s t l o c a t i n g the <ACCEPTS TYPE OPTION> of the <PROCEEURE DECLARATIONS A Program Development F a c i l i t y \ | (INTEGER, INTEGER, CHARACTER, CHARACTER) HANOI (N-1,I,S,D) ELSE 0 F I . ED MAIN 3 1 3 1 The system moves to the a p p r o p r i a t e subtree. Again, screen would f l a s h by the user unnoticed. A Program Development F a c i l i t y 123 HANOI (N- 1 ,I,S,D) ELSE 0 FI. ED MAIN 3 1 3 1 The second Down command selects the <TYPE I'IST> of the <ACCEPTS TYPE OPTION>, thus removing the parentheses present in the l a s t display. A Program Development F a c i l i t y 124 i • 1 | |INTEGER,INTEGER,CHARACTER,CHARACTER | The user now i s s u e s h i s REPLACE command which i s to r e p l a c e the second item of the <TYPE LIST> with the <TYPE> CHARACTER. ELSE 0 F I . | ED MAIN | 3 1 I 3 1 I REP %2% CHARACTER._ I A Program Development F a c i l i t y 1 2 5 | INTEGER, CHARACTER, CHARACTER ,CHARACTER ELSE 0 F I . ED MAIN 3 1 3 1 REP %2% CHARACTER. O b l i g i n g l y , t h e system makes the c o r r e c t i o n . Ncte t h a t a change t o the da t a b l o c k c f t h i s t o p - l e v e l p r o c e d u r e r e q u i r e s r e c o m p i l a t i o n o f a l l n e s t e d p r o c e d u r e s ( i n t h i s c a s e , the e n t i r e program) . A Program Development F a c i l i t y 126 | INTEGER , CHARACTER/CHARACTER,CHARACTER ED MAIN 3 1 3 1 REP %2% CHARACTER. The user now wishes t o go back to the top o f the procedure, and so he e n t e r s an Up command with a r e l a t i v e l y l a r g e number. The system w i l l not complain i f t h i s number i s too l a r g e , but w i l l stop at the top of the c u r r e n t procedure d e c l a r a t i o n . A Program Development F a c i l i t y 127 |PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (I NT F, GIB, C K AB A CT IR, 3 . 1 . 3 . 1 . . . | CHARACTER,CHARACTER); | CODE 4 | HANOI(4,"SOURCE","INTERMEDIATE","DESTINATION") ED MAIN 3 1 3 1 REP %2% CHARACTER, I 1 0 Here the system d i s p l a y s the e n t i r e procedure d e c l a r a t i o n . A Program Development F a c i l i t y 128 r -|PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,CHARACTER, 3 . 1 . 3 . 1 . . . | CHARACTER/CHARACTER); | CODE 4 | HANOI(4 , "SOURCE" , " INTERMEDIATE" , "DESTINATION") 3 1 3 1 REP %2% CHARACTER, | 10 ED HANOI Now the user wants to go back to h i s p r o c e d u r e HANOI. He wishes to add a p e r i o d t o the end of the move message which i t o u t p u t s . A Program Development F a c i l i t y IPROCEDURE HANOI(N,S,I,D) | DATA |CODE 4 | IF H > 0 4.1.2 | THEN HANOI(#EXPR LIST*); 4.1.2.2 | OUTPUT := #STBISG# + # FORMULA*; 4.1.2.3 | HANOI (# EXPR LIST*) 4.1.3 | ELSE 0 | FI 3 1 3 1 REP %2% CHARACTER. | 10 ED HANOI The e d i t o r responds by d i s p l a y i n g procedure HANOI, A Program Development F a c i l i t y 130 PROCEDURE HANOI(N,S,I,D) DATA CODE 4 4.1.2 4.1.2.2 4.1.2.3 4.1.3 IF N > 0 THEN HANOI (#EXPR LIST*) ; ELSE 0 OUTPUT := #STRING# + # FOR MU LA* ; HANOI(#EXPR LIST*) FI 3 1 REP %2% CHARACTER. | 10 ED HANOI 4 1 2 2 The user wishes to a l t e r the assignment to the pseudo-v a r i a b l e OUTPUT, and so he enter s the set of Dewey decimal i n d i c e s which i s p r i n t e d beside i t i n the l i s t i n g . A Program Development F a c i l i t y 131 | OUTPUT := MOVE PIE C E " + STRING(tSTOB EEF#) + 3.3.3.3 | FROM " + S + #STRING# + #STOR EEF# 3 1 REP %2% CHARACTER. | 10 ED HANOI 4 1 2 2 Here, the system has completed the set of moves which were 1) to the EXPRESSION SEQUENCE> of the COMPILATION UNIT>; 2) to the <IF EXPRESSION> which i s the f i r s t member of the -(EXPRESSION SEQUENCE>; 3) to the EXPRESSION SEQUENCE> making up the true a l t e r n a t i v e of the <IF EXPRESSIONS and 4) to the <FORMULA> which i s the second element of the EXPRESSION SEQUENCE. The int e r m e d i a t e d i s p l a y s have been e l i m i n a t e d . A Program Development F a c i l i t y 132 | OUTPUT := »• MOVE PIECE " + STRING (#STOR REF#) + 3.3.3.3 , | " FROM " + S + tSTRIVG* + #STOR REF# REP %2% CHARACTER. | 10 ED HANOI 4 1 2 2 3 3 3 3 The user again uses Down commands t c move through the r i g h t p a r t s of the s e r i e s of formulas. A Program Development F a c i l i t y i | |S + " TO " + D REP %2% CHARACTER. 110 ED HANOI 4 1 2 2 3 3 3 3 The user i s now c l o s e to the t a i l of the formula. Again three i n t e r v e n i n g d i s p l a y s have been removed. A Program Development F a c i l i t y i | |S + TO " + D H O ED HANOI 4 1 2 2 3 3 3 3 3 The user decides to move down yet another l e v e l t c r i g h t operand of the <FOHMULA>. A Program Development F a c i l i t y 135 r 1 I |« TO " + D I I M O | | ED HANOI | | 4 1 2 2 | | 3 3 3 3 | I 3 | l _ | I | «- j T h i s leaves the user a t the <F0PK0LA> node whose r i g h t operand he wishes t o change. ' A Program Development F a c i l i t y 136 |" TO " + D ED HANOI 4 1 2 2 3 3 3 3 3 REP %3% D + • » . " , i i The user i s s u e s the command to add the p e r i o d tc the end of the m e s s a g e . . . A P r o g r a m D e v e l o p m e n t F a c i l i t y 1 3 7 ED HANOI 4 1 2 2 3 3 3 3 3 REP %3% D . . . a n d t h e s y s t e m m a k e s t h e c h a n g e . T h i s c h a n g e w o u l d o n l y r e q u i r e r e c o m p i l a t i o n o f t h e p r o c e d u r e HANOI s h o u l d t h e p r e v i o u s c o m p i l a t i o n o f t h e p r o g r a m b e o t h e r w i s e v a l i d . A Program Development F a c i l i t y |PROCEDURE HANOI(N,S,I,D) | DATA | CODE 4 I I F N > 0 4. 1.2 I THEN HANOI (#EXPR L I S T f ) ; 4. 1.2.2 I ODTPDT := #STRING# + #FORMULA*; 4. 1. 2.3 I HANOI(#EXPR LIST*) 4. 1.3 | ELSE 0 | F I 4 1 2 2 3 3 3 3 3 REP %3% D + " . » . I 10 i The user now enters an Up command to r e t u r n to the top the procedure, and the e d i t o r does so. A Program Development F a c i l i t y 139 i 1 | |PROCEDURE MAIN I I |DATA t | |3 | INTEGER PROCEDURE HANOI (INTEGER/CHARACTER, | J3.1.3.1...| CHARACTER,CHARACTER) ; I | |CODE | |4 | HANOI(4,"SOURCE","INTERMEDIATE","DESTINATION") | 3 3 3 3 I 3 I REP %3% D + " . " . I | 10 I ED MAIN I The user now goes back t o procedure MAIN i n o r d e r to make a f i n a l change. A Program Development F a c i l i t y 140 The user wishes to output the f i n a l r e s u l t of HANOI. He f i r s t moves down to" the EXPRESSION SEQUENCE > of the COMPILATION UNITX A Program Development F a c i l i t y 141 |HANOI (4,"SOURCE","INTERMEDIATE","DESTINATION") I REP %3% D + ".". I 10 ED MAIN 4 REP 5M% OUTPUT := STRING (31$). 1 Here, the user i s s u e s a command to r e p l a c e the f i r s t element of the EXPRESSION SEQUENCE> with an assignment tc the OUTPUT pseudo-variable of the CHARACTER r e p r e s e n t a t i o n of HANOI'S r e s u l t . T h i s command w i l l e f f e c t i v e l y embed the prev i o u s c a l l of HANOI i n the t e x t s u p p l i e d . A Program Development F a c i l i t y 142 |OUTPUT := STRING(HANOI#PABMS#) REP %3% D + | 10 ED MAIN 4 REP %1% OUTPUT := STRING i J The e d i t o r makes the replacement. In s i t u a t i o n s such as t h i s , the s t r u c t u r e e d i t o r i s c l e a r l y more convenient than a context type e d i t o r . T h i s replacement would only r e q u i r e t h a t the system recompile procedure MAIN, s i n c e no data b l c c k has been a l t e r e d . A Program Development F a c i l i t y 143 |PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,CHARACTER , 3 . 1 . 3 . 1 . . . | CHARACTER,CHARACTER); | CODE 4 | OUTPUT := STRING (tSTOR REF#) I 10 ED MAIN 4 REP %1% OUTPUT I 10 := STRING {% 1%) i Again, the user r e t u r n s to the top of the procedure t e x t . A Program Development F a c i l i t y 1 4 4 i 1 | |PROCEDURE MAIN | | |DATA | | 3 | INTEGER PROCEDURE HANOI (INTEGER,CHARACTER, | 1 3 . 1 . 3 . 1 . . . | CHARACTER,CHARACTER) ; | I |.CODE | | 4 | OUTPUT := STRING (#STOR REFt) | j ED MAIN I |4 I | REP %"\% OUTPUT := STRING (*1X). I || 10 I | COMPILE I I ~ I I I The user now i s s u e s a COMPILE command t o ge n e r a t e the o b j e c t code f o r h i s program. A Program Development F a c i l i t y 145 | PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,CHARACTER, 3 . 1 . 3. 1 . ... | CHARACTER,CHARACTER) ; | CODE 4 | OUTPUT := STRING(#STOR REF#) ED MAIN 4 REP %1% OUTPUT := STRING (9M%) . 110 COMPILE ENTER FILE NAME. i 1 The system responds by r e q u e s t i n g an obj e c t f i l e name since t h i s i s the f i r s t time t h a t t h i s program has been compiled. As with e r r o r messages, the request i s d i s p l a y e d f c r about f i v e seconds of r e a l time, then removed from the screen, A Program Development F a c i l i t y |PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,CHARACTER, 3.1.3.1...| CHARACTER,CHARACTER); | CODE U | OUTPUT := STRING (#STOR REF#) 4 REP %n OUTPUT := STRING(^U). I 10 COMPILE OBJECT The user e n t e r s the f i l e name and the c o m p i l a t i o n proceeds. T h i s o b j e c t f i l e name w i l l become attached to t h i s program, and w i l l be preserved by subsequent SAVE commands. The l i s t i n g s c f those procedures compiled (in t h i s case a l l of them) are produced on the f i l e "-LIST" along with any a s s o c i a t e d d i a g n o s t i c s . A Program Development F a c i l i t y 147 IPROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,CHARACTER, 3.1.3.1. ..| CHARACTER,CHARACTER); | CODE 4 | OUTPUT := STRING (#STOR REF#) REP %'\% OUTPUT := STRING | 10 COMPILE OBJECT QUIT The user now decides to leave the system and so he enters the QUIT command. Note t h a t s i n c e he has not checkpcinted h i s workspace by means of the SAVE command, he has l o s t h i s program t e x t . The system stops execution and c o n t r o l of the 3270 r e t u r n s to the standard MTS Device S e r v i c e Routine. A Program Development F a c i l i t y 148 The f o l l o w i n g t e x t i s t h a t produced by the compiler cn the f i l e "-LIST" f o r the COMPILE command i n the sample run. L i k e the screens themselves, t h i s l i s t i n g has been "sguashed" to allow i t s i n c l u s i o n i n the document. The f i l e c o n t a i n s the paragraphed l i s t i n g s of the procedures compiled, the machine code emitted f o r those procedures, and f i n a l l y a t r e e - s t r u c t u r e d l i s t i n g of the procedures of the program. Normally the. l i s t i n g c o n t a i n s t i t l e s and each procedure s t a r t s a new page, but these f e a t u r e s have been removed t o conform to the format of t h i s document. |PROCEDURE MAIN | DATA 3 | INTEGER PROCEDURE HANOI (INTEGER,CHARACT I B , 3.1.3.1...| CHARACTER,CHARACTER) ; | CODE 4 | OUTPUT := STRING ( HANOI (4,"SOURCE","INTER MEDIATE" 4.1.3.2...| ,"DESTINATION")) EMITTED CODE LISTING 0 GPUSH 0 0 19 LITCALL 4 27 SLITCALL "SOURCE" 38 SLITCALL "INTERMEDIATE" 55 SLITCALL "DESTINATION" 70 CALL 184 1 3 76 INTTOSTR 80 PUT 84 SRETURN 4 4.1.2 4.1.2.2 Q • 1 * 2 • 2 • * 4.1.2.3 4.1.3 PROCEDURE HANOI (N, S, I, D) DATA CODE IF N > 0 THEN HANOI (N - 1,S,D,I); OUTPUT := " MOVE PIECE " + STRING (N) + " FROM " + S * " TO " + D + " ." ; HANOI (N - 1 ,I,S,E) ELSE 0 FI EMITTED CODE LISTING 0 GPUSH 1 3 11 LITCALL 0 20 VALCALL G I 1 0 2 6 GT A Program Development F a c i l i t y 149 28 BHANCHF 273 43 LITCAL1 1 52 VALCALL G I 1 0 58 MINUS 65 VALCALL G S 1 0 74 VALCALL G S 1 2 83 VALCALL G S 1 1 89 CALL 184 1 3 94 VOID 111 SLITCALL n • it 118 VALCALL G S 1 2 124 CATENATE 128 SLITCALL n TO n 136 CATENATE 142 VALCALL G S 1 0 148 CATENATE 152 SLITCALL II FROM II 162 CATENATE 172 VALCALL G I 1 0 177 INTTOSTR 181 CATENATE 185 SLITCALL ti MOVE PIECE 201 CATENATE 205 PUT 207 SVOID 218 LITCALL 1 227 VALCALL G I 1 0 233 MINUS 240 VALCALL G S 1 1 249 VALCALL G s 1 0 258 VALCALL G s 1 2 264 CALL 184 1 3 270 BRANCH 283 277 LITCALL 0 286 RETURN MAIN HANOI A Program Development F a c i l i t y 150 I I | Appendix 2 — I n t e r p r e t e r I n s t r u c t i o n Set | I I This appendix describes the order code of the Eighty-One i n t e r p r e t e r . The code i s b a s i c a l l y single-address and byte-o r i e n t e d , with each operation code ta k i n g up a s i n g l e byte f o l l o w e d by a v a r i a b l e number of bytes g i v i n g the operands of that i n s t r u c t i o n . Operation mnemonics used i n t h i s s e c t i o n are those used i n the code l i s t i n g of the compiler. In what f o l l o w s , the term "addr M w i l l be used t c i n d i c a t e a two byte address f o l l o w i n g the op-code and c o n t a i n i n g the four f i e l d s described i n the s e c t i o n on machine addressing s t r u c t u r e . The symbols bl through bn w i l l be used to i n d i c a t e the values of the f i r s t through nth bytes f o l l o w i n g the i n s t r u c t i o n s . I t i s assumed that the reader i s f a m i l i a r with the general s t r u c t u r e of the stacks used w i t h i n the machine as described e a r l i e r . PLUS MINUS TIMES DIVIDE AND OR EQ NE L T GT GE These are the single-address i n t e g e r operations cf the machine corresponding to the i n t e g e r operations of the language. In a l l cases, these i n s t r u c t i o n s pop the the top two e n t r i e s o f f the i n t e g e r s t a c k , perform the reguired operation upon them, and push the r e s u l t back onto the i n t e g e r stack. As stated i n the d e s c r i p t i o n of the language, the r e l a t i o n a l operations r e t u r n r e s u l t s of 0 (false) and 1 ( t r u e ) , while the l o g i c a l operations act upon the 32 b i t i n t e r n a l r e presentations of i n t e g e r s i n tfce standard f a s h i o n . CATENATE This i n s t r u c t i o n pops the top two e n t r i e s from the s t r i n g A Program Development F a c i l i t y 151 s t a c k , concatenates them, and pushes the r e s u l t onto the s t r i n g s t a c k . T h i s o p e r a t i o n may r e q u i r e new storage a l l o c a t i o n and c o u l d a l s o cause a garbage c o l l e c t i o n of the s t r i n g s t a c k , which c o n t a i n s a l l l o c a l and g l o b a l v a r i a b l e s as well as the i n t e r m e d i a t e r e s u l t s of computations. SEQ SHE SLT SGT S LE SGE These i n s t r u c t i o n s , which perform the comparisons of i n d i v i d u a l c h a r a c t e r s t r i n g s , pop t h e i r two arguments from the top of the s t r i n g s t a c k and push t h e i r i n t e g e r r e s u l t s cf e i t h e r 0 or 1 onto the i n t e g e r stack. Comparisons are made using the l e n g t h of the s h o r t e r of the two s t r i n g s , with a longer s t r i n g c o n s i d e r e d to be l e x i c a l l y g r e a t e r than a s h o r t e r one i f the s t r i n g s match to the l e n g t h of the s h o r t e r one. SUBSTB Another s i n g l e address i n s t r u c t i o n , t h i s o p e r a t i o n corresponds to the three-argument v e r s i o n of the SUESTRING f u n c t i o n . The two i n t e g e r arguments, the f i r s t c h a r a c t e r p o s i t i o n and the remaining l e n g t h , are popped o f f the i n t e g e r s t a c k , while the s t r i n g argument i s pepped o f f the s t r i n g stack. A new d e s c r i p t o r f o r the s u b s t r i n g i s c r e a t e d (without a l l o c a t i n g any storage i n the f r e e s t r i n g area) and i s pushed onto the s t r i n g stack. SUBSTRE This i s the two-argument v e r s i o n of the SUESTR i n s t r u c t i o n which takes the remaining p o r t i o n of the s t r i n g from the s p e c i f i e d p o s i t i o n . As would be expected, the i n t e g e r and s t r i n g arguments are popped from t h e i r r e s p e c t i v e s t a c k s , and the r e s u l t i s pushed onto the s t r i n g stack. INTTOSTR Th i s i n s t r u c t i o n , which corresponds to the STRING f u n c t i o n of the language, pops an i n t e g e r from the i n t e g e r stack, c o n v e r t s the i n t e g e r to c h a r a c t e r s , a l l o c a t e s space from the f r e e s t r i n g area f o r these c h a r a c t e r s , c r e a t e s a d e s c r i p t o r f o r t h i s r e p r e s e n t a t i o n , and pushes t h a t d e s c r i p t o r onto the s t r i n g s t ack. LENGTH A Program Development F a c i l i t y 152 T h i s o p e r a t i o n , which corresponds to the LENGTH f u n c t i o n of the language, pops the top s t r i n g from the s t r i n g stack and pushes i t s length onto the i n t e g e r stack. ASSIGN addr T h i s one-address i n s t r u c t i o n takes the top entry from the i n t e g e r or s t r i n g s t a c k (as i n d i c a t e d by the type f i e l d of "addr") and s t o r e s i t i n t o the stack l o c a t i o n named by "addr". The stack i s not popped. ASSIGNSUB addr Another one-address i n s t r u c t i o n , t h i s o p e r a t i o n a s s i g n s the top of the i n t e g e r or s t r i n g stack to the array l o c a t e d by "addr" and indexed by the top n elements of the i n t e g e r stack. The type b i t of "addr" i n d i c a t e s the stack used f o r the assignment, but the remaining p o r t i o n s of the address always r e f e r to the a r r a y d e s c r i p t o r i n the i n t e g e r stack. Since the d e s c r i p t o r c o n t a i n s the number of s u b s c r i p t s f o r the a r r a y , t h i s number i s not i n c l u d e d with the i n s t r u c t i o n . As the s u b s c r i p t s are used, they are popped o f f the i n t e g e r s t a c k , thus exposing the i n t e g e r value to be assigned i f the assignment a p p l i e s to t h a t stack. VOID T h i s i n s t r u c t i o n j u s t pops the i n t e g e r stack, throwing away the v a l u e . I t i s used mainly to d i s c a r d i n t e r m e d i a t e values i n statement sequences. SVOID. The same as VOID, but o p e r a t i n g on the s t r i n g stack. DVOID b1 T h i s i n s t r u c t i o n i s used t o v o i d more than one entry from the i n t e g e r stack a f t e r the c r e a t i o n of jan array d e s c r i p t o r . It pops b1 e n t r i e s from the i n t e g e r stack. GPUSH b1,b2 T h i s i n s t r u c t i o n i s used at' the entry of a procedure to a l l o c a t e g l o b a l storage f o r the simple v a r i a b l e s of t h a t procedure. The i n t e g e r and s t r i n g s t a c k s are pushed by b1 and b2 r e s p e c t i v e l y . In order to maintain the v a l i d i t y of the data s t r u c t u r e s i n v o l v e d , a l l new e n t r i e s a l l o c a t e d cn the s t r i n g stack are set to the n u l l s t r i n g , A Program Development F a c i l i t y 153 A1L0CARRAY b1,addr This i n s t r u c t i o n a l l o c a t e s an array with b1 bounds as s p e c i f i e d by the top b1 e n t r i e s of the i n t e g e r stack. The type b i t s of addr i n d i c a t e the type of the array while the r e s t of the b i t s l o c a t e i t s d e s c r i p t o r i n the integ e r stack. Space reg u i r e d f o r the array i s c a l c u l a t e d from the bounds and the appropriate data stack pointer i s incremented a c c o r d i n g l y . Again, e n t r i e s a l l o c a t e d on the s t r i n g stack are set t o the n u l l s t r i n g . In order to allow the system to a l l o c a t e mere than one array with the same bounds as i s provided f o r i n the syntax of the language, the bounds are not popped from the integ e r stack. o LPUSH b1,b2 This i n s t r u c t i o n i s executed to enter a b l c c k . The re g u i r e d stack p o i n t e r s and other information are pushed onto the l o c a l stack and b1 and b2 c e l l s are a l l o c a t e d cn the in t e g e r and s t r i n g stacks r e s p e c t i v e l y . ENTERDO The required values are pushed onto the do stack. POP The l o c a l stack i s popped, r e s t o r i n g the data stack p o i n t e r s and other values stored by the matching LPUSH i n s t r u c t i o n . In a d d i t i o n , the value at the top of the integ e r stack i s copied down to the new stack top created by pepping the l o c a l v a r i a b l e s of the block e x i t e d . SPOP This i n s t r u c t i o n i s s i m i l a r to the POP i n s t r u c t i o n , but the s t r i n g stack top r a t h e r than the in t e g e r stack top i s moved down. This corresponds to e x i t i n g a block r e t u r n i n g a s t r i n g value. CALL b1,b2,b3 This i n s t r u c t i o n i n i t i a t e s a c a l l of the procedure numbered b1 i n the object module (and hence i n the compiler symbol t a b l e ) . This i n s t r u c t i o n pushes the g l o b a l stack p c i n t e r and s t o r e s such information as the cu r r e n t value of the appropriate d i s p l a y l e v e l and the previous procedure number on that stack. In a d d i t i o n , the d i s p l a y l e v e l f o r the procedure i s updated to contain the current i n t e g e r stack p c i n t e r minus b2 and the current s t r i n g stack p o i n t e r minus b3. This s e t s up the bases f o r the c a l l e d procedure by moving the stack pointers down below A Program Development F a c i l i t y 154 the arguments t o the procedure. RETURN The g l o b a l stack i s popped, r e s t o r i n g the data stack p o i n t e r s , previous procedure base and program counter, and other v a l u e s s t o r e d by the matching CALL i n s t r u c t i o n . As i n the POP i n s t r u c t i o n , the top value of the i n t e g e r stack i s copied down to the newly-created stack top, thus r e t u r n i n g the i n t e g e r value of the procedure. SRETURN S i m i l a r to the RETURN i n s t r u c t i o n , but the s t r i n g r a t h e r than the i n t e g e r value from the top of the data stack i s moved. VALCALL addr T h i s i n s t r u c t i o n pushes the value at the l o c a t i o n i n the data stack r e f e r e n c e d by addr onto the top cf that stack. VALCALLSUB addr T h i s i n s t r u c t i o n c a l l s the value r e f e r e n c e d by addr and indexed by the top values of the i n t e g e r stack onto the a p p r o p r i a t e stack. As i n the ASSIGNSUB i n s t r u c t i o n , s u b s c r i p t s are popped o f f as they are evaluated thus l e a v i n g the top of the i n t e g e r stack f r e e to r e c e i v e i t s new i n t e g e r value shculd addr address the i n t e g e r s t a c k . LITCALL n T h i s i n s t r u c t i o n pushes the value of n onto the i n t e g e r stack. N i s represented by the next four bytes of o b j e c t code. SLITCALL s t r i n g The s t r i n g " s t r i n g " i s a l l o c a t e d storage i n the f r e e s t r i n g area and i t s d e s c r i p t o r i s placed on the top of the s t r i n g stack. The s t r i n g i s represented by the next byte of obj e c t code which giv e s i t s l e n g t h m f o l l o w e d by m bytes g i v i n g the c h a r a c t e r s of the s t r i n g . DESCCALL addr The a r r a y d e s c r i p t o r r e f e r e n c e d by addr i s moved tc the top of the i n t e g e r s t a c k . T h i s o p e r a t i o n i s used to pass array d e s c r i p t o r s as parameters to r o u t i n e s . A Program Development F a c i l i t y 155 BRANCH p l The program l o c a t i o n p l (represented by the next two bytes of o b j e c t code) r e p l a c e s the c u r r e n t value of the program counter i n the i n t e r p r e t e r , thus producing an u n c o n d i t i o n a l branch. BRANCHF p l The value at the top of the i n t e g e r stack i s popped and examined. I f t h a t value i s 0, p l r e p l a c e s the c u r r e n t program counter, otherwise the program counter i s l e f t p o i n t i n g to the byte f o l l o w i n g p l . EXIT p l Information at the top of the do stack i s used to r e s t o r e the values of the i n t e g e r and s t r i n g stack p o i n t e r s and the o l d top e n t r y of the i n t e g e r stack i s copied down to the new stack top thus c r e a t e d . The value of p l a l s o r e p l a c e s the cu r r e n t program counter, causing a branch out of the e n c l o s i n g DO-OD loop. SEXIT p l T h i s i n s t r u c t i o n i s s i m i l a r to the EXIT i n s t r u c t i o n , but the top of the s t r i n g s t a c k i s copied, thus r e t u r n i n g a s t r i n g value from the e n c l o s i n g DG-OD loop. PDSHLOC b1 The value of b1 i s pushed onto the i n t e r p r e t e r l o c a t i o n stack. REPLLOC b1 The value of b1 r e p l a c e s the top value of the i n t e r p r e t e r l o c a t i o n s t a c k . P0PL0C The top value i s popped from the i n t e r p r e t e r l o c a t i o n stack. GET A l i n e i s read from MTS l o g i c a l u n i t SCARDS and moved i n t o the f r e e s t r i n g a r ea. A d e s c r i p t o r f o r the l i n e i s pushed onto A Program Development F a c i l i t y 156 the s t r i n g stack. PUT The s t r i n g represented by the d e s c r i p t o r at the top of the s t r i n g stack i s output on HTS l o g i c a l u n i t SPRINT with i t s f i r s t c h a r a c t e r s e r v i n g as c a r r i a g e c o n t r o l . A Program Development F a c i l i t y 157 | Appendix 3 — SUE Program L i s t i n g s I \ J T h i s appendix c o n t a i n s SUE System Language code f o r the more s i g n i f i c a n t type d e f i n i t i o n s and v a r i a b l e d e c l a r a t i o n s of the Eighty-One system. These program segments are not s t r i c t l y c o r r e c t SUE code, l a r g e l y because the constant d e f i n i t i o n s f o r most of the magic numbers have been e l i m i n a t e d . Hopefully, the v a r i a b l e names are meaningful enough that the c o n s t a n t d e f i n i t i o n s are s u p e r f l u o u s . These long v a r i a b l e names should a l s o e l i m i n a t e the need f o r ex t e n s i v e comments, since the names are both suggestive of the f u n c t i o n s of the types and v a r i a b l e s and s i m i l a r to those used i n the e n g l i s h language d e s c r i p t i o n s of the data s t r u c t u r e s given i n the chapter on system s t r u c t u r e . A Program Development F a c i l i t y 158 data Eighty_One D e f i n i t i o n s ; D e f i n i t i o n s cf v a r i o u s ranges and t y p e s . V £Y.E§ Parse_Node_Index_Type = (1 to Maximum_Parse_Nodes) ; type Parse_Node_Pointer_Type = (0 to Maximum_Parse_Ncdes) ; type String_Area_Index_Type = (0 to Maximum_String_Area) ; type Symbol_Table_Index_Type = (0 to Maximum_Symtcl_Table) ; type String_Table_Index_Type = (1 to Maximum_String_Table) ; i!2§ S t r i n g _ T a b l e _ P o i n t e r _ T y p e = (0 to Maximum_String_Table); £Y.£§ Comment_Table_Index_Type = (1 to Maximum_Ccmment_Table) ; type Comment_Table_Pointer_Type = (0 to Maximum_Comment_Table); type String_Length_Type = (0 to Maximum_String_Length) ; type Character_Buffer_Type = c h a r a c t e r (Maximum_String_Length type E r r o r _ S e v e r i t y _ T y p e = (Message, U s e r _ E r r o r , Abcrt) ; type ln_Use_Flag_Type = ( A c t i v e , I n a c t i v e ) ; type Language_Operation_Type = ( P l u s _ O p e r a t i c n , Minus_Operation, Times_Operation, D i v i d e _ O p e r a t i o n , And_Operation , O r _ 0 p e r a t i o n , E g u a l _ C p e r a t i o n , Not Egual^Operation, Less_Than_Operation, Greater_Than_Operation, Less_Than_Gr_Egual_Operation, Greater_Than_Or_Egual_Operation, Assignment_Operation); type Language_Number_Type = b i t (32) ; /* Types of the language. */ type Internal_Type_Type = (Integer, C h a r a c t e r _ S t r i n g , Unknown); type Language_Type_Type •= (Integer to C h a r a c t e r _ S t r i n g ) ; /* Types of parse nodes used. */ type Parse_Node_Type = (Formula_Node, If_Node, Exit_Node, Do_Node, Number_Node, String_Node, Block_Node, I d e n t i f i e r _ N o d e , Bracketed_Expression_Node, Declaration_S eguence_Node, Expressicn_Seguence_Ncde, V a r i a b l e Declaration_Node, Procedure Declaration_Node, I d e n t i f i e r _ L i s t _ N o d e , E x p r e s s i o n _ L i s t _ N ode, ); /* Operators of the language. V A Program Development F a c i l i t y 159 Parameters_Node, Formal_Parameters_Ncde, Compilation_Unit_Node, Accepts_Type_Ncde, Type_List_Node, Type_Ncde, Bounds_Node, Bound_List_Node) ; * * * D e f i n i t i o n of a parse node. * * * type Parse_Node = re c o r d , Parse_Node_Pointer_Type (Backward_Link), case Parse_Node_Type tag Node_Tag; Formula_Node: Comment_Table_Pointer_Type (Operator_Comment), Language_Operation_Type (Operation), Parse_Node_Pcinter_Type (Left_Operand, Right Operand) ; If_Node: Comment_Table_Pointer_Type (If_ Comment, Then_Comment, Else_Comment, Fi_Comment), Parse_Node_Pointer_Type ( I f _ C o n d i t i o n , T r u e _ A l t e r n a t i v e , F a l s e _ A l t e r n a t i v e ) ; Exit_Node: Comment_Table_Pointer_Type (Exit_Comment, With_Comment) , Parse_Node_Pointer_Type ( E x i t _ C o n d i t i o n ) ; Do_Node: Comment_Table_Pointer_Type (Do_Comment, Od_Corament), Parse_Node_Pointer_Type (Seguence_To_Repeat); Number_Node: Comment_lable_Pointer_Type {Uumber_Comment), Language_Number_Type (Number_Representation); String_Node: Comment_Table_Pointer_Type (String_Comment), String_Table_Index_Type ( S t r i n g _ R e p r e s e n t a t i o n ) ; Block_Node: Comment_Table_ Pointer_Type (Eegin_Comment, End_Comment), Parse_Node_Pointer_Type ( D e c l a r a t i o n s , Statements); I d e n t i f i e r _ M o d e : Comment_Table_Pointer_Type (Identifier_Comment), Symbol_Table_Index_Type ( I d e n t i f i e t _ I n d e x ) , Parse_Node_Pointer_Type (ftctual_Parameters) ; Bracketed_Expression_Node: Comment_Table_Pointer_Type (Open_Comment, Close_Comment), Parse_Node_Pointer_Type ( B r a c k e t e d _ E x p r e s s i c n ) ; Declaration_Sequence_Node: Comment_Table_Pointer_Type ( Declaration_Sequence_Semicolon_Comment), Parse_Node_Pointer_Type ( D e c l a r a t i o n , N e x t D e c l a r a t i o n ) ; Expression_Seguence_Node: A Program Development F a c i l i t y 160 Comment_Table_Pointer_Type ( Expression_Seguence_Semicolon Comment), Parse_Node_Pointer_Type (Expression_Of_Seguence, Next_Expression_Of_Seguence); V a r i a b l e _ D e c l a r a t i o n _ N o d e : Comment_Table_Pointer_Type (Variable_Type Comment), Language_Type_Type (Type_Of_Variable) , Parse_Node_Pointer_Type (Bound_List, V a r i a b l e _ L i s t ) ; Procedure Declaration_Node: Comment_Table_Pointer_Type (Prccedure_Type_Comment, Procedure Comment, P r o c e d u r e _ I d e n t i f i e r Comment), Language_Type_Type (Procedure_Beturns_Type), Symbol Table_Index Type ( P r o c e d u r e _ I d e n t i f i e r Index ) , Parse_Node_Pointer_Type (Procedure_Accepts_Types); I d e n t i f i e r _ L i s t _ N o d e : Comment_Table_Pointer_Type ( I d e n t i f i e r _ L i s t _ I d e n t i f i e r Comment, Identifier_IistComma_Comment), Symbol_Table_Index_Type " ( T h i s _ I d e n t i f ier_Index) , Parse_Node_Pcinter_Type ( K e x t _ I d e n t i f i e r ) ; E xpression_List_Node: Comment_Table_Pointer_Type ( E x p r e s s i o n _ L i s t Comma Comment), Parse_Node_Pointer_Type ( E x p r e s s i o n _ O f _ L i s t , N e x t _ E x p r e s s i o n _ O f _ L i s t ) ; Parameters_Node: Comment_Table_Pointer_Type (Parameter£_Open_Comment, Para meters Close Comment) , Parse_Node_Pointer_Type (Parameters_Pointer); Formal_Parameters_Node: Comment_Table_Pointer_Type ( Formal_Parameters_ 0pen Comment, Formal_Parameters Close Comment), Parse_Node_Pointer_Type (Formal_Parameters_Pointer); Compilation_Unit_Node: Comment_Table_Pointer_Type (Unit_P rocedure Comment, U n i t _ I d e n t i f i e r Comment, Data Comment, Code Comment) , Symbol_Table_Index_Type ( U n i t _ I d e n t i f i e r _ I n d e x ) , Parse_Node_Pointer_Type (Formal_Parameters, U n i t _ D e c l a r a t i o n s , Dnit_Statements) ; Accepts_Type_Node: Comment_Table_Pointer_Type (Accepts_ 0pen Comment, A c c e p t s C l o s e Comment) , Parse_Node_Pointer_Type (Accepts_Types); Type_List_Node: Comment_Table_Pointer Type (Type L i s t Comma Comment ), Parse_Node_Pointer_Type (This_Type, Next_T5pe) ; Type_Node: Comment_Table_Pointer_Type (Type_Type_Comment), Language_Type_Type (Type_Of_Type), Parse_Node_PoInter_Type "(Type_Bound_List) ; Bounds_Node: Comment_Table_Pointer_Type (Bounds_Open_Comment, A Program Development F a c i l i t y 161 Bounds Close Comment) , Parse_Node_Pointer_Type (Eounds); Bound_List_Node: Comment_Table_Pointer_Type ( Bound_List Comma Comment), Parse_Node_PoInter_Type (Next_Eound) end end; /* S t r i n g d e s c r i p t o r f o r a symbol t a b l e entry. */ type Symbol_Table_Entry_Type •= record case In_Use_Flag_Type tag Symbol_Table_Flag; I n a c t i v e : A c t i v e : Terminal_Symbcl_Type (Type_Cf_Symbol), String_Length_Type (Length_Of_Symbol) , String_Area_Index_Type (First_Character_Of_Symbol) end end; /* S t r i n g d e s c r i p t o r f o r a s t r i n g table entry. V type String_Table_Entry_Type = record case In_Use_Flag_Type tag S t r i n g _ T a b l e _ F l a g ; I n a c t i v e : String_Table_Pointer_Type (Next_Free_String); A c t i v e : String_Length_Type (Length_Cf_String), String2Area_Index_Type ( F i r s t _ C h a r a c t e r _ O f _ S t r i n g ) end end ; /* S t r i n g d e s c r i p t o r f o r a comment t a b l e entry. */ type Comment_Table_Entry_Type = record case In_Use_Flag_Type tag Comment_Table_Flag; I n a c t i v e : Coinment_Table_Pointer_Type (Next_Free Comment) ; A c t i v e : * Comment_Table_Pointar_Type (Next Comment) , String_length_Type (Length_Cf_Comment), String_Area_Index_Type (First_Character_Of Comment), Boolean (First_Thing_On_Line) end A Program Development F a c i l i t y 162 end ; /* Types to f i n d our p l a c e i n the parse t r e e . * * * F i r s t , enumerate the p o s s i b l e cases. */ tyjae P o s i t i o n _ I n d i c a t o r _ T y p e _ T y p e = ( I n v a l i d _ P o s i t i o n , T r e e _ P o s i t i o n , O p e r a t o r _ P o s i t i o n , I d e n t i f i e r _ P o s i t i o n , T y p e _ P o s i t i o n , Bound_Position); /* Record d e f i n i n g v a r i o u s types of p o s i t i o n s . */ type P o s i t i o n _ I n d i c a t o r _ T y p e = re c o r d case P o s i t i o n _ I n d i c a t o r _ T y p e _ T y p e tag P o s i t i o n _ T a g ; I n v a l i d _ P o s i t i o n : T r e e _ P o s i t i o n : Parse_Node_Pointer_Type ( P o s i t i c n _ S u b t r e e ) ; Opera t o r _ P o s i t i o n : Comment_Table_Pointer_Type ( Position_Cperation_Comment), Language_Operation_Type ( P o s i t i c n _ O p e r a t i c n ) ; I d e n t i f i e r _ P o s i t i o n : Comment_Table_Pointer_Type ( Po s i t i o n _ I d e n t i f i e r _ C o m m e n t ) , Symbol_Table_Index_Type ( P o s i t i o n _ I d e n t i f i e r ) ; T y p e _ P o s i t i o n : Comment_Table_Pointer_Type (Fosition_Type_Comment), Language_Type_Type (P o s i t i o n _ T y pe) ; Bound_Position: end end; /* S t u f f to handle the obj e c t f i l e . * * When " o b j e c t _ f i l e _ d e f i n e d " , " o b j e c t _ f i l e _ n a m e " * * co n t a i n s the HTS filename of the o b j e c t f i l e . */ d e c l a r e Boolean ( O b j e c t _ F i l e D e f i n e d ) , c h a r a c t e r ( G e t f d _ S t r i n g _ l e n g t h ) (Cbject_File_Name) ; /* G l o b a l d e c l a r a t i o n s t o handle fr e e l i s t s of s t r i n g and * * comment comment d e s c r i p t o r s . */ d e c l a r e String_Table_Pointer._Type ( F i r s t _ F r e e _ S t r i n g ) , Comment_Table_Pointer_Type (First_Free_Comment); /* D e c l a r a t i o n s f o r t a b l e s a l l o c a t e d from GETS PACE. * * * * F i r s t , the s t r i n g area. */ type String_Area_Type = array (String_Area_lndex_Type) cf A Program Development F a c i l i t y 163 c h a r a c t e r (1); /* Type of maximum ar r a y of parse nodes. */ type Parse_Node_Area_Type = array (Parse_Node_Index_Type) of Parse_Node; /* P o i n t e r s to v a r i o u s a r r a y s . */ d e c l a r e p o i n t e r to String_Area_Type ( S t r i n g _ A r e a ) , p o i n t e r to Parse_Node_Irea_Type (Parse_Ncde_Area) ; /* Free l i s t v a r i a b l e s f c r parse nodes. */ d e c l a r e Parse_Node_Pointer_Type (Next_Parse_Ncde_To_Allocate), Parse_Node_Index_Type (Number_Of_Parse_Nodes_Allccated); /* A l l o c a t i o n v a r i a b l e s f o r s t r i n g s p o i n t e d t o ty * * d e s c r i p t o r s . */ d e c l a r e String_Area_lndex_Type ( N e x t _ S t r i n g _ T c _ A l l o c a t e , S t r i n g _ A r e a _ S i z e , Next_String_Area_Size) ; / * * * D e f i n i t i o n s f o r the 3270 screen support. * * * * F i r s t , d e f i n i t i o n s of types and ranges. * type Tv_Line_Type = c h a r a c t e r (Tv_Screen_Width) ; type Display_Area Index Type = (0 to D i s p l a y Area_Length - 1 ); type Entry_Area_Index_Type = (0 to Maximum_Entry_Area) ; type C i r c u l a r _ E n t r y _ B u f f e r _ P o i n t e r _ T y p e = b i t (32); type Tv_Line_Index_Type = (0 to Tv_Screen_Width) ; /* Record r e c o r d i n g a past p o s i t i o n i n the input area. */ type Input_Checkpoint_Type = record ~ C i r c u l a r _ E n t r y _ B u f f e r _ P o i n t e r _ T y p e ( P r e v i o u s _ E n t r y _ P o s i t i o n ) , f a s t Tv_Line_Index_Type ( P r e v i o u s _ L i n e _ P o s i t i o n ) , Boolean (Previous_New_Line_Flag) end; /* V a r i a b l e s to maintain the screen. */ A Program Development F a c i l i t y d e c l a r e C i r c u l a r _ E n t r y _ E u f f e r _ P o i n t e r _ T y p e (Entry_Area_fiead, Entry_Area_Pointer) , f a s t Tv_Line_Index_Type ( E n t r y _ I i n e _ F o s i t i o n ) , Boolean (fiead_New_Iine), Input_Checkpoint_Type (Main_Scanner_Checkpoint), Tv_Line_Type ( E r r o r _ H e s s a g e _ I i n e ) , a r r a y (Display_Area_lndex_Type) of Tv_Line_Type ( D i s p l a y _ A r e a ) , a r r a y (Entry_Area_lndex_Type) of Tv Iine_Type (Entry_Area * * * D e f i n i t i o n s to maintain r e c o m p i l a t i o n i n f o r m a t i o n . * F i r s t , the v a r i o u s s t a t u s e s of procedures. * type Recompilation_Flag_Type = (Unused, V a l i d , Subseguent_Block A l t e r e d , Program_Elock_Altered, D a t a _ B l o c k _ A l t e r e d ) ; constant Symbol_Table_Null = - 1; type Symbol_Table_Pointer_Type = (Symbol_Table_Null to Maximum_Symbol_Table); /* An entry i n the r e c o m p i l a t i o n t a b l e . */ type Recompilation_Table_Entry_Type = re c o r d Parse_Node_Pointer_Type ( U n i t _ L i n k ) , Boolean (Code_Generated), case Recompilation_Flag_Type tag Recompilation__Tag; Unused:Da t a _ B l o c k _ A l t e r e d : Valid:Subseguent_Block_Altered:Program_Elock_Altered: Symbol_Table_Pointer_Type (Father_Unit, B r o t h e r _ U n i t , Son_Unit) end end; /* P o i n t e r to r o o t of procedure t r e e i n symbol t a b l e . */ declare Symbol_Table_Pointer__Type (Top_level) ; /* D e c l a r a t i o n s f o r the s t a t i c a l l y a l l o c a t e d t a b l e s . */ d e c l a r e a r r a y (Symbol_Table_Index_Type) cf Symbol_Table_Entry_Type (SymboT_Table), A Program Development F a c i l i t y 165 array (String_Table_Index_Type) of String_Table_Entry_Type (String_Table) , a r r a y (Comment_Table_Index_Type) of Comment_Table_Entry_Type (Comment_Table), array (Symbol_Table_Index_Type) of Reccmpilation_Table_Entry_Typetype Paragrapher_Depth_Type = (0 to Maximum_Paragrapher_Depth); /* Modes of o p e r a t i o n f o r the paragrapher. */ £Y.E<= Paragrapher_Mode_Type = (Tv_Screen, P r i n t e r ) ; /* D e f i n i t i o n f o r " i n v i s i b l e " t e r m i n a l s used to " d i r e c t " * * the parser toeards the c o r r e c t parse. */ ty_pe Parse_Target_Type = (Accepts_Type_Opticn_Target to T y p e _ L i s t _ T a r g e t ) ; /* - Types of tokens returned by the l o w - l e v e l scanner. */ type Token_Type_Type = (Open_Token, Clese_Token, Conma_Token, Semicolcn_Token, Percent_Token, Period_Token, Operator_Token, Number_Token, String_Token, I d e n t i f i e r J T o k e n , Comment_Token); /* Record d e s c r i b i n g token returned by low l e v e l scanner. */ * l i E S Token_Type = record case Token__Type_Type tag Token_Tag; Operator_Token: Language_0pefation_Type (Token_Operator); Number_Token: Language_Number__Type (Token_Number) ; String_Token: f a s t String_Length_Type (Token_String_Length), Character_Buffer_Type (Token_String C h a r a c t e r s ) ; I d e n t i f i e r _ T o k e n : f a s t String_Length_Type ( I d e n t i f i e r _ S t r i n g _ L e n g t h ) , C h a r a c t e r _ B u f f e r Type ( I d e n t i f i e r _ S t r i n g C h a r a c t e r s ) ; Comment_Token: Boolean ( F i r s t _ T o k e n _ O n _ I i n e ) , f a s t String_Length_Type (Comment_String_Length), Character_Buffer_Type (Comment_String Characters) end end; /* Token r e t u r n e d by i n t e r f a c e between low l e v e l scanner * * and p a r s e r . */ type Scanned_Symbol_Type = A Program Development F a c i l i t y 166 r e c o r d Comment_Table_Pointer_Type (Symbol_Comment), case Terminal_Symbol_Type tag Scanned_Symbol_Tag; Accepts_Type_Option_Symbol to Declaration_Seguence_Symbol:Expression_Symbcl t c Type_List_Symbol: Parse_Node_Pointer_Type (Tree_Portion) ; Declaration_Type_Symbol: Language_Type_Type (Declared_To_Be); I d e n t i f i e r _ S y m b o l : Symbol_Table_Index_Type ( I d e n t i f i e r _ L o c a t i o n ) ; Number_Symbol: Language_Number_Type (Number_Value); Operator_Symbol: Language_Operation_Type (Cperator_Value); String_Symbol: String_Table_Index_Type ( S t r i n g _ V a l u e ) ; e l s e : end end ; /* Types f o r v a r i o u s e n t r i e s on the parse s t a c k . */ tyjae Stack_Element_Type = (Symbol_Cn_Stack, Node_On_St ack, List_On_Stack, Declaration_Cn_Stack, Nothing_On_Stack); /* Entry on parse stack according to type. */ typ_e Parse_Stack_Element_Type = r e c o r d State_Type ( S t a t e ) , case Stack_Element_Type tag Type_Cf_Element; Symbol_On_Stack: Scanned_Symbcl_Type (Symbol); Node_On_Stack: Parse_Node_Pointer_Type (Node_Pcinter); L i s t _ O n _ S t a c k : Parse_Node_Pointer_Type (List_Head, L i s t _ T a i l ) ; D eclaration_On_Stack: Language_Type_Type (Type_Of D e c l a r a t i o n ) , Comment_Table_Pointer_Type (Type_Comments) ; Nothing_on_Stack: end end; /* Parser v a r i a b l e s . */ d e c l a r e a r r a y (Parse_Stack_Index_Type) of Parse_Stack_Element_Type (Parse_Stack), f a s t Parse_Stack__Index_Type (Stack_Pcinter) , Scanned_Symbol_Type (Last_Symbol_Scanned), A Program Development F a c i l i t y 167 Boolean ( P a r s e r _ A c t i v e , Scanned_Symbol_Valid), ' f§§£ Comment_Table_Pointer_Type (Comment^is^Head, Comment_List_Tail); /* Record d e s c r i b i n g f i r s t l i n e of checkpoint f i l e . */ typ_e Checkpoint_Record_Type = r e c o r d b i t (32) ( C h e c k p o i n t _ I d e n t i f i c a t i o n ) , Cdate_Date_Type (C_Date_Saved), String_Area_Index_Type (C_Next_String_To_ A l l o c a t e , C _ S t r i n g _ A r e a _ S i z e , C _ N e x t _ S t r i n g _ A r e a _ S i z e ) , Parse_Node_Pointer Type (C Next_Parse Node To A l l o c a t e ) , Parse_Node_Index_Type ( C_Number_Of_Parse_Nodes_A11ocated), S t r i n g _ T a b l e _ P o i n t e r _ T y p e ( C _ F i r s t _ F r e e _ S t r i n g ) , Comment_Tafcle_Pointer_Type ( C _ F i r s t _ F r e e Comment), Symbol_Table_Pointer_Type ( C _ T o p _ l e v e l ) , Boolean ( C _ O b j e c t _ F i l e _ D e f i n e d ) , £ h§I3£lSI^ G e t f3_String_Iength) (C_Object_File_Name) end; /*************************************************** ********' * * * D e s c r i p t i o n s of some machine f e a t u r e s . * * * ******************************************************* /* Array d e s c r i p t o r format: * * * * word 0 - number of s u b s c r i p t s * * word 1 - p o i n t e r to f i r s t l o c a t i o n i n a r r a y * * words 2... N+1 - bounds of array */ constant Descriptor_Overhead = 2; constant B a s e _ P o i n t e r _ O f f s e t = 1 ; /* The i n t e r p r e t e r i n s t r u c t i o n set. */ type Machine_Operation_Type = /* F i r s t , the simple i n t e g e r o p e r a t i o n s . */ (Plus_Op, Minus_Op, Times_Op, Divide_Cp, And_Cp, Cr_Cp, Egual_Op, Not_Egual_Op, Less_Than_Op, Greater_Than_Op, Less_Than_Or_Equal_Op, Greater_Than_Cr_.Egual_Op, /* Simple s t r i n g o p e r a t i o n s . */ Catenate_Op, String_Egual_Op, String_Not_Equal_Cp, String_Less_Than_Op, String_Greater_Than_0 p, S t r i n g _ L e s s _ T han_Or_Equal_Op, String_Greater_Than_Cr_Egual_Gp, /* S u b s t r i n g o p e r a t i o n s . */ A Program Development F a c i l i t y 168 Substring_Op , Substring_To_End_Op, /* Conversion o p e r a t i o n s . */ Integer_To_String_Op, Length_Op, /* Assignment o p e r a t i c n s . */ Assign_Op, Assign_Subscripted_Op, /* A l l o c a t i o n and stack manipulation o p e r a t i o n s . */ Void_Integer_Op, Void_String_Op, Void_Descriptor_Op, Push_Global_Display_Gp, Allocate_Array_Op, Push Display_Op, Enter_Do_Op, Pop_Display_Integer_0p, Pop_Display_String_Op, /* Subroutine o p e r a t i c n s . */ C a l l _ O p , Return_Integer_Op, Return_String_Op, /* Stack l o a d i n g o p e r a t i c n s . */ Value_Call_Op, I n t e g e r _ L i t e r a l _ C a l l _ C p , S u b s c r i p t _ C a l l _ O p , S t r i n g _ L i t e r a l _ C a l l _ O p , D e s c r i p t o r _ C a l l _ O p , /* Branch o p e r a t i o n s . */ Branch_Op, Branch_False_Op, Exit_Integer_Op, E x i t _ S t r i n g _ O p , /* L o c a t i o n o p e r a t i o n s . */ Push_Location_Op, Replace_Location_Cp, Fop_Location_Gp, /* Input-output o p e r a t i c n s . */ Get_Op, Put_Op) ; /* Types o f i n t e r n a l v a r i a b l e s of the machine. */ type Display_Index_Type = (0 to Maximum_Display_Index) ; type Access_Level_Type = ( L o c a l , Global) ; type Offset_Type = (0 t c Maximum_Offset); type Subscript_Number_Type = (0 to Maxiraum_Subscripts) ; type Program_Counter_Type = (0 to Maximum_Code_Area); type Byte = b i t ( 8 ) ; /* I n t e r n a l data address d e s c r i p t i o n . */ type Machine_Address_Type = A Program Development F a c i l i t y 169 group b i t (16) ; LanguagejT ype_Type (Type_Bit) , Access_Level_Type ( A c c e s s _ B i t ) , Display_Index_Type ( D i s p l a y _ B i t s ) , Offset_Type ( O f f s e t _ B i t s ) end; /* Object f i l e format: * * * * l i n e -1 - i n f o r m a t i o n about prcgram as i n * * "program_info_type". * * l i n e n - i n f o r m a t i o n about the procedure as i n * * " p r o c e d u r e _ i n f o _ t y p e " . (n i s the number of the * * procedure i d e n t i f i e r i n the symbol t a b l e ) . * * l i n e n. 001 - the procedure name. * * l i n e s n. 002... The procedure cede. V /* Record c o n t a i n i n g i n f o r m a t i o n about the e n t i r e program * * . */ type Program_Info_Type = record Symbol_Table_Index_Type ( E n t r y _ P o i n t ) , Boolean (Invalid_Program) end; /* Record c o n t a i n i n g i n f o r m a t i o n about an i n d i v i d u a l * * procedure. */ type Procedure_Info_Type = r e c o r d Program_Counter_Type (Program_Size), Display_lndex_Type (Program_level) end; /*********************************************************** * The main compiler data s t r u c t u r e s . * * * * F i r s t , the ranges of v a r i a b l e s . * * * *************************************** ty£§ Error_Message_Count_Type = (0 to Maximum_Errcrs); type Syt_Pointer_Type = (0 to Maximum_Syt_Size); type Exit_Index_Type = (0 to Maximum_Exits); type Do_Index_Type = (0 t o Maximum_Hested_Dcs); /* O f f s e t s i n the run stack are t r e a t e d as a p a i r - cne * * i n each data s t a c k . */ type Run_£tack_Offset_Type = a r r a y (language_Type_Type) of Offset_ T y p e ; A Program Development F a c i l i t y 170 /* T h i s type holds both l o c a l and g l o b a l o f f s e t s . */ type Current_Stack_Offset_Typa = array (Access_Le vel_T ype) of Bun_Stack _ o ffset_Type; /* T h i s type h o l d s the c u r r e n t l e v e l f o r both l o c a l and * * g l o b a l data. */ ty_£e Current_Level_Type = array (Access_Level_Type) cf (- 1 to Maximum _ D i s p l a y _ I ndex) ; /* Types of e n t r i e s on the symbol stack. */ type Syt_Tag_Type = (Sim p l e _ V a r i a b l e , A r r a y _ V a r i a b l e , Function, B u i l t i n _ F u n c t i o n ) ; /* The types of b u i l t i n f u n c t i o n s a v a i l a b l e . */ type B u i l t i n _ F u n c t i o n _ T y p e = (Get_Function, P u t _ F u n c t i o n , I n t e g e r _ T o _ S t r i n g _ F u n c t i o n , S u b s t r i n g _ F u n c t i o n , Length_Function) ; /* Type d e s c r i b i n g an entry on the symbol stack. */ type Syt_Entry_Type = r e c o r d Symbol_Table_Index_Type (Syt_Back_Link), Syt_Pointer_Type (Previous_Syt_Entry) , case Syt_Tag_Type tag Syt_Tag; S i m p l e _ V a r i a b l e : Language_Type_Type (Simple_Variable_Type), Access_Level_Type (Simple_Variable_Access) , Display_Index_Type ( V a r i a b l e _ L e v e l ) , 0ffset_TYPe ( V a r i a b l e _ O f f s e t ) ; A r r a y _ V a r i a b l e : Language_Type_Type (Arr a y _ V a r i a b l e _ T y p e ) , Access_Level_Type ( A r r a y _ V a r i a b l e _ A c c e s s ) , Subscript_Number_Type (Number_Of_Subscripts), Display_Index_Type ( D e s c r i p t o r _ L e v e l ) , 0 f f s e t _ T y p e ( D e s c r i p t o r _ 0 f f s e t ) ; F u n c t i o n : Parse_Node_Pointer_Type (Function_Pointer) ; B u i l t i n _ F u n c t i o n : B u i l t i n _ F u n c t i o n _ T y p e (Function_Name) end end; /* Type d e s c r i b i n g an e n t r y on the do stack. */ type Do_Stack_Entry_Type = record Internal_Type_Type ( E x i t _ T y p e ) , Exit_Index_Type (Branch_Stack_Pointer) A Program Development F a c i l i t y 171 end; /* Type d e s c r i b i n g an e n t r y on the l o c a l s t a c k . */ type Local_Stack_Entry_Type = r e c o r d Run_Stack_Offset_Type (Local_Of f s e t ) , Syt_Pointer_Type (Local_Syt) end; /* Type d e s c r i b i n g an entry on the g l o b a l stack. */ type Global_Stack_Entry_Type = r e c o r d ~Run_Stack _ o ffset_Type (Global_Gf f s e t ) , Syt_Pointer_Type (Global_Syt) end ; /* D e c l a r a t i o n s f o r some simple v a r i a b l e s . */ d e c l a r e Display_Index_Type (Altered_Data Count) , Symbol_Table_Pointer_Type (Subsequent_Procedure_Eead, Subsequent_Procedure_Tail), Internal_Type_Type (Compile_Result_Type), Current_Stack_Offset_Type ( C u r r e n t _ S t a c k _ O f f s e t ) , Error_Message_Count_Type (Error_Message Count) , Access_Level_Type (Current_Access), Current_Level_Type ( C u r r e n t _ L e v e l ) , Program Counter_Type (Program Counter), f a s t (- 1 to Maximum_Paragrapher Depth) ( Location_S t a c k _ P c i n t e r ) , Do_Index_Type (Do_Stack_Pointer), Exit_Index_Type ( E x i t _ S t a c k _ P o i n t e r ) , f a s t Syt_Pointer_Type ( S y t _ P o i n t e r ) , Fdub (Object_File_Fdub) , Mts_Line_Length_Type (Line_Length), Mts_Modifier_Type ( M o d i f i e r s ) , Mts_Line_Number_Type (Line_Number); /* D e c l a r a t i o n s of the l a r g e r a r r a y s . */ d e c l a r e array (Program_Counter_Type) of Byte (Program_Area), array (Paragrapher_Depth_Type) of Paragrapher_Width_Type ( Location_S tack) , a r r a y (Paragrapher_Depth_Type) of Ercgram_Ccunter_Type ( L a s t _ L o c a t i o n _ I n s t r u c t i o n ) , array ((1 to Maximum_Nested_Dos)) of Do_Stack_Entry_Type ( Do_Stack), a r r a y ((1 to Maxiraum_Exits)) of Program Ccunter_Type ( E x i t _ S t a c k ) , a r r a y (Display_Index_Type) of Local_Stack_Entry_Type ( L o c a l _ S t a c k ) , a r r a y ( (T to Maximum_Syt_Size)) of Syt_Entry_Type (Syt) , array (Display_Index_Type) of Global_Stack_Fntry_Type ( A Program Development F a c i l i t y 1 7 2 G l o b a l _ S t a c k ) , array (Symbol_Table_Index_Type) of Syt_Pointer_Type ( -Symbol_Table_To_Syt) ; ~ type Stack_Pointer_Type = (- 1 to Haximum_Stack); type Global_S tac k^_Pointer_Type = (0 to Maximum_Global_Stack) ; type L o c a l _ D i s p l a y _ P o i n t e r _ T y p e = (- 1 to naximum_Local_Display) ; type Do_Stack_Pointer_Type = (- 1 to naximum_Dc_Stack) ; type L o c a t i o n _ S t a c k _ P o i n t e r _ T y p e = |- 1 to Maximum_Location_Stack); type Code_Area_Type = a r r a y (Program_Counter_Type) of Byte; type Procedure_Base_Type = p o i n t e r to Code_Area_Type; type String_Area_Index_Type = (0 to String_Area_Maximum); /* The types of program e x c e p t i o n s . */ type Trap_Type = (String_Too_Long, Integer_Stack_Overflow, B a d _ S u b s t r i n g _ P o s i t i o n , Bad_Substring_Length, String_Stack_Overflow, N e g a t i v e _ S u b s c r i p t , S u b s c r i p t _ T o o _ l a r g e , L o c a l _ D i s p l a y _ O v e r f l o w , Do_Stack_Overflow, G l o b a l _ S t a c k _ 0 v e r f l o w , Location_Stack_Overflow, S t r i n g _ A r e a _ C v e r f l o w ) ; /* A s t r i n g d e s c r i p t o r i n the i n t e r p r e t e r . */ type S t r i n g = r e c o r d String_Length_Type ( L e n g t h _ O f _ S t r i n g ) , String_Area_lndex_Type ( F i r s t _ C h a r a c t e r _ C f _ S t r i n g ) end; /* A g l o b a l d i s p l a y e n t r y . */ type Display_Entry_Type = r e c o r d Stack_Pointer_Type (Integer_Sp, String_Sp) end; /* A g l o b a l stack e n t r y . */ A Program Development F a c i l i t y 173 type Global_Stack_Entry_Type = r e c o r d Symbol_Table_Index_Type (Previous_Procedure_Number), Program_Counter_Type ( P r e v i o u s _ P r o g r a m C o u n t e r ) , L o c a l _ D i s p l a y _ P c i n t e r _ T y p e ( P r e v i o u s _ L o c a l _ D i s p l a y _ P o i n t e r ) , L o c a t i o n _ S t a c k _ P o i n t e r _ T y p e ( P r e v i o u s _ L o c a t i o n _ S t a c k ) , Display_Entry_Type (Previous_Display_Intr y) end; /* Procedure t a b l e e n t r i e s b u i l t by the loader. */ type Procedure_Table_Entry_Type = record Procedure_Info_Type ' ( S u p p l i e d _ l n f c ) , Procedure_Base_Type (Load_Point) end; /* A do stack e n t r y . */ type Do_Stack_Entry_Type = r e c o r d Display_Entry_Type (Sp_At_Entry), L o c a l _ D i s p l a y _ P o i n t e r _ T y p e (Display_Tcp_At E n t r y ) , Location_S tack_Pointer_Type (Location_Stack_A t_Entry) end; /* The main i n t e r p r e t e r v a r i a b l e s . */ d e c l a r e String_Area_Index_Type ( N e x t _ S t r i n g _ T c _ A l l o c a t e ) , f a s t L o c a l _ D i s p l a y _ P c i n t e r _ T y p e ( L o c a l _ D i s p l a y _ P c i n t e r , L oca 1_D i sp l a y_T op), f a s t Display_lndex_Type ( C u r r e n t _ G l c b a l _ L e v e l ) , f a s t Do_Stack_Pointer_Type (Do_Stack_Pointer), f a s t G l o b a l _ S t a c k _ P o i n t e r _ T y p e ( G l o b a l _ S t a c k _ P c i n t e r ) , f a s t L o c a t i o n _ S t a c k _ P o i n t e r _ T y p e ( L o c a t i c n _ S t a c k _ P o i n t e r ) , f a s t Program_Counter_Type (Program_Ccunter), f a s t Symbol_Table_Index_Type (Current_Procedure_Number), Procedure_Base_Type (Procedure_Ease), Mts_Modifier_Type ( Z e r o _ H o d i f i e r s ) , f a s t Stack_Pointer_Type ( I n t e g e r _ S t a c k _ P o i n t e r , S t r i n g _ S t a c k _ P o i n t e r ) ; /* The d e c l a r a t i o n s f c r the i n t e r p r e t e r a r r a y s . */ d e c l a r e ( (0 £2 Maximum_Stack)) of language_Number_Type ( Integer_Stack) , §I£SI ((0 12 Maximum_Stack) ) of S t r i n g ( S t r i n g _ S t a c k ) , array (Display_Index_Type) of Display_Entry_Type ( G l o b a l _ D i s p l a y ) , §.££§.1 ((0 £2 Maximum_Iocal_Display)) cf Display_Entry_Type ( L o c a l _ D i s p l a y ) , array ((0 to Maximum_Do_Stack) ) of Do_Stack_Entry_Type ( Dc_S tack)", ~ ~ A Program Development F a c i l i t y 174 a r r a y (Global_Stack_Pointer_Type) of Global_Stack_Entry_Type ( G l o b a l _ S t a c k ) , array (Symbol_Table_Index_Type) of Procedure_Table_Entry_Type (Procedure_Table), array ( (0 to Maximum_Location_Stack)) of Paragrapher_Width_Type ( L o c a t i o n _ S t a c k ) , array ((0 to String_Area_Maximum - 1)) of c h a r a c t e r (1) ( String_Area) 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051760/manifest

Comment

Related Items