UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Operator identification in Algol 68 Kwan, Ying 1973

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

Full Text

\ i OPERATOR IDENTIFICATION IN ALGOL 68 by YING KWAN B.Sc. , Taiwan Normal U n i v e r s i t y , 1963 M.A., 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 , 1970 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n t h e Department o f COMPUTER SCIENCE We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1973 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the Head o f my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood t h a t c o p y i n g or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a llowed without my w r i t t e n p e r m i s s i o n . Department o f Covr^p^ttLr Science The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date i i ABSTRACT The s p e c i a l f e a t u r e t h a t modes and o p e r a t o r s c a n be d e f i n e d by t h e u s e r o f ALGOL 68 has i n d u c e d t h e p r o b l e m s o f c o e r c i o n , b a l a n c i n g and o p e r a t o r i d e n t i f i c a t i o n . T h i s work d e a l s w i t h t h e mode m a n i p u l a t i o n and o p e r a t o r i d e n t i f i c a t i o n i n ALGOL 68. The a l g o r i t h m s a r e based on t h o s e o f [ Z ] , Some o f t h e r e v i s i o n s t o t h e ALGOL 68 R e p o r t c o n c e r n i n g modes, s u c h a s no p r o c e d u r i n g , t h e v o i d s y m b o l , t h e d e f i n i t i o n o f NONPROC, t h e d e f i n i t i o n o f a vacuum, and t h e h i p p i n g o f a vacuum a r e i n c l u d e d . The program i n ALGOL W i s based on t h a t o f [ P ] . The program d e s c r i b e d i n t h i s t h e s i s does f o u r main j o b s : mode e g u i v a l e n c i n g , mode c o e r c i o n , mode b a l a n c i n g and o p e r a t o r i d e n t i f i c a t i o n . In mode e g u i v a l e n c i n g , i t c h e c k s t h e c o n t e x t c o n d i t i o n s c o n c e r n i n g " s h o w i n g " [ R . 4 . 4 . 4 ] and t h e m u l t i p l e o c c u r r e n c e o f t h e same f i e l d s e l e c t o r i n a s t r u c t u r e [ R . 4 . 4 . 3 e ] , and c h e c k s r e l a t e d modes i n u n i o n s [ B . 4 . 4 . 3 b , d ] . I n mode c o e r c i o n , i t d e t e r m i n e s t h e c o e r c i o n s t e p s . T h i s i s a l s o a b a s i c p a r t o f mode b a l a n c i n g and o p e r a t o r i d e n t i f i c a t i o n . In b a l a n c i n g , i t a l s o c o n s i d e r s c o l l a t e r a l d i s p l a y s . T h i s i s a model f o r t h e o p e r a t o r i d e n t i f i c a t i o n p a r t o f an ALGOL 68 c o m p i l e r . i i i ACKNOWLEDGEMENTS I am d e e p l y i n d e b t e d t o P r o f e s s o r J - E. L. Peck f o r i n i t i a t i n g my s t u d y o f ALGOL 68 and ALGOL W, f o r s u g g e s t i n g t h e t o p i c o f t h i s t h e s i s and f o r r e n d e r i n g i n v a l u a b l e a s s i s t a n c e , e n c o u r a g e m e n t and p a t i e n c e t h r o u g h o u t t h e c o u r s e o f my work. I would l i k e t o thank t h e g r o u p which i s w o r k i n g u n d e r Dr. Peck f o r t h e ALGOL 68 i m p l e m e n t a t i o n , Dr. W. J . Hansen and e s p e c i a l l y Dr. M. Z o s e l f o r many h e l p f u l s u g g e s t i o n s and d i s c u s s i o n s . I g r a t e f u l l y a c k n o w l e d g e t h e f i n a n c i a l s u p p o r t o f NRC. i v TABLE OF CONTENTS Page CHAPTER I : I n t r o d u c t i o n 1 CHAPTER I I : Mode R e p r e s e n t a t i o n 6 CHAPTER I I I : Mode E g u i v a l e n c i n g 14 CHAPTER IV : C o e r c i o n Of Modes 30 CHAPTER V : Mode B a l a n c i n g 46 CHAPTER V I : O p e r a t o r I d e n t i f i c a t i o n 64 CHAPTER V I I : C o n c l u d i n g Remarks 69 REFERENCES : 71 APPENDIX A: The Program And 72 How To Use I t 95 APPENDIX B: The R e v i s e d S y n t a x R u l e s 102 INTRODUCTION 1 CHAPTER I INTRODUCTION A v e r y i m p o r t a n t f a c t o r o f t h e power o f a g e n e r a l p u r p o s e l a n g u a g e i s t h e f a c i l i t y i n c o r p o r a t e d t o t r e a t t h e b i t s o f c o m p u t e r memory a s d i f f e r e n t d a t a t y p e s : b i t s , l o g i c a l v a l u e s , c h a r a c t e r s , i n t e g e r s , r e a l s , complex numbers, a r r a y s , s t r i n g s , l i s t s , t r e e s , e t c . Some programming l a n g u a g e s a l l o w t h e u s e r t o d e f i n e new d a t a t y p e s and t o e x t e n s i v e l y use t h e d e f i n e d d a t a t y p e s by: (1) u s i n g them i n f u r t h e r d e f i n i t i o n s , (2) u s i n g them as p a r a m e t e r s t o p r o c e d u r e s , (3) e x t e n d i n g t h e r a n g e o f e x i s t i n g o p e r a t o r s t o i n c l u d e them and (4) d e f i n e new o p e r a t o r s t o o p e r a t e on them. ALGOL 68 p e r m i t s t h e u s e r t o d e f i n e d a t a t y p e s termed modes, and a l l o w s t h e f o u r f e a t u r e s m e n t i o n e d . T h i s g e n e r a l i t y i n t h e l a n g u a g e p o s e s t h e f o l l o w i n g p r o b l e m s f o r t h e c o m p i l e r i m p l e m e n t o r : (1) when t h e r e a r e two modes r e p r e s e n t i n g t h e same d a t a t y p e ( e g u i v a l e n c i n g ) , (2) when and how a mode c a n be t r a n s f o r m e d t o a n o t h e r ( c o e r c i o n ) , (3) t c what mode s h o u l d e l e m e n t s o f a l i s t o f modes be c o e r c e d ( b a l a n c i n g ) and (4) - how t h e o p e r a t o r d e f i n i t i o n i n an a p p l i e d o c c u r r e n c e o f t h e o p e r a t o r i s d e t e r m i n e d ( o p e r a t o r i d e n t i f i c a t i o n ) . INTRODUCTION 2 Example ( 1 ) , r e a l x := 3; where t h e v a l u e p o s s e s s e d by 3 i s o f mode i n t e g r a l and t h e v a l u e which i s t o be a s s i g n e d must be o f mode r e a l . So t h e v a l u e o f mode r e a l which i s e q u i v a l e n t t o 3 must be d e r i v e d b e f o r e t h e a s s i g m e n t . The p r o c e s s o f t r a n s f o r m i n g i n t e g r a l t o r e a l i s a c o e r c i o n c a l l e d w i d e n i n g . E x a m p l e ( 2 ) f r e a l x,y; x:= x+y; i n t h e e x p r e s s i o n x+y, t h e o p e r a t o r i s + , t h e o p e r a n d s a r e x and y whi c h a r e o f mode r e f e r e n c e to r e a l . T h i s i s an a p p l i e d o c c u r r e n c e o f t h e o p e r a t o r •. The d e f i n i n g o c c u r r e n c e o f t h e o p e r a t o r + must be d e t e r m i n e d . I n t h e R e p o r t , t h e r e a r e a t l e a s t 16 d e f i n i n g o c c u r r e n c e s c f t h e o p e r a t o r + [R. 1 0 . 2 . 3 i , j , 1 0 . 2 . 4 i , j , 10.2.5a,b, 10.2.6b, 1 0 . 2 . 7 j , k , p , g , r , s , 1 0 . 2 . 1 0 j , k # l . ] . Among them, op + = ( L r e a l a,b) L r e a l : a — b ; [ R . 1 0 . 2 . 4 i ] i s the o n l y d e f i n i n g o c c u r r e n c e t o be i d e n t i f i e d by t h e f o r m u l a x+y. Coercion, i s t h e way t h r o u g h which one mode c a n be t r a n s f o r m e d t o a n o t h e r . O n l y COERCENDS c a n be c o e r c e d . T h e r e a r e f i v e d i f f e r e n t p o s i t i o n s f o r a COERCEND: s t r o n g , f i r m , meek, weak and s o f t . T h e r e a r e s e v e n d i f f e r e n t c o e r c i o n s : d e p r o c e d u r i n g , d e r e f e r e n c i n g , u n i t i n g , r o w i n g , w i d e n i n g , h i p p i n g and v o i d i n g . B a l a n c i n g o c c u r s i n a c o n d i t i o n a l c l a u s e , s e r i a l c l a u s e , t h e f i r m MODE b a l a n c e PACK i n a f i r m c o l l a t e r a l row o f MODE c l a u s e o r t h e s t r o n g s t r u c t u r e PACK i n a s t r o n g INTRODUCTION 3 c o l l a t e r a l s t r u c t u r e c l a u s e . T h e r e a r e a l s o f i v e p o s i t i o n s o f b a l a n c i n g . In a FEAT b a l a n c e , one o f t h e c o n s t i t u e n t CLAUSE must be FEAT, w h i l e t h e o t h e r may be s t r o n g . O p e r a t o r i d e n t i f i c a t i o n i s n e c e s s a r y when t h e r e i s more t h a n one d e f i n i n g o c c u r r e n c e o f an o p e r a t o r . I n o p e r a t o r -i d e n t i f i c a t i o n , t h e p o s i t i o n o f an o p e r a n d i s a l w a y s f i r m . In t h i s p r o c e s s o f mode m a n i p u l a t i o n and o p e r a t o r i d e n t i f i c a t i o n , t h e p r o b l e m o f d e t e r m i n i n g whether ( a j x j y ) ( i ) i s a s l i c e o r a c a l l c a n be s o l v e d when t h e (a p r i o r i ) modes o f x and y a r e g i v e n . T h i s work d e a l s w i t h t h e mode m a n i p u l a t i o n and o p e r a t o r i d e n t i f i c a t i o n i n ALGOL 68 w i t h t h e a l g o r i t h m s based on t h o s e o f [ Z ] . I t i s based on t h e r e v i s e d s y n t a x which i s g i v e n i n A p p e n d i x B so some o f t h e r e v i s i o n s t o t h e ALGOL 68 R e p o r t c o n c e r n i n g modes, s u c h as nc p r o c e d u r i n g , the v o i d s y m b o l , t h e d e f i n i t i o n o f NOS'PROC, t h e d e f i n i t i o n o f a vacuum, and t h e h i p p i n g o f a vacuum a r e i n c l u d e d . The program i n ALGOL W i s based on t h a t o f [ P ] . The program d e s c r i b e d i n t h i s t h e s i s d o e s f o u r main j o b s : mode e g u i v a l e n c i n g , mode c o e r c i o n , mode b a l a n c i n g and o p e r a t o r i d e n t i f i c a t i o n . I n mode e g u i v a l e n c i n g , i t c h e c k s t h e c o n t e x t c o n d i t i o n s c o n c e r n i n g " s h o w i n g " [ R . 4 . 4 , 4 ] and t h e m u l t i p l e o c c u r r e n c e o f t h e same f i e l d s e l e c t o r i n a s t r u c t u r e [ R . i 4 . 4 . 3 e ] , and c h e c k s r e l a t e d modes i n u n i o n s [ R . 4 . 4 . 3 b , d ] , I n mode c o e r c i o n , i t d e t e r m i n e s t h e c o e r c i o n s t e p s . T h i s i s a l s o a b a s i c p a r t o f mode b a l a n c i n g and INTRODUCTION 4 o p e r a t o r i d e n t i f i c a t i o n . In b a l a n c i n g , i t a l s o c o n s i d e r s c o l l a t e r a l d i s p l a y s . T h i s work i s an e x t e n s i o n o f [ P ] , so t h e i n p u t , o u t p u t f o r m a t and t h e i n t e r n a l r e p r e s e n t a t i o n a r e t h e same and i t i s d i f f e r e n t from f_ P ] i n t h e f o l l o w i n g r e s p e c t s : (1) An echo p r i n t f o r i n p u t i s added. (2) An e x p l i c i t v o i d s y m bol i s i n c l u d e d . (3) The t r e a t m e n t o f s k i p s , n i h i l s , jumps and vacuums a r e i n c l u d e d and t h e y a r e c o n s i d e r e d as s p e c i a l modes. (4) The c o n s i d e r a t i o n s t a r t s f r o m th e a p r i o r i mode ( t h e s o u r c e mode) t h a t a v o i d s some u n n e c e s s a r y f l a g g i n g o f some modes. (5) Makes use o f v e c t o r s o f b i t s t r i n g s and t h e o p e r a t i o n s AND and OR i n s t e a d o f t h e APL o p e r a t o r A/B i n many p l a c e s . The l e n g t h o f t h e p a r a m e t e c l i s t r e m a i n s t h e same t h r o u g h o u t t h e p r o c e s s h e r e w h i l e t h a t i s n o t t h e c a s e i n [ P ]. (6) Changes i n t h e r e v i s e d R e p o r t s u c h a s no p r o c e d u r i n g , meek c o e r c i o n a r e i n c l u d e d and (7) The i d e n t i f i c a t i o n o f a ( i ) as s l i c e o r c a l l i s a l s o i n c l u d e d . In t h i s t h e s i s , each c h a p t e r t h a t d e s c r i b e s a p a r t o f t h e program, i s d i v i d e d i n t o t h r e e s e c t i o n s which may be s u b d i v i d e d . In t h e f i r s t s e c t i o n , t h e meanings o f the terms c o n c e r n e d i n t h a t c h a p t e r a r e shown, and p e r h a p s some s y n t a x r u l e s a b o u t them a r e g i v e n . So t h e t e r m s used i n the above INTRODUCTION 5 p a r a g r a p h s a r e n o t e x p l a i n e d h e r e . I n t h e s e c o n d s e c t i o n , t h e a l g o r i t h m i s g i v e n and i n t h e t h i r d s e c t i o n , an example i s g i v e n t o show how t h e program works. For t h e s a k e o f b r e v i t y , c o n t r a c t i o n s s u c h as i n t f o r i n t e g r a l , r e f f o r r e f e r e n c e t o , e t c . , a r e used t h r o u g h o u t t h i s work. MODE REPRESENTATION 6 CHAPTER I I MODE REPRESENTATION T h i s c h a p t e r d e s c r i b e s how a mode i s d e c l a r e d and how i t i s s t o r e d . 2.1. Mode d e c l a r e r s : The s y n t a x o f d e c l a r e r s i s p r o v i d e d i n t h e R e p o r t : [ R . 1 . 2 . 1 ] , [ R . 1 . 2 . 2 ] , [ B . 1 . 2 - 7 ] , [ R . 7 . 1 . 1 ] and [ R . 7 . 2 . 1 ] . E x a mples o f mode d e c l a r a t i o n s a r e : mode rod = s t r u c t ( s t r i n g t , cw, b i t s f l a g , i n t mn, n f , r e f u n i o n (nd, md) l i n k , f i e l d ) ; mode nd = s t r u c t ( r e f md v, r e f nd nxtmd). 2.2. The mode s t o r a g e grammar: Modes can be r e p r e s e n t e d by a grammar [ Z , P 2 ] . L e t t h e p r i m i t i v e modes be P1 = { v o i d , b o o l , i n t , r e a l , c h a r , f o r m a t , b i t s , b y t e s , s k i p , jump, n i l , vacuum} { v o i d , s k i p , jump, n i l and vacuum a r e not r e a l l y modes, however, they a r e t r e a t e d l i k e modes. The l o n g v e r s i o n s o f i n t , r e a l and compl a r e n o t c o n s i d e r e d i n t h i s t h e s i s ) . L e t t h e p r e f i x e s be s u b d i v i d e d i n t o two s e t s : P2 = { r e f , p r o c , row, rowof } and P3 = { u n i o n , s t r u c t , p r o c p } where p r c c p i s p r o c e d u r e w i t h p a r a m e t e r s (row, rowof a r e used f o r [ ] ) . MODE HEPBESENTATION 7 L e t t h e MODE d e c l a r e r s be viewed a s a grammar g = < T,N,P > where t h e s e t c f t e r m i n a l s i s T = P1 0 P2 U P3 U P4, where P1,P2,P3 a r e d e f i n e d a b o v e . PU i s t h e s e t o f a l l f i e l d s e l e c t o r s o f t h e d e f i n e d s t r u c t u r e s . N i s t h e s e t o f n o n t e r m i n a l s , i . e . , t h e s e t o f a l l t h e modes (each r e p r e s e n t e d by an i n t e g e r ) and P i s t h e s e t o f p r o d u c t i o n r u l e s . A p r o d u c t i o n r u l e i s i n th e form o f mx = p my(1) my (2) ... my(n) w i t h mx, my(1), my (2) , my (n) i n N, p c a l l e d t h e t e r m i n a l , i n T; i f p i s i n P1 t h e n my(1) ... my (n) i s empty, i f p i s i n P2 t h e n n=1 and my(1) i s t h e d e c l a r e r f o l l o w i n g p i n mx, i f p i s i n PU t h e n n=1 and my(1) i s t h e d e c l a r e r o f t h e p o r t r a y a l c o n t a i n i n g t h e f i e l d s e l e c t o r p, i f p i s i n P3 t h e n n>1 and t h e m y ( i ) ' s f o r i = 1,...,n a r e t h e c o n s t i t u e n t s o f p where i f p i s " u n i o n " , my(1), my (2 ) , . . . my (n) a r e t h e c o n s t i t u e n t modes f o r p; i f p i s " s t r u c t " t h e n my ( i ) i s t h e i - t h p o r t r a y a l ; i f p i s p r o c p t h e n my (1),...my (n-1) a r e t h e modes o f t h e p a r a m e t e r s and my (n) i s t h e mode d e l i v e r e d by t h e p r o c e d u r e . P o r t r a y a l s o f a s t r u c t u r e [ r e v i s e d R.7.1.1.ea] a r e p a r t o f MODE REPRESENTATION 8 t h e mode so t h e r e a r e modes i n t h e form mx = g my w i t h q n o t i n t h e u n i o n o f PI, P2 and P3. I n t h i s c a s e , g must be a f i e l d s e l e c t o r o f a s t r u c t u r e and my i s t h e mode of g. Note t h a t i t i s c o n v e n i e n t h e r e t o i n t e r c h a n g e t h e o r d e r i n a p o r t r a y a l . As modes c a n be i n f i n i t e i n l e n g t h b u t not t h e d e c l a r e r s , modes a r e s t o r e d a s d e c l a r e r s . Each mode d e c l a r e r i s r e p r e s e n t e d by a number. The p r i m i t i v e modes c o n s i d e r e d i n t h i s s t u d y a r e : mO = v o i d , 01 = b o o l . m2 = i n t , ro3 = r e a l . D)4 = c h a r , m5 = f o r m a t , m 6 - b i t s . m7 = b y t e s . m12 = s k i p . m13 = jump. n14 = n i l . m15 = vacuum. The s t a n d a r d modes which r e s i d e i n t h e program a r e t h e p r i m i t i v e s t o g e t h e r w i t h t h e f o l l o w i n g : m8 = , s t r u c t m10 m11 (complex) m9 = rowof m4 ( s t r i n g ) m10 = r e ra3 MODE REPRESENTATION 9 m11 = im m3. Here m10 and ra11 a r e t h e two p o r t r a y a l s o f m8. 2.3.1. R e p r e s e n t a t i o n o f t h e modes i n t h e program: As t h e program i s w r i t t e n i n ALGOL W, a l l t h e terms used h e r e a r e i n ALGOL W s e n s e . In t h e p r o g r a m , a r e c o r d ' md* i s a l l o c a t e d t o each mode number d e f i n e d i n t h e above way. The r e c o r d c l a s s 'md' i s d e f i n e d a s r e c o r d md ( s t r i n g (6) t , cw; b i t s f l a g ; i n t e g e r mn, n f ; r e f e r e n c e ( md, nd ) l i n k , f i e l d ) ; r T 1 1 1 1 : 1 T | t | cw | f l a g | mn | nf | l i n k 1 f i e l d | I I I I I I I I | " " | " " | # \ i n t | i n t | — > | — > | I I I I I I (nd,md) | <nd,md) | I I . L I I I 1 J where nd i s a n o t h e r r e c o r d c l a s s d e f i n e d as r e c o r d nd ( r e f e r e n c e (md) v; r e f e r e n c e (nd) nxtmd ) ; | v J nxtmd | I i 1 | — >(md) | — >(nd) | C L J which i s u s e d f o r a l i s t o f modes. (The arrow i n d i c a t e s a r e f e r e n c e . ) I n t h e r e c o r d 'md 1, t h e f i r s t f i e l d *t» i s a s t r i n g o f 6 c h a r a c t e r s , which i s t h e t e r m i n a l o f t h e mode. The s e c o n d f i e l d 'cw* i s a s t r i n g o f 6 c h a r a c t e r s , which i s used a s t e m p o r a r y s t o r a g e f o r t h e c o e r c i o n word f o r t h e mode i n t h e MODE REPRESENTATION 10 p r o c e s s o f c o e r c i o n . The t h i r d f i e l d ' f l a g ' i s a b i t s t r i n g u s e d t o s t o r e t h e f l a g s i n t h e p r o c e s s o f c o e r c i o n . T h i s i s t h e most u s e f u l f i e l d i n t h e m a n i p u l a t i o n . The f o u r t h f i e l d •mn• i s an i n t e g e r f o r mode number. T h i s i s t h e i n t e g e r o f t h e l e f t hand s i d e o f a r u l e o f t h e mode grammar, o r a f i x e d number f o r a s t a n d a r d mode. F o r example: 'an' o f v o i d i s 0, b o o l i s 1. The f i f t h f i e l d * n f i s an i n t e g e r to show t h e number o f modes r e f e r e n c e d by ' f i e l d * o f t h e mode. I f t h e t e r m i n a l i s a p r i m i t i v e mode t h e n t h e ' n f i s 0, o t h e r w i s e i t i s e g u a l t o t h e number o f modes i n t h e mode l i s t t o f o l l o w t h e t e r m i n a l i n t h e r u l e . The s i x t h f i e l d * l i n k ' i s a r e f e r e n c e t o e i t h e r an •md" o r an 'nd'. * l i n k ' i s used a s w o r k i n g s t o r a g e t o r e f e r e n c e an *md' t o l i n k t h o s e modes w h i c h a r e o f t h e same c l a s s i n e q u i v a l e n c e o r t o l i n k b a c k w a r d s i n c o e r c i o n . The s e v e n t h f i e l d ' f i e l d * i s a l s o a r e f e r e n c e t o e i t h e r an 'md' o r an *nd*. F o r a p r i m i t i v e mode, i t i s n u l l o t h e r w i s e i t p o i n t s to t h e mode l i s t t h a t c o n t a i n s t h e c o n s t i t u e n t s o f t h e t e r m i n a l , i f the t e r m i n a l i s u n i o n , s t r u c t o r p r o c p , o r i t p o i n t s t o t h e mode t h a t f o l l o w s t h e t e r m i n a l o f t h e p r e s e n t mode. A r e c o r d 'md' i s a l s o a l l o c a t e d t o s o m e t h i n g t h a t i s n o t r e a l l y a mode i n t h e ALGOL 68 s e n s e , b u t t h a t i s l o o k e d upon as a mode and i s used t o h e l p s i m p l i f y t h e m a n i p u l a t i o n i n t h e program; i n t h i s c a s e , t h e r e c o r d 'md* i s s a i d t o be us e d f o r a 'pseudo-mode*. T h e r e a r e two c a s e s o f a •pseudo-mode *: (1) t h e modeO i n t h e program: MODE REPRESENTATION P ti n " J " H ]~ #o 1 -1 I 0 T n u l l [ n u l l ] I 1 : L i x i L i . (2) An 'md* whose *cw»—field c o n t a i n s " c o n d " , " s e r i " o r " c o l l ' ! t o show t h a t i t s ' l i n k ' - f i e l d p o i n t s t o a mode l i s t f o r a c o n d i t i o n a l , s e r i a l o r c o l l a t e r a l c l a u s e . An example i s : " " ~ T ~ " c o n d " T ~ #0 T -1 ] ~ 0 T — > ( n 3 ) T n u l l ] L L : I L L t L I . 2.3.2. An example t o show how i t works i n t h e program: In u s i n g t h e program, mode d e c l a r e r s a r e e n t e r e d by u s i n g t h e command "GRAMMAR" and a s e t o f r u l e s o f grammar t o be e n t e r e d f o l l o w e d by an i n t e g e r l e s s t h a n -1 t h a t shows t h e end o f t h e s e t o f r u l e s . E ach r u l e c f t h e mode grammar i s e n t e r e d a s m t p where (a) m i s an i n t e g e r s u c h t h a t 15 < m < 35. A w a r n i n g w i l l be g i v e n and t h e r u l e w i l l be e n t e r e d a t t h e end of t h e whole s e t o f r u l e s f o r t h e f i r s t time t h i s r e s t r i c t i o n i s b r o k e n , i f i t i s b r o k e n more t h a n once, o n l y t h e l a s t o f t h e r u l e s b r e a k i n g t h i s r e s t r i c t i o n w i l l be e n t e r e d and t h e o t h e r s t h a t b r e a k t h i s r e s t r i c t i o n w i l l be n e g l e c t e d . (b) t i s a t e r m i n a l which i s a s t r i n g s o t h a t i t must be e n c l o s e d i n q u o t e s . (c) p i s e i t h e r a mode i . e . an i n t e g e r i su c h t h a t 0 < i < 35 o r a mode l i s t i . e . a s e q u e n c e o f modes MODE REPRESENTATION 12 f o l l o w e d by an i n t e g e r l e s s t h a n - 1 . Example: "grammar" 16 " r e f " 17 17 " u n i o n " 2 18 19 -2 18 " r o w o f " 3 19 " s t r u c t " 20 21 23 -2 20 " a " 9 21 »b" 22 22 " r e f " 19 23 "c» 22 24 " r e f " 18 25 " p r o c " 3 -2 In t h e above example, m16 = r e f u n i o n ( i n t , [ ] r e a l , m_19) , ml9 = s t r u c t ( s t r i n g a , r e f mJ9 b , r e f ml.9 c) , ml8 = rowof r e a l , m24 = r e f [ ] r e a l , m25 = j j r o c r e a l . The —2 i n m17 i s t o t e r m i n a t e t h e l i s t o f modes i n t h e u n i o n , t h e -2 i n m19 i s t o t e r m i n a t e t h e l i s t o f modes i n t h e f i e l d s o f t h e s t r u c t u r e . The l a s t -2 i s t o t e r m i n a t e t h e r u l e s o f t h e grammar. The command "GRAMMAR" t h e n comes t o an end. A l l t h e modes d e f i n e d a r e put i n an a r r a y o f fi n d ' s , MODE, o f which t h e f i r s t 16 a r e f i x e d . Now some o f t h e e l e m e n t s o f MODE a r e a s f o l l o w s : MODE R E P R E S E N T A T I O N M O D E ( 1 6 ) i s i ^ — T : — • 1 : T : — : 1 T r 1 I ref | J 0 | 1 6 | 1 | null | —> | I I I I lnode(17) | MODE ( 1 7 ) i s r - r — T - 1 : 1 T 1 —: r -i | union | | 0 l 1 7 | 3 | null | —> | l _ J J_ | j i 'A' J where A is H->HODE (2)~T"-+->r — > M O D E ( 1 8 ) T -+-> | " — > M O D E ( 1 9 ) TNUIL| M O D E ( 1 8 ) is r— 1 ^ 1 1 T T ; 1 1 | rowcf | | 0 | 1 8 | 1 j null | —> | [ _ [ . 1 1 1 1 |mode{3) | MODE ( 1 9 ) i s i : T : T T — r 1 r T Istruct | | 0 | 1 9 J 3 | null | —> | I I i I I I I ' B • | I 1 . 1 : 1 L L j . l where E is f _ _ > M 0 D E ( 2 0 ) [ ~ I + - > [ — > M O D E ( 2 1 ) ] " - + - > [ — > M O D E ( 2 3 ) T N O L I ] M O D E ( 2 0 ) is i ; r : T r 1 1 T T I a I J 0 | 2 0 | 1 | null | —> | I I I I I I |mode(9) | I L • _ 1 1 1 1 I I and so cn. MODE EQUIVALENCING 1U CHAPTER I I I MODE EGUIVALENCING 3.1.1. E q u i v a l e n t modes: In an ALGOL 68 program, t h e programmer might have d e f i n e d some modes which a r e e q u i v a l e n t , t h a t i s t h e y a r e t h e same t e r m i n a l p r o d u c t i o n o f t h e m e t a n o t i o n BODE. An example o f e q u i v a l e n t mode d e c l a r e r s : mode u = s t r u c t ( i n t i , r e f u j ) ; mode v = s t r u c t ( i n t i , r e f s t r u c t ( i n t i , r e f v j) j) . 3.1.2. R e l a t e d modes and r a v e l i n g o f a u n i o n mode: Two modes a r e s a i d t o be ' r e l a t e d * t o one a n o t h e r i f t h e y a r e b o t h f i r m l y c o e r c e a b l e from one same mode [R. 4 . 4 . 3 . b ] « Thus a mode i s r e l a t e d t o i t s e l f . The modes r e f p r o c r e a l and r e a l a r e r e l a t e d w h i l e t h e modes r e f r e a l and p r o c r e a l a r e not (the l a t t e r two were r e l a t e d i n R ! ) , s i n c e t h e r e i s no p r o c e d u r i n g c o e r c i o n ( i n t h e r e v i s e d R e p o r t ) . I t i s n o t a l l o w e d t o d e f i n e a mode u n i t e d f r o m two modes r e l a t e d t o one a n o t h e r [ R 4 . 4 . 3 d ] , The r e l a t i o n • r e l a t e d ' i s o n l y c h e c k e d when t h e modes a r e t h e c o n s t i t u e n t modes o f a u n i o n . S i n c e t h e u n i o n modes i n s i d e a u n i o n a r e r a v e l e d , no u n i o n s a r e i n v o l v e d i n t h i s p r o c e s s . I f a u n i o n mode ml i s a c o n s t i t u e n t o f a n o t h e r u n i o n mode m, ml i s t o be r a v e l e d s u c h t h a t ml i s no l o n g e r a c o n s t i t u e n t o f m, but each c o n s t i t u e n t o f ml i s a MODE EQUIVALENCING 15 c o n s t i t u e n t o f m. Example: u n i o n ( b o o l , u n i o n ( i n t , c h a r )) w i l l be changed t o u n i o n ( b c o l , i n t , c h a r ) when i t s c o n s t i t u e n t s a r e r a v e l e d . B e f o r e t h e r e l a t i o n ' r e l a t e d ' i s c h e c k e d , t h e c o n s t i t u e n t s o f t h e u n i o n mode a r e r a v e l e d , s o r t e d i n o r d e r by mode numbers and d u p l i c a t e d c o n s t i t u e n t s a r e removed. 3.1.3. Some c o n t e x t c o n d i t i o n s : S i n c e t h e programmer i s a l l o w e d t o d e f i n e h i s own modes and i n f i n i t e modes may be d e c l a r e d , some c o n d i t i o n s must be s a t i s f i e d s u c h t h a t (1) no mode may a l l o w ambiguous p a r s i n g o f t h e program and (2) a v a l u e o f any mode must not t a k e i n f i n i t e s t o r a g e s p a c e i n t h e c o m p u t e r . An example f o r (1) : mode t = s t r u c t ( i n t a, r e a l a ) . Exa m p l e s f o r (2) : mode f = s t r u c t ( [ 1 : 1 0 ] f a, i n t s ) . mode t = r e f t . The f i r s t c o n d i t i o n i s t h a t no d u p l i c a t e s e l e c t o r i s a l l o w e d i n a s t r u c t u r e mode [ R . 4 . 4 . 3 . e ] and t h e s e c o n d i s t h e c o n t e x t c o n d i t i o n s h i e l d i n g [ R . 4 . 4 . 4 ] , The f o l l o w i n g i n d i c a t i o n s a r e s h i e l d e d and so a r e l e g a l : (1) mode a = s t r u c t ( i n t b, r e f a c ) where t h e s e c o n d o c c u r r e n c e o f a i s a v i r t u a l - d e c l a r e r f o l l o w i n g a r e f e r e n c e - t o - s y m b o l i n a p o r t r a y a l . (2) mode a = r e f s t r u c t ( i n t b, a c ) where t h e s e c o n d o c c u r r e n c e o f a i s a v i r t u a l - d e c l a r e r c o n t a i n e d i n a MODE EQUIVALENCING 16 p o r t r a y a l c o n t a i n e d i n a v i r t u a l - d e c l a r e r f o l l o w i n g a r e f e r e n c e - t o - s y m b o l . (3) mode a = firocjJ (a) a where t h e s e c o n d o c c u r r e n c e o f a i s a v i r t u a l p a r a m e t e r and t h e t h i r d o c c u r r e n c e o f a i s a v i r t u a l d e c l a r e r f o l l o w i n g a v i r t u a l - p a r a m e t e r s - p a c k . A d e c l a r e r i s " s h o w i n g " i f i t c o n t a i n s a m o d e - i n d i c a t i o n w h i c h i s not " s h i e l d e d " (see examples f o r (2) a b o v e ) . 3.2.1, D e f i n i t i o n o f e q u i v a l e n t modes i n t h e mode-grammar: In t h e mode-grammar d e s c r i b e d i n CHAPTER I I , two modes a r e u n e q u a l i f t h e i n t e g e r s r e p r e s e n t i n g them a r e n o t t h e same. T h e r e i s a u n i g u e p r o d u c t i o n r u l e f o r e a c h n o n t e r m i n a l . In t h e f o l l o w i n g , t h e t e r m i n a l s and t h e n o n t e r m i n a l s a r e t h o s e on t h e r i g h t hand s i d e s o f t h e p r o d u c t i o n r u l e s f o r t h e modes. Two modes a r e n o t e q u i v a l e n t i f and o n l y i f one o f t h e f o l l o w i n g i s t r u e : (1) t h e t e r m i n a l s a r e n o t t h e same, (2) i f t h e t e r m i n a l s a r e n o t ' u n i o n ' , t h e numbers o f n o n t e r m i n a l s a r e n o t e g u a l , (3) i f t h e t e r m i n a l s a r e n o t ' u n i o n * , a n o n t e r m i n a l o f one p r o d u c t i o n r u l e i s not e q u i v a l e n t to t h e c o r r e s p o n d i n g n o n t e r m i n a l o f t h e o t h e r , (U) i f t h e t e r m i n a l s a r e *union«, t h e r e e x i s t s a n o n t e r m i n a l o f one r u l e n o t e q u i v a l e n t t o any o f t h e n o n t e r m i n a l s o f t h e o t h e r . MODE EQOIVALEHCITJG 17 3.2.2. A l g o r i t h m s : I n o r d e r t o s a v e s t o r a g e s p a c e and n o t t o c o m p l i c a t e t h e p r o c e s s o f c o e r c i o n and b a l a n c i n g , modes a r e e q u i v a l e n c e d , t h a t i s i f two o r more modes a r e e q u i v a l e n t , o n l y one i s k e p t , as so o n a f t e r t h e y have been e n t e r e d as p o s s i b l e . B e f o r e e g u i v a l e n c i n g , t h e c o n t e x t c o n d i t i o n s d e s c r i b e d above a r e c h e c k e d and u n i o n s a r e r a v e l e d . The a l g o r i t h m t o c h e c k t h e c o n t e x t c o n d i t i o n s o f a mode: I n p u t : mode: a mode whose c o n t e x t c o n d i t i o n s a r e t o be c h e c k e d . r e f : a l o g i c a l v a l u e which i s f a l s e when t h e p r o c e d u r e i s f i r s t c a l l e d . T h i s i s t r u e , i f ' r e f * has a p p e a r e d b e f o r e . s t r u c t : a l o g i c a l v a l u e which i s a l s o f a l s e when t h i s p r o c e d u r e i s f i r s t c a l l e d . T h i s i s t r u e , i f ' s t r u c t * has a p p e a r e d b e f o r e . O u t p u t : e r r o r message, i f t h e c o n t e x t c o n d i t i o n s a r e n o t met. F u n c t i o n : t o change d u p l i c a t e d f i e l d s e l e c t o r s t o "%". To change modes which a r e " s h o w i n g " t o ' b o o l * . S t e p l : l e t m be 'mode'. I f t h e f l a g - f i e l d o f m i s #1, t h e n g o t o s t e p 6 . S t e p 2 : s e t t h e f l a g - f i e l d o f m t o #1. S t e p 3 : i f t h e t e r m i n a l o f m i s " p r o c p " t h e n g o t o s t e p 5 . I f t h e t e r m i n a l i s " r e f " t h e n i f ' s t r u c t * i s t r u e t h e n g o t o s t e p 5 , i f f a l s e t h e n s e t ' r e f t r u e . MODE EQUIVALENCING 18 I f t h e t e r m i n a l i s " s t r u c t " t h e n go t o s t e p 7 . S t e p 4 : i f t h e f i e l d - f i e l d o f m p o i n t s t o an *md* t h e n r e c u r s i v e l y c h e c k t h e c o n d i t i o n s o f t h e mode p o i n t e d t o by t h e f i e l d - f i e l d o f m w i t h t h e p r e s e n t l o g i c a l v a l u e s o f * r e f * and ' s t r u c t ' (by g o i n g t h r o u g h s t e p l ) , I f t h e f i e l d - f i e l d o f m p o i n t s to an 'nd' t h e n r e c u r s i v e l y c h e c k t h e c o n d i t i o n s o f e a c h mode i n t h e mode l i s t p o i n t e d t o by t h e f i e l d - f i e l d o f m w i t h t h e p r e s e n t l o g i c a l v a l u e s o f ' r e f and ' s t r u c t * . S t e p 5 : s e t t h e f l a g - f i e l d o f m back t o #0. S t o p . S t e p 6 : t h e mode m i s sho w i n g i t s e l f . S e t m t o »bcol' t o a v o i d t h i s d a n g e r o u s s i t u a t i o n and a message i s g i v e n . S t o p . S t e p 7 : c h e c k f o r r e p e a t e d f i e l d - s e l e c t o r : c h e c k t h e modes i n t h e mode l i s t p o i n t e d t o by t h e f i e l d — f i e l d of m, i f t h e r e a r e two i d e n t i c a l t e r m i n a l s , g i v e an e r r o r message and s e t t h e s e c o n d one t o "$". S t e p 8 : i f ' r e f i s t r u e t h e n g o t o s t e p s . S t e p 9 : s e t * s t r u c t * t r u e . Goto s t e p U . End o f t h e a l g o r i t h m f o r c h e c k i n g c o n t e x t c o n d i t i o n s o f a mode. The a l g o r i t h m f o r r a v e l i n g t h e u n i o n s i n a mode l i s t which i s t h e c o n s t i t u e n t s o f a u n i o n : I n p u t : m d l i s t : t h e l i s t o f modes which a r e t h e c o n s t i t u e n t s o f a u n i o n mode, t o be r a v e l e d . MODE EQDIVAIEUCING 19 O u t p u t : -F u n c t i o n : t o change ' m d l i s t ' t o a l i s t which c o n t a i n s t h e n o n - u n i o n modes o f • m d l i s t ' and c o n s t i t u e n t s o f t h o s e r a v e l e d u n i o n modes o f ' m a i i s t * . S t e p l : i f ' m d l i s t ' i s n u l l t h e n g o t o s t e p 2 o t h e r w i s e do s t e p l . a t h r o u g h s t e p l . g . S t e p l . a : i f t h e t e r m i n a l o f v ( ' m d l i s t ' ) i s not " u n i o n " t h e n g o t o s t e p l . f . S t e p l . b : l e t g be a c o p y o f t h e l i s t o f modes p o i n t e d t o by t h e f i e l d - f i e l d o f v(» m d l i s t ' ) . S t e p l . c : l e t nxtmd ( ' m d l i s t * ) be c o n c a t e n a t e d t o g. S t e p l . d : s e t ' m d l i s t 1 = g; r a v e l ( • m d l i s t • ) . S t e p l . e : g o t o s t e p 2 . S t e p l . f : l e t p be e q u a l t o nxtmd ( ' m d l i s t • ) . S t e p l . g : r a v e l ( p ) . S t e p 2 : s t o p . End o f t h e a l g o r i t h m f o r r a v e l i n g u n i o n s . The a l g o r i t h m f o r e g u i v a l e n c i n g o f a l l t h e d e f i n e d modes: I n p u t : . O u t p u t : . F u n c t i o n : t o p a r t i t i o n a l l t h e r u l e s d e f i n e d i n t h e grammar t o e q u i v a l e n c e c l a s s e s s u c h t h a t two r u l e s a r e i n t h e same c l a s s i f and o n l y i f t h e y a r e e q u i v a l e n t . F o r e a c h e q u i v a l e n t c l a s s o f modes, o n l y one i s k e p t , t h e r e s t i s d i s c a r d e d . S t e p l : p a r t i t i o n a l l t h e r u l e s d e f i n e d i n t h e grammar t o MODE EQUIVALEHCIHG 20 e q u i v a l e n c e c l a s s e s s u c h t h a t two r u l e s a r e i n t h e same c l a s s i f and o n l y i f t h e i r t e r m i n a l s on t h e r i g h t hand s i d e a r e the same. S t e p 2 : p a r t i t i o n e ach c l a s s e x c e p t t h e c l a s s w i t h t h e t e r m i n a l " u n i o n " , o b t a i n e d i n s t e p l i n t o s u b c l a s s e s , s u c h t h a t two r u l e s a r e i n t h e same s u b c l a s s i f and o n l y i f t h e y have t h e same number o f n o n t e r m i n a l s on t h e r i g h t s i d e . So i n t h i s new p a r t i t i o n o f t h e r u l e s , a l l r u l e s whose t e r m i n a l s a r e " u n i o n " a r e i n t h e same c l a s s , any o t h e r two r u l e s a r e i n t h e same c l a s s i f and o n l y i f t h e y have t h e same t e r m i n a l s and e q u a l numbers o f n o n t e r m i n a l s . S t e p 3 : s u b d i v i d e e a c h c l a s s whose t e r m i n a l i s n o t " u n i o n " , i n the p r e v i o u s p a r t i t i o n i n t o s u b c l a s s e s s u c h t h a t two r u l e s a r e i n t h e same s u b c l a s s i f and o n l y i f t h e i — t h n o n — t e r m i n a l o f one r u l e i s i n t h e same c l a s s as t h e i — t h n o n t e r m i n a l o f t h e o t h e r f o r a l l 1 < ii < n where h i s t h e number o f n o n t e r m i n a l s on t h e r i g h t hand s i d e o f t h e r u l e . S u b d i v i d e each c l a s s whose t e r m i n a l i s " u n i o n " i n t h e p r e v i o u s p a r t i t i o n i n t o s u b c l a s s e s s u c h t h a t two r u l e s a r e i n t h e same s u b c l a s s i f and o n l y i f e a c h o f t h e n o n t e r m i n a l s o f t h e one i s i n t h e same c l a s s as one o f t h e n o n t e r m i n a l s o f t h e o t h e r . S t e p 4 : i f no s u b d i v i s i o n o c c u r r e d i n s t e p 3 t h e n s t o p o t h e r w i s e g o t o s t e p 3 . End o f t h e a l g o r i t h m f o r e g u i v a l e n c i n g . MODE EQUIV ALENCING 21 The a l g o r i t h m t o c h e c k i f t h e r e a r e r e l a t e d modes i n a l i s t o f modes i s as f o l l o w s : I n p u t : a l i s t o f modes. O u t p u t : a s u b l i s t o f t h e i n p u t l i s t t h a t c o n t a i n s a l l t h e modes such t h a t e a c h o f them i s r e l a t e d t o some o t h e r mode i n t h e l i s t ( t h i s l i s t i s n u l l when no two o f t h e g i v e n modes a r e r e l a t e d ) . S t e p l : mark ea c h mode m1f m2, . » . , mk o f the l i s t . S t e p 2 : l e t ' r e t u r n ' be a n u l l mode l i s t . S t e p 3 : f o r i:=1 u n t i l k do s t e p 3 . a t o s t e p 3 . c . S t e p 3 . a : l e t m = mi. S t e p 3 . b : i f m = p r o c n o r m = r e f n t h e n i n c a s e t h a t n i s marked, t h e n n and mi a r e r e l a t e d and s e a r c h - i n s e r t them t o ' r e t u r n ' ( t h a t means i f t h e y were not t h e r e t h e n i n s e r t them i n o r d e r ) e l s e s e t m = n and g o t o s t e p 3 . b : o t h e r w i s e , s t e p 3 . c : mi has been c o m p l e t e l y p r o c e s s e d . S t e p 4 : ' r e t u r n ' i s t h e mode l i s t t o be r e t u r n e d . End o f t h e a l g o r i t h m f o r c h e c k i n g r e l a t e d modes. 3.2.3. R e v e r s e r a v e l i n g o f u n i o n s : The j o b o f ' c o e r c i o n * i s t o c h e c k i f a g i v e n mode, t h e s o u r c e mode can be t r a n s f o r m e d t o some o t h e r mode, t h e t a r g e t mode. The s o u r c e mode i s c a l l e d t h e a p r i o r i mode and t h e t a r g e t mode t h e a p o s t e r i o r i mode. I n o r d e r t o s i m p l i f y t h e p r o c e s s e s o f ^ c o e r c i o n ' , ' b a l a n c i n g * and • c o l l a t e r a l * , a p r o c e d u r e c a l l e d *reverse_ravel» i s c a l l e d MODI EQUIVAIEUCING 22 i m m e d i a t e l y a f t e r e g u i v a l e n c i n g . In * r e v e r s e _ r a v e l ' , d e f i n e d s u b - u n i o n s o f a u n i o n mode a r e added as f i e l d s t o t h e g i v e n u n i o n mode. F o r example: i f t h e mode u n i o n ( i n t , r e a l , comjjl ) and u n i o n ( i n t , r e a l ) a r e d e f i n e d , u n i o n ( i n t , r e a l , comjjl ) w i l l be c h a n g e d t o u n i o n ( i n t , r e a l , c o m j j l , u n i o n ( i n t , r e a l )) by »r e v e r s e _ r a v e l » . In t h e p r o c e s s o f ' c o e r c i o n ' , ' b a l a n c i n g ' or ' c o l l a t e r a l ' , t h e a p o s t e r i o r i mode i s f l a g g e d and t h e modes from which i t c a n be c o e r c e d a r e a l s o f l a g g e d , f o r example, when the a p o s t e r i o r i mode i s r e a l and t h e p o s i t i o n i s s t r o n g t h e n r e a l and i n t a r e b o t h f l a g g e d b e c a u s e i n t can be s t r o n g l y widened t o r e a l . So i n t h e above example, whenever u n i o n ( i n t , compj. )i i s g i v e n as t h e a p o s t e r i o r i mode i n s t r o n g o r f i r m c o e r c i o n , as a b a l a n c e d mode i n b a l a n c i n g or a s . t h e mode o f an o p e r a n d i n a d e f i n e d o c c u r r e n c e o f an o p e r a t o r which i s t o be i d e n t i f i e d , t h e n t h e modes u n i o n ( i n t , r e a l , SOJJrl ) t i i } t f r e a l , comjjl and u n i o n ( i n t , r e a l ) s h o u l d a l l be f l a g g e d . W i t h o u t » r e v e r s e _ r a v e l i n g ' , from the mode u n i o n ( i n t , r e a l , comp ) , the mode u n i o n ( i n t , r e a l ) can be r e a c h e d o n l y by s e a r c h i n g t h r o u g h a l l t h e d e f i n e d modes, and a s e a r c h f o r ea c h o c c u r r e n c e o f t h e g i v e n u n i o n mode as an a p o s t e r i o r i mode i s n e c e s s a r y . With ' r e v e r s e _ r a v e l i n g ' , t h e s u b u n i o n modes c a n be a c c e s s e d from t h e c o n s t i t u e n t s , and t h e s e a r c h i s once f o r a l l . The a l g o r i t h m f o r r e v e r s e r a v e l i n g a u n i o n mode: I n p u t : mi, a u n i o n mode . O u t p u t : »mi'. MODE EQUIVALEHCING 23 F u n c t i o n : t o i n c l u d e t h e s u b u n i o n s o f 'mi' i n t h e l i s t r e f e r e n c e d by t h e • f i e l d * - f i e l d of 'mi*. S t e p l : f o r ea c h d e f i n e d u n i o n mode mj o t h e r t h a n mi do s t e p 2 . S t e p 2 : i f t h e mode l i s t p o i n t e d t o by t h e f i e l d - f i e l d o f mj i s a s u b l i s t o f t h e mode l i s t p o i n t e d t o by t h e f i e l d - f i e l d o f mi th e n add mj t o t h e mode l i s t p o i n t e d t o by t h e f i e l d - f i e l d o f mi. S t e p 3 : s t o p . End o f t h e a l g o r i t h m f o r r e v e r s e r a v e l i n g a u n i o n mode. 3.3.1. An example t o show how to c h e c k t h e c o n t e x t c o n d i t i o n s f o r a g i v e n mode: Suppose t h e f o l l o w i n g mode grammar i s e n t e r e d : 16 " s t r u c t " 19 17 " r e f " 16 18 " s t r u c t " 20 19 " i " 17 20 " j " 18 -2 . T h a t i s mJ6 = s t r u c t ( r e f m_16 i ) and m18 = s t r u c t (m_18 j) . In c h e c k i n g t h e c o n d i t i o n s f o r mJ6 : (1) MODE (16) i s c h e c k e d w i t h Vref» = f a l s e , ' s t r u c t * = f a l s e : f l a g (MODE (16)) i s s e t t o #1 and t h e f i e l d s e l e c t o r s a r e c h e c k e d . (2) MODE (19) i s c h e c k e d w i t h ' r e f = f a l s e , ' s t r u c t * = t r u e : MODE EQUIVALENCING 24 f l a g (MODE (19)) i s s e t t o #1. (3) MODE (17) i s c h e c k e d w i t h ' r e f * = f a l s e , ' s t r u c t ' = t r u e : f l a g (MODE (17)) i s s e t t o #1. (4) s i n c e i t s t e r m i n a l i s " r e f " , t h e n f l a g (MODE ( 1 7 ) ) i s s e t back t o #0, and so a r e t h e f l a g - f i e l d s o f MODE (19), MODE (16) . In c h e c k i n g t h e c o n d i t i o n s f o r mJ8 : (1) MODE (18) i s c h e c k e d w i t h ' r e f * = f a l s e , ' s t r u c t ' = f a l s e : f l a g ( M O D E (18)) i s s e t t o #1. (2) MODE(20) i s c h e c k e d w i t h *ref» = f a l s e , ' s t r u c t * = t r u e : f l a g (MODE(20)) i s s e t t o #1 (3) MODE (18) i s c h e c k e d a g a i n w i t h ' r e f * = f a l s e , ' s t r u c t * = t r u e : f l a g ( M O D E (18)) i s #1 a l r e a d y , s o an e r r o r message i s g i v e n and MODE (18) i s s e t t o * b o o l ' , a mode e q u i v a l e n t t o MODE(1) . 3.3.2. The mechanism used t o e q u i v a l e n c e modes i n t h e program: In t h e program, an *nd* I N I T I A L i s used s u c h t h a t e a c h mode i n t h e mode l i s t i s from a d i f f e r e n t c l a s s . T h e r e i s a one t o one c o r r e s p o n d e n c e o f an e l e m e n t o f t h e l i s t I N I T I A L and a c l a s s o f t h e p a r t i t i o n o f t h e r u l e s . A l l t h e modes i n ea c h c l a s s a r e l i n k e d t o g e t h e r t h r o u g h t h e i r l i n k - f i e l d s t o f o r m a l i n k e d l i s t and t h i s l i s t hangs down from t h a t e l e m e n t f o r t h i s c l a s s i n t h e l i s t I N I T I A L . The f l a g - f i e l d o f t h e modes a r e used f o r t h e c l a s s number o f the c l a s s which t h e mode i s i n . MODE EQUIVALENCING 25 At f i r s t , modes a r e c l a s s i f i e d by t h e i r t e r m i n a l s , i . e . e a ch e l e m e n t o f t h e l i s t I N I T I A L hangs a l i s t o f modes, l i n k e d t h r o u g h t h e i r l i n k - f i e l d s , w i t h t h e same t e r m i n a l . The f i r s t 12 c l a s s e s (from 0 t o 11th) a r e f o r t h e p r i m i t i v e modes, t h e 1 2 t h and t h e 13th a r e f o r * r e * and 'im' o f •complex*. The 14th i s f o r 'rowof* and t h e 15th i s f o r • s t r u c t * . C l a s s e s w i t h t e r m i n a l s o t h e r t h a n t h e above 16, a r e a t t a c h e d t o t h e end o f t h e l i s t I N I T I A L . The modes a r e l i k e t h i s : I N I T I A L I «-- >|->mode (0) T~-+->[->mode (1) !"-+->---L I I L I J ...->[->mode (7) | ~ Z J _ > f I > m o d e (12) 1 — H— > I ; I I I L I ...->[->mode ( 1 5 ) T ~ ^ > ! - > i » c d e (10)T——4—> r r — — i i T — T r T u J->mode(11)l -+->)->mode(9) | -+-> |->mode (8) | -+->... I . I I L L I L L I The f i r s t 15 e l e m e n t s o f t h e l i s t a r e t h e s t a n d a r d modes. A l l modes w i t h t h e same t e r m i n a l a r e i n a l i s t h a n g i n g down from an e l e m e n t o f t h e l i s t I N I T I A L , and t h e c l a s s number o f ea c h mode i s r e c o r d e d i n t h e f l a g f i e l d . The p r o c e s s o f e g u i v a l e n c i n g i s t h e n d i v i d e d i n t o * p a s s ' e s , In e a c h * p a s s * two p o i n t e r s t o mode l i s t s , *p' and ' f i n a l * a r e i n i t i a l i z e d t o p o i n t t o t h e 13-th and t h e l a s t e l e m e n t o f t h e l i s t I N I T I A L , and a p o i n t e r t o a mode l i s t o r a mode, • t a i l ' , i n i t i a l i s e d as a p o i n t e r t o t h e l a s t e l e m e n t o f MODE EQUIV ALENCTNG 26 I N I T I A L , i s used t o p o i n t t o t h e p l a c e where modes b e l o n g i n g t o a new c l a s s s h o u l d be p l a c e d ; and a p a s s i s c o m p l e t e when •p' goes f r o m t h e 1 3 - t h t o t h e end o f t h e l i s t I N I T I A L . Each * p a s s ' i s d i v i d e d i n t o ' s c a n s ' . A ' s c a n ' f o r an e l e m e n t m o f t h e mode l i s t I N I T I A L i s a moving o f a l l t h o s e modes which were i n t h e same c l a s s w i t h m, b u t a r e n o t now, t o t h e p l a c e p o i n t e d t o by T A I L ; t h a t i s t h e l i n k e d l i s t h a n g i n g f r o m m i s c h e c k e d and a l l t h o s e modes i n t h i s l i s t t h a t a r e no l o n g e r i n t h e same c l a s s a s m a r e g r o u p e d t o g e t h e r t o f o r m a new c l a s s h a n g i n g down from an e l e m e n t added t o t h e end o f t h e mode l i s t I N I T I A L . In ' p a s s * 1, e a c h c l a s s , e x c e p t the one w i t h t e r m i n a l " u n i o n " i s s u b d i v i d e d a c c o r d i n g t o t h e n f - f i e l d . T h i s i s s t e p 2 o f t h e a l g o r i t h m . A f t e r ' p a s s * 1, a l l t h e u n i o n modes a r e i n t h e same c l a s s and e a c h o f t h e o t h e r c l a s s e s c o n t a i n s a l l t h e modes which a r e o f t h e same t e r m i n a l and have e q u a l numbers o f n o n t e r m i n a l s . T h i s * p a s s ' s u b d i v i d e s t h e c l a s s e s h a n g i n g f r o m e l e m e n t s a f t e r t h e 12-th o f t h e l i s t I N I T I A L . The c l a s s number r e c o r d e d i n t h e f l a g - f i e l d i s u p d a t e d . In ' p a s s * 2, e a c h c l a s s i s s u b d i v i d e d a s i n s t e p 3 o f th e a l g o r i t h m by u s i n g t h e f l a g - f i e l d (s) o f t h e mode (s) p o i n t e d t o by t h e f i e l d — f i e l d o f t h e mode. T h i s ' p a s s ' i s r e p e a t e d u n t i l no more new c l a s s i s f o r m e d . Now t h e mode l i s t I N I T I A L c o n t a i n s as many e l e m e n t s as e q u i v a l e n t c l a s s e s . The l i n k f i e l d o f e a c h mode i s s e t t o p o i n t t o t h e f i r s t e l e m e n t o f i t s c l a s s and a l l t h e MODE EQUIV ALENCING 27 f i e l d - f i e l d s o f t h e modes a r e changed a c c o r d i n g l y , t h a t i s , a mode i s r e p l a c e d by t h e f i r s t mode c f i t s c l a s s , O n l y t h e f i r s t e l e m e n t o f a c l a s s i s k e p t . D i s c a r d a l l d u p l i c a t e d modes and compact t h e grammar. F o r a u n i o n mode, t h e n o n t e r m i n a l s a r e s o r t e d and r e p e a t e d modes a r e removed and t h e c o n t e x t c o n d i t i o n o f r e l a t e d modes i s c h e c k e d . The d e t a i l o f how to c h e c k i f a l i s t c f modes c o n t a i n s r e l a t e d modes w i l l be i n n e x t s e c t i o n . I n t h e program, t h i s i s i n i t i a t e d by t h e command "EQUIVALENCE" and no o t h e r d a t a a r e r e q u i r e d . , 3.3.3. Examples t o show how r e l a t e d modes a r e c h e c k e d : In c h e c k i n g t h e c o n t e x t c o n d i t i o n o f r e l a t e d modes, t h e f l a g - f i e l d s o f t h e modes a r e used f o r mar k i n g t h e modes. The command t o t e s t whether a l i s t o f modes c o n t a i n s some r e l a t e d modes i s "RELATED" f o l l o w e d by a l i s t o f modes. Note t h a t i f two modes i n t h e g i v e n l i s t a r e r e l a t e d by i n v o l v i n g t h e c o e r c i o n • u n i t e 1 c a n n o t be d e t e c t e d by t h i s command as a l l the modes i n s i d e a u n i o n mode a r e s u p p o s e d t o have been r a v e l e d , and t h i s c o n d i t i o n i s c h e c k e d o n l y when the l i s t c f modes f o r m s t h e c o n s t i t u e n t s o f a u n i o n mode. Example: s u p p o s e t h e grammar e n t e r e d i s 16 " r e f " 17 17 " p r o c " 3 MODE EQUIVALENCING 28 18 " p r o c " 19 19 " r e f " 3 20 " r e f " 19 21 " r e f " 2 -2. When t h e command "BELATED" 16 18 2 0 - 2 i s e n t e r e d , t h e n (1) The f l a g - f i e l d s o f MODE ( 1 6 ) , MODE (18) and MODE (20) a r e s e t #1. (2) C o n s i d e r r e f p r o c r e a l (MODE ( 1 6 ) ) , i t b e g i n s w i t h r e f , t h e n c h e c k i f t h e f l a g - f i e l d o f p r o c r e a l ( i . e . MODE(17)) i s #1, i t i s n o t . (3) C o n s i d e r p r o c r e a l , i t b e g i n s w i t h p r o c t h e n c h e c k i f t h e f l a g - f i e l d o f r e a l i s #1, i t i s n e t . (4) C o n s i d e r p r o c r e f r e a l (MODE ( 1 8 ) ) , i t b e g i n s w i t h p r o c t h e n check i f t h e f l a g - f i e l d o f r e f r e a l i s #1; i t i s n o t . (5) C o n s i d e r r e f r e a l , i t b e g i n s w i t h r e f t h e n c h e c k i f t h e f l a g — f i e l d o f r e a l i s #1; i t i s n o t . (6) C o n s i d e r r e f r e f r e a l (MODE ( 2 0 ) ) , i t b e g i n s w i t h r e f , th e n c h e c k i f t h e f l a g — f i e l d o f r e f r e a l i s #1; i t i s n o t . (7) C o n s i d e r r e f r e a l , i t b e g i n s w i t h r e f , t h e n c h e c k i f t h e f l a g - f i e l d o f r e a l i s #1; i t i s n o t . T h i s l i s t d o e s n o t c o n t a i n any s e t o f r e l a t e d modes. When t h e command i s MODE 1QUIVALEHCING 29 "RELATED" 16 18 20 3 -2 t h e n (1) The f l a g - f i e l d s o f MODE (16 ) , MODE ( 1 8 ) , MODE(20) and MODE (3) a r e s e t #1. (2) C o n s i d e r r e f p r o c r e a l , i t b e g i n s w i t h r e f t h e n c h e c k i f t h e f l a g — f i e l d o f p r o c r e a l i s #1; i t i s n o t . (3) C o n s i d e r p r o c r e a l , i t b e g i n s w i t h p r o c , t h e n c h e c k i f t h e f l a g — f i e l d o f r e a l i s #1; i t i s . (4) Both r e a l and r e f p r o c r e a l a r e i n s e r t e d t o t h e r e l a t e d mode l i s t ' r e t u r n * . (5) C o n s i d e r p r o c r e f r e a l a s b e f o r e and t h e f l a g - f i e l d o f r e a l i s #1; so p r o c r e f r e a l i s i n s e r t e d t o ' r e t u r n * ( r e a l i s t h e r e a l r e a d y ) . (6) C o n s i d e r r e f r e f r e a l as b e f o r e and t h e f l a g - f i e l d o f r e a l i s #1; so r e f r e f r e a l i s a l s o i n s e r t e d t o ' r e t u r n * . The mode l i s t ' r e t u r n ' c o n t a i n i n g r e a l , r e f p r o c r e a l , p r o c r e f r e a l and r e f r e f r e a l i s d e l i v e r e d . COERCION OF MODES 30 CHAPTER IV COERCION OF MODES U.1. The c o e r c i o n p r o c e s s : I n ALGOL 68, s i n c e t h e programmer i s a l l o w e d t o d e f i n e modes a c c o r d i n g t o t h e s y n t a x r u l e s £ 8 . 7 . 1 . 1 and 8. 7 . 2 . 1 ] , t h e c o e r c i o n p r o c e s s , t h a t i s t h e way i n which a mode c a n be t r a n s f o r m e d t o a n o t h e r , i s more c o m p l i c a t e d t h a n any o t h e r l a n g u a g e which does n o t a l l o w the programmer t o have t h i s f r e e d o m . T h e r e a r e f i v e p o s i t i o n s f o r c o e r c i o n : s t r o n g , f i r m , meek, weak and s o f t . The p o s i t i o n depends on t h e c o n t e x t . The c o e r c i o n p r o c e s s i s d e s c r i b e d i n t h e s y n t a x o f t h e l a n g u a g e [ 8 . 8 ] , A mode MS i s s a i d t c be c o e r c e a b l e f r o m a mode MB i f t h e r e i s a pat h i n t h e s y n t a x s u c h t h a t SORTETY MS b a s e *==> MB b a s e . G r a p h i c a l l y , t h e c o e r c i o n r o u t e s d e s c r i b e d by t h e s y n t a x a r e shown i n t h e f o l l o w i n g c h a r t which i s m o d i f i e d from p.208 o f f _ L ] . T h i s i s f o r t h e r e v i s e d s y n t a x . COERCION OF MODES 32 Because t h e l a n g u a g e a l l o w s t h e [ ] symbols t o be r e p l a c e d by () s y m b o l s , a p r o b l e m i s p o s e d . F o r example: y:=a ( i ) where whether a ( i ) i s a s l i c e o r a c a l l i s n o t known, b e c a u s e i d e n t i f i e r i d e n t i f i c a t i o n i s made a t t h e same t i m e a s t h e c o e r c i o n p r o c e s s . The q u e s t i o n i s whether t h e p o s i t i o n o f t h e 'a' i s s o f t o r weak. I n s u c h a c a s e , t h e a p o s t e r i o r i mode and t h e s o r t a r e n o t known, however t h i s p r o b l e m can be s o l v e d and i t s s o l u t i o n i n c l u d e d i n t h e c o e r c i o n p r o c e s s . 4.2. The a l g o r i t h m f o r c o e r c i o n : The f o l l o w i n g i s t h e g r a p h i c a l r e p r e s e n t a t i o n o f t h e main theme o f t h e a l g o r i t h m . Mr i s t h e a p r i o r i mode, ms i s t h e a p o s t e r i o r i mode. A s t a t e o f t h e s t a t e d i a g r a m i s a s f o l l o w s : i 1 1 (1) I 2(b) ViELy I (3) | i i w i t h (1) t h e c o e r c i o n s t e p (2) t h e c o n d i t i o n s f o r e n t r y t o t h i s s t a t e : (a) t h e form o f t h e mode under c o n s i d e r a t i o n , (b) t h e f o r m o f mr and COEBCION OF MODES 33 (c) c o e r c e n d and (3) t h e mode t o c o n s i d e r n e x t , s p e c i f i e d i n terms o f 2 ( a ) . Note t h a t t h e c o e r c i o n s t e p c a n be t a k e n o n l y when t h e c o n d i t i o n s i n (2) a r e s a t i s f i e d . In t h e g r a p h , i f mr i s s k i p , jump, n i l o r vacuum do t h e s t e p h i p p e d t o see i f i t i s c o e r c e a b l e o r n o t , o t h e r w i s e do t h e f o l l o w i n g : s e t t h e mode under c o n s i d e r a t i o n t o be ms, t h e n do (1) d e t e r m i n e t h e s t a t e (or s t a t e s ) t o be t a k e n by c h e c k i n g the c o n d i t i o n s o f (a) t h e mode under c o n s i d e r a t i o n , (b) t h e f o r m o f mr and (c) t h e c o e r c e n d . I f t h i s i s not t h e s t a r t i n g s t e p ( i . e . i f t h e mode under c o n s i d e r a t i o n i s not ms), t h e n t h e s t a t e t a k e n must be l e d t o t h r o u g h an arrow f r o m t h e p r e v i o u s s t a t e . ( n o t e t h a t t h e t h i c k b a r s a r e o f b o t h d i r e c t i o n s w h i l e t h e o t h e r l i n e s a r e one way o n l y ) . I f no p r o p e r s t a t e c a n be f o u n d t h e n , mr i s n o t c o e r c e a b l e t o ms and h a l t ; o t h e r w i s e , (2) t r a n s f o r m t h e c o n s i d e r e d mode as s p e c i f i e d , and (3) i f t h e c o n s i d e r e d mode i s t h e same as mr t h e n , mr i s c o e r c e a b l e t o ms and h a l t ; o t h e r w i s e , g o t o (1 ) . The s t e p t o be t a k e n may n o t be u n i q u e . F o r example: i f t h e c o n s i d e r e d mode i s row rowof b o o l , t h e n b o t h s t a t e s f o r •rowed* and 'widened* have t o be c o n s i d e r e d . COERCION OF MODES STRONG POSITION 34 |hipped| r i | rowed | r skip V—-7 1^  mr | rc l - j ~ r " J >• * 5 Ihippedj jump V-—J I mr | |hipped| /ref m \ n i l \----J r-M I ref- | Irowed | /ref [ ] \ uiV |ref m| | voided^ • void \ comorf 7 I mr | i i r T |voided j :1 "t r T I widened / com P i U— I xeal | TTZZ I widened| / real \ \-'J | int j r X T |widened| / [ ] b o c l \ V— I bits | i i void A |widened| /TI charA morf |non-proc| Jpart of | I nr | » "js J V 7 bytes FIRM ^POSITIOt r—•*—: 1 ;ION united | 'union <m1, . . . . f inn) m1,•..,mn and a l l sub-unions of the considered mode J i Z l Ide-ref-| | erenced j r m ref m J ref m J zz"J | de-pro-1 |cedured| r . . . proc m Iproc m| COERCION OF MODES MEEK POSITION ." f ^ " | depro-|, j c e d u r e d | r—\ . . . p r o c m V [ p r o c m| I r—"• * — T 1 d e r e f - | J e r e n c e d | r e f m V-—7 f i 1 r e f m | I „ i WEAK POSITION K | d e p r o - | | c e d u r e d | p r o c m | p r o c ni IT C7 J d e r e f - j | e r e n c e d 1 . . r e f r e f m o r . . r e f p r o c n. | r e f r e f J | m o r | I r e f | | p r o c n | L , 1 T SOFT POSITION I 1 | d e p r o - | |ce d u r e d | f—7~\ ... p r o c m V—J I p r o c m | COERCION OF MODES 36 The a l g o r i t h m f o r c o e r c i o n : I n p u t : mr: t h e a p r i o r i mode (the s o u r c e mode). ms: t h e a p o s t e r i o r i mode (the t a r g e t mode) o r a n u l l mode l i s t . s o r t : t h e p o s i t i o n . T h i s i s s t r o n g , f i r m , meek, weak o r s o f t . c o e r c e n d : t h i s t e l l s whether i t i s a comorf o r n o t . O u t p u t : a l o g i c a l v a l u e t o t e l l whether 'mr* i s ' s o r t ' l y c o e r c e a b l e t o 'ms* o r n o t . F u n c t i o n : i f a c o e r c i o n s t e p c a n be t a k e n , t h e c o e r c i o n word i s s t o r e d i n t h e ' c w ' - f i e l c l o f t h e mode. I f •mr' i s * s o r t * l y c o e r c e a b l e t o *ms* t h e n t h e c o e r c i o n s e g u e n c e i s g i v e n . S t e p l : l e t • r e t u r n 1 be a l o g i c a l v a l u e . Combine the grammar r u l e s f o r 'ms' and •mr» and a p p l y t h e e q u i v a l e n c e a l g o r i t h m . S t e p 2 : i f ' s o r t 1 i s " •», t h e n l e t t h e f i r s t p r e f i x o t h e r t h a n r e f o r p r o c o f 'mr* be p i , i f p i i s not row o r rowof and p i i s n o t p r o c p t h e n g o t o s t e p 1 9 , i f p i i s row o r rowof t h e n *scrt*:=weak o t h e r w i s e • s o r t ' : = f i r m . S t e p 3 : i f *ms* i s n u l l do s t e p 3 . a t o s t e p 3 . d o t h e r w i s e g o t o s t e p 5 . S t e p 3 . a : l e t x be *mr*. S t e p 3 . b : i f x i s p r o c m, t h e n s e a r c h - i n s e r t x t o ' i s ' , i . e . , i f x i s n o t i n 'ms* t h e n i n s e r t x t o the l i s t •ms* i n o r d e r , l e t x = m and g o t o s t e p 3 . b ; COERCION OF MODES 37 o t h e r w i s e , s t e p 3 . c : i f x i s r e f m t h e n do s t e p 3 . c . 1 t o s t e p 3 . d o t h e r w i s e g o t o s t e p 3 . d . S t e p 3 . c . 1 : i f ' s o r t ' i s f i r m o r meek t h e n , s e a r c h - i n s e r t x t o 'ms 1, l e t x = m and g o t o s t e p 3 . b ; o t h e r w i s e , s t e p 3 . c . 2 : i f ' s o r t * i s weak and i f m i s p r o c n o r r e f n t h e n , s e a r c h - i n s e r t x t o 'ms' , l e t x = m and g o t o s t e p 3 . c ; o t h e r w i s e , s t e p 3 . d : s e a r c h - i n s e r t x t o 'ms' and g o t o s t e p 2 2 . S t e p H . a : l e t n = 'mr'. S t e p U . b : mark n. I f n i s r e f x o r p r o c x and t h a t n c a n be ' s o r t ' l y d e p r o c e d u r e d o r d e r e f e r e n c e d , t h e n l e t n = x and g o t o s t e p 4 , b ; o t h e r w i s e , go t o s t e p 5 . Note t h a t when a mode b e g i n s w i t h p r o c , i t c a n be • s o r t ' l y d e p r o c e d u r e d ; when a mode b e g i n s w i t h r e f , i t c a n be s t r o n g l y , f i r m l y o r meekly d e r e f e r e n c e d , or weakly d e r e f e r e n c e d when t h e p r e f i x f o l l o w i n g r e f i s p r o c o r r e f . The a l g o r i t h m i s s i m i l a r t o s t e p I O t o s t e p 1 7 . S t e p 5 : i f • s o r t * i s " s o f t " t h e n g o t o s t e p 1 2 . I f ' s o r t * i s "weak" t h e n g o t o s t e p 1 4 . I f ' s o r t ' i s "meek" t h e n g o t o s t e p 1 6 . S t e p 6 : i f ' s o r t ' i s " s t r o n g " and 'mr* i s " s k i p " o r "jump", t h e n f l a g 'mr' and g o t o s t e p I O . S t e p 7 : i f * s o r t * i s " s t r o n g " and 'mr' i s ' n i l ' t h e n i f 'ms' s t a r t s w i t h ' r e f t h e n f l a g *mr* and go t o s t e p I O . S t e p 8 : i f ' s o r t * i s " s t r o n g " and 'mr* i s "vacuum", i f 'ms' COERCION OF MODES 38 s t a r t s w i t h 'row' o r ' r o w o f the n f l a g *mr* and g o t o s t e p l 0 . S t e p 9 : f l a g t h e n o n t e r m i n a l s y m b o l s i n the combined grammar a s f o l l o w s : I f ' s o r t * i s " s t r o n g " t h e n s t a r t i n s t a t e I o t h e r w i s e s t a r t i n s t a t e I I . Each s t a t e g i v e s t h e f l a g g i n g i n s t r u c t i o n s and t e l l s what f u r t h e r n o n t e r m i n a l s must be c o n s i d e r e d o r what f u r t h e r i n s t r u c t i o n s must be f o l l o w e d . The p r o c e s s s t o p s when t h e r e a r e no more n o n t e r m i n a l s t o be c o n s i d e r e d , o r when t h e r e a r e some more t e r m i n a l s t o be c o n s i d e r e d and t h e n o n t e r m i n a l b e i n g c o n s i d e r e d i s marked. COERCION OF MODES 39 STATE I : f l a g t h e n o n t e r m i n a l c o n s i d e r e d . C o n s i d e r new n o n t e r m i n a l s o r f o l l o w t h e i n s t r u c t i o n s a s f o l l o w s : i f t h e r i g h t s i d e o f the n i n t h e r u l e i s c o n s i d e r STATE row m m l rowof m m I rowof t o o l b i t s I I I rowof c h a r b y t e s I I I u n i o n m(1) n> (k) M1) , ••*# m (k) I I r e f m m IV compl r e a l I r e a l i n t I v o i d g o t o s t e p 1 8 o t h e r no o p e r a t i o n COERCION OF MODES 40 STATE I I : f l a g t h e n o n t e r m i n a l s C o n s i d e r new n o n t e r m i n a l s as f o l l o w s : i f t h e r i g h t s i d e o f t h e n t h e r u l e i s c o n s i d e r c o n s i d e r e d . i n STATE v o i d u n i o n m(1) ... m (k) o t h e r u n f l a g v o i d and g o t o s t e p I O m (1) , ...#m (k) no o p e r a t i o n I I STATE I I I : f l a g t h e n o n t e r m i n a l , n o n t e r m i n a l s t o be c o n s i d e r e d . No new STATE I V: do n o t f l a g t h e n o n t e r m i n a l . I f t h e r u l e f o r t h e c o n s i d e r e d n o n t e r m i n a l d o e s n o t s t a r t w i t h •row* o r »rowof' t h e n t h e r e i s n o t h i n g t o do. I f t h e r i g h t s i d e o f t h e r u l e i s row m o r rowof m t h e n , i f r e f m i s i n t h e grammar t h e n f l a g t h e n o n t e r m i n a l r e f m, c o n s i d e r t h e t e r m i n a l m i n STATE IV (even i f r e f m i s not i n t h e grammar). — — — — — —. — s t e p I O : l e t n = 'mr'. S t e p 1 1 : c o n s i d e r t h e n o n t e r m i n a l n. I f t h e n o n t e r m i n a l c o n s i d e r e d i s f l a g g e d ( i n s t e p 9 , s t e p 7 , s t e p 8 o r COERCION OF MODES s t e p 6 ) , t h e n *ms* i s STIRMly c o e r c e a b l e from 'mr* and s t o p , I f t h e r u l e f o r the c o n s i d e r e d n o n t e r m i n a l i s r e f m o r p r o c m, t h e n s e t n = m and g o t o s t e p 1 1 ; o t h e r w i s e , s t o p and 'ms* i s n o t STIRMly c o e r c e a b l e f r o m »mr*. S t e p 1 2 : l e t n * «mr». S t e p 1 3 : i f n = *ms* t h e n g o t o s t e p 2 2 . I f n = p r o c m t h e n s e t n = m and g o t o s t e p 1 3 , o t h e r w i s e g o t o step20» S t e p 1 4 : l e t n = 'mr». S t e p 1 5 : i f n = 'ms* t h e n goto s t e p 2 2 . I f n = p r o c m t h e n s e t n = m and g o t o s t e p 1 5 . I f n = r e f m and m = r e f p o r m = p r o c p t h e n s e t n = m and g o t o s t e p 1 5 . Goto s t e p 2 0 . S t e p 1 6 : l e t n = »mr*. S t e p 1 7 : i f n = *ms* t h e n g o t o s t e p 2 2 . I f n = p r o c m o r n = r e f m t h e n s e t n = m and g o t o s t e p l 7 , o t h e r w i s e g o t o s t e p 2 0 . S t e p 1 8 : (a) i f t h e a p o s t e r i o r i mode i s not v o i d t h e n u n f l a g v o i d , t h e mode under c o n s i d e r a t i o n and g o t o s t e p I O ( R . 8 . 2 . 3 . 1 . a ) , ( a f t e r v o i d i n g , no c o e r c i o n may t a k e p l a c e ) (R.8,2.4.1.and R.8.2,6.1) ; o t h e r w i s e (b) i f the c o e r c e n d 'mr* i s a c o m o r f , t h e n f l a g »mr», t h e a p r i o r i mode (R.8.2.8.1.a) and g o t o s t e p I O ; o t h e r w i s e , (c) i f t h e a p r i o r i mode »mr» ends w i t h n o n - p r o c v o i d (where n o n — p r o c i s any p r e f i x o t h e r t h a n proc) t h e n u n f l a g ' v o i d * (R.8.2.2.1.a) ( o n l y d e p r o c e d u r i n g COERCION OF MODES 42 can go b e f o r e v o i d i n g R.8.2. 1.1) and go t o s t e p I O ; o t h e r w i s e , (d) i f t h e a p r i o r i mode 'mr' i s n o t ' v o i d * o r doe s n o t end w i t h p r o c v o i d t h e n f l a g t h e mode f o l l o w i n g t h e l a s t p r o c o f 'mr* (R8.2. 1.b)and g o t o s t e p I O . S t e p 1 9 : g i v e an e r r o r message. S t e p 2 0 : r e t u r n := f a l s e . S t e p 2 1 : ' r e t u r n * i s t h e l o g i c a l v a l u e t c be r e t u r n e d . S t o p . S t e p 2 2 : r e t u r n : = t r u e and g o t o s t e p 2 1 . End o f c o e r c i o n a l g o r i t h m . 4.3. an example t o show how t h e c o e r c i o n p r o c e d u r e w orks: I n t h e program, t h e f l a g - f i e l d o f a mode i s used f o r m a r k i n g t h e t e r m i n a l i n s t e p 4 and p l a n t i n g the f l a g s i n s t e p 6 , s t e p 7 , s t e p 8 and s t e p 9 o f t h e a l g o r i t h m , t h e c w - f i e l d i s t o s t o r e t h e c o e r c i o n word and t h e l i n k - f i e l d i s used a s a backward l i n k so t h a t t h e c o e r c i o n s e q u e n c e c a n be o b t a i n e d from t h e c w - f i e l d s o f t h e modes t h r o u g h t h e l i n k - f i e l d . I n t h e program, t h e command t o c h e c k whether mode MR i s SORTly c o e r c e a b l e t o mode MS i s "COERCE" f o l l o w e d by t h e a p r i o r i mode, t h e a p o s t e r i o r i mode, t h e p o s i t i o n and t h e c o e r c e n d which t e l l s whether 'mr* i s a COMORF o r n o t . The a p r i o r i mode i s a mode r e p r e s e n t e d by a number and so i s t h e a p o s t e r i o r i mode. The p o s i t i o n i s " s t r o n g " , " f i r m " , "meek", "weak" o r " s o f t " . The c o e r c e n d i s e i t h e r " c o m o r f " COERCION OF MODES o r « Example: s u p p o s e t h e grammar e n t e r e d i s 16 " p r o c " 17 17 " r e f " 2 18 " u n i o n " 1 2 3 - 2 -2 . I f t h e command "COERCE" 16 18 " f i r m " " " i s e n t e r e d t h e n p r o c r e f i n t , r e f i n t and i n t a r e marked and t h e n MODE (18) i s changed from ONION | 0 I 17 | T NULL | — > L1 ] - J L J t o | ONION J L L-I 17 T L. | NOLL | -I L_ •> L1 where L1 i s 1 ~% i T — i r T 1 -> MODE ( 1 ) | -+-> | — > MODE (2) | -+-> | — > MODE (3) | NOLL] MODE{1) i s c h a n g e d f r o m | EOOL | I L-I L NULL NULL | to | BOOL | UNITE | T" — > T NULL 1 | MODE (17) j | M0DE(2) i s changed from COERCION OF MODES 44 |~ INT ~T~ " I " 0 ~T 2 T 0 T NULL T NULL ] I L ; 1 1 : I L L I t o I 1 T " 1 T T 1 1 T | INT | UNITE | 1 1 2 | 0 | — > | NULL | I I I ! ! | BODE ( 1 7 ) | | l— i 1 L 1 J . X J . MODE ( 3 ) i s n o t c o n s i d e r e d t h o u g h i t i s i n t h e l i s t o f modes t o be c o n s i d e r e d , b e c a u s e MODE (2) i s marked. Then MODE(16) i s c o n s i d e r e d : t h e f l a g - f i e l d i s # 0 , and t h e t e r m i n a l i s " p r o c " , t h e c o e r c i o n word i s d e p r o c e d u r e . MODE ( 1 7 ) i s c o n s i d e r e d : t h e f l a g - f i e l d i s # 0 , and the t e r m i n a l i s " r e f " , t h e c o e r c i o n word i s d e r e f e r e n c e . MODE (2) i s c o n s i d e r e d , and f l a g - f i e l d i s # 1 ; so MODE ( 1 8 ) i s f i r m l y c o e r c e a b l e f r o m MODE ( 1 6 ) and t h e c o e r c i o n s eguence i s d e p r o c e d u r e , d e r e f e r e n c e , u n i t e . I f t h e command "COERCE" 2 8 " s t r o n g " " " i s e n t e r e d , t h e n i n t i s marked and MODE (8 ) i s changed from 1 T T T ! 1 1 r 1 | STRUCTt | 0 | 8 J 2 | NULL | — > L 2 | to | ~ S T R U C T T ~ [ 1 1 8 T~ 2 1 N U I L "T~~> L2] I L : L I I I i X I where L2 i s |~—> MODE ( 1 0 ) T ~ H — > [ —>MODE (1 1)TNULL^| MODE ( 3 ) i s changed from COERCION OF MODES 45 P REAL T~ 1 0 T~ 3 1 0 T NOLL T NOLL ] « • 1 . 1 1 1 1 L I t o i T i I 1 T T r 1 I REAL 1 WIDEN | 1 | 3 | 0 | — > | NULL | J . i 1 1 , M ° D E ( 8 ) 1 1 MODE (2) i s c h a n g e d f r o m I 1 1 T 1 1 1 1 1 I INT | | 0 I 2 J 0 I NULL | NULL | to [~ INT | WIDEN r 1 " I " 2 j 0 T" — > T NULL ] I I I I I I MODE (3) | | 1 _t 1 1 1 1 1 L I MODE(2) i s c o n s i d e r e d a g a i n . S i n c e i t s f l a g - f i e l d i s #1, MODE (8) i s s t r o n g l y c o e r c e a b l e from MODE (2) and t h e c o e r c i o n s e q u e n c e i s widen, w i d e n . MODE BALANCING 46 CHAPTER V MODE BALANCING 5.1. B a l a n c i n g and i t s r e l a t e d o p e r a t i o n s : In s e r i a l c l a u s e s , c o l l a t e r a l c l a u s e s and c o n d i t i o n a l c l a u s e s , t h e r e i s a s p e c i a l f e a t u r e c o n c e r n i n g mode t h a t i s r e f l e c t e d by t h e r u l e s : R.6.1.1g: s u i t e o f FEAT CLAUSE t r a i n s : FEAT CLAUSE t r a i n ; FEAT CLAUSE t r a i n , c o m p l e t e r , s u i t e o f s t r o n g CLAUSE t r a i n s ; s t r o n g CLAUSE t r a i n , c o m p l e t e r , s u i t e o f FEAT CLAUSE t r a i n s . R.6.2.1d: f i r m c o l l a t e r a l row c f MODE c l a u s e : f i r m MODE b a l a n c e PACK. R.6.2.1e: f i r m MODE b a l a n c e : f i r m MODE u n i t , comma s y m b o l , s t r o n g MODE u n i t l i s t ; s t r o n g MODE u n i t , comma s y m b o l , f i r m MODE u n i t ; s t r o n g MODE u n i t , comma sym b o l , f i r m MODE b a l a n c e . R.6.4.1d: FEAT c h o i c e CLAUSE: FEAT t h e n CLAUSE, s t r o n g e l s e CLAUSE; s t r o n g t h e n CLAUSE, FEAT e l s e CLAUSE. T h i s f e a t u r e i s t h a t when t h e a p o s t e r i o r i mode and t h e p o s i t o n o f a s e r i a l , c o l l a t e r a l , c r c o n d i t i o n a l c l a u s e a r e g i v e n we have t o c h e c k whether t h e c o n s t i t u e n t s o f t h e c l a u s e a r e s y n t a c t i c a l l y c o r r e c t o r n o t . T h i s i s c a l l e d b a l a n c i n g o f t h e modes ( t h e a p r i o r i modes o f t h e c o n s t i t u e n t s ) t o t h e a p o s t e r i o r i mode which i s c a l l e d t h e b a l a n c e d mode. MODE BALANCING 47 I n b a l a n c i n g , i f a l i s t o f a p r i o r i modes i s g i v e n , t h e a p o s t e r i o r i mode and t h e s o r t ( p o s i t i o n ) a r e a l s o g i v e n , ( t h e l a s t two a r e n o t n e c e s s a r i l y g i v e n and t h i s w i l l be d i s c u s s e d l a t e r ) t h e n we c a n c h e c k whether t h e l i s t o f a p r i o r i modes can be ' s o r t ' l y b a l a n c e d t o the a p o s t e r i o r i mode by c h e c k i n g : (1) t h a t e a c h o f t h e a p r i o r i modes i s s t r o n g l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode and (2) t h a t one o f t h e a p r i o r i modes i s ' s o r t ' l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode i f s o r t i s n o t s t r o n g . F o r example: boo 1 a; r e a l x; x: = (a | 3 J 0. 3) ; where we have a c o n d i t i o n a l c l a u s e , ( a | 3 | 0 . 3 ) , whose p o s i t i o n i s s t r o n g , t h e a p o s t e r i o r i mode i s r e a l and t h e a p r i o r i modes a r e i n t and r e a l . Sometimes t h e a p o s t e r i o r i mode i s n o t known. F o r example: i n t y; r e a l x; x:=(x>0 Jy|x)+3 ; where t h e a p o s t e r i o r i mode o f t h e c o n d i t i o n a l c l a u s e (x>0jy|x) i s n o t known. I n s u c h a c a s e , a p o s s i b l e l i s t o f a p o s t e r i o r i modes can be s u p p l i e d . Thus we have t o e x t e n d t h e meaning o f b a l a n c i n g s u c h t h a t when a l i s t o f a p o s t e r i o r i modes which may be n u l l o r a s i n g l e t o n , t h e p o s i t i o n and a l i s t o f a p r i o r i modes a r e g i v e n , b a l a n c i n g i s t o f i n d a mode o r some modes o r t o i d e n t i f y a mode o r some modes o f t h e l i s t o f a p o s t e r i o r i modes t o which t h e l i s t o f a p r i o r i modes c a n be ' s o r t ' l y b a l a n c e d . MODI BALANCING 48 In y:=(x>0|a|b) ( i ) ; whether a ( i ) and b ( i ) a r e s l i c e s o r c a l l s may n o t y e t be known. I n s u c h a c a s e , t h e p o s i t i o n and t h e a p o s t e r i o r i mode a r e n o t g i v e n and we have t o d e t e r m i n e whether t h e p o s i t i o n i s weak o r s o f t and t o p r o v i d e a p o s s i b l e l i s t o f a p o s t e r i o r i modes. In a d d i t i o n t o t h e above, c o l l a t e r a l c l a u s e s s h o u l d a l s o be t a k e n c a r e o f he r e b e c a u s e a c o n s t i t u e n t may be a c o l l a t e r a l c l a u s e e .g. [ 1 : 3 ] r e a l a 1 , b c o l p; a1 := (p| (1, 2. 2, 3) | (1, 2, 3) ) ; . I f t h e l i s t o f a p o s t e r i o r i modes ( p o s s i b l y n u l l ) and t h e p o s i t i o n a r e g i v e n when a c o l l a t e r a l d i s p l a y ( i . e . a l i s t o f a p r i o r i modes) i s g i v e n , t h e j o b o f t h e p r o c e d u r e • c o l l a t e r a l * i s t o f i n d o r t o i d e n t i f y f r o m t h e a p o s t e r i o r i mode l i s t , a mode o r some modes which c a n be c o e r c e d f r o m a row o r s t r u c t u r a l d i s p l a y made up o f t h e e l e m e n t s o f t h e a p r i o r i mode l i s t . 5.2. The a l g o r i t h m s : I n t h e f o l l o w i n g a l g o r i t h m s , t h e o p e r a t i o n s AND and OR between two b o o l e a n v e c t o r s p r o d u c e s t h e v e c t o r r e s u l t o f a P p l y i n 9 them between c o r r e s p o n d i n g e l e m e n t s o f t h e v e c t o r s . B a l a n c e A l g o r i t h m : I n p u t : p a r a m e t e r l i s t : a l i s t o f n o n t e r m i n a l s y m b o l s which r e p r e s e n t t h e a p o s t e r i o r i modes (may be n u l l ) . o p e r a n d l i s t : a l i s t o f modes which a r e t h e a p r i o r i modes. MODE BALANCING 49 s o r t : s t r o n g , f i r m , meek, weak o r s o f t , O u t p u t : a b o o l e a n v e c t o r s e l e c t i n g t h e e l e m e n t s o f t h e »pa r a m e t e r l i s t • f o r which a ' s o r t * b a l a n c e o f t h e ' o p e r a n d l i s t ' c a n be f o u n d . F u n c t i o n : i f ' s o r t * i s n u l l t h e n a s s i g n weak o r meek t o ' s o r t ' i f t h e a p r i o r i mode c o n t a i n s a s l i c e o r a c a l l , o r g i v e an e r r o r message i f t h e a p r i o r i mode d o s e n ' t . I f t h e ' p a r a m e t e r l i s t * i s n u l l , t h e n a l i s t o f p o s s i b l e b a l a n c e d mode i s a s s i g n e d t o t h e ' p a r a m e t e r l i s t *. S t e p l : r a v e l t h e ' o p e r a n d l i s t * , i . e . i f t h e l i s t c o n t a i n s an e l e m e n t which i s a s e t o f modes t o be b a l a n c e d t h e n r e p l a c e t h i s by t h e s e t o f modes. T h i s p r o c e s s i s s i m i l a r t o t h e r a v e l i n g o f u n i o n s . T h i s c a n be done b e c a u s e i n * s o r t * b a l a n c i n g a l l o f t h e a p r i o r i modes must be s t r o n g l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode and o n l y one o f t h e a p r i o r i mode must be ' s o r t ' l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode. I f one o f t h e a p r i o r i modes i s a b a l a n c e p ack, t h i s i s e i t h e r ' s o r t ' l y c o e r c e a b l e o r s t r o n g l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode. I n t h e f i r s t c a s e , a l l t h e o t h e r a p r i o r i modes a r e s t r o n g l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode and a l l t h e c o n s t i t u e n t s o f t h e b a l a n c e pack a r e s t r o n g l y c o e r c e a b l e w i t h one ' s o r t ' l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode. I n t h e s e c o n d c a s e , one o f the o t h e r a p r i o r i modes i s ' s o r t ' l y c o e r c e a b l e t o and MODE B&IaNCING 50 a l l t h e o t h e r s t o g e t h e r w i t h t h e c o n s t i t u e n t s o f t h e b a l a n c e pack a r e s t r o n g l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode. S t e p 2 : i f ' s o r t ' i s not g i v e n , t h e n l e t mi be t h e f i r s t mode o t h e r t h a n s k i p , jump, n i l o r vacuum i n t h e ' o p e r a n d l i s t ' ; l e t t h e f i r s t p r e f i x o t h e r t h a n r e f c r p r o c o f mi be p i . I f p i i s row o r rowof t h e n •so r t ; ' := weak, i f p i i s p r c c p t h e n ' s o r t ' :=f i r m o t h e r w i s e g o t o s t e p 1 1 . S t e p 3 : i f ' p a r a m e t e r l i s t * i s n u l l and i f t h e ' s o r t * i s n o t s t r o n g and not f i r m t h e n l e t k be t h e number o f modes i n t h e ' o p e r a n d l i s t ' and f o r i:=1 t o k do s t e p 3 . a t o s t e p 3 . d below; o t h e r w i s e , g o t o s t e p U . S t e p 3 . a : l e t x be t h e n o n t e r m i n a l r e p r e s e n t i n g o p e r a n d ( i ) . S t e p 3 . b : i f x i s p r o c m, t h e n s e a r c h - i n s e r t x t o t h e ' p a r a m e t e r l i s t * , l e t x = m and g o t o s t e p 3 . b ; o t h e r w i s e , s t e p 3 . c : i f x i s r e f m t h e n do s t e p s 3.c. 1, 3.c.2; o t h e r w i s e , g o t o s t e p 3 . d . S t e p 3 . c . 1 : i f ' s o r t ' i s f i r m o r meek t h e n s e a r c h - i n s e r t x t o t h e ' p a r a m e t e r l i s t * , l e t x = m and g o t o s t e p 3 , b ; o t h e r w i s e , s t e p 3 . c . 2 : i f * s o r t * i s weak and i f m i s p r o c n o r m i s r e f n t h e n s e a r c h i n s e r t x t o t h e ' p a r a m e t e r l i s t ' , l e t x = m and g o t o s t e p 3 . b ; o t h e r w i s e , s t e p 3 . d : s e a r c h - i n s e r t x t o t h e ' p a r a m e t e r l i s t ' . Operand ( i ) has been c o m p l e t e l y p r o c e s s e d i n f o r m i n g MODE BALANCING 51 t h e p a r a m e t e r l i s t . S t e p 4 : l e t n be t h e number o f e l e m e n t s i n t h e • p a r a m e t e r l i s t L e t c h e c k _ h i p be a v e c t o r o f 4 b o o l e a n v a l u e s , w h i c h a r e f o r • s k i p 1 , * jump*, ' n i l ' and 'vacuum*. Any one c f them i s i n t h e * o p e r a n d l i s t * i f and o n l y i f t h e c o r r e s p o n d i n g v a l u e i s t r u e . S t e p 5 : l e t s t r o n g _ m a t r i x be a b o o l e a n m a t r i x o f d i m e n s i o n nXm where m i s t h e number o f modes d e f i n e d . S t r o n g _ m a t r i x i s formed i n the f o l l o w i n g way: s t e p 5 . a : f o r j:=1 t o n do t h e f o l l o w i n g : s t e p 5 . a . 1 : u n f l a g a l l t h e f l a g s o f t h e modes. S t e p 5 . a . 2 : c r e a t e a s e t o f f l a g s as d i r e c t e d by s t e p 9 o f t h e c o e r c i o n a l g o r i t h m , s t a r t i n g f r o m s t a t e I w i t h p a r a m e t e r (j) as t h e n o n t e r m i n a l c o n s i d e r e d , and i f c h e c k _ h i p i s not a l l f a l s e , t h e n t h e s e t o f f l a g s i s m o d i f i e d by f o l l o w i n g s t e p 5 , s t e p 6 , o r / a n d s t e p 8 o f t h e c o e r c i o n a l g o r i t h m . S t e p 5 . a . 3 : s t r o n g _ m a t r i x ( i , n - j ) := f l a g (mode ( i ) ) , f o r i = 1,... , m. S t e p 5 . a . 4 : p a r a m e t e r (j) has been c o m p l e t e l y p r o c e s s e d . S t e p 6 : i f »sort* i s s t r o n g t h e n g o t o s t e p 7 o t h e r w i s e l e t «sort_matrix* be a b o o l e a n m a t r i x o f d i m e n s i o n nXm. ' s o r t _ m a t r i x ' i s formed i n t h e f o l l o w i n g way: s t e p 6 . a : f o r j:=1 t o n do t h e f o l l o w i n g : s t e p 6 . a . 1 : u n f l a g a l l t h e f l a g s o f t h e modes. S t e p 6 . a . 2 : c r e a t e a s e t o f f l a g s as d i r e c t e d by s t e p 9 o f MODE BALANCING 52 t h e c o e r c i o n a l g o r i t h m . S t a r t i n s t a t e I I i f ' s o r t 1 i s f i r m e l s e i n s t a t e I I I w i t h p a r a m e t e r ( j ) a s t h e n o n t e r m i n a l under c o n s i d e r a t i o n . S t e p 6 . a . 3 : »sort_matrix* ( i , n - j ) := f l a g ( m o d e ( i ) ) , f o r i = 1 , . . . , m. S t e p 6 . a . U : p a r a m e t e r (j) has been c o m p l e t e l y p r o c e s s e d . S t e p 7 : l e t fl, B be b o o l e a n v e c t o r s o f n e l e m e n t s ; A be a l l t r u e and B a l l f a l s e . L e t k be t h e number o f e l e m e n t s i n t h e ' c p e r a n d l i s t * . S t e p 8 : f o r i:=1 t o k do s t e p 8 . a t o s t e p 8 . f . S t e p 8 . a : l e t C, D be b o o l e a n v e c t o r s o f l e n g t h n. S t e p 8 . b : i f o p e r a n d ( i ) i s a d e f i n e d mode t h e n l e t 11 be t h e n o n t e r m i n a l o f o p e r a n d ( i ) , C := 1 1 - t h row o f s t r o n g - m a t r i x ; o t h e r w i s e , g o t o s t e p 8 . c . S t e p 8 . b . 1 : l e t o p e r a n d ( i ) be x. S t e p 8 . b . 2 : i f x = r e f m o r p r o c m t h e n l e t 12 be t h e n o n t e r m i n a l o f m, D := 1 2 - t h row o f s t r o n g _ m a t r i x , C := C OB D, l e t x := m and g o t o s t e p 8 . b . 2 ; o t h e r w i s e g o t o s t e p 8 . d . S t e p 8 . c : i f o p e r a n d ( i ) i s a c o l l a t e r a l c l a u s e t h e n C := c o l l a t e r a l ( p a r a m e t e r l i s t , t h e l i s t o f modes o f th e c o l l a t e r a l c l a u s e , s t r o n g ) o t h e r w i s e g o t o s t e p 8 . f . S t e p 8 . d : A := A and C. S t e p 8 . e : i f ' s o r t 1 i s s t r o n g t h e n g o t o s t e p 8 . f . S t e p 8 . e . 1 : i f o p e r a n d ( i ) i s a d e f i n e d mode then C := t h e 1 1 - t h row o f »sort_matrix' o t h e r w i s e g o t o MODE BALANCING 53 s t e p 8 . e . 5 . S t e p 8 . e . 2 : l e t o p e r a n d ( i ) be x. S t e p 8 . e . 3: i f x = p r o c m o r i f x = r e f m and x c a n be • s o r t ' l y d e r e f e r e n c e d t h e n D := 1 2 - t h row o f • s o r t _ m a t r i x • ; o t h e r w i s e g o t o s t e p 8 , e . 6 . S t e p 8 . e , 4 : C := C OB D, l e t x := m and go t o s t e p 8 . e . 3 . S t e p 8 . e . 5 ; C := c o l l a t e r a l ( p a r a m e t e r l i s t , t h e l i s t o f modes o f t h e c o l l a t e r a l c l a u s e , ' s o r t ' ) . S t e p 8 . e . 6 : B := B OR C. S t e p 8 . f : o p e r a n d ( i ) has been c o m p l e t e l y p r o c e s s e d , S t e p 9 : i f ' s o r t * i s not s t r o n g t h e n A := A AND B. S t e p I O : r e t u r n the b o o l e a n v e c t o r A and s t o p . S t e p l 1 : g i v e an e r r o r message. L e t A be a l l f a l s e . Goto s t e p I O . End o f t h e b a l a n c e a l g o r i t h m . C o l l a t e r a l A l g o r i t h m : I n p u t : p a r a m e t e r l i s t : a l i s t o f n o n t e r m i n a l symbols o f modes which a r e t h e a p o s t e r i o r i modes, o p e r a n d l i s t : a l i s t o f n o n t e r m i n a l s y m b o l s o f modes which a r e t h e a p r i o r i modes, s o r t : s t r o n g , f i r m , meek, weak o r s o f t . O u t p u t : a b o o l e a n v e c t o r s e l e c t i n g t h e e l e m e n t s o f • p a r a m e t e r l i s t ' w h i c h c a n be ' s o r t ' l y b a l a n c e d from t h e c o l l a t e r a l mode d i s p l a y ' o p e r a n d l i s t * . MODE BALANCING 54 F u n c t i o n : i f t h e ' p a r a m e t e r l i s t ' i s n u l l , a l i s t o f p o s s i b l e b a l a n c e d mode i s a s s i g n e d t o ' p a r a m e t e r l i s t ' . S t e p l : c r e a t e a b o o l e a n v e c t o r 'row', o f which an e l e m e n t i s t r u e i f and o n l y i f t h e c o r r e s p o n d i n g e l e m e n t o f • p a r a m e t e r l i s t ' b e g i n s w i t h row o r r o w o f . I f • s o r t 1 i s s t r o n g , c r e a t e a b o o l e a n v e c t o r ' s t r u c t * c f which an e l e m e n t i s t r u e i f and o n l y i f t h e c o r r e s p o n d i n g e l e m e n t o f ' p a r a m e t e r l i s t * b e g i n s w i t h s t r u c t . I f ' p a r a m e t e r l i s t * i s n u l l t h e n i n s e r t a l l t h e d e f i n e d modes b e g i n n i n g w i t h row o r rowof t o t h e ' p a r a m e t e r l i s t ' . S t e p 2 : l e t ' p l i s t ' be a l i s t o f modes s u c h t h a t ' p l i s t ' and ' p a r a m e t e r l i s t ' a r e o f t h e same l e n g t h and i f an e l e m e n t o f ' p a r a m e t e r l i s t ' i s row m o r rowof m t h e n t h e c o r r e s p o n d i n g e l e m e n t o f ' p l i s t * i s m, o t h e r w i s e t h e c o r r e s p o n d i n g e l e m e n t o f ' p l i s t * i s t h e p s e u d o -mode (modeO) which i s not a d e f i n e d mode, b u t c o n s i d e r e d a s a mode i n t h e l i s t . L e t ' g l i s t ' be a cop y o f ' o p e r a n d l i s t * . S t e p 3 : l e t B be a b o o l e a n v e c t o r . B := b a l a n c e ( p l i s t , g l i s t , s o r t ) . S t e p 4 : i f * s o r t ' i s not s t r o n g c r ' s t r u c t * i s a v e c t o r o f f a l s e v a l u e s t h e n goto s t e p 7 . I f ' s o r t ' i s s t r o n g and ' s t r u c t ' n ot a l l f a l s e t h e n l e t ' p l i s t ' be a l i s t o f modes s u c h t h a t ' p l i s t * and ' p a r a m e t e r l i s t ' a r e o f t h e same l e n g t h and i f an e l e m e n t o f ' p a r a m e t e r l i s t * i s s t r u c t ml m2 ... Mk and k i s MODE BALANCING 55 e g u a l t o t h e number o f e n t r i e s i n ' o p e r a n d l i s t * t h e n t h e c o r r e s p o n d i n g e l e m e n t of ' p l i s t * i s s t r u c t ml ... Mk, o t h e r w i s e t h e c o r r e s p o n d i n g e l e m e n t o f • p l i s t ' i s t h e pseudo mode. S t e p 5 : l e t A be a b o o l e a n v e c t o r o f which an e l e m e n t i s t r u e i f and o n l y i f t h e c o r r e s p o n d i n g e l e m e n t o f p l i s t i s a mode ( i . e . not t h e pseudo mode). I f A i s a l l f a l s e t h e n g o t o s t e p 6 . F o r i;=1 t o k do s t e p 5 . a t o s t e p 5 . g . S t e p 5 . a : c r e a t e a new mode l i s t ' r l i s t ' o f t h e same l e n g t h a s ' p l i s t ' s u c h t h a t i f an e l e m e n t o f * p l i s t ' i s a d e f i n e d mode t h e n t h e c o r r e s p o n d i n g e l e m e n t o f • r l i s t * i s t h e i - t h f i e l d o f t h a t mode o f ' p l i s t ' (which i s a s t r u c t u r e ) o t h e r w i s e i t i s t h e ps e u d o -mode modeO. S t e p 5 . b : f o r ea c h mode o t h e r t h a n modeO o f ' r l i s t ' , jump o v e r t h e s e l e c t o r t o g e t the mode. S t e p 5 . c : c r e a t e a b o o l e a n v e c t o r ' c h e c k _ h i p * as i n s t e p 4 o f t h e b a l a n c e a l g o r i t h m . S t e p 5 . d : l e t s t r o n g _ m a t r i x be a b o o l e a n m a t r i x o f d i m e n s i o n nXm a s t h a t i n s t e p 5 o f t h e b a l a n c e a l g o r i t h m by d o i n g s t e p S . a o f b a l a n c e a l g o r i t h m w i t h n := number o f e l e m e n t s i n * r l i s t ' (the same a s i n ' p a r a m e t e r l i s t ' ) . S t e p 5 . e . 1 : l e t c be a b o o l e a n v e c t o r o f l e n g t h n, S t e p 5 . e . 2 . a : i f o p e r a n d ( i ) i s a d e f i n e d mode t h e n , l e t 11 be t h e n o n t e r m i n a l o f o p e r a n d ( i ) , C := 1 1 - t h row o f MODE BALANCING 56 s t r o n g _ m a t r i x ; o t h e r w i s e g o t o s t e p 5 . e . 3 . S t e p 5 . e . 2 . b : l e t o p e r a n d ( i ) be x. S t e p 5 . e . 2 . c : i f x = r e f m o r x = p r o c m t h e n , l e t 12 be t h e n o n t e r m i n a l o f m, D := 1 2 - t h row o f s t r o n g _ m a t r i x , C := C OR D, l e t x = m and g o t o s t e p 5 . e . 2 . c ; o t h e r w i s e g o t o s t e p 5 . f . S t e p 5 . e . 3 : i f o p e r a n d ( i ) i s a c o l l a t e r a l c l a u s e t h e n C := c o l l a t e r a l ( r l i s t , l i s t o f modes o f t h e c o l l a t e r a l c l a u s e o f ope r a n d ( i ) , " s t r o n g " ) ; o t h e r w i s e , s t e p 5 . e . 4 : i f o p e r a n d ( i ) i s a s e r i a l o r a c o n d i t i o n a l c l a u s e t h e n , C := b a l a n c e ( r l i s t , l i s t o f modes o f t h e c l a u s e o f o p e r a n d ( i ) , " s t r o n g " ) ; o t h e r w i s e g o t o s t e p 5 . g . S t e p 5 . f : A := A AND C, i f A i s a l l f a l s e , t h e n g o t o s t e p 7 . S t e p 5 . g : o p e r a n d ( i ) has been c o m p l e t e l y p r o c e s s e d t h a t i s t h e i - t h f i e l d o f t h e s t r u c t u r e has been c o m p l e t e l y p r o c e s s e d . S t e p 6 : B := B OR A s t e p 7 : r e t u r n t h e b o o l e a n v e c t o r B and s t o p . End o f t h e c o l l a t e r a l a l g o r i t h m . 5.3. E x a mples t o show how t h e p r o c e d u r e s work: In t h e pro g r a m , i n s t e a d o f a b o o l e a n m a t r i x , a v e c t o r o f b i t s t r i n g s i s formed so t h a t a row o f t h e m a t r i x i n t h e a l g o r i t h m i s but a b i t s t r i n g . • b a l a n c e * and • c o l l a t e r a l * a r e two s u b r o u t i n e s and b i t s t r i n g s a r e r e t u r n e d by them. MODE BALANCING 57 When t h e command i s "BALANCE" f o l l o w e d by t h e o p e r a n d l i s t , t h e s o r t and the p a r a m e t e r l i s t , • b a l a n c e ' i s c a l l e d and a s u b l i s t o f t h e p a r a m e t e r l i s t ( i f i t was n o t n a i l ) o r a l i s t o f modes t o ea c h o f which t h e o p e r a n d l i s t c a n be b a l a n c e d w i l l be g i v e n . When t h e command i s "COLLATESAL" f o l l o w e d by t h e o p e r a n d l i s t , t h e s o r t and t h e p a r a m e t e r l i s t , ' c o l l a t e r a l * i s c a l l e d and a s u b l i s t o f t h e p a r a m e t e r l i s t o r a l i s t o f modes t o each c f w h i c h t h e o p e r a n d d i s p l a y c a n be b a l a n c e d w i l l be g i v e n . Example: s u p p o s e t h e mode grammer e n t e r e d i s 16 " r e f " 3 17 " p r o c " 3 18 " r e f " 17 19 " r o w o f " 3 20 " r o w o f " 2 -2. When t h e command "BALANCE" 17 18 1 9 - 2 " f i r m " -2 i s e n t e r e d t h e n (1) As M0DE(17), MODE (18) and MODE (19) a r e modes, n o t h i n g i s done by ' r a v e l * . (2) The p a r a m e t e r l i s t i s n u l l and s o r t i s f i r m , t h e n t h e p a r a m e t e r l i s t i s formed a s f o l l o w s : MODE (17) i s r e f r e a l , s o r e f r e a l and r e a l a r e i n s e r t e d t o t h e ' p a r a m e t e r l i s t ' . MODE (18) i s r e f p r o c r e a l , s o r e f p r o c r e a l , p r o c r e a l and r e a l a r e i n s e r t e d t o t h e ' p a r a m e t e r l i s t ' . MODE BALANCING 58 MODE(19) i s ro w o f r e a l , so rowof r e a l i s i n s e r t e d t o t h e p a r a m e t e r l i s t . The ' p a r a m e t e r l i s t ' i s now r e a l , r e f r e a l , p r o c r e a l , r e f p r o c r e a l , and rowof r e a l . (3) t h e s t r o n g _ m a t r i x i s formed a s f o l l o w s : ( i ) 'check_hip« i s #0 a s none o f s k i p , jump, n i l and vacuum a p p e a r s i n t h e o p e r a n d l i s t . ( i i ) t h e l a s t column ( i . e . t h e 32nd column) i s (00010000000000000000) * t where ( a b ) * t means r i I a J I fc | S i n c e r e a l i s t h e a p o s t e r i o r i mode i n ' p o s t ' o n l y t h e f l a g f i e l d o f r e a l i s s e t t o #1, t h a t i s f l a g (MODE(3)) i s #1, t h e r e f o r e t h e f o u r t h e l e m e n t i s 1, t h e o t h e r s a r e z e r o f o r t h i s c o lumn. ( i i i ) t h e 3 1 s t column i s (00000000000000001000)*t s i n c e r e f r e a l , t h a t i s MODE (16) i s t h e a p o s t e r i o r i mode i n ' p o s t * s o t h e 17th ele m e n t o f t h i s column i s 1, the o t h e r s a r e z e r o f o r t h i s c o l u m n . ( i v ) s i m i l a r i l y t h e 30th column i s (00000000000000000100)*t, t h e 2 9 t h i s (00000000000000000010)*t and t h e 2 8 t h i s (00010000000000000001) * t . E n t r i e s e l s e w h e r e a r e z e r o . (4) t h e s o r t _ m a t r i x i s formed l i k e s t r o n g _ m a t r i x and t h e s o r t _ m a t r i x i s t h e same as s t r o n g _ m a t r i x e x c e p t t h a t s o r t _ m a t r i x (3,28) i s 0 w h i l e s t r o n g _ m a t r i x ( 3 , 2 8 ) i s 1. T h i s i s b e c a u s e i n p o s t i n g f l a g s f r o m rowof r e a l , r e a l i s f l a g g e d CD ii U l > II o _» o _» o —» o —> o -» O -a o o -* O —» o -» o -» o -» o —* o — o -* o -» o -» O — a O -k O — i o -» o —» o o -» o -* o —> o -» o -» o -» o -» O —k o ~-•-a tr (0 Hi H 5 I a o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o h o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o X o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o H* o o o o o o o o o o o o o o o o o o o CO o o o o o o o © o o o o o o o © o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o tn o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o Hi o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o £ o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o _ ^ o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o h o o o © o o o o o o o o o o o o h o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o —» o o o i-3 Hi sr O (0 h rt- rt-H H O O D £3 -» I © O O O O O O O O O O O O O O O O O O O B cr O O O O O O O O O O O O O O O O O O O O 01 c O O O O O O O O O O O O O O O O O O O O rt- rt-O O O O O O O O O O O O O O O O O O O O H O O O O O O O O O O O O O O O O O O O O H- 3 O O O O O O O O O O O O O O O O O O O O !X o O O O O O O O O O O O O O O O O O O O O rt-O O O O O O O O O O O O O O O O O O O O H-O O O O O O O O O O O O O O O O O O O O tn Hi O O O O O O O O O O O O O O O O O O O O o O O O O O O O O O O O O O O O O O O O O Q» H O O O O O O O O O O O O O O O O O O O O to 3 O O O O O O O O O O O O O O O O O O O O Hi o O O O O O O O O O O O O O O O O O O O O Hi t ) O O O O O O O O O O O O O O O O O O O O O H n O O O O O O O O O O O O O O O O O O O O l-» B O O O O O O O O O O O O O O O O O O O O t—' • CD O O O O O O O O O O O O O O O O O O O O O 3» o o o o o o o o o o o o o o o o o o o o e f O O O O O O O O O O O O O O O O O O O O W <f O O O O O O O O O O O O O O O O O O O O •• si o o o o o o o o o o o o o o o o o o o o n O O O O O O O O O O O O O O O O O O O O H O O O O O O O O O O O O O O O O O O O O 52 O O O O O O O O O O O O O O O O O O O O tn O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O -»ooooooooooooooo-»ooo o - » o o o o o o o o o o o o o o o o o o O O - i O O O O O O O O O O O O O O O O O O O O - i O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O — » o o o ___________ _ __ D 80 8 = 9 "(101.10000000000000000000000000000) = (L0000000000000000000000000000000) HO (OOL000000000000000000 00000000000) HO (OOOLOOOOOOOOOOOOOOOOOOOOOOOOOOOO) = D (t01Ot000000000000000000000000000) = (tOUL OOOOOOOOOOOOOOOOOOOOOOOOOOO) as? (10101000000000000000000000000000) = D am ? = ? * (totuooooooooooooooooooooooooooo) = (t0001OOOOOOOOOOOOOOOOOOOOOOOOOOO) HO (00100000000000 000000000000000000) HO (00010000000000000000000000000000) = D p a j s p x s a o o S T oozd JBI ' (z) pueaado (/.) •(LOLOOOOOOOOOOOOOOOOOOOOOOOOOOOOO) = D HO I = 1 (10100000000000000000000000000000) = (Iooooooooooooooooooooooooooooooo) HO (00100000000000000000000000000000) = D (toioiooooooooooooooooooooooooooo) = (I 0101ooooooooooooooooooooooooooo) ao ( i i m u u i i u i u i u u i i u i u i u i ) = dot oi ooooooooooooooooooooooooooo) = Uoooiooooooooooooooooooooooooooo) HO (001.00000000000000000000000000000) = 3 p a c t s p t s u c o s i x e a j o o i d ' (|.) p u e j a d o (9) 09 sttioRvivg aaow • j e a i * } U T *}ux S T ^ STXpueaedo aq} ajaqw {}IOS'^sTXPacrrado'^syxd)aoaexeq = g (e) « } U T 'xeaa S U T B ^ H O D } S T X aq:». *a-x Z- Z Z = *4STl3» (£) '(00000000000000000000000000000000) = iPt»ns t ' (UOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO) = .«o3, ( i ) uaq} '2- 02 6t ««3TJu 2- £ 3 Z i i l V S a i V H O D n s i pueinaico aq} uaqM •apom paouexeq aq^ S T x E a* J O M O J *a*T *x e a j j o H o i :}aamar.a auo saTB^uoa paujn^aj aq c-} + S J X aqi (oi) *(00001000000000000000000000000000) = doiiiooooooooooooooooooooooooooo) an* (ooootooooooooooooooooooooooooooo) = a OKY v = v (6) (totuooooooooooooooooooooooooooo) = 3 80 a = 8 (00001000000000000000000000000000) = D (oooot000000000000000000000000000) = D V = ¥ (00001000000000000000000000000000) = D pajapxsaoo S T X E 9 3 jOKoa * (e) puBjtado (g) •(10L10000000000000000000000000000) = doit 00000 00 000 000 00 00 00 000 0000 00) ao Uoiooooooooooooooooooooooooooooo) = 19 DHIDRtflVa saow o II o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 0> as o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o O O o o O O o o o o O O o o O O O O o o o o o o O O o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o a o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o -» -» o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o J i-3 cr (0 M o ii rt I s 0> rt i i H-X H « W i-3 cr (0 Ui rt-H o 3 I o o o o o o o o o o o © o o o o o o o o s o o o o o o o o o o o o o o o o o o o o fl) o o o o o o o o o o o o o o o © o o o © r t o o o o o o o o o o o o o o o o © o o o rt o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o © o o o o o o X! o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o w o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o 3 o © o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o a o o o o o o o o o o o o o o © o o o o o o o o o o o o o © o o o o o o o o o © o o o o o o o o o © o © o o o © o o o o o w o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o © o © © o o o o o r> o o o o o © o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o © o 23 o o o o o o o o o o o o o o o o o o o o n o o o o o o o o o o o o o o o o o o o o H o o o o o o o © o © o o o o o o o o o o 52S o o o o o o o o o o o o o o o o o o o o cn o o o o o o o o o o © o o o o o o o o o o o o o o o © o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o _ » o o o o o o o o o o o o o o o o o o — » -A o o ON to MODE BALANCING 63 (00000000000000000000000000000011) AND (00000000000000000000000000000001) = (0000000000000000000000 0000000001) B = (00000000000000000000000000000010) OR (00000000000000000000000000000010) OR (000000000000000000 00000000000001) = (00000000000000000000000000000011) A = A AND B = (00000000000000000000000000000001) (4) The l i s t t o be r e t u r n e d c o n t a i n s rowof r e a l o n l y . OPERATOR IDENTIFICATION 64 CHAPTER VI OPERATOR IDENTIFICATION 6.1. O p e r a t o r i d e n t i f i c a t i o n : ALGOL 68 a l l o w s t h e programmer t o d e f i n e new o p e r a t o r s o r t o e x t e n d t h e d e f i n i t i o n o f e x i s t i n g o p e r a t o r s t c c o v e r modes which he has d e f i n e d so t h a t he may make f u l l use o f t h e d i f f e r e n t d e f i n e d modes. Because o f t h i s , t h e f o l l o w i n g p r o b l e m a r i s e s . In an a p p l i e d o c c u r r e n c e o f an o p e r a t o r , t h i s o p e r a t o r may have been d e f i n e d more t h a n o n c e , f o r example, t h e o p e r a t o r + h a s had a t l e a s t 16 d e f i n i t i o n s i n t h e s t a n d a r d p r e l u d e , t h e q u e s t i o n i s how t o c h o o s e t h e c o r r e c t d e f i n i t i o n f o r t h e o p e r a t o r . The p r o c e s s o f c h o o s i n g t h e c o r r e c t o p e r a t o r i n an a p p l i e d o c c u r r e n c e i s c a l l e d t h e i d e n t i f i c a t i o n o f t h e o p e r a t o r - d e f i n i n g o c c u r r e n c e o f t h e o p e r a t o r [R.4.3.2b, R . 4 . 4 c ] , An a p p l i e d o c c u r r e n c e o f an o p e r a t o r o c c u r s i n a f o r m u l a where t h e modes o f t h e o p e r a n d s (a p r i o r i modes) a r e g i v e n and n a t u r a l l y t h e y may be c o n d i t i o n a l c l a u s e s , c l o s e d c l a u s e s , c o l l a t e r a l c l a u s e s o r s e r i a l c l a u s e s whose a p r i o r i modes a r e g i v e n . The s y n t a x o f a f o r m u l a [ R . 8 . 4 . 1 ] a l l o w s e a c h o p e r a n d t o be a f i r m MODE t e r t i a r y . Thus t o i d e n t i f y an o p e r a t o r i s t o f i n d c u t t h e d e f i n i n g o c c u r r e n c e o f t h e o p e r a t o r s u c h t h a t t h e modes o f t h e p a r a m e t e r s i n t h a t d e f i n i n g o c c u r r e n c e a r e f i r m l y c o e r c e a b l e from t h e c o r r e s p o n d i n g o p e r a n d s o f t h e a p p l i e d o c c u r r e n c e o f t h e OPEBATOB IDENTIFICATION 65 o p e r a t o r . A l s o t h e d e f i n i n g o c c u r r e n c e i d e n t i f i e d s h o u l d be u n i g u e ( a f u r t h e r d i s c u s s i o n i s i n c h a p t e r 7 ) . 6.2. The a l g o r i t h m : In t h i s a l g o r i t h m , t h e c o r r e c t o p e r a t o r symbol and t h e c o r r e c t number o f p a r a m e t e r s a r e assumed. I n p u t : l e f t o p e r a n d : t h e mode o f t h e l e f t o p e r a n d o f t h e o p e r a t o r i n t h e a p p l i e d o c c u r r e n c e . T h i s may be a c o n d i t i o n a l / s e r i a l c l a u s e o r c o l l a t e r a l c l a u s e . I t i s n u l l i f t h e o p e r a t o r i s monadic. r i g h t o p e r a n d : t h e mode o f t h e r i g h t o p e r a n d o f t h e o p e r a t o r i n t h e a p p l i e d o c c u r e n c e . T h i s i s s i m i l a r t o t h e l e f t o p e r a n d e x c e p t t h a t i t c a n n o t be n u l l , e l i g i b l e o p l i s t : a l i s t o f o p e r a t o r s d e n o t e d by mode p a i r s , e a c h o f which i s f o r t h e l e f t and t h e r i g h t p a r a m e t e r o f a d e f i n i n g o c c u r e n c e o f t h e o p e r a t o r . O u t p u t : a b o o l e a n v e c t o r which s e l e c t s f r o m t h e e l i g i b l e o p l i s t t h o s e i d e n t i f i e d by t h e o p e r a n d s . S t e p l : make a l i s t , ' p a r a m e t e r l i s t * o f n o n t e r m i n a l s o f modes o f t h e r i g h t p a r a m e t e r s o f t h e ' e l i g i b l e o p l i s t ' . S t e p 2 : l e t A,B be b o o l e a n v e c t o r s o f n e l e m e n t s , where n i s the number o f e n t r i e s i n t h e p a r a m e t e r l i s t . I f ' r i g h t o p e r a n d ' r e q u i r e s b a l a n c i n g , t h e n g o t o s t e p 1 2 o t h e r w i s e s t e p 3 : l e t f i r m - m a t r i x be an mXn b o o l e a n m a t r i x where m i s t h e number o f d e f i n e d modes, n i s t h e number o f e n t r i e s i n t h e p a r a m e t e r l i s t ; f i r m - m a t r i x i s f o r m e d i n t h e f o l l o w i n g way: OPEBATOB IDENTIFICATION 66 f o r j=1 t o n do s t e p 3 . a t o s t e p 3 . d . S t e p 3 . a : u n f l a g a l l t h e f l a g s o f t h e modes. S t e p 3 . b : c r e a t e a s e t o f f l a g s as d i r e c t e d by s t e p 9 o f t h e c o e r c i o n a l g o r i t h m s t a r t i n g f r o m STATE I I w i t h t h e j - t h e n t r y o f t h e p a r a m e t e r l i s t a s t h e mode c o n s i d e r e d . S t e p 3 . c : f i r m - m a t r i x ( i , n - j ) := f l a g (mode ( i ) ) f o r i = 1,... , m. S t e p 3 . d : t h e j - t h e n t r y o f t h e p a r a m e t e r l i s t has been c o m p l e t e l y p r o c e s s e d . S t e p U : l e t 1 be t h e n o n t e r m i n a l o f t h e r i g h t o p e r a n d , A be a b o o l e a n v e c t o r o f n f a l s e v a l u e s . S t e p 5 : A = A OR t h e 1-th row o f f i r m - m a t r i x . I f 1 i s r e f m o r p r o c m t h e n l e t 1 be t h e n o n t e r m i n a l o f m and g o t o s t e p 5 ; o t h e r w i s e , s t e p 6 : i f t h e o p e r a t o r i s monadic t h e n g o t o s t e p 1 1 ; o t h e r w i s e , r e p l a c e the p a r a m e t e r l i s t by a l i s t o f n o n t e r m i n a l s r e p r e s e n t i n g t h e l e f t p a r a m e t e r s o f t h e • e l i g i b l e o p l i s t ' . S t e p 7 : i f t h e l e f t o p e r a n d r e q u i r e s b a l a n c i n g t h e n go t o s t e p l U ; o t h e r w i s e , s t e p 8 : t h e same as s t e p 3 ( i n c l u d i n g s t e p 3 . a t o s t e p 3 . d ) . S t e p 9 : l e t 1 be t h e n o n t e r m i n a l s o f t h e ' l e f t o p e r a n d 1 , B a b o o l e a n v e c t o r o f n f a l s e v a l u e s . S t e p I O : B = B OR t h e 1-th row o f f i r m - m a t r i x , i f 1 i s r e f m o r p r o c m t h e n l e t 1 be t h e n o n t e r m i n a l o f m and g o t o s t e p I O , o t h e r w i s e A = A AMD B. S t e p l 1 : A i s t h e v e c t o r t o be r e t u r n e d . S t o p . OPERATOR IDENTIFICATION 67 S t e p 1 2 : make a l i s t , ' o l i s t ' o f t h e o p e r a n d s i n s i d e t h e c l a u s e o f the r i g h t o p e r a n d . S t e p 1 3 : i f t h e r i g h t o p e r a n d i s a s e r i a l o r c o n d i t i o n a l c l a u s e t h e n A = b a l a n c e ( p a r a m e t e r l i s t , o l i s t , " f i r m " ) o t h e r w i s e A = c o l l a t e r a l ( p a r a m e t e r l i s t , o l i s t , " f i r m " ) . Goto s t e p 6 . S t e p 1 4 : make a l i s t • o l i s t 1 o f t h e o p e r a n d s i n s i d e t h e c l a u s e o f t h e l e f t o p e r a n d . S t e p 1 5 : i f t h e l e f t o p e r a n d i s a s e r i a l o r c o n d i t i o n a l c l a u s e t h e n B = b a l a n c e ( p a r a m e t e r l i s t , o l i s t , " f i r m " ) o t h e r w i s e B = c o l l a t e r a l ( p a r a m e t e r l i s t , o l i s t , " f i r m " ) . A = A AND B. Goto s t e p 1 1 . End o f t h e a l g o r i t h m o f o p e r a t o r i d e n t i f i c a t i o n . 6.3. An example: In t h e pro g r a m , a b i t s t r i n g i s used f o r a b o o l e a n v e c t o r a s i n b a l a n c e and c o l l a t e r a l . The l i s t o f mode p a i r s i s t e r m i n a t e d by -2 -2 o r any two numbers l e s s t h a n -2. I f t h e o p e r a t o r i s monadic, t h e n t h e l i s t i s -2 n1 -2 n2 -2 n3 ... -2 -2 where n1,n2... A r e n o n t e r m i n a l s f o r t h e modes o f t h e r i g h t p a r a m e t e r s o f t h e o p e r a t o r , -2 may be r e p l a c e d by any number l e s s t h a n -2. When t h e command i s "OPERATORS" f o l l o w e d by t h e l e f t o p e r a n d , t h e r i g h t o p e r a n d and the p a i r s o f p a r a m e t e r s , a s u b l i s t o f ' o p e r a t o r s ' which can be i d e n t i f i e d by t h e o p e r a n d s w i l l be g i v e n . F o r example: 3 *—' SB* tr-io II II II o ^ , ts o o o o ID o o o o H o o o o CU o o o o rt o o o o O o o o o ri o o o o o o o o H- o o o o tn o o o o o o o o S o o o o O o o o o 3 o o o o Co o o o o Oi o o o o H* o o o o o o o o o • o o o o o o o o o o o o o o o o 1-3 o o o o B* o o o o ro o o o o o o o o o o o o o o o o o •n o o o o (0 o o o o H o o o o CU _ J o o rt-o • H o Oi ro a rt-H-Hi H-ID Oi t-3 rt) l-h tn ro a rt-ID H fl) Oi o o o o o o o o o o o o o o o o o o o s o o o o o o o o o o o o o o o o o o o 1 o o o o o o o o o o o o o o o o o o o B o o o o o o o o o o o o o o o o o o o 0> o o o o o o o o o o o o o o o o o o o o f t o o o o o o o o o o o o o o o o o o o tt rt o o o o o o o o o o o o o o o o o o o H' w o o o o o o o o o o o o o o o o o o o !*» o o o o o o o o o o o o o o o o o o o t-3 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o w so o o o o o o o o o o o o o o o o o o o w o o o o o o o o o o o o o o o o o o o * o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 1 o o o o o o o o o o o o o o o o o o o ro o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o U l o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o © o o o o o o o 1 o o o o o o o o o o o o o o o o o o o to o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o OJ o o o o o o o o o o o o © o o o o o o o o o o o o o o o o o o o o o o o o o 1 o o o o o o o o o o o o o o o o o o o to o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o CTi o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 1 o o o o o o o o o o o o o o o —' o o o to 3 Oi rt tr (0 n o 9 a P> 3 Oi I to 00 -J _ = -f i ti (0 H ro Hi O Hi 3 n s - J CO tn c T3 T3 O cn ft 3* ro 9 O Oi ro vQ H CU a B U> H ro a rt ro H ro Oi H" cn o w Ed O » M fcj M SS 1-3 H hi H n > H3 H O £3 I to CD CONCLUDING REMARKS 69 CHAPTER V I I CONCLUDING REMARKS T h i s i s a model i n ALGOL W t h a t shows how modes c a n be m a n i p u l a t e d i n an ALGOL 68 i m p l e m e n t a t i o n . T h i s i s done a c c o r d i n g t o t h e r e v i s e d s y n t a x r u l e s . The main c h a n g e s i n t h e r e v i s e d s y n t a x a r e : v o i d i s a s y m b o l ( s t i l l n o t a mode), no p r o c e d u r i n g i n c o e r c i o n , t h e c o e r c i o n t o vacuum i s h i p p i n g , t h e d e f i n i t i o n o f vacuum and n o n p r o c a r e d i f f e r e n t , h i p p i n g i s n o t an e x p l i c i t c o e r c i o n , h o w e v e r i m p l i c i t l y i t i s , and a c o m p i l e r s h o u l d t a k e c a r e o f i t . The d e f i n i t i o n o f e q u i v a l e n t modes i s n o t g i v e n i n [ R ] and n o t i n c l u d e d i n t h e new s y n t a x y e t . The d e f i n i t i o n g i v e n i n c h a p t e r 3 i s one m o d i f i e d , f r o m t h a t g i v e n by Ma r y Z o s e l i n p.7 o f [ Z ] , w h i c h i s n o t e x a c t a s we c a n s e e t h e modes u and v d e f i n e d b e l o w a r e n o t e q u i v a l e n t by t h e d e f i n i t i o n . Mode u = u n i o n ( b o o l , p_rocjj (u) i n t ) and mode v = u n i o n ( b o o l , £rocjj (u) i n t , p r o c p (v) i n t ) . B u t t h e y a r e e q u i v a l e n t by h e r a l g o r i t h m . The d e f i n i t i o n i s n o t a p p l i c a b l e o w i n g t o (1) t h e r e p r e s e n t a t i o n o f a u n i o n mode i s n o t u n i q u e , (2) a u n i o n w i t h two c o n s t i t u e n t s may be e q u i v a l e n t t o a u n i o n w i t h more t h a n two c o n s t i t u e n t s . The p r e s e n t d e f i n i t i o n i s o n l y a s u g g e s t e d one, p r o b a b l y t h e r e w i l l be a p r o p e r d e f i n i t i o n i n t h e R e v i s e d R e p o r t . T h e r e a r e r e s t r i c t i o n s (R.4.4.2c and R.4.4.3c) i n CONCLUDING REMARKS 70 d e f i n i n g o c c u r r e n c e s o f o p e r a t o r s , and t h e y have been shown n o t p o w e r f u l enough t o g u a r a n t e e t h e u n i q u e n e s s i n i d e n t i f i c a t i o n o f o p e r a t o r s i n i t s a p p l i e d o c c u r r e n c e [W], [ L 1 ] . I n i d e n t i f i c a t i o n o f o p e r a t o r s , one and o n l y one o p e r a t o r s h o u l d be i d e n t i f i e d . I n t h i s work, a l i s t o f o p e r a t o r s i d e n t i f i e d i s d e l i v e r e d , i f t h i s i s n u l l t h e n no d e f i n i n g o c c u r r e n c e c a n be i d e n t i f i e d , i f t h i s c o n t a i n s more t h a n one e n t r y , t h e n t h e o p e r a t o r i s ambiguous. I n t h i s model, t h e number o f b a l a n c e d modes o r t h e number o f d e f i n i n g o c c u r r e n c e s o f an o p e r a t o r i s a t most 31. When t h i s i s a p p l i e d i n a r e a l c o m p i l e r , i n b a l a n c i n g , i f t h e b a l a n c e d mode i s g i v e n t h e n t h e number o f b a l a n c e d modes i s one, i f n o t , t h e n a l i s t o f p o s s i b l e b a l a n c e d modes t h a t c o n t a i n s t h e a p r i o r i modes and modes ' s o r t ' l y d e f e r e n c e d o r ' s o r t ' l y d e p r o c e d u r e d f r o m them w i l l be s u p p l i e d . Thus 31 i s a number b i g enough f o r t h a t . I n o p e r a t o r i d e n t i f i c a t i o n , i f t h e number o f d e f i n e d o c c u r r e n c e s o f t h e o p e r a t o r i s g r e a t e r t h a n 31, t h e n t h e l i s t o f o p e r a t o r s t o be i d e n t i f i e d c a n be b r o k e n up i n t o s u b l i s t s o f o p e r a t o r s o f l e s s t h a n 31 e l e m e n t s s o t h i s r e s t r i c t i o n c a n be h a n d l e d . I f t h e r e i s no ' f i r m c o l l a t e r a l d i s p l a y ' (which may be i n c l u d e d i n t h e r e v i s e d R e p o r t ) , t h e s u b r o u t i n e ' c o l l a t e r a l ' w i l l be much s i m p l e r and t h e s u b r o u t i n e ' p i c k ' c a n be s i m p l i f i e d t o o . REFERENCES 71 REFERENCES [ A ] A l g o l W Programming M a n u a l , U n i v e r s i t y o f N e w c a s t l e upon T y n e , 1970. £ K ] K o s t e r , C. H. A. On I n f i n i t e Modes, A l g o l B u l l e t i n AB 30.3.3, Feb., 1969 pp. 86-89. [ L ] L i n d s e y , C. H. and van d e r Meulen, S. G. I n f o r m a l I n t r o d u c t i o n t o ALGOL 68, N o r t h - H o l l a n d P u b l i s h i n g Company, Amsterdam, 1971. [ L 1 ] L i n d s e y , C. H. D i s p l a y s and l o o s e l y r e l a t e d , I F I P WG 2.1, No. 3 ( 1 6 8 ) , N o v o s i b i r s k , S e p t . 1971. [ P ] Peck, J . E. L. Some s t e p s i n c o m p i l i n g ALGOL 68, G e s e l l s c h a f t f u r I n f o r m a t i k , B e r i c h t Nr. 4, S a a r b r u c k e n , 7-9 March, 1972. [ P 1 ] P e c k , J . E. L . An ALGOL 68 Companion, 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 , 1971. [P2 ] P e c k , J . E. L. On s t o r a g e o f modes and some c o n t e x t c o n d i t i o n s , P r o c . . I n f o r m a l C o n f e r e n c e on ALGOL 68 I m p l e m e n t a t i o n , 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 , Aug. 1969 pp. 70-77. £ R] van W i j n g a a r d e n , A., M a i l l o u x , B. J . , Pe c k , J . E. L., and K o s t e r , C. H. A. R e p o r t on t h e a l g o r i t h m i c l a n g u a g e ALGOL 68, M a t h e m a t i s c h Centrum, MR101, Amsterdam, O c t . , 1969, and N u m e r i s c h e M a t h e m a t i c , 14, 1969 pp. 79-218. [ S ] S c h e i d i g , H. C o e r c i o n s i n ALGOL 68, T e c h n i s c h e H o c h s c h u l e , Munchen, F e b . 1970. [W] Wossner,H. On i d e n t i f i c a t i o n o f o p e r a t o r s i n ALGOL 68, ALGOL 68 I m p l e m e n t a t i o n , Peck ( E d . ) , N o r t h - H o l l a n d P u b l i s h i n g Company, Amsterdam, 1971, pp.111-118. £ Z ] Z o s e l , M. A f o r m a l grammar f o r t h e r e p r e s e n t a t i o n o f modes and i t s a p p l i c a t i o n t o ALGOL 68. U n i v e r s i t y o f W a s h i n g t o n , O c t . 1971. APPENDIX A 72 APPENDIX A THE PROGRAM BEGIN COMMENT d a t e 1973 A p r i l ; RECORD md (STRING ( 6 ) t , c w ; BITS f l a g ; INTEGER mn, n f ; REFERENCE ( m d , n d ) l i n k , f i e l d ) ; COMMENT 'md's a r e u s e d f o r t h e i n t e r n a l s t o r a g e o f modes. The f i e l d * t ' i s t h e t e r m i n a l , "mn1 i s t h e mode number, ' n f i s t h e number o f f i e l d s and ' f i e l d ' i s a r e f e r e n c e t o a n o t h e r «md' ( t h e f i e l d ) o r a r e f e r e n c e t o an 'nd' l i s t ( the f i e l d s ) . The p a r t s 'cw', ' l i n k ' and • f l a g * a r e dynami c , i . e . a r e u s e d f o r t e m p o r a r y s t o r a g e d u r i n g t h e mode m a n i p u l a t i o n a l g o r i t h m s , 'cw* i s used t o s t o r e c o e r c i o n s t e p s , * l i n k * t o l i n k modes t o g e t h e r i n l i s t s and ' f l a g * f o r v a r i o u s f l a g s ; RECORD nd (REFERENCE (md)v; REFERENCE (nd)nxtmd) ; COMMENT *nd' i s used f o r s i m p l e l i s t s o f modes; RECORD ndo (STRING ( 6 ) o p _ s y m b o l ; REFERENCE ( m d ) l _ p a r , r _ p a r ; REFERENCE ( n d o ) n x t o p ) ; COMMENT t h e nodes 'ndo* a r e used f o r l i s t s o f o p e r a t o r s ; COMMENT t h e p r o c e d u r e s a r e r e l a t e d a c c o r d i n g t o t h e f o l l o w i n g grammar: < « u t i l i t y » > c l e a n _ u p :. c l e a n _ f l a g : . s e a r c h i n : s e a r c h i n . mpr : . r a v e l : s e l e c t , r a v e l . s e l e c t : s e l e c t , p o s t : c o n s i d e r , h i p _ l i n k , u n i o n s , s e a r c h . c o n s i d e r : . h i p _ l i n k : . u n i o n s : c o n s i d e r . s e a r c h : e q u a l , e q u a l : e q u a l , p o s s i b l e : s e a r c h i n , f i t . f i t : . < < < e q u i v a l e n c e » > e q u i v a l e n c e : c o n t e x t , r a v e l , j o i n _ c l a s s , p a s s , s e a r c h i n , r e l a t e d , c l e a n _ f l a g . c o n t e x t : c o n t e x t . j o i n _ c l a s s : . p a s s : s c a n . s c a n : e q u i v u , e q u i v l . e q u i v u : elmu. elmu : elmu. e q u i v l : e q u i v l . r e l a t e d : s e a r c h i n . APPENDIX A 73 <<<coercion>>> coerce : p o s s i b l e , f i t , post. <<<operator i d e n t i f i c a t i on»> op_ident : operand_ident, c l e a n _ f l a g . operand_ident : make_pars, form_matrix, check_hip, which. make_pars : make_pars. form_matrix : post. check_hip : check_hip. which : i d , clean_up, c o l l a t e r a l , b a l a . i d : f i t . c o l l a t e r a l : s e a r c h i n , f i e l d l i s t e r , p i c k , balance, check_hip, form_matrix, which, c l e a n _ f l a g . f i e l d l i s t e r : f i e l d l i s t e r . p i c k : p i c k . balance : r a v e l , p o s s i b l e , form_matrix, check_hip, c l e a n _ f l a g , b a l a . bala : which. <<<testing»> test_them : e q u i v a l e n c e , r e v e r s e _ r a v e l , r e l a t e d , c l e a n _ f l a g , coerce, clean_up, s e l e c t , i d e n t i f y , balance, c o l l a t e r a l , s e l e c t o , op_ident, enter_grammar. i d e n t i f y : form_matrix, i d . r e v e r s e _ r a v e l : i n c l u d e . i n c l u d e : i n c l u d e , s e l e c t o : s e l e c t o . enter_grammar : mpr. Each of the above procedures may c a l l some i n p u t or output procedures which are not s t a t e d , i n a d d i t i o n to read, readon, w r i t e and writeon. The I/O procedures are r e l a t e d as f o l l o w s : « < i n p u t > » r e a d m d l i s t : readmd, r e a d m d l i s t . readmd : . r e a d o p l i s t : readmd. < « o u t p u t > » procedures to save output to the output b u f f e r * o u t _ l i n e * : s a v e o p l i s t : saveopnd, saveon. saveopnd : save, s a v e m d l i s t , saveon, save_md. sav e m d l i s t : saveopnd, saveon. saveon : save, save : . save_md : save, saveon, save_md. The procedure to p r i n t out the output b u f f e r ' o u t _ l i n e ' : saveout : . ; APPENDIX A <UTILITY> 74 COMMENT «clean_up* c l e a n s up t h e f i e l d s ' l i n k ' , »flag' and •cw" i n ea c h mode o f t h e grammar; PROCEDURE c l e a n _ u p ; FOR i:=0 UNTIL max DO BEGIN l i n k (mode ( i ) ) :=NULL; f l a g (mode ( i ) ) :=#0; cw (mode ( i ) ) :=" " END; COMMENT * c l e a n _ f l a g * c e l a n s up t h e ' f l a g * f i e l d i n e a c h mode o f t h e grammar; PROCEDURE c l e a n _ f l a g ; FOR i;=0 UNTIL max DO f l a g (mode ( i ) ) : = #0 ; COMMENT • s e a r c h i n 1 s e a r c h e s t h e 'nd» l i s t * r * f o r t h e •md' 'p* and i n s e r t s i t , i f n e c e s s a r y , i n t h e o r d e r o f mode numbers {'mn') ; PROCEDURE s e a r c h i n ( R E F E R E N C E (md) VALUE p; REFERENCE(nd) VALUE RESULT r ) ; IF r=NULL THEN r : = nd (p,NULL)ELSE I F p=v(r) THEN ELSE I F mn (p) <mn (v ( r ) ) THEN r : = n d ( p , r ) ELSE s e a r c h i n (p,nxtmd ( r ) ) ; COMMENT 'mpr* d e l i v e r s t h e s t r i n g "mi" where " i " i s t h e v a l u e o f ' i ' . I f i < m i n t h e n i t d e l i v e r s t h e p r i m i t i v e mode i n s t e a d ; s t r i n g (5) p r o c e d u r e mpr ( i n t e g e r v a l u e i ) ; EEGIN STRING ( 1 5 ) s ; s : = " "; IF i<0 THEN ELSE I F i< m i n THEN s (0 | 6) : = t (mode ( i ) ) ELSE BEGIN s: = i n t b a s e 1 0 ( i ) ; s (9 J 1) :=•»» ; s (0| 6) :=s (9|6) END; s (0| 5) END mpr; COMMENT * r a v e l * r a v e l s t h e u n i o n s ('i'=1) o r t h e c o n d i t i o n a l c l a u s e s (»i'=2) i n t h e mode l i s t 'p'. I n r a v e l i n g t h e u n i o n s , i t assumes t h a t c o n t e x t c o n -d i t i o n s have a l r e a d y been c h e c k e d ; PROCEDURE r a v e l ( R E F E R E N C E ( n d ) VALUE RESULT p; INTEGER VALUE i ) ; IF p-*=NULL THEN BEGIN I F t r a c e _ i t THEN BEGIN s a v e ( " t r a v e l " ) ; s a v e m d l i s t (p) ; s a v e o u t END; IF CASE i OF (t (v (p) ) = " u n i o n " , (cw (v (p) ) =»'cond") OR (cw (v (p) ) = " s e r i " ) ) THEN BEGIN REFERENCE (nd) g , r ; g:=r:=CASE i OF ( s e l e c t ( - # 0 , f i e l d (v ( p ) ) ) , l i n k (v (p)) ) ; WHILE nxtmd (r) ->=ND1L DO r : = n x t m d ( r ) ; nxtmd ( r ) : = n x t m d ( p ) ; p:=g; r a v e l ( p , i ) END ELSE r a v e l (nxtmd (p) , i ) END; COMMENT * s e l e c t * p e r f o r m s t h e a p l o p e r a t i o n a / l i s t ; REFERENCE (nd)PROCEDURE s e l e c t (BITS VALUE a ; REFERENCE(nd) VALUE l i s t ) ; I F l i s t = N U L L THEN NULL ELSE I F a AND #1 = #1 THEN nd (v ( l i s t ) - , s e l e c t (a SHR 1, nxtmd ( l i s t ) ) ) ELSE APPENDIX A <UTILITY> 75 s e l e c t (a SHR 1, nxtmd. ( l i s t ) ) ; COMMENT ' p o s t 1 f l a g s 'mr' i f 'mr* i s " s k i p " o r "jump", i f •mr* i s " n i l " and 'ms' s t a r t s w i t h " r e f " , o r i f 'mr' i s "vacuum" and 'ms1 s t a r t s w i t h "row" o r " r o w o f " o t h e r w i s e t r a c e s t h e a p o s t e r i o r i r o u t e t h r o u g h t h e grammar, from t h e mode «ms*, p l a n t i n g t h e f l a g ' f l a g l ' a s i t g o e s ; PROCEDURE post(REFERENCE(md) VALUE mr,ms; BITS VALUE f l a g l ; STRING (6) VALUE s o r t , c o e r c e n d ) ; BEGIN REFERENCE ( n d e ) c n s d ; REFERENCE(md)m, 1st; INTEGER s t ; RECORD nde (REFERENCE ( n d e ) n x t n d e ; REFERENCE (md)mde, l a s t ; INTEGER s t a t e ) ; COMMENT — ' n d e ' s a r e used by t h e g u e u e i n g mechanism; REFERENCE(nd)p; COMMENT — ' c o n s i d e r * gueues t h e mode *m1* a l o n g w i t h t h e s t a t e ' s t * and s a v e s c o e r c i o n s t e p *cwd' i n t h e *cw* f i e l d o f •ml *; PROCEDURE c o n s i d e r ( R E F E R E N C E (md) VALUE ml; INTEGER VALUE s t a t e ; STRING (6) VALUE cwd) ; BEGIN IF cnsd=NULL THEN cnsd:=nde(NULL,ml,m,state) ELSE BEGIN REFERENCE (nde) g; q:=cnsd; WHILE n x t n d e (q)-.=NULL DO q: = n x t n d e ( q ) ; n x t n d e ( g ) : = n d e ( N U L L , m l , m , s t a t e ) END; cw(m1): = cwd END c o n s i d e r ; COMMENT — * h i p _ l i n k ' f l a g s * mr' and l i n k s 'mr*, 'ms' when 'mr* i s c o e r c e a b l e t o *ms» by h i p p i n g ; PROCEDURE h i p _ l i n k ; BEGIN c w ( m r ) : = " h i p p e d " ; f l a g (mr): = f l a g (mr) OR f l a g l ; l i n k (mr) := ms; l i n k (ms) :=modeO END h i p _ l i n k ; COMMENT —.-. ' u n i o n s * t a k e s c a r e o f t h e u n i o n mode »m* i n s t r o n g o r f i r m c o e r c i o n ; PROCEDURE uni o n s ( R E F E R E N C E (md) VALUE m); BEGIN REFERENCE (nd) p; p: = f i e l d ( m ) ; WHILE p-i=NULL DO BEGIN c o n s i d e r (v (p) , 3 , " u n i t e " ) ; p: = nxtmd (p) END END u n i o n s ; COMMENT ; ' s e a r c h ' s e a r c h e s t h r o u g h t h e mode grammar f o r t h e mode e g u a l t o *g'. O n l y t h e * t ' , »nf* and ' f i e l d ' f i e l d s a r e examined; REFERENCE(md) PROCEDURE s e a r c h (REFERENCE (md) VALUE g ) ; BEGIN COMMENT ' e g u a l ' d e t e r m i n e s whether t h e •nd• l i s t s •p' and 'g' a r e e g u a l ; LOGICAL PROCEDURE e g u a l (REFERENCE (nd)VALUE p , q ) ; I F p=q THEN TRUE ELSE I F p=NULL THEN q=NULL ELSE (v(p) = v ( q ) ) AND e q u a l (nxtmd (p) ,nxtmd (q) ) ; REFERENCE (md)mi; INTEGER i ; i : = min; APPENDIX A <UTILITY> 76 WHILE i<=max DO BEGIN mi: = mode(i); IF (nf (q)=nf (mi) ) AND (t(g) = t(mi)) AND (IF f i e l d (q) IS nd THEN equal(field(g),field(mi)) ELSE f i e l d (q)=field (mi)) THEN i:=max+2 ELSE i:=i + 1 END; IF i-.=max + 2 THEN mi:=NULL; mi END search; cnsd:=NULL; m:=modeO; consider(is, IF sort="strong" THEN 1 ELSE IF sort="firm" THEN 2 ELSE 3, •». ") ; WHILE cnsd-=NULL DO . BEGIN st:=state (cnsd) ; m: = mde (cnsd) ; 1st:=last (cnsd) ; IF t r a c e _ i t THEN write("*** considering ", IF m=NOLL THEN " n u l l " ELSE mpr(mn(m))," in state ", st , " l a s t was ", IF lst=NOLL THEN " n u l l " ELSE mpr(mn(1st))); cnsd: = nxtnde (cnsd) ; IF (flag (m)=-.#1) AND (t (m) ="void") AND (sort-.= "strong") THEN COMMENT i f void appears as the a p o s t e r i o r i mode i n a position other than strong and that seems to be coerceable, e.g. the a p r i o r i mode i s ref proc void, then a message w i l l be given and the res u l t i s not coerceable; write("invalid a p o s t e r i o r i mode") ELSE BEGIN CASE s t OF BEGIN BEGIN COMMENT ********** state 1 (strong); l i n k (m) :=lst; f lag (m) :=f lag (m) OR f l a g l ; IF (t (mr)="skip") OR (t (mr) = " jump") THEN hip link ELSE IF (t~(mr)="nil") AND (t (ms) = "ref") THEN hip_link ELSE IF (t (mr) = "vacuum") AND (t (ms) ="ref") THEN hip_link ELSE IF t(ra)="union" THEN unions(m) ELSE IF t(m)="rowof" THEN BEGIN consider ( f i e l d (m) , 1, "row") ; IF t ( f i e l d (m) ) ="bool" THEN consider(mode (bitsl),3,"widen") ELSE IF t ( f i e l d (m) )="char" THEN consider(mode(bytes),3,"widen") END ELSE IF t(m)="row" THEN consider(field(m),1,t(m)) ELSE IF m=mode(compl) THEN consider (mode(reall),1,"widen") ELSE IF m=mode(3) THEN consider (mode (2),3,"widen") ELSE IF t(m)="ref" THEN consider ( f i e l d (m) ,4 , "ref row") ELSE APPENDIX A <UTILITY> 77 I F t (m)="void" THEN BEGIN I F l i n k (m)-.= mode0 THEN COMMENT no c o e r c i o n goes a f t e r v o i d i n g , so i f t h e a p o s t e r i o r i mode i s v o i d , no p r e f i x s h o u l d go b e f o r e v o i d ; f l a g (m) : = f l a g ( m ) AND - . f l a g l ELSE BEGIN REFERENCE(md) mm, mp; mm:=mr; IF ( c o e r c e n d = " c o m o r f " ) OR ( c o e r c e n d = " l o o p " ) THEN BEGIN flag(mm):=flag(mm) OR f l a g l ; cw (mm) : = " v o i d e d " ; l i n k (mm) :=m END ELSE BEGIN mp:=mr; WHILE f i e l d (mp) IS md DO BEGIN mm:=mp; mp;=field(mp) END; IF (t (mp)="void") AND (t (mm) -*="proc") AND (mm-i=mp) THEN f l a g (m) : = f l a g (m) AND - . f l a g l ELSE BEGIN mp:=mr; WHILE f i e l d (mp) IS md DO BEGIN I F t(mp) = " p r c c " THEN mm:=f i e l d (mp) ELSE I F t(mp) (0|3)="row« THEN mp:=md(" " , " ",#0,0,0,NULL,modeO) ; mp:=field(mp) END; cw (mm) : = " v o i d e d " ; l i n k (mm) : = I F t (mm)="void" THEN NULL ELSE m; f l a g (mm):= f l a g (mm) OR f l a g l END END END END END s t a t e _ 1 ; BEGIN COMMENT * * * * * * * * * * s t a t e 2 ( f i r m ) ; I F t (m)-.="void« THEN COMMENT v o i d i s assumed n o t t o a p p e a r a s t h e a p o s t e r i o r i mode i n any p o s i t i o n o t h e r t h a n s t r o n g ; BEGIN l i n k (m) : = l s t ; f l a g (m) :=f l a g (m) OR f l a g l END; I F t (m) = " u n i o n " THEN u n i o n s (m) END s t a t e _ 2 ; BEGIN COMMENT * * * * * * * * * * s t a t e 3; I F t (m) - = " v o i d " THEN BEGIN l i n k (m) : = l s t ; f l a g (m) : = f l a g (m) OR f l a g l END END s t a t e 3; BEGIN COMMENT * * * * * * * * * * s t a t e 4; IF t(m) (0|3)="row" THEN BEGIN REFERENCE(md)mg1; l i n k (m) : = l s t ; c o n s i d e r ( f i e l d (m) , 4, " r e f row") ; mg1:=search(md ( " r e f " , " ",#0,0,1,NULL, f i e l d (m))) ; IF mq1-i=NULL THEN BEGIN l i n k ( m g 1 ) : = l s t ; m:=mg1 ; cw (m): = " r e f r o w " ; f l a g ( m ) : = f l a g (m) OR f l a g l END END END s t a t e _ 4 END END; IF f l a g j m ) = ^ # 0 THEN cnsd:=NDLL END; IF t r a c e _ i t THEN w r i t e o n ( " f l a g = " , f l a g ( m ) ) END p o s t ; COMMENT ' p o s s i b l e ' d e l i v e r s a l i s t o f a l l modes which c a n be ' s o r t ' l y c o e r c e d from a t l e a s t one o f the modes i n the l i s t »p«. Note t h a t i t i s n o t c a l l e d when ' s o r t ' i s " s t r o n g " and when ' s o r t * i s " f i r m " i t does n o t c o n s i d e r APPENDIX A <UTILITY> 78 u n i t i n g ; r e f e r e n c e ( n d ) p r o c e d u r e p o s s i b l e ( r e f e r e n c e ( n d ) v a l u e p; STRING (6) VALUE s o r t ) ; BEGIN REFERENCE(nd) r e t u r n , g; r e t u r n : = N U L L ; WHILE p-«=NULL DO EEGIN REFERENCE(md) m; q:=NULL; m: = v ( p ) ; COMMENT - — ' s k i p ' , 'jump', ' n i l * and 'vacuum 1 c a n n o t be an a p o s t e r i o r i mode; I F ( (t (m) = " s k i p " ) OR ( t (m) = " jump") OR (t (m) = " n i l " ) OR (t (m) ="vacuum") ) THEN BEGIN s e a r c h i n (m,g) ; WHILE f i t ( m , s o r t ) DO BEGIN m : = f i e l d (m); s e a r c h i n ( m , g ) END; WHILE g-.= NULL DO BEGIN s e a r c h i n (v (q) , r e t u r n ) ; q: = nxtmd(g) END END; p: = nxtmd(p) END; IF t r a c e _ i t THEN BEGIN s a v e ( " ^ p o s s i b l e " ) ; s a v e m d l i s t ( p ) ; s a v e ( s o r t ) ; s a v e o u t END; r e t u r n END p o s s i b l e ; COMMENT ' f i t * d e t e r m i n e s whether t h e c o e r c i o n s t e p , d e r e f e r e n c e o r d e p r o c e d u r e , c a n be t a k e n f r om t h e mode 'm'; LOGICAL PROCEDURE f i t ( R E F E R E N C E (md) VALUE m; STRING (6) VALUE s o r t ) ; IF t ( m ) = " p r o c " THEN TRUE ELSE IF (sort-.= " s o f t " ) AND (sort-*="weak") THEN t ( m ) = " r e f " ELSE I F s o r t = " w e a k " THEN BEGIN I F t ( m ) = " r e f " THEN (t ( f i e l d (m) ) = " r e f " ) OR ( t ( f i e l d (m)) ="proc") ELSE FALSE END ELSE FALSE; COMMENT ' e q u i v a l e n c e ' c o n t a i n s t h e mode e g u i v a l e n c i n g p r o c e d u r e s . D u r i n g e g u i v a l e n c i n g t h e modes a r e i n an 'nd' l i s t whose f i r s t e l e m e n t i s ' i n i t i a l ' and whose l a s t e l e m e n t i s ' f i n a l ' : a t t h e b e g i n n i n g , a l l t h e modes o f t h e same t e r m i n a l s a r e l i n k e d t o g e t h e r t h r o u g h t h e i r ' l i n k * f i e l d s and a t t a c h e d t o one o f t h e e l e m e n t s o f t h e 'nd'. At t h e end o f e g u i v a l e n c i n g , t h e r e a r e as many e l e m e n t s i n t h e 'nd' l i s t as t h e r e a r e e q u i v a l e n c e c l a s s e s . A s e t o f e g u i v a l e n t modes t h e n hangs f r o m e a c h e l e m e n t o f t h e 'nd'. The ' f l a g * f i e l d o f an 'md» i s use d t o r e c o r d t h e e g u i v a l e n c e c l a s s number; PROCEDURE e q u i v a l e n c e ; BEGIN COMMENT — ' c o n t e x t * c h e c k s f o r two c o n t e x t c o n d i t i o n s . I t d e t e r m i n e s whether a mode shows i t s e l f and whether t h e r e a r e m u l t i p l e o c c u r r e n c e s o f t h e same f i e l d s e l e c t o r i n a s t r u c t u r e ; PROCEDURE context(REFERENCE(md) VALUE m; LOGICAL VALUE r e f , s t r u c t ) ; BEGIN I F flag(m)=#1 THEN BEGIN APPENDIX A <EQUIVALENCE> 79 w r i t e ( " c o n t e x t c o n d i t i o n e r r o r i n v o l v i n g t h e mode"); save_md (m); s a v e o n ( " , " ) ; s a v e o u t ; w r i t e ( " which i s r e p l a c e d by * b o o l * . " ) ; COMMENT t h i s d a n g e r o u s s i t u a t i o n must be c o r r e c t e d so we change t h e mode t o s o m e t h i n g s i m p l e " b o o l " ; f i e l d (m):=NULL; t (m):="bool"; nf (ra):=0 END~ELSE BEGIN f l a g (m) :=#1; COMMENT c h e c k f o r s h i e l d i n g ; IF t (m)-="procp" THEN BEGIN I F t ( m ) = " s t r u c t " THEN BEGIN REFERENCE(nd) p,q; COMMENT c h e c k f o r r e p e a t e d s e l e c t o r s ; p : = f i e l d ( m ) ; WHILE p-=NULL DO BEGIN g: = nxtmd(p) ; WHILE q-=NULL DO BEGIN I F t (v (p) ) =t (v (g)) THEN BEGIN I F max<35 THEN BEGIN v(q) : = md ("%"," " , f l a g (v (p)) , BEGIN max:=max+1; max END, 1, l i n k ( v ( g ) ) , f i e l d ( v ( g ) ) ) ; mode (max) : = v (q) END; w r i t e ( " c o n t e x t c o n d i t i o n e r r o r " , " i n t h e s t r u c t u r e " ) ; save_md (m); s a v e ( " m u l t i p l e " ) ; s a v e ( " s e l e c t o r " ) ; sa ve (t (v (p) )) ; s a v e o u t END; g: = nxtmd(g) END; p: = nxtmd (p) END; s t r u c t : = T R U E END ELSE I F t ( m ) = " r e f " THEN ref:=TRDE; I F - ( r e f AND s t r u c t ) THEN BEGIN I F f i e l d (m) IS md THEN c o n t e x t ( f i e l d ( m ) , r e f , s t r u c t ) ELSE BEGIN REFERENCE (nd) p; p: = f i e l d ( m ) ; WHILE p-=NULL DO BEGIN c o n t e x t ( v ( p ) , r e f , s t r u c t ) ; p: = nxtmd(p) END END END END; f l a g ( m ) : = #0 END END c o n t e x t ; COMMENT — * j o i n _ c l a s s ' adds t h e mode • m i 1 t o t h e c l a s s which ' v ( q ) ' b e l o n g s . T h i s i s used when »mi* and »v (g)» a r e o f t h e same t e r m i n a l ; PROCEDURE j o i n _ c l a s s (REFERENCE (md) VALUE mi; REFERENCE (nd) VALUE q) ; BEGIN REFERENCE (md) x; x: = v (q) ; WHILE l i n k (x)-<=NULL DO x: = l i n k ( x ) ; l i n k (x) : = mi; f l a g (mi) : = f l a g (x) END; COMMENT — » p a s s ' makes one p a s s t h r o u g h t h e »nd» l i s t . The p a r a m e t e r ' i * d e t e r m i n e s which o f t h e two d i f f e r e n t k i n d s o f t e s t s f o r e q u i v a l e n c e s h o u l d be made. 1 - t e s t t h e number o f f i e l d s , 2 - t e s t t h e c l a s s numbers; PROCEDURE p a s s (INTEGER VALUE i ) ; BEGIN APPENDIX A CEQUIVALENCE> 80 COMMENT - — ' s c a n ' makes one s c a n t h r o u g h an 'md1 l i s t . I t c o n s i d e r s t h e i n i t i a l mode and d e t e r m i n e s whether any of t h e r e m a i n i n g modes o f t h e l i s t i s i n t h e same e g u i v a l e n c e c l a s s as t h e i n i t i a l e l e m e n t . I f one i s n o t t h e n i t i s t r a n s f e r r e d t o t h e l i s t h a n g i n g f r o m • f i n a l ' and i s g i v e n a new c l a s s number; PROCEDURE s c a n (REFERENCE (md) VALUE p; INTEGER VALUE i ) ; BEGIN COMMENT ' e q u i v u ' d e t e r m i n e s whether t h e u n i t e d modes * a * and 'b» s h o u l d be i n t h e same e g u i v a l e n c e c l a s s ; LOGICAL PROCEDURE e g u i v u (REFERENCE (nd) VALUE a , b ) ; BEGIN COMMENT — — 'elmu' d e t e r m i n e s whether t h e mode 'a' i s e g u i v a l e n t t o a member o f t h e mode l i s t 'b*; LOGICAL PROCEDURE elmu (REFERENCE (md) VALUE a ; REFERENCE (nd) VALUE b) ; IF b=NULL THEN FALSE ELSE IF f l a g (a) =f l a g (v (b) ) THEN TRUE ELSE elmu (a,nxtmd (b)) ; LOGICAL r e t u r n ; REFERENCE (nd) p; re t u r n : = T R U E ; p:=a; WHILE p-.= NULL DO IF e l m u ( v ( p ) , b ) THEN p: = nxtmd(p) ELSE BEGIN p:=NULL; r e t u r n : = F A L S E END; IF r e t u r n = T R U E THEN BEGIN p:=b; WHILE p-=NULL DO IF elmu (v (p) ,a) THEN p: = nxtmd(p) ELSE BEGIN p:=NULL; r e t u r n : = F A L S E END END; r e t u r n END e g u i v u ; COMMENT ' e g u i v l ' d e t e r m i n e s whether two •nd' l i s t s o f modes a r e s u c h t h a t t h e c o r r e s p o n d i n g e l e m e n t s a r e i n t h e same e g u i v a l e n c e c l a s s e s . I t i s c a l l e d by • s c a n ' t o d e a l w i t h t h e modes whose t e r m i n a l s a r e " s t r u c t " and " p r o c p " ; LOGICAL PROCEDURE e g u i v l (REFERENCE (nd) VALUE a,b) ; IF a=NULL THEN b=NULL ELSE ( f l a g (v (a) ) = f l a g (v (b) )) AND e g u i v l (nxtmd (a) ,nxtmd (b) ) ; REFERENCE (md) q, r ; r : = p; g: = l i n k ( r ) ; WHILE g-.= NULL DO I F CASE i OF ( IF t ( p ) = " u n i o n " THEN TRUE ELSE n f (p) =nf (g) -, I F f i e l d ( p ) = f i e l d ( g ) THEN TRUE ELSE IF f i e l d (p) IS md THEN f l a g ( f i e l d (p)) =f l a g ( f i e l d (g)) ELSE IF t ( p ) = " u n i o n " THEN e g u i v u ( f i e l d (p) , f i e l d (g)) ELSE e g u i v l ( f i e l d (p) , f i e l d (g)) ) THEN BEGIN r : = l i n k ( r ) ; g: = l i n k ( r ) END ELSE BEGIN l i n k (r) : = l i n k (g) ; l i n k (g) : = NULL; APPENDIX A <EQUIVALENCE> 81 f l a g ( g ) : = b i t s t r i n g ( c l a s s ) ; IE t a i l IS nd THEN v ( t a i l ) : = g ELSE l i n k ( t a i l ) : = g; t a i l : = q ; q : = l i n k ( r ) ; I F t r a c e _ i t THEN BEGIN s a v e ('"Btail •= ") ; s a v e _ m d ( t a i l ) ; s a v e o u t END END END s c a n ; p:=pre; s v c l ; = c l a s s ; WHILE v (p) -i=NULL DO BEGIN I F v ( f i n a l ) - = N D L L THEN BEGIN t a i l : = f i n a l : = n x t m d ( f i n a l ) : = n d ( N U L L , N U L L ) ; c l a s s : = c l a s s + 1 END; s c a n (v (p) , i ) ; p:=nxtmd(p) END END p a s s ; REFERENCE (nd) i n i t i a l , f i n a l , p, p r e ; INTEGER c l a s s , s v c l ; REFERENCE (nd,md) t a i l ; COMMENT — c h e c k c o n t e x t c o n d i t i o n s and r a v e l a l l t h e u n i o n s ; FOR i:=min UNTIL max DO BEGIN c o n t e x t (mode ( i ) , FALSE, FALSE) ; IF t (mode(i) ) = » u n i o n " THEN r a v e l ( f i e l d (mode ( i ) ) , 1) END; COMMENT —:-. modes a r e c l a s s i f i e d by t h e i r t e r m i n a l s , i . e . each e l e m e n t o f t h e *nd» i n i t i a l hangs a l i s t o f modes, l i n k e d t h r o u g h t h e i r l i n k - f i e l d s , w i t h t h e same t e r m i n a l . The f i r s t 12 c l a s s e s (from 0 - t h t o 11-th) a r e f o r p r i m i t i v e s , t h e 12-th and t h e 13-th a r e f o r 're» and 'im• of 'complex', t h e 14-th i s f o r ' r o w o f and t h e 15-th i s f o r ' s t r u c t * . C l a s s e s w i t h t e r m i n a l s o t h e r t h a n t h e above 16, a r e a t t a c h e d t o t h e end o f 'nd'; p , : T i n i t i a l . : = nd (mode (0) ,NULL) ; FOR i:=1 UNTIL 7 DO • BEGIN nxtmd (p) : = nd (mode ( i ) , NULL) ; f l a g (mode ( i ) ) : = b i t s t r i n g ( i ) ; p:=nxtmd (p) END; FOR i:=1 UNTIL 4 DO BEGIN nxtmd ( p ) : = nd (mode (i+11),NULL) ; f l a g (mode ( i ) ) : = b i t s t r i n g (i+7) ; p: = nxtmd(p) END; nxtmd (p) : = nd (mode(10) ,NULL) ; f l a g (mode (10) ) : = b i t s t r i n g (12) ; p r e : = p: = nxtmd (p) ; nxtmd ( p ) : = nd (mode (11),NULL) ; f l a g (mode (11)) ; = b i t s t r i n g (13) ; p: = nxtmd (p) ; nxtmd (p) : = nd (mode (9) ,NULL) ; f l a g (mode (9) ) : = b i t s t r i n g (14) ; p:=nxtmd (p) ; nxtmd (p) : = nd (mode (8) ,NULL) ; f l a g (mode (8)) : = b i t s t r i n g (15) ; f i n a l : = p:=nxtmd (p) ; c l a s s : = 1 5 ; FOR i:=min UNTIL max DO BEGIN I F n f (mode ( i ) ) = 0 THEN p; = i n i t i a l ELSE p:=pre; WHILE nxtmd (p) -»=NULL DO BEGIN I F t (mode ( i ) )-=t (v (p) ) THEN p: = nxtmd (p) ELSE BEGIN j o i n _ c l a s s ( m o d e ( i ) , p ) ; p;=nd (NULL,NULL) END END; I F V (p) -.=NULL THEN BEGIN I F t (mode ( i ) ) =t (v (p) ) THEN j o i n _ c l a s s (mode ( i ) , p) ELSE APPENDIX A <EQUIVALENCE> 82 BEGIN c l a s s : = c l a s s + 1 ; nxtmd (p) :=nd (mode ( i ) ,NULL) ; f l a g ( m o d e ( i ) ) : = b i t s t r i n g ( c l a s s ) END END END; f i n a l : = p r e ; WHILE nxtmd ( f i n a l ) -»=NULL DO f i n a l : = n x t m d ( f i n a l ) ; COMMENT — c l a s s e s a r e r e f i n e d by t h e ' n f , f i e l d and t h e c l a s s numbers i n t h e f l a g - f i e l d (s) o f t h e f i e l d - f i e l d s ; p a s s _ 1 : p a s s (1) ; COMMENT — m o d e s a r e s e p a r a t e d by ' n f f i e l d ; p a s s _ 2 : svcl:=0; WHILE s v c K c l a s s DO p a s s (2); COMMENT — m o d e s a r e s e p a r a t e d by t h e ' c l a s s - n u m b e r ' o f t h e i r f i e l d o r f i e l d s ; COMMENT —•- c o l l e c t t h e g a r b a g e ; BEGIN REFERENCE(nd) p, g; REFERENCE(md) r , s; INTEGER j ; COMMENT make a l l t h e ' l i n k ' f i e l d s o f an •md* p o i n t t o t h e f i r s t e l e m e n t o f t h e e g u i v a l e n c e c l a s s and r e s e t t h e ' f l a g ' s ; p: = i n i t i a l ; WHILE v(p)-.= NULL DO BEGIN r : = v ( p ) ; WHILE r-*=NULL DO BEGIN s:=r; f l a g ( r ) : = #0; r : = l i n k ( r ) ; l i n k (s) : = v (p) END; p: = nxtmd(p) END; COMMENT — go t h r o u g h a l l t h e modes and upd a t e t h e • f i e l d ' o f t h e »md• t o p o i n t t o t h e u n i q u e e l e m e n t o f t h e e q u i v a l e n c e c l a s s ; p : = i n i t i a l ; WHILE v(p)-«NULL DO BEGIN I F nf( v ( p ) ) > 0 THEN I F f i e l d ( v ( p ) ) IS md THEN f i e l d ( v (p)) : = l i n k ( f i e l d (v (p))) ELSE BEGIN g: = f i e l d (v (p) ) ; WHILE q-.=NULL DO BEGIN v (q) : = l i n k ( v (g) ) ; g: = nxtmd{g) END END; p: = nxtmd (p) END u p d a t i n g ; COMMENT - — compact t h e mode grammar; j:=min; FOR i;=min UNTIL max DO IF l i n k (mode ( i ) ) =mode ( i ) THEN I F t (mode ( i ) ) -*=" " THEN BEGIN mode (j) : = mode ( i ) ; mn (mode ( j ) ) :=j ; j : = j + 1 END ; FOR i : = j UNTIL max DO mode ( i ) : = md (" "," ", #0, i,0 , NULL, NULL) ; max:= j - 1 END g a r b a g e _ c o l l e c t i o n ; COMMENT — l o o k a t a l l u n i o n s t o d e t e r m i n e whether t h e y s a t i s f y t h e c o n d i t i o n r e g a r d i n g r e l a t e d modes; FOR i:=min UNTIL max DO IF t ( m o d e ( i ) ) = " u n i o n " THEN BEGIN REFERENCE (nd) p, g; q:=NULL; COMMENT s o r t and remove r e p e a t e d modes; p: = f i e l d (mode ( i ) ) ; WHILE p->=NULL DO BEGIN s e a r c h i n (v (p) ,q) ; p: = nxtmd(p) END; f i e l d (mode ( i ) ) :=g; q : = r e l a t e d (q) ; c l e a n _ f l a g ; IF g-*=NULL THEN BEGIN w r i t e ( " e r r o r i n mode"); save_md(mode ( i ) ) ; s a v e ("modes") ; s a v e m d l i s t (g) ; sav e ( " a r e " ) ; s a v e ( " r e l a t e d " ) ; s a v e o u t END END END e q u i v a l e n c e ; COMMENT ' r e l a t e d ' d e t e r m i n e s whether t h e s e t o f modes i n ' l i s t ' c o n t a i n s a p a i r o f r e l a t e d modes and i f s o , d e l i v e r s a l i s t o f modes o f which e a c h i s r e l a t e d t o some o t h e r mode APPENDIX A <COERCION> 83 o f t h e l i s t ; REFERENCE(nd) PROCEDURE r e l a t e d ( R E F E R E N C E ( n d ) VALUE l i s t ) ; BEGIN REFERENCE(nd)p, r e t u r n ; REFERENCE (md)x; p : = l i s t ; r e t u r n : = N U L L ; WHILE p-=NULL DO BEGIN f l a g (v (p)) :=#1 ; p: = nxtmd (p) END; p: = l i s t ; WHILE p~.= NULL DO BEGIN x : ~ v ( p ) ; WHILE f i e l d (x)-.= NULL DO IF ( t ( x ) = " r e f " ) OR (t (x)="proc») THEN BEGIN x: = f i e l d ( x ) ; I F flag(x)=#1 THEN BEGIN s e a r c h i n ( x , r e t u r n ) ; s e a r c h i n ( v ( p ) , r e t u r n ) END END ELSE x:=modeO; p:=nxtmd(p) END; IF t r a c e _ i t THEN BEGIN s a v e ( " ^ r e l a t e d : " ) ; s a v e m d l i s t ( l i s t ) ; s a v e o u t END; r e t u r n END r e l a t e d ; COMMENT ' c o e r c e * d e t e r m i n e s whether t h e mode 'mr' c a n be ' s o r t ' l y c o e r c e d t o mode 'ms'; LOGICAL PROCEDURE c o e r c e ( REFERENCE (md) VALUE mr; REFERENCE (md,nd) VALUE RESULT ms; STRING (6) VALUE RESULT s o r t ; STRING (6) VALUE c o e r c e n d ) ; BEGIN LOGICAL r e t u r n ; REFERENCE (md) mm, m, mq; mq:=m:=mr; re t u r n : = T R U E ; I F s o r t = " " THEN BEGIN REFERENCE (md) mp; mp: = mm: = mr; WHILE mm-»= NULL DO BEGIN s o r t : = I F t (mm) (0 j 3 ) = " r o w " THEN "weak" ELSE IF t (mm)=«'procp" THEN "meek" ELSE " "; IF s o r t = " » THEN BEGIN mp:=mm; mm:=field(mm) END ELSE BEGIN mq:=IF t(mp) = " r e f " THEN mp ELSE mm; mm:=ms:=NULL END END END; IF s o r t = " " THEN BEGIN w r i t e (»*** e r r o r : d u b i o u s s o r t ***") ; r e t u r n : = F A L S E END ELSE BEGIN I F ms=NULL THEN BEGIN s a v e o p n d (mr); s a v e ( s o r t ) ; s a v e o n ( " l y " ) ; s a v e ( " c o e r c e a b l e " ) ; s a v e ( " t o " ) ; I F sort-«="strong" THEN m s : = p o s s i b l e ( n d ( m g , NULL), s o r t ) ; s a v e m d l i s t (ms) END ELSE BEGIN s a v e ( s o r t ) ; s a v e ( " c o e r c i o n " ) ; s a v e ( " o f " ) ; s a v e ( c o e r c e n d ) ; s a v e o p n d (mr) ; s a v e ( " t o " ) ; s a v e o p n d (ms) ; s a v e ( " : " ) ; IF (sort-.= " s t r o n g " ) AND (sort-«="f irm") THEN BEGIN mm:=mr; WHILE (mr-.= ms) AND (mm-=NULL) DO IF f i t (mr, s o r t ) THEN BEGIN s a v e { " d e " ) ; s a v e o n (t (mr) (0 | 4)) ; mr : = f i e l d (mr) ; s a v e ( " t o " ) ; s a v e (mpr (mn (mr))) END ELSE BEGIN r e t u r n : = F A L S E ; mm:=NULL END END ELSE BEGIN WHILE ( t ( m ) = " r e f " ) OR (t (m) = " p r o c " ) DO BEGIN f lag (m) 1 ; m : = f i e l d (ra) END; f l a g (m) :=-<#1; APPENDIX A <OPERATOR I D E N T I F I C A T I O N 84 I F (f l a g (ms) =-.#1) AND (t (m)-.= " v o i d " ) THEN f l a g (ms): = #1 ELSE p o s t ( m r , m s , # 1 , s o r t , c o e r c e n d ) ; m:=mr; WHILE ( f l a g ( m ) AND #1 = #0) AND r e t u r n DO IF ( t (m)="ref") OB ( t ( m ) = " p r o c " ) THEN BEGIN s a v e ("de") ; s a v e o n (t (m)) ; s a v e ("to") ; m: = f i e l d ( m ) ; s a v e ( m p r (mn (m))) END ELSE r e t u r n : = F A L S E END END; IF r e t u r n = T R U E THEN WHILE l i n k (m)-i=NULL DO BEGIN sav e (cw(ni)) ; m: = l i n k ( m ) ; I F l i n k (m) -»=NULL THEN BEGIN save ( " t o " ) ; s a v e (mpr (mn (m))) END END END; r e t u r n END c o e r c e ; COMMENT •op_ident» i s t h e o p e r a t o r i d e n t i f i c a t i o n a l g o r i t h m o f Z o s e l . I t r e c e i v e s a l i s t o f e l i g i b l e o p e r a t o r s and d e l i v e r s a l i s t o f t h o s e which c a n be i d e n t i f i e d . T h i s r e s u l t i n g l i s t may have z e r o , one o r mere t h a n one e l e m e n t ; BITS PROCEDURE o p _ i d e n t (REFERENCE (ndo) VALUE e l i g i b l e o p l i s t ; REFERENCE (md) VALUE r _ o p n d , l_opnd) ; BEGIN BITS a ; BITS ARRAY s _ m a t r i x , f _ m a t r i x (0::max); COMMENT — * o p e r a n d _ i d e n t • d e l i v e r s a b i t s t r i n g t h a t i d e n t i f i e s t h e l e f t p a r a m e t e r s (i=1) o r t h e r i g h t p a r a m e t e r s (i=2) o f t h e g i v e n o p e r a t o r s • e l i g i b e o p l i s t * by t h e o p e r a n d 'opnd*; BITS PROCEDURE o p e r a n d _ i d e n t (REFERENCE(ndo) VALUE e l i g i b l e o p l i s t ; INTEGER VALUE i ; REFERENCE (md) VALUE opnd) ; BEGIN REFERENCE(nd)p; BITS b; COMMENT - — 'make_pars» d e l i v e r s an 'nd* l i s t o f t h e l e f t ( i~1) o r r i g h t (i=2) p a r a m e t e r s o f t h e e l e m e n t s o f • l i s t * ; REFERENCE(nd)PROCEDURE make_pars (REFERENCE(ndo)VALUE l i s t ; INTEGER VALUE i ) ; I F l i s t = N 0 1 L THEN NULL ELSE CASE i OF (nd ( l _ p a r ( l i s t ) , make_pars (nxtop ( l i s t ) , i ) ) , nd ( r _ p a r ( l i s t ) , make_pars (nxtop ( l i s t ) , i ) ) ) ; p: = make_pars ( e l i g i b l e o p l i s t , i ) ; f o r m _ m a t r i x ( p , # 0 , # 1 , " f i r m " , f _ m a t r i x ) ; IF l i n k ( o p n d ) IS nd THEN f o r m _ m a t r i x ( p , c h e c k _ h i p ( l i n k ( o p n d ) ) , # 1 , " s t r o n g " , s _ m a t r i x ) ; b: = w h i c h ( p , o p n d , " f i r m " , s _ m a t r i x , f _ m a t r i x ) ; b END o p e r a n d _ i d e n t ; a:=operand i d e n t ( e l i g i b l e o p l i s t , 2 , r _ o p n d ) ; I F l _ o p n d ^= NULL THEN BEGIN c l e a n _ f l a g ; I F a-=#0 THEN a:=a AND o p e r a n d _ i d e n t ( e l i g i b l e o p l i s t , 1 , l _ o p n d ) END; a END o p _ i d e n t ; APPENDIX A <OPERATOR IDENTIFICATION> 85 COMMENT ' f o r m _ m a t r i x * f o r m s t h e ' s o r t * m a t r i x o f t h e • p l i s t ' ; p r o c e d u r e f o r m _ m a t r i x ( r e f e r e n c e (nd) v a l u e p l i s t ; b i t s v a l u e k,g1; STRING (6) VALUE s o r t ; BITS ARRAY s o r t m a t r i x (*) ) ; BEGIN REFERENCE (nd) p; BITS f 1 ; p: = p l i s t ; f1:=g1; WHILE p-=NULL DO BEGIN I F v(p)-.= modeO THEN BEGIN p o s t (mode (1) , v (p) , f 1 , s o r t , " ") ; IF s o r t = " s t r o n g " THEN BEGIN I F k AND #1 #0 THEN p o s t ( m o d e ( s k i p ) , v ( p ) , f 1 , s o r t , " ") ; IF k AND #2 #0 THEN p o s t (mode (jump) ,v (p) , f 1 , s o r t , " •') ; IF k AND #4 -.= #0 THEN p o s t (mode ( n i l ) , v (p) , f 1, s o r t , •• •») ; I F k AND #8 -.= #0 THEN p o s t ( m o d e ( v a c u u m ) , v ( p ) , f 1 , s o r t , " ") END END; p:=nxtmd(p); f 1 : = f 1 SHL 1 END; FOR i:=0 UNTIL max DO s o r t _ m a t r i x ( i ) :=f l a g (mode ( i ) ) ; IF t r a c e _ i t THEN BEGIN s a v e ("%£orm_matrix") ; s a v e m d l i s t ( p l i s t ) ; s a v e ( s o r t ) ; s a v e o u t END END f o r m _ m a t r i x ; COMMENT * c h e c k _ h i p * g i v e s a b i t s t r i n g s u c h t h a t e a c h o f t h e l o w e s t 4 b i t s i s on i f »skip*, •jump*, »nil* o r 'vacuum* i s i n t h e * o l i s t * r e s p e c t i v e l y ; BITS PROCEDURE c h e c k h i p (REFERENCE (nd) VALUE o l i s t ) ; BEGIN BITS k; REFERENCE(nd) p; k:=#0; p : = o l i s t ; WHILE p-=NULL DO BEGIN I F v (p) i = modeO THEN BEGIN I F -i ( l i n k (v (p) ) IS nd) THEN BEGIN I F t (v (p) ) = " s k i p " THEN k:=k OR #1 ELSE I F t (v (p))="jump" THEN k: = k OR #2 ELSE I F t (v (p) ) = " n i l " THEN k:= k OR #4 ELSE I F t ( v (p))="vacuum" THEN k:= k OR #8 END ELSE k:=k OR c h e c k _ h i p ( l i n k (v (p)) ) END; p:=nxtmd(p) END; k END c h e c k _ h i p ; COMMENT 'which* a c c e p t s a l i s t o f modes ' l i s t ' and an o p e r a n d 'x* and, d e p e n d i n g upon whether 'x' i s a mode, a c o l l a t e r a l mode d i s p l a y o r a s e r i a l / c o n d i t i o n a l mode d i s p l a y , i t d e t e r m i n e s which method t o u s e . i t r e t u r n s a b i t s t r i n g t h a t c a n be u s e d f o r s e l e c t i n g t h o s e e l e m e n t s o f ' l i s t ' which c a n be ' s o r t ' l y c o e r c e d from 'x*; BITS PROCEDURE which (REFERENCE(nd) VALUE l i s t ; REFERENCE (md) VALUE X ; STRING (6) VALUE s o r t ; BITS ARRAY s t r o n g _ m a t r i x , f e a t _ m a t r i x (*)) ; BEGIN BITS b; I F t r a c e _ i t THEN BEGIN s a v e ("%which:") ; s a v e m d l i s t ( l i s t ) ; s a v e o n ( " ; " ) ; APPENDIX A <OPERATOR IDENTIFICATION> 86 s a v e o p n d ( x ) ; s a v e o n (";") ;save ( s o r t ) ; s a v e o u t END; c l e a n _ u p ; b: = I F - * ( l i n k ( x ) IS nd) THEN BEGIN I F s o r t = » s t r o n g " THEN i d ( x , " s t r o n g " , s t r o n g _ m a t r i x ) ELSE i d (x, s o r t , f e a t _ m a t r i x ) END ELSE IF cw (x) = " c o l l " THEN c o l l a t e r a l ( l i s t , l i n k ( x ) , s o r t ) ELSE b a l a ( l i s t , l i n k ( x ) , s o r t , s t r o n g _ m a t r i x , f e a t _ m a t r i x ) ; b END w h i c h ; COMMENT ' i d ' d e l i v e r s a b i t s t r i n g b s u c h t h a t 'x' i s • s o r t ' l y c o e r c e a b l e t o e a c h o f t h e modes i n t h e l i s t c o r r e s p o n d i n g t o a ' 1 ' o f b; BITS PROCEDURE i d (REFERENCE(md) VALUE x; STRING (6) VALUE s o r t ; BITS ARRAY s o r t _ m a t r i x ( * ) ) ; BEGIN BITS b; b : = s o r t _ m a t r i x (mn (x)) ; I F t r a c e _ i t THEN BEGIN s a v e ("%id") ; save_md (x) ; s a v e ( s o r t ) ; s a v e o u t END; WHILE f i t ( x , s o r t ) DO BEGIN x : = f i e l d ( x ) ; b:=b OR s c r t _ m a t r i x (mn (x)) END; b END i d ; COMMENT ' c o l l a t e r a l * d e l i v e r s a b i t s t r i n g which may be used f o r s e l e c t i n g t h o s e e l e m e n t s o f ' p a r a m e t e r l i s t ' t o wh i c h t h e c o l l a t e r a l mode d i s p l a y ' o p e r a n d l i s t ' may be • s o r t ' l y b a l a n c e d ; BITS PROCEDURE c o l l a t e r a l (REFERENCE (nd) VALUE RESULT p a r a m e t e r l i s t ; REFERENCE (nd) VALUE o p e r a n d l i s t ; STRING<6) VALUE s o r t ) ; BEGIN COMMENT — * f i e l d l i s t e r « d e l i v e r s a l i s t o f t h e i - t h f i e l d o f e a c h o f t h e modes i n ' l i s t * ; REFERENCE (nd) PROCEDURE f i e l d l i s t e r ( INTEGER VALUE i ; REFERENCE (nd) VALUE l i s t ) ; I F l i s t = N U L L THEN NULL ELSE IF f i e l d ( v ( l i s t ) ) = N U L L THEN nd ( m o d e O , f i e l d l i s t e r ( i , n x t m d ( l i s t ) ) ) ELSE IF f i e l d ( v ( l i s t ) ) IS md THEN nd ( f i e l d (v ( l i s t ) ) , f i e l d l i s t e r ( i , n x t m d ( l i s t ) ) ) ELSE BEGIN REFERENCE(nd) p; p : = f i e l d ( v ( l i s t ) ) ; FOR j:=2 UNTIL i DO p:=nxtmd (p) ; nd ( v ( p ) , f i e l d l i s t e r ( i , n x t m d ( l i s t ) ) ) END; COMMENT — ' p i c k ' f o r m s a new 'nd' l i s t s u c h t h a t a mode c o r r e s p o n d i n g t o a * 1 ' i n * a ' i s p r e s e r v e d o t h e r w i s e modeO i s u s e d ; r e f e r e n c e ( n d ) p r o c e d u r e p i c k ( b i t s v a l u e a ; REFERENCE (nd) VALUE l i s t ; INTEGER VALUE i ) ; IF l i s t = N U L L THEN NULL ELSE BEGIN REFERENCE (md) m; m: = v ( l i s t ) ; nd( I F a AND #1 =#1 THEN APPENDIX A <OPERATOR I D E N T I F I C A T I O N 87 CASE i OF ( v ( l i s t ) , md ( t (m) , cw(m) , f l a g (m) ,mn (m) , nf (m) , p i c k (-#0,link (in) , i ) , f i e l d (m) ) ) ELSE modeO, p i c k ( a SHR 1, n x t m d ( l i s t ) , i ) ) END; BITS f , a , b , b 1 , r o w , s t r u c t ^ R E F E R E N C E ( n d ) p l i s t , r l i s t , q l i s t , p ; f:=#1; row:=struct:=#0; p : - p a r a m e t e r l i s t ; WHILE p-i=NULL DO BEGIN IF t ( v ( p ) ) (0j3) = "row" THEN row:=row OR f ELSE IF t ( v ( p ) ) = " s t r u c t " THEN s t r u c t : = s t r u c t OR f ; p:=nxtmd (p) ; f : = f SHL 1 END; COMMENT — c o n s i d e r t h o s e which b e g i n w i t h •row 1 o r • r o w o f ; i f p a r a m e t e r l i s t = n u l l t h e n BEGIN p a r a m e t e r l i s t : = n d (mode (9) ,NOLL) ; FOR i:=min UNTIL max DO IF t ( m o d e ( i ) ) (0|3)="row" THEN s e a r c h i n (mode (i ) , p a r a m e t e r l i s t ) ; p l i s t : = f i e l d l i s t e r ( 1 , p a r a m e t e r l i s t ) END ELSE p l i s t : = f i e l d l i s t e r ( 1 , p i c k ( r o w , p a r a m e t e r l i s t , 1 ) ) ; IF t r a c e _ i t THEN BEGIN s a v e { " ^ c o l l a t e r a l : " ) ; s a v e m d l i s t ( p a r a m e t e r l i s t ) ; s a v e o n ( " ; " ) ; s a v e m d l i s t ( o p e r a n d l i s t ) ; s a v e o n ( " ; " ) ; s a v e ( s o r t ) ; s a v e o u t END; g l i s t : = p i c k (-»#0,operandlist, 2) ; b: = b a l a n c e ( p l i s t , g l i s t , s o r t ) ; COMMENT f b » remembers t h o s e which a r e p o s s i b l e i f we have a row d i s p l a y . Next c o n s i d e r s t r o n g s t r u c t u r e d i s p l a y s ; IF s o r t = " s t r o n g " THEN I F s t r u c t -=#0 THEN BEGIN INTEGER no; COMMENT — f i r s t c o u n t t h e number "no' o f e l e m e n t s i n th e s t r u c t u r e d i s p l a y ' o p e r a n d l i s t ' ; p : = o p e r a n d l i s t ; no:=0; WHILE p-«=NULL DO BEGIN no:=no+1; p:=nxtmd(p) END; b1:=#0; f:=#1; p : = p a r a m e t e r l i s t ; WHILE p-=NULL DO BEGIN I F n f ( v ( p ) ) = n o THEN b1: = b1 OR f ; p:=nxtmd(p); f : = f SHL 1 END; COMMENT — — e l i m i n a t e t h o s e s t r u c t u r e s o f i n c o m p a t i b l e l e n g t h ; b1:=b1 AND s t r u c t ; I F b1-=#0 THEN BEGIN p l i s t : = p i c k ( b 1 , p a r a m e t e r l i s t , 1 ) ; f:=#1; p : = p a r a m e t e r l i s t ; a:=b1; FOR i:=1 UNTIL no DO IF a-.=#0 THEN BEGIN COMMENT c o n s i d e r e a c h o p e r a n d e l e m e n t i n t u r n ; BITS ARRAY s t r o n g _ m a t r i x ( 0 : : m a x ) ; BITS k; r l i s t : = f i e l d l i s t e r ( i , p l i s t ) ; COMMENT ' r l i s t ' c o n t a i n s t h e c o r r e s p o n d i n g p o r t r a y a l s ; p : = r l i s t ; WHILE p-=NULL DO BEGIN COMMENT jump o v e r t h e s e l e c t o r t o g e t APPENDIX A <OPERATOR I D E N T I F I C A T I O N 88 t h e mode; v ( p ) : = I F f i e l d ( v ( p ) ) = N U L L THEN modeO ELSE f i e l d ( v { p ) ) ; p:=nxtmd (p) END; c l e a n _ f l a g ; I F l i n k ( v ( o p e r a n d l i s t ) ) IS nd THEN k : = c h e c k _ h i p ( l i n k ( v ( o p e r a n d l i s t ) ) ) ELSE k : = c h e c k _ h i p (nd (v ( o p e r a n d l i s t ) ,NULL) ) ; f o r m _ m a t r i x ( r l i s t , k , # 1 , " s t r o n g " , s t r o n g _ m a t r i x ) ; a:=a AND which ( r l i s t , v ( o p e r a n d l i s t ) , " s t r o n g " , s t r o n g _ m a t r i x , s t r o n g _ m a t r i x ) ; o p e r a n d l i s t : = n x t m d ( o p e r a n d l i s t ) END; b:=b OR a END END; b END c o l l a t e r a l ; COMMENT "•balance* p r o d u c e s a b i t s t r i n g which may be u s e d f o r s e l e c t i n g t h o s e e l e m e n t s o f • p a r a m e t e r l i s t * t c which t h e s e r i a l / c o n d i t i o n a l d i s p l a y *operandlist» may be • s o r t ' l y b a l a n c e d . N o t e t h a t i f * p a r a m e t e r l i s t * i s n u l l and t h e ' s o r t ' i s meek, weak o r s o f t , t h e n i t w i l l s u p p l y i t s own by c a l l i n g ' p o s s i b l e * . I f t h e s o r t i s n o t g i v e n , t h e n i t w i l l c h e c k i f the ' o p e r a n d l i s t ' i s a c a l l o r a s l i c e , and i t w i l l s u p p l y t h e s u i t a b l e ' s o r t ' and t h e ' p a r a m e t e r l i s t ' ; BITS PROCEDURE b a l a n c e (REFERENCE (nd) VALUE RESULT p a r a m e t e r l i s t , o p e r a n d l i s t ; STRING (6) VALUE RESULT s o r t ) ; BEGIN REFERENCE(nd) p l i s t , p; BITS a; BITS ARRAY s t r o n g _ m a t r i x , f e a t _ m a t r i x (0::max); r a v e l ( o p e r a n d l i s t , 2 ) ; I F s o r t = " " THEN BEGIN REFERENCE(nd) mm; REFERENCE (md) mp, mg; m m : = o p e r a n d l i s t ; WHILE mm-»=NULL DO BEGIN mp: = v (mm); I F ( t (mp)="skip") OR ( t (mp) = "jump") OR (t (mp) =" n i l " ) OR (t (mp)="vacuum") THEN mm: = nxtmd (mm) ELSE mm: = NULL END; mg: = mp; WHILE mp->=NULL DO BEGIN s o r t := I F t(mp) (013) = "row" THEN "weak" ELSE I F t (mp) = " p r o c p " THEN "meek" ELSE " "; I F s o r t = " " THEN BEGIN mq: = mp; mp: = f i e l d (mp) END ELSE BEGIN I F t (mg)-.="ref" THEN mg:=mp; p a r a m e t e r l i s t : = p o s s i b l e (nd(mg, NULL), s o r t ) END END END; IF s o r t = " " THEN BEGIN w r i t e ( " * * * e r r o r : d u b i o u s s o r t * * * " ) ; a:=#0 END ELSE BEGIN I F p a r a m e t e r l i s t = NULL THEN I F (sort-»="strong") AND (sort-.= " f irm") THEN p a r a m e t e r l i s t : = p o s s i b l e ( o p e r a n d l i s t , s o r t ) ; p l i s t : = p a r a m e t e r l i s t ; f o r m _ m a t r i x ( p l i s t , c h e c k _ h i p ( o p e r a n d l i s t ) , # 1 , " s t r o n g " , s t r o n g _ m a t r i x ) ; IF s o r t " s t r o n g " THEN BEGIN c l e a n _ f l a g ; f o r m _ m a t r i x ( p l i s t , # 0 , # 1 , s o r t , f e a t _ m a t r i x ) END; APPENDIX A <TESTING> 89 a : = b a l a { p l i s t , o p e r a n d l i s t , s o r t , s t r o n g _ m a t r i x , f e a t _ m a t r i x ) ; I F t r a c e _ i t THEN BEGIN s a v e ("^balance:") ; s a v e m d l i s t ( p a r a m e t e r l i s t ) ; s a v e o n ( " ; " ) ; s a v e m d l i s t ( o p e r a n d l i s t ) ; s a v e o n (";") ; s a v e ( s o r t ) ; s a v e o u t END END; a END b a l a n c e ; COMMENT * b a l a * y i e l d s a b i t s t r i n g s u c h t h a t each o f the c o r r e s p o n d i n g modes i n t h e 'plist» c a n be ' s o r t ' l y b a l a n c e d f r o m t h e *olist»; BITS PROCEDURE bala ( R E F E R E N C E (nd) VALUE p l i s t , o l i s t ; STRING (6) VALUE s o r t ; BITS ARRAY s t r o n g _ m a t r i x , f e a t _ m a t r i x ( * ) ) ; BEGIN BITS a,b; REFERENCE(nd) p; p : = o l i s t ; a:=-#0; b:=#0; WHILE p-=NULL DO BEGIN I F v(p)-=modeO THEN BEGIN a := a AND w h i c h ( p l i s t , v ( p ) , " s t r o n g " , s t r o n g _ m a t r i x , f e a t _ m a t r i x ) ; I F s o r t -*= " s t r o n g " THEN b := b OR w h i c h ( p l i s t , v ( p ) , s o r t , s t r o n g _ m a t r i x , f e a t _ m a t r i x ) END; p := nxtmd(p) END; IF t r a c e _ i t THEN BEGIN s a v e ( " I b a l a " ) ; s a v e m d l i s t ( o l i s t ) ; s a v e ( s o r t ) ; s a v e o u t END; IF s o r t = " s t r o n g " THEN a ELSE a AND b END b a l a ; COMMENT * t e s t _ t h e m ' t e s t s a l l t h e p r o c e d u r e s ; PROCEDURE t e s t them; BEGIN COMMENT —,-. ' r e v e r s e _ r a v e l * i s t h e r e v e r s e o f r a v e l i n g u n i o n s . F o r ea c h u n i o n mode, add t o i t s f i e l d a l l d e f i n e d modes which a r e i t s p r o p e r s u b u n i o n s . A p r o p e r s u b u n i o n o f a g i v e n u n i o n mode i s a u n i o n , t h e s e t o f whose c o n s t i t u e n t modes i s a p r o p e r s u b s e t o f t h a t o f t h e g i v e n mode.; PROCEDURE r e v e r s e r a v e l ; BEGIN COMMENT ' i n c l u d e * d e t e r m i n e s whether t h e s o r t e d *nd* l i s t *p* i s i n c l u d e d i n t h e s o r t e d *nd* l i s t *g*; LOGICAL PROCEDURE i n c l u d e (REFERENCE(nd) VALUE p, g ) ; I F p=NULL THEN TRUE ELSE I F q=NULL THEN FALSE ELSE I F v ( p ) = v ( g ) THEN i n c l u d e (nxtmd ( p ) , nxtmd (q)) ELSE i n c l u d e (p, nxtmd (q) ) ; FOR. i : = min UNTIL max DO BEGIN REFERENCE (md) mi; mi: = m o d e ( i ) ; IF t ( m i ) = " u n i o n " THEN BEGIN FOR j:=min UNTIL max DO BEGIN IF t (mode ( j ) ) = " u n i o n " THEN APPENDIX A <TESTING> 90 IF i-.= j THEN I F i n c l u d e ( f i e l d (mode ( j ) ) , f i e l d (mi)) THEN BEGIN REFERENCE(nd) mq; m q : = f i e l d ( m i ) ; WHILE nxtmd (mq)-=NULL DO mq:=nxtmd (mq) ; nxtmd (mq): = nd (mode (j),NULL) END END END END; I F t r a c e _ i t THEN BEGIN s a v e ( " % r e v e r s e _ r a v e l " ) ; s a v e o u t END END r e v e r s e _ r a v e l ; REFERENCE(nd) m d l l , mdl2; REFERENCE(md) l o ; REFERENCE(md,nd) r o ; REFERENCE (ndo) op; STRING t e s t ; STRING (6) s o r t , c o e r c e n d ; BITS b; COMMENT — r - p e r f o r m t h e r e q u i r e d t e s t s ; w r i t e (" ") ; w r i t e ( " e n t e r command: d o n * t f o r g e t q u o t e s " ) ; w r i t e (" " ) ; r e a d ( t e s t ) ; w r i t e (" ") ; w r i t e o n ( t e s t ) ; I F t e s t = " t r a c e " THEN BEGIN w r i t e ( " t r a c e t u r n e d o n " ) ; t r a c e _ i t : = TRUE END ELSE I F t e s t = " n o t r a c e " THEN BEGIN t r a c e _ i t : = FALSE; w r i t e ( " t r a c e t u r n e d o f f " ) END ELSE I F t e s t = " e q u i v a l e n c e " THEN BEGIN e q u i v a l e n c e ; FOR i:=0 UNTIL min-1 DO BEGIN f l a g (mode(i)) : = #0; l i n k (mode ( i ) ) :=NUIL END; w r i t e ("modes e g u i v a l e n c e d " ) ; FOR i:=min UNTIL max DO BEGIN s a v e (mpr ( i ) ) ; s a v e ("=") ; save_md (mode ( i ) ) ; s a v e o u t ; f l a g ( m o d e ( i ) ) : = # 0 ; l i n k ( m o d e ( i ) ) : = N U 1 L END; r e v e r s e _ r a v e l END ELSE IF t e s t = » r e l a t e d " THEN BEGIN w r i t e ( " e n t e r : m o d e l i s t " ) ; w r i t e (" ") ; s a v e ( " m o d e . l i s t " ) ; m d l l : = r e a d m d l i s t ; s a v e m d l i s t ( m d l 1 ) ; s a v e o u t ; m d l 2 : = r e l a t e d ( m d l l ) ; I F mdl2-.= NULL THEN BEGIN s a v e ( " t h e " ) ; s a v e ( " s e t " ) ; s a v e m d l i s t ( m d l 2 ) ; s a v e ( " c o n t a i n s " ) ; s a v e ( " r e l a t e d " ) ; s a v e ("modes."); s a v e o u t END ELSE w r i t e ("no two o f t h e s e modes a r e r e l a t e d " ) ; c l e a n _ f l a g END ELSE I F t e s t = " c o e r c e " THEN BEGIN w r i t e ( " e n t e r : a p r i o r i mode, a p o s t e r i o r i mode,"); w r i t e o n (" s o r t , c o e r c e n d " ) ; w r i t e (" ") ; lo:=readmd; ro:=readmd; r e a d o n ( s o r t ) ; r e a d o n ( c o e r c e n d ) ; w r i t e o n ( s o r t ) ; w r i t e o n ( " ") ; w r i t e o n ( c o e r c e n d ) ; IF c o e r c e ( l o , r o , s o r t , c o e r c e n d ) THEN s a v e o u t ELSE BEGIN o u t _ l i n e ; = " "; o u t _ p t r : = 1; save_md ( l o ) ; s a v e ( " n o t " ) ; s a v e ( s o r t ) ; s a v e o n ( " l y " ) ; s a v e ( " c o e r c e a b l e " ) ; s a v e ( " t o " ) ; save_md ( r o ) ; s a v e o u t END; c l e a n _ u p END ELSE I F t e s t = " i d e n t i f y " THEN BEGIN w r i t e ( " e n t e r : mode, s o r t , m o d e l i s t " ) ; w r i t e (" " ) ; r o : = readmd; s a v e ("mode:"); s a v e o p n d ( r o ) ; APPENDIX A <TESTING> 91 s a v e o n C 1 ; " ) ; r e a d o n ( s o r t ) ; s a v e ( " s o r t : " ) ; s a v e ( s o r t ) ; s a v e o n ( " ; " ) ; w r i t e o n ( s o r t ) ; m d l l : = r e a d m d l i s t ; s a v e ( " m o d e . l i s t : ") ; s a v e m d l i s t (mdl1) ; s a v e o u t ; w r i t e ( " p o s s i b l e modes i d e n t i f i e d : ") ; s a v e m d l i s t ( s e l e c t ( i d e n t i f y ( m d l l , r o , s o r t ) , m d l l ) ) ; clean_up;' s a v e o u t END ELSE IF ( t e s t = " b a l a n c e " ) OS ( t e s t = " c o l l a t e r a l " ) THEN BEGIN w r i t e ( " e n t e r : o p e r a n d modes, s o r t , p a r a m e t e r modes"); write(» " ) ; m d l l : = r e a d m d l i s t ; s a v e ( " o p e r a n d . d i s p l a y : " ) ; s a v e m d l i s t ( m d l l ) ; s a v e o n (";"); r e a d o n ( s o r t ) ; s a v e ( " s o r t : " ) ; w r i t e o n ( s o r t ) ; s a v e ( s o r t ) ; s a v e o n ( " ; " ) ; m d l 2 : = r e a d m d l i s t ; s a v e ( " p a r a m e t e r s : " ) ; s a v e m d l i s t (mdl2) ; s a v e o u t ; w r i t e ( " p o s s i b l e ", t e s t , " : " ) ; b:= I F t e s t = " b a l a n c e " THEN b a l a n c e ( m d l 2 , m d l l , s o r t ) ELSE c o l l a t e r a l ( m d l 2 , m d l l , s o r t ) ; s a v e m d l i s t ( s e l e c t (b, m d l 2 ) ) ; c l e a n _ u p ; s a v e o u t END ELSE IF t e s t = " o p e r a t o r s " THEN BEGIN w r i t e ( " e n t e r : l e f t o p e r a n d , r i g h t o p e r a n d , " , " o p e r a t o r s " ) ; w r i t e (" ") ; lo:=readmd; ro:=readmd; w r i t e (" " ) ; op: = r e a d o p l i s t ; s a v e ( " l e f t . o p e r a n d : " ) ; s a v e o p n d ( l o ) ; s a v e o n ( " ; " ) ; s a v e o u t ; s a v e ( " r i g h t . o p e r a n d : " ) ; s a v e o p n d ( r o ) ; s a v e o n ( " ; " ) ; s a v e o u t ; s a v e ( " o p e r a t o r s : " ) ; s a v e o p l i s t ( o p ) ; s a v e o u t ; w r i t e ( " p o s s i b l e o p e r a t o r s : " ) ; s a v e o p l i s t ( s e l e c t o ( o p _ i d e n t ( o p , r o , l o ) ,op)) ; c l e a n _ u p ; s a v e o u t END ELSE ~ IF t e st="grammar" THEN enter_grammar ELSE IF t e s t = " s t o p " THEN work:=FALSE ELSE BEGIN w r i t e ( " s o r r y - t r y a g a i n " , " — c o e r c e , r e l a t e d , grammar, i d e n t i f y , b a l a n c e , " , " c o l l a t e r a l , o p e r a t o r s , e g u i v a l e n c e , t r a c e , " , " n o t r a c e o r s t o p . " ) ; w r i t e ( " *») END END t e s t _ t h e m ; CONSENT ' i d e n t i f y * d e l i v e r s a b i t s t r i n g t h a t can be used f o r s e l e c t i n g t h o s e e l e m e n t s o f ' p l i s t ' t o which t h e mode »x» may be ' s o r t ' l y c o e r c e d ; BITS PROCEDURE i d e n t i f y ( R E F E R E N C E (nd) VALUE p l i s t ; REFERENCE (md) VALUE x; STRING (6) VALUE s o r t ) ; • BEGIN BITS ARRAY s t r o n g _ m a t r i x , f e a t _ m a t r i x (0::max); BITS k, b; k:=#0; IF t r a c e _ i t THEN BEGIN save ( " S l i d e n t i f y : " ) ; s a v e m d l i s t ( p l i s t ) ; s a v e o n (";") ; s a v e o p n d ( x ) ; s a v e o n (";") ; s a v e ( s o r t ) ; s a v e o u t END; I F s o r t = " s t r o n g " THEN BEGIN f o r m _ m a t r i x ( p l i s t , c h e c k _ h i p ( n d ( x , N U L L ) ) , # 1 , s o r t , s t r o n g _ m a t r i x ) ; b : = i d ( x , s o r t , s t r o n g _ m a t r i x ) END ELSE BEGIN f o r m _ m a t r i x ( p l i s t , # 0 , # 1 , s o r t / f e a t _ m a t r i x ) ; b: = i d (x, s o r t , f ea t _ m a t r i x ) END; b END i d e n t i f y ; APPENDIX A <TESTING> 92 COMMENT ' s e l e c t o ' d o e s t h e same j o b a s ' s e l e c t ' b u t f o r » n d o ' - l i s t s ; REFERENCE (ndo)PROCEDURE s e l e c t o (BITS VALUE a ; REFERENCE (ndo) VALUE l i s t ) ; I F l i s t = N U L L THEN NULL ELSE IF a AND #1 = #1 THEN ndo (op_symbol ( l i s t ) , l _ p a r ( l i s t ) , r _ p a r ( l i s t ) , s e l e c t o (a SHR 1, n x t o p ( l i s t ) ) ) ELSE s e l e c t o (a SHR 1, n x t o p ( l i s t ) ) ; COMMENT 'enter_grammar• a c c e p t s a number o f r u l e s o f t h e f o r m 'n s m', where «n' i s an i n t e g e r , ' s * i s a s t r i n g and 'm' i s an i n t e g e r ( r e p r e s e n t i n g one mode) o r an i n t e g e r s e g u e n c e f o l l o w e d by -2 ( r e p r e s e n t i n g a l i s t o f modes). The l i s t i s u s e d i n t h e c a s e t h a t t h e s t r i n g i s " s t r u c t " , " u n i o n " o r " p r o c p " ; PROCEDURE enter_grammar; BEGIN I N T E G E R ~ i ; STRING (6) t e r m i n a l ; max:=15; FOR i:=min UNTIL max+20 DO mode ( i ) : = md (" ", " ", #0, i , 0, NULL, NOLL); w r i t e ( " e n t e r t h e grammar:"); w r i t e (" ") ; WHILE BEGIN r e a d ( i ) ; w r i t e (" " ) ; w r i t e o n ( i ) ; i>-2 END DO BEGIN I F (i>max) AND (i<35) THEN roax:-i; I F ( K r n i n ) OR (i>34) THEN BEGIN i:=35; I F t (mode (35) ) =» " THEN w r i t e ( " * * * w a r n i n g *** t h e r e i s a r e s t r i c t i o n ", » 1 5 < i < 3 5 . ") ELSE w r i t e ("*** i i s o u t s i d e t h e l i m i t s 15<i<35 a g a i n , ", " t h e p r e v i o u s mode(i) w i t h i o u t s i d e t h e ", " l i m i t s w i l l n ot be e n t e r e d ***") END; r e a d o n ( t e r m i n a l ) ; t (mode ( i ) ) : = t e r m i n a l ; w r i t e o n (" ") ; w r i t e o n ( t e r m i n a l ) ; f i e l d ( m o d e ( i ) ) : = I F ( t e r m i n a l -*= " u n i o n " ) AND ( t e r m i n a l " s t r u c t " ) AND ( t e r m i n a l -«= " p r o c p " ) THEN readmd ELSE BEGIN INTEGER n; REFERENCE (nd)11,12; 11: = r e a d m d l i s t ; 12: = 11; n;=0; WHILE 12-=NULL DO BEGIN 12:=nxtmd(12); n:=n+1 END; nf (mode ( i ) ) : = n ; 11 END; I F f i e l d ( m o d e ( i ) ) IS md THEN nf (mode ( i ) ) : = 1 END; IF t (mode(35))-=" " THEN BEGIN I F max<35 THEN BEGIN max:=max + 1; mode (max): = mode(35) END END; COMMENT . p r i n t t h e mode t a b l e , f i r s t as a grammar and s e c o n d as a l i s t o f i n d i v i d u a l modes; FOR i:=min UNTIL max DO I F mode(i) -.= NULL THEN I F f i e l d (mode ( i ) ) -«= NULL THEN BEGIN REFERENCE(md) m; s a v e ( m p r ( i ) ) ; save ("=") ; m: = m o d e ( i ) ; s a v e (t (m)) ; IF f i e l d (m) IS md THEN s a v e (mpr (mn ( f i e l d (m)))) ELSE BEGIN REFERENCE (nd) p; p: = f i e l d (m) ; WHILE p--=NULL DO BEGIN s a v e (mpr (mn (v ( p ) ) ) ) ; p:=nxtmd(p); I F p-=NULL APPENDIX A <INPDT> THEN saveon(",») END END; s a v e o u t END; w r i t e (" " ) - ; FOB i:=min UNTIL max DO BEGIN s a v e (mpr ( i ) ) ; s a v e ("="); save_md ( m o d e ( i ) ) ; s a v e o u t END END enter_grammar; COMMENT ' r e a d m d l i s t * r e a d s a s e q u e n c e o f i n t e g e r s which i t i n t e r p r e t e s a s a l i s t o f modes. The l i s t must end w i t h t h e v a l u e »-,2' ; REFERENCE(nd) PROCEDURE r e a d m d l i s t ; BEGIN REFERENCE(md) m; m:=readmd; I F m=NULL THEN NULL ELSE nd(m, r e a d m d l i s t ) END r e a d m d l i s t ; COMMENT 'readmd' r e a d s e i t h e r a mode ( i . e . , an i n t e g e r ) o r a mode d i s p l a y ( i . e . -1 f o l l o w e d by a s t r i n g f o l l o w e d by an i n t e g e r s e g u e n c e f o l l o w e d by - 2 ) . Note t h a t d u r i n g i n p u t o f t h e grammar t h i s p r o c e d u r e i s a l w a y s g i v e n a n o n - n e g a t i v e i n t e g e r ; r e f e r e n c e (md) p r o c e d u r e readmd; EEGIN INTEGER i ; REFERENCE(md) m; r e a d o n ( i ) ; w r i t e o n ( i ) ; IF i>=0 THEN m:=mode(i) ELSE I F i<=-2 THEN m:=NULL ELSE BEGIN STRING (6) s; r e a d o n ( s ) ; w r i t e o n ( s ) ; m: = md(" ", s, #0, - 1 , 0, r e a d m d l i s t , NULL) END; m END readmd; COMMENT • r e a d o p l i s t ' r e a d s a s e q u e n c e o f i n t e g e r p a i r s which a r e i n t e r p r e t e d a s t h e l e f t and r i g h t p a r a m e t e r modes o f t h e o p e r a t o r •+*. I t i s t e r m i n a t e d by t h e p a i r -2 - 2 ; REFERENCE(ndo) PROCEDURE r e a d o p l i s t ; BEGIN REFERENCE(md)ml,m2; m1:=readmd; m2:=readmd; IF m2=NULL THEN NULL ELSE ndo("+", ml, m2, r e a d o p l i s t ) END r e a d o p l i s t ; COMMENT • s a v e o p l i s t ' s a v e s t h e o p e r a t o r l i s t * o l ' f o r o u t p u t ; PROCEDURE s a v e o p l i s t (REFERENCE(ndo) VALUE o l ) ; WHILE ol-=NULL DO BEGIN s a v e (»» <") ; s a v e o p n d ( l _ p a r ( c l ) ) ; s a v e o n (op_symbol ( o l ) ) ; s a v e o p n d ( r _ p a r ( o l ) ) ; s a v e o n ( " ) " ) ; o l : = n x t o p ( o l ) ; I F ol-*=NULL THEN s a v e o n (",") END s a v e o p l i s t ; COMMENT 'saveopnd* s a v e s a mode o r a mode d i s p l a y f o r o u t p u t ; PROCEDURE saveopnd(REFERENCE(md) VALUE l o ) ; I F lo=NULL THEN s a v e ( " n u l l " ) ELSE I F l i n k ( l o ) IS nd THEN BEGIN save ( " ( " ) ; s a v e m d l i s t ( l i n k ( l o ) ) ; s a v e o n (")") END ELSE save_md ( l o ) ; COMMENT ' s a v e m d l i s t ' s a v e s t h e mode l i s t » m d l ' f o r o u t p u t ; PROCEDURE s a v e m d l i s t ( R E F E R E N C E (nd) VALUE mdl) ; WHILE mdl-=NUIL DO APPENDIX A <OUTPUT> 94 BEGIN s a v e o p n d (v (mdl)) ; mdl: = nxtmd (mdl) ; IE mdl-=NULL THEN s a v e o n (",") END s a v e m d l i s t ; PROCEDURE s a v e o n (STRING VALUE s 1 ) ; BEGIN o u t _ p t r : = o u t _ p t r - 1 ; s a v e ( s 1 ) END s a v e o n ; COMMENT ' s a v e ' s a v e s t h e n o n - b l a n k p a r t o f * s 1 ' i n • o u t _ l i n e * f o l l o w e d by one b l a n k ; PROCEDURE s a v e (STRING VALUE s 1 ) ; BEGIN INTEGER i ; i : = 0 ; I F o u t _ p t r > 2 2 5 THEN s a v e o u t ; WHILE i<=15 DO I F s 1 ( i | 1 ) = " THEN i:=16 ELSE BEGIN o u t _ l i n e ( o u t _ p t r | 1) :=s1 ( i | 1) ; i:=i+1 ; o u t _ p t r : = o u t _ p t r + 1 END; o u t _ p t r : = o u t _ p t r + 1 END s a v e ; COMMENT 'save_md* s a v e s t h e mode »m' i n t h e s t r i n g • o u t _ l i n e ' f o r t h e p u r p o s e o f r e a d a b l e o u t p u t ; PROCEDURE save_md(REFERENCE(md) VALUE a); BEGIN I F m NULL THEN BEGIN BITS s g n ; sgn:=#80000000; IF nf(m)=0 THEN s a v e ( t ( m ) ) ELSE IF f l a g ( m ) AND sgn=#0 THEN BEGIN s a v e ( t ( m ) ) ; f l a g (m) : = f l a g (m) OR s g n ; IF ( t (m)-="union") AND (t (m)-.="procp") AND (t <m) - = » s t r u c t M ) THEN save_md ( f i e l d (m)) ELSE IF t (m) =«'procp" THEN BEGIN REFERENCE (nd) p; s a v e ("(•') ; o u t _ p t r : = o u t _ p t r - 1 ; p:= f i e l d (m) ; WHILE p-^=NULL DO BEGIN I F nxtmd (p)=NULL THEN s a v e o n (»)») ; save_md (v (p) ) ; p: = nxtmd (p) END END ELSE BEGIN s a v e ('»("); s a v e m d l i s t ( f i e l d (m) ) ; s a v e o n (»)») END; f l a g (m) : = f l a g (m) AND - s g n END ELSE save(mpr(mn(m))) END END save_md; COMMENT ' s a v e o u t * p r i n t s o u t t h e o u t p u t b u f f e r • o u t _ ; l i n e ' ; PROCEDURE s a v e o u t ; BEGIN w r i t e ( o u t _ l i n e (0J60)) ; I F o u t _ p t r > 6 0 THEN w r i t e ( o u t j l i n e ( 6 0 1 6 0 ) ) ; I F o u t _ p t r > 1 2 0 THEN w r i t e ( o u t _ l i n e (120|60)) ; IF o u t _ p t r > 1 8 0 THEN w r i t e ( o u t _ l i n e ( 1 8 0 | 6 0 ) ) ; o u t _ p t r : = 1 ; o u t _ l i n e ; = " " END s a v e o u t ; LOGICAL t r a c e _ i t , work; INTEGER v o i d , i n t , b o o l , r e a l l , c h a r , f o r m a t , b i t s l , b y t e s , s t r n g , c o m p l , s k i p , jump, n i l , vacuum, min, max, o u t _ p t r ; REFERENCE(md) ARRAY mode{0::35); REFERENCE(md) modeO; STRING (240) o u t _ l i n e ; COMMENT i n i t i a l i z a t i o n p a r t . ' t r a c e _ i t ' i s a l o g i c a l v a r i a b l e which c o n t r o l s some b u i l t i n t r a c i n g ; APPENDIX A 95 s t a r t : i n t f i e l d s i z e : = 4 ; o u t _ l i n e : = " o u t _ p t r : = 1 ; t r a c e _ i t : = F A L S E ; work:=TRUE; void:=0 ; b o o l : = 1 ; i n t : = 2 ; r e a l 1 : = 3 ; char:=4; f o r m a t : = 5 ; b i t s 1 : = 6 ; b y t e s : = 7 ; ccmpl:=8; s t r n g : = 9 ; s k i p : = 1 2 ; jump:=13; n i l : = 1 4 ; vacuum:=15; min:=16; max:=15; mode6:=md(" "," ",#0,-1,0,NULL,NULL); m o d e ( v o i d ) : = md ( " v o i d " , " ",#0,0,0,NULL,NULL) ; mode ( b o o l ) : = md ( " b o o l " , " ",#0,1,0,NULL,NULL); mode ( i n t ) : = md ( " i n t " , " ",#0,2,0,NULL,NULL) ; mode ( r e a l l ) : = m d ( " r e a l " , " ",#0,3,0,NULL,NULL) ; mode ( c h a r ) : = m d ( " c h a r " , " ",#0,4,0,NULL,NULL) ; mode ( f o r m a t ) : = md ("format"," ",#0,5,0,NULL,NULL); mode ( b i t s l ) : = m d ( " b i t s " , " ",#0,6,0,NULL,NULL) ; mode(bytes) :=md("bytes"," ",#0,7,0,NULL,NULL) ; mode (10):=md ("re" , " " , # 0 , 1 0 , 1 , N U L L , m o d e ( r e a l l ) ) ; mode (11):=md(»im"," » , # 0 , 1 1 , 1 , N U L L , m o d e ( r e a l l ) ) ; mode (skip):=md ( " s k i p " , " ",#0,12,0,NULL,NULL); mode (jump) :=md ("jump"," ",#0,13,0,NULL,NULL) ; m o d e ( n i l ) : = m d ( " n i l " , " ",#0,14,0,NULL,NULL) ; mode(vacuum) : = md("vacuum"," » , # 0 , 1 5 , 0 , N U L L , N U L L ) ; mode(compl) : = md ( " s t r u c t " , " ",#0,8,2,NULL, nd (mode (10) ,nd(mode(11) ,NULL))) ; mode ( s t r n g ) : = md ("rowof"," ",#0,9,1,NULL,mode ( c h a r ) ) ; WHILE work DO t e s t _ t h e m ; END. How To Use The Program The program a c c e p t s t h e f o l l o w i n g commands which must be e n c l o s e d i n g u o t e s : "TRACE", "NOTRACE", "GRAMMAR", "EQUIVALENCE", "COERCE", "RELATED", "IDENTIFY", "BALANCE", "COLLATERAL", "OPERATORS" and "STOP". E x c e p t f o r "TRACE", "NOTRACE", "EQUIVALENCE" and "STOP", i n p u t i n a c e r t a i n f o r m a t i s t o be e n t e r e d . A mode which i s no t n u l l i s r e p r e s e n t e d by a n o n - n e g a t i v e i n t e g e r l e s s t h a n o r e g u a l t o t h e maximum o f t h e r u l e number e n t e r e d i n t h e grammar ( t h a t i s l e s s t h a n o r e g u a l t o 3 5 ) . A n u l l mode i s r e p r e s e n t e d by an i n t e g e r l e s s t h a n - 1 . A mode l i s t i s a s e q u e n c e o f modes (0 < i n t e g e r s < 35) f o l l o w e d by an i n t e g e r l e s s t h a n - 1 . A mode d i s p l a y i s a mode l i s t p r e c e d e d by -1 " c o l l " , -1 " s e r i " o r -1 " c o n d " e.g. -1 " c o l l " 2 3 14 - 2 . • s o r t ' i s a s t r i n g , i t i s " s t r o n g " , " f i r m " , "meek", "weak" o r " s o f t " . ' c o e r c e n d * i s a s t r i n g , i t i s e i t h e r " c o m o r f " t o t e l l t h a t t h e c o e r c e n d i s a c o m o r f o r "morf" ( or " " ) t o t e l l t h a t t h e c o e r c e n d i s n o t a co m o r f . An o p e r a n d i s a mode o r a mode d i s p l a y . A l i s t o f o p e r a t o r s i s a s e g u e n c e o f p a i r s o f o p e r a n d s t e r m i n a t e d by -2 -2. An u n a r y o p e r a t o r i s an o p e r a t o r whose f i r s t ( l e f t ) o p e r a n d i s n u l l . The s t a n d a r d modes o f t h e program a r e as f o l l o w s : APPENDIX A 96 mO = v o i d ml = b o o l m2 = i n t m3 = r e a l mU = c h a r m5 = f o r m a t m6 = b i t s m7 = b y t e s m8 = s t r u c t m10 m11 (complex) m9 = rowof m4 ( s t r i n g ) m10 = r e m3 m11 = im m3 m12 = s k i p m13 = jump ra14 = n i l m15 = vacuum. (1) The command "TRACE" t u r n s on a b u i l t i n t r a c e , "NOTRACE" t u r n s t h a t o f f . (2) When t h e command i s "GRAMMAR", r u l e s o f a mode grammar f o l l o w e d by an i n t e g e r l e s s t h a n -1 t h a t shows t h e end o f t h e s e t o f r u l e s , a r e t o be e n t e r e d . Each r u l e o f t h e mode grammar i s e n t e r e d as m t p where (a) m i s an i n t e g e r s u c h t h a t 15 < m < 35. (b) t i s a t e r m i n a l which i s a s t r i n g s o t h a t i t must be e n c l o s e d i n q u o t e s . The t e r m i n a l s a r e " r e f " , " p r o c " , "row", " r o w o f " , " u n i o n " , " s t r u c t " , " p r o c p " ( p r o c e d u r e w i t h p a r a m e t e r s ) , o r a f i e l d - s e l e c t o r o f a s t r u c t u r e , o r any o t h e r s t a n d a r d mode. (c) p i s e i t h e r a mode o r when t i s " s t r u c t " , " u n i o n " o r " p r o c p " a mode l i s t . T h i s command a l l o c a t e s a r e c o r d •md1 t o e a c h r u l e e n t e r e d , so t h a t t h e y c an be u s e d by some o t h e r commands t o f o l l o w . (3) The command "EQUIVALENCE" c o m p a c t s t h e mode grammar by r e m o v i n g e q u i v a l e n t modes. (4) When t h e command i s "COERCE", t h e s o u r c e mode (the a p r i o r i mode), t h e t a r g e t mode(the a p o s t e r i o r i mode), t h e s o r t ( p o s i t i o n ) and t h e c o e r c e n d a r e t o be e n t e r e d . I t d e t e r m i n e s whether t h e a p r i o r i mode i s s o r t l y c o e r c e a b l e t o t h e a p o s t e r i o r i mode. (5) F o r t h e command "RELATED", t h e i n p u t i s a mode l i s t . T h i s d e t e r m i n e s whether t h e r e a r e r e l a t e d modes i n t h e mode l i s t . (6) The i n p u t f o l l o w i n g "IDENTIFY" i s mode, s o r t and mode APPENDIX A 97 l i s t . T h i s i s t o i d e n t i f y f r o m t h e mode l i s t t h o s e modes t o whic h t h e g i v e n mode i s s o r t l y c o e r c e a b l e . (7) The i n p u t f o l l o w i n g "BALANCE" o r "COLLATERAL" i s s o u r c e mode l i s t , s o r t , t a r g e t mode l i s t . The s o u r c e mode l i s t c o n t a i n s t h e modes i n a c o n d i t i o n a l / s e r i a l c l a u s e o r a c o l l a t e r a l c l a u s e , and any one o f t h e s e modes may be a s e r i a l / c o n d i t i o n a l o r c o l l a t e r a l mode d i s p l a y . The command "BALANCE" d e t e r m i n e s f r o m t h e t a r g e t mode l i s t t h e modes t o whic h t h e s e r i a l / c o n d i t i o n a l mode d i s p l a y ( i . e . t h e s o u r c e mode l i s t ) c a n be s o r t l y c o e r c e d . The command "COLLATERAL" d e t e r m i n e s from t h e t a r g e t mode l i s t t h o s e modes t o which t h e c o l l a t e r a l mode d i s p l a y c a n be s o r t l y c o e r c e d . (8) The i n p u t f o l l o w i n g t h e command "OPERATORS" i s l e f t o p e r a n d , r i g h t o p e r a n d and t h e l i s t o f o p e r a t o r s . T h i s i d e n t i f i e s f r o m t h e l i s t o f o p e r a t o r s t h a t o p e r a t o r ( o r t h o s e o p e r a t o r s i f ambiguous) i d e n t i f i e d by a f o r m u l a w i t h t h e g i v e n o p e r a n d s . Note t h a t u n a r y o p e r a t o r s and b i n a r y o p e r a t o r s a r e n o t t o be mixed i n t h e o p e r a t o r s and t h a t o n l y a l i s t o f u n a r y o p e r a t o r s w i l l be g i v e n a s a t a r g e t l i s t f o r a monadic f o r m u l a . (9) The command "STOP" t e r m i n a t e s t h e e x e c u t i o n . A Sample Run ENTER COMMAND: DON'T FORGET QUOTES NOTRACE TRACE TURNED OFF ENTER COMMAND: DON'T FORGET QUOTES GRAMMAR ENTER THE GRAMMAR: 16 REF 3 17 PROC 3 18 REF 17 19 ROWOF 3 20 REF 19 21 UNION 2 3 19 22 STRUCT 23 25 -2 23 A 24 24 ROWOF 4 25 B 26 26 REF 22 27 ROWOF 1 28 UNION 1 21 -2 29 UNION 1 21 -2 30 REF 30 -2 APPENDIX A 98 H16 = REF REAL M17 = PROC REAL Ml 8 = REF M17 M19 = ROWOF REAL M20 = REF M19 M21 = ONION INT, REAL, M19 M22 = STRUCT M23, M25 M23 = A M24 M24 = ROWOF CHAR M25 = B M26 M26 = REF M22 M27 = ROWOF BOOL M28 = UNION BOOL, M21 M29 = UNION BOOL, M21 M30 = REF M30 M16 = REF REAL M17 = PROC REAL M18 = REF PROC REAL M19 = ROWOF REAL M20 = REF ROWOF REAL M21 = UNION ( INT, REAL, ROWOF REAL) M22 = STRUCT ( A ROWOF CHAR, B REF M22) M23 = A ROWOF CHAR M24 = ROWOF CHAR M25 = B REF STRUCT ( A ROWOF CHAR, M25) M26 = REF STRUCT ( A ROWOF CHAR, B M26) M27 = ROWOF BOOL M28 = UNION ( BOOL, UNION ( INT, REAL, ROWOF REAL)) M29 = UNION { BOOL, UNION ( INT, REAL, ROWOF REAL)) M30 = REF M30 ENTER COMMAND: DON'T FORGET QUOTES EQUIVALENCE CONTEXT CONDITION ERROR INVOLVING THE MODE REF K30, WHICH IS REPLACED BY 'BOOL'. MODES EQUIVALENCED M16 = REF REAL M17 = PROC REAL M18 = REF PROC REAL M19 = ROWOF REAL M20 = REF ROWOF REAL M21 = UNION ( INT, REAL, ROWOF REAL) M22 = STRUCT ( A ROWOF CHAR, B REF M22) M23 = A ROWOF CHAR M2U = B REF STRUCT ( A ROWOF CHAR, M24) M25 = REF STRUCT ( A ROWOF CHAR, B M25) M26 = ROWOF BOOL M27 = UNION ( BOOL, INT, REAL, ROWOF REAL) ENTER COMMAND: DON'T FORGET QUOTES COERCE APPENDIX A 99 ENTER: A PRIGBI MODE, A POSTERIOR I MODE, SORT, COERCEND 18 0 STRONG COMORF STRONG COERCION OF COMORF REF PROC REAL TO VOID : VOIDED TO VOID ENTER COMMAND: DON'T FORGET QUOTES COERCE ENTER: A PRIORI MODE, A POSTERIORI MODE, SORT, COERCEND 18 0 STRONG MORF STRONG COERCION OF MORF REF PROC REAL TO VOID : DEREF TO M1 7 DEPROC TO REAL VOIDED TO VOID ENTER COMMAND: DON'T FORGET QUOTES COERCE ENTER: A PRIORI MODE, A POSTERIORI MODE, SORT, COERCEND 18 21 FIRM MORF FIRM COERCION OF MORF REF PROC REAL TO UNION ( INT, REAL, R OWOF REAL) : DEREF TO M17 DEPROC TO REAL UNITE TO M21 ENTER COMMAND: DON'T FORGET QUOTES COERCE ENTER: A PRIORI MODE, A POSTERIORI MODE, SORT, COERCEND 18 21 MEEK MORF REF PROC REAL NOT MEEKLY COERCEABLE TO UNION ( INT, REAL, R OWOF REAL) ENTER COMMAND: DON'T FORGET QUOTES COERCE ENTER: A PRIORI MODE, A POSTERIORI MODE, SORT, COERCEND 18 -2 FIRM MORF REF PROC REAL FIRMLY COERCEABLE TO REAL, PROC REAL, REF PRO C REAL ENTER COMMAND: DON'T FORGET QUOTES RELATED ENTER: MODELIST 3 16 17 18 19 -2 MODE.LIST REAL, REF REAL, PROC REAL, REF PROC REAL, ROWOF R E AL THE SET REAL, REF REAL, PROC REAL, REF PROC REAL CONTAINS R ELATED MODES. ENTER COMMAND: DON'T FORGET QUOTES IDENTIFY ENTER: MODE, SORT, MODELIST 18 STRONG 16 20 21 22 -2 MODE: REF PROC REAL; SORT: STRONG; MODE.LIST: REF REAL, REF ROWOF REAL, UNION ( INT, REAL, ROWOF REAL), STRUCT ( A ROWO F CHAR, B REF M22) APPENDIX A 100 POSSIBLE MODES IDENTIFIED: UNION { INT, BEAL, BOWOF BEAL) ENTER COMMAND: DON'T FORGET QUOTES BALANCE ENTER: OPERAND MODES, SORT, PARAMETER MODES 20 16 -2 WEAK 3 18 19 20 -2 OPERAND.DISPLAY: REF BOWOF REAL, REF REAL; SORT: WEAK; PARA METERS: REAL, REF PROC REAL, ROWOF REAL, REF ROWOF REAL POSSIBLE BALANCE : REF ROWOF REAL ENTER COMMAND: DON'T FORGET QUOTES BALANCE ENTER: OPERAND MODES, SORT, PARAMETER MODES 20 18 -2 MEEK 3 18 19 20 -2 OPERAND.DISPLAY: REF ROWOF REAL, REF PROC REAL; SORT: MEEK; PARAMETERS: REAL, REF PROC REAL, ROWOF REAL, REF ROWOF REAL POSSIBLE BALANCE : ROWOF REAL ENTER COMMAND: DON'T FORGET QUOTES BALANCE ENTER: OPERAND MODES, SORT, PARAMETER MODES 17 18 -2 FIRM -2 OPERAND.DISPLAY: PROC REAL, REF PROC SEAL; SORT: FIRM; PARA METERS: POSSIBLE BALANCE : ENTER COMMAND: DON'T FORGET QUOTES COLLATERAL ENTER: OPERAND MODES, SORT, PARAMETER MODES 9 25 -2 STRONG 19 20 21 22 -2 OPERAND,DISPLAY: ROWOF CHAR, REF STRUCT ( A ROWOF CHAR, B M 2 5 ) ; SORT: STRONG; PARAMETERS: ROWOF REAL, REF ROWOF REAL, U NION ( INT, REAL, ROWOF REAL), STRUCT ( A ROWOF CHAR, B REF M22) POSSIBLE COLLATERAL : STRUCT ( A ROWOF CHAR, B REF M22) ENTER COMMAND: DON'T FORGET QUOTES OPERATORS ENTER: LEFT OPERAND, RIGHT OPERAND, OPERATORS 18 3 21 21 22 22 8 3 -2 -2 LEFT.OPERAND: REF PROC REAL; RIGHT.OPERAND: REAL; APPENDIX A 101 OPERATORS: ( ONION ( INT, REAL, ROWOF REAL)+ UNION { INT, R EAL, ROWOF R E A L ) ) , ( STRUCT ( A ROWOF CHAR, B REF M22)+ STRU CT ( A ROWOF CHAR, B REF M22)), ( STRUCT ( RE REAL, IM REAL) + REAL) POSSIBLE OPERATORS: ( UNION ( INT, REAL, ROWOF REAL)+ UNION ( INT, REAL, ROWOF REAL)) ENTER COMMAND: DON'T FORGET QUOTES OPERATORS ENTER: LEFT OPERAND, RIGHT OPERAND, OPERATORS -2 3 -2 3 -2 17 -2 16 -2 -2 LEFT.OPERAND: NULL; RIGHT.OPERAND: REAL; OPERATORS: ( NULL+ REAL) , { NULL+ PROC REAL), { NULL+ REF R EAL) POSSIBLE OPERATORS: ( NULL+ REAL) ENTER COMMAND: DON'T FORGET QUOTES STOP 0001.64 SECONDS IN EXECUTION APPENDIX B 102 APPENDIX B REVISED SYNTAX RULES T h i s t h e s i s i s based on t h e s y n t a x r u l e s which a r e b r o u g h t f o r w a r d t o t h e m e e t i n g a t V i e n n a i n September, 1972, ( i t i s n o t y e t a d o p t e d ) , The r u l e s which a r e m o d i f i e d and c o n c e r n w i t h t h i s t h e s i s a r e a s f o l l o w s : The numbers a r e t h e same as use d i n t h e R e p o r t . 1.2.1. M e t a p r o d u c t i o n R u l e s o f Modes o) STOWED: s t r u c t u r e d w i t h FIELDS; ROWS o f MODE, vb) ROWS: row; ROWS row. 1.2.2. M e t a p r o d u c t i o n R u l e s A s s o c i a t e d w i t h Modes bb) ROW: row; row o f . d) d e l e t e d . ea) NONREF: UNITED; PLAIN; f o r m a t ; PROCEDURE; s t r u c t u r e d w i t h FIELDS; ROWS o f MODE, h) NONPROC: PLAIN; f o r m a t ; p r o c e d u r e w i t h PARAMETERS MOID; r e f e r e n c e t o NONPROC; UNITED; s t r u c t u r e d w i t h F I E L D S ; row o f MODE, i b ) PARAMS: p a r a m e t e r and PARAMETERS; p a r a m e t e r , rb) FOLDS: f i e l d TAG and FIE L D S ; f i e l d TAG. 1.2.3. M e t a p r o d u c t i o n R u l e s A s s o c i a t e d w i t h P h r a s e s and C o e r c i o n a) d e l e t e d . b) d e l e t e d . C) SOME: SORT MOID. cb) SIGNLE: u n i t a r y ; ENCLOSED. d) ENCLOSED: c l o s e d ; c o l l a t e r a l ; CHOICE. e) d e l e t e d . ea) CHOICE: c o n d i t i o n ; c a s e ; c o n f o r m i t y . eb) UNETI: UNITED; EMPTY. ec) CONFETY: UNITED c o n f o r m i t y ; EMPTY. f) d e l e t e d . g) SORT: s t r o n g ; FEAT. h) FEAT: f i r m ; meek; weak; s o f t . i ) STRONG: FIRM; widened; rowed; v o i d e d . 1) FIRM: MEEK; u n i t e d . l b ) MEEK: unchanged f r o m ; d e p r o c e d u r e d ; d e r e f e r e n c e d , o) FROBYT; f r o m ; b y ; t o . 1.2.4. M e t a p r o d u c t i o n R u l e s A s s o c i a t e d w i t h C o e r c e n d s b) FORM: MORF; COMORF. bb) FORMSPEC: FORM; s p e c i f i c a t i o n . c) d e l e t e d . ca) MORF: r o u t i n e t e x t ; PRIETY ADIC f o r m u l a ; s e l e c t i o n ; mode i d e n t i f i e r ; s l i c e ; c a l l . cb) COMORF: a s s i g n a t i o n ; c a s t ; i d e n t i t y r e l a t i o n ; APPENDIX B 103 g e n e r a t o r ; d e n o t a t i o n , d) ADIC: d y a d i c ; monadic, eb) PRIETY: PRIORITY; EMPTY. 6.1. S e r i a l C l a u s e s 6.1.1. S y n t a x a) SOME s e r i a l c l a u s e : d e c l a r a t i o n p r o l o g u e s e r i e s o p t i o n , SOME p a r a d e . b) d e c l a r a t i o n p r o l o g u e : s t r o n g v o i d u n i t s e r i e s o p t i o n , SINGLE d e c l a r a t i o n . c) d e l e t e d . d) d e l e t e d . e) SOME u n i t : SOME u n i t a r y c l a u s e . f ) d e l e t e d . g) SORT MOID p a r a d e : SORT MOID t r a i n ; SORT MOID t r a i n , c o m p l e t i o n t o k e n , l a b e l , s t r o n g MOID p a r a d e ; s t r o n g MOID t r a i n , c o m p l e t i o n t o k e n , l a b e l , SORT MOID p a r a d e . h) SOME t r a i n : s t r o n g v o i d l a b e l l e d u n i t s e r i e s o p t i o n , SOME l a b e l l e d u n i t . i ) d e l e t e d . j) SOME l a b e l l e d u n i t : l a b e l s e g u e n c e o p t i o n , SOME u n i t . 6.2. C o l l a t e r a l P h r a s e s 6.2.1. S y n t a x c) STIRM ROW MODE c o l l a t e r a l c l a u s e : STIRM MODE b a l a n c e PACK. d) d e l e t e d . e) SORT MOID CONFETY b a l a n c e : SORT MOID CONFETY u n i t , comma t o k e n , s t r o n g MOID CONFETY u n i t l i s t ; s t r o n g MOID CONFETY u n i t , comma t o k e n , SORT MOID CONFETY u n i t ; s t r o n g MOID CONFETY u n i t , comma t o k e n , SORT MOID CONFETY b a l a n c e . f) s t r o n g s t r u c t u r e d w i t h FIELDS and FIELD c o l l a t e r a l c l a u s e : FIELDS and FIELD p o r t r a i t PACK. g) FIELDS and FIELD p o r t r a i t : FIELDS p o r t r a i t comma t o k e n , FIELD p o r t r a i t . h) MODE f i e l d TAG p o r t r a i t : s t r o n g MODE u n i t . 6.3. C l o s e d C l a u s e s 6.3.1. S y n t a x a) SOME c l o s e d c l a u s e : SOME s e r i a l c l a u s e PACK. 6.4. C h o i c e C l a u s e s 6.4.1. S y n t a x a a ) * c h o i c e c l a u s e : SOME CHOICE c l a u s e . APPENDIX B 104 ab) SOME CHOICE c l a u s e : MATCH CHOICE s t a r t t o k e n , SOME MATCH CHOICE c h o o s e r c l a u s e , MATCH CHOICE f i n i s h t o k e n . ac) SOME MATCH CHOICE c h o o s e r c l a u s e : UNITY CHOICE, SOME MATCH UNETY CHOICE a l t e r n a t e c l a u s e . ba) c o n d i t i o n : meek b o o l e a n s e r i a l c l a u s e . bb) c a s e : meek i n t e g r a l s e r i a l c l a u s e . be) UNITED c o n f o r m i t y : meek UNITED s e r i a l c l a u s e . c) SORT MOID MATCH UNETY CHOICE a l t e r n a t e c l a u s e : SORT MOID MATCH UNETY CHOICE i n c l a u s e , s t r o n g MOID MATCH CHOICE o u t c l a u s e o p t i o n ; s t r o n g MOID MATCH UNETY CHOICE i n c l a u s e , SORT MOID MATCH CHOICE o u t c l a u s e . ea) SOME MATCH c o n d i t i o n i n c l a u s e : MATCH c o n d i t i o n i n t o k e n , SOME s e r i a l c l a u s e . eb) SOME MATCH c a s e i n c l a u s e : MATCH c a s e i n t o k e n , SOME b a l a n c e . ec) SOME MATCH UNITED c o n f o r m i t y i n c l a u s e : MATCH c o n f o r m i t y i n t o k e n , SOME UNITED c o n f o r m i t y u n i t ; MATCH c o n f o r m i t y i n t o k e n , SOME UNITED c o n f o r m i t y b a l a n c e . ed) SOME UNITED c o n f o r m i t y u n i t : u n i t e d t o UNITED s p e c i f i c a t i o n , SOME u n i t . e f ) meek MODE s p e c i f i c a t i o n : open t o k e n , f o r m a l MODE d e c l a r e r , MODE mode i d e n t i f i e r o p t i o n , c l o s e t o k e n , a l t e r n a t e t o k e n . eg) SOME MATCH CHOICE o u t c l a u s e : MATCH CHOICE o u t t o k e n , SOME s e r i a l c l a u s e ; MATCH CHOICE a g a i n t o k e n , SOME MATCH CHOICE c h o o s e r c l a u s e . 7.1. D e c l a r e r s 7. 1.1. S y n t a x e) VICTAL s t r u c t u r e d w i t h FIELDS d e c l a r a t o r : s t r u c t u r e t o k e n , VICTAL FIELDS p o r t r a y e r pack. g) * f i e l d p o r t r a y e r : VICTAL FIELD p o r t r a y e r . h) d e l e t e d . ha) VICTAL r e f e r e n c e t o MODE FOLDS p o r t r a y e r : v i r t u a l r e f e r e n c e t o MODE d e c l a r e r , VICTAL r e f e r e n c e t o MODE FOLDS HOMETY c o n t i n u a t i o n . hb) VICTAL NONREF FOLDS p o r t r a y e r : VICTAL NONREF d e c l a r e r , VICTAL NONREF FOLDS HOMETY c o n t i n u a t i o n . he) VICTAL MODE f i e l d TAG and MODE FOLDS homogeneous c o n t i n u a t i o n : MODE f i e l d TAG s e l e c t o r , comma t o k e n , VICTAL MODE FOLDS HOMETY c o n t i n u a t i o n . hd) VICTAL MODE f i e l d TAG HOMETY c o n t i n u a t i o n : mode f i e l d TAG SELECTOR. he) VICTAL MODE1 f i e l d TAG and MODE2 FOLDS c o n t i n u a t i o n : MODE1 f i e l d TAG s e l e c t o r , comma t o k e n , VICTAL M0DE2 FOLDS p o r t r a y e r . m) f o r m a l r e f e r e n c e t o r e f e r e n c e t o MODE d e c l a r a t o r : r e f e r e n c e t o t o k e n , v i r t u a l r e f e r e n c e t o MODE d e c l a r e r . APPENDIX B 105 n) f o r m a l r e f e r e n c e t o NONREF d e c l a r e r : r e f e r e n c e t o t o k e n , f o r m a l NONREF d e c l a r e r . 0) VICTAL BOWS o f r e f e r e n c e t o MODE d e c l a r a t o r : VICTAL f l e i t h e r o p t i o n , VICTAL ROWS rower BRACKET, v i r t u a l r e f e r e n c e t o MODE d e c l a r e r . p) VICTAL ROWS o f NONREF d e c l a r a t o r : VICTAL f l e i t h e r o p t i o n , VICTAL ROWS rower BRACKET, VICTAL NONREF d e c l a r e r . pb) f o r m a l f l e i t h e r : f l e x i b l e t o k e n : e i t h e r t o k e n , pc) a c t u a l f l e i t h e r : f l e x i b l e t o k e n . g) VICTAL row ROWS r o w e r : VICTAL row rower, comma t o k e n , VICTAL ROWS rower, r a ) a c t u a l row r o w e r : l o w e r bound, up t o t o k e n , u p p e r bound. rb) VIRMAL row r o w e r : up t o t o k e n o p t i o n , s) d e l e t e d . t) LOWPER bound: meek i n t e g r a l u n i t , u) d e l e t e d , v) d e l e t e d , x) d e l e t e d . z) v i r t u a l v o i d d e c l a r e r : v o i d t o k e n , aa) d e l e t e d . dd) LMOODSETY LMOOD open BOX: LMOODSETY c l o s e d LMOOD end BOX. ee) LMOODSETY1 c l o s e d LMOODSETY2 LMOOD end BOX: LMOODSETY1 c l o s e d LMOODSETY2 LMOOD LMOOD end BOX; LMOODSETY1 open LMOODSETY2 LMOOD BOX. f f ) LMOODSETY1 c l o s e d LMOODSETY2 LMOOD1 end LMOOD2 BOX: LMOODSETY1 c l o s e d LHOODSETY2 LMOOD2 LMOOD1 end BOX. 7.4. I d e n t i f i e r D e c l a r a t i o n s 7.4.1. S y n t a x a) i d e n t i f i e r d e c l a r a t i o n : i d e n t i t y d e c l a r a t i o n ; v a r i a b l e d e c l a r a t i o n . b) i d e n t i t y d e c l a r a t i o n : MODE i d e n t i t y d e c l a r a t i o n ; p r o c e d u r e i d e n t i t y d e c l a r a t i o n . c) MODE i d e n t i t y d e c l a r a t i o n : f o r m a l MODE d e c l a r e r , MODE i d e n t i t y d e f i n i t i o n l i s t . d) MODE i d e n t i t y d e f i n i t i o n : MODE mode i d e n t i f i e r , e g u a l s s y m b o l , s t r o n g MODE u n i t . e) p r o c e d u r e i d e n t i t y d e c l a r a t i o n : p r o c e d u r e t o k e n , PROCEDURE mode i d e n t i f i e r , e g u a l s s y mbol, PROCEDURE r o u t i n e t e x t . f ) v a r i a b l e d e c l a r a t i o n : MODE v a r i a b l e d e c l a r a t i o n ; p r o c e d u r e v a r i a b l e d e c l a r a t i o n . g) MODE v a r i a b l e d e c l a r a t i o n : heap t o k e n o p t i o n , a c t u a l MODE d e c l a r e r , MODE v a r i a b l e d e f i n i t i o n l i s t . h) MODE v a r i a b l e d e f i n i t i o n : r e f e r e n c e t o MODE mode i d e n t i f i e r , MODE i n i t i a l i z a t i o n o p t i o n . 1) MODE i n i t i a l i z a t i o n : becomes t o k e n , MODE s o u r c e . j) p r o c e d u r e v a r i a b l e d e c l a r a t i o n ; heap t o k e n o p t i o n , p r o c e d u r e t o k e n , r e f e r e n c e t o PROCEDURE mode APPENDIX B 106 i d e n t i f i e r , becomes t o k e n , PROCEDURE r o u t i n e t e x t . 7.5. O p e r a t i o n D e c l a r a t i o n s 7.5.1. S y n t a x a) o p e r a t i o n d e c l a r a t i o n : o p e r a t i o n t o k e n , o p e r a t o r d e f i n i t i o n . b) o p e r a t o r d e f i n i t i o n : PRAM ADIC o p e r a t o r , e q u a l s s y m b o l , PRAM r o u t i n e t e x t ; v i r t u a l PRAM p l a n , PRAM PRIETY ADIC o p e r a t o r , e q u a l s s y m b o l , s t r o n g PRAM u n i t . 8.1. U n i t a r y C l a u s e s 8. 1. 1. S y n t a x a) SOME u n i t a r y c l a u s e : SOME l o o p ; SOME r o u t i n e t e x t ; SOME a s s i g n a t i o n ; SOME i d e n t i t y r e l a t i o n ; SOME t e r t i a r y . b) SOME t e r t i a r y : SOME c a s t ; SOME PRIETY ADIC f o r m u l a ; SOME s e c o n d a r y . c) SOME s e c o n d a r y : SOME g e n e r a t o r ; SOME s e l e c t i o n ; SOME p r i m a r y . d) SOME p r i m a r y : SOME d e n o t a t i o n ; SOME mode i d e n t i f i e r ; SOME s l i c e ; SOME c a l l ; SOME h i p ; SOME ENCLOSED c l a u s e . 8.2. C o e r c e n d s 8.2.0. 1. S y n t a x a) * c o e r c e n d : COERCEND. b) * STRONG c o e r c e n d : STRONG t o COERCEND. c) d e l e t e d . d) s t r o n g COERCEND: STRONG t o COERCEND. e) f i r m COERCEND: FIRM t o COERCEND. f ) d e l e t e d . f a ) meek COERCEND: MEEK t o COERCEND. f b ) weak r e f e r e n c e t o MODE FORM: meek r e f e r e n c e t o MODE FORM. f c ) weak NONREF FORM: unchanged from NONREF FORM; d e p r o c e d u r e d t o NONREF FORM. G) s o f t r e f e r e n c e t o MODE FORM: unchanged t o r e f e r e n c e t o MODE FORM; o n l y d e p r o c e d u r e d t o r e f e r e n c e t o MODE FORM. h) unchange t o MODE FORK: MODE FORM. 8.2.1. D e r e f e r e n c e d C o e r c e n d s 8.2,1.1. S y n t a x a) d e r e f e r e n c e d t o MODE FORM: meek r e f e r e n c e t o MODE FORM. APPENDIX B 107 8.2-2. D e p r o c e d u r e d C o e r c e n d s 8.2.2.1. S y n t a x aa) d e p r o c e d u r e d t o MODE FORM: meek p r o c e d u r e MODE FORM. ab) d e p r o c e d u r e d t o v o i d MORF: meek p r o c e d u r e v o i d MORF. c) o n l y d e p r o c e d u r e d t o MODE FORM: unchanged t o p r o c e d u r e MODE FORM; o n l y d e p r o c e d u r e d t o p r o c e d u r e MODE FORM. 8.2.3. a l l d e l e t e d . 8.2.4. U n i t e d C o e r c e n d s 8.2.4.1. S y n t a x a) u n i t e d t o u n i o n o f LMOODS MOOD mode FORMSPEC: one o u t o f LMOODS MOOD mode FORMSPEC; some o f LMOODS MOOD and b u t n o t FORMSPEC. b) one o u t o f LMOODSETY MOOD RMOODSETY mode FORMSPEC: meek MOOD FORMSPEC. c) some o f LMOODSETY1 MOOD and RMOODSETY but n o t LMOODSETY2 FORMSPEC: some o f LMOODSETY1 and MOOD RMOODSETY b u t n o t LMOODS ETY2 FORMSPEC; some o f LMOODSETY1 RMOODSETY b ut net MOOD and LMCODSETY2 FORMSPEC. d) some o f EMPTY and LMOOD MOOD RMOODSETY b ut n o t LMO0D2 LMOODSETY2 FORMSPEC: meek u n i o n o f LMOOD MOOD RMOODSETY mode FORMSPEC. 8.2.5. Widened C o e r c e n d s 8.2.5.1 s y n t a x a) widened t o LONGSETY r e a l FORM: meek LONGSETY i n t e g r a l FORM. b) widened t o s t r u c t u r e w i t h LONGSETY r e a l f i e l d l e t t e r r l e t t e r e and LONGSETY r e a l f i e l d l e t t e r i l e t t e r m FORM: meek LONGSETY r e a l FORM; widened t o LONGSETY r e a l FORM. c) widened to row o f b o o l e a n FORM: meek BITS FORM. d) widened t o row o f c h a r a c t e r FORM: meek BYTES FORM. 8.2.6; Rowed C o e r c e n d s 8.2.6.1. S y n t a x a) rowed t o REFETY row o f MODE FORM: s t r o n g REFETY MODE FORM. b) d e l e t e d . 8.2.7. H i p s 8.2.7;1. S y n t a x APPENDIX B 108 a) s t r o n g MOID h i p : MOID s k i p ; MOID jump; MOID n i h i l ; MOID vacuum, e) ROWS o f MODE vacuum: vacuum t o k e n . 8.2.8. V o i d e d C o e r c e n d s 8.2.8.1. S y n t a x a) v o i d e d t o v o i d COMORF: unchanged from MODE COMORF. b) v o i d e d t o v o i d MORF: d e p r o c e d u r e d t o NONPROC MORF; unchanged f r o m NONPROC MORF. 8.3A. Loops 8.3A.1. S y n t a x a) s t r o n g v o i d l o o p : f o r p a r t o p t i o n , f r o m p a r t o p t i o n , by p a r t o p t i o n , t o p a r t o p t i o n , w h i l e p a r t o p t i o n , do p a r t . b) f o r p a r t : f o r t o k e n , i n t e g r a l mode i d e n t i f i e r . c) PROBYT p a r t : FROBYT t o k e n , meek i n t e g r a l u n i t . d) w h i l e p a r t : w h i l e t o k e n , meek b o o l e a n s e r i a l c l a u s e , db) do p a r t : do t o k e n , s t r o n g v o i d u n i t . 8.3.0.1. d e l e t e d . 8.3.2. C o n f o r m i t y R e l a t i o n s 8.3.2.1. S y n t a x a) b o o l e a n c o n f o r m i t y r e l a t i o n : u n i t e d t o UNITED sa m p l e , c o n f o r m s t o and becomes t o k e n , meek UNITED t e r t i a r y ; u n i t e d t o UNITED d e c l a r a n d , c o n f o r m s t o t o k e n , meek UNITED t e r t i a r y . b) meek MODE sam p l e : s o f t r e f e r e n c e t o MODE t e r t i a r y . c) meek MODE d e c l a r a n d : v i r t u a l MODE d e c l a r e r . 8,4. F o r m u l a s 8.4.1. S y n t a x a ) * f o r m u l a : SOME PRIETY ADIC f o r m u l a . B) MOID PRIORITY d y a d i c f o r m u l a : MODE1 PRIORITY o p e r a n d , p r o c e d u r e w i t h MODE1 p a r a m e t e r and MODE2 p a r a m e t e r MOID PRIORITY d y a d i c o p e r a t o r , M0DE2 PRIORITY p l u s one o p e r a n d . c) * o p e r a n d : MODE PRIETY o p e r a n d . d) MODE PRIORITY o p e r a n d : f i r m MODE PRIORITY d y a d i c f o r m u l a ; MODE PRIORITY p l u s one o p e r a n d . e) MODE p r i o r i t y NINE p l u s one o p e r a n d : f i r m MODE monadic f o r m u l a ; f i r m MODE s e c o n d a r y , g) MOID monadic f o r m u l a : p r o c e d u r e w i t h MODE p a r a m e t e r MOID monadic o p e r a t o r , MODE p r i o r i t y NINE p l u s one APPENDIX D 109 o p e r a n d . h ) * d y a d i c f o r m u l a : MOID.PRIORITY d y a d i c f o r m u l a . 8.6.1. S l i c e s 8.6.1.1. S y n t a x aa) REFETY ROBS o f MODE s l i c e : weak REFETY ROWSETY BOWS o f MODE p r i m a r y , ROWSETY ROWS l e a v i n g ROWS i n d e x e r BRACKET; weak BEFETY ROWS2 o f ROWS o f MODE p r i m a r y , B0WS2 l e a v i n g EMPTY i n d e x e r BRACKET. ab) REFETY UONROW s l i c e : weak REFETY ROWS2 o f NONROW p r i m a r y , ROWS2 l e a v i n g EMPTY i n d e x e r BRACKET. b) row ROWS l e a v i n g row ROWSETY i n d e x e r : t r i m m e r , comma t o k e n , ROWS l e a v i n g ROWSETY i n d e x e r ; s u b s c r i p t , comma t o k e n , ROWS l e a v i n g row ROWSETY i n d e x e r . c) row ROWS l e a v i n g EMPTY i n d e x e r : s u b s c r i p t , comma t o k e n , ROWS l e a v i n g EMPTY i n d e x e r . d) row l e a v i n g row i n d e x e r : trimmer o p t i o n . e) row l e a v i n g EMPTY i n d e x e r : s u b s c r i p t . f ) t r i m m e r : l o w e r bound o p t i o n , up t o t o k e n , upper bound o p t i o n , new l o w e r bound p a r t o p t i o n ; new lower bound p a r t . g) new l o w e r bound p a r t : a t t o k e n , new l o w e r bound. h) new l o w e r bound: meek i n t e r a l u n i t . i ) s u b s c r i p t : meek i n t e g r a l u n i t , j ) * t r i m s c r i p t : t r i m m e r ; s u b s c r i p t . k ) * i n d e x e r : ROWS l e a v i n g ROWSETY i n d e x e r . 1 ) * b o u n d s c r i p t : LOWPER bound; new l o w e r bound; s u b s c r i p t . 8.6.2. C a l l s 8.6.2.1. S y n t a x a) MOID c a l l : meek p r o c e d u r e w i t h PABAMETERS MOID p r i m a r y , a c t u a l PARAMETERS pack. b) a c t u a l MODE p a r a m e t e r : s t r o n g MODE u n i t . 

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

Comment

Related Items