UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Language and computer design for effective software systems Lillich, Alan W. 1979

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

Full Text

9 LANGUAGE AND COMPUTER DESIGN FOE EFFECTIVE SOFTWARE SYSTEMS by ALA M W. L I L L I C H B.S., Mathematics, Oregon State U n i v e r s i t y , 1975 B-S., Computer Scie n c e , Oregon S t a t e U n i v e r s i t y , 1975 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOE THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (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 s t andard. THE UNIVERSITY OF BEITISH COLUMBIA January, 1979 (cp Alan W. L i l l i c h , 1979 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e 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 e e t h a t t h e L i b r a r y s h a l l m a k e 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 a n d s t u d y . I f u r t h e r a g r e e 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 p u r p o s e s may be g r a n t e d by t h e H e a d o f my D e p a r t m e n t 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 n o t 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 . D e p a r t m e n t 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 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 D a t e / / . / ? " 7 ? A b s t r a c t This t h e s i s d e s c r i b e s two d i s t i n c t , but mutually s u p p o r t i v e , r e s e a r c h p r o j e c t s . The f i r s t i s the design and implementation of a high l e v e l language intended to be s u i t a b l e f o r w r i t i n g o p e r a t i n g systems among other l a r g e software products. I t provides f a c i l i t i e s f o r the c r e a t i o n and c o n t r o l of asynchronous processes along with powerful data and " s e q u e n t i a l " c o n t r o l s t r u c t u r e s . The second p r o j e c t i s the design and implementation of a machine a r c h i t e c t u r e which i s a c o n g e n i a l host f o r modern block s t r u c t u r e d languages. T h i s machine has s e v e r a l advantages compared to most of todays computers; code g e n e r a t i o n i s simple, the o b j e c t code i s very compact and the machine i s reasonably f a s t . E f f e c t i v e software systems are w e l l designed, r e l i a b l e , have "low" space-time products and are developed, maintained and used with a minimum amount of human e f f o r t . The work presented here i s intended t o be a v i a b l e f i r s t s tep towards the production o f an environment f o r the production of e f f e c t i v e software systems. Language and Machine Design f o r E f f e c t i v e Software Systems i i i Table of Contents PAST 1 - The programming language WISCH ....................... 1 A. Introduction to WISCH ... . 1 B. Excuses and r a t i o n a l i z a t i o n s ........................... 3 C. Overview 6 C . l . Programs and processes ............................ 6 C.2. Statements ....................................... 13 C. 3. Data types, l i t e r a l denotations and expressions .. 14 C-4. Modules ............... ---16 D. Primitive elements .................................... 17 D. I . Alphabet, i d e n t i f i e r s and comments ............... 17 D.2. Reserved words .....................................19 D.3. Special symbols .................................. 20 D.4. Standard i d e n t i f i e r s ............................. 21 D.5. A note on the syntax graphs ...................... 22 E. Compilation unit ...................................... 24 F. Declarations .......................................... 25 F.1. Constants ........................................ 25 F.2. Types ............. - ..................... 26 F.2. 1. Assignable types .......... ............ 29 F.2.1.1. Scalar types ........................... 29 F. 2.1.1.1. Boolean ................ ........ 30 F.2.1.1.2. Character 31 F. 2. "1.1.3. Integer ..................31 F.2. 1.1.4. Storage 33 F.2. 1.1.5. Enumeration ........................ .34 F. 2. 1.1-6. Subrange .......................... 35 F.2.1.2. Real 37 F. 2. 1.3. Powerset . 40 F-2-1.4. String ..... 43 F. 2-1.5. Normal pointer ......................... 46 F.2.2. Array ............................... 49 F.2.3. Record 51 F.2.4. Pool pointer 53 F.2.5. Pool - 54 F.2.6. Process ..................................... 55 F.2.7. Compatability, coercions and attributes ..... 56 F.3. Variable 60 F.4. Program .......................................... 61 F.5. Procedure ........................................ 63 F.6. Function ......................................... 64 F.7. Module 65 F. 8. Scope of names ................................... 67 G. Statements ............................................ 69 G. 1. Block - ......69 G.2. Assignment ....................................... 70 G.3. Procedure c a l l ................................... 72 G.4. Return ........ ....................... ...... ...... 72 G.5. If 73 G.6. Loop 74 G.7. Exit 75 Language and Machine Design f o r E f f e c t i v e Software Systems i v G.8. For 76 G.9. Iterate 77 G.10. Fork .......... - 78 G. 11. Bind 79 G. 1 2. Assert .... ........ 79 G.13- C r e a t e . . 80 G.14. Start 80 G.15. Stop ... 81 G.16. Destroy .......... 81 G.17. Await 82 G.18. Send ......... . .................. 82 G.19. Option 83 H. Expressions ........................................... 84 I. I/O f a c i l i t i e s 87 J. Loading and running programs dynamically .............. 89 K. Implementation of WISCfl . .. ..--90 L. Future work with W.ISCH ... ..... 92 PAST II - The architecture of a stack processor ............. 94 M. Introduction to ASP ................................... 94 N. Basic structure of ASP ---- 95 0. Design r a t i o n a l e ...................................... 100 P. Instruction repertoire ............................... 102 P.I, One address in s t r u c t i o n s ........................ 102 P.2. Immediate operand i n s t r u c t i o n s .....................104 P.3. Jump instructions ............................... 105 P.4. Program r e l a t i v e i n s t r u c t i o n s ................... 106 P.5. Memory block i n s t r u c t i o n s ....................... 106 P.6. Zero address load, store 6 save ................. 107 P.7. Machine r e g i s t e r access .........................108 P.8. Shi f t instructions .............................. 109 P.9. Word operations 10.9 P.10. Real operations ................................ 110 P.11. Other instructions ............................. 110 Q. Implementation of ASP ...................115 R. Future work with ASP ................................. 117 Bibliography ............................................... 119 Appendix 1. Shy WISCfl with a C? .......... . 121 Language and Machine Design f o r E f f e c t i v e Software Systems v Acknowledgements I would l i k e to thanki My wife Pat, f o r her patience and support- .. My advisor Bary Pollack, for h i s help and guidance. Dave Brent, for the excellent work done on the compiler. The department, for providing a salary for Dave. My o f f i c e mates, for their good company. My b i c y c l e , for teaching me the value of patience. WISCH Heport A. Introduction to HISCH 1 A. Introduction to HISCH High l e v e l languages have firmly established themselves as the only sensible t o o l f o r so-called applications programming tasks, but with a few notable exceptions, the realm of "systems" programming has remained within the t i g i i t grasp of assembly language hackers. The combined e f f e c t s of the inadequacy of commonly available languages, the need to "control the machine", the need f o r space/time e f f i c i e n c y and the t e r r i b l y backward state of most contemporary computer architectures have made t h i s area very resistant to the introduction of high-level languages. WISCH provides one approach to language design for systems programming. I t i s a member of the growing family of PASCAL based languages, bearing cl o s e s t resemblance to PLATON [SOB 7 5 J and MODULA £WIB 7 6 ] . It provides powerful data and control structures f o r t r a d i t i o n a l sequential tasks along with mechanisms for the creation and control of groups of concurrent processes. 1 The philosophy of WISCH i s that the programmer should concentrate on the high l e v e l structure of a system, and not on the d e t a i l s of how that structure i s to be implememted. Thus for example, concurrent processing f a c i l i t i e s are provided lThe word "sequential" here refers to the well-defined flow of control found i n most languages. Programs written i n F0RT8AN, COBOL, PASCAL, etc. are a l l sequential programs. A "concurrent" program i s a single program embodying two or more asynchronous processes- The moment-to-moment locus of control i n a concurrent program may depend not only on the source program and data but also on external objects such as peripheral devices, schedulers, etc. WISCH Report A. Introduction to WISCH 2 as language primitives with minimal s p e c i f i c a t i o n of their implementation. In e f f e c t , the language provides a small operating system kernel, s i m i l i a r to those constructed i n more t r a d i t i o n a l manners (eg., see £ K AH 78 j ) . WISCH i s also a strongly typed language, attempting to make maximal compile time checks on the v a l i d i t y of programs and using run-time checking where necessary. The language should be useful for constructing concurrent systems where the data structures and algorithms used are more important than the low l e v e l d e t a i l s of how the i n d i v i d u a l tasks are implemented and controlled. Obvious areas of application include operating systems, terminal concentrators, laboratory instrument monitors, etc. With i t s emphasis on the high l e v e l aspects of inter-task communications rather than the low l e v e l d e t a i l s of a pa r t i c u l a r implementation, the language should also be useful i n areas where " r e a l " parallelism would be very useful but i s not often found, such as simulation, graphics, multi-pass compilation, etc. (For a novel application of multi-programming see i DIJ 78].) B. Excuses and r a t i o n a l i z a t i o n s 3 r a t i o n a l i z a t i o n s Existing high-level languages have been used to write successful operating systems. A variant of ALGQL-60 has been used for some years by Burroughs for systems on t h e i r B5500 and l a t e r machines. MULTICS i n PL/I and UNIX in C are probably the best known examples. Others include OS-6 i n BCPL 1STO 7 2 J and SOLO in Concurrent Pascal J. BEI 753- EUCLID *.LAM 7 7 \ t MODULA, PLATON and SUE £ ATW 7 2 ] , also are inter e s t i n g languages in which operating systems could (almost) be written. Given t h i s body of existing work, why invent yet another version of the wheel? In looking for a language to do systems programming on a minicomputer, several c r i t e r i a were developed: 1 . The language must provide powerful data and control structures. A l l large software systems are primarily c o l l e c t i o n s of complex data structures and algorithms for their manipulation. 2. In balance with the above c r i t e r i o n , the language must not be excessively large. 3. The language must have b u i l t - i n mechanisms for concurrent programming. (An a r b i t r a r y decision to research what could be done with such languages.) 4. The language must provide adequate f l e x i b i l i t y to handle a wide range of " r e a l " problems, p a r t i c u l a r l y in the area of operating systems. I t must be more than a toy. HISCH Report hs. Excuses and HISCH E e p o r t B. E x c u s e s and r a t i o n a l i z a t i o n s 4 A l l o f t h e a b o v e l a n g u a g e s f a i l t o meet one o r more o f t h e s e c r i t e r i a . BCPL and PLATON a r e v e r y weak i n t h e a r e a o f d a t a s t r u c t u r e s (by t h e i n t e n t o f t h e i r d e s i g n e r s ) . S t o y a n d S t r a c h e y c l a i m "The r e s o u r c e s o f t h e i d e a l s o f t w a r e l a n g u a g e s h o u l d , i n o u r o p i n i o n , be c o n c e n t r a t e d a r o u n d c o n t r o l f a c i l i t i e s , a n d m a t t e r s c o n c e r n i n g s t o r a g e and r e p r e s e n t a t i o n l e f t v e r y much t o t h e p r o g r a m m e r . " T h i s i s f u n d a m e n t a l l y o p p o s e d t o t h e WISCH p h i l o s o p h y t h a t t h e s y s t e m p r o grammer o f t e n n e e d s p o w e r f u l c o n t r o l and d a t a s t r u c t u r e s . C i s a l s o weak on d a t a s t r u c t u r e s , b u t t o a much l e s s e r e x t e n t . C o n c u r r e n t P a s c a l i s d e p l o r a b l y weak i n p r o c e d u r a l m e c h a n i s m s . I t n o t o n l y f o r b i d s r e c u r s i v e r o u t i n e s and A l g o l - l i k e m u l t i p l e s c o p e l e v e l s , i t d o e s n o t e v e n a l l o w n e s t e d r o u t i n e s . The d a t a s t r u c t u r e s o f P L / I a r e f a r t o o r i c h i n some a r e a s ( e g . n u m e r i c p r e c i s i o n ) and t o o weak i n o t h e r s ( e g . t h e l a c k o f P A S C A L - l i k e s u b r a n g e s o r e n u m e r a t i o n s ) . EUCLID and P L / I a r e b o t h f a r t o o l a r g e t o be p r a t i c a l l a n g u a g e s . Many f e a t u r e s o f P L / I a r e n o t o r i o u s l y h a r d t o i m p l e m e n t , e s p e c i a l l y e x c e p t i o n a l c o n d i t i o n s . EUCLID i s a new and s t i l l u n i m p l e m e n t e d l a n g u a g e . A m a j o r g o a l o f i t s d e s i g n was t o e n s u r e t h a t EUCLID p r o g r a m s c o u l d h a v e t h e i r c o r r e c t n e s s m e c h a n i c a l l y v e r i f i e d . T h i s h a s r e s u l t e d i n m a k i n g t h e l a n g u a g e r a t h e r c o m p l e x and g u i t e l a r g e . I t a l s o h a s s e v e r a l n o v e l f e a t u r e s t h a t c o u l d be d i f f i c u l t t o i m p l e m e n t . C h i e f among t h e s e a r e t h e a b i l i t y t o p a r a m e t r i z e t y p e d e c l a r a t i o n s and t h e module t y p e (whose p r o p e r t i e s a r e q u i t e d i f f e r e n t f r o m t h e module o f MODULA an d WISCH). SUE i s a l s o a r a t h e r l a r g e and b a r o q u e l a n g u a g e . O n l y C o n c u r r e n t P a s c a l , WISCH Report B- Excuses and r a t i o n a l i z a t i o n s 5 MODULA and PLATON have mechanisms f o r c o n c u r r e n t programming, (The multiprogramming f a c i l i t y of PL/I i s a r c h a i c and u n s u i t a b l e . ) The " s t a t i c " n a t u r e o f c o n c u r r e n t P a s c a l c a u s e s i t t o f a l l s h o r t on p o i n t 4. HODULA, never i n t e n d e d t o be an o p e r a t i n g system language, a l s o f a i l s t o meet p o i n t 4. S i n c e no s u i t a b l e language was f o u n d , the c h o i c e became one o f d e s i g n i n g a new language or a d a p t i n g an e x i s t i n g one. To p r o v i d e t h e n e c e s s a r y freedom i n the d e s i g n i t was d e c i d e d t o c r e a t e a new language from s c r a t c h r a t h e r than attempt t o modify an e x i s t i n g one. WISCH R e p o r t C . O v e r v i e w C . O v e r v i e w 6 T h i s s e c t i o n p r o v i d e s a b r i e f i n t r o d u c t i o n t o t h e s y n t a x a n d s e m a n t i c s o f W I S C H . A t t h e o u t e r m o s t l e v e l , WISCH i s a l a n g u a g e o f p r o g r a m s a n d p r o c e s s e s . A p r o c e s s i s a d y n a m i c o b j e c t . I t i s t h e u n i t o f c o m p u t a t i o n a l a c t i v i t y ; t h a t i s , a p r o c e s s o r e x e c u t i n g some s e t o f i n s t r u c t i o n s a n d a f f e c t i n g some s e t o f d a t a o b j e c t s . E a c h p r o c e s s e x e c u t e s i t s i n s t r u c t i o n s i n a p u r e l y s e q u e n t i a l m a n n e r . H o w e v e r , d i f f e r e n t p r o c e s s e s e x e c u t e i n " p a r a l l e l " s i n c e t h e y a r e e s s e n t i a l l y i n d e p e n d a a t c o m p u t a t i o n s . A l l p r o c e s s e s e x e c u t e a t a n o n - z e r o s p e e d , b u t n o t h i n g may be a s s u m e d a b o u t t h e r e l a t i v e s p e e d s a m o n g p r o c e s s e s e x c e p t t h a t " h i g h p r i o r i t y " p r o c e s s e s a r e f a v o r e d . ( P r o c e s s p r i o r i t y i s d e s c r i b e d l a t e r u n d e r PROGRAM d e c l a r a t i o n s a n d t h e C R E A T E s t a t e m e n t . F a c i l i t i e s a r e p r o v i d e d f o r i n t e r p r o c e s s c o m m u n i c a t i o n a n d s y n c h r o n i z a t i o n . P r o c e s s e s h a v e names a n d may b e r e f e r e d t o b y t h e i r c r e a t o r s . P r o g r a m s p r o v i d e t h e s t a t i c m o d e l o f i n s t r u c t i o n s a n d d a t a o b j e c t s f r o m w h i c h p r o c e s s e s may be c r e a t e d . T e x t u a l l y , p r o g r a m s l o o k a l o t l i k e p r o c e d u r e s . T h e y h a v e a h e a d i n g w i t h f o r m a l p a r a m e t e r s , l o c a l d e c l a r a t i o n s a n d a s e q u e n c e o f s t a t e m e n t s f o r a b o d y . P r o g r a m s may be n e s t e d , b u t u n l i k e p r o c e d u r e s , t h e y h a v e n o k n o w l e d g e o f t h e i r o u t e r e n v i r o n m e n t -WISCH Report c . Overview 7 A MiSCH system consists of an outermost (level zero) program and a l l nested objects. That i s , a WISCH system i s a complete "operating system" written i n WISCH. When a system begins execution an anonymous process i s created (modeled aft e r the l e v e l zero program). As t h i s process executes, i t may create other processes modeled after the programs immediately nested inside the l e v e l zero program. Because of the nested nature of programs, a WISCH system exhibits a tree structure of processes with the o r i g i n a l process as the root. These concepts are i l l u s t r a t e d by the following (much simplified) example: 1 PROGRAM Example; 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 PROGRAM prog_faz(CONST more: BOOLEAN) ; PROGRAM prog_foo; {declarations for prog_foo]; BEGIN prog_foo {body of prog_foo} ; END prog_foo; END prog_faz; PROGRAM prog_bazfaz; {declarations for prog_bazfaz}; BEGIN prog_bazfaz {body cf prog_bazfaz]; END p.rog_fcazfaz; BEGIN prog_faz VAR process_f1, process_f2: PROCESS; START process_f2; F l ; {rest of prog_fazj ; CREATE processor 1 FROM prog_bazfaz; START process_f1; IF more THEN CREATE process_f2 FROM prog_bazfaz; WISCH Report C. Overview 8 29 VAR process_a, process_b, process_c : PROCESS; 30 31 BEGIN Example 32 CREATE process_a FROM prog_faz (true) ; 33 START process_a; 34 CREATE process_b FROM prog_faz (false) ; 35 START process_b; 36 CREATE process_c FROM prog_foo; 37 START process_c; 38 {rest of the body of example] ; 39 END Example . The nodes of the process tree are drawn; i 1 J process | | program | i i In t h i s diagram, "process" i s the name of the process variable and "program" i s the name of t i e program that i t i s modelled a f t e r . Immediately before Example executes l i n e 30, the tree i s : | (anonymous)| | Example | WISCH Report C. Overview 9 assuming that Example f i n i s h e s l i n e 33 just as process_a f i n i s h e s l i n e 19, but before process_b actually s t a r t s , the tree structure i s ; ] (anonymous) | \ Example ] L 1 J -J i i T i i i | process_a J I prog_faz J i T 1 process_b | I prog_faz J |process_f1 | J prog_bazfaz| J T J process_f2 | 1prog_bazfaz| F i n a l l y , at some l a t e r time the tree i s ; J (anonymous) | 1 Example | I J T J process_a J 1 prog_faz | 1 i T i ~i |process_f1 | J prog_bazf az J i t S I T |process_f2 | 1prog_bazfazj i "i ] process_b j \ prog_faz I I I 1 T jprocess_f1 J J prog_bazfazj L J I T 1 T j process_c | \ prog_foo | although there are two processes with names process_f1 and patterned after prog_bazfaz, they are d i f f e r e n t processes having WISCH Report C. Overview 10 different parents. Since a program cannot declare two variables with the same name and can refer only to i t s immediate o f f s p r i n g processes by name, there i s no confusion about which process i s being refered to at any point. In other words, every process has a unigue path name from the root process to i t s e l f . For example, the leftmost process on the bottom layer of the above diagram has a path name of (anonymous).process_a.process_faz1 and the righmost process on the bottom layer has a path name of (anonymous).process_b.process_faz1. Communication and synchronization among processes uses a message passing f a c i l i t y modeled afte r that of PLATON. Programs may declare pools of shared objects, request objects from pools, and send objects to pools. Pools are actually linked l i s t s of variables, a l l of the same type. I f two di f f e r e n t processes are passed the same pool as a parameter, they may communicate via i t . (Note that the parameters s y n t a c t i c a l l y belong to programs). When a process requests access to an object from a pool, i t i s given the f i r s t one i f the pool i s non-empty. I f the pool i s empty, the process i s stopped and added to the end of a l i s t of processes waiting for objects from that pool. When a process sends an object to a. pool, i f there are no processes waiting on that pool, the object sent i s added to the end of the l i s t . If there are processes waiting for objects from that pool, the f i r s t one i s given the new object and allowed to continue. I t i s guaranteed that a shared object can be accessed from only one process at a time. Shared objects may be passed WISCa Seport C. Overview 11 by r e f e r e n c e (processes are given p o i n t e r s to them), a l l o w i n g l a r g e b l o c k s of data t c be shared with l i t t l e overhead. For example, c o n s i d e r a very simple, d e d i c a t e d " b a t c h " system t h a t reads i n p u t from one d e v i c e , processes i t , and w r i t e s output on another d e v i c e . To achieve concurrency of I/O and p r o c e s s i n g the system i s composed o f three processes, an i n p u t process, a compute process and an output process. The computation process communicates with the i n p u t and output processes v i a pools o f shared b u f f e r s . S c h e m a t i c a l l y , the system i s ; 1 I I I , > | p o o l o f J 1 i — > J p o o l o f I - j J J f u l l i n p u t | I | J f u l l o u t p u t j | I J I i l l I I I  L J 1 | —-i i — a i ; 1 1 input | | compute | J output j \ I process | J process 1 1 process 1 i . i i i i 1 1 1 A 1 1 I I i j r 1 i J r , J 1 1 i < • «• 1 l < « | pool of 1 i pool of J Jempty i n p u t | lempty output! J 1 I I i j i i Note t h a t we r e a l l y have two c l a s s i c a l producer/consumer r e l a t i o n s h i p s here. The i n p u t process produces f o r the compute process t o consume, and the compute process produces f o r the output process to consume. WISCH Report C. Overview 12 A s k e l e t a l version of the code f o r t h i s system follows, (For now, simply note that a PERVASIVE name i s known everywhere and that the notation "ffi POOLED type" denotes a pointer to a shared object of the spec i f i e d type.) I PROGRAM batch; 2 3 PERVASIVE CONST 4 in_len = (an appropriate value} ; 5 out_len = {an appropriate value}; 6 no_in_bufs = {an appropriate value}; 7 no_out_bufs = (an appropriate value.] ; 8 9 PERVASIVE TYPE 10 in_buf = STBING (in_len); I I out_buf = STRING (out_len); 12 13 VAR 14 empty_in, f u l l _ i n : POOL OF i n _ i u f ; 15 empty_out, f u l l _ o u t : POOL OF out_buf; 16 input, compute, output : PROCESS; 17 18 PROGRAM input_prog (VAR empty, f u l l : POOL OF in_buf) ; 19 VAR buffer : a POOLED in_buf; 20 BEGIN input_prog 21 FOR i ;= 1 TO no_in_bufs LOOP {allocate buffers} 22 NEW (buffer); 23 SEND buffer TO empty 24 NEXT; 25 LOOP {read input foreverj 26 AWAIT buffer PRCM empty; 27 { f i l l the buffer}; 28 SEND buffer TO f u l l RESPOND empty; 29 NEXT; 30 END input_prog; 31 32 PROG BAM compute_prog 33 (VAR f u l l _ i n : POOL OF in_buf; 34 VAR empty_out, f u l l _ o u t : POOL OF out_buf); 35 VAR 36 inbuf : 3 POOLED in_buf; 37 outbuf : S POOLED out_buf; 38 BEGIN compute_prog 39 FOR i := 1 TO no_out_bufs LOOP {allocate buffers} 40 NEW (outbuf); 41 SEND outbuf TO einpty_out 42 NEXT; 4 3 LOOP {process input foreverj 44 AWAIT inbuf FROM f u l l _ i n ; WISCH Report C Overview 13 45 AWAIT outbuf FROM empty_out; 46 {produce the output from the input}; 47 SEND inbuf TO SENDER; 48 SEND outbuf TO f u l l _ o u t SESPOND empty_out; 4.9 NEXT; 50 END compute_prog; 51 52 PROGRAM output_prog (VAR f u l l : POOL OF out_buf) ; 53 VAS buffer : a POOLED out_buf; 54 BEGIN output_prog 55 LOOP {write the output foreverj 56 AWAIT buffer FROM f u l l ; 57 {output the buffer] 58 SEND buffer TO SENDER; 59 NEXT; 60 END output_prog; 61 62 BEGIN batch 63 CREATE input FROM input_prog(empty_in,full_in); 64 START input; 65 CREATE compute 66 F BOM compute_prog (f u l l _ i n , empty_out, full_out) ; 67 STABT compute; 68 CREATE output FBOM output_prog(full^out); 69 STABT output; 70 END batch. C.2. Statements WISCH provides a pleasing, e c l e c t i c blend of the better control structures from such languages as PASCAL, ALGOL-68, EOCLID and PLATON, along with some recently published proposals. The structures provided f a c i l i t a t e the cle a r and easy expression of a wide variety of algorithmic concepts. A l l "compound" statements (IF, FOB, etc.) have a f u l l y delimited syntax with short, mnemonic keywords delimiting a l l major syntactic units. This "closed" syntax allows an a r b i t r a r y sequence of statements to be used any place that a singl e WISCH Beport C. Overview 14 statement can with no extraneous BEGIN—END pairs, The philosophy of WISCH i s to be easy to read and reasonable to write. Verbosity and redundancy are used to improve r e a d a b i l i t y and prevent simple errors from going undetected, while avoiding the COBOL-esque extreme of hindering the programmer, C. 3. Data types, l i t e r a l denotations and expressions In the t r a d i t i o n of PASCAL, the primitive data types, type declaration f a c i l i t i e s and operators of WISCH provide the programmer with a powerful tool for the manipulation of problem oriented data. Elements are extracted from PASCAL, PLATON, MODULA, BCPL and PL/1. Included are almost a l l of the type concepts from PASCAL, and the shared variable and process structuring type concepts from PLATON. The primitive types include boolean, character, integer, r e a l , storage ( b i t s t r i n g ) , character s t r i n g and process. Among the type declaration concepts are enumerations, subranges, sets, pointers, arrays, records and pools (of shared v a r i a b l e s ) . The l i t e r a l denotations for the standard primitive types are quite f a m i l i a r . Of note i s the a b i l i t y to write structured l i t e r a l s of set, array and record types. Note that a l i t e r a l i s a denotation f o r a data value that represents i t s e l f , such as the integer value 100 or the s t r i n g value "abc". Thus, the values of a l l l i t e r a l s (and l i t e r a l expressions) are known at compile time. A l i t e r a l expression i s one involving only WISCH Report C. Overview 1 5 l i t e r a l s , declared constants known at compile time, data att r i b u t e s known at compile time and standard function references with l i t e r a l expressions as arguments. The word constant i s used in WISCH to denote a name f o r a value which cannot be altered by a program (as opposed to a vari a b l e ) . The value of a constant i s often a l i t e r a l value, but doesn't have to be. For example, a procedure might define a constant whose value i s computed using a parameter of the procedure. The value of t h i s constant i s computed at every procedure entry, but once i n i t i a l i z e d , the constant cannot be altered. Apart from the widely used r e l a t i o n a l , arithmetic and boolean operators, WISCH provides operations on b i t s t r i n g s , sets and character st r i n g s . A l l expressions are "s e l f - t y p i n g " , that i s no context external to an expression i s needed to determine the r e s u l t type. There are are almost no automatic type conversions associated with operators. Programmed conversions are ava i l a b l e though, along with the values of some at t r i b u t e s for most data types. L i t e r a l expressions are guaranteed to be evaluated at compile time, with possible (but not guaranteed) e f f e c t s on the compiled code. For example, the source l i n e ; IF b THEN s i ELSE s 2 F l might get compiled as simply: s 1 i f b i s a l i t e r a l expression with the value TBOE. WISCH S e p o r t C. Overview 16 C.4. Modules WISCH has a m o d u l a r i z a t i o n f a c i l i t y s i m i l i a r t o t h a t o f MODOLA. T h i s a l l o w s the programmer to b u i l d semipermeable w a l l s around s e c t i o n s o f d e c l a r a t i o n s , e x p l i c i t l y c o n t r o l l i n g what p o r t i o n s o f t h e o u t s i d e w o r l d a r e known w i t h i n t h e module and what o b j e c t s d e c l a r e d i n s i d e the module a r e known o u t s i d e o f i t . The module p r o v i d e s a means o f h i d i n g i m p l e m e n t a t i o n d e t a i l s from p o r t i o n s o f the code which have no need o r b u s i n e s s knowing them. WISCH Report D. Primitive elements 17 D. Primitive elements This section describes WISCH at the lowest l e x i c a l l e v e l , that of the strings of characters composing a l l programs- WISCH i s a free format language, allowing source text to be written anywhere on a source l i n e and allowing blanks and/or comments to occur between any syntactic objects- However, as opposed to some languages, physical source l i n e s are sometimes s i g n i f i c a n t -Comments and st r i n g l i t e r a l s are not allowed to. cross l i n e boundaries. The i d e n t i f i e r s a f t e r the BEGIN and END of program, procedure and function bodies must be on the same l i n e s as the BEGIN and END. In the t r a d i t i o n of other ALGOL-like languages, semicolons are used to separate major syntactic constructs. WISCH allows an optional terminating semicolon for those who prefer the PL/1-like rule that constructs are terminated with semicolons (the examples given throughout t h i s report are written i n t h i s manner). I t i s desirable, but not required, that an implementation allow a programmer to omit semicolons where possible. D.1. Alphabet, i d e n t i f i e r s and comments Letters = A B C D E F G H I J K L H N O P Q f i S T U V W X Y Z a b c d e f g h i j k l a n o p g r s t u v w x y z Di g i t s = 0 1 2 3 4 5 6 7 8 9 Others = - # ; : * " _ ( ) { 3 < > = « • - * / - . & I % a » $ # WISCH Eeport D. Primitive elements 18 The set of l e t t e r s i n WISCH consists of the 72 English upper and lower case l e t t e r s . No d i s t i n c t i o n i s made between the cases anywhere in tbe language except f o r character and st r i n g l i t e r a l s . For example: and. And, AND are three ways to s p e l l the same sord. The programmer can pretend that a l l l e t t e r s {except those in character or s t r i n g l i t e r a l s ) are converted to upper case (or lower case) by a preprocessor and not go wrong. The set of d i g i t s i s composed of the ten decimal d i g i t s . I d e n t i f i e r s are written as strings of l e t t e r s , d i g i t s and underscores (_). The f i r s t character must be a l e t t e r and the l a s t must not be an underscore. I d e n t i f i e r s may be of ar b i t r a r y length, but an implementation may place a l i m i t on the number of s i g n i f i c a n t characters i n an i d e n t i f i e r . This l i m i t must not be less than f i f t e e n however. The set of "other" characters l i s t e d above includes a l l other characters used as part of the language. They are a l l found i n the 128 character ASCII set. Of course, characters not used i n the language but i n the implementation set may be used in character and s t r i n g l i t e r a l s . Suggested t r a n s l i t e r a t i o n s for some sp e c i a l symbols are given below in the section on speci a l symbols. Comments i n WISCH extend from a l e f t brace ({) to a rig h t brace {j) or end of the source l i n e (which ever comes f i r s t ) . A single comment may not cross a li n e boundary. For example: WISCH Report D. Primitive elements 19 IF a < b THEN a := b; {Select the larger of a and b-or^ VAB ( i , j ) : = 0 {# usedj, k:=-1 [next free) : INTEGEB; With t h i s convention i t i s impossible to write "reversed" programs and i t i s much easier to avoid inadvertant i n c l u s i o n of code i n comments. Comments may be used anywhere i n the source program that a " t r i v i a l " blank may. Comments i n WISCH may also be nested, so that the following i s a l i n e that i s completely commented out by the f i r s t l e f t brace and the end of lines { dump_status (current_state); {for debugging only) D.2. Beserved words The following table l i s t s the reserved words of WISCH; ABS ELSE FOSK NEXT SENDEE ASSAY END FORWARD OF SET ASSEBT ENDBLOCK FROM OPTION STACK AW AIT ENDFINAL FUNCTION OTHER STABT. BEGIN EN DINITIAL HEAP PEBVASIVE STOP BIND ENDMODULE I F POOL STRING BLOCK ENDS ECO BD IMPOST POOLED THEN BY EE BOB IN PBIOBITY TIME CASE EXIT IN IT IALLY PBOCEDUBE TYPE CONST EXPORT ITEBATE PROGBAM UNBIND CREATE EXTEBNAL «IOIN BECOBD UNLESS DESTROY F l LOOP BEU VAR DIV FIN MOD BESPOND WHEN DOING FINALLY MODULE BETUBN XOB EL IF FOB MYSELF SEND These words may not be used as user defined i d e n t i f i e r s . Again, although they are written in upper case throughout t h i s report, they may l e g a l l y be written using any combination of upper and lower case. WISCH Report D. Primitive elements 2 0 D.3. Special symbols The s p e c i a l symbols used i n WISCH can be divided f o r convenience i n syntactic separators and operators. Some of the reserved words are actually operators, so they are l i s t e d again here. The syntactic separators are: '• * • 1 $ 1 ( ) { } £ 1 := : = : + : = : += -: = *: = : *= /: = s/= %t = s«= S: = :£= |: = :| = ; **= &£: = :&&= 1 |s = : J 1= IN: = -.IN : -DIV: = : Div= SEM:= : BEH= MOD: = ;MOD= XOR: = : XOR= <: = :<= -.<: = : -.<= <=: = :<== -<=: = : -<== >: = ;>= ->: = : ->= * .m-m — — >=: = :>== ->=: = : perators are: 1 •* ^  + - * / DIV REM MOD ABS ** * -» & 1 6S i i XOR < -< <= -.<= >= ->= > -> IN -IN Suggested t r a n s l i t e r a t i o n s for non-ASCII character sets includ'e: {* and *) for { and j <. and .) for £ and J WISCH Report D. Primitive elements 21 D_ 4 _ Stan dard i d e n t i f i e r s The following table l i s t s the standard i d e n t i f i e r s of WISCH-ADDR FALSE MAX SHIFT ATAN 'FIND_CHA.fi MAX_POS_SEAL SIGN BOOLEAN FIRST MIN SIN CARD FIRST_ELEM MIN POS SEAL SQRT CEIL FLOOR NEW STORAGE CHAR INCB NIL SUCC COS INTEGER PAD_STRING TAN DECR LAST PR ED TRUE DISPOSE LAST_ELEH PROCESS TRUNC EM PT Y LENGTH REAL UP_BND EXP LO_BND SOTATE VALUE SIZE LOG ROUND WAITING LOG 10 These i d e n t i f i e r s are treated as though they are declared in a scope surrounding the WISCH program, procedure or function being compiled. The standard d e f i n i t i o n s for each are given where they are introduced i n the body of the report. Most of them are treated exactly as though they are ordinary, programmer defined names and may be redefined i f desired. However, the standard type names (BOOLEAN, CHAS, INTEGER, PROCESS, REAL, and STORAGE), the boolean values (TRUE and FALSE) and the n i l pointer value (NIL) are pervasive names and may not be redefined- Thus, to the programmer these names look l i k e reserved words. WISCH Report D. Primitive elements 22 D.5 . A note on the syntax graphs Many sections of t h i s report include syntax charts relevant to their topic. The "r u l e s " of these charts are as follows: 1 . Words written i n a l l CAPITAL l e t t e r s represent reserved words. They are in a l l c a p i t a l s for i d e n t i f i c a t i o n only. WISCH allows them to be written as any combination of upper and lower case. Standard names are written i n upper case also. 2. Items written i n lower case and enclosed in angle brackets (<,>) are syntactic objects described with charts of the i r own. 3 . Seguences of sp e c i a l characters are l i t e r a l s representing themselves. 4. A l l charts have a single entry at the l e f t and a single e x i t at the ri g h t . 5 . Flow i n the charts i s ba s i c a l l y counter-clockwise, that i s , from l e f t to r i g h t ; or down, from l e f t to r i g h t and back up; or up, from right to l e f t and back down. Arrows on the charts help emphasize t h i s . As an example consider the chart for program, procedure and function formal parameters: prog/proc/func foraal parans : COSST —y - V\B -<iaent> — I — s < t y p e > -jc WISCH Report D, Primitive elements 23 The parameters consist of a l e f t parenthesis { () , followed by one or more declarations separated by semicolons, followed by a right parenthesis {)). A declaration consists of the word CONST or the word VAE or neither, followed by one or more i d e n t i f i e r s separated by commas, followed by a colon and a type., I d e n t i f i e r and type are defined by other charts. WISCH Report E„ Compilation unit 24 E. Compilation unit coapilatioa unit : E <program declaration> 5-<procedare declarat.ion> —T <functiou declaration> • The the unit of compilation i n WISCH i s a single program, procedure or function. A compilation defines a completely closed scope, so a separately compiled piece of code knows nothing about the environment i t i s eventually used i n . That i s to say, while an inner procedure of a program has access to a l l objects declared i n outer scopes, a separately compiled procedure declared at the same l e v e l has no access to any of those outer objects, a separately compiled program, procedure or function i s declared by specifying that i t s body i s EXTERNAL. (See the sections below on PROGRAM, PROCEDURE and FUNCTION declarations.) WISCH Report Declarations 25 F. Declarations declarations : <constant declaration> -<type declaration> — — <variable declaration> -<prograni declaration> — <nrocedure declaration> <£unction declaration> -<nodule declaratioa> WISCH has s i x forms of declarations: constant, type, variable, program, procedure and function. They may be mixed i n any order, provided that a l l i d e n t i f i e r s are declared before they are used. (A small exception i s made for the object type of pointers.) I t i s also i l l e g a l to redefine a name i n a scope once i t has been used i n that scope. (This i s explained more f u l l y below in the section on scope of names.) F.1. Constants constant d e c l a r a t i o n : P E R V A S I V E COHST <ident> = — - <expressioa> The CONST declaration allows i d e n t i f i e r s to be eguated with unalterable values. The expression may or may not be a l i t e r a l expression, i t s type i s the type that w i l l be associated with the i d e n t i f i e r . I f the expression cannot be evaluated at compile time, the CONST declaration e s s e n t i a l l y declares a HISCH Report F. Declarations 26 variable which i s i n i t i a l i z e d at scope entry and cannot otherwise be assigned to- The PERVASIVE attribute i s discussed in the section on the scope of names. Some examples of constant declarations are: TYPE chars = SET OF CHAR; vec = ARRAY (1.-5) OF INTEGER; CONST size = 100; ibm = "IBM"; hp = "HP"; target = hp; di g i t _ s e t = chars (» 0. . * 9) ; 1o«er_case_set = chars('a..*z); alpha_set = lower_case_set * d i g i t s ; codes = vec(0,2,4,6,8) ; F.2. Types typo d e c l a r a t i o n : P E H V R S I V E — T Y P E <ident> <type> type <type nane> — — — — <scalar typs> 1 <sot type> <string typ<3> — — <array typs> <rocord type> — — — — <norna.l pointer type> <pool type> »— <pool pointer type> WISCH Beport F . Declarations 27 type name : <iaent> —1  <standard type naae> standard type naae : standard scalar <standard scalar> real boolean —— char • integer process ——- storage This section describes data types i n d e t a i l . The syntax and semantics presented here also apply to types used i n variable, parameter and function declarations. WISCH i s a strongly typed language, that i s types must be known at compile time for a l l objects and checking of a l l operands i s enforced. A large variety of types are provided, including six standard types and ten constructors. KISCH Beport F. Declarations 28 A clear understanding of the data type nomenclature used throughout t h i s report i s es s e n t i a l to understand the following sections, so the following table i s presented; type class standard scalar assignable shareable structured process X r e a l x X X boolean X X X X character X X X X integer X X X X storage X X X X enumerated X X X subrange X X X s t r i n g X X set X X array <1> <2> record <1> <2> normal pointer X pool pointer pool module <1> - Arrays and records are assignable i f f a l l <2> - " 11 tt II shareable II n X X X The standard types are the f i v e b u i l t - i n types. Scalar types are those with values that can be mapped 1 to 1 with some f i n i t e subset of the integers. Assignable types are those f o r which variables of that type may be assigned to. Shareable types are those f o r which objects of that type may be shared among di f f e r e n t processes (pooled objects). Structured types are those for which "structured" values may be written. WISCH Report F. Declarations 29 J_.2-.l- Assignable types The assignable types are those that may be involved i n an assignment statement, that i s a variable of that type may be assigned to. F.2, 1. 1. Scalar types The scalar types are the simplest data types. The values of any scalar type are f i n i t e (in number and magnitude) and are t o t a l l y ordered. There exists a {machine-dependant) one-to-one mapping between the values of any scalar type and a subset of the integer values represented on the machine. A l l scalar types share the r e l a t i o n a l operators <, -*<, < = , -«<=, =, -•=, >=, -»>=, ># which have the obvious meanings (less than, not less than, l e s s than or equal to, e t c . ) . The r e l a t i o n a l operators have p r i o r i t y 0, lower than a l l other operators. There are six standard functions defined for a l l scalar types. The functions FIRST and LAST accept the name of a scalar type or variable, and return the lowest and highest values of the type respectively. The functions SUCC and PEED accept a scalar expression and return the next larger and next smaller values respectively. An attempt to take the SUCC of the largest value or the PRED of the smallest value i s an error. The functions MIN and MAX accept two scalar expressions as arguments and return the value of the smaller and larger respectively. WISCH Seport Two standard procedures, INCH and and decrement scalar variables checked for range errors. F. Declarations 30 DECR are provided to increment (by "one"). They are also In addition, the name of any scalar type may be used as a generic transfer function to convert a value from any scalar type to the named one, with appropriate range checking. The conversion i s defined by the implementation defined mapping between any scalar type and the integers. For example, on a machine using the 128 character ASCII set, CHAR (7) i s the b e l l character, INTEGER('a) i s 97 and CHAR (300) i s i l l e g a l . F.2. 1. 1.1. Boolean The type boolean i s denoted by the standard type name BOOLEAN. The values of boolean are the words TRUE and FALSE, with FALSE < TRUE. There are three operators which accept boolean arguments and return a boolean value: operator ££i°.£i±! operation S 2 l o g i c a l conjunction (and) J 1 l o g i c a l disjunction (or) -. 1 unary l o g i c a l negation (not) The operators S and I are evaluated i n a l e f t - t o - r i g h t "McCarthy" manner, that i s a st r i n g of and»ed terms i s not evaluated past the leftmost term that i s FALSE, and a s t r i n g of or'ed terms i s not evaluated past the leftmost term that i s TRUE. Because of t h i s McCarthy evaluation, boolean operators WISCH Report cannot be said to associate. F. Declarations 3 1 F . 2 . 1 . 1 . 2 . Character The type character i s denoted by the standard type name CHAR. The values of type character are an implementation defined character set. An implementation may (should) also define other s p e c i f i c character types, such as ASCII_64, ASCII_128 or EBCDIC. There are no operators on character values except the r e l a t i o n a l ones. Character l i t e r a l s are written as a single character preceded by an apostrophe (*), for example »A. An apostrophe i s written as two consecutive apostrophes, that i s **. Non-printable characters may not be denoted d i r e c t l y , but may be denoted using the CHAR transfer function mentioned above with a l i t e r a l argument. There are no direct denotations for alternate character types, but they may be written using the b u i l t - i n transfer functions mentioned above. For example, ASC1I_64(*A) would return the &SCII_64 representation representation of the character * A. F . 2 . 1 . 1 . 3 . Integer inteaer l i t e r a l (no embedded blanks) WISCH Report F. Declarations 32 The type integer i s denoted by the standard type name INTEGER. the values of type integer are an implementation defined subset of the integers. Negative integer values are represented i n t e r n a l l y i n an implementation defined manner. L i t e r a l s are written as a seguence of d i g i t s , optionally followed by an octothorpe (#) and an unsigned decimal integer specifing the number base. There can be no characters between the l a s t d i g i t of the number and the octothorpe or between the octothorpe and the f i r s t d i g i t of the radix. If the base s p e c i f i e r i s ommited, the number i s assumed to be decimal. The allowable radix values must include at lea s t 2, 8, 10 and 16. The d i g i t s of the number must be legal for the base used, for example, 459#8 i s i l l e g a l . There are no predefined constants for the minimum and maximum integer values since they may be obtained via FIRST (INTEGER) and LAST (INTEGER) . There are ten operators which accept integer operands and return an integer r e s u l t : operator p r i o r i t y operation ** 3 integer exponentiation * 2 mul t i p l i c a t i o n DIV 2 d i v i s i o n (truncate towards zero) REM 2 d i v i s i o n remainder i REM j = i - (i/j ) * j the sign of (i REM j) i s always the same as the sign of i MOD 2 mathematical modulus the sign i s always positive f o r i>=0, i MOD j = i REM j else, i MOD j = ( i REM j) + (ABS j) +,- 1 addition and subtraction •,- 1 unary plus and unary minus ABS 1 unary absolute value Integer exponentiation i s defined in the obvious manner. That WISCH Report F. Declarations 33 i s , a**b i s defined as a*a* ... *a ( i . e . , b occurances of a) i f b i s po s i t i v e , 1 i f b i s zero, and 1 DIV (a**-b) i f b i s negative. Association of a l l integer operators except ** i s function, SIGN, i s provided to extract the numeric sign of an integer expression. I t accepts a single argument and returns -1 i f i t i s negative, 0 i f i t i s zero and +1 i f i t i s positive. LL2-.i-i-.ii Storage storage l i t e r a l : (DO embedded blanks) — $ —-1— + —x— <integer l i t era l> • • 1. > The type storage i s denoted by the standard type name STORAGE. The values of type storage are b i t patterns. L i t e r a l s are written as signed integer l i t e r a l s preceeded by a d o l l a r sign ($), for example $64 and $100#8 both represent the b i t pattern 1000000 (ignoring leading zeros). The range of integers allowed and the i r corresponding bit patterns i s implementation defined. There are four operators which accept storage arguments and return a storage r e s u l t : operator p r i o r i t y operation l e f t-to-r ight, associates r i g h t - t o - l e f t. A standard 5& i I X O R 2 1 1 bitwise and bitwise i n c l u s i v e or bitwise exclusive or unary bitwise complement HISCH Seport F. Declarations 34 Note that although these operators look s i m i l i a r to the boolean operators &, | and ->, they are indeed very d i f f e r e n t . In pa r t i c u l a r , the storage operators do not work i n a "McCarthy" manner. Association of a l l storage operators i s l e f t - t o - r i g h t . The meaning of r e l a t i o n a l comparisons between storage values i s implementation defined. In addition, there are two functions which accept a storage f i r s t argument and an integer second argument. They are the s h i f t i n g functions, SHIFT and SOTATE. SHIFT i s an end-off, z e r o - f i l l s h i f t and SOTATE i s a c i r c u l a r r otation. The integer argument i s the number of b i t s to s h i f t , a positive value indicates a l e f t s h i f t and a negative value indicates a ri g h t s h i f t . (Easy to remember i f l e f t s h i f t s are thought of as being e s s e n t i a l l y multiplications by a power of two.) F.2.1.1.5. Enumeration enumeration : [ <iflent> —'— ] . •> Enumeration types are declared by giving a l i s t (enumeration) of unique i d e n t i f i e r s which are the values of the type. The values are ordered l e f t to ri g h t , from lowest to highest. The value i d e n t i f i e r s may not be redefined i n any WISCH Report F„ Declarations 35 inner scope that has access to the type. There are no operators for values of enumeration types except the r e l a t i o n a l ones. Some examples of enumeration types are: TYPE color = [ black,red,green,blue,white "j; disk_op = [read,write,seek,resetJ; The type color has fi v e values, l i t e r a l s of type color are denoted by the i d e n t i f i e r s black, red, green, blue and white. The lowest value i s black, the highest i s white. F.2.1.1.6. Subrange subrange : <expression> .. <expression> > Subrange types are based on other scalar types. They are declared by providing l i t e r a l expressions of the basis type for the i n i t i a l and f i n a l values of the subrange. The lower bound must not be larger than the upper bound. The values of a subrange are the values of the basis type between the values of the i n i t i a l and f i n a l expressions, i n c l u s i v e . L i t e r a l denotations and operators are the same as for the basis type. Some examples of subrange types are; TYPE hue = red..blue; c a p i t a l _ l e t t e r = »A..*Z; {dangerous with EBCDICI} table_index = 0..size-1; WISCH Report F. Declarations 36 Subrange types may also be defined for which the exact l i m i t s are not known at compile time. I f eith e r (or both) of the subrange bound expressions are not l i t e r a l expressions, the subrange defined i s a "dynamic" subrange. In t h i s case, the l i m i t s of the range are not f i x e d u n t i l scope entry at run time. The range expressions are evaluated exactly once for each e x p l i c i t usage of a dynamic subrange. For example, given the code segment; TYPE range = 1 .. no_entries+1; VAR old, new: ARBAY(range, range) OF CHAB; i 1 , i 2 , i 3 : 0 .. no_entries+1; J1# j 2 , j3: 0 ., no_entries*1; the expression "no_entries+1" i s evaluated three times, once i n the declaration of the type "range", once i n the declaration of the " i " variables and once f o r the " j " v ariables. I t i s not reevaluated when "range" i s used i n the array type s p e c i f i c a t i o n . The dynamic bounds are reevaluated though whenever a variable i s created with the NEW procedure (see pointer types for a description of NEW). For example, given the code: VAE (lwb, upb):=0 : INTEGER; TYPE index = lwb-1. . upb+1; dyn_array = S ARRAY (index) OF INTEGER; VAR table"!, table2: dyn_array; BEGIN lwb := 0; upb := 19; NEW(tablel) ; HISCH Report F» Declarations 37 lwb .:= 1; upb := 100; NEW(table2); the variable table 1 w i l l point to an array with 22 elements indexed from -1 to 20 and table2 w i l l point to an array with 102 elements indexed from 0 to 101- The expressions "Iwb-I" and 11 upb+1" are evaluated twice, once each for the creation of the arrays. Dynamic subranges thus allow the creation and manipulation of data structures whose size i s not known t i l run time. They also allow procedures to accept variably sized arrays as parameters, for example: FUNCTION mean {lwb, upb: INTEGER; values; ARB AY (lwb-.upb) OF SEAL) : REAL; F.2. 1.2. Seal r e a l l i t e r a l : (no embedded blanks) -^ <digit> —I— . <digit> —^  J Z <digit> The type r e a l i s denoted by the standard type name BEAL. The values of type r e a l are an implementation defined subset of the r a t i o n a l numbers. L i t e r a l s are written as a sequence of decimal d i g i t s , a point (.), another sequence of decimal d i g i t s and an optional exponent. Note that there must be at least one d i g i t on each side of the point and that no embedded blanks are allowed. The exponent i s written as the l e t t e r e (or E) WISCH Beport Declarations 38 followed by an optional sign and a decimal integer l i t e r a l , again with no embedded blanks- The range and precision of r e a l values i s implementation defined. There are eight operators which accept r e a l arguments and return a r e a l r e s u l t : operator p r i o r i t y operation association of a l l r e a l operators except ** i s l e f t - t o - r i g h t , ** associates r i g h t - t o - l e f t . If the operators f o r exponentiation, m u l t i p l i c a t i o n , addition or subtraction have one re a l argument and one integer argument, they w i l l y i e l s a r e a l value. The operator for r e a l d i v i s i o n always y i e l d s a real value, either or both arguments w i l l be converted i f necessary. The r e l a t i o n a l operators defined above for scalar values are of course also defined for r e a l values. Exponentiation i s guaranteed to be implemented as repeated multiplications for some implementation defined range of integer exponents. The actual algorithm used i s implementation defined, i t i s only guaranteed that logarithms and exponentials w i l l not be used. For example: x ** 9 might be implemented as: x * x * x * x * x * x * x * x * x or as: ABS * 3 2 2 1 1 1 exponentiation mult i p l i c a t i o n d i v i s i o n addition and subtraction unary plus and unary minus unary absolute value X * { (X2) 2 ) 2 WISCH Report F. Declarations 3 9 that i s , with 4 multiplications instead of 8 - Note that exponentiation hy a r e a l value i s indeed allowed. The point made above i s that exponentiation by certain integer values may be fas t e r and more accurate than exponentiation by equivalent r e a l values. There are several standard functions for conversion between integers and reals and for mathematical computation. The type name REAL may be used as a function to convert integer values to rea l values (but i s actually superfluous since t h i s w i l l be done automatically). There are four functions to convert re a l values to integers, TRUNC, ROUND, FLOOR and CEIL. TSUNC gives a truncation towards zero. ROUND gives a rounding away from zero. FLOOR gives the largest integer that i s les s than or egual to the real value. CEIL gives the smallest integer that i s greater than or egual to the r e a l value. The mathematical functions are SQRT, EXP, LOG (natural), L O G 1 0 (common), SIM, COS, TAN and ATAN. The standard functions WIN and MAX defined above for scalar values also accept real arguments, as does the function SIGN defined above for integer values. ,• A l l three return re a l values when given r e a l agruments. There are two standard constants of type REAL, MAX_EOS_REAL and aiN_POS_aEAL. HAX_POS_REAL i s the largest r e a l value that may be represented and MIN_POS_REAL i s the smallest positive (non-zero) value that may be represented. WISCH Report F. Declarations UO F. 2. 1.3- Power set set type : S E T OF <scalar type> > Powerset types (hereafter simply c a l l e d set types) are defined based on some scal a r type (other than a dynamic subrange). The values of a set type are elements of the powerset of t i e scalar basis type. For example the type "SET OF hue" has eight values (with hue as defined above i n the subrange type examples). They are the sets (red), (green), (blue), (red,green), (red,blue) , (green,blue) , (red,green,blue) and () (the empty s e t ) . Values of a set type are written as the type name followed by a parenthesized l i s t of expressions in the basis type (the elements) . If a l l elements are l i t e r a l expressions, then the denotation i s a set l i t e r a l . For example, given the declaration: TYPE hues = SET OF hue; one could write: hues(red, green) WISCH Report F- Declarations A "subrange1' notation may also be used i n set values- An element of the form a-.b denotes a l l values from a to b in c l u s i v e , where a and b are arb i t r a r y expressions of the basis type. For example: chars (•+,•<).. '5, •-) i s equivalent to; chars {» + , * 0, M , «2, *3, *4,»5, '-) If the lower bound i s larger than the upper bound, the " n u l l range" i s used- For example: ints{0, 1,7..3,10) i s equivalent to: ints(0,1,10) A p a r t i c u l a r implementation may place r e s t r i c t i o n s on the allowable c a r d i n a l i t y of the basis type and on the allowable "magnitude" of the basis values, but must at least allow for the declaration of a SET OF CHAR. There are four operators which accept set arguments and return a set value: operator p r i o r i t y operation • 3 2 1 set intersection set union set difference i n terms of bitwise l o g i c , 1 a - b = a XOE (a && b) unary set complement WISCH .fieport F. Declarations 42 association of a l l set operators i s l e f t - t o - r i g h t . The r e l a t i o n a l operators defined above for scalar values may also be used with set values. They test the subset r e l a t i o n , f o r example, set_a < set_b i s TRUE i f the value of set_a i s a proper subset of the value of set_b. There are also two operators which accept a scalar l e f t argument, a set r i g h t argument and return a boolean value. They are the set element operators, IN and -IN. IN returns TRUE i f the l e f t argument i s an element of the r i g h t , F a_S£ otherwise, -IN does just the opposite. Note that i f the value of the l e f t operand i s not within the set basis type IN returns FALSE (-.IN returns TRUE) , agreeing with normal i n t u i t i o n . Like the other r e l a t i o n a l operators, these have a p r i o r i t y of 0. For example, given the following code segment: TYPE chars = SET OF char; nums = SET OF 0,.10; vaR char_digits : chars; num_digits : nums; BEGIN char_digits := chars(*0.. '9) ; num_digits := nums(1,3,5,7,9); the following expressions are TRUE: •3 IN char_digits 10 -IN num_digits and the following are FALSE: •a IN char_digits 4 IN num_digits 500 IN num-digits There are three standard functions dealing with sets. The WISCH Report F- Declarations 43 functions FIRST_ELEM and LAST_EL£m" accept a set as an argument and return the scalar value of the smallest and largest elements respectively- It i s an error i f either i s passed the empty set-The function CARD accepts a set as an argument and returns the ca r d i n a l i t y of i t . F.2.1.4. String string type : STRING — ( <expression> — ) 1 > The string types are denoted by the reserved word STRING followed by a l i t e r a l expression giving the maximum s t r i n g length. String variables i n HISCH may have values of a varying length, up to the declared maximum. An implementation may place l i m i t s on the range of allowed maximum lengths. Values of st r i n g types are sequences of characters from an implementation defined set (the same as the set used f o r the type CHAR), l i t e r a l s of st r i n g types are written as seguences of characters enclosed i n quotes ("). If an implementation provides alternate character types, i t must also provide string types for each character set- The maximum length of a l i t e r a l i s i t s exact length, f o r example the l i t e r a l "a s t r i n g " i s a STRING(8) value. The guote may be included i n a str i n g l i t e r a l by writing i f twice, for example "a guote " i s a STRING (10) (not 11) value. WISCH Report F. Declarations 44 The empty s t r i n g i s "". String l i t e r a l s are not allowed to cross l i n e boundaries in the source program. I t i s i l l e g a l to attempt to assign a value to a s t r i n g variable which i s longer than the variable's maximum length. Non-printable characters may not be denoted d i r e c t l y i n a s t r i n g l i t e r a l . There i s one operator on string values, %, the concatenation operator which has a p r i o r i t y of 1., This operator also accepts character values as either or both arguments, treating them as though they were STRING(1) values. The r e l a t i o n a l operators for ineguality (<, -»<, etc) perform standard l e x i c a l comparisons, with the c o l l a t i n g seguence being the ordering of the appropriate character set. If a l l "exis t i n g " characters match, the shorter s t r i n g i s always " l e s s " than the longer. These operators w i l l also accept mixtures of st r i n g and character expressions. Note that since HISCH allows constant expressions, the r e s t r i c t i o n to single l i n e strings and no non-printables i s r e a l l y no problem at a l l : CONST alpha_string = "abcdefghijklmnopgrstuvwxyz" % "ABCDEFGHIJKLHNOPQRSTUVWXYZ" ; s p e c i a l _ s t r i n g = " a s c i i control chars:" % " b e l l " % CHAR (7) % » cr " % CHAR (13) % " If " % CHAR (12) ; SISCH Seport F. Declarations 45 Substrings may be selected by s u f f i x i n g a s t r i n g variable with a substring selector, two integer expressions specifying the i n i t i a l character for the substring and the length of i t . For example; string_var (start,length) Characters i n a string are numbered from the l e f t s t a r t i n g at one. The value of a substring selection i s the "e x i s t i n g " portion of the selected s t r i n g . For example, given the code segments VAR s : s t r i n g (10); s := "12345"; the value of s(3,5) i s "345" and the value of s(7,4) i s the n u l l string.Assignment to a substring i s allowed and causes replacement of the selected s t r i n g by the r i g h t hand side. The st a r t of the substring must not be beyond the end of the current s t r i n g value. (This i s to prevent the subsequent value from having "holes" i n i t . ) There are two standard functions and one standard procedure fo r strings. The function LENGTH accepts a s t r i n g as an argument and returns i t s current length. The function FIND_CHAS accepts a s t r i n g and a character as arguments, returning the position of the f i r s t occurence of the character i n the s t r i n g . It returns zero i f the character i s not present. The procedure PAD_.STR.ING accepts a st r i n g variable and a character as arguments. It pads the value of the variable to i t s maximum length with the character. W I S C H E e p o r t F. 2.1-5. N orroal pointer F. Declarations 46 norral pointer type : <type> E_zn — PBOGRAH PUNCTIOH - | • <func f o r a a l params> • <functioc result> The space for most variables i s allocated at scope entry and deallocated at scope e x i t . I t i s also possible to a l l o c a t e data objects dynamically and have them continue to exist for an i n d e f i n i t e period. Such objects cannot be referenced in the usual manner, but must be accessed via "pointers'* to them. The "normal" pointers described here (as opposed to "pool" pointers) may point to dynamically created objects used completely within one program. For the rest of this section (only), the word pointer means normal pointer. Pointer types are declared by preceding a declaration of the object type with an at-sign (8) . To allow self-referencing types, a pointer type may be defined before or i n s i d e of i t s object type. Pointers values may only be references to values of the declared object type. Pointer types may also be declared to point to programs, procedures or functions. Their values are then references to a code object instead of a data object. WISCH Report F. Declarations 47 There i s only one l i t e r a l of any pointer type, the standard name NIL. The value of NIL i s a reference to no object. There are only two operators that accept pointer arguments, the equality operators = and -»=. The object pointed to i s obtained by s u f f i x i n g a pointer variable name with an at-sign (a>) . Data objects are created by the standard procedure NEW. I t accepts a pointer variable as an argument, creates a data object of the appropriate type and assigns a reference to the object to the pointer variable. These objects are created from a heap data area, separate from the area where normal variables are allocated. WISCH does not provide any automatic garbage c o l l e c t i o n . Dynamic objects which are no longer needed may be returned to the heap by the standard procedure DISPOSE. I t accepts a pointer variable as an argument, returns the object that i t references to the heap and sets the variable to NIL. Note that the security of the heap i s not guaranteed i f the programmer uses DISPOSE- It i s the programmer's r e s p o n s i b i l i t y to eliminate "dangling references" to recycled storage. Pointer types that are declared to reference programs, procedures or functions also have the value NIL and the equality operators, but since code objects cannot be created dynamically, the NEW procedure cannot be used with them- Instead, the standard function ADD! may be used to obtain a reference to a code object- The ADDR function may only be applied to (and hence references may only be obtained to) programs, procedures HISCH Report F. Declarations 48 and functions which are external or are declared i n the outermost scope of the program. Dereferencing a pointer to a program may only be done in a CREATE statement and y i e l d s the program pointed to. Dereferencing a pointer to a procedure or function causes i t to be c a l l e d . Although the formal parameter names of the object type are included in the declaration of the pointer, they are present f o r mnemonic reasons only and are completely ignored. The formal parameters of the objects referenced must only agree i n number, type and order with the pointer's object type. Some examples of pointer types and th e i r use are; TYPE i n t = INTEGER; i n t _ p t r = a INTEGER; node_ptr = 3 node; node = RECORD op : CHAR; l e f t : node_ptr; {node_ptr and "S node"} ri g h t : 3 node; {are equivalent types.} ENDfiECOBD; func_ptr = a FONCTION ( i : int) RETORNS (j : i n t ) ; foo = a PROCEDURE (bar: foo); {note c i r c u l a r reference} VAR i_p : i n t _ p t r ; root : node_ptr; func ; func_ptr; i s INTEGER; FUNCTION f a c t o r i a l (n: int) RETURNS ( i : i n t ) ; EXTERNAL; BEGIN NEH (i_p) ; i_p3 0; root := NIL; func := ADDR(factorial); i ;= funcS( i ) ; WISCH Report F . Declarations 49 F.2.2. Array array type : A P a A T ( —^- <scalar type> — » — ) O F <type> > t The array types are composite types, with a l l components of the same type. The components are selected by indices which may be of any scalar type. An array type i s assignable and/or sharable i f i t s component type i s . There are no operators on values of array types except the equality tests which are defined as an element by element test. An array value i s written s i m i l i a r l y to a set value. The "subrange" notation allowed for set values i s also allowed here. In addition, a re p e t i t i o n factor may be applied to a component. This i s written as "repetitions ! component". I f a l l components are l i t e r a l expressions, the value denoted i s an array l i t e r a l . Note that a component of a one dimensional array i s a simple element, of a two dimensional array i s a row, etc. For example, given the declarations;: TYPE vector = ASSAY (1..5) OF INTEGER; vecvec = ARRAY (1..2) OF vector; matrix = ARRAY (1--2, 1..5) OF INTEGER; the following: vector (-1,310 , 1 ) WISCH Beport F. Declarations 50 vecvec(2 ! vector (1,2 ,3 , 4, 5) ) matrix{2! (5,4,3,2,1)) are equivalent to; vector(-1,0,0,0, 1) vecvec (vector (1,2, 3,4,5) , vector (1,2,3,4,5)) matrix((5,4,3,2, 1) , (5,4,3, 2,1) ) Some examples of array types are; CONST prime = {an appropriate value] ; TYPE name_table = ARRAY (0., prime-1) OF STRING (10); vec = ARRAY (-1.. + 1) OF INTEGER; mat1 = ABB AY (1-.2) OF vec; mat2 = ARRAY (1-.2, -1..+1) OF INTEGER'; VAR old_names, new_names ; name_table; numsl : mat1; nums2 ; mat2; letter_counts ; ARRAY (•A..4Z) OF INTEGER; BEGIN FOR ch := »A TO 'Z LOOP letter_counts (ch) := 0 NEXT; numsl := mat1 (vec (1,2,3) ,vec(4,5,6) ) ; nums2 := mat2 ((1,2,3), (4,5, 6)) ; FOB i := -1 TO +1 LOOP numsl (1) (i) +:= numsl (2) (i) NEXT; FOR i := -1 TO +1 LOOP nums2(l,i) *•;= numsl (2,i) NEXT; Note in p a r t i c u l a r the s i m i l a r i t i e s and differences between the denotations of values of types mat1 (array of arrays) and mat2 (two dimensional array) . The standard functions LO_BND and UP_BND may be used to find the lower and upper l i m i t s of any dimension of an array. They accept an array type or expression and an integer as arguments. The integer argument selects the dimension whose bound i s wanted. I t may be omitted for one dimensional arrays. •WISCH Report F. Declarations 51 F-2-3. Record r e c o r d t y p e : B E C O B D < f i e l d l i s t > - — E H D K E C O H D *> f i e l d l i s t ^ — < i d e n t > < t y p e > P O B K < v a r i a u t b o d y > J O I N 7ZT variant b o d y : < i d e n t > <scalar type> OF <case f i e l d l i s t> case f i e ld l i s t : * • C ' S E < e x p r > < e z p r > <field l i s t> <field l i s t> The record types are composite types with components of possibly different types. The components are selected by i d e n t i f i e r s known as f i e l d selectors. The f u l l name of a record f i e l d i s the record name, a dot (.) and the f i e l d i d e n t i f i e r . The i d e n t i f i e r s of a l l f i e l d s i n a record must be d i f f e r e n t , but may be the same as i d e n t i f i e r s i n other (possibly nested) records or i d e n t i f i e r s outside the record. S p e c i f i c a l l y , the f u l l names of a l l record f i e l d s must be unigue i n a l l scopes where that name i s known. HISCH Report F. Declarations 52 Record types may also have "variant" portions whose exact structure i s determined by a "tag f i e l d " . The value of the tag f i e l d determines which of the cases in the FORK clause apply. F i e l d names i n di f f e r e n t cases must be d i f f e r e n t from each other and d i f f e r e n t from a l l other f i e l d names in the record. Values of a record type (with no variants) are written l i k e array values, except that the components are of possibly d i f f e r e n t types and the r e p e t i t i o n notation may not be used. Values may not be written for records with variant portions. Some examples of record types are; TYPE binary_tree_node = RECORD kind : 0..10; l e f t , right : a> bin_tree_node; ENDR ECORD; dev_kind = [disk, mag_tapei, paper_tape, terminal); status_rec = RECORD up ; BOOLEAN; channel ; INTEGER; i o _ w a i t _ l i s t : S process_list_node; FORK kind : dev_kind OF CASE disk : block_size : INTEGER; CASE mag_tape : density : INTEGER; nine_track : BOOLEAN; OTHER : [emptyj ; JOIN; ENDR ECORD; HISCH Beport F. Declarations 5 3 F . 2 . 4 . Pool pointer pool pointer type : 3 POOLED <type> » Pool pointers are the second pointer type i n WISCH. Where normal pointers may point only to heap or "code" objects known within a single program, pool pointers may only point to pooled data objects. Since pools may only contain objects of a shareable type, pool pointers may only point to objects of a shareable type. They are not assignable and may only be compared with the value NIL (not with each other since they w i l l never be equal). Upon creation, a l l variables of pool pointer types are i n i t i a l i z e d to the value NIL. Shared variables are created by the standard procedure NEW, but are not necessarily allocated from the same heap as non-shared variables. The procedure DISPOSE may also be used to return shared variables to free storage. A reference to a shared object may be assigned to a pool pointer only by the NEW procedure or the AWAIT statement. In either case the pointer must have the value NIL immediately prior to the assignment. This reference i s removed when the pointer i s subsequenly used in a SEND statement. It i s "guaranteed" that no shared object can be pointed to by more than one pool pointer at a time. (The guarantee i s not absolute since there are ways i n WISCH to circumvent a l l checks i f one i s WISCH Beport F - D e c l a r a t i o n s 54 r e a l l y so i n c l i n e d . ) P o o l p o i n t e r s may not be d e r e f e r e n c e d except v i a t h e BIND st a t e m e n t . F_2.5_ P o o l p o o l t y p e : POOL OP <type> > The b a s i c s e m a n t i c s of p o o l s have a l r e a d y been d i s c u s s e d . P o o l s a r e c o l l e c t i o n s of message b u f f e r s t h a t a r e shared among p r o c e s s e s f o r the purpose of communication. P o o l s may o n l y c o n t a i n o b j e c t s o f s h a r e a b l e t y p e s . The o b j e c t s i n t h e p o o l a c t u a l l y c o n s i s t of an i n a c c e s s i b l e p o r t i o n used f o r l i n k a g e , e t c . , and t h e a c c e s s i b l e b u f f e r p o r t i o n . They may be viewed as l i n k e d l i s t s o f d a t a o b j e c t s , a l l o f t h e same t y p e . a l l p o o l s a r e empty when c r e a t e d . I f t h e o b j e c t type o f a p o o l i s o r c o n t a i n s a dynamic subrange, the range e x p r e s s i o n s are n o t e v a l u a t e d and a s s o c i a t e d w i t h t h e pool v a r i a b l e . When a sh a r e d v a r i a b l e i s c r e a t e d by t h e NEW p r o c e d u r e , any dynamic subrange bounds a r e e v a l u a t e d and f i x e d f o r t h a t one o b j e c t . The same p o o l p o i n t e r may l a t e r be used t o c r e a t e a n o t h e r shared v a r i a b l e w i t h d i f f e r e n t subrange l i m i t s . S i n c e a p o o l v a r i a b l e i s r e a l l y j u s t a header f o r a l i n k e d l i s t of shared v a r i a b l e s , t h e p o o l may c o n t a i n s e v e r a l v a r i a b l e s w i t h d i f f e r e n t l i m i t s f o r any dynamic subranges. Thus, one c o u l d c r e a t e a p o o l which HISCH Report F. Declarations 55 contained varying length one dimensional vectors of storage units. For example; TYPE buffer_pool = POOL OF ARRAY (lwb..upb) OF STORAGE; where lwb and upb are variables declared elsewhere. There are no l i t e r a l s , constants, or operators for pool types. Only variables and VAS parameters may be of pool types. Variables of pool types must be declared i n the outermost scope of a program. There are two standard functions, EMPTY and WAITING, which accept a pool variable and return a boolean value.. EMPTY returns TRUE i f there are no objects l e f t in the pool. WAITING returns TRUE i f there are any process waiting f o r access to objects from the pool. Note that WAITING implies EMPTY. References to pooled objects are obtained and relinquished using the AWAIT and SEND statements. A l l pooled objects have a pool associated with them, the reply pool, which may be used to t e l l a process where to return the object. The reply pool i s i n i t i a l l y a standard "garbage" pool, but may be changed i n the SEND statement. F.2.6. Process The type process i s denoted by the standard type name PROCESS. Only variables and VAR parameters may be of type process. Variables must be declared i n the outermost scope of a program. There are no l i t e r a l s or constants of process type. WISCH Report F. Declarations 56 and no operators on values of process type. Process variables may only be acted upon by the CREATE, START, STOP and DESTROY statements. A process may be in one of four states. I t may not exis t (a process variable which could be said to have a void value). I t may e x i s t , but be stopped, i n which case i t cannot execute further u n t i l restarted. I t may be ready, i n which case i t i s ready to be executed by a processor at any time. Lastly, i t may be blocked, t h i s occurs when i t i s waiting on some external event (usually waiting on a reguest f o r a pooled object). There i s a standard enumeration type, process_status_type, and a standard function, process_status, that may be used to determine the current status of a process. They are defined as: TYPE process_status_type = [void, stopped, blocked, ready}; FUNCTION process_statas (CONST proc ; PROCESS) : process_status_type; (return the current status of proc}; F , 2 . 7 . Compatability, coercions and attributes Two l e v e l s of compatibility are defined i n WISCH. A type x i s weak!y compatable with a type y i f the intersection of t h e i r sets of values i s not empty. A type x i s strongly compatable with a type y i f the values of x are a superset of (or the same as) the values of y. WISCH Report F. Declarations 57 For example, given the declarations; TYPE zero_to_ten - 0..10; one_to_nine =1.-9; The type zero_to_ten i s strongly compatable with one_to_nine, but one_to_nine i s not strongly compatable with zero_to_ten. They are of course weakly compatable with each other. Note that weak compatability i s a commutative r e l a t i o n but strong compatability i s not. Also, x strongly compatable with y implies at l e a s t y weakly compatible with x. I n t u i t i v e l y , i f x i s weakly compatable with y, then values of type y may be assigned to a variable of type x with appropriate run time checks for range errors. I f x i s strongly compatable with y, then values of type y may always be assigned to a variable of type x with no checking at run time. The standard types BOOLEAN, CH AB, and PROCESS are of course compatable themselves. Any two subrange types are weakly compatable i f they are defined on the same basis type and have a non-null i n t e r s e c t i o n . A scalar type x i s strongly compatable with a scalar type y i f y i s a subrange of x. {Note that any scalar type i s a subrange of i t s e l f . ) INTEGEB, BEAL, STOBAGE (strongly and weakly) with MISCH Seport F. Declarations 58 Two set types are compatable (weakly and strongly) i f t h e i r basis types are the same. Any two str i n g types are weakly compatable. String type x i s strongly compatable with s t r i n g type y i f the maximum length of x i s at least as large as that f o r y. Two normal pointer types are compatable (weakly and strongly) i f t h e i r object types are strongly compatable. Two pool pointer types are compatable (weakly and strongly) i f t h e i r object types are strongly compatable. Two pool types are compatable (weakly and strongly) i f th e i r object types are strongly compatable. Any two module types are weakly (strongly) compatable i f a l l exported names are the same and are weakly (strongly) compatable. Two array types are weakly (strongly) compatable i f the i r index types are i d e n t i c a l and their component types are weakly (strongly) compatable. Two record types are compatable (weakly and strongly) i f a l l f i e l d s have the same names (in the same order) and are a l l of strongly compatable types. WISCH Report F . D e c l a r a t i o n s 59 The use of (and need f o r ) type c o m p a t a b l i l t y i s d i s c u s s e d i n the s e c t i o n s about programs, procedures, f u n c t i o n s , the assignment statement and exp r e s s i o n s -There are only two type c o e r c i o n s i n WISCH- Where a p p r o p r i a t e , the types CHAR and STRING ( 1 ) are coerced t o each ot h e r . and INTEGER may be coerced t o REAL. Note t h a t these c o e r c i o n s only apply to uses i n e x p r e s s i o n s . For example, an i n t e g e r value may be used as an argument to a procedure where the c o r r e s p o n d i n g f o r m a l parameter i s a CONST or p l a i n parameter of type REAL, but i t may not be used i f the corresponding f o r m a l parameter i s a VAR parameter of type REAL. (See the d i s c u s s i o n on parameters of programs, procedures and f u n c t i o n s f o r an e x p l a n a t i o n of CONST, VAR and p l a i n parameters.) However, t r a n s f e r f u n c t i o n s do e x i s t f o r programmed co n v e r s i o n s . R e c a l l t h a t any s c a l a r type name may be used as a g e n e r i c t r a n s f e r f u n c t i o n t o c o n v e r t s c a l a r values to the named type. I n s i d e a machine dependent program, procedure or f u n c t i o n , any type name may be used as a g e n e r i c f u n c t i o n with a s i n g l e argument t o convert the type of the argument to the named type. The s i z e s of values of the two ty p e s must be the same. (A r o u t i n e i s d e c l a r e d "machine dependent" by u s i n g the OPTION statement.) WISCH fieport F. Declarations 60 Standard functions exist to access various attributes of data types. The FIRST and LAST functions for scalar types have already been mentioned. The VALUE_SIZE function provides information about the space required to hold values of any type. I t accepts a variable or type name and returns an integer, the number of storage units needed to hold a value of that type. The function TOTAL_SIZE i s s i m i l a r , except i t returns the t o t a l number of storage units needed by a variable of that type. For example, TOTAL_SIZE gives the number of storage units of heap space that s i l l be used i f a variable of that type i s created by the NEW procedure. The functions LO_BND and 0P_BND accept two arguments, the name of an array variable and an integer expression, and return the lower and upper bounds of the appropriate dimension of the array respectively. Of course, the integer expression must have a value between one and the number of dimensions of the array (inclusive). F-3- Variable v a r i a b l e d e c l a r a t i o n : r — PKRVASIVE —a—- VIB \ - O a r l i s t > : <type> -» var list <ident> — ? — := <expression> I ( ^ir. <ident> •  <ezpression> WISCH Beport F. Declarations 61 Variables are declared via the VAR declaration- A l l variables used in a program must be declared before use. I f a variable i s of an assignable type, an i n i t i a l value may be specified for i t . Each time the variable i s created (at a scope entry) the expression i s evaluated and the value i s assigned to the variable. Note that although pool pointer variables are not assignable, they are always i n i t i a l i z e d to NIL when created (by scope entry or use of the NEW procedure). The i n i t i a l value expression refers only to the i d e n t i f i e r (or l i s t of i d e n t i f i e r s on i t s immediate l e f t - For example: VAB i , j:=0, k : INTEGER; causes only j to be i n i t i a l i z e d , while: V1B ( i , j ) : = 0, k : INTEGER; causes both i and j to be i n i t i a l i z e d . F. U . Program p r o q r a a d e c l a r a t i o n ; < p r o g r a o h e a d i n g > < p r o g / p r o c / f u n c b o d ? > E X T E B N A L T ~ T ; T - > p r o g r a m h e a d i n g I PROGRAM < i d e n t > — q — < p r o g / p r o c / f u n c f o r o a l p a r a m s > ^ j 1 ; ^ > p r o g / p r o c / f u n c f o r a a l p a r a a s : COMST v < i d e n t > - VAR -<type> A 1 • > HISCH Report F. D e c l a r a t i o n s 62 p r o g / p r o c / f u n c body : — — <decls> — — BEGIN — <ident> — <statoments> — BHD — - <ideut> > Most of the f e a t u r e s of programs have already been presented. A l l t h a t r e a l l y remains i s to d i s c u s s f o r m a l parameters. Programs (and procedures) may have three kinds of formal parameters, VAR, CONST and p l a i n . For VAR parameters, the types of a c t u a l arguments must be s t r o n g l y compatable with the corresponding formal parameters. For CONST and p l a i n parameters, t h e a c t u a l arguments need only be weakly compatable with the corresponding formal parameters. Var parameters are passed by r e f e r e n c e , that i s a use of the f o r m a l parameter i n the program i s r e a l l y a use of the a c t u a l argument passed v i a the CREATE statement. A l l "name computation" (array s u b s c r i p t i n g , p o i n t e r d e r e f e r e n c i n g , etc.) f o r VAR parameters i s done once, while arguments are being evaluated i n the CREATE statement. The a c t u a l argument f o r a VAR parameter must be a v a r i a b l e name. The onl y VAR parameters allowed f o r programs are pool v a r i a b l e s . CONST parameters are t r e a t e d as cons t a n t s i n the program. T h e i r value i s the value of the a c t u a l argument, which must be an e x p r e s s i o n (of which a l i t e r a l or v a r i a b l e r e f e r e n c e i s a HISCH Report F. D e c l a r a t i o n s 63 t r i v i a l k i n d ) . Note that CONST parameters can only be of an a s s i g n a b l e type. P l a i n parameters are those f o r which n e i t h e r VAR or CONST i s s p e c i f i e d . They look l i k e l o c a l v a r i a b l e s which are i n i t i a l i z e d to the value o f the a c t u a l argument ( i . e . passed by v a l u e ) . The a c t u a l argument must be an e x p r e s s i o n . F.5. Procedure procedure declaration : <procedure heading> <prog/proc/func body> EXTEBHAL. FOEBABD procedure heading rSOCEDtJBE - <ident> <prog/proc/func formal parass> prog/proc/func fornal paraas COM ST - VAR -JL sir <ident> —i— : <type> -ja— prog/proc/func body : — <decls> BEGIN <iaent> <statenents> SHD <ident> > WISCH Eeport F. Declarations 64 A l l procedures i a WISCH are capable of being c a l l e d recursively. They may be nested to any depth. Formal parameters for procedures are the same as for programs, except that procedures may have VAB parameters of any type. Name computation f o r VAR parameters i s done only once, while arguments are being evaluated prior to the actual c a l l . F.6. Function f u n c t i o n d e c l a r a t i o n : —— < f u n c t i o n h e a d i n g > <prog/proc/func body> -jjf E X T E R N A L '• : FORWARD • f u n c t i o n h e a d i n g : F U H C T I O N — < i d e n t > — j — < f a n c f o r a a l s > - J R — < f u n c r e s u l t > f u n c t i o n r e s u l t : R E T U R N ( < i a e n t > : < t y p e > ) p r o g / p r o c / f u n c f o r n a l p a r a a s : ( - ™ | | CONST 4t • < i d e n t > - VAR -< t y p e > ~x p r o g / p r o c / f a n c b o d y : " • » < d e c l s > B E G I K < i d e n t > < s t a t e a e n t s > — E H D — < i d e n t > > Like procedures, a l l functions are recursive and may be nested to any depth. Function formal parameters are the same as for programs and procedures. The function value i s returned via WISCH Report F. Declarations 65 the RETURNS variable. Within the function looks l i k e a l o c a l variable. When the function returns, i t s value becomes the value of the function. __Z_ Module feodule d e c l a r a t i o n : HODOLB < i d e n t > —p- < i a p / e x p > — ; j — - <nodule body> END <ident> > inp/exp * I I M P O R T JK<ident> — ^ — r — ; ~>y 1— E X P O R T — ' 1 •—' n o d u l e b o d y : < d e c l a r a t i o n s > •• "j < i n i t i a l a c t i o n > •• [• •• < f i n a l a c t i o n > ^ • > i n i t i a l a c t i o n : I N I T I A L < b l o c k b o d y > E N D I H I T I A L > f i n a l a c t i o n : P I N A L < b l o c k b o d y > E H D P I K A L • > b l o c k b o d y : < d e c l a r a t i o n s > B E G I N — — < s t a t e a e n t s > > Modules provide an means to encapsulate variables and routines. The modules of WISCH are derived from those of MOD ULA. They allow the implementation d e t a i l s of an abstract design to be hidden from the users of that design. I d e n t i f i e r s HISCH Report F. Declarations 6 6 defined inside a module are unknown outside of that module unless they are e x p l i c i t l y exported. Exported variables are read only outside of the module. Exported types are "opaque", variables of that type may be declared outside of the module but they may not be operated on externally since the structure of the type i s unknown. They may only be operated on by routines defined within the module. I d e n t i f i e r s known i n the scope surrounding the module are unknown within the module unless they are e x p l i c i t l y imported {or are PERVASIVE). When a module i s created (when i t s containing scope i s entered), the optional INITIAL block i s executed. This can be used for any necessary i n i t i a l i z a t i o n of int e r n a l (or external) data structures. When the containing scope i s exited the optional FINAL block i s executed, providing a means to do any f i n a l cleanup, reporting, etc. WISCH Report F. Declarations 67 An example of a module i s ; MODULE symbol_table_manager IMPOST tab l e _ s i z e , sym_type; EXPORT enter_syra, find_sym; VAR sym_tab ; ARRAY (0..table_size - 1) OF sym_type; num_entries, num_collisions : INTEGER; PROCEDURE enter_sym (ne»_sym : syn_type) ; {add new_sym to table i f not there nowj ; END enter_sym; PROCEDURE find_sym Csym:sym_type; VAR found: BOOLEAN) ; {look up. sym (by name), i f found then} { f i l l i n the rest of the info to sym } ; END find_sym; INITIAL BEGIN (num_entries, num_coliisions) ;= 0; ENDINITIAL FINAL. BEGIN {report s t a t i s t i c s on use, c o l l i s i o n s } ; ENDFINAL END symhol_table_manager; F. 8. Scop_e of names The region of source text in which a par t i c u l a r name (and the object i t names) i s known i s c a l l e d the scope of that name. These nested, delimited regions are c a l l e d scopes. The scope delimiters i n WISCH are program declarations, procedure declarations, function declarations, module declarations, blocks, FOR statements and BIND statements. A l l references to a HISCH Report F. Declarations 68 name are to the innermost declaration of the name, working outward from the reference. Normally, the only names known within a program are the formal parameter names and l o c a l l y declared names. A l l names declared i n outer scopes are unknown. This rule i s excepted for PERVASIVE names, which are known i n a l l inner scopes and cannot be redeclared. Any constant or type name may be PERVASIVE, but the only variables that may be are pool variables. Procedures, functions and blocks know the innermost declaration of a l l names declared i n outer scopes. The only (non-PERVASIVE) external names known i n a module are those which are e x p l i c i t l y imported. Names which are exported from a module are known as though declared i n the immediately surrounding scope. The index variable of the FOR statement i s known only within the statement body, where i t i s a constant. The binding i d e n t i f i e r of the BIND statement i s known only within the statement body, where i t i s a normal variable. Once a name has been used i n a scope {e.g., i n an expression or as a type i d e n t i f i e r ) , i t ma.y not be redeclared i n that scope {but may be i n an inner scope). For example, the following i s i l l e g a l : CONST max_size = 1 0 0 0 ; PROCEDURE foo; VAR index : 0..raax_size; CONST max_size = 1 0 0 ; WISCH Report G. Statements 69 Statements statements : <block> <as?:ignnRnt s t a t e m e n t > < p r o c e d u r e c a l l > — — — < r e t u r n s t a t e m e n t > < i f s t a t e a e n t > T 7 N <loop s t a t e m e n t > < f o r s t a t e m e n t > — <<v*it s t a t e n o n t > — < i t e r a t e s t a t e n e n t > < f o r k s t a t e ; s e n t > <bind s t a t e m e n t > < a s s e r t s t a t e i c e n O -< c r e a t e s t a t e n e n t > -< s t a r t s t a t e m e n t > — <stop s t a t e m e n t > < d e s t r o y s t a t e n e n t > <send state£sent> — -< a v a i t s t a t e a e n t > < o p t i o n s t a t e m e n t > G. 1 - Block block : BLOCK <bloc!c body> EHDBLOCK > b l o c k body : <dr-cIarati.on;i'> BEGIN <statements> The block opens a new scope, allowing l o c a l declarations to be made. I t i s e s s e n t i a l l y an i n l i n e , parameterless procedure. WISCH Report G. 2. Assignment G- Statements 70 a s s i g n m e n t s t a t e a e n t <narae> ; 3 < a s s i g n s y B b o l > —— < e x p r e s s i o n > <name> <nane> < n a n e > a s s i g n s y m b o l : ( n o e a b e d d e d b l a n k s ) < r e l o p > := <add op> — — := • < s u l o p > : = ' < p o w e r o p > : = — : — <add o p > = — — : < m u l o p > = — L— . < p 0 v e c op> — • = WISCH has a large variety of assignment symbols. The standard assignment uses := to assign the value of the expression on the r i g h t to the storage sp e c i f i e d by the name on the l e f t . The name i s evaluated after the expression to be assigned. The type of the name must be weakly compatable with the type of the expression. I f i t i s strongly compatable, no run-time checks are needed; otherwise a check must be made before the assignment to ensure type sequrity. The symbol performs a storage swap. For simple values, a b i s equivalent to (but perhaps more e f f i c i e n t than): BLOCK VAR t : type_of_a_and_b; BEGIN t := a; a := b; b z- t; ENDBLOCK; WISCH Seport G. Statements 71 For overlapping values (e.g., two substrings of the same variable) the re s u l t of a :=: b i s implementation defined. The other assignment symbols are a l l very similar to one another, being shorthand for "update" operations on variables. They may be divided into two classes by form {and function). The f i r s t c l a s s i s of the form "op;=", the second i s ":op=". For the f i r s t , a op:= b i s equivalent to a z- a op b, except that the name of "a" i s evaluated only once i n the former case. S i m i l a r l y , a :op= b i s equivalent to a := b op a. For example: i +:= 1 increments the integer variable i by 1, and s :%= "value of s: " concatenates "value of s: " onto the front of s t r i n g variable s. There i s one of these symbols (in each form) for each binary operator (for which i t makes sense). Multiple assignments are allowed for a l l assignment operators except the swap operator by writing a parenthesized l i s t of variable names to be assigned to. For example: (a,b,c) +: = expr; i s equivalent to: a *:= expr; b •:= expr; c +:= expr; except expr i s evaluated only once i n the former case, before any of the names. WISCH Report G. Statements 72 G.3, Procedure c a l l p r o c e d u r e c a l l : <name> — i — ( ^ <expression> — * — ) > Procedures are c a l l e d by simply writing the procedure name and supplying a l i s t of actual arguments- The arguments are evaluated from l e f t to right , and must be strongly compatable with their corresponding formal parameters, G.4. Return r e t u r n s t a t e a e n t : R E T U R N > The return statement i s simply the word RETURN- I t causes an immediate return from the current procedure or function. It i s i l l e g a l to attempt to return from the outer l e v e l of a program. (To stop a program use the STOP statement.) HISCH Report G. Statements 73 G.5. If i f statement : EL I F I F - i k - < e x p t > T H E N < s t Q t s > - i — p E LSE < s t a t s > -7^- FI The IF statement allows ar b i t r a r y seguences of statements for either branch. The ELIF clause allows concise coding of the common IF-THEN-ELSE-IF seguence. For examples IF bl THEN s i ; s2; ELSE IF b2 THEN S 3 ; s<4; F l ; F l ; can be compressed t o : IF b1 THEN s1; s2; ELIF b2 THEN s3; s4; F l ; WISCH Report G . 6 . Loop G. Statements 74 l o o p s t a t e a e n t : LOOP <statements> NEXT > The i n d e f i n i t e looping structure of WISCH i s actually defined via two statements, LOOP and EXIT- The LOOP statement delimits a range of statements to be repeated u n t i l terminated by executing an EXIT statement. This provides a single structure to handle a l l common forms of looping such as the "while" and "repeat" statements of PASCAL-The t r a d i t i o n a l "WHILE b DO s" form can be written as: LOOP EXIT UNLESS b; s • NEXT; The "REPEAT s UNTIL b" form can be written as: LOOP s« EXIT WHEN b; NEXT ; The "n+1/2" times loop can be written as: LOOP s1; EXIT WHEN b; s 2 ; NEXT ; WISCH Report G. Statements 75 G. 7. Exit loop control: T — EXIT -x—I— UNLESS - — — <expr> 'Vk"-| DOIKG <stmts> FIH — a f — - ITERATE — " — WHEN 1 1 •• ' The EXIT statement i s used to immediately exit from the closest enclosing LOOP or FOR within the current program, procedure or function body. Use of the EXIT statement when not inside a loop (in the current program, etc.) i s i l l e g a l . In other words, the EXIT must have something to e x i t from, and cannot cause execution to leave the current program, procedure or function. I t i s legal though to EXIT from a l o c a l BLOCK. The exit w i l l occur unconditionally i f no WHEN clause i s present, otherwise i t w i l l occur i f the boolean expression i s true. The DOING clause allows s p e c i f i c a t i o n of a "postlude" action, useful f o r multi-level exits and "side e f f e c t s " f o r s p e c i f i c exit conditions. For example, consider the following code to do disk track a l l o c a t i o n : new_track z- - 1 ; FOR cylinder := 0 TO last_cyUnder LOOP FOR track ;= 0 TO tracks_per_cylinder-1 LOOP EXIT WHEN -reserved(cylinder,track) DOING new_track := cylinder*tracks_per_cylinder + track; EXIT; {from outer FOR also} FIN; NEXT; NEXT ; IF new_track ->= - 1 THEN . . . When a free track i s found, both loops are exited and new_track KISCfl Report G. Statements 76 i s assigned the value of the track- If no tracks are free, the outer loop w i l l f i n i s h leaving new_track as -1- This loop construct (and example) are due to M. Yasumura iYAS 773-G.8. For for statement : F O E <for control> L O O P <stateaents> — — N E X T > for control : <ident> := — <expr> — j — TO <expr> — p - BY <eipr> ^ A > '— B Y — — <expr> — — TO — <expr> ' The FOR statement i s very s i m i l a r to those found i n other ALGGL-like languages. The index variable i s l o c a l to the loop and i s a constant within i t . The «;=« and "TO" control expressions may be of any scalar type (but must be of the same type) and the "BY" expression must have an integer value. The semantics are roughly to step the index variable from the z= value to the TO value, using every ABS (BY) 'th value inbetween. The sign of the BY expression determines whether the loop i s ascending (positive) or descending (negative). The BY expression must not be zero. I f the i n i t i a l value i s beyond the f i n a l at the s t a r t , the loop body i s n ' t entered. A l l three control expressions are evaluated only once, at the beginning of the loop. The FOR statement may also be exited early via an EXIT statement. WISCH Report G. Statements 77 The precise semantics of the FOB statement are i l l u s t r a t e d by the following WISCH code: FOB index := st a r t TO f i n a l BY step LOOP statements NEXT i s eguivalent to; ELOCK TYPE -int = INTEGER; index_type = {type of st a r t and final} ; CONST t1 = f i n a l ; t2 = step; vaa t3:=start : index_type; BEGIN LOOP EXIT WHEN (int (t3) *SIGN (t2) ) > (int (t 1) *SIGN (t2) ) ; BLOCK CONST index = t3; BEGIN statements; ENDBLOCK; t3 := index_type (int (t3) +t2) ; NEXT; ENDBLOCK; where t l , t2 and t3 are not otherwise used i n the program. l o o p c o n t r o l : WISCH Report G. Statements 78 The ITERATE statement causes an immediate jump to the next i t e r a t i o n of a LOOP or FOR statement. For a LOOP statement, t h i s means to the s t a r t of the loop body and for a FOR statement to the "increment and tes t " portion. Like the EXIT statement, i t may only be used inside a LOOP or FOR statement i n the current program, procedure or function. _ _ ± Q _ Fork fork stateaent : \ FORK <expression> — OF —— <case stmt list> — — JOIH case stat l i s t : CASE - - - <ex - OTHER pr> <expr> <statenents> <stateaents> The FORK statement i s WISCH's version of what i s known in some languages as a "case" statement. The branch expression must have a scalar value, which selects one of the labeled case l i s t s f or execution. The case labels must be l i t e r a l expressions agreeing i n type with the branch expression. A pa r t i c u l a r case may be labeled by any number of values. The "subrange" form of case l a b e l i s short f o r the l i s t of a l l values in the range. The OTHER case i s selected i f none of the e x p l i c i t labels match the expression value. It i s an error i f no OTHER case i s present and none of the e x p l i c i t labels match. WISCH Report G. 1 1. Bind G- Statements 79 bind stateaent : I : 1 B I N D v | < i d e n t > TO <name> ~ a r - 1 — I N < s t a t s > D N B I H D ) The BIND statement creates a scope in which a (long and complex) variable name i s bound to some (short and simple) i d e n t i f i e r (the bound i d e n t i f i e r ) . On entry to the statement, the variable name i s "evaluated", possibly involving such actions as array subscripting, record f i e l d selection and/or pointer dereferencing. The bound i d e n t i f i e r i s then made to refer to the selected storage location and has the same type as the name. Subseguent changes to the "name" do not change the location referenced by the bound i d e n t i f i e r . Pool pointers may only be dereferenced when used as part of the variable name in a BIND statement. A pool pointer may not be altered (by a SEND or AWAIT) while i t i s dereferenced i n a BIND statement. G.12. Assert a s s e r t s t a t e a e n t : A S S E R T — ( — < e x p r e s s i o n > HISCH Report G. Statements 80 The ASSERT statement evaluates the boolean expression, and i f i t i s not TRUE, causes the process to stop with a f a t a l error. G.1 3 . Create Create statement : — - C R E A T E <name> - — FROH — < n a a e > — < c r e a t e o p t i o n s > ••' > c r e a t e o p t i o n s : {011st b e i n o r d e r f r o a t o p t o b o t t o m ) ERROR < n a a o > — PRIORITY <expression> j ! STACK ——• <expression> — HEAP — — <exprassion> — TIME — <expression> The CREATE statement creates a new process modeled a f t e r the specified program. The process variable must not already refer to an exis t i n g process. G. 1 a. Start s t a r t s t a t e m e n t : S T A R T <name> > WISCH Beport G- Statements 81 The STABT statement removes a process from the stopped state. Where i t goes depends on i t s state when i t was stopped. If i t was waiting, i t w i l l go back to a waiting state, otherwise must have been in a started state and w i l l join the l i s t of processes ready to be executed. I t w i l l then be given processor time in some implementation defined manner (the only guarantee i s that i t w i l l be given processor time eventually). G. 15. Stop stop statenent : STOP — I — <narae> A — > I HISELF 1 The STOP statement removes a process from the started or waiting states and puts i t i n the stopped state. As long as i t i s stopped, i t w i l l not get any processor time, nor w i l l i t be given any shared objects i f i t was waiting. G-.J.6- Destroy d e s t r o y s t a t e a e n t : DESTIiOT <naoe> > WISCH Report G. Statements 82 The DESTROY statement destroys the process, which must be i n a stopped state. A l l pooled objects to which the object has references are returned to t h e i r owner pools. __12_ Await a v a i t s t a t e a e n t : AWAIT < n a a e > FROH < n a a e > » The AWAIT statement requests that an object be allocated from a pool and the reference to i t assigned to a pool pointer. The pointer must have the value NIL before the assignment. I f an object i s available the process i s given i t and allowed to continue. I f the pool i s empty, the process i s put in the waiting state and attached to the pool. G. 18. Send s e n d s t a t e a e n t ; SEND <name> TO <naae> • - SENDER RESPOHD < u a a e > The SESD statement sends an object pointed to by a pool pointer to a pool, allowing the sending process to continue. If the pool i s empty and there are any processes i n the waiting WISCH Report G. Statements 83 state, one of them i s given access to the object and placed i n the started state. I f OWNER i s specified in the TO clause, the object i s sent to i t s owner pool. I f SENDER i s specif i e d , i t i s sent to the response pool given in the previous SEND on that object. The RESPOND clause s p e c i f i e s the pool to be used in future "returns to sender". I f i t i s omitted, the f i e l d i s l e f t unchanged. G.19. Option option statement : OPTION <iient> The OPTION statement i s used to specify compile time options. (At t h i s time, the standard options are undefined.) BISCH Report H. E x p r e s s i o n s 84 H_ Expressions expression : — <relation> - - j - - <repeat op> - — <relation> ^ ) relation : <siap expr> <rel op> <simp expr> —— ' > h~ <elem op> — <siap expr> s i i r . p e x p : <uaary op> - <tera> j ^  <add op> - — <tera> ^ * tern : <factor> < E U 1 op> <factor> factor : <itea> — j ^  <potrer op> - — <factor> ~* ^  — » item : ( — a—• <expression> • '• • ) —yr - 1 — i ——-I <Uteral> ' <naae> rel op < — -.< -<= ->= --.>= > — add op I — II ' XOR % — elea op BUI op — — • -»IH - — 1 * — / — DIV REM MOD S — 6 6 -WISCH Report H» E x p r e s s i o n s 8 5 <ident> I , — ( — 3 t - <expression> . <ident> — . a i d e n t : (no embedded b l a n k s , l a s t c h a r cannot be _) < l e t t e r > -i <letter> 1 ^  < d i g i t > -unary op : Eh. l i t e r a l : <boolean l i tera l> — <char l i tera l> <enurcerated l i t e i a l > <integer l i t era l> <real l i t era l> <string l i t era l> —— <st.orago l i t era l> < s t r u c t u r e d l i t e r a l > power op : ** > repeat op : ! > While t h i s r e p o r t d i s c u s s e s e x p r e s s i o n s i n terms of "typed" e x p r e s s i o n s , i e . i n t e g e r , boolean, e t c . , and programmers u s u a l l y t h i n k of them i n these terms, i t i s very important to r e a l i z e t h a t the a n a l y s i s of ex p r e s s i o n s i n WISCH i s governed s o l e l y by the precedence of op e r a t o r s and not by the types of the operands. T h i s i s not to say th a t types are ignored, on the con t r a r y , WISCH i s a s t r o n g l y typed language and a l l operands must have s u i t a b l e types f o r t h e i r o p e r a t o r s . What t h i s does say i s t h a t the determination of which opera t o r s have which operands i s done on the b a s i s of operator precedence only. T h i s i s e s p e c i a l l y n o t i c e a b l e i n e x p r e s s i o n s which c o n t a i n boolean HISCH Report H. Expressions 86 operators (S, | , and -«) and r e l a t i o n a l operators. Since the boolean operators are treated liJce other scalar operators (such as * or * f o r integers), they have higher p r i o r i t y than the r e l a t i o n a l operators. Thus common expressions such as: (p NIL) & (pa.value < a) must be parenthesized f c r proper i n t e r p r e t a t i o n . The following table summarises the operators available in WISCH: operator prec. operands description ** 3 integer,real exponentiation * 2 integer,real m u l t i p l i c a t i o n * 2 set set intersection / 2 r e a l r e a l d i v i s i o n DIV 2 integer integer d i v i s i o n REM 2 integer integer remainder MOD 2 integer mathematical modulus & 2 boolean l o g i c a l and &S 2 storage bitwise and + , ~ 1 i n t e g e r , r e a l addition, subtraction 1 set set union, set difference 1 1 boolean l o g i c a l or II,XOB 1 storage bitwise or, bitwise xor % 1 s t r i n g s t r i n g concatenation *,- <l integer,real unary plus, unary minus ABS 1 integer,real unary absolute value - 1 set unary set complement 1 boolean unary l o g i c a l negation 1 storage unary bitwise complement <,-<,<= 0 any < 1 > general inequality test - < = r > = . 0 i i it « ii ->=,>,-> 0 n i i II II = , ~ v = 0 any,pointer " equality " IN . - . I H 0 scalar S set set element test <1> Where "any" means any scalar, r e a l , s t r i n g or set type. WISCH Seport I. I/O f a c i l i t i e s 87 __ I/O f a c i l i t i e s The WISCH programmer has a need for two d i s t i n c t forms of I/O f a c i t i t i e s . First,, i n order to write an operating system, f a c i l i t i e s must he provided to control and communicate with any device at the l e v e l of a device handler- Second, higher l e v e l mechanisms are needed to perform the I/O required by the higher l e v e l protions of the system, e.g., to read from and write to a "console" terminal or to access f i l e s on backing store. The low l e v e l f a c i l i t i e s are v i r t u a l l y impossible to define i n a machine or even configuration independant manner. Different machines have vastly d i f f e r e n t mechanisms for co n t r o l l i n g peripheral equipment. A single machine may have quite d i f f e r e n t means of communicating with d i f f e r e n t devices depending on the device type, use of direc t memory access, etc. Because of these d i f f i c u l t i e s , WISCH does not define a single approach to I/O. Instead, an implementation must provide the necessary low l e v e l drivers as standard routines that may only be c a l l e d from a machine dependant program, procedure or function. These drivers w i l l provide only very low l e v e l support, f o r example seeking a disk arm to a cylinder, reading/writing a sector from the current cylinder, requesting status information, reading/writing a single character/line to/from a terminal, etc. To the process requesting i t , the I/O transfer appears as a WISCH fieport I. I/O f a c i l i t i e s 88 synchronous, i n d i v i s i b l e operation. The WISCH programmer has no need to be at a l l concerned about any underlying interrupt structure. I f a process i n i t i a t e s an I/O operation that i s interrupt driven, i t w i l l become blocked u n t i l completion of the operation. Of course for operations that are not interrupt driven {e.g. the reading of a r e a l time clock), the process need not block. Ideally, t h i s blocking mechanism would u t i l i t i z e the existing message passing f a c i l i t i e s . Since the structure of the high l e v e l I/O mechanisms i s exactly what one i s writing in WISCH, they must also be l e f t undefined. WISCH Beport J. Loading and running programs dynamically 89 J-, Loading and running programs dynamically The design of a "complete" language suitable for writing " r e a l " operating systems i s complicated by a d i f f i c u l t issue not found in "normal" language design. An operating system must be able to dynamically lead an arbit r a r y program int o main memory and then execute that program. The new program must be able to communicate with the system, preferably i n a well-controlled, secure manner. Unfortunately, t h i s issue i s only partly resolved in WISCH. It i s suggested that an implementation provide a standard procedure, LOAD, which accepts two main arguments: a VAB parameter which i s a pointer to a program and • a pointer to a procedure. LOAD w i l l acquire a suitable amount of memory (the amount may be another parameter) and w i l l c a l l the routine passed to i t to do the actual loading. (This procedure should have a large ABBAY OF ST08AGE as a VAB parameter.) LOAD w i l l set up any necessary descriptor information and make the program pointer refer to the newly loaded program. Processes may then be created from t h i s program just l i k e any other. WISCH Report K. Ifflplementatio . i l of WISCH 90 K. Implementation of WISCH A major aspect of th i s research has been the actual implementation of most of the language. Due to the si z e of the project, the implementation e f f o r t has so far been r e s t r i c t e d to the sequential parts of the language. Except for the multi-programming features, the only major unimplemented items are array and record l i t e r a l s , dynamic subranges and the OPTION statement. Several other areas are incompletely implemented as of this writing, notably many of the standard routines, s t r i n g operations, the FORK statement, the BIND statement, modules, most run-time checking and "code" pointers. The bulk of the implementation i s the compiler, which produces object modules for the ASP machine (described i n PART II of t h i s t h e s i s ) . The compiler i s written in PASCAL and runs under MTS on the university*s AMDAHL 470. The ASP l i n k e r i s used to l i n k the load modules and translate them into a form suitable for f i n a l loading on the Hewlett-Packard 21 MX minicomputer owned by the department of Computer Science. The WISCH program may then be run using the ASP machine under the RTE-2 operating system on the 21UX. Thus, WISCH i s currently implemented as a cross-compiled, seguential high-level language. The compiler consists of three passes and i s somewhat modelled after the Concurrent PASCAL and Sequential PASCAL compilers £ HAR 77]. The f i r s t pass performs l e x i c a l analysis WISCH Report K„ Implementation of WISCH 91 and parsing, using a hand-coded recursive descent parser. I t generates an intermediate code f i l e containing a postfix representation of the parse tree. Pass two i s the heart of the compiler. I t builds the block structured symbol table, performs declaration analysis, evaluates l i t e r a l expressions and generates code for statements. I t i s organized as a push-down automaton, transforming the postfix output from pass one into a "tokenized" assembly language f o r pass three. Pass three i s r e l a t i v e l y small; i t i s e s s e n t i a l l y assembler accepting the tokenized output from pass two and generating load modules for the ASP l i n k e r . Each routine i s output as a separate load module. These modules contain not just the name of the routine, but also i t s path name i n the program tree. The compiler allows separate compilation of i n d i v i d u a l routines and the replacement of a load module i s a simple task. (This must currently be done by manual editing, but a program to do i t would be guite simple.) External routines must be i d e n t i f i e d by name and location i n the program tree. The linker builds a tree-structured load map as i t l i n k s things together. Two routines with the same name are no problem at a l l (provided they are not s i b l i n g s ) . L. Future work with WISCH 92 Although i t i s intended to be a useable tool, WISCH i s s t i l l a research vehicle. There are several interesting areas a r i s i n g out of the language yet to be investigated. The compiler i s well structured and reasonably well documented so completing the implementation or modifying the language i s a fe a s i b l e task. Much of the language works at present, making evaluation of i t s current design also f e a s i b l e . Some of these possible areas of future development are; 1. Completion of the implementation of the concurrency features. There are several i n t e r e s t i n g questions involved here, p a r t i c u l a r l y involving how to organize the process control and message passing f a c i l i t i e s . There are many chioces of how to p a r t i t i o n physical memory, how to provided the shared memory for pools, etc. 2. Investigate the actual usefulness of the language, p a r t i c u l a r l y i n applications that have not t r a d i t i o n a l l y used multiprocessing. Evaluation of the sequential aspects of the language, especially the control structures and modules, could be attempted at t h i s time. Evaluation of the concurrent parts depends on completion of them, but could be an exciting area. 3. Examine solutions to some problems faced by a l l "systems programming" languages. One such issue i s how to provide an a b i l i t y to c a l l procedures with varying numbers of parameters without abandoning the " p r o t e c t i o n i s t " philosophy of the language. Another i s how to handle type escapes; WISCH WISCH Eeport L. Future work with WISCH WISCH Report L. Future work with WISCH 93 currently defines one approach but there are c e r t a i n l y others. The combination of these two i s also i n t e r e s t i n g , i t i s the problem faced when one t r i e s to write routines such as PASCAL'S BEAD and WRITE without having them b u i l t into the compiler. 4 . Use the language as a base for further language development. The current design and implementation could provide a good basis for other experiments i n language design. It i s hoped that people w i l l f e e l free to modify the language at w i l l . The ASP machine M. Introduction to ASP 94 fl. Introd uction to ASP The primary motivation .for the design and implementatioa of the programming language WISCH was to provide a suit a b l e high-level language for systems programming on the department of Computer Science's Hewlett-Packard 2 1 M X microprogramable minicomputer. Since the architecture of the 21 MX i s less than pleasant, especially for the implementation of A l g o l - l i k e languages, i t was decided that WISCH would be implemented on a t o t a l l y d i f f e r e n t architecture, ignoring the standard 21 MX inst r u c t i o n set. The ASP machine (& Stack Processor) i s the resul t of t h i s design e f f o r t . Although designed as a vehicle for WISCH, ASP i s a su i t a b l e machine f o r many modern languages. I t has been microprogrammed to run on an HP 2 1 M X , E-series computer. It i s not a v i r t u a l or abstract machine, i t i s every b i t as r e a l as the standard 2 1 M X or any other microprogrammed computer. Because of thi s commitment to r e a l i t y , performance constraints and the nature of the underlying hardware have forced compromises into the design. ASP i s not claimed to be an "optimal" machine i n any sense. I t i s however a viable architecture, offering easy to generate code, very compact code and reasonable speed. The ASP machine N. Basic structure of ASP 95 I i i Basic structure of ASP The machine has a f a i r l y normal stack oriented architecture. Conceptually, memory i s divided into three d i s t i n c t areas, the program, the stack, and the heap. The program area contains the re-entrant program code plus large constants. At any instant, the stack contains a stack frame for each currently activated routine. Stack a l l o c a t i o n of variables and recursive routines are the normal mode of operation. The heap i s used for dynamic a l l o c a t i o n of space under e x p l i c i t program co n t r o l . A l l memory i s composed of 16 b i t words and i s word addressed. The rightmost (least s i g n i f i c a n t ) b i t of a word i s b i t 0. An early version of the machine used byte addressing, but this caused serious performance problems (because of the hardware of 21MX). Some of the terminology used i n the rest of t h i s document i s a carry over from t h i s version and deals with (8 bit) bytes. But unless otherwise mentioned, a l l si z e s , o f f s e t s and addresses i n the sequel are i n words. Integer arithmetic i s two's complement. The exact format of reals i s currently undefined, but they are tentatively planned to use 6 bytes of memory. Strings are stored as a one word (current) length followed by "max-length" bytes for the characters in the st r i n g . Sets are simply a seguence of words, 16 elements per word. Arrays are just a sequence of elements stored in lexicographic order. The array subscripting i n s t r u c t i o n The ASP machine N. Basic structure of ASP 96 requires a descriptor, but this may be located anywhere in memory and need not be linked to the array. Physical memory i s organized as follows: (high address) heap (grows down) <— stack l i m i t <— workspace top workspace (grows up) variables parameters linkage area <— current stack frame function value ( i f appropriate) e a r l i e r stack frames global stack frame <— stack base program area (low address) The code f o r a routine consists of a "prologue" area followed by the actual body of the routine. The prologue contains; offset contents 0 s i z e of parameter and linkage area 1 size of variable area 2 maximum amount of workspace needed 3 siz e of "constant" area 4-n 11 constant" area (large l i t e r a l s ) The f i r s t four words must always be present. The constant area may be empty, but by convention the f i r s t part of i t should be a str i n g l i t e r a l giving the name of the routine. The linkage area The ASP machine N. Basic structure of ASP 97 for each stack frame i s a six word area composed of: offset contents 0 s t a t i c l ink 1 entry point of current routine 2 dynamic link 3 return address 4 index r e g i s t e r save 5 address of l a s t stack word needed {end of variables and maximum workspace) The global {bottom-most) stack frame i s a sp e c i a l case. I t s must begin with a nine word area organized as follows; of f s e t contents 0 address of f i r s t word i n the stack {a pointer to i t s e l f ) 1 main entry point of the program 2 address of HP save area 3 address of ASP save area 4 entry point of interrupt interface 5 address of l a s t stack word needed by main program 6 address of highest word available for stack or heap 7 error code mask 8 i n s t r u c t i o n that caused the error The use of these words i s explained in the section dealing with the actual implementation of ASP. The machine has eight i n t e r n a l registers., Normally, only the index register i s dealt with d i r e c t l y , the others are used i m p l i c i t l y . There are i n s t r u c t i o n s , however, to load or store any of them d i r e c t l y {intended to be used only by debugging and error handling routines). The registers are: PC - program counter PS - program status SB - stack base pointer SF - stack frame pointer HP - workspace top pointer SL - stack l i m i t pointer IR - index register CI - current in s t r u c t i o n The ASP machine N. Basic structure of 4SP 98 The program status register i s as organized as; xxxx xxxx EE EE SCCC The "x" b i t s are currently unused- The "E" b i t s are the machine error status. Normally they are zero, but i f a f a t a l error occurs, they are set to a code to i d e n t i f y the error. The "S" b i t i s for a planned single-step mode. The "C" bits are the comparison condition code. They are set by compare ins t r u c t i o n s and tested by conditional branch in s t r u c t i o n s . The program counter contains the address of the next i n s t r u c t i o n to be executed. The stack . base regi s t e r contains the address of the f i r s t word in the global stack frame. I t allows rapid access to global variables. The stack frame register contains the address of the f i r s t word of the current stack frame. The workspace top register contains the address of the top word currently in the workspace. The stack l i m i t r e g i s t e r contains the address of the l a s t word available for the stack. I t defines the boundary between the heap and the stack, so i t changes as the heap grows and shrinks- The index register may be used i n operand addressing and loop c o n t r o l . The current i n s t r u c t i o n register contains the f i r s t word of the current i n s t r u c t i o n . In the event of a f a t a l error, i t s contents are stored at offset 8 i n the global stack frame. The machine currently recognizes 1 1 error states. These states and t h e i r associated codes are: 0 - no error 1 - i l l e g a l i n s t r u c t i o n 2 - stack overflow 3 - heap overflow 4 - integer arithmetic error 5 - r e a l arithmetic error 6 - (unused) The ASP machine N. Basic structure of ASP 99 7 - subscript out of range 8 - range check f a i l u r e 9 - (unused) 10 - s t r i n g operation error 11 - assertion f a i l u r e (used with the "suicide" instruction) 12 - FOfiK jump error (used with the "suicide" instruction) Almost a l l expression evaluation i s done using only the workspace for temporary storage. The exceptions are the s t r i n g and set operations which must use stack or program space set aside for temporaries. A l l workspace operands are 1, 2, 3 or 4 words long. Commonly used dyadic operators have a one address form. The f i r s t operand i s taken from the top of the workspace, the second i s the addressed operand and the r e s u l t i s placed back on the workspace. (Comparison operations do not return a value to the workspace, they simply set the comparison condition code.) A few common monadic operations are also provided in a one address form. Less commonly used operations are provided in a zero address form with a l l operands taken from the workspace. The ASP machine 0. Design rationale 100 0. Design rationale The stack orientation with expression evaluation on the workspace was chosen over a register orientation f o r s i m p l i c i t y of code generation and code compaction. Register machines are more f l e x i b l e and potentially f a s t e r , but are considerably more d i f f i c u l t to generate code for and the r e s u l t i n g code almost cert a i n l y w i l l be larger. The mixture of one address and zero address operations was selected over a pure zero address machine for space and time savings. Consider the evaluation of an expression with n variables (n-1 operators). The zero address machine w i l l require n LOAD ins t r u c t i o n s and n-1 zero address operations. The one address machine w i l l require at most n/2 LOAD'S, n/2 one address operations and (n/2)-1 zero address operations (many intermediate r e s u l t s ) . (The expressions A+B+C+D and (A + B)*(C+D) i l l u s t r a t e these two extremes.) To provide some numbers, assume that LOAD'S and one address operations are 16 b i t s long and zero address operations are 8. Tabulating the above r e s u l t s : •The ASP machine 0- Design rationale 101 zero addr. 2n - 1 24n - 8 best one addr. worst one addr. 1.5n - 1 20n - 8 # of i n s t r . # of b i t s n 16n For various values of n the following r a t i o s of zero address to one address are obtained: n best worst best worst 2 1. 50 1.50 1.25 1.25 3 1.67 1.43 1-33 1.23 4 1.75 1.40 1.38 1-22 5 1.80 1.38 1-40 1.22 l i m i t 2.00 1.33 1.50 1-20 Further improvements may be realized through an encoding scheme as suggested by Tannenbaum £TAN 78J. However, such schemes reguire cheap byte addressing to perform well, which i s d e f i n i t e l y not the case for the hardware that ASP must deal with- A l l ASP in s t r u c t i o n lengths are multiples of 16 b i t s (so the worst case size above becomes 24n-16). An "optimal" machine should also be designed after an analysis of actual programs i n the languages that the machine i s to support, c l e a r l y a d i f f i c u l t task with WISCH. # of i n s t r . # of b i t s . The ASP machine P. Instruction repertoire 102 P_ Instruction repertoire In the" instruction descriptions that follow, classes of i n s t r u c t i o n s are defined and described. The names attached to these classes are simply l a b e l s , they are not meant to be d e f i n i t i o n s . For example, the "Program Relative Instructions" are r e a l l y a form of one address i n s t r u c t i o n , but are d i f f e r e n t i n structure from the "One Address Instructions". Following each c l a s s description i s a l i s t of the i n s t r u c t i o n s i n that class- This l i s t gives a short description of the i n s t r u c t i o n and the basic hexadecimal value of the f i r s t word of i t ( i e . showing the opcode). P-1. One address instructions These a l l have both one and two word forms. The f i r s t byte of the i n s t r u c t i o n i s always; CCCC CCSG where "CCCC CC" i s the "opcode", "S" gives the i n s t r u c t i o n s i z e (0 i s one word) and "G" selects addressing r e l a t i v e to the current or global stack frame (0 i s current). For the one word form, byte 2 i s : IXOO 0000 where " I " selects i n d i r e c t addressing (0 i s d i r e c t ) , "X" s e l e c t s indexed addressing (0 i s non-indexed) and "00 0000" i s the o f f s e t (a value from 0 to 63). For the two word form, byte two i s ; The ASP machine P. Instruction repertoire 103 I X — LLLL where " I " and "X" are as above and "LLLL" s e l e c t s the r e l a t i v e s t a t i c l e v e l (0 i s l o c a l , 1 i s the "father", 2 the "grandfather", e t c . ) . If the "G" b i t of byte 1 i s set the "LLLL" b i t s are ignored. The second word in the two word form i s the offset as a 16 b i t signed integer {ie. i t can be negative). Indirection i s single l e v e l and occurs before indexing. 0000 1000 2000 3000 4000 5000 6000 7000 8000 900 0 A000 B000 C000 D000 E0O0 PQQ0 0400 1400 2400 3400 4400 5400 6400 7400 8400 9400 A4Q0 B400 C400 D400 E400 F400 0800 180 0 2800 3800 4800 load 2 bytes to top of the workspace II n it ii it 4 6 8 ii ti ti II II ti II II ii ii it II ti i i ti it the upper byte of a word (as a value from 0 to 255) store ti ii n zero lower " " " " " " " " " " index register e f f e c t i v e address to top of the workspace bytes from the top of the workspace (pop work) ii it ti ti it ii ii II it it II it ti II it it n II to the upper byte of a word II II lower " " " " the index register a word in the stack ti - II it IJ II ii it it i i i i II increment " decrement " compare stack operand with zero (opnd r e l zero) compare index register with stack operand integer add stack operand to workspace top " subtract stack operand from workspace top " multiply workspace top by stack operand " divide " " " " " " compare workspace top with stack operand bitwise AND stack operand to workspace top II OE " " " " " r e a l add stack operand to workspace top subtract stack operand from workspace top multiply workspace top by stack operand divide " " " " " compare workspace top with stack operand save 2 bytes from workspace to stack (no pop) H it ti it it n it it «i it ii it II ii it i t II II i t n II II n 6 Q II II II It to the upper byte of a word The ASP machine P. Instruction repertoire 104 5800 " " " lower " " " " __2_ Immediate operand in s t r u c t i o n s These also have one and two word forms. The f i r s t byte i s always; CCCC 10S-where "CCCC" i s the opcode and "S" gives the i n s t r u c t i o n s i z e as before. For the 1 word form the lower 9 b i t s of the word are the operand, treated as a 9 bit signed integer (-256 to +255). For the two word form the second word contains the value as a 1 6 b i t signed integer while the lower 9 b i t s of the f i r s t word are ignored. 6800 load immediate t G top of workspace 7800 " " " index r e g i s t e r 8800 add " " " " 9800 " " " top of workspace A800 multiply top of workspace by immediate 8800 divide " " » " " C800 bitwise AND immediate to top of workspace D800 " OE " " " " " E8Q0 compare index register with immediate F800 compare top of workspace with immediate The ASP machine P. Instruction repertoire 105 P.3. Jump in s t r u c t i o n s The jump instructions a l l use addressing r e l a t i v e to the f i r s t word past the jump i t s e l f - They have both one and two word forms. The f i r s t byte i s always: SXXX 110-where "XXX" i s the opcode and "S" i s the inst r u c t i o n s i z e . For the one word form the lower 9 b i t s are treated as a 9 bit signed integer (-256 to +255). For the two word form the lower 9 b i t s of the f i r s t word are ignored; the second word contains the jump off s e t as a 16 b i t signed integer. Thus, for a one word jump an of f s e t of -1 i s an i n f i n i t e loop, while f o r a two word jump an of f s e t of -2 gives an i n f i n i t e loop. 0C00 jump unconditionally 1C00 " on equal 2C00 " " greater 3C00 " " greater or equal 4C0 0 « " l e s s 5C00 " " less or equal 6C00 " " not equal (less or greater) 7C00 » via FOBK table The FOBK jump needs further explanation. I t adds the jump offset to the top of the workspace (which i s then popped) and then to the program counter. This value at the location thus referenced i s then added in to give the f i n a l jump address. In higher l e v e l terms, the jump o f f s e t i s the offset to a branch table. The top of the workspace contains an index into t h i s t a b l e . The table entries are of f s e t s from themselves to a f i n a l destination. \ The ASP machine P. Instruction repertoire 106 P. 4. Prog rani r e l a t i v e instructions These instructions use addressing r e l a t i v e to the entry point of a routine instead of r e l a t i v e to a stack frame. Their primary intent i s to provide a simple access mechanism to large constants stored in the program area. They have both one and two word forms. The f i r s t byte i s always; SCCC 1110 where "CCC" i s the opcode and "S" gives the i n s t r u c t i o n s i z e . The rest of the i n s t r u c t i o n i s i d e n t i c a l to the one address in s t r u c t i o n s . 0E0 0 load 2 bytes from the program area 1E0 0 '» 6 " " " " " 2E00 " the e f f e c t i v e address 3E00 r e a l add program operand to top of workspace 4E00 " subtract program operand from top of workspace 5E00 " multiply tcp of workspace by program operand 6E0 0 " divide " " " " " " 7E00 " compare " » " to " " P.5, Memory block i n s t r u c t i o n s These are instructions which deal with contiguous "chunks" of memory. Except for the workspace pointer increment, they a l l reguire two absolute addresses on the top of the workspace. A l l of them have both one and two word forms. The f i r s t byte i s always: CCCS 1111 where "CCC" i s the opcode and "S" i s the i n s t r u c t i o n s i z e . For The ASP machine P. Instruction repertoire 107 the. one word case, the second byte i s the operand length in words as a value from 0 to 255. For the two word case the bottom b i t of the f i r s t word s e l e c t s a "dynamic" mode. I f i t i s cle a r , the second word contains the operand length as a signed 16 b i t integer. Obviously, negative values are nonsense for a l l but the workspace pointer increment i n s t r u c t i o n . I f b i t 0 i s set, the second word of the i n s t r u c t i o n i s omitted and the length i s taken from the top of the workspace (above the addresses). 0F00 increment the workspace pointer r e g i s t e r by the operand length; no addresses are used 2F0 0 compare words as integers; the top address i s the r i g h t comparand, the bottom address i s the l e f t one; the comparison stops at the f i r s t pair of d i f f e r i n g words 4FO0 move a block of words; the top address i s the "to" address and the bottom i s the "from" address; the move goes from low address to high address 6F00 swap two blocks of words; the swap goes from low address to high address P.6. Zero address load, store & save These instructions are zero address analogues of the one address instructions described above. They are a l l one word long. The bottom two b i t s of the word are " I " and "X" b i t s as for the one address in s t r u c t i o n s (bit 1 i s " I " and b i t 0 i s "X"). load 2 bytes to top of the workspace II n ii ii ii II ii ii ii 5 II it it II ii it ti 3 it ii it ii it it " the upper byte of a word (as a value from 0 to 255) ti it i n w r » " « 1 1 " •« « n « 11 8F00 8F10 8F20 8F30 8F4 0 8F50 The ASP machine P. Instruction repertoire 108 8 F 6 0 store 2 bytes from the top of the workspace (pop work) 8 P 7 0 11 H i t i t t i i t II i i II •t H 8 F 8 G II g i t t i i t t i II t i II » i t 8 F 9 0 II g n t i t i t i i t i t •• i t t i 8 F A 0 II to the upper byte of a word i i t i 8 F B 0 i t " » lower " " " " t i i i 8 F C 0 save 2 bytes from workspace to stack (no pop) 8 F D 0 «i 4 i i i t n i t i t i t n 8 F E 0 i i £ 11 11 It 11 11 II i i 8 F F 0 II g i t i i t i II i t II t i 9 F 0 0 i t to the upper byte of a word 9 F 1 0 i t " " lower " •'• " " 9 F 2 0 t i e f f e c t i v e address to top of the workspace P.7. Machine register access This group of instructions allows the workspace top to be loaded from or stored to any of the eight machine registers. To keep the terminology consistent with the other i n s t r u c t i o n descriptions, note that the word "load" means to transfer a value from a regi s t e r to the top of the workspace and the word store means to transfer a value from the top of the workspace to a r e g i s t e r . Except f o r the index r e g i s t e r transfers, these i n s t r u c t i o n s are provided f o r test and debugging purposes. They are not intended for general use. A l l are one word long. 9F3 0 store to the status r e g i s t e r 9F31 i t i i i t program counter 9F32 II II t i stack iaase pointer 9F33 t i tt tt stack frame pointer 9F34 i t n i i workspace top pointer 9F35 i t i t i t stack l i m i t pointer 9F36 i t n i t index r e g i s t e r 9F37 i t 41 t i current instruction register 9F38 load from the status r e g i s t e r 9F39 • i tt t i program counter 9F3A i t i t t i stack base pointer 9F3B i t tt i t stack frame pointer 9F3C n i i t i workspace pointer The ASP machine P. Instruction repertoire 109 .9*3 D II II i t stac 9F3E II i t i i inde 9P.3F t i 11 II curr k l i m i t pointer x register ent i n s t r u c t i o n register P.8- Shif t i n s t r u c t i o n s These three insructions operate on the workspace top and have the s h i f t count and d i r e c t i o n encoded in the i n s t r u c t i o n . The d i r e c t i o n i s i n b i t 4 , 0 i s l e f t and 1 i s r i g h t . The bottom four b i t s have the s h i f t count as a value from 0 to 1 5 . 9 F 4 0 l o g i c a l s h i f t (end-off, z e r o - f i l l ) 9 F 6 0 arithmetic s h i f t 9 F 8 0 rotation P-.9 __ lord operations These instructions are the zero address operations for single word operands. They are a l l one word long. The s h i f t i n s t r u c t i o n s presented here have the count on the workspace above the value to be s h i f t e d . a positive count indicates a l e f t s h i f t , a negative count i s a r i g h t s h i f t . If the absolute value of the count i s larger than 16 i t i s assumed that 16 i s meant. 9 F A 0 integer addition 9 F A 1 " subtraction 9 F a 2 " multiplication 9 F A 3 " d i v i s i o n 9 F A 4 " modulus (see the HISCH report f o r the) 9 F A 5 11 remainder (difference between these two) 9 F a 6 " absolute value The ASP machine P. Instruction repertoire 110 9FA7 " negation 9FA8 " comparison (pop both operands) 9FA9 " comparison (pop only the l e f t operand) 9 3? A A bitwise AND 9FAB " i n c l u s i v e OR 9FA " exclusive OR 9FAD " complement 9FAE " l o g i c a l s h i f t 9FAF 11 arithmetic s h i f t 9FB0 »' rotation P.10- Real operations Although t h e i r format i s undefined, opcodes a have been allocated f o r zero address instructions to operate on r e a l values. They are a l l one word long. 9FC0 r e a l addition 9FC " subtraction 9FC " mu l t i p l i c a t i o n 9FC " d i v i s i o n 9FC " absolute value 9FC " negation 9FC " compare 9FC " convert integer to r e a l 9FC " " r e a l to integer _____ instructions There are many other miscellaneous instructions i n the ASP machine repertoire. They are collected together here and given i n d i v i d u a l descriptions below. 9FF0 array subscripting This i n s t r u c t i o n i s one word long. The bottom four b i t s The &SP machine P. Instruction repertoire 111 are "CDDD", where "C" i s a checking b i t and "DDD" i s the number of dimensions in the array l e s s one. If the "C" b i t i s set each index i s checked to make sure that i t i s within i t s proper range, no checking at a l l i s done i f i t i s c l e ar. This i n s t r u c t i o n reguires n+2 arguments on the workspace for an n dimensional array. The top of the workspace must be a pointer to a descriptor block. This block contains 2n+1 words. The f i r s t n pairs are the lower bound and range (upper-lower*1) f o r each dimension. The lower bound i s the f i r s t word in the pair. The l a s t word in the descriptor i s the size of a single array element. The next n elements of the workspace must be the array i n d i c e s , with the n*th on top. The bottom argument i s the address of the s t a r t of the array- The instruction, leaves the address of the selected element on the top of the workspace. &F00 normal routine c a l l This i n s t r u c t i o n i s two words long. The bottom four b i t s of the f i r s t word give the r e l a t i v e s t a t i c l e v e l of the c a l l e d routine, 0 i s a son of the c a l l e r , 1 i s a brother, 15 i s a "global" l e v e l routine. The second word of the i n s t r u c t i o n i s the absolute address of the routine entry. This i n s t r u c t i o n assumes that a l l parameters (including the 6 word linkage area) are on the workspace- I t uses the word at o f f s e t 0 of the routine prologue to decide how far the st a r t of the new stack frame should be below the current top of the workspace. The workspace pointer i s The ASP machine P. Instruction repertoire 112 then incremented by the size of the variable area and a check i s made to make sure that there i s enough workspace for the routine. AP10 routine return This i n s t r u c t i o n i s one word long. I t simply causes a return from the current routine. AF20 dynamic routine c a l l This i n s t r u c t i o n i s one word long. I t s bottom four b i t s contain the r e l a t i v e l e v e l of the c a l l e d routine as defined above. The entry point of the c a l l e d routine i s on the top of the workspace instead of i n l i n e i n the program space. AF30 duplicate top of workspace This one word instruction duplicates values on the top of the workspace. I t s bottom two b i t s contain the number of words to duplicate less one. AF80 range check This i n s t r u c t i o n checks that the top word of the workspace (treated as a signed integer) i s within a spec i f i e d range, causing a f a t a l error i f i t i s n ' t . I t does not pop the value being cheked. The inst r u c t i o n has one, two and three word forms. I t s bottom four b i t s are "xxCC", where "SS" selects the s i z e . Opcode AF8Q i s a two word i n s t r u c t i o n , the second word containing the range bounds. Both bounds must be between 0 and 255. The upper byte of the second word i s the upper bound, the lower byte i s the lower bound. Opcode AF81 i s a three word i n s t r u c t i o n . The ASP machine P. Instruction repertoire 113 The second word i s the lower bound and the' third i s the upper. Both bounds are treated as 16 b i t signed integers. Opcode AF83 i s a one word i n s t r u c t i o n , the bound are on the workspace. The top value i s the upper bound, the next i s the lower. AF4Q f u l l exit from ASP This one word i n s t r u c t i o n requires two arguments on the workspace. The top must be a pointer to an 8 word save area f o r the ASP i n t e r n a l r e g i s t e r s . The next must be a pointer to a 4 word save area for the HP registers P, S, X, and Y- F i r s t the ASP registers PC, PS, SB, SF, HP, SL, IR and CI are stored in the ASP save area. Next the HP registers are loaded from th e i r save area. F i n a l l y the HP A r e g i s t e r i s loaded with the pointer to the ASP save area, the B with the HP pointer and control i s returned to the HP i n s t r u c t i o n set. AF50 i n l i n e e x i t from ASP This i n s t r u c t i o n i s one word long. It allows ASP and HP in s t r u c t i o n s to be intermingled i n a single routine. I t pushes the ASP registers SL and IR on the workspace (IR on top), puts the ASP PS into the HP A, the ASP WP into the HP B (actually B points to SL, i e . i t i s WP-1), the ASB SB into the HP Y and the ASP SF int o the HP X. I t then simply e x i t s to the HP i n s t r u c t i o n interpreter so that i t w i l l begin execution of the next i n s t r u c t i o n i n seguence. , AF6 0 suicide exit from ASP The one word suicide i n s t r u c t i o n i s intended to be used The ASP machine P. Instruction repertoire 114 for debugging and to programably cause f a t a l errors- I t s bottom four b i t s are placed i n the "EEEE" b i t s of the PS register and an error e x i t from ASP i s made. AF70 interrupt e x i t from ASP This i s a one word in s t r u c t i o n , provided to allow testing of the ASP-HP interrupt i n t e r f a c e . The function of t h i s i n t e r f a c e i s described below i n the section on the implementation of ASP. The ASP machine Q. Implementation of ASP 115 Q. Implementation of ASP As mentioned previously, the ASP machine has been implemented as a microprogram f o r a Hewlett-Packard 21MX E-series computer. It allows ASP programs to be run under the BTE-2 operating system. To s t a r t an ASP program the machine must be loaded into the HP*s WCS memory, the base of the global stack frame must be set up and the ASP registers must be given i n i t i a l values. Words 0 and 1 of the global stack frame are s e l f explanatory. Words 2 and 3 are l e f t alone. Word 4 points to the s t a r t of an interrupt interface routine. The structure of t h i s routine i s described below. Word 5 l a s the same purpose as word 5 of a normal routine frame; i t i s used for checking f o r stack overflow. Word 6 i s also s e l f explanatory, the i n i t i a l value of the SL register should be the same. Word 7 i s a b i t mask for f a t a l errors that are to be ignored. Bit i masks out error code i . Word 8 i s l e f t alone. An 8 word save area must be set up with the i n i t i a l values for the ASP registers PC, PS, SB, SF, WP, SL, IB, and CI. The HP A register i s loaded with the address of t h i s save area and the HP B reg i s t e r with the address of a 4 word HP save area. This HP save area w i l l get the values of the HP registers P, S, X and Y when ASP i s started. Execution of the HP i n s t r u c t i o n with octal code 101611 w i l l then cause the ASP machine to be started. The save area pointers w i l l be stored i n global locations 2 and 3 automatically. If a The ASP machine Q. Implementation of ASP 116 f a t a l error i s deteced by ASP, a f u l l e x i t i s done automatically using these save areas. Since ASP has no I/O ins t r u c t i o n s i t i s necessary to be able to e x i t to the HP inst r u c t i o n set to perform I/O and then to re-enter ASP. Control must also be automatically surrendered to the HP i n s t r u c t i o n set whenever an interrupt i s detected. The former c a p a b i l i t y i s provided by the i n l i n e e x i t and entry ins t r u c t i o n s . The ASP i n l i n e exit l e t s routines be schizophrenic and i s described above. The HP ins t r u c t i o n with octal code 101612 accomplishes the inverse operation. When an interrupt request i s detected while ASP i s running, a s p e c i a l quick e x i t i s made to the HP i n s t r u c t i o n set to allow i t to be handled. The PS, SL and IB r e g i s t e r s are pushed onto the workspace (IB on top)', the PC i s put into the HP A reg i s t e r and UP into the HP B regis t e r (B actually points to the PS value, i e . i t i s SP-2). The ASP SF and SB registers happen to be the same hardware registers as the HP X and Y, so they are l e f t alone. The HP P register i s then loaded with the interrupt entry point and control i s given to the HP i n s t r u c t i o n set. T y p i c a l l y , the interface routine i s just a few HP NOP instructions (to allow the interrupt to be caught) followed by an interrupt return to ASP, HP i n s t r u c t i o n 101613. The ASP machine B. Future work with ASP 117 l i Future work with ASP Like WISCH, ASP i s both a working tool and a research vehicle. There are two main areas of future work with ASP that seem well suited to M.Sc. research. An excellent project would be to take the ASP machine and revise and polish i t into a better kernel machine for a variety of languages, especially languages of l o c a l i n t e r e s t to UBC such as BCPL, C, PASCAL and ZED. Properly designed, i t could even allow i n t e r - l i n g u a l routine c a l l s with no overhead. This project could benefit from the large body of existing programs in these languages to analyze what language features are actually used. This new machine could also be extended to contain i n s t r u c t i o n s forl/O and memory management, making i t a " r e a l " computer i n the f u l l e s t sense. Such a project would place the design of computer architecture where i t r e a l l y belongs, subservient to the acutal needs of programmers. The machine produced would l i k e l y be of considerable p r a c t i c a l value. Another project, which f i t s well with the f i r s t , would be to study how to best provide more sophisticated, language s p e c i f i c i n s t r u c t i o n s . For WISCH t h i s might include i n s t r u c t i o n s for s t r i n g manipulation, set operations, heap maintainance, message passing and process c o n t r o l . These instructions could be designed as optional extentions to the The ASP machine B. Future work with ASP 118 kernel machine mentioned above. Bibliography 119 1- Atwood, J. ». , et- a l - Project SUE status report- Technical report CSRG-11, Computer Systems lesearch Group, University of Toronto (April 1972). 2- Brinch Hansen, P. Structured multiprogramming. Communications of the ACM, Vol. 15, No. 7 (July 1972), pp. 574-578. 3. Brinch Hansen, P. The programming language Concurrent Pascal. IEEE Transactions on Software Engineering. Vol. 1, No. 2 (June 1975), pp. 199-207. 4. Brinch Hansen, P. Experience with modular concurrent programming. IEEE Transactions on Software Engineering, Vol. SE-3, No. 2 (March 1977), pp. ,156-159. Corbato, F. J. PL/1 as a tool f o r system programming. Datamation, Vol. 15, No. 5 (May 1969) , pp. €8-76. 5. Hart ma nn, A. A Concurrent Pascal Compiler f o r Minicomputers. Springer-Verlag, B e r l i n , (1977). 6. Hoare, C. A. R. Towards a theory of p a r a l l e l programming. Operating Systems Techniques, ed. C. A- R. Hoare and R. H. Perrot. Academic Press, New York (1972). 7. Hoare, C. A. R. Monitors: An operating system structuring concept. Communications of the ACM, Vol. 17, No. 10 (October 197 4), pp. 549-557. 8. Hoare, C. A. R. P a r a l l e l Programming: An axiomatic approach. Computer Languages, V c l . 1 (1975) , pp. , 151-160. 9. Jensen, K. and Wirth, N. PASCAL User Manual and Report. Springer-Verlag, B e r l i n (1974). 10. Kahn, K. A s m a l l - s c a l l operating system foundation for microprocessor applications. Proceedings of the IEEE, Vol. 6€>, No. 2 (February 1978), pp. 209-215.~ 11. Lampson, B. W., et. a l . Report on the programming language EUCLID. Sigplan Notices, Vol. 12, No. 2 (February 1977). 12. Liskov, B. The design of the Venus operating system. Communications of the ACM, Vol. 15, No. 3 (March 1972), pp. 144-149. 13. Ran d e l l , B., ed. The Origins of D i g i t a l Computers. Springer-Verlag, B e r l i n (1973). 14. Richard, F. and Ledgard, H. F. A reminder for language designers. Sigplan Notices, Vol- 12, No. 12 (December 1977), pp. 73-82. Bibliogra phy 120 15- Silberschatz, A., et- a l . Extending Concurrent Pascal to allow dynamic resource management. IEEE Transactions on Software Engineering, Vol. SE-3, No. 3 (May 1.977), pp. 210-217. 16. Sorensen, S. M. and Stanstrup, J. PLATON reference manual. Report R-75-58, Regional EDP Center, University of Aarhus (July 1975) . 17. Sorensen, S. M. and Stanstrup, J. PLATON - Design and implementation on RC 3500. Report RECAU-77-80-R, Regional EDP Center, University of Aarhus (May 1977). 18- Stanstrup, J . , and Sorensen, S. M. PLATON - A high l e v e l language for systems programming. Report R-75-59, l e g i o n a l EDP Center, University of Aariius (May 1975). 19. Stoy, J. E. and Strachey, C. OS6 - An experimental operating system for a small computer- Part 1; General p r i n c i p l e s and structure. Computer Journal, Vol- 15, No.2 (April 1972), pp. 117-124. 20. Tannenbaum, A. Implications of structured programming ;for machine architecture. Communications of the ACM, Vol. 21, No. 3 (March 1978), pp. 2 37-246-21- Hhitaker, fl. A. The U- S. Department of Defense common high order language e f f o r t . Sigplan Notices, Vol. 13, No. 2 (February 1978) , pp. 19-29. 22. Wirth, N. MODULA: A language for modular multiprogramming. Eidgenossische Technische Hochschule, Zurich (March 1976). 23. Wirth, N. The use of MODULA and Design and implementation of MODULA. Eidgenossische Technische Hochschule, Zurich (July 1976) . 24. Yasumura, M. Evolution of loop statements. Sigplan Notices, Vol. 12, No. 9 (September 1977), pp. 124-129. Appendix 1. Why WISCH with a C? 121 The word WISCH comes from the name Wlhelm SCHickard, a German astromomer who b u i l t a cal c u l a t i n g machine i n the early 162G*s. Unfortunately the machine was destroyed by f i r e not long after i t was finished- Schickard died during the Plague and no copies of his machine were ever made. Evidence of i t s existence comes from a description and drawings sent to Johannes Kepler i n 1624 (at which time Blaise Pascal was one year o l d ) . 

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

Comment

Related Items