UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Software Portability : Theory and Practice Kalicharan, Noel 1976

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_1976_A6_7 K34.pdf [ 4.46MB ]
Metadata
JSON: 831-1.0051773.json
JSON-LD: 831-1.0051773-ld.json
RDF/XML (Pretty): 831-1.0051773-rdf.xml
RDF/JSON: 831-1.0051773-rdf.json
Turtle: 831-1.0051773-turtle.txt
N-Triples: 831-1.0051773-rdf-ntriples.txt
Original Record: 831-1.0051773-source.json
Full Text
831-1.0051773-fulltext.txt
Citation
831-1.0051773.ris

Full Text

C-. Software P o r t a b i l i t y - Theory and P r a c t i c e by Noel K a l i c h a r a n B.Sc. (Hons) , U n i v e r s i t y of the West I n d i e s , 1973, A T h e s i s Submitted i n P a r t i a l F u l f i l l m e n t of the Requirements f o r the Degree of Master of Science i n the Department of Computer Science 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 June 1976 (c) Noel K a l i c h a r a n , 1976 In p r e s e n t i n g 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 r e q u i r e m e n t s f o r an advanced degree at the 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 , I a g r ee t h a t t he L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r ag ree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y pu rpo se s may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f CpMPtneg. ^ C ^ N J C E The U n i v e r s i t y o f B r i t i s h Co l umb i a 2075 Wesbrook P l a c e Vancouver, Canada V6T 1WS C i ABSTRACT Large amounts o f time and money are c u r r e n t l y b e i n g spent i n t r a n s f e r r i n g computer programs from one machine t o a n o t h e r . I t seems u n l i k e l y t h a t the problem of t r a n s f e r r i n g such programs e f f i c i e n t l y w i l l e v e r be c o m p l e t e l y s o l v e d . 8 h a t can be done, however, i s t o program i n such a way t h a t t r a n s f e r c o s t s a r e m i n i m i z e d . The f i r s t p a r t o f t h i s paper d i s c u s s e s some e f f e c t i v e t e c h n i q u e s which have been developed t o f a c i l i t a t e the w r i t i n g of m o b i l e programs. The second p a r t d i s c u s s e s two d e t a i l e d a p p l i c a t i o n s o f one of t h e s e t e c h n i g u e s , the use of an A b s t r a c t L o g i c a l Language,, i i Contents 0. 0 Introduction. 1 1.0 Part 1 - THEORY ...'.............................••.-..».» « • • * 2 1.1 On Producing Portable Compilers.......................... 3 1.1.1 The UNCOL Concept or Daydreams i n Retrospect........ 4 1.1.2 Roster's Solution: the Compiler Compiler approach.,.7 1.1.3 Self-Compiling Compilers. ........... . ....... . . • »••*. • • 9 1.1.3.1 BCPL - a Language with a Self-Compiling Compiler. 12 1.2 On Producing Portable Software for Non-Numeric Applications............................................ 14 1.2.1 What's i n a Name?. ..,,„.,.. ..................... 15 1.2.2 Design C r i t e r i a for an ALL.................. . , •••••••16 1.2.3 Implementation Osing an ALL........................ 19 1.2.4 Overheads, Disadvantages and L i m i t a t i o n s . . 2 1 1.2.5 Examples. .................. 23 2.0 Part 2 - PRACTICE. ................... • ........ .. ... ... ... 24 2.1 Experiment 1 24 2.1.1 Objectives.......................... ............. • ,.28 2.1.2 Implementations........................... ......, ..29 2.1.3 Notes on Mapping 31 2.1.4 Results of Experiment 1........................... ,.33 2.1.4.1 Space Measurements...,.............,,,,33 2.1.4.2 Time Measurements., ., ...............,....... 35 2. 2 Experiment 2 , 40 2.2.1 Outline O f ALGEBRA.........................,v..40 2.2.2 Outline of LOWL .....46 2. 2. 3 ALGEBRA Coding.. ........ ..... ... .••••,•47 2.2.4 Mapping the M l - l o g i c . . . . . . . . . . . . . . . . . . . , , 4 9 2.2.4.1 Source Format Problems............. ..... ,49 2.2.4.2 The OF Macro.................................. 53 2.2.4.3 Mapping of Registers.......................... 56 2.2.4.4 Mapping the Output Statements................. 57 2.2.5 Further Notes on Implementation 58 2.2.6 Conclusions.,...................................... 58 Bibliography. * ° • •' ' ^  Appendix A • • • • •• "* *'%t Appendix B..,.,,,,.•••,»•«•»••.*»•?•.•• • • »> »••*•• «•» ' • " > " * " " Appendix C • •••• " " ^ Appendix D.... .. .....,..,, • •«• * . Appendix E.. , • • * ~ Appendix F.... • • • i i i ACKNOWLEDGEMENTS I wish to thank Dr. John Peck, my supervisor, for his many hel p f u l suggestions which made the writing of t h i s thesis possible, and Dr. Harvey Abramson for his time and patience i n reading the thesis., 1 0.0 Introduction There i s a pressing problem that any . designer or implementor of software must face today. I t i s one of obsolescence. The threat of obsolescence may manifest i t s e l f i n more ways than one. For instance, the computer on which the software i s running may become obsolete and have to be replaced, or the designer/implementor i s moving and wants to take his software with him, necessitating a transfer to another i n s t a l l a t i o n . These threats can be a l l e v i a t e d i f due consideration i s given to the writing of the software i n as machine-independent a way as possible., I f not, many good pieces of software w i l l die with the computer they ran on. Software p o r t a b i l i t y i s of supreme p r a c t i c a l importance since astronomical sums of money are currently spent i n re-programming for new environments. It i s an obvious waste of time and e f f o r t , i f , in order to implement i d e n t i c a l pieces of software on d i f f e r e n t computers, one has to st a r t from scratch in each case. I t seems unlikely that the problem of transferring programs e f f i c i e n t l y from one machine to another w i l l ever be completely solved. I t w i l l always be the case that some software would need to be recoded f o r a new environment. What can be done Is to program i n such a way that transfer costs are minimized. Hany e f f e c t i v e techniques have been developed which lend themselves to the writing of highly mobile programs. Some of these techniques are discussed i n the sequel, and two p o r t a b i l i t y exercises are presented. 2 1.0 Part 1 - THEORY Before concentrating on the major techniques used i n the production of portable software, l e t us dispense with two extreme, t r i v i a l cases. Case 1 : No Solution W a r s h a l l 2 S argues that i t i s impossible to achieve true p o r t a b i l i t y . , Undoubtedly, t h i s i s true i f our p o r t a b i l i t y exercise i s of the form: software S i s implemented on one machine and then someone else wants an implementation for his machine* This new someone might have a machine, M, which was designed years after S was f i r s t implemented. M might be r a d i c a l l y d i f f e r e n t from any machine produced up to that time. The point i s that i t may be impossible to achieve p o r t a b i l i t y over a l l current machines and a l l that can be imagined i n the future. But that i s not to say that one should not t r y to achieve mobility over most current computers; and i f the design i s f l e x i b l e enough, there i s a good chance that the software can be ported to future machines., Case 2 : No Problem There i s a growing trend towards computer networks. Here we have a number of d i f f e r e n t computers linked together i n some way, so that, i n p r i n c i p l e , a user has access to a l l computers in a given network. Within a network the problem of p o r t a b i l i t y i s bypassed,, For i f some software i s available on one machine, 3 t h e n i t i s n o t n e c e s s a r y t o implement i t on a n o t h e r w i t h i n t h e network. The p o r t a b i l i t y p r o b l e m o n l y a r i s e s i f one network wants a program f r o m a n o t h e r n e t w o r k . I t i s not i m p o s s i b l e t o i m a g i n e t h e u l t i m a t e network i n which a l l c o m p u t e r s a r e l i n k e d t o g e t h e r , b ut i t i s a b i t f a r - f e t c h e d a t t h e p r e s e n t t i m e . U n t i l s u c h a network i s v i a b l e , t h e p o r t a b i l i t y p r o b l e m w i l l r e m a i n a t h o r n i n t h e s i d e s o f computer programmers, 1.1 On P r o d u c i n g P o r t a b l e C o m p i l e r s The i n t r o d u c t i o n o f h i g h - l e v e l l a n g u a g e s e a s e d c o n s i d e r a b l y t h e b u r d e n o f w r i t i n g programs i n a s s e m b l y o r machine l a n g u a g e s . But i t c r e a t e d a p r o b l e m . F o r e a c h l a n g u a g e i n t r o d u c e d , a c o m p i l e r or i n t e r p r e t e r had t o be w r i t t e n f o r i t . Today t h e r e i s a p r o l i f e r a t i o n o f l a n g u a g e s - f r o m s p e c i a l p u r p o s e o n e s d e s i g n e d t o s o l v e one p a r t i c u l a r c l a s s o f p r o b l e m s , e . g . , L I S P f o r l i s t p r o c e s s i n g , o r P i c t u r e " D e s c r i p t i o n L a n g u a g e s f o r w r i t i n g g r a p h i c s p r o g r a m s , t o g e n e r a l p u r p o s e ones l i k e PL / 1 o r ALGOL W. I t i s no s u r p r i s e , t h e r e f o r e , t h a t w i t h t h e p o s s i b l e e x c e p t i o n o f O p e r a t i n g S y s t e m s , c o m p i l e r s a r e p r o b a b l y t h e most i m p o r t a n t components o f s o f t w a r e t o d a y , c o n s e q u e n t l y i t i s o f immense b e n e f i t t o most p e o p l e t o have p o r t a b l e c o m p i l e r s a r o u n d . 1.1,1 The UNCOL Concept or Daydreams i n Retrospect As far back as the nineteen f i f t i e s (see footnote), people were postulating ways to ease the burden of transferring software from one computer to another., The most ent i c i n g to emerge was the ONCOL (ONiversal Computer Oriented Language) concept* 2. The problem i t proposed to solve was the following: given m machines and 1 languages, i t i s reguired to construct, for each language L and each machine M, a compiler which translates from L to the order code of M. In the straightforward scheme of doing things, i . e . , write a separate compiler for each pairing of languages and machines, 1 * m pieces of complicated software must be written. In the UNCOL scheme of things, only 1 generators (none of which i s any more d i f f i c u l t to write than any of the above compilers) and m translators ( a l l of which would be much simpler to write than any of the above) need to be written., A l l generators would be written in UNCOL. Each would accept a program PL written i n some language L, producing as output the ONCOL version of PL. Each tra n s l a t o r translates from UNCOL to the order code of the machine M f o r which i t was written. A tran s l a t o r can be written i n the assembly language of M or i n any other language available on a . , Now a program written i n L, say, can be compiled i n two stages, L -> UNCOL and Though the f i r s t published paper was in 1958, the concept was discovered by many independent persons since 195*4. Some even claim that i t might not be d i f f i c u l t to prove that " t h i s was well-known to Babbage". 5 UNCOL -> machine language. Thus we see that UNCOL reduces the requirement of 1 * m programs to writing 1 + m programs. In practice, 1 and m are much greater than 2, and hence, i f the UNCOL concept could be re a l i z e d , i t would r e s u l t i n a marked savings in programming, debugging and documentation with the consequent sizable reduction ^n the cost of producing compilers. .. Not only wouid i t solve the 1 languages, m machines problem, but i t can be adapted e a s i l y to accomodate a new language NEWL, or a new machine NEWM. Notation : {A,B -> C} represents a program written i n A, which accepts a program written i n B and translates i t to an equivalent program i n the language C. In the case of NEWL, a l l that i s needed i s A, [UNCOL, NEWL -> UNCOL}. (Presumably t h i s would be provided by the formulator of NEWL, but i t doesn't have to be). To implement NEWL on a machine OLDM, A i s input to B, {OLDM-ML,UNCOL -> QLDM-ML} where OLDM-ML stands for the machine language of OLDM. The output i s C, {OLDM-ML, NEWL -> UNCOL}. A program written in NEWL can then be compiled by inputting to C, and the output submitted to B. In the case of NEWM , any exist i n g machine OLDM using the UNCOL system may be used.„ A l l that i s needed i s a translator D, {UNCOL, UNCOL -> NEWM-ML}. D i s input to {OLDM-ML, UNCOL -> OLDM-ML} to produce E, [OLDM-ML, UNCOL -> NEWM-ML}.. D i s then input to E to produce [NEWM-ML, UNCOL -> NEWM-ML}. The generators {UNCOL, L i -> UNCOL} can now be used to provide 6 {HEWH-HL, L i -> UNCOL}., From the above discussion, i t seems that the UNCOL concept was a very a t t r a c t i v e one. Why, then, was i t never realized? I t was not a l o g i c a l i m p o s s i b i l i t y since S t e e l 1 9 provided a demonstration of the l o g i c a l existence of a language with the properties of UNCOL, He also demonstrates the d e s i r a b i l i t y and economic f e a s i b i l i t y of UNCOL, or some sim i l a r proceeding. The UNCOL dream was shattered by more mundane considerations. The universally accepted language suitable as a target for a l l compilers was never agreed upon by a s i g n i f i c a n t proportion of the computing profession., Also l o g i c a l p o s s i b i l i t y i s not p r a c t i c a l p o s s i b i l i t y . It i s clear that UNCOL would have to be suitable as both a source and a target language. Naturally, t h i s leads to the reguirement that i t possess a number of somewhat c o n f l i c t i n g properties. I t must be (a) simple and general because i t has to be implemented on every computer; (b) e f f i c i e n t , r i c h and expressive because of prime importance i s the ease and e f f i c i e n c y with which the algorithm f o r accomplishing the task can be programmed i n UNCOL. (c) problem-oriented, because i t w i l l be used for writing the generators {UNCOL, Lj -> UNCOL}. Summarily, i t must possess the best of the two worlds of high-and low-level languages. The creation of an UNCOL with such properties i s a monumental task in software engineering. 7 1.1,2 Roster's Solution : the Compiler Compiler Approach Roster 9 attempts to solve the UNCOL problem by a separation of the various functions of UNCOL. He proposes the design of a special-purpose high-level language, UNCOLH, say, which would have only one function - only compilers would ever be written i n i t . It must be simple, e f f i c i e n t and problem-oriented towards the writing of compilers. It may very well lack many of the conventional f a c i l i t i e s present i n today's high-level languages. In f a c t , CDL, the Compiler Description Language he has been using, lacks features such as an assignment, array-access and arithmetic operations. Once UNCOLH i s agreed upon (is i t possible?) the problem of r e a l i z i n g the 1 * m translators (Mj, L i -> Mj} i=1{1}l, j=1{1}m, can be solved by constructing the coll e c t i o n s {UNCOLH, L i -> Mj} and {Mj, UNCOLH -> Mj}. A compiler f o r L i on Mj i s effected by inputting {UNCOLH, L i -> Mj} to {Mj, UNCOLH -> Mj}. Output i s {Mj, L i -> Mj}. A program written i n L i i s then compiled i n the usual way. At f i r s t glance the above seems to be worse than the straightforward solution of writing 1 * m compilers, for now we need to write 1 * m + m translators. The benefit i s that i f UNCOLH i s well chosen, i t should be a l o t easier to write {UNCOLH, L i -> Mj} than {Mj, L i -> Mj}; the m transl a t o r s (Mj, UNCOLH -> Hj} should not present too much d i f f i c u l t y i f UNCOLH i s simple., Further advantages accrue to thi s new approach., Most 8 noteworthy i s that UNCOLH i s never used a target language, but only as a source language. Hence less stringent conditions are imposed on i t than on UNCOL proper. This i s so because i t i s no longer necessary to be able to r e a l i z e the concepts of a l l other languages i n UNCOLH. Also the tr a n s l a t i o n from L i to Mj i s a one stage process and consequently there i s a better chance of achieving e f f i c i e n c y . Kost'er further explains that the size of the problem can be decreased using macro techniques. He points out that for a given language Lk, the translators [UNCOLH, Lk -> Mj} j=1{1}m, w i l l show a marked s i m i l a r i t y since the l e x i c a l and syntactic phases w i l l be mostly common. The target machine orientation of the translator w i l l be manifest mainly i n the code-generation phase. He proposes to exploit t h i s fact by using macro techniques for t h i s l a s t phase. For each language Lk, the m translators [UNCOLH, Lk -> Mj} can be replaced by the single translator [UNCOLH, Lk -> MIMCk} where MIMCk i s a seguence of machine independent macro c a l l s . MIMCk can be regarded as the language of a high-level abstract machine well suited f o r r e a l i z i n g Lk, To rea l i z e Lk on a machine M, a l l that i s needed i s a c o l l e c t i o n of macros whose replacement text i s the order code of M, The problem has been reduced to the construction of m tra n s l a t o r s [Mj, UNCOLH -> Mj}, 1 translators [UNCOLH, L i -> MIMCi} and 1 * m c o l l e c t i o n s of macros. This l a s t i s a r e l a t i v e l y small job and hence there has been an impressive reduction i n the siz e of the problem. But, as i s usual i n Computer Science, t h i s saving has not been 9 achieved without a price. Macro expansion i s a r e l a t i v e l y slow business and since the code generation module and the macro processor forms part of the f i n a l production compiler, i t may, as a r e s u l t , be slow. 1.1.3 Self-Compiling Compilers k self-compiling compiler i s one which i s written i n the language i t compiles, e.g., writing an ALGOL 68 compiler in ALGOL 68. In a paper written i n 1960, Masterson 1 0 describes the method and how i t was used to implement the NELIAC language. So the idea i s not new, but there aren't many self-compiling compilers available at present. This stems from the fac t that not many languages are suitable for coding their own compiler. Very few people would support the idea of writing a COBOL compiler in COBOL and, because of i t s l i m i t e d character manipulation f a c i l i t i e s , FORTRAN i s not the best language f o r writing a FORTRAN compiler. When the language i s su i t a b l e , however, self-compiling can be a valuable aid to p o r t a b i l i t y . Before describing the method, some observations are in order. Much of the e f f o r t required to transfer a compiler i s i n the rewriting of the code-generator for the new machine - the si z e of the machine-independent parts of the compiler i s ir r e l e v a n t . This suggests that p o r t a b i l i t y does not suffer s i g n i f i c a n t l y i f the language includes higher l e v e l features such as conditional commands and the scope rules of i d e n t i f i e r s . 10 whereas p o r t a b i l i t y i s enhanced mainly by reducing the more fundamental f a c i l i t i e s of the language such as the variety of storage and data types, the complexity of tha c a l l i n g mechanism for procedures and the number of primitive expression operators. H i l k e s 2 7 indicates that a programming language can be divided into two parts : (i) The Outer Syntax - consists of those language features that are independent of the data being manipulated, e.g., a conditional or GOTO statement. (ii ) The Inner Syntax - consists of those language features concerned with the manipulation and declaration of data. In S i l k e s ' terminology, the p o r t a b i l i t y of a language i s hardly affected by the size of i t s outer syntax, whereas p o r t a b i l i t y i s inversely proportional to the size of the inner syntax., Having observed that the p o r t a b i l i t y of a compiler revolves around i t s code generator, we now describe how self-compiling can aid p o r t a b i l i t y . The compiler, f o r a language L, say, must be designed so that there i s as r i g i d an interface as possible between the machine-independent (.HI) parts and the code-generation module which generates machine code from some i n t e r n a l machine-independent form. The MI parts are coded i n L. To eff e c t a f i r s t implementation, one must either translate the compiler to machine code by hand, or use some sort of bootstrapping technique, i n much the same way as Wilkes did i n implementing WISP2*. Now that we have a compiler for L on some machine M1, how 11 much e f f o r t must we expend to transfer i t to another machine, H2? Since we must produce code capable of being executed on H2, the f i r s t task i s to a l t e r the code generator so that i t generates code for M2. A potential problem arises at t h i s point., Since the modified cods-generator w i l l be used as a part of each of the two compilers on Ml and Ei2 (see below), i t i s best coded i n a machine-independent way, and presumably, the best choice i s to use the language L. In the following we assume that t h i s i s the case. Letting M10 and M20 represent the order codes of M1 and M2 respectively, we have the following translators : A, {M10, L -> M10}, the given compiler; B, £L, L -> M20}, the source code of the compiler with the ,new code-generator. I t i s required to construct {H20, L -> M20}, a compiler for L on H2. Construction B i s input to A to produce C, {M10, L -> M20}, a hybrid compiler which runs on M1 but produces code for M2. B i s then input to C to produce {H20, L -> M20}, as was required. The above process i s simple and straightforward i n theory, but there are p r a c t i c a l problems to contend with. One might be that 132 i s too small to accomodate the compiler, in which case overlaying techniques may have to be used. Also one would need to adapt to new operating system conventions and the l i k e . It i s these apparently t r i v i a l d e t a i l s , not the o v e r a l l 12 organization of a porting project, that defeat many well-planned projects. One would be well-advised to give them serious consideration i n the early stages of planning to have reasonable assurance of success. 1.1.3.1 BCPL - A Language with a Self-Compiling Compiler BCPL 1 6 was designed as a tool for compiler writing and systems programming. A major design goal was that i t should be inherently portable. Consequently, i t has a small number of primitive f a c i l i t i e s . For instance, i t has one data type, three storage types, a very simple procedure c a l l i n g mechanism and few expression operators., I t s one data type makes i t reasonable to allocate space f o r items in the run-time stack by the machine-independent part of the compiler., The code-generator i s thus s i m p l i f i e d and the p o r t a b i l i t y of the compiler i s improved. Since BCPL was designed s p e c i a l l y f o r software writing, i t should be quite suitable for encoding i t s own compiler. The BCPL compiler f i r s t translates a source program into an intermediate object code, OCODE, designed s p e c i f i c a l l y for t h i s purpose., This intermediate code i s then passed to the code-generation module which converts i t to the order code of the real machine. A prospective implementor of BCPL on machine, 13, say, i s supplied with the compiler i n one of two forms, OCODE or INTCODE, The l a t t e r i s a low-level assembly language designed 13 by R i c h a r d s 1 8 . For the OCODE form, one needs to write a translator, OCT, from OCODE to the order code of M. OCT i s f i r s t used to translate the OCODE version of the compiler to M's machine language, and then acts as the code-generation phase of the new compiler. OCT can be written i n any way convenient to the implementor., For instance, i t can be written i n any suitable language available on M, and i f one has access to an existing BCPL compiler, i t can be written i n BCPL., Even a macro processor with the appropriate macro d e f i n i t i o n s can be used to generate machine code from OCODE, but t h i s i s not recommended since macro processing i s slow and the compilation time of a BCPL program would be adversely affected. Once you have a working version of the compiler, you can modify an exis t i n g optimising code-generator to produce better code f o r ft. If one i s interested in getting a working version of BCPL quickly, the INTCODE k i t of the compiler i s recommended. Because of i t s s i m p l i c i t y , i t i s much easier to write an INTCODE translator than an OCODE one. Ri c h a r d s 1 8 qives a good summary of the advantages of t h i s approach. Among them are: 1., Less knowledge and less work i s required to construct the f i r s t bootstrap. 2. INTCODE i s easier to learn and i s more convenient to write or modify than OCODE. 3. The text of the INTCODE form of the compiler i s more compact than the corresponding OCODE text, an important factor when using cards or paper-tape. 14 1.2 On Producing Portable Software for Non-Numeric Applications Hhy i s i t that many compilers can produce f a i r l y e f f i c i e n t code for programs that are mainly numerical in nature, but fare rather badly when i t comes to non-numerical applications? The reason i s that the numerical f a c i l i t i e s i n a language can be e f f i c i e n t l y mapped into, the machine instructions available on most computers, whereas i t i s d i f f i c u l t to map e f f i c i e n t l y the non-numerical f a c i l i t i e s because machines vary widely i n the way they manipulate characters and data structures, and no set of common primitive operations would be universally e f f i c i e n t . So given the s i t u a t i o n that most compilers generate i n e f f i c i e n t code for non-numerical algorithms, a prospective implementor must decide in what language he must code his software. In addition to the above, encoding software in a pre-defined high-level language has further drawbacks. The primitive operations and data types provided by the language may not coincide with those required by the software, and hence i t becomes necessary to represent the needed primitives i n terms of those offered by the high-level language. The representation might, perforce, be awkward, leading to large i n e f f i c i e n c y factors. The i n e f f i c i e n c y r e s u l t s because i t i s d i f f i c u l t , i f not impossible, to generate e f f i c i e n t code for a l l possible combinations of primitive operations. Another bete noire i s that one may have to pay the price for f a c i l i t i e s provided by the language, but not used i n implementing one's software. Examples might be recursion, run-time storage organization or 15 dynamic l i m i t s on looping statements. afte r weighing the above considerations, i t i s cl e a r that using a pre-defined high-level language i s not the way to go, fo r , i n that case, you would be t a i l o r i n g your software to s u i t a language - not the best policy to adopt f o r production software. so the o r i g i n a l question remains - what language should you use? The answer i s : t a i l o r a language to s u i t your software - design an Abstract Logical Language (ALL) whose primitives are just the primitives your software needs! The task of writing software i s s i m p l i f i e d considerably i f i t i s written i n a language s p e c i f i c a l l y t a i l o r e d to i t . Not only does an implementation become easier, but i t i s e f f i c i e n t compared to what can be obtained by using a pre-defined high-level language. The e f f i c i e n c y r e s u l t s from the f a c t that the primitives of the language are just those that are needed, and the language need contain no extraneous statements not used i n the coding of the software, so you do not pay a price for features you do not use. We w i l l c a l l such a language an Abstract Logical Language. 1.2.1 What's i n a Name? Other terms are used in the l i t e r a t u r e to express the same concept. Waitezz c a l l s i t an Abstract Machine, his philosophy being that the operations provided in an Abstract Logical Language (ALL) can be viewed as the order code of an imaginary machine that i s independent of a l l r e a l machines. ., Brown3 uses 16 the term DLIMP (Descriptive Language Implemented by Macro Processor), which s p e c i f i c a l l y states the method to be used to r e a l i z e an ALL on a r e a l machine. we prefer the term Abstract Logical Language because we are more interested in the language aspect than the machine aspect, and we do not wish to state a p r i o r i how to r e a l i s e an ALL on a r e a l machine, even though a macro processor would be used most of the time. Why " l o g i c a l " ? Two reasons, the second being more of a pun than anything else. The f i r s t i s that the language must be the " l o g i c a l " choice for that p a r t i c u l a r piece of software and secondly, the language i s to be used for encoding the " l o g i c " of the software. The mnemonic ALL may be misleading because an Abstract Logical Language, LLA, say, i s designed to implement a pa r t i c u l a r piece of software. Hopefully LLA w i l l be suitable for encoding other pieces of software (though t h i s should not be so a p r i o r i ) , but i t c e r t a i n l y w i l l not be appropriate for encoding a l l the software one needs to implement.. 1.2.2 Design C r i t e r i a for an ALL An Abstract Logical Language i s an embodiment of the basic operations required to perform a pa r t i c u l a r task.. Choosing an ALL f o r writing a given piece of software i s very much an engineering problem.. An excellent account of the actual design of an a l l ALL i s given by Waite 2 2. In deciding upon an ALL, 17 three considerations (enumerated by Waite) are of prime importance, 1, The ease and e f f i c i e n c y with which the algorithm f o r accomplishing the task can be programmed i n the ALL. 2. The ease and e f f i c i e n c y with which the ALL can ba r e a l i s e d on machines available currently and i n the forseeable future. 3.., The tools at hand for the r e a l i s a t i o n i n 2., Let us elaborate on these points. Assume that our aim i s to design an ALL for some software S. Suppose the basic data items of S consist of integers, stacks, trees and character s t r i n g s . Then the ALL must provide data structures i n which these concepts can be expressed, and operations for manipulating them. For instance, stacking operations such as pushing and popping should be included. One should also bear i n mind the macro processor which w i l l be used to expand the ALL, and design the syntax of the language accordingly. For example, i n Waiters case, he wanted his abstract language to be expandable by SIMCMP, a very simple macro processor., According to him, t h i s was his prime consideration and any cl e a r choice would be resolved i n i t s favour., Since SIMCMP could only accept single character parameters, a l l operations i n the FLUB language (his ALL) had single characters ( l e t t e r s or digits) as operands, e.g., PTR A = B + 7, which means add the PoinTeR f i e l d s of r e g i s t e r s B 18 and 7 and store the r e s u l t i n the pointer f i e l d of reg i s t e r A; or TO 72 IF PTE Y = D, with the obvious meaning. The macro d e f i n i t i o n s f o r these two would begin with PTE * = * + *, and TO ** IF PTE * = *. respectively., Unless one i s forced to choose otherwise, the macro processor should be one which works i n free-mode (as opposed to a processor l i k e GPH2 0 which reguires a warning marker to herald a macro c a l l ) , as t h i s i s a valuable aid to f l e x i b i l i t y . In th i s case, i t becomes easier to cater f o r unusual object machines or languages, since a free-mode processor does not f i x i n advance what i s a macro and what i s not, and hence which parts of an ALL are to be changed on a mapping and which parts are not., This feature would be very useful In dealing with such annoying, t r i v i a l d e t a i l s such as l a b e l formats. Suppose that an ALL allowed statement labels to be i d e n t i f i e r s of up to eight characters, and, for some reason, some software written i n t h i s ALL were to be expanded into i t s FORTRAN version, where only numeric labels are permitted. A macro pre-pass could examine a l l l a b e l declarations and generate a unique integer corresponding to each declaration. For example, i f START, PROCEED and END were labels i n the program, output from a pre-pass could be macro d e f i n i t i o n s which define START as 1, PROCEED as 2 and END as 3. These d e f i n i t i o n s can then be combined with the rest of the mapping macros for the f i n a l expansion. The design of the language should proceed concurrently with the design of S, T y p i c a l l y , you should choose what you consider 19 suitable instructions and then s t a r t the coding of S* Perhaps you w i l l f i n d that you have omitted several key operations and included some ir r e l e v a n t ones. Some data types may also need changing. In t h i s case, you should modify your i n s t r u c t i o n set, write some more code, and, again, perhaps i n s t i t u t e some useful changes. , By a process of gradual refinement, you should a r r i v e at the primitives best suited f o r expressing your algorithm. 1.2.3 Implementation Using an ALL Suppose i t i s reguired to implement some software S i n a portable manner. This can only be done i f S i s inherently machine-independent (MI). If the machine-dependent (MD) parts of S (e.g., input/output, hashing algorithms or modules depending on the i n t e r n a l representation of characters) are of comparable size to the MI parts, then the following technigue w i l l not produce s a t i s f a c t o r y r e s u l t s . This i s only to be expected since major parts of S would have to be coded by hand for each new machine. Let us assume, therefore, that at most 10% of S i s machine-dependent., F i r s t the l o g i c of S must be separated into i t s MI and MD parts. There i s no clear-cut d i s t i n c t i o n between these two and the dividing l i n e may contain a certain arbitrariness about i t . Yet, subjective as i t may be, most people w i l l agree on what features are, and are not, machine-dependent. After the above separation i s made, an Abstract Logical 20 Language, SALL, say, must be designed for S. Next the MI l o g i c i s coded in SALL., As noted above, the MD l o g i c must be coded anew for each new machine.. The interface between the two can consist of direct GOTO statements.,. There i s another approach which i s best i l l u s t r a t e d by an example. Suppose that S reguires a conversion from integer to character representation., This i s a machine-dependent task., You can solve i t by introducing the statement CONVIG PAH i n SALL. On a par t i c u l a r machine, t h i s can be mapped into a hand-coded routine to do the actual conversion. Now suppose we have coded the MD parts for a machine M, and we have the MI parts coded in SALL. To effect an implementation on M, we need to map the MI parts into the order code of M.„ A macro processor can be used to achieve t h i s . Presumably S was designed to be translatable by some macro processor(s) the designer had in mind. Suppose the macro processor (MP) i s available on a machine MAC. The following must be.accomplished: 1. write macros acceptable to MP to translate SALL into M's Assembly language. 2. ; Using MP - on MAC, remember - expand the MI parts of S. The resul t i s an Assembly language program for M. 3., Input the MD parts with the r e s u l t of 2 to M's Assembler. Output i s software S i n M*s machine code. I f MAC i s not disadvantages. F i r s t M i s remote from N, the same as M, this approach has many one must have access to both M and N. I f and the macros are written i n c o r r e c t l y the 21 f i r s t time (almost a c e r t a i n t y ) , steps 2 and 3 would have to be repeated (perhaps more than once) and the commuting between MAC and M would make t h i s , at l e a s t , inconvenient, slow and perhaps, costly.. Secondly, MAC must be capable of writing Assembly language for M. If t h i s i s not the case, i t becomes necessary to do annoying translations at each i t e r a t i o n of 2 and 3. However, these problems can be overcome by using a system s i m i l a r to Saite's Mobile Programming System (see experiment 1). 1.2.4 Overheads, Disadvantages and Limitations There i s a large overhead involved i n producing portable software using an Abstract Logical Language, I f a s u i t a b l e ALL does not e x i s t , then the implementor must design one. One should not knead one's software i n order to use an e x i s t i n g language, f o r , i n that case, you would be t a i l o r i n g your software to s u i t a language rather than vice versa, and the ef f i c a c y of the technique would be l o s t . Once the language has been designed, i t i s very important to complement i t with a macro test program. The absence of such a test program makes i t necessary for a l a t e r implementor to be fa m i l i a r with the inner workings of the program i n order to debug his macros. This may be very undesirable. To quote from Waite 2 2, "I cannot overstress the importance of a comprehensive macro test program i n the successful implementation of a machine independent system. Macro coding errors can be very subtle, requiring hours of debugging to trace them down i f the 22 machine-independent program i s the only test case. A conservative estimate based on our experience i s that a lack of a good test program w i l l increase by a factor of f i v e the time required to complete an implementation when the author of the system i s available to debug the macros. When he i s not available, the task i s almost hopeless." There i s also a minor overhead involved i n organising the l o g i c of the software in a machine independent way. Of course, for a f i r s t implementation the program needs to be debugged, and f i n a l l y the p o r t a b i l i t y method must be well-documented.. Apart from the large i n i t i a l overhead in using an ALL to produce portable software, there are other disadvantages. One i s that any language which can be compiled by a macro processor must necessarily ba set at a f a i r l y low level.., I f set at too high a l e v e l , the macro d e f i n i t i o n s become much more d i f f i c u l t to write, and one begins to lose the p o r t a b i l i t y that the use of a macro processor was o r i g i n a l l y meant to provide. Thus the technique i s unsuitable for those applications requiring p o r t a b i l i t y , but where a general high-level language would be more apt than any low-level ALL. Also, when using an ALL, the generated object code i s le s s e f f i c i e n t than would be produced by hand-coding i n assembly language, but i s generally more e f f i c i e n t than that produced by using a pre-defined high-level language. 23 1.2.5 Examples Perhaps the most ambitious use of an Abstract Logical Language has been i n the implementation of SN0B0L4 7 , a text processing language. The reference gives a detailed description of the project. The ALL used to implement SN0B0L4 i s c a l l e d SIL and contains 130 d i f f e r e n t types of statements.,. Apart from minor changes i n character representations, etc., SIL can be mapped by any reasonably powerful macro-assembler. However, t h i s does not preclude the use of free-mode processors such as STAGE2 or ML/1., The implementation of WISP2 6 , a simple general l i s t - p r o c e s s i n g language, i s another good example of the use of the above technigue. But WISP i s unigue in that the ALL used to implement i t i s WISP i t s e l f . In f a c t , the experiment combines the technigues of using an ALL with that of bootstrapping a compiler written i n the language i t compiles. 24 2.0 Part 2 - PRACTICE The rest of thi s paper deals with two experiments i n p o r t a b i l i t y , using the concept of an Abstract Logical Language. 2.1 Experiment 1 The f i r s t experiment concerns the implementation of STAGE2, using a f u l l bootstrap, i . e . , we assume no access to a running version of STAGE2. , A very simple processor, SIMCMP1*, i s implemented by hand, and then used to obtain a more complex one, STAGE2. STAGE2 was designed by William Waite. It i s s i m i l a r to an e a r l i e r macro processor, LIMP 2 1, also designed by Waite. STAGE2 provides a l l the features normally associated with a general macro processor 1 1. Its input recognition procedure i s language-independent, employing the LIMP type of scanning mechanism to recognize macro c a l l s and is o l a t e parameters. With each macro i s associated a template. A template consists of fixed strings with gaps between them fo r the arguments, , To recognize a macro c a l l , each source l i n e i s compared with the template., If several templates match the source l i n e , a notion of "closest f i t " i s used to resolve ambiguities., For example, the source l i n e PTE A = B + 0 would match the templates p-re • = • • • • and PTE ' = » + 0. 25 In t h i s case STAGE2 assumes that the source line matches the second template. Conditional expansion, i t e r a t i o n and the l i k e are provided by "processor functions" rather than by e x p l i c i t program structure. One can also perform d i f f e r e n t parameter conversions., For a complete description of STAGE2, see Waite 2 3. STAGE2 was designed as a tool for creating machine-independent software. To be e f f e c t i v e , STAGE2 i t s e l f must be highly mobile. Hence the system i n which i t i s embedded must require minimal support from any computer on which i t i s to be implemented. As i t turns out, the only thing reguired from the target machine i s an Assembler (which need not have any macro c a p a b i l i t y ) . With his Mobile Programming System (MPS), Haite solves the commuting and tra n s l a t i n g problems mentioned on page 19. His method enables a l l the work to be done on the object machine. The base of the MPS i s a very simple macro-processor, SIMCMP1*.., It i s available as an 89-statement program written in ASA Fortran. If Fortran i s available on the object machine, implementation of SIMCMP i s t r i v i a l . I f not, the l o g i c of SIMCMP i s so simple that i t can be translated by hand into assembly language i n about 4-8 hours. Once SIMCMP i s running, i t i s used to implement STAGE2, a much more powerful macro-processor. I t should be emphasized that SIMCMP has one job - to translate FLUB, the Abstract Logical Language i n which STAGE2 i s written. Indeed, FLUB was designed to be translatable by SIMCMP, Hhen STAGE2 i s running, i t can be used to generate a 26 more optimised version of i t s e l f . This i s possible because the mapping macros can now be written, u t i l i s i n g the conditional a f a c i l i t i e s of STAGE2, to recognize s p e c i a l cases such as PTH A = 0 + 0, or recognizing when use can be made of sp e c i a l i nstructions such as BCTR REG,0. ,. The FLUB Language FLUB {First Language Under Bootstrap) was designed s p e c i f i c a l l y for the task of constructing a machine-independent macro-processor. A complete description of the c h a r a c t e r i s t i c s and the rationale behind the design of the FLUB language i s given by Waite 2 2. The FLUB program which implements STAGE2 must conform to the r e s t r i c t i o n s imposed by SIMCMP, the only tool available for converting i t to assembly language., Consequently, only single character parameters (and hence arguments) are allowed., The basic data type of the language i s the FLUB word, which consists of three f i e l d s -1., the FLG f i e l d , which must be able to hold the integers 0 to 3. 2. ,. the VAL f i e l d , which must be able to hold the largest character or the longest s t r i n g length. 3., the PTR f i e l d , which must be able to hold the largest machine address. The operations on these f i e l d s are as follows FLG - test and/or set; VAL - addition and subtraction; tests f o r equality of VAL 27 f i e l d s ; PTB - addition, subtraction, m u l t i p l i c a t i o n and d i v i s i o n ; tests f o r r e l a t i v e magnitude. In any mapping of FLUB to a r e a l computer, the way the FLUB word i s mapped i s of prime importance. One would be lucky to find a computer whose words are partitioned into three f i e l d s of the types constituting a FLUB word., Hence one-to-one mappings from FLUB to a r e a l computer are very rare. Otherwise, there are two possible approaches -1, pack the f i e l d s of the FLUB word int o one or more words of the target computer; 2. use one target computer word for each^field. The f i r s t choice w i l l minimize the space required to store information, but w i l l (presumably) introduce large overheads to pack and unpack f i e l d s . The second choice w i l l be wasteful of space, but one should expect faster execution., To resolve the dilemma, FLUB has 36 " r e g i s t e r s " named by the characters A-Z and 0-9., Each regi s t e r has the same format as a FLUB word. Hence, i n an implementation, i f one target computer word i s allocated for each r e g i s t e r f i e l d , only 108 words w i l l be so used,,, Since almost a l l FLUB operations take place on the r e g i s t e r s , memory can be packed without introducing excessive overheads due to packing and unpacking. 28 2.1.1 Objectives In order to survey the e f f e c t s of d i f f e r e n t methods of expansion of the FLUB language, four versions of STAGE2 were implemented. The main features to be studied were (a) the e f f e c t on speed and size when (i) the FLUB r e g i s t e r s and memory are packed and ( i i ) the registers are kept in unpacked form but memory i s packed., In the unpacked form, a FLUB regis t e r was represented using three 370 machine words - one for each of the FLG, VAL and PTR f i e l d s . In the packed form, one 370 machine word was used for the PTR f i e l d and one for the FLG and VAL f i e l d s - each occupying a half-word. , (b) the e f f e c t on speed and s i z e when sp e c i a l cases are optimised and use i s made of special i n s t r u c t i o n s . For example, i n a straightforward expansion of VAL C = A + 0, the VAL f i e l d of A i s added to the VAL f i e l d of 0 and the r e s u l t stored i n the VAL f i e l d of C. In an optimised version, the VAL f i e l d of A i s simply transferred to the VAL f i e l d of C. As an example of using a s p e c i a l i n s t r u c t i o n , consider VAL H •= X - 1; t h i s can be recognised as a s p e c i a l case of subtraction decrementing by one - hence use can be made of the BCTS GR,0 i n s t r u c t i o n to accomplish the subtraction.. 29 2.1.2 Implementations Let us denote the FLUB version of the machine-independent part of STAGE2 as STAGE2. FLUB. , Version 1 was a straightforward expansion of STAGE2.FLUB by SIHCHP, with no attempt at optimisation. No trouble was taken to recognise s p e c i a l cases. (It i s possible to do so, a l b e i t awkwardly, with SIMCHP, by writing macros with s p e c i a l i s e d templates, e. g. PTE ' = • + 0) . The macros were written in the simplest, most dire c t way acceptable to SIMCMP.. The only object was to get a running version of STAGE2. The FLUB registers and FLUB memory were held i n packed form. The macros for Version 1 are given i n Appendix A. Version 2 was s i m i l a r to Version 1 i n that no optimisation was attempted. However, the FLUB registers were held unpacked, while the FLUB memory was packed., The macros for Version 2 are given in Appendix B. One may wonder why no version was implemented with both the registers and memory being unpacked. While such an implementation should be faster (no packing and unpacking has to be done), i t i s very wasteful of space, and would be impractical for most purposes. Version 3 was produced using the running versions of STAGE2. The macros were written as STAGE2 macros, u t i l i s i n g the greater power of t h i s macro-processor. S p e c i f i c a l l y , extensive use was made of the conditional and unconditional branching f a c i l i t i e s of STAGE2 to recognize s p e c i a l cases and hence 30 produce a more optimised mapping than either of versions 1 or 2. Further optimisation was possible by holding the frequently used constants, 0, 1 and 8 (the number of 370 address units - bytes -making up a FLUB word i n memory) i n general registers., When a macro c a l l using one of these constants was encountered, the r e g i s t e r - r e g i s t e r i n s t r u c t i o n was generated instead of the register-memory equivalent. Since the former i n s t r u c t i o n s are faster and occupy only half a word, we should expect some improvement i n size and e f f i c i e n c y . As i n Version 1, the FLUB regi s t e r s and memory were held i n packed form., The macros fo r Version 3 are given i n Appendix C. , Version 4 was s i m i l a r to Version 3 i n that special-cases optimisation was performed., However, the FLUB r e g i s t e r s were held unpacked, while the FLUB memory was packed. The macros fo r Version 4 are given i n Appendix D. As an indica t i o n of the r e l a t i v e s i z e performance of these versions, the following figures show the number of IBM 370 Assembly Language statements generated for the two macro test programs FLT1 and FLT2. FLT1 and FLT2 consists of 735 and 536 FLUB statements respectively. , Version 1 Version 2 Version 3 Version 4 FLT1 1851 1851 1440 1440 FLT 2 1288 1328 1012 1052 As expected, the optimised versions produced less code than the unoptimised ones. But i t can be easily seen that the 31 "unpacked registers, packed memory" versions generated more statements than t h e i r "packed r e g i s t e r s , packed memory" counterparts. This i s readily explained by an examination of the STO and GET macros for the d i f f e r e n t versions. V1 and 72 produce the same number of statements for a l l macros except STO and GET. (Note that t h i s applies only to the number of statements, not the statements themselves)... Hence the difference i n the amount of code produced by V1 and V2 i s dependent on the number of STO and GET statements in the source program. Since FLT1 contains none of these statements, the number of assembly statements produced i s the same for V1 and V2. Similar remarks apply to V3 and V4. 2 .1.3 Notes on Happing A problem arose with the mapping of the LOC statement. In e f f e c t a LOC ' * statement labels the next source statement. The most natural way to map LOC 98, say, i s to map i t into LL98 ANOP where ANOP i s the assembler pseudo-op meaning "no operation". Unfortunately, the name f i e l d of ANOP must be a seguence symbol (one s t a r t i n g with a period). But i f we translate LOC98 to . LL98 ANOP then we cannot branch to i t by BZ .LL98, say, since the l a t t e r i s an i l l e g a l 370 Assembler statement. The problem can be solved by making an entry i n the STAGE2 memory whenever a 32 LOC »' statement i s encountered. Then whenever any other macro i s to be expanded a check i s made to see i f a LOC '* statement was just processed. I f so, the appropriate label i s attached to the f i r s t statement i n the expansion of the current macro, and the memory i s cleared. This would work f i n e , except that extra statements would have to be included in every macro d e f i n i t i o n to test whether or not a l a b e l should be attached to the f i r s t statement generated by the macro. This i s not vary appealing, because of the extra work in writing the macros, plus the more important fact that macro processing would be slowed considerably, A cruder, but much simpler, solution i s to generate a "useless" i n s t r u c t i o n LL98 LTS TEH,TEH USED AS A NOOP The above i n s t r u c t i o n , which just clears a temporary working register, w i l l not af f e c t the flow of the program. I t s only purpose i s to provide an in s t r u c t i o n to which a l a b e l can be attached. Of course, now for every l a b e l i n the source program we have an extra i n s t r u c t i o n . Hence whenever we branch to a l a b e l , we execute one more in s t r u c t i o n than we need to. However, once the macros are debugged, a simple procedure can be written to examine the assembler l i s t i n g , deleting the "useless" instructions and attaching t h e i r labels to the following statements. The following procedure w i l l do the job: LOOP BALR 12,0 USING *,12 ENTER SCARDS LINE1 , (U) ,EXIT=E0F CLC LINE1 (2) , = C«LL» BNE OUTPUT S'CARDS LINE2 , (4) , EXIT=EGF READ A LINE DOES IT HAVE AN 1LL' LABEL? IF NOT,WRITE THE LINE ELSE READ NEXT LINE 33 ** IF ENDFILE, GOTO EOF ATTACH LABEL TO NEW LINE WRITE IT OUT MVC LINE2(4) ,LINE1 SPDNCH LINE2, (4) B LOOP OUTPUT SPUNCH LINE1,{4) WRITE LINE WITHOUT • LL,« LABEL B LOOP EOF EXIT LINE1 DS 80C LINE2 DS 80C END 2.1.4 Results of Experiment 1 Let us divide STAGE2 into two parts - the invariant and variant. The invariant part consists of those pieces common to a l l the versions. The variant part consists of the assembly code equivalent to STAGE2.FLUB. It i s variant because the number of assembly language statements generated depends on the macro-processor and the macro d e f i n i t i o n s used to expand STAGE2•FLUB. 2.1.4.1 Space Measurements The breakdown of the core storage occupied by the invariant part of STAGE2 follows. The figures indicate the numbers of words on the IBM 370/168. 416 - generalised I/O package, including the l i n e buffer and four channel buffers. 34 270 - i n i t i a l i z a t i o n code plus constant d e f i n i t i o n s . 16004 - data space f o r FLUB registers and memory. Total Size of invariant part - 16690 words. Notation: Let Vi represent Version i , i=1,4., The s t a t i s t i c s f o r the variant part of STAGE2 are as follows. The figures indicate the number of assembly language statements (generated from 983 PLUB statements) a f t e r the "useless" i n s t r u c t i o n s have been deleted. Since the same number i s deleted for each version, the comparison i s not affected. V1 V2 V3 V4 2330 3048 2052 2770 Mhen assembled, the number of words of memory occupied by the variant part for the d i f f e r e n t versions were V1 V2 V3 V4 2284 3004 1988 2710 At a glance, i t i s evident that the "unpacked r e g i s t e r s , packed memory" versions are s i g n i f i c a n t l y larger than their "unpacked reg i s t e r s , packed memory" counterparts. S p e c i f i c a l l y , V2 i s 32% longer than V1 and V4 i s 36% longer than V3. As expected, the unoptimised versions are longer than the optimised ones; V1 i s 15% longer than V3 and V2 i s 11% longer than V4. Me conclude that the optimised version with packed re g i s t e r s provide the most compact implementation. , 35 But there are other considerations which can influence one (s decisions; consider the following table, where STG2.V refers to the size of the invariant part and % refers to the percentage of the t o t a l s i z e that STG2.V occupies.. V1 V2 V3 V4 STG2.V 2284 3004 1988 2710 TOTAL 18974 19694 18678 19400 % 11.5 15.3 10.6 14.0 Even in the most unoptimised case, V2, STG2.V i s only 15,3% of the t o t a l s i z e . Hence any r e a l saving i n space would come from a reduction i n the work space allocated to STAGE2, i f that i s feasible. This i s highlighted by the fact that though the variant part of V3 i s 1516 smaller than that of v i , say, the t o t a l size of V3 i s 98^ that of 71. 2.1.4.2 Time Measurements Next we did some time measurements. . Notation: Let Vi represent Version i , i=1,4. Each version was given four tasks to perform, and each task was to be done four times., To eliminate the differences in times given by the operating system when the same program i s run at d i f f e r e n t times, corresponding times were obtained by running the d i f f e r e n t versions at approximately the same time via a 36 batch j o b . To f u r t h e r e l i m i n a t e d i f f e r e n c e s due to o p e r a t i n g system overheads, the time t o perform one of the ta s k s was taken as the average of the f o u r times obtained f o r that t a s k . The tasks were as f o l l o w s : 1., Executing the standard t e s t data f o r t e s t i n g a STAGE2 implementation. 2. T r a n s l a t i n g LOW!TEST (see experiment 2) to 370 Assembler. L0W1TEST c o n s i s t s of 775 source statements and each version, produced 1243 assembler statements, 3. T r a n s l a t i n g ALGEBRA (see experiment 2) to 370 Assembler. ALGEBRA c o n s i s t s of 1097 source statements and each v e r s i o n produced 1450 assembler statements. 4. T r a n s l a t i n g STAGE2 t o 370 Assembler using the macros f o r V e r s i o n 3. STAGE2 c o n s i s t s of 983 source statements and each v e r s i o n produced 2146 assembler statements. The r e s u l t s are shown i n Table 1, The times shown are i n seconds of CPU time. A i s task 1, B i s task 2, C i s task 3 and D i s task 4., Comments on Table 1 Not only do the "unpacked r e g i s t e r s , packed memory" v e r s i o n s occupy more space than the "packed r e g i s t e r s , packed memory" v e r s i o n s , they are a l s o slower, as evidenced by comparisons between v i and V2, and V3 and V4. T h i s i s somewhat 37 surprising since one would normally expect the unpacked versions to be f a s t e r . However, for the IBM 370/168, this apparent contradiction can be explained. In the packed form, even though the r e g i s t e r s are compressed to f i t into two words, no "unpacking" (in the sense of loading and s h i f t i n g b i t s around) had to be done. This i s so because one can use the half-word in s t r u c t i o n s on the 370 to access the FLG and VAL f i e l d s . , Also, the 370 has two useful i n s t r u c t i o n s , Load Double and Store Double, which one can use to manipulate two words at a time. These instructions enabled the STO and GET macros (the major factors i n determining size) to be implemented e f f i c i e n t l y , since i n each case, a l l that i s involved i s a transfer of two full-words from one part of the 370 memory to another., When the registers are unpacked (occupying three full-words) and memory i s packed (occupying two full-words), one cannot implement STO and GET by a simple transfer of a block of information from one part of memory to another.„ So the above contradiction i s explained by another contradiction - that one has to unpack f i e l d s when the registers are unpacked but not when they are packed. An in t e r e s t i n g case i s the comparison between V1 and V4. In a l l cases, V1 i s s i g n i f i c a n t l y faster than V4.„ Hence we can conclude that the l o c a l optimisation obtained i s more than n u l l i f i e d by the extra overheads due to the unpacking necessary to transfer information between the FLUB memory and the FLUB re g i s t e r s . Comparison between V3 and V1 shows that l o c a l optimisation 38 produced s l i g h t l y b e t t e r code. The improvement i s not d r a s t i c , however. T h i s i s e x p l a i n e d by t h e f a c t t h a t i n t h e t a s k s performed, STAGE2 s p e n t most o f i t s time i n the I/O r o u t i n e s , and i n the t r a n s f e r of i n f o r m a t i o n between the FLUB memory and r e g i s t e r s . The o p t i m i s a t i o n s h o u l d be more n o t i c e a b l e i f t h e macro d e f i n i t i o n s i n v o l v e d more n u m e r i c a l c omputation. RON A 1 2 3 4 Ave B 1 2 3 4 Ave C 1 2 3 4 Ave D 1 2 3 4 Ave V1 • tn • 44 . 42 .43 . 42 3. ?2 3. 86 3.90 4.00 3. 92 4. 24 4. 47 4. 30 4. 42 4.36 4.23 4.03 4.23 4. 19 4. 17 V2 .42 .49 . 44 .45 .45 4. 22 4.40 4. 25 4. 45 4. 33 4.73 4. 83 4. 60 4.75 4.73 4.49 4.45 4.70 4.50 4. 53 V3 . 40 .45 .38 .39 • 40 3 . 7 1 3. 85 3. 65 3.74 3.74 4. 16 4.35 4. 10 4. 16 4. 19 3 . 9 9 4. 03 4.00 3.99 4.00 V4 • 43 . 47 • 43 .44 . 44 4. 23 4.59 4. 29 4. 40 4. 40 4. 79 4. 98 4. 70 4. 69 4. 7 9 4. 58 4. 87 4. 67 4.50 4. 65 T a b l e 1 40 2.2 E x p e r i m e n t 2 A f t e r STAGE2 was s u c c e s s f u l l y i m p l e m e n t e d , i t was us e d t o e f f e c t t h e i m p l e m e n t a t i o n o f a s y m b o l i c l o g i c p a c k a g e , ALGEBRA. ALGEBRA i s a program d e s i g n e d f o r s t u d e n t s and r e s e a r c h w o r k e r s i n B o o l e a n a l g e b r a and o t h e r k i n d s o f l o g i c . I t s s p e c t r u m o f u s e s r a n g e f r o m f r i v o l o u s a p p l i c a t i o n s t o g a m e - p l a y i n g t o t h e a n a l y s i s o f s w i t c h i n g n e t w o r k s . I t i s b a s t u s e d i n c o n v e r s a t i o n a l mode., A c o m p l e t e d e s c r i p t i o n o f ALGEBRA i s g i v e n by Brown and L o w e 5 and Brown*. .. We w i l l o u t l i n e t h e main f e a t u r e s below. , 2.2.1 O u t l i n e o f ALGEBRA Each l i n e o f d a t a f e d t o ALGEBRA must be a s t a t e m e n t . T h e r e a r e f o u r t y p e s o f s t a t e m e n t s : t h e OPERATOR s t a t e m e n t , t h e TABLE s t a t e m e n t , t h e TRY s t a t e m e n t and t h e NULL s t a t e m e n t . A comment may be appended t o any s t a t e m e n t by p r e c e d i n g i t w i t h a s e m i - c o l o n , e. g. OPERATOR > ; THIS IS THE IMPLIES OPERATOR A comment c a n o c c u p y a whole l i n e i f t h e l i n e s t a r t s w i t h a s e m i - c o l o n . , O n l y t h e f i r s t two l e t t e r s o f a s t a t e m e n t a r e used t o d e t e r m i n e i t s t y p e , e. g. OPXXX + i s t h e same a s OP + i s t h e same a s OPERATOR +. , 41 Def i n i t i o n s 1. A SYHBOL i s used to represent the name of a value, operator or variable. It must be either (a) a NAME SYMBOL which i s an a r b i t r a r i l y long sequence of one or more l e t t e r s or d i g i t s , or (b) a PUNCTUATION SYMBOL which i s a single character that i s NOT any of a l e t t e r , d i g i t , comma, tab, space, semi-colon, l e f t parenthesis, r i g h t parenthesis or the newline character. Examples of v a l i d symbols are A, 7, ATOM45, AVESYLONGSYMBOLNAME, + , ~ . I. Examples of i n v a l i d symbols are SPA CE (contains a blank), ;, -> (not a single character). 2. A VARIABLE i s any symbol that i s not the name of an existing operator or value. 3. , An EXPRESSION i s a series of operators with values or variables as operands. During the evaluation of an expression, operators of highest precedence are performed f i r s t . Subject to t h i s , operators are evaluated from l e f t to rig h t . Parentheses can be used to override precedence. The following sample terminal session should give one an idea of how the system operates. The statements prefixed with ">» are typed by the program,, The others are typed by the user. # RON ALGEBRA.0 T=1 42 # EXECUTION BEGINS > ALGEBRA - VERSION 1 > PLEASE ENTER VALUES TRUE FAL(E > ERROR - ILLEGAL SYMBOL > PLEASE ENTER VALUES TRUE FALSE THESE TWO LINES ARE PRINTED WHEN AL-GEBRA IS FIRST ENTERED.,THE SYSTEM IS NOW EXPECTING THE SYMBOLS TO BE USED AS VALUE NAMES. IF AN INVALID SYMBOL IS USED THE REQUEST IS REPEATED. ONCE ESTABLISHED, VALUE NAMES CANNOT BE CHANGED DURING THE COURSE OF A RUN -YOU MUST START AGAIN FROM SCRATCH IF YOU WISH TO USE DIFFERENT VALUE NAMES ANY NUMBER OF VALUES MAY BE ENTERED. AFTER THE VALUES HAVE BEEN DECLARED, INPUT STATEMENTS ARE EXECUTED. OPERATOR THIS IS THE "NOT" OPERATOR ANY SYMBOL THAT IS NOT THE NAME OF A VALUE MAY BE USED AS THE NAME OF AN OPERATOR. , OPERATORS CAN BE DEFINED AT ANY POINT OF A SUN, NOT NECESSARILY AT THE BEGINNING. OPERATORS CAN BE REDEFINED, THE NEW DEFINITION OVERRIDING THE OLD. EACH OP STATEMENT IS FOLLOWED BY A SERIES OF QUESTIONS. > > > > > > UNARY OR BINARY ? ; STATE THE TYPE OF OPERATOR U MARY **INPUT ERROR. MUST BE "UNARY" OR "BINARY" OR ANY SYMBOL BEGINNING WITH UN OR BI -ONLY THE FIRST TWO LETTERS ARE USED. THE NOT OPERATOR IS UNARY UNARY OR BINARY ? UNARY PRECEDENCE ? 1000 **INPUT ERROR. PRECEDENCE ? -1 **INPUT ERROR. PRECEDENCE ? 99 - TRUE? FALS **INPUT ERROR. TRUE? FALSE - FALSE? TRUD **INPUT ERROR. STATE THE PRECEDENCE OF THE OPERATOR MUST BE BETWEEN 0 AND 999 THE PRECEDENCE OF AN OPERATOR IS IMPORT-ANT ONLY IN RELATION TO THE PRECEDENCE OF OTHER OPERATORS. FOR EXAMPLE, A PRE-CEDENCE OF 10 IS THE SAME AS THAT OF 900 IF ALL OTHER OPERATORS HAVE PRECEDENCE LESS THAN 10. MUST BE BETWEEN 0 AND 999 NEXT THE USER IS ASKED TO DEFINE THE VALUE OF THE OPERATOR FOR ALL POSSIBLE VALUES OF ITS OPERANDS. . MUST BE ONE OF THE DEFINED VALUES MUST BE ONE OF THE DEFINED VALUES I 43 > > > > > > > > > > FALSE? TRUE OP & ; DEFINE THE "AND" OPERATOR UNARY OR BINARY ? BUNARY **INPUT ERROR. MUST BE "UNARY" OR "BINARY" UNARY OR BINARY ? BINARY PRECEDENCE ? 49 TRUE S TRUE? TRUE TRUE S FALSE? FALSE FALSE & TRUE? FALSE FALSE & FALSE? FALSE OP | ; THE "OR" OPERATOR UNARY OR BINARY ? BIN PRECEDENCE ? 9 TRUE | TRUE? TRUE TRUE J FALSE? TRUE FALSE | TRUE? TRUE FALSE | FALSE? FALSE OP > ; IMPLY OPERATOR UNARY OR BINARY ? BIN PRECEDENCE ? 1 TRUE > TRUE? TRUE TRUE > FALSE? FALSE FALSE > TRUE? TRUE FALSE > FALSE? TRUE ; END OF OPERATOR DEFINITIONS. IF WE NEED MORE WE CAN ALWAYS ; ADD THEM LATER. TABLE —X > (Y S ->Z) THE TABLE STATEMENT IS A REQUEST TO PRINT THE VALUES OF THE EXPRESSION FOR ALL POSSIBLE COMBINATIONS OF VALUES OF ITS VARIABLES. ANY NUMBER OF VARIABLES ARE PERMITTED.,IF NECESSARY, VARIABLES WILL BE TRUNCATED TO SIX CHARACTERS IN THE TABLE HEADING. 44 > X Y Z : VALUE > • > TRUE TRUE TRUE : TRUE ; THIS TABLE IS PRINTED > TRUE TRUE FALSE : TRUE ; BY ALGEBRA., > TRUE FALSE TRUE : TRUE > TRUE FALSE FALSE : TRUE > FALSE TRUE TRUE :FALSE > FALSE TRUE FALSE : TRUE > FALSE FALSE TRUE :FALSE > FALSE FALSE FALSE :FALSE TRY (X & Y) > ( -X I Y) ; THE TRY STATEMENT IS AN ABBREVIATED » FORM OF THE TABLE STATEMENT. IF THE ; EXPRESSION HAS THE SAME VALUE V, SAY, ; FOR ALL POSSIBLE COMBINATIONS OF ; VALUES OF ITS VARIABLES, THE RESULT V ; IS PRINTED. OTHERWISE, ; "VALUE DEPENDS ON VALUE (S) OF VARIABLE (S) " ; IS PRINTED. > TRUE TRY (A | B) > B > VALUE DEPENDS ON VALUE(S) OF VARIABLE(S) Let us use the above d e f i n i t i o n s to solve the following pro-blem, we know the following three facts: 1. , If Jones did not meet Smith l a s t night, then either Smith was the murderer or Jones i s lyi n g . 2. I f Smith was not the murderer, then Jones did not meet Smith l a s t night and the murder took place after midnight 3. I f the murder took place after midnight, then either Smith was the murderer or Jones i s lyin g . . The guestion i s : was Smith the murderer? We can answer the question as follows: Let p represent "Jones met Smith l a s t night" Let g represent "Smith was the murderer" Let r represent "Jones i s l y i n g " Let s represent "The murder took place after midnight" Fact 1 can be expressed as ->p > (q J r) Fact 2 can be expressed as ->q > (~ip & s) Fact 3 can be expressed as s > (q I r) The above question can now be posed thus: Is i t always the case that <-P > (g I r)) & (-q > (-p & s)) & (s > (g | r)) > g 45 ; i s true, regardless of the truth values of p, g, r and s? ; The answer i s given by the following statement; TRY (-P > (Q | R) ) S (-Q > (-.P & S) ) S (S > (Q | R) ) > Q > VALUE DEPENDS ON VALUES OF VARIABLES ; Hence the conjunction of the above facts do not imply ; that Smith was the murderer. Let us examine the table., TABLE ({-TP > (Q 1 R)} & (-Q > ( - P S S) ) & (S > (Q | R) ) ) > Q > p Q R S : VALU > j > TRUE TRUE TRUE TRUE : TRUE~ > TRUE TRUE TRUE FALSE :TRUE > TRUE TRUE FALSE TRUE :TRUE > TRUE TRUE FALSE FALSE :TRUE > TRUE FALSE TRUE TRUE : TRUE > TRUE FALSE TRUE FALSE :TRUE > TRUE FALSE FALSE TRUE : TRUE > TRUE FALSE FALSE FALSE :TRUE > FALSE TRUE TRUE TRUE : TRUE > FALSE TRUE TRUE FALSE : TRUE > FALSE TRUE FALSE TRUE :TRUE > FALSE TRUE FALSE FALSE :TRUE > FALSE FALSE TRUE TRUE :FALSE > FALSE FALSE TRUE FALSE : TRUE > FALSE FALSE FALSE TRUE :TRUE > FALSE FALSE FALSE FALSE : TRUE ; The value "FALSE" appears in only one l i n e i n the l a s t ; column - a narrow escape indeed for Smith! The machine-independent part of ALGEBRA was o r i g i n a l l y coded in L, a high-level Abstract Logical Language (ALL) used by Brown for implementing his ML/1 macro processor 2. , The L version has been mapped into LOHL, an ALL set at a much lower l e v e l than L. Brown4 gives a complete description of LOWL. 46 2.2.2 Outline of LOWL LOWL statements have a format s i m i l a r to assembly language. They are written one to a l i n e , and each consists of an optional la b e l followed by a mnemonic operation code followed by a number of arguments separated by commas., Each i n s t r u c t i o n has a fixed number of arguments - i f a certain argument i s not applicable i n a given case, i t i s indicated by an X. The argument l i s t i s n u l l f o r some inst r u c t i o n s . , arguments that are l i t e r a l character strings are enclosed i n quotes. The following are some sample LOWL statements: NB 1 THESE ARE SAMPLE LOWL STATEMENTS' DCL HOLD OK LAL 1 STV HOLD,X ALIGN GOSOB TEST,X CAL 0 GOEQ OK INCR BUMP HOLD,2 BSTK LOWL consists of a kernel, the statements of which are used by a l l software encoded i n i t , plus extensions oriented towards each i n d i v i d u a l piece of software. For example, ALGEBRA needs two extension statements, the EMESS and the QMESS statements, i n addition to the 60 statements in the kernel. Almost a l l statements i n LOWL involve a storage address, and a l l assignments, comparisons and arithmetic operations are done via three r e g i s t e r s . A, B and C.,,, A i s the numerical accumulator. 47 B i s £he index register. C i s the character r e g i s t e r . A l l statements that use the A or B registers have numerical operands, and those that use the C register have a single character as operand. The statements i n the kernel can be c l a s s i f i e d roughly as follows: a. statements for declaring variables; b. , data d e f i n i t i o n statements for defining table items; c. load statements - load a value into one of the reg i s t e r s A, B or C; d. store statements; e. arithmetic and l o g i c a l statements - these include addition, subtraction, m u l t i p l i c a t i o n and ANDing; f. compare and branching statements; g. statements for defining and branching into and out of subroutines; h. stacking and block moving statements; i . , I/O statements; j . , comment and layout statements. 2.2.3 ALGEBRA Coding The coding i s divided into two parts - the machine-independent (MI) part, which i s coded i n LOWL and must be mapped into the assembly language of the object machine, and the machine-dependent (MD) part which needs to be coded by hand 48 for each implementation. The MD-logic consisted of some i n i t i a l i z a t i o n code plus a set of short subroutines. The i n i t i a l i z a t i o n code performs the following tasks: 1. reserves storage for the stacks used by LOWL, and sets pointers to point to the star t and immediately beyond the end of the reserved area; 2. i n i t i a l i z e s the subroutine stack; 3. sets up the handling of interrupts during a run of ALGEBRA; 4. i n i t i a l i z e s the output buffer; 5. prints an introductory message; 6 . branches to the lab e l BEGIN i n the Mi-logic. The subroutines reguired were the following: MDLINE - reads a l i n e of input and sets a pointer to point at the f i r s t character of the buffer; checks i f end - o f - f i l e was detected. MDQUIT - closes a l l I/O (outputs an incomplete l i n e i n the output b u f f e r ) , and returns to the Operating System (not to i t s point of c a l l ) . MDERCH, HDRCH, MDQCH - outputs the character i n the C regist e r on the message, r e s u l t s and guestions stream, respectively - in thi s case, the f i l e attached to the MTS l o g i c a l I/O unit SPRINT. 49 2.2.4 Mapping the Ml-logic The major part of the project was concerned with the mapping of the LOWL version of ALGEBRA into the assembly language of the IBM 370/168, using STAGE2 as the mapping t o o l . A number of problems arose, mainly due to the r e s t r i c t i o n s imposed by the 370 Assembler on the format of statements i t would accept, and the argument and template matching conventions of STAGE2. 2.2.4.1 Source Format Problems In the following n represents a blank. , The most troublesome problems arose because the Assembler does not allow blanks i n the argument l i s t of an operation code, e. g. L GH8,oHOLD i s i n v a l i d . T y p i c a l l y , these problems arose because the LOWL l i s t i n g from which we worked was i n free format, in the sense that an arbitrary number (but at least one) of blanks separated the various f i e l d s of an in s t r u c t i o n , with zero or more blanks at the end of the ins t r u c t i o n . For example, consider the following macro d e f i n i t i o n f o r the LAV (Load A from a Variable) statement; 5 0 »nLAVann*., 1 | S 1 0 L #GBA ,X20*F1$ $ If the source statement was pnaanLAVnnaFFPT,X the generated i n s t r u c t i o n would be aaaaaL #GRA,FFPT which i s a l l r i g h t , but i f the source statement was nnnnaLAVrinnnFFPT,X the generated i n s t r u c t i o n would be aaaaaL #GRA,nFFPT which i s an i n v a l i d assembler statement. I f the template was written with 4 blanks between the V and the second parameter f l a g , then the generated i n s t r u c t i o n for the second statement, would by v a l i d , but now the f i r s t would not match the template. The only way to solve the problem was to write a procedure which would accept the free-format l i s t i n g and produce a fixed-format l i s t i n g , with a known fixed number of blanks between the various f i e l d s . The following procedure would accomplish t h i s : INLENGT EQU 4 SET UP REGISTERS CHAR EQU 5 INPTR EQU 6 OUTPTR EQU 7 BALR 1 2 , 0 SET UP BASE REG USING * , 1 2 ENTER NEXTLN SCARDS INBUFF, (INLENGT),EXIT=E0F READ A LINE ** GOTO EOF IF END-FILE MVC OUTBUFF (1) ,BLANK BLANK THE OUTPUT MVC OUTBUFF+1(79),OUTBUFF BUFFER. CLI INBUFF /C ,* , IS IT A COMMENT? BE OUTCOM YES, WRITE IT OUT SR INPTR,INPTR INIT BUFFER POINTERS 51 LA OUTPTR,5 GETLAB IC CHAR, IN BUFF (INPTR) GET THE LABEL, IF ANY CLH CHAR,1,BLANK A BLANK ENDS THE BE SKPBLNK LABEL FIELD STC CHAR,OUTBUFF(INPTR) MOVE NON-BLANK TO OUTBUFF LA INPTR, 1 (INPTR) INCREASE IN-BUFFER PTR B GETLAB SKPBLNK LA INPTR,1 (INPTR) CR INPTR,INLENGT WRITE LINE IF IT HAS BE OUTPUT BEEN PROCESSED IC CHAR,IN BUFF(INPTR) THIS SECTION OF CODE CLH CHAR,1,BLANK SKIPS OVER THE BLANKS BE SKPBLNK BETWEEN FIELDS. , LA OUTPTR,6 (OUTPTR) STCHAfi STC CHAR,OUTBUFF-1 (OUTPTR) LA INPTR, 1 (INPTR) CR INPTR,INLENGT AN END-OF-LINE CAN END BE OUTPUT THE ARGLIST, IF ANY IC CHAR,INBUFF(INPTR) CLM CHAR,1,BLANK A BLANK ENDS THE BE SKPBLNK OPCODE OR ARGLIST LA OUTPTR, 1 (OUTPTR) B STCHAR OUTPUT SPUNCH OUTBUFF, (OUTPTR) B NEXTLN OUTCOM SPUNCH INBUFF, (INLENGT) B NEXTLN EOF EXIT BLANK DC C« ' INBUFF DS CL80 OUTBUFF DS CL80 END The templates could now be written with the appropriate number of blanks between parameter fla g s . This solved most of the problems. However, i n certain cases, a t r a i l i n g blank s t i l l caused headaches. An example was the LAM (Load A Modified) statement., The macro d e f i n i t i o n o r i g i n a l l y used was * nLAMannna'| %10 L #GRA,%20(#GRB)$ $ If the input statement was L25noaaLAMnnnaa8 52 with no t r a i l i n g blank, the i n s t r u c t i o n generated would be L25oannL #GRA,8(#GRB) which i s a l l r i g h t . But i f the statement was L25nannLAMannnn8n the generated i n s t r u c t i o n would be L25anoa.L #GRA, 8n (#GRB) which i s an i n v a l i d Assembler statement. The problem could have been solved by using the above procedure which also chops o f f t r a i l i n g blanks. (The one used o r i g i n a l l y did not do so). Another solution was to use some character to indicate the end of a source l i n e , as i s customary when writing programs using the FLUB language., But since the number of statements (4) causing such problems were few, i t was easier to introduce another macro d e f i n i t i o n with the template 'nLAMnnnnn1n|. It should be remarked that ST AG £.2 looks for an expression which i s balanced with respect to parentheses to match with a parameter f l a g . This caused a problem with the mapping of the CCL (Compare C with a L i t e r a l ) statement. The d e f i n i t i o n was "aCCLnonnn*) XIOaCLI #CHARLOC,C%20%F1$ $ This works well f o r statements l i k e CCL 'A' or CCL '0 f.„ But when i t comes to CCL » (' or CCL •) •, 53 STAGE2 would not match the unbalanced parenthesis with the parameter f l a g , and hence the source statement was considered a mismatch with the given template. As a r e s u l t , the source statements CCL • ( • and CCL ') •, were punched out instead of CLI *CHABLOC,C*(' and CLI #CHARLOC,C•}'., In our case, since there were only two instances to consider, we simply translated them by hand to the 370 Assembler inst r u c t i o n s . 2,2.4.2 The OF Macro One of the more d i f f i c u l t tasks of the mapping was the handling of the OF macro. Using t h i s macro i s one way to represent numerical constants. I t uses the submacros LCH - the number of storage units used to represent a character; LNM - the number of storage units used to represent an integer; LICH - 1/LCH. The OF macro i s of the form OF (argument) where "argument" i s one of a. N*S+S b. N*S-S c. S + S 54 a. s-s e. S where N stands for any positive integer and S for any of the submacros. Examples of the OF macro are OF (LNM+LNM) OF(LCH) 0 7 ( 3 * L C H + L N H ) . I t i s used, f o r example, i n LAL OF (LNM+LNM) i . e., load A with the value 8 ( i f LNM i s 4) . On the IBM 370/168, LCH i s 1 and LNM i s 4., A s p e c i a l STAGE2 macro was defined » EQUAL «| %F3$ $ This macro inserts i t s f i r s t argument i n the STAGE2 memory and gives i t the value of the second argument, evaluated as an arithmetic expression. For example, after the statement LCH EQUAL 1 i s encountered, LCH and 1 can be used interchangeably. Now consider the d e f i n i t i o n of the OF macro: •OF (') ' | %10%24%30%F1$ $ The whole l i n e i s copied as i s , except that OF(expression) i s replaced by the value of "expression". Let us i l l u s t r a t e the workings of t h i s macro via the BUMP 55 i n s t r u c t i o n . The format of the BUMP statement i s BUMP variable,expression and i t increases the value of i t s f i r s t argument by i t s second argument. For example, BUMP HOLD,4 increases the value of HOLD by 4. The BUMP macro d e f i n i t i o n i s as follows: • BUMP • , ' 1 %10 LA #GRT,%30$ A #GHT#X2036F1$ ST #GRT,%20%F1$ $ Consider the input statement L10 BUMP STKPT,0F(3*LCH+LNM) The f i r s t statement generated by the above d e f i n i t i o n i s L10 LA #GRT,OF<3*LCH+LNM) But since the f i r s t l i n e in the body of the d e f i n i t i o n does not end with %F1, the generated l i n e i s rescanned to see i f i t matches any given template. I t turns out that i t matches the template of the OF macro. That d e f i n i t i o n evaluates the expression 3*LCH+LNM and f i n a l l y the l i n e L10 LA #GRT,7 i s generated. The f u l l output from the above c a l l of BUMP i s L10 LA #GRT,7 A #GRT,STKPT ST #GRT,STKPT 56 2.2,4.3 Happing of Registers The numerical r e g i s t e r s A and B were mapped into two general purpose re g i s t e r s . However, the character r e g i s t e r C was held i n memory. It was designated by #CHARLQC. Since the 370 i n s t r u c t i o n set contains a number of memory-memory and memory-immediate ins t r u c t i o n s , t h i s choice for C enabled a much more concise mapping of ALGEBRA than i f C was mapped to a general register., For example, consider the LOWL statement CCI CPTR which compares the character i n the C register with the character pointed at by CPTR. In the implementation, the above statement was mapped to L #GRT,CPTR CLC #CHARL0C<1) ,0 (#GRT) However, i f the general r e g i s t e r , #GRC, say, was used as the C regist e r , the generated statements would be something l i k e L #GRT,CPTR IC #GRT,0(#GRT) N #GRT,=X«0OOO00FF' CR #GRC,#GRT Even t h i s assumes that the high-order 24 bi t s of #GRC are always zero. The AND in s t r u c t i o n could be eliminated i f #GRT represents a re g i s t e r whose high-order 24 b i t s are always guaranteed to be zero. In either case, holding C i n memory enables fewer statements to be generated. The same observation holds for almost a l l the other i n s t r u c t i o n s involving the C 57 r e g i s t e r . 2.2.4.4 Mapping the Output Statements - MESS, R MESS and QMESS The three output statements were implemented the same way. The biggest problem was encountered i n dealing with newlines -as represented by a within the argument. For instance, the statement MESS '**INVALID STATEMENTS' should cause ••INVALID STATEMENT to be printed on the output device, whereas MESS »**INVALID STATEMENT' should simply place the message i n the output buffer without printing i t (unless the buffer overflows). This was accomplished by passing the argument s t r i n g to a routine which sequenced through the str i n g , taking the appropriate action depending on whether or not a '*$" was encountered. I f the current character was a "$", then the output buffer was written on the output device. Otherwise, the output buffer pointer was increased by one. I f th i s now exceeded the length of the buffer, the buffer was written. Otherwise the current character was stored i n the buffer. 58 2.2.5 Further Notes on Implementation The debugging of the macros was f a c i l i t a t e d by a macro t e s t program, LOWLTEST. The complete text of t h i s program i s given by Brown*. Subroutine c a l l s are handled by a stack mechanism. When the subroutine i s entered, the return address i s pushed on the stack, and when the routine i s about to be exited, the stack i s popped, giving the return address. The program accepts interrupts at any time. For instance, i f a large table i s being output, the user can interrupt i t without losing any information concerning values or operator d e f i n i t i o n s . If no values have been defined when the interrupt occurs, a return to the Operating System i s taken.. A complete l i s t i n g of the macros f i n a l l y arrived at i s given in Appendix E. For those macros implemented by subroutine c a l l s , the subroutines are given i n Appendix F., 2.2.6 Conclusions The mapping t o o l , STAGE2, was adeguate but not id e a l . A powerful macro assembler might have avoided the format problems mentioned e a r l i e r , because the LOWL statements are of the form that i s readily acceptable to such processors. Also bypassed would be the problem that STAGE2 had in t r a n s l a t i n g the CCL • ( ' statement. On the other hand, i t may not have been 59 able to handle the c a l l of the OF macro within another macro c a l l . Problems may also have arisen due to r e s t r i c t i o n s imposed on what characters could appear i n the replacement text of macro bodies. For example the IBH 370 Assembler does not allow one to generate a comment (a l i n e starting with *) from within a macro. 60 Bibliography I . , Brooker, R. A. And Morris, D. - A General Translation Program for Phrase Structure l4aag.ua.aSS* Jour. ACM,9*7l, pp7, 1-T0~7l962) 2. Brown, P. J. - The HL^1 Macro Processor, Comm. ACM,10,10, pp. 618-623 (1967)." ~ 3. Brown, P. J. - Using a Macro Processor to Aid Software Implementation. Computer Journal,12,4, pp. 327-331 (1969)*." 4.. Brown, P. J. - Macro Processors and Techniques f o r P o r t a b l e Software, Wiley &~Sons~7l974)7 ~ 5. Brown, P. J. And Lowe, J.D. - A Comeuter P£oqram for Siab o l i c Logic, B u l l e t i n IMA,7, 1 T7~pp7320-322 77971) . ~ 6.,, Ferguson, D. , E. „ - The Evolution, of the Me^a-assembly. Program, Comm. ACM,9,3, pp7, 190-193 7l966}, 7. Griswold, R. E. - The Macro ISElementation- of SNOBOL4, Freeman, San Francisco (1972). 8. Halpern, M. I. - Towards a General £roeessor for Programming Languages, Comm. ACM,11,1, pp. 15-25 (1968) . 9.,, Koster, C,,H, - Portable Compilers and the ONCOL. Problem, IFIP Working Conference on Machine Oriented Higher Level Languages, Trondheim, 1973. 10.,, Masterson, K, S. - Compilation for Two Coigute^s Using NELIAC, Comm. ACM,37l1, pp.,~607-611 (196077" I I . ., Mc Il r o y , M. ,D. - Macro Extensions of Compiler. Langu.ages, Comm. ACM,3,4, pp7 214-220 7t960)7 12., Mock, 0. et a l - The Problem of £rogramm,ing Communicatioa Mith Changing Machnes - a Profiosed Solution, Comm., ACM,1, Aug. pp., 12-18, Sept. pp. 9-15 7l958) . 13, Newey, M.,C., Poole, P. C. , And Waite, W. M. - Abstract Machine Modelling to Produce Portable Software - a Review and Evaluation, Software - Practice and Experience,2, pp7, 707-136 (1972). 14.,, Orgass, R . J . and Waite, W. ,M. - A Base f o r a- Mobile Programming System, Comm. ACM,12,9, pp. 507-510 (1969) " . - " 15.,, Poole, P. , C. , And Waite, W. M» , - Machine- Is492§fii§S.t 61 Software, Proceedings of the ACM 2nd Symposium on Operating System P r i n c i p l e s , Princeton, New Jersey (1969) . 16. , Richards, M. A. y- BCPL - A Tool for Comgiler l e i t i n g and System Programming, AFIPS Conference Proceedings,34, pp. 557-566 (1969) . 17. Richards, M.A. - The Portability, of the BCPL Compiler, Software - Practice and Experience,1, pp., 135-146 (1971) . 18.,, Richards, M. A. - Boot shagging the BCPL. Compiler Using. INTCODE, IFIP Working Conference on Machine Oriented Higher Level Languages, Trondheim, 1973., 19. Ste e l , T. B.,- ONCOL: the Myth and the Fact, Annual Review in Automatic Programming,2, pp., 325-344 (1961). 2 0 . Strachey, C. - A General Purpose Macrogenerator, Computer Journal,8,3, pp7~ 225-241~(1967)7 21.,, Waite, W. M. - A Language Independent Macro E£2£essor, Comm. ACM,10,77 Pp7~ 433-440 "(1967)". 22., Waite, W.,M. - Building a fiobile firogramming System, Tech., Sep., 69-2, Graduate School Computing Center, U of Colorado, Boulder, colo. USA. 23. Waite, W.,M. - The ST AGE 2 Macro Processor, Tech..,, Sep., 69-3, Graduate School Computing Center, U of Colorado, Boulder, colo. OSA. 24.,, Waite, W. , M. - The Mobile- Programming System: STA.GE2., Comm., ACM, 13,7, pp7415-42T" (1970)*. , 25. Warshall, S. - Laa2uaS§ lB^§£§5dence? # Incompatibility, Infotech State of the Art "Report 9, pp. 233-244 (1972) . 26.,, Wilkes M. , V. , - An Exrjeriment &ith a Se^f-compiling Q2SfiiI§£ £.2L §. L i s t Processing Language, Annual Review in Automatic Programming, 4, pp., 1-48 (1964), 27. Wilkes M.„V, ,- The Outer and Inner Sy.nt.ax of a Programming Language, Computer Journal,11,3, pp. 260-263 (1968). 62 Appendix A The following are the SIMCMP mapping macros used for producing STAGE2, Version 1. . '$'0 FLG ' = '. LH TEM,LIST+'21*3$ STH TEM,LIST+'11*8$ $ VAL 1 = PTR 1. L T£M,LIST+4+'21*8$ STH TEM,LIST+2+»11*8$ $ PTR • = VAL ». LH TEM,LIST+2+'21*8$ ST TEA,LIST+4+'11*8$ $ GET ' = '. L TEM,LIST+4+'21*8$ LD EVENS,LIST(TEM)$ STD EVENR,LIST+'11*8$ $ STO » = » . L TEM,LIST+4+' 11*8$ LD EVENR,LIST+»21*8$ STD EVENR,LIST (TEM)$ $ TO » ' . B 1L»10'20$ $ STOP. , EXIT$ $ TO " IF FLG » = '. CLC LIST+'31*8 (2),LIST+»41*8$ BE LL•10•20$ $ TO » » IF VAL • = ». CLC LIST+2+'31*8(2),LIST+2+•41*8$ BE LL»10'20$ $ TO " I F PTR « = ». CLC LIST+4+»31*8(4),LIST+4+»41*8$ BE LL'10'20$ $ TO •' IF FLG * NE •., CLC LIST+'31*8 (2),LIST+« 41*8$ BNE LL*10'20$ $ TO " IF VAL • NE '. CLC LIST+2+'31*8 (2),LIST+2+*41*8$ 6 3 BNE LL * 10 * 20$ $ TO ' « I F PTR • NE • . CLC LIST+4 + *31*8 ( 4 ) , L I S T + 4 + » 4 1 * 8 $ BNE L L * 1 0 « 2 0 $ $ TO • ' I F PTR * GE ' , L TEM,LIST+4+*31*8$ C TEM ,L I ST+4+«41 * 8$ BNL L L « 1 0 * 2 0 $ $ TO • ' BY ' . LA TEM,L*00+4$ ST TEM/LIST+4+*31*8$ L'OO B LL»10»20$ $ RETURN BY •. L RTN,LIST+4+ '11*8$ BR RTN$ $ LOC ••. L L * 10*20 SS TEM,TEM USED AS A NOOP$ $ END PROGRAM. END$ $ VAL ' = ' + •. LH TEM,LIST+2+ '21*8$ AH TEM,LIST+2+ '31*8$ STH TEM,LIST+2+*11*8$ $ VAL * = * - * . LH TEM,LIST+2+*21*8$ SH TEM,LIST+2+*31*8$ STH T E M ^ I S T * ^ * * 11*8$ $ PTR » = • + ' . L TEM , L I ST+4+«21 * 8$ A TEM,LIST+4+*31*8$ ST TEM,LIST+4+*11*8$ $ PTE • = » - » . L TEM ,L I ST+4+»21 * 8$ S TEM,LIST+4+*31*8$ ST TEM,LIST+4+*11*8$ $ PTR • = * / * . L £ V E N R , L I S T + 4 + * 2 1 * 8 $ SRDA EVENR,32$ D EVENR,LIST+4+ '31*8$ ST ODDR,L I ST+4+»11 *8$ $ PTE • = * * ' , L ODDR # L I ST+4+»21 * 8$ 64 M EVENR,LIST+4+»31*8$ ST 0DDR,LIST+4+'11*8$ $ VAL » = CHAR., L PAR1,MINUS2$ BAL RTN,ICHIO$ STH RTNVAL,LIST+2+'11*8$ $ CHAR = VAL •., LH PARI,LIST+2+'11*8$ BAL RTN,ICHIO$ STH RTNVAL,LIST+'11*8$ $ READ NEXT '. LH PARI,LIST+2+'11*8$ BAL RTN,IREAD$ STH RTNVAL,LIST+*11*8$ $ WRITE NEXT *. LH PARl,LIST+2+*11*8$ BAL RTN,IWRITE$ STH RTNVAL,LIST*'11*8$ $ REWIND ». L RTNVAL,TWO$ STH RTNVAL,LIST+*11*8$ $ MESSAGE * * ' • TO * . SPRINT M'10*20*30* 40, L*10» 20•30*4 0$ SR RTNVAL,RTNVAL$ STH RTNVAL,LIST+*51*8$ 65 Appendix B The following are the SIMCMP mapping macros used for producing STAGE2, Version 2. .' $*0 FLG • = ». L TEM,LIST+'21*12$ ST TEM,LIST*'11*12$ $ VAL • = PTE L TEM,LIST+8+'21*12$ ST TEH,LISI+4+'11*12$ $ PTR • = VAL $ GET ' = L TEM,LIST+4+«21*12$ ST TEM,LIST+8+*11*12$ L TEM,LIST+8+*21*12$ LH TEM1 ,LIST (TEM) $ ST TEM1,LIST+*11*12$ LH TEMl,LIST+2 (TEM) $ ST TEM1,LIST+4+*11*12$ L TEMl„LIST+4 (TEM) $ ST TEM1,LIST+8+»11*12$ $ STO • = •» . L TEM,LIST+8+'11*12$ L TEM1,LIST*•21*12$ STH TEM 1,LIST (TEM) $ L TEM1,LIST+U+'21*12$ STH TEMl,LIST + 2(TEM) $ 1 TEMl,LIST+8+'21*12$ ST TEMl,LIST + 4(TEM) $ $ TO " . B LL 110*20$ $ STOP.„ EXIT$ $ TO '' IF FLG ' = '. CLC LIST + 2+'31*12 (2) ,LIST + 2 +•41*12$ BE LL»10'20$ $ TO •• IF VAL • = «. CLC LIST+6+131*12 (2) ,LIST+6+ «41*12$ BE LL*10*20$ $ TO •• IF PTE ' = '. CLC LIST+8+«31*12 (4) ,LIST+8 + *41*12$ BE LL«10'20$ $ TO ' » I F FLG • NE * . CLC LIST + 2+ »31*12(2),LIST+2+» 41*12$ BNE LL'10*20$ $ TO * * I F VAL ' NE * . CLC LIST+6+»31*12(2),LIST+6+*41*12$ BNE LL•10*20$ $ TO *• IF PTB ' NE ' . CLC LIST+8+'31*12(4),LIST+8+'41*12$ BNE LL'10*20$ $ TO *• I F PTR * GE * . L TEH,LIST+8+'31*12$ C TEM,LIST+8+»41*12$ BNL LL'10'20$ $ TO •• BY *. LA TEM,L*00+4$ ST TEM,LIST+8+'31*12$ L'OO B LL*10»20$ $ RETURN BY *. L RTN,LIST+8+*11*12$ BR RTN$ $ LOC * * . LL'10*20 SR TEM,TEH USED AS A NOOP$ $ END PROGRAM. END$ $ VAL • = » + «. L TEM,LIST+4+*21*12$ A TEM,LIST+4+* 31*12$ ST TEM,LIST+4+*11*12$ $ VAL » = « - * . L TEM,LIST+4+«21*12$ S TEM,LIST+4+»31*12$ ST TEM,LIST+4+*11*12$ $ PTR * = • + *. L TEM,LIST+8+«21*12$ A. TEM,LIST + 8+'31*12$ ST TEM,LIST+8+*11*12$ $ PTR • = • - ' . L TEH,LIST+8+*21*12$ S TEM,LIST+8+'31*12$ ST TEM,LIST+8+*11*12$ 67 PTR » = » / » . L EVENR,LIST+8+•21*12$ SRDA E V E N S ,32$ D EVENR,LIST+8+'31*12$ ST 0DDR,LIST+8+»11*12$ $ PTR » = » * • . L ODDR,LIST+8+'21*12$ M EVENR,LIST+8 + * 31*12$ ST 0DDR,LIST+8+«11*12$ $ VAL • = CHAR. L PAR1,BINUS2$ BAL RTN,ICHIO$ ST RTNVAL,LIST+4+'11*12$ $ CHAR = VAL '. L PARI,LIST+4+*11*12$ BAL RTN,ICHIO$ ST RTNVAL,LIST+»11*12$ $ READ NEXT •. L PARI,LIST+4+'11*12$ BAL RTN,IREAD$ ST RTNVAL,LIST+ * 11 *12$ $ HRITE NEXT ». , L PARI,LIST+4+'11*12$ BAL RTN,IWRITE$ ST RTNVAL,LIST+•11*12$ $ REWIND •. MVC LIST+'11*12(4),TWO$ $ MESSAGE '• " TO ». SPRINT M*10»20'30'40,L»10«20'30'40$ SR RTNVAL,RTNVAL$ ST RTNVAL,LIST+»51*12$ $$ 68 Appendix C The following are the S T A G E 2 mapping macros used for producing S T A G E 2 , Version 3 . . ' $ ' 0 (+-*/) IF • = » SKIP «. •F50$ $ IF * NE * SKIP • . , »F51$ $ SKIP ». 'F4$ $ FLG « = ». IF '20 •= 0 SKIP 3$ IF '20 = 1 SKIP 4$ IF '20 = 2 SKIP 5$ SKIP 6$ STH #ZERO,LIST+«18*8 'F1$ SKIP 6$ STH #ONE,LIST+»18*8 'F1$ SKIP 4$ STH #TBO,LIST+»18*8'F1$ SKIP 2$ LH TEM,LIST+'28*8 ,F1$ STH TEM,LIST+'18*8'F1$ $ VaL » = PTR «. L TEM,LIST+4+'28*8'F1$ STH TEM,LIST+2+*18*8'F1$ $ PTR • = VAL » . LH TEH,LIST+2+*28*8 ,F1$ ST TEM,LIST+4+«18*8'F1$ $ GET • = ' . L TEM,LIST+4+'28*8'F1$ LD EVENS,LIST (TEM) *.F1$ STD EVENR,LIST+'18*8*F1$ $ STO ' $ TO • • L TEM,LIST+4+»18*8»F1$ LD EVENR,LIST+«28*8»F1$ STD EVENR,LIST (TEM) *F1$ B L L ' I O ^ O ' F U $ STOP. EX IT ' FU $ TO • * IF FLG « = '. CLC LIST +'38*8 (2) ,LIST+« 48*8'F1$ BE LL'IO^O'FIS $ TO • 1 IF VAL • = ».,• CLC LIST+2+'38*8(2),LIST+2+*48*8*F1$ BE LL»10»20*F1$ $ TO •• IF PTE « = » . CLC LIST+4+'38*8(4) ,LIST+4+'48*8» F1$ BE LLMO^O'FIS $ TO •» IF FLG • NE « . CLC LIST+»38*8 (2) ,LIST+» 48*8'F1$ BNE LL f10«20*F1$ $ TO •• IF VAL • NE •. CLC LIST+2+«38*8(2),LIST+2+»48*8'F1$ BNE LL«10»20'F1$ $ TO ' * IF PTS ' NE *., CLC LIST+4+'38*8(4),LIST+4+»48*8»F1$ BNE LL»10»20»F1$ $ TO «• IF PTE » GE ' . L TEM,LIST+4+V38*8»F1$ C TEM,LIST+4+»48*8«Fl$ BNL LL ,10«20 ,F1$ $ TO •• BY *. LA TEM,L'00+4'F1$ ST TEM,LIST+4+«38*8'F1$ L'OO B 1L».10»20»F1$ $ RETURN BY *. L BTN,LIST+4+«18*8»F1$ BR RTN1F1$ $ LOC ••. LL'10'20 SR TEM,TEM USED AS A N00P»F1$ $ END PROGRAM. END* F1$ «F0$ $ VAL « = » + « . IF «30 = 0 SKIP 5$ IF »20 = 0 SKIP 9$ LH TEM,LIST+2+'28*8,F1$ AH TEM,LIST+2+,38*8,F1$ STH TEM,LIST+2+'18*8'F1$ SKIP 6$ IF '20 - 0 SKIP 2$ MVC LIST+2+'18*8 (2) ,LIST+2+«28*8*F1$ SKIP 3$ STH #ZER0,LIST+2+»18*8«F1$ SKIP 1$ MVC LIST+2+ 118*8(2),LIST+2+«38*8»Fl$ $ VAL • = • - » . _ LH TEM,LIST+2+«28*8»F1$ IF «30 NE 1 SKIP 2$ BCTR TEM,0«F1$ SKIP 1$ SH TEM,LIST+2+V38*8'F1$ STH TEM,LIST+2+ ,18*8»F1$ $ PTR • = « + • . IF «30 = 0 SKIP 8$ IF '20 = 0 SKIP 12$ L TEM,LIST+4+»28*8'F1$ IF «30 NE 7 SKIP 2$ AR TEM,tEIGHT'F1$ SKIP 1$ A TEM,LIST+4+»38*8»F1$ ST TEM,LIST+4+*18*8«F1$ SKIP 6$ IF «20 = 0 SKIP 2$ MVC LIST+4+'18*8 (4) ,LIST+4 + '28*8«F1$ SKIP 3$ ST #ZERO,LIST+4+«18*8«F1$ SKIP 1$ MVC LIST+4+*18*8(4),LIST+4+•38*8'F1$ $ PTR • = • • - » , L TEM,LIST + 4+'28*8'F1$ IF »30 NE 7 SKIP 2$ SB TEM,#EIGHT'F1$ SKIP 1$ S TEM,LIST+4+'38*8,F1$ ST TEM,LIST+4+»18*8«F1$ $ PTR » = 1 / . L EVENB,LIST+4+»28*8«F1$ SB DA EVENR,32'F1$1 D EVENR,LIST+4+»38*8*F1$ ST ODDR,LIST+4+«18*8»F1$ $ PTR • = » * » . L ODDR,LIST+«4 + ,28*8 ,F1$ M EVENR,LIST*4+» 38*8VF1$ ST 0DDR,LIST+4+ l18*8»F1$ $ VAL 1 = CHAR. L PAR1,MINUS2'F1$ BAL RTN,ICHI0*F1$ STH BTNVAL,LIST+2+'18*8«F1$ 71 CHAR = VAL •. LH PARl,LIST+2+'18*8»F1$ BAL RTN,ICHIO * F 1$ STH RTNVAL,LIST+*18*8 * F1$ $ READ NEXT ». LH PARI,LIST+2+'18*8'F1$ BAL RTN,IREAD* F1$ STH RTNVAL,LIST*•18*8»F1$ $ WRITE NEXT •. LH PARl,LIST+2+«18*8VF1$ BAL RTN,IWRITE«F1$ STH RTNVAL,LIST+'18*8*F1$ $ REWIND •. L RTNVAL,TWO'F1$ STH RTNVAL,LIST+*18*8*F1$ $ MESSAGE 1 1 • • TO 1. SPRINT M«10«20«30«40,L»10 * 20'30«40'F1$ STH #ZER0,LIST+'58*8«F1$ 72 Appendix D The following are the STAGE2 mapping macros used for producing STAGE2, Version 4. . »,$•(> (+-*/) I F « = * SK I P »F50$ IF * NE ' •F51$ $ SKIP ». •F4$ $ FLG » = • IF »20 = IF «20 = IF «20 = SKIP 6$ ST 6$ ST 4$ ST 2$ L ST SKIP SKIP SKIP SKIP 3$ 4$ 5$ SKIP SKIP SKIP $ VAL $ PTR $ GET #ZERQ,LIST+«18*12»F1$ #ONE,LIST+*18*12'F1$ #TSO,LIST+ «18*12»F1$ T E M ^ I S T + ^ S ^ ' F U TEM,LIST+'18*12»F1$ $ STO = PTR «. L TEM,LIST+8+* 28*12'FIS ST TEM,LIST+4+»18*12'F1$ = VAL •. L TEM,LIST+4+»28*12«F1$ ST TEM,LIST+8+»18*12'F1$ L TEM,LIST+8+»28*12»F1$ LH TEMP, LIST (TEM) *F1$ ST TEMP,LIST+»18*12'F1$ LH TEMP,LIST+2 (TEM) «F1$ ST TEMP,LIST+4+»18*12»F1$ L TEMP,LIST+4 (TEM) »F1$ ST TEMP,LIST+8+*18*12«F1$ L TEM,LIST+8+»18*12'F1$ L TEMP,LIST+«28*12'F1$ STH TEMP,LIST(TEM)'F1$ L TEMP,LIST+4+'28*12fFl$ STH TEMP,LIST+2 (TEM) «F1$ L T E M P , L I S T + 8 + f 2 8 * 1 2 , F 1 $ ST TEMP, L IST+4 (TEM) ' F 1 $ $ TO " . B L L M 0 » 2 0 ' F 1 $ $ STOP. , E X I T V F U $ TO » ' I F FLG » = •. CLC L I ST+2+*38*12 (2) , L I ST+2+•48*12•F1$ BE L L « 1 0 » 2 0 * F 1 $ $ TO ' » I F VAL • = ». CLC L I ST+6+*38*12 (2) ,L IST+6 + • 4 8 * 1 2 , F 1 $ BE L L » 1 0 ' 2 0 » F 1 $ $ TO « ' I F PTR • = • . CLC L I ST+8+*38*12 (4) , L I ST+8+•48*12•F1$ BE L L » 1 0 » 2 0 » F 1 $ $ TO «• I F FLG • NE • . CLC L I S T + 2 + ' 3 8 * 1 2 ( 2 ) , L I S T + 2 + » 4 8 * 1 2 ' F 1 $ BNE L L « 1 0 « 2 0 ' F 1 $ $ TO »• I F VAL » NE • . CLC L I S T + 6 + ' 3 8 * 1 2 ( 2 ) , L I S T + 6 + * 4 8 * 1 2 • F 1 $ BNE L L M 0 , 2 0 ' F 1 $ $ TO ' • I F PTE • NE « . CLC L I S T + 8 + ' 3 8 * 1 2 ( 4 ) , L I S T + 8 + » 4 8 * 1 2 • F 1 $ BNE L L M O ^ O ' F H $ TO •» I F PTE • GE » . L T E M , L I S T + 8 + ' 3 8 * 1 2 ' F 1 $ C T E H # L I S T + 8 + « 4 8 * 1 2 » F 1 $ BNL L L « 1 0 * 2 0 » F 1 $ $ TO * ' BY ' . LA TEM,L * 00 + 4•F1$ ST T E M , L I S T + 8 + • 3 8 * 1 2 ' F 1 $ L 'OO B L L « 1 0 » 2 0 » F 1 $ $ RETURN BY ' . L R T N , L I S T + 8 + » 1 8 * 1 2 ' F 1 $ BR RT N * F1 $ $ LOC ' « , L L ' 1 0 ' 2 0 SR TEM,TEM USED AS A N 0 0 P ' F 1 $ $ END PROGRAM., END* F1$ » F 0 $ $ VAL ' = • + '. IF '30 = 0 SKIP 5$ IF '20 = 0 SKIP 9$ L TEM,LIST+4+«28*12'F1$ A TEM,LIST+4+'38*12'F1$ ST TEM,LlST+4+'18*12»F1$ SKIP 6$ IF »20 = 0 SKIP 2$ MVC LIST+4+'18*12(4),LIST+4+» 28*12'F1$ SKIP 3$ ST #ZERO,LIST+4+'18*12'F1$ SKIP 1$ MVC LIST+4+'18*12(4),LIST+4+»38*12'F1$ $ VAL ' = ' - • . L TEM,LIST+4+«28*12'F1$ IF '30 NE 1 SKIP 2$ BCTR TEM,0'F1$ SKIP 1$ S TEM,LIST+4+«38*12'F1$ ST TEM,LIST+4+»18*12»F1$ $ PTR ' = ' + » . IF '30 = 0 SKIP 8$ IF '20 = 0 SKIP 12$ L TEM,LIST+8+'28*12»F1$ IF '30 NE 7 SKIP 2$ AR TEM ,#EIGHT•F1$ SKIP 1$ A TEM,LIST+8+'38*12'F1$ ST TEM,LIST+8+«18*12'F1$ SKIP 6$ IF »20 = 0 SKIP 2$ MVC LIST + 8 + * 18*12 (4) ,LIST+8+» 28*12»F1$ SKIP 3$ ST #ZERO,LIST+8+'18*12»F1$ SKIP 1$ MVC LIST+8+'18*12(4),LIST + 8 +'38*12» F1$ $ PTR ' = » - « . L TEM,LIST+8+»28*12'F1$ IF »30 NE 7 SKIP 2$ SR TEM,#EIGHT'F1$ SKIP 1$ S TEM,LIST+8+'38*12'F1$ ST TEM,LIST+8+*18*12'F1$ $ PTR • = • / '. L EVENR,LIST+8+'28*12»F1$ SRDA EVENR,32'F1$ D EVENR,LIST+8+'38*12»F1$ ST ODDR,LIST+8+»18*12»F1$ $ PTR » = « * • . L 0DDR,LIST+8+'28*12'F1$ M EVENR,LIST+8+'38*12'F1$ ST 0DDR,LIST+8+*18*12'F1$ $ VAL » = CHAR. 1 PAR1,MINUS2'F1$ BAL RTN,ICHI0»F1$ ST RTNVAL,LIST+4+'18*12'F1$ $ CHAR = VAL '. L PARl,LIST+4+«18*12'F1$ BAL RTN,ICHI0'F1$ ST RTNVAL,LIST+'18*12'F1$ $ READ NEXT ». L PARI,LIST+4+118*12'F1 $ BAL RTN,IREAD* F1$ ST RTNVAL,LIST+ * 18*12'F1$ $ WRITE NEXT «., L PARl,LIST+4 + « 18*12'F1$ BAL RTN,IIRITE»F1$ ST RTNVAL,LIST+'18*12'F1$ $ REWIND •. MVC LIST+'18*12(4),TWO'F1$ SET ERROR RETURN CODE $ MESSAGE " •» TO '. SPRINT M«10'20»30'40,L'10*20'30'40»F1$ SR #ZERO,#ZERO»F1$ RESET GR1 USED BY SPRINT ST #ZERO,LIST+'58*12»F1$ $$ 76 Appendix E The following are the STAGE2 macros used in the mapping of the LO&L version of ALGEBRA. }«$%0 (+-*/) 'OF (») » | %10%24%30%F1$ $ IF » = » SKIP »| %F50$ $ « EQUAL • | %F3$ $ SKIP •| % ? H $ $ « DCL « j 38F1$ 22222222 DS F$ $ » CON » | mo DC F'%20'$ $ « CON » [ %10 DC F ,%20»$ $ * EQU ',*) %F1$ 22222222 DS F$ $ • IDENT • , ' l %F1$ 22222222 EQU 333333333$ $ » NCH • J %10 DC AL.8(%20)%F1$ $ ' NCH » J X10 DC AL. 8 ($20) %F1$ $ » STR • | %10 DC CI20%F1$ $ ' LAV • , « | IF SS30 = R SKIP 2$ IF %30 = R SKIP 1$ %10 L #GRA,%20%F1$ $ » LBV « | %10 L #GRB,%20%F1$ $ ' LAI « | IF %2Q = 0 SKIP 3$ IF 120 = 0 SKIP 2$ S610 LA #GRA,%20$ SKIP 1$ %10 LR #GRA,#ZER0HF1$ $ • LCN » j %10 MVI #CHARLOC,<I20S&F1$ $ • LAI »,* I IF 3630 = R SKIP 3$ IF %30 = R SKIP 2$ 110 L #GRT,%20%F1$ 1 #GRA,0 (#GRT)%F1$ $ • LCI * , ' | IF S630 = R SKIP 3$ IF X30 = R SKIP 2$ %10 L #GRT,%20%F1$ MVC #CHARLOC(1) ,0 (#GRT) %F1$ $ • LAA ' , » | %10 LA #GRA,%20%F1$ $ • STV %10ST #GRA,%20fF1$ $ • S T I • , » | %10 L #GRT,%20%F1$ ST #GRA,0 (#GRT) %F1$ $ f CLEAR • | X10 ST #ZERO,X20*F1$ $ • AAV • J %10 A #GRA,%20%F1$ $ » ABV »| X10 A #GRB,%20%F1$ $ • AAL »| %10 LA #GRT,%20$ AR #GRA,#GRT%F1$ $ » SAV *| %10 S #GRA,X20%F1$ $ • SBV '| %10 S #GRB,JS20%F1$ $ » SAL »| %10 LA #GRT,%20$ $ ' S.BL 3610 LA $ ' MULTL 3610 LA $ • ANDV 3610 N $ • A HDL 1610 LA $ • BUHP 3610 LA $ ' CAV S610 C $ » CAL IF 3620 -IF 3620 • 3610 LA SKIP 1$ 3610 LTR $ * CCL 3610 CLI $ « CCN %10 CLI $ 1 CAI 3610 L $ ' CCI 3610 L $ • GO 3610 B $ 1 GOEQ 3610 BE $ » GONE SR #GRA,#GRT%F1$ ' I #GRT, 3620$ SR #GRB,#GRT36F1$ #GRT, 362036$ HR #GRAE,#GRT%F1$ #GRA,S6203SF1$ 'I #GRT,%20$ NR #GRAV*GRT36F1$ I #GRT,%30$ A #GRT,5620J6F1$ ST #GRT,.362036F1$ #GRA#J62036F1$ »l 0 SKIP 4$ 0 SKIP 3$ #GRT,%20$ CR #GRA,#GRT.36F1$ #GRA,#GRA36F1$ *CHARLOC,C362036F1$ * I #CHARLOC# 362036F1$ #GRT,?62056F1$ C #GRA,0 (#GRT) 36F1$ #GRT,12036F1$ CLC fCHARLOC (1) ,0 (#GRT) 1F1$ * » 1 * * # ' I X2036F1$ * i 11 * t1 I %2036F1$ i * t i l i t $610 BNE $ » GOGE X10 BNL $ • GOGE 3610 Bfl $ • GOLE 5610 BNH $ • GOLT %10 BL $ » GOPC %10 CLI $ • GOND 3610 CLI $ • GOADD 3610 L $ ' GOSUB 3610 BAL $ • SDBR %20 %20%F'\$ S2056F1$ • i t t 5620$F1$ i • • I j %20%Y1$ • i i t %20%F1$ iCHABLOCjC'A'^FlS BL %20%F1$ i i i I I i i i J #CHABLOC,C'0'56F1$ BL ?620%F1$ IC #GR A , #CHARLOC56F1 $ N #GRA,=X»0000000F«S6F1$ #GRA,S620%F1$ LA #GRT,*+8%F1$ B #G0ADD%F1$ #GRBTN,%20S6F1$ i » i I LA #GRPTR,4 (#GBPTR)HF1$ C #GBPTB,#BSTKSZ^F1$ BH #STKEBBlF1$ ST #GRRTN,#RTNSTK(#GRPTR) %F1$ IF X30 = X SKIP 1$ ST #GBA,363036F1$ $ • EXIT 3610 L IF S520 = SKIP 1$ $ ' LAM 3610 L $ • LAM 3610 L $ #GBBTN,#BTNSTK (#GEPTR) 36F1$ S #GRPTB,#F0UR%F1$ 1 SKIP 2$ B (3620-1) *4 (#GBRTN) 56F1$ BR #GRBTN 36F1$ I #GRA, 3620 (#GRB) $ #GRA,?620 (#GBB) $ ' LCM » | %10 MVC #CHARL0C{1) ,%20 (#GRB) $ $ • LCM »| %10 MVC tCHARLOC (1) , %20 (#GRB) $ $ ' ALIGN'I %10 BAL #GRRTN,#ALIGN%F1$ $ 1 CSS'| %10 L #GRPTR,#MINUS4%F1$ $ » FSTK'| %10 BAL #GRRTN,#FSTK%F1$ $ • BSTK*| %10 BAL #GRRTN, #BSTK5JF1$ $ • CFSTK'J %10 BAL tGRRTN,#CFSTK%F1$ $ » UNSTK «| %10 LA #GRA,%20&F1$ BAL #GRRTN,#UNSTK?£F1$ $ • FMOVE1| %1Q BAL #GRRTN,#FM0VE?SF1$ $ ' BMOVE*| %10 BAL #GSRTN,#BMOVE%F1$ $ • PRGST » j ** THIS IS THE START OF THE MI-CODE OF %20%F1$ $ • PRGEN *| END #START%F1$ %F0$ $ ' NB ' | *fS10 %20%F1$ $ • MESS * J %10 BAL #GRA,*+6+( (L»##foOO+1)/2*2) AROUND C0NS%F1$ DC Y(L'##%00) LENGTH%F1$ ##%00 DC C%2056F1$ BAL #GRRTN,#«SITE?JF1$ $ • QMESS •| 5610 BAL #GRA,*+6+( (L'##%00 + 1)/2*2) AROUND C0NS%F1$ DC Y(L'##%00) LENGTH%F1$ ##%00 DC C%20%F1$ BAL #GRRTN,#WRITE%F1$ $ « RMESS 1 | 81 % 1 0 B A L #GRA,*+6+((L»##S00+1)/2*2) AROUND CONS%F1$ DC Y ( L » # # % 0 0 ) L E N G T H 1 F 1 I ##%00 DC C % 2 0 % F 1 $ ' BAL # G R R T N , # H R I T E % F 1 $ $$ LNM EQUAL 4 LC H EQUAL 1 L I C H EQUAL 1 82 Appendix F The following procedures complement the mapping macros given i n Appendix E. They represent those LOWL statements which are mapped into subroutine c a l l s . ** THIS PROCEDOEE ALIGNS THE CONTENTS OF THE ** A REGISTER TO THE NEXT FULLWORD BOUNDARY. •ALIGN #OKA ** ** THIS ** FFPT ** #FSTK LR tGRTE,tGRA SRDA tGRTE,32 D tGRTE,fFOUR LTR tGRTE,tGRTE IS IT ALREADY ALIGNED ? BZ #OKA I.E. IS REMAINDER ZERO? L tGRT,tFOUR IF NOT, ADD (4-REMAINDER) SR #GRT,tGRTE IF NOT, ADD (4-REMAINDER) AR tGRA,tGRT TO THE A REGISTER BR tGRRTN PROCEDURE STACKS A ON THE FORWARDS STACK. POINTS TO THE FIRST FREE STACK LOCATION. ** STACK ** tCFSTK L tGRT,FFPT ST tGRA, 0 (tGRT) LA tGRT, LNM (tGRT) C tGRT,LFPT BNL ERLSO ST tGRT,FFPT BR tGRRTN INCREASE STACK POINTER IF FORWARDS STACK PTR MEETS BACKWARDS STACK PTS, THE STACK SPACE IS USED UP. ** ** STACK ** tBSTK C, AS REPRESENTED BY tCHARLOC, ON THE FORWARDS STACK. L tGRT,FFPT IC tGRTE,tCHARLOC STC tGRTE,0(tGRT) LA tGRT,LCH(tGRT) CHECK FOR STACK C tGRT,LFPT OVERFLOW, AS IN BNL ERLSO tFSTK. ST tGRT,FFPT BR tGRRTN A ON THE BACKWARDS STACK. L tGRT,LFPT S tGRT,tFOUR C tGRT,FFPT BNH ERLSO ST tGRT,LFPT ST tGRA,0 (tGRT) BR tGRRTN DECREASE BACKWARDS STACK PTR; STACK OVERFLOW IF IT MEETS FORWARDS STACK PTR. STACK A. 83 ** ** STORES IT ** #UNSTK UNSTACKS NUMBER AT THE TOP OF THE BACKWARDS AND IN A V A R I A B L E , WHOSE ADDRESS IS IN A.. L #GBT,LFPT L #GBB,0(#GBT) ST #GBB,0(#GRA) A #GRT,#FOUR ST #GRT,LFPT BR #GHRTN #GRA CONTAINS A(V) INCREASE BACKWARDS STACK PTR #GOADD M #GRAE,#FOUE AR #GBA,#GBT BR #GR A ** ** PERFORMS A CHARACTER-BY-CHARACTER MOVE FROM SOURCE ** (POINTED AT BY SRCPT) TO DESTINATION (POINTED AT BY ** DSTPT), STARTING WITH THE FIRST CHARACTER AND ENDING ** WITH THE LAST. THE NUMBER OF CHARACTERS TO BE MOVED ** IS GIVEN BY THE CONTENTS OF A. ** frFMOVE L #GRT,SRCPT L iGBTE,DSTPT #NXTMOV IC #GRB,0 (#GRT) STC #GBB,0 (#GRTE) LA #GBT,1 (#GRT) LA #GBTE, 1 (#GRTE) BCT #GBA,#NXTMOV BR tGBBTN ** ** THIS IS SIMILAR TO FMOVE ABOVE, EXCEPT THAT-THE ** MOVE STARTS WITH THE LAST CHARACTER AND ENDS ** WITH THE FIRST. ** #BMOVE L L AR AR #NXTMOVT BCTR BCTR IC STC BCT BR ** ** THIS PROCEDURE WORKS IN CONJUNCTION WITH #WRCH ** BELOW. THE CHARACTER STRING TO BE WRITTEN IS PASSED ** TO IT. REMEMBER THAT THIS STRING HAY OR MAY NOT ** CONTAIN THE NEWLINE CHARACTER{"$"). IT PASSES ** THE CHARACTERS ONE AT AT TIME (VIA THE C REGISTER) ** TO WBCH WHICH DETERMINES WHAT ACTION SHOULD BE TAKEN. ** #WRITE ST tGBBTN,#SAVADB1 LH #GRB,0 (#GRA) #GRT,SRCPT #GRTE,DSTPT #GRT,#GRA #GRTE,#GRA #GRT,0 #GRTE,0 #GRB,0(#GRT) #GRB,0 (#GRTE) #GRA,#NXTM0V1 tGRRTN 84 LA tGRA,2 (tGRA) ADDRESS OF STRING SR tGRAE,tGBAE INDEX TO STRING tNEXTCH IC tGRTE,0 (tGBAE, tGRA) STC tGRTE,tCHARLOC STORE CHAR IN C BAL tGRRTN,tWRCH LA tGRAE,1 (tGRAE) INCREASE STRING PTR BCT tGRB,tN EXTCH L tGRRTN,tSAVADRI BR tGRRTN ** ** THIS PROCEDURE TAKES DIFFERENT ACTIONS DEPENDING ** ON THE CHARACTER IN THE C REGISTER AND THE ** CURRENT LENGTH OF THE OUTPUT BUFFER. ** tWRCH CLI tCHARLOC,C $* WRITE LINE IF C CONTAINS BZ tNEWLINE $ OR CLI tCHARLOC,NLREP THE NEWLINE CHARACTER(X**05*') BZ tNEWLINE LH tGRT,tOUTLEN LA tGRT,1(tGRT) ELSE STORE CHAR IN THE IC tGRTE,tCHARLOC NEXT AVAILABLE LOCATION STC tGRTE,tOUTBUFF-1 (tGRT) IN BUFFER. , C tGRT,=F»132' WRITE BUFFER IF FULL BH tOUTPUT STH tGRT,tOUTLEN STORE NEW BUFFER LENGTH BR tGRRTN tOUTPUT STH tGRT,tOUTLEN tNEWLINE ST tGRRTN,tSAVADR SPRINT tOUTBUFF,tOUTLEN WRITE BUFFER ON DEVICE L tGRRTN,tSAVADR LA tGRT,1 INITIALIZE BUFFER LENGTH STH tGRT,tOUTLEN BR tGRRTN ** 

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-0051773/manifest

Comment

Related Items