UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Mode checking in Algol 68 Thomson, John Donald 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 T46_4.pdf [ 4.4MB ]
Metadata
JSON: 831-1.0052014.json
JSON-LD: 831-1.0052014-ld.json
RDF/XML (Pretty): 831-1.0052014-rdf.xml
RDF/JSON: 831-1.0052014-rdf.json
Turtle: 831-1.0052014-turtle.txt
N-Triples: 831-1.0052014-rdf-ntriples.txt
Original Record: 831-1.0052014-source.json
Full Text
831-1.0052014-fulltext.txt
Citation
831-1.0052014.ris

Full Text

MODE CHECKING IN ALGOL 68 by i John Donald Thomson B.Sc., U n i v e r s i t y of B r i t i s h Columbia, 1971 A t h e s i s submitted i n p a r t i a l f u l f i l m e n t of the requirements f o r the degree of Master of Science i n the Department of Computer Science We accept t h i s t h e s i s as conforming to the r e g u i r e d standard The U n i v e r s i t y of B r i t i s h Columbia September, 1973 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available f o r reference and study. I further agree that permission f o r extensive copying of t h i s thesis for scholarly purposes may be granted by the Head of my Department or by h i s representatives. It i s understood that copying or publication of t h i s thesis f o r 1 f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of Go^po^or QCv&nCe The University of B r i t i s h Columbia Vancouver 8, Canada i A b s t r a c t The programming language ALGOL 68 o f f e r s great f l e x i b i l i t y i n the use of modes and o p e r a t o r s . The convenience f o r the programmer r e s u l t s i n problems f o r the implementor i n c o e r c i o n , b a l a n c i n g , and i d e n t i f i c a t i o n of o p e r a t o r s . T h i s t h e s i s presents a s o l u t i o n to these problems t h a t i s being s u c c e s s f u l l y used i n an ALGOL 68 comp i l e r . i i T a ble of Contents 1. I n t r o d u c t i o n ..1 1.1. S p e c i a l Features of ALGOL 68 .....1 1.2. Some Implementation Terms ...2 1.3. D e s c r i p t i o n Methods ....4 2. Program Tree R e p r e s e n t a t i o n .....6 2.1. Terminology 6 2.2. Nodes i n the Program Tree .....7 2.2.1. D e c l a r e r Nodes(Modes) 8 2.2.2. Coercend Nodes 11 2.2.3. S t r u c t u r a l Nodes 13 2.2.4. Format Nodes ...13 2.2.5. D e c l a r a t i o n Nodes ..13 3. B u i l d i n g the Program Tree ..........................15 3.1. A c t i o n on the Semantics Stack ..................15 3.2. The B u i l d i n g Routines ...........17 3.3. Tree Pruning During the Parse ..........21 4. Touring the Program Tree ..........23 4.1. Procedure S t r u c t u r e 23 * 4.2. Tour ......25 4.3. D i s p l a y s ( C o l l a t e r a l Clauses) ......27 4.4. S l i c e s ................30 4.5. I d e n t i f i c a t i o n of I d e n t i f i e r s ........32 4.6. I d e n t i f i c a t i o n of S e l e c t o r s ,,.....34 4.7. I d e n t i f i c a t i o n of C a l l s and S l i c e s ....35 4.8. V i c t a l Checking ,. ...36 , i i i 4.9. E r r o r Recovery ...........36 5. Ba l a n c i n g and Operator I d e n t i f i c a t i o n 40 5.1. D e f i n i t i o n of Ba l a n c i n g 40 5.2. The Need f o r E f f i c i e n t B a l ancing 41 5.3. The Development of B a l a n c i n g .........42 5.4. General B a l a n c i n g Theorem 44 5.4.1. D e f i n i t i o n of h .44 5.4.2. P r o p e r t i e s of h 45 5.4.3. C o e r c i o n P r o p e r t i e s ....46 5.4.4. Mode Ordering Theorem ....47 5.4.5. Proof of General B a l a n c i n g Theorem .........50 5.5. Meek, Weak, and S o f t Balancing Algorithms ......51 5.6. Operator I d e n t i f i c a t i o n and Firm Balancing......53 6. C o e r c i o n .........56 6.1. I n t r o d u c t i o n 56 6.2. The Z o s e l Strong-Firm Coercion Algorithm .......59 6.3. Meek, Weak, and S o f t Coercion ..61 6.4. Examples of Co e r c i o n Paths ...64 6.5. Lengthening and Shortening 66 Conclusion .................70 B i b l i o g r a p h y ....71 Appendix 1. Sample Buns .72 Appendix 2. Program Tree Nodes ..86 i v L i s t of Tables Table 5.1- h Function .....44 Table 5.2. Balancing 52 Table 6 . 1 . Coercion 58 Table 6.2. Coercion Contexts .....59 V L i s t 2 l F i g u r e s F i g u r e 2.1 ..........7 Figure 2.2. ..8 Fi g u r e 2.3 10 Fi g u r e 2.4. .........11 Fi g u r e 2.5 12 F i g u r e 2.6 13 Fig u r e 2.7 14 Fig u r e 3.1 ..........15 F i g u r e 3.2 18 Fig u r e 3.3. ...........19 F i g u r e 4.1. 24 Fi g u r e 6.1 57 Fig u r e 6.2 64 Fig u r e 6.3. 65 Fi g u r e 6.4 ..66 1 v i My supervisor, Professor John Peck, has always been available for questions and has provided a great amount of encouragement to me. He, and the other members of the ALGOL 68 project at U.B.C. (especially Vince Manis, Dave Ramer, and Peter van den Bosch) have given me many useful suggestions and participated in many long, revealing discussions. I am grateful for the f i n a n c i a l support of NRC for thi s project. i 1 Chapter 1 . i 1 i l | I n t r o d u c t i o n | I I i i 1 . 1 . S p e c i a l F e a t u r e s of ALGOL 68 The most n o t i c e a b l e f e a t u r e s of ALGOL 68 are i t s g e n e r a l i z a t i o n of data types, modes, and the f l e x i b i l i t y allowed the programmer to c r e a t e and manipulate these modes. A programmer may c o n s t r u c t any number of modes i n a program, and may do so i n a v a r i e t y of ways. E i t h e r of the two c o n s t r u c t i o n s • s t r u c t ( i n t i , j ) x» and "mode £air = s t r u c t (in t i , int. j ) ; £air xm may be chosen by the programmer but are r e q u i r e d to produce i d e n t i c a l o b j e c t s . These o b j e c t s may c o n v e n i e n t l y be manipulated i n formulas, s i n c e ALGOL 68 allo w s a programmer to d e f i n e h i s own ope r a t o r s on modes he has c r e a t e d . For example, the d e c l a r a t i o n op_ - = ( jaair a) jaair: (-i of a , - j of b) ; Would d e f i n e an ope r a t o r a c t i n g on a data o b j e c t of mode •£air•. As a d i r e c t r e s u l t of the great f l e x i b i l i t y of ALGOL 68, the process of mode checking ( g e n e r a l i z e d type checking) i s 2 complex. Three major mode checking a l g o r i t h m s a r e : c o e r c i o n (changing one mode to a n o t h e r ) , b a l a n c i n g ( f i n d i n g a " r e p r e s e n t a t i v e " mode from a group of modes), and operator i d e n t i f i c a t i o n . T h i s t h e s i s d e s c r i b e s these a l g o r i t h m s as they are used i n a compiler, and shows how they can be e f f i c i e n t l y executed, remain l o g i c a l l y independent, and produce m e a n i n g f u l l e r r o r messages. 1.2. Some Implementation Terms The Report on the a l g o r i t h m i c Language ALGOL 68 [ 2 ] s t a t e s t h a t "The syntax of ALGOL 68 i s such t h a t the p a r s i n g of a program can be performed independently of the modes of i t s c o n s t i t u e n t s " . T h i s statement suggests a method of determining whether or not a sequence of symbols i s an ALGOL 68 program. A "mode independent parse" of the symbols i s f i r s t made to see i f they can be generated by a "context f r e e grammar". Then, the v a r i o u s c o n s t r u c t i o n s are examined i n a "mode dependent parse" to see t h a t the modes of the c o n s t r u c t i o n s meet with the s y n t a c t i c requirements of the Report. T h i s i s the method used i n the Vancouver implementation. The mode independent parse of a program produces a s y n t a c t i c parse t r e e of the program, c a l l e d the program t r e e , that w i l l be the r e p r e s e n t a t i o n of the program f o r a l l l a t e r passes of the c o m p i l e r . In a d d i t i o n , the mode independent parse of the program b u i l d s a "mode t a b l e " t h a t c o n t a i n s r e p r e s e n t a t i v e s of a l l modes 3 i n the program. T h i s mode t a b l e i s the primary data s t r u c t u r e of the c o e r c i o n , b a l a n c i n g , and operator i d e n t i f i c a t i o n a l g o r i t h m s . The d e s c r i p t i o n of the c o e r c i o n model of Peck £5] s t a t e s t h a t "the mode t a b l e may be minimized so that each mode occurs o n l y once. The det e r m i n a t i o n of c o e r c i o n can then be accomplished." What t h i s means i s that i f the two d e c l a r e r s " S t r u c t (int. i , j) • and " S t r u c t ( i n t i , i n t j ) • appear i n the program and are i n i t i a l l y put i n t o the mode t a b l e , one "copy" may be d i s c a r d e d from the mode t a b l e when they are dis c o v e r e d to be e q u i v a l e n t . The c o e r c i o n a l g o r i t h m model makes use of the f a c t t h a t there are not two c o p i e s of an e q u i v a l e n t mode i n the mode t a b l e . While t h i s method of d e a l i n g with e q u i v a l e n t modes i s adequate f o r a model of c o e r c i o n , i t i s not q u i t e adequate i n a compiler because the mode r e p r e s e n t a t i v e s f o r row and rowof modes must c o n t a i n bound i n f o r m a t i o n . The two d e c l a r e r s • s t r u c t ([ 1:5 ] i n t i , bool j)» and - s t r u c t ([1:10 ] i n t i , bool j) •, f o r example, are of the same mode. One copy or mode r e p r e s e n t a t i v e cannot be thrown away s i n c e the bound i n f o r m a t i o n may be d i f f e r e n t , and must be preserved u n t i l code gener a t i o n time. To conform to standard p r a c t i c e , t h i s document s t i l l speaks of a "mode t a b l e " , although i t may more a c c u r a t e l y be thought of as a " d e c l a r e r t a b l e " , c o n s i s t i n g of r e p r e s e n t a t i v e s of a l l d e c l a r e r s i n the program. One p i e c e of i n f o r m a t i o n a s s o c i a t e d with each d e c l a r e r r e p r e s e n t a t i o n i s the equi v a l e n c e c l a s s or 4 mode of which that d e c l a r e r i s a member. Thus i n the example above, the two d e c l a r e r s would be kept s e p a r a t e l y and have d i f f e r e n t bound i n f o r m a t i o n , but would belong to the same c l a s s (be of the same mode). 1.3. D e s c r i p t i o n Methods Numerous r e f e r e n c e s to the Report and the Revised Report appear throughout t h i s document. These are, r e s p e c t i v e l y , to the Report on the A l g o r i t h m i c Language ALGOL 68 [ 2 ] and to the D r a f t Revised Report on the A l g o r i t h m i c Language ALGOL 68. A s e c t i o n of the Revised Report, where a p p r o p r i a t e , i s i n d i c a t e d w i t h i n the braces "{" and "}", f o r example {6 . 1.d}. Since the l a t t e r document i s s t i l l changing somewhat, s e c t i o n s may be s l i g h t l y d i f f e r e n t i n the f i n a l v e r s i o n . PL360 i s the language t h a t i s used to implement ALGOL 68 i n Vancouver. The s i z e of programs i n t h i s language makes i t i m p r a c t i c a l to i n c l u d e a source l i s t i n g of the mode checking a l g o r i t h m s , even as an appendix. To i n c l u d e a l g o r i t h m s i n the "step 1, ... , step 9a" format would be s e l f d e f e a t i n g , s i n c e t h i s t h e s i s d e a l s with ALGOL 68, an " a l g o r i t h m i c language" " s e r v i n g many people i n many c o u n t r i e s " [2 ]. For these reasons, important a l g o r i t h m s have been i n c l u d e d as ALGOL 68 procedure d e c l a r a t i o n s , with long, "meaningful" i d e n t i f i e r s and s e l e c t o r s . I t i s hoped t h a t a l g o r i t h m s presented i n t h i s f a s h i o n are more readable. For b r e v i t y , common abre " r e f e r e n c e t o " and "L i n t " f o r many s i t u a t i o n s where the meanin v i a t i o n s such as " r e f " f o r "LONGSETY i n t e g r a l " are used i n g i s c l e a r . \ 6 Chapter 2. I I | Program Tree Re p r e s e n t a t i o n | I I i : ; j 2.1. Terminology As the mode independent parse of an ALGOL 68 program proceeds, a r e c o r d must be kept of the s y n t a c t i c c o n s t r u c t i o n s which occur. T h i s i n f o r m a t i o n i s needed f o r l a t e r mode checking and code g e n e r a t i o n passes of the compiler. The implementation at Vancouver uses the s y n t a c t i c t r e e of the parse as the b a s i c form of t h i s r e c o r d and c a l l s i t the program t r e e . The program t r e e should be thought of as the e s s e n t i a l substance o f the s y n t a c t i c parse t r e e , i . e . , those p a r t s which have no semantic content and are necessary only f o r p a r s i n g have been e l i m i n a t e d . In a d d i t i o n , space i s l e f t i n the program tr e e a t those p l a c e s where i n f o r m a t i o n must l a t e r be p l a c e d . Some simple t r e e pruning and compaction i s done as the program t r e e i s b u i l t . For ease of d i s c u s s i o n , the nodes of a program t r e e and the sons of th a t node are given names a s s o c i a t e d with the production r u l e i n v o l v e d i n th a t node. For example, an " a s s i g n a t i o n " node 7 with a " t e r t i a r y " son and a " u n i t " son i s suggested by the context f r e e p r o d u c t i o n r u l e : a s s i g n a t i o n : t e r t i a r y , becomes symbol, u n i t , (here the becomes symbol i s d i s c a r d e d because i t no longer possesses semantic v a l u e ) . 2 . 2 . Nodes i n the Program Tree The s t r u c t u r e of the program t r e e nodes i s given i n the f i g u r e s t h a t f o l l o w . The program t r e e nodes are d i v i d e d i n t o f i v e c l a s s i f i c a t i o n s , a c c o r d i n g to t h e i r uses: d e c l a r e r nodes, coercend nodes, s t r u c t u r e nodes, format nodes and d e c l a r a t i o n i n f o r m a t i o n nodes. Within each of these c l a s s i f i c a t i o n s , there are common f i e l d s (the head). For example the f i r s t f i v e f i e l d s i n the a s s i g n a t i o n node (a coercend) are common to a l l coercend nodes: r type J nf= 3 | L ^ range # | coor # | > — > " u n i t " .J F i g u r e 2.1 / 8 The l a s t two f i e l d s (the t a i l ) are unique to the a s s i g n a t i o n node. 2 . 2 . 1 . D e c l a r e r Nodes (Hodes) The d e c l a r e r nodes c o n t a i n a l l the i n f o r m a t i o n needed f o r the e l a b o r a t i o n of a d e c l a r e r . They are d i v i d e d i n t o e q u i v a l e n c e c l a s s e s (modes) t h a t are used i n the mode checking pass of the c o m p i l e r . The " r e f e r e n c e to mode" node below shows the s t r u c t u r e of the head f o r a l l d e c l a r e r nodes: [ type T~ nf=3 ] , L , I dn | mn | | cw | h | j L j | f l a g s | , .j | l i n k | | • H—> >submode i 1 type = type of node nf = number of s u b f i e l d s dn = d e c l a r e r number mn = mode number cw = coercend word h = the b a l a n c i n g f u n c t i o n F i g u r e 2 . 2 The f u n c t i o n h i s used i n b a l a n c i n g . The f l a g s and l i n k f i e l d s are used i n v a r i o u s a l g o r i t h m s to f l a g the d e c l a r e r s and to l i n k them together i n a l i s t . The c o e r c i o n word i s used during 9 c o e r c i o n t o hold an item of a c o e r c i o n sequence. When e q u i v a l e n c i n g i s done, the mode number i s f i l l e d with the eq u i v a l e n c e c l a s s to which the d e c l a r e r belongs. Thus cw, f l a g s and l i n k are e s s e n t i a l l y s c r a t c h p a d s . I t i s necessary to keep c o p i e s of two d e c l a r e r s of the same mode because their'bounds (or bounds of t h e i r s u b d e clarers) may be d i f f e r e n t . For example, the f o l l o w i n g s t r u c t u r e d d e c l a r e r s must be kept separate although they s p e c i f y the same mode: s t r u c t ([1:5 ] i n t x, r e a l y) s t r u c t ([ 1:10 ] i n t x, r e a l y) In an ALGOL 68 program i t i s p o s s i b l e to use a d e c l a r e r before i t i s d e f i n e d , f o r example: mode a = s t r u c t (b x, y) ; mode b = r e f a; Because of t h i s , temporary d e c l a r e r s are c r e a t e d during the parse of a program. They are e l i m i n a t e d a f t e r the parse i s completed. S l i c e s and s e l e c t i o n s cause another c o m p l i c a t i o n i n ALGOL 68. In t h i s example, the mode of the s e l e c t i o n and the s l i c e i s r e f e r e n c e to i n t e g r a l : [1:2 ] i n t a; s t r u c t ( i n t i , j) x; a[1 ] := i of x := 1; Notice t h a t s t a r t i n g with the modes of a and x, namely r e f e r e n c e to rowof i n t e g r a l and r e f e r e n c e to s t r u c t u r e d with i n t e g r a l l e t t e r i i n t e g r a l l e t t e r j , there i s no simple path i n the mode 10 t r e e to the mode r e f e r e n c e to i n t e g r a l . One must s t a r t with the mode i n t e g r a l , and search through a l l modes u n t i l r e f e r e n c e to i n t e g r a l i s found. To avoid t h i s seach being done each time v a s l i c e or s e l e c t i o n i s used i n the program, there i s an e x t r a f i e l d i n the row, rowof and f i e l d d e c l a r e r nodes where the r e f e r e n c e t o mode i n f o r m a t i o n i s kept. For the above example the d e c l a r e r nodes f o r rows would be b u i l t : j F i g u r e 2.3 11 2.2.2. Coercend Nodes At c e r t a i n p l a c e s i n the syntax of ALGOL 68, c o e r c i o n s are performed. T h i s i n v o l v e s t a k i n g a value of some mode and changing i t i n t o a corresponding value of another mode. For example, i n the a s s i g n a t i o n • l o c r e a l : = 1», *1« must be coerced from an i n t e g r a l value t o a r e a l value. T h i s c o e r c i o n , c a l l e d widening from i n t e g r a l to r e a l , must be placed somewhere i n the program t r e e d u r i n g mode checking so that i t may be found a t the a p p r o p r i a t e time during code g e n e r a t i o n . Coercend nodes are those nodes whose a s s o c i a t e d values may be coerced, f o r example: r r » | deno. | n f = 3 | | range # j coor # | j L 1 | • - J—> >coercion sequence | • -|—> >denotation mode | deno ace # | Figur e 2.4 A p o i n t e r to a c o e r c i o n seguence i s p a r t of the head of c o e r c i o n nodes, a f t e r type, range and c o o r d i n a t e i n f o r m a t i o n . Two coercend nodes t h a t deserve s p e c i a l a t t e n t i o n are the r o u t i n e node and the " c a l i c e " node ( i . e . , a mode which may be a c a l l or s l i c e ) . The mode of a r o u t i n e must be c o n s t r u c t e d and i n c l u d e d as p a r t of the r o u t i n e node f o r use by the mode checking r o u t i n e s . In the program: 12 begin ( l i n t i ) i n t : i+1) (1) end The mode procedure with i n t e g r a l parameter y i e l d i n g i n t e g r a l must be i n c l u d e d i n the r o u t i n e node, i n the pl a c e i n d i c a t e d by r o u t i n e mode below: >coercion sequence >formal p.p. or n i l > M u n i t " mode >"unit" >routine mode Fig u r e 2.5 It i s i m p o s s i b l e to t e l l at parse time, i n the Vancouver implementation, whether • a(i,j)« i s a c a l l or s l i c e . For t h i s reason a " c a l i c e " node i s c r e a t e d at parse time. During the mode checking pass these w i l l be r e s o l v e d . The c a l l , s l i c e and c a l i c e nodes are i d e n t i c a l l y s t r u c t u r e d , so that t h i s may be done by a simple change i n the type f i e l d . r T 1 | r o u t i n e | 5 | | range # | coor # | [ . H—> I 4 , 1 1 -I ^ • +—> 1 3 2.2.3. S t r u c t u r a l Nodes These program t r e e nodes have no s p e c i a l p r o p e r t i e s ; they merely preserve the s t r u c t u r e of the program f o r l a t e r passes. For example, a u n i t s e r i e s i s s t o r e d i n the f o l l o w i n g way: F i g u r e 2.6 2.2.4. Format Nodes Because of the complexity of ALGOL 68 formats, i t i s necessary to c o n s t r u c t format nodes to preserve the s t r u c t u r e of the parse. The major reason formats cannot be broken down i n t o l i n e a r s t r i n g s at /this time i s dynamic r e p l i c a t o r s - r e p l i c a t i o n f a c t o r s t h a t are e l a b o r a t e d a t run time. 2.2.5. D e c l a r a t i o n Nodes D e c l a r a t i o n nodes are b u i l t each time an i d e n t i f i e r , i n d i c a t i o n or o p e r a t o r , i s d e f i n e d ' i n the program. The head of 14 these d e c l a r a t i o n nodes c o n t a i n s type and range i n f o r m a t i o n as i n other nodes. As we l l there i s a c r o s s - r e f e r e n c i n g f i e l d and a f i e l d used to l i n k a l l d e f i n i t i o n s of the same l e x i c a l symbol together. T h i s l i n k i n g i s needed to i d e n t i f y an a p p l i e d occurrence. There are fou r of these d e c l a r a t i o n nodes f o r modes, i d e n t i f i e r s , o p e r a t o r s (parameters and body), and p r i o r i t i e s (of some o p e r a t o r ) . For example, the f o l l o w i n g node i s c r e a t e d f o r each mode d e c l a r a t i o n i n the program: j mode dec | 4 | j. J .| | range # | coor # | | • 1—> > i n d l i n k j • -|—> >xref l i n k | mode dec # | y. -J \ • +—> >mode d e c l a r e r F i g u r e 2.7 1 5 Chapter 3. I ] B u i l d i n g the Program Tree I i 3.1. A c t i o n on the Semantics Stack The v a r i o u s p a r t s of a program t r e e node are c o l l e c t e d on a semantics stack during the parse of an ALGOL 68 program. When a l l the p a r t s have been c o l l e c t e d and the r e d u c t i o n i n v o l v i n g an a s s o c i a t e d p r o d u c t i o n r u l e occurs, the node i s b u i l t , the p a r t s on the semantic stack are removed, and a p o i n t e r to the node i s pla c e d on the semantics stack. During a read o p e r a t i o n of the parser (see [ 1 0 ] ) , any t e r m i n a l symbol which i s read and has some semantic content (a semantic terminal) i s placed on the semantics s t a c k . I t i s then c o n s i d e r e d p a r t o f some node. For example, we w i l l t r a c e through the semantics stack during the p a r s i n g of the a s s i g n a t i o n : «x := 1«. 1. A c t i o n of pa r s e r : read (tag symbol) Re s u l t i n semantics s t a c k : V 16 I —I I— 1 i 2 . A c t i o n of p a r s e r : reduce (primary: tag symbol) Re s u l t i n semantics s t a c k : j I 1 » +—> tag node 3. A c t i o n of p a r s e r : read (becomes symbol) Resul t i n semantics s t a c k : unchanged. 4. A c t i o n of p a r s e r : read ( i n t e g r a l d e n o t a t i o n symbol) Result i n semantics s t a c k : I-1 17 A c t i o n of p a r s e r : symbol) reduce (denotation: i n t e g r a l d e n o t a t i o n R e s u l t i n semantics s t a c k : I I j I r i • +—> denotation node • +—> tag node 6. A number of r e d u c t i o n s not a f f e c t i n g the semantics stack that parse the primary as a t e r t i a r y , and the known den o t a t i o n as a u n i t . A c t i o n of p a r s e r : u n i t ) reduce ( a s s i g n a t i o n : t e r t i a r y , becomes. R e s u l t i n semantics s t a c k : ^ i i - i i ^ l • -J—> a s s i g n a t i o n node F i g u r e 3. 1 3.2. The B u i l d i n g Routines The changes i n the semantics stack t h a t r e s u l t i n the program t r e e nodes being b u i l t are accomplished by c a l l i n g c e r t a i n node b u i l d i n g r o u t i n e s . These are designed t o handle 18 the two d i f f e r e n t types of nodes: f i x e d length (e.g., a s s i g n a t i o n ) and v a r i a b l e l e n g t h (e.g., u n i t s e r i e s ) . r T 1 | a s s i g n | 3 | | range # | coor # | j * +—> >coercion sequence , j I • + — > > " t e r t i a r y " r 1 j • +—> >"unit" >"unit" 1 >"unit" n F i g u r e 3.2 The i n c l u s i o n of v a r i a b l e l e n g t h nodes s l i g h t l y changes the program t r e e s t r u c t u r e from t h a t of the s y n t a c t i c parse t r e e , e.g., the u n i t s e r i e s node of the s y n t a c t i c parse t r e e might look l i k e : | u n i t s e t . | 2 | r » A ^ | range # J coor # | I • + — > >unit s e r i e s | u n i t s e r . | range # | coor # —i —+__>— i 19 F i g u r e 3.3 Compacting v a r i o u s l i s t s , s e r i e s , t r a i n s , e t c . i n t o one node r e s u l t s i n a sav i n g of st o r a g e , and speeds up l a t e r passes through the program t r e e . When a node of v a r i a b l e l e n g t h i s being b u i l t on the semantics stack, a counter of i t s c u r r e n t l e n g t h must be kept there and updated when necessary. The f o l l o w i n g r o u t i n e s are used to manage the semantics s t a c k : • b u i l d b l o c k (type, mask)• t h i s r o u t i n e i s c a l l e d to b u i l d a node of type •type* from items on the semantics s t a c k . These items are removed and r e p l a c e d by a p o i n t e r to the node j u s t b u i l t . The •mask* i s used to d i s t i n g u s h between d i f f e r e n t forms of the node (e.g., between "l o o p : f o r p a r t , do c l a u s e " and "loop: do c l a u s e " ) . •increment* t h i s r o u t i n e i s c a l l e d to increment by one the count on the top of the semantics stack which i s the len g t h of the top v a r i a b l e l e n g t h node, e.g., •increments would be c a l l e d f o r the pro d u c t i o n r u l e u n i t s e r i e s : u n i t s e r i e s , go on symbol, u n i t . • s t a r t b l o c k (type, num)• s t a r t a v a r i a b l e l e n g t h node of type «type* with the top •num* items on the semantics stack. I n i t i a l i z e the l e n g t h 20 count t o I D U O I I . f o r example, • s t a r t b l o c k (ustype, 1) • would be c a l l e d f o r the pr o d u c t i o n r u l e u n i t s e r i e s : u n i t . endblock(type, depth)• b u i l d a v a r i a b l e l e n g t h node of type *type* which i s •depth* items from the top of the semantics s t a c k . The items making up t h i s node on the semantics stack are removed and r e p l a c e d by a p o i n t e r to the node. For example, * e n d b l o c k ( u l t y p e , 0 ) * would be c a l l e d f o r the pro d u c t i o n r u l e u n i t l i s t proper pack: open symbol, u n i t l i s t proper, c l o s e symbol. The f o l l o w i n g ALGOL 68 procedure d e c l a r a t i o n s give l g o r i t h m s f o r * b u i l d b l o c k , s t a r t b l o c k , increment* and endblock*, assuming the given d e c l a r a t i o n s : mode £tr=union(int,ref node); i n t top; [ T : 1 0 0 ] £tr s t a c k ; p_roc s t a r t b l o c k = ( i n t type, num)void: stack[top+:=1]:=num; proc increment=void: begin p_tr i:=stack[ top ]; i n t j:=case s t a c k [ t o p - 1 ] i n ( i n t k):k esac+1; sta c k [ top ]: = j ; s t a c k [ top-1 ]: = i end; 21 pjroc endblock=(int type, depth) v o i d : begin ir i t j:=casg stackf t o p ] i n ( i n t k):k esac+1; i n t k:=top-j-depth-1; stack[ k ]:=makenode (type,stackf k: top-1 ]) ; k + : = 1; s t a c k [ k: k+depth ]: = stack[ top-depth: top ]; top:=k+1 end; p_roc b u i l d b l o c k = ( i n t type, mask) v o i d : case type i n $ • • • $ # assignment, f o r example # begin # make node from t e r t i a r y and u n i t # stac k [ top-1 ]: = makenode (asstype, stack[ top-1: top ]) ; top-:=1 end, $ m • • $ esac; 3.3. Tree Pruning During the Parse In a d d i t i o n to i g n o r i n g t e r m i n a l s with no semantic content, there are other methods used t o make the program t r e e s m a l l e r than the s y n t a c t i c parse t r e e without l o s i n g e s s e n t i a l i n f o r m a t i o n . Many p r o d u c t i o n r u l e s (e.g., secondary: primary) are not used to group p a r t s of a c o n s t r u c t i o n t o g e t h e r , but are necessary f o r p a r s i n g purposes o n l y . A "secondary" node i s u s e l e s s f o r f u r t h e r passes and i s t h e r e f o r e never b u i l t . E l i m i n a t i n g these nodes r e s u l t s i n s i g n i f i c a n t savings s i n c e 25% 22 of the r u l e s are of t h i s type. Another easy way to reduce the s i z e of the program i s to e l i m i n a t e nodes such as u n i t s e r i e s , i f there i s only one member of the s e r i e s . T h i s may save q u i t e a l o t of space f o r some programs, s i n c e about 1 0 % of the pr o d u c t i o n r u l e s i n v o l v e l i s t s , s e r i e s , sequences, e t c . 23 Chapter 4. Touring the Program Tree 4.1. Procedure S t r u c t u r e The mode checking pass of the Vancouver ALGOL 68 compiler c o n s i s t s of a main r o u t i n e «tour« that v i s i t s a l l of the nodes of a program t r e e and, a t a p p r o p r i a t e p l a c e s , c a l l s the i d e n t i f i c a t i o n , c o e r c i o n , and b a l a n c i n g r o u t i n e s . «tour« i s a r e c u r s i v e r o u t i n e whose purpose i s to set up parameters to the mode checking r o u t i n e s i n such a way t h a t these r o u t i n e s need know nothing of the s t r u c t u r e of the program t r e e . The f o l l o w i n g f i g u r e i l l u s t r a t e s the h i e r a r c h y of the v a r i o u s r o u t i n e s i n the mode checking pass (a r o u t i n e " p o i n t s " to a l l r o u t i n e s t h a t i t c a l l s ) : 24 I r—>| balance j i d e n t i f y | \-—> | dyadic +-J o p e r a t o r s | ( i d e n t i f y | I-—>-| monadic +—> |operators! ->| tour I i I +— j I L < — ^ d i s p l a y s J < — + — > | i d e n t i f y | | s e l e c t o r s j I i i I-—>| coerce | j >+— j i d e n t i f y j >| c a l l s , + — > J j s l i c e s | i | i d e n t i f y j «-—>|identi- | | f i e r s | L F i g u r e 4.1 The f o l l o w i n g sequence of c a l l s would be made by checking the a s s i g n a t i o n i n • i n t i ; i : = 1 ; « : t o u r ( s t r o n g , a s s i g n a t i o n , v o i d ) tour ( s o f t , t a g , n i l ) i d e n t i f y i d e n t i f i e r (i) c o e r c e ( s o f t , #from# r e f i n t , #to# n i l ) tour ( s t r o n g , d e n o t a t i o n , i n t ) coerce (strong, #from# i n t , #to# i n t ) coerce (strong, #from# r e f i n t , #to# void) 25 A compiler pragmatic w i l l produce t r a c e s of t h i s form (see [ 1 1 ] ) -The c a l l * t o u r ( s t r o n g , r o o t of program t r e e , v o i d ) • i n i t i a t e s the mode checking pass. As i n other cases, the conn e c t i o n between the syntax of the Revised Report and the c a l l s of »tour* can be c l e a r l y seen: {2.2.1} program: str o n g v o i d new c l o s e d c l a u s e . 4.2. Tour The procedure - t o u r - must decide when to c a l l i d e n t i f i c a t i o n , c o e r c i o n , and b a l a n c i n g r o u t i n e s . Deciding when to c a l l the i d e n t i f i c a t i o n r o u t i n e s i s an easy task (e.g. • i d e n t i f y s e l e c t i o n * i s c a l l e d when at a s e l e c t i o n node i n the program tree) . C a l l i n g the coercion- and ba l a n c i n g r o u t i n e s i s a l i t t l e t r i c k i e r . In order to make the b a l a n c i n g r o u t i n e independent of the s t r u c t u r e of the program t r e e , a l l modes of the balance must be a v a i l a b l e when -balance* i s c a l l e d . To accomplish t h i s , i t i s necessary to " t o u r " the t r e e i n the s t a t e s : s t r o n g , f i r m , meek, weak, s o f t , and e r r o r corresponding to the SORTS of c o e r c i o n (plus a s t a t e of e r r o r ) . Deciding when to c a l l -balance* and -coerce* i s based on these s t a t e s . In a st r o n g p o s i t i o n , the a p o s t e r i o r i mode i s a l s o passed to * t o u r * . The parameter l i s t s f o r -balance* and *coerce* are b u i l t up 26 on • p a i r s t a c k a . The items of t h i s s t a c k c o n s i s t of a mode f i e l d , and a f i e l d which i s a p o i n t e r to where the c o e r c i o n sequence a s s o c i a t e d with t h a t mode may he s t o r e d . A count of the number of " p a i r s " on the stack i s always on the top of the s t a c k . There are two i n t e r e s t i n g types of nodes as f a r as c o e r c i o n i s concerned: "coercends", the o b j e c t s which may be coerced, and " c o e r c e r s " , the o b j e c t s which s y n t a c t i c a l l y i n i t i a t e a c o e r c i o n or balance e.g., i n t e g r a l e n q u i r y c l a u s e which i s a meek i n t e g r a l s e r i e s . I f a coercend i s a r r i v e d a t i n a strong p o s i t i o n (the a p o s t e r i o r i mode w i l l be known) then the procedure •c o e r c e * i s c a l l e d d i r e c t l y . Otherwise, the a p o s t e r i o r i mode w i l l not, i n g e n e r a l , be known and the mode of the coercend and i t s c o e r c i o n sequence' w i l l be placed on the p a i r s t a c k . The a c t i o n s at the a s s i g n a t i o n node ( and the de n o t a t i o n node are given below i n an attempt t o c l a r i f y t h i s e x p l a n a t i o n . DTOC tour= ( i n t s o r t , r e f node n, md a p o s t ) v o i d : b e ^ i n r e f md a p r i o r i , newapost; case node type of n i n # denotation # # a denotation i s a c o e r c i b l e o b j e c t # at a coercend(sort,mode of n,cs of n), # a s s i g n a t i o n # # an a s s i g n a t i o n i n i t i a t e s c o e r c i o n as we l l as being i t s e l f a c o e r c i b l e o b j e c t # p a i r s t a c k [ t o p + : = 1 ] : = ( 0 , n i l ) ; # s e t count to zero # tour ( s o f t , a s s t e r t i a r y of n , s k i p ) ; # stack l h s modes # i f at a c o e r c e r ( s o f t , a p r i o r i , n e w a p o s t ) # s o f t c o e r c i o n r e t u r n s a p r i o r i and new a p o s t e r i o r i modes # then 27 c l e a r ( p a i r stack); tour (strong,assunit of n, newapost); at a coercend (sort, a p r i o r i , c s of n) else error ("no possible soft balance"); clear (pair stack) ; tour (error,assunit of n,newapost) esac end Here the procedure «at a coercend* decides whether to c a l l •coerce* immediately, or stack a mode to be coerced l a t e r . The procedure *at a c o e r c e n decides whether to balance or coerce: p_roc at a coercend= (int sort,md m, ref cs c) void: i f sort=strong then coerce (strong,m,apost,c) e l s f sort-«=error then i n t i:=m of pair stack[top]; i + : = 1; pair stack[top ]:= (m,c); pair stack[ top+ :=1 ]:= ( i , n i l ) proc at a coercer=(int sort,type ref md a p r i o r i , newapost)bool: begin int i:=m of pair stack[ top]; [ 1 : i ] p_air a:=pair stack[ top-i- 1: top-1 ] ; i f i>1 then balance(sort,type,i,a) else coerce (sort, m of a[ 1 ], newapost, c of a[ 1 ]) Ik end 4.3. Displays ( C o l l a t e r a l Clauses) The change U33 of- [7] i n the language ALGOL 68 greatly eases many implementation problems. This change, r e s t r i c t i n g c o l l a t e r a l clauses to a strong position, resulted from 28 a m b i g u i t i e s i n operator i d e n t i f i c a t i o n d i s c o v e r e d by Wttssner and Yoneda [ 1 ] . The f o l l o w i n g s e c t i o n of an ALGOL 68 program i s the example given by Yoneda: mode a = [1:1] s; mode c = [1:2,1:1] s; mode s = s t r u c t ( r e f a f , g ) ; a a; s s; o£ ? = (c x) i n t : s k i p ; op ? = (s x) i n t : s k i p ; ? i f bool then s e l s e (a,a) f i I f the d i s p l a y a(a,a)« i s allowed i n a f i r m p o s i t i o n , then the i d e n t i f i c a t i o n of •?• depends on whether the d i s p l a y i s i n t e r p r e t e d as a row d i s p l a y or a s t r u c t u r e d i s p l a y . I f «(a,a)« i s taken as a s t r u c t u r e d i s p l a y of mode msm then the second d e c l a r a t i o n of • ? • i s i d e n t i f i e d . But i t may a l s o be taken as a row d i s p l a y of mode i n which case the f i r s t d e c l a r a t i o n of •?• i s i d e n t i f i e d . The r e s t r i c t i o n t h a t d i s p l a y s must be st r o n g s i m p l i f i e s weak and f i r m b a l a n c i n g , s i n c e a l l modes t h a t c o u l d p o s s i b l y be i n the weak or f i r m p o s i t i o n of the balance are now known. I f encountered as pa r t of a balance, d i s p l a y s may be s e t a s i d e u n t i l the mode of the balance i s found. Then the d i s p l a y s can be simply handled s i n c e t h e i r mode i s now known. The f o l l o w i n g syntax from the Revised Report {3.3.1} i n d i c a t e s c l e a r l y how d i s p l a y s must be handled: s t r o n g v o i d NEST c o l l a t e r a l c l a u s e : ' str o n g void NEST j o i n e d p o r t r a i t PACK, s t r o n g v o i d NEST p a r a l l e l c l a u s e : p a r a l l e l token, s t r o n g v o i d NEST c o l l a t e r a l c l a u s e . 29 s t r o n g ROWS of MODE NEST c o l l a t e r a l c l a u s e : where <ROWS> i s <row>, stro n g MODE NEST j o i n e d p o r t r a i t PACK; where <ROWS> i s <row R0WS1>, str o n g R0WS1 of MODE NEST j o i n e d p o r t r a i t PACK, st r o n g s t r u c t u r e d with FIELDS FIELD mode NEST c o l l a t e r a l c l a u s e : NEST FIELDS FIELD p o r t r a i t PACK. NEST FIELDS FIELD p o r t r a i t : NEST FIELDS p o r t r a i t , comma token, NEST FIELD p o r t r a i t . NEST MODE f i e l d TAG p o r t r a i t : s t r o n g MODE NEST u n i t . * s t r u c t u r e d i s p l a y : s t r o n g s t r u c t u r e d with FIELDS FIELD mode NEST c o l l a t e r a l c l a u s e . * row d i s p l a y : s t r o n g ROWS of MOST c o l l a t e r a l c l a u s e . A l l d i s p l a y s must be e i t h e r v o i d , ROWS of MODE, or s t r u c t u r e d with FIELDS mode. I f v o i d , then a l l c o n s t i t u e n t s of the d i s p l a y must be examined and s t r o n g l y coerced to v o i d . I f row ROWS of MODE (or row of MODE), then the c o n s t i t u e n t s of the d i s p l a y must be s t r o n g l y coerced to ROWS of MODE (or MODE). I f s t r u c t u r e d with FIELDS, then each c o n s t i t u e n t must be s t r o n g l y coerced to the mode of i t s a s s o c i a t e d FIELD. The f o l l o w i n g a l g o r i t h m i s used i n the Vancouver implementation to accomplish t h i s . T h i s a l g o r i t h m i s c a l l e d when the a p o s t e r i o r i mode of the d i s p l a y i s d i s c o v e r e d . proc d i s p l a y = (ref node n, md apost) v o i d : i f apost=void then f o r i to number of su b t r e e s of n do begin node t:= (subtree of n ) [ i ] ; tour ( s t r o n g , t , v o i d ) end e l s f modetype of apost=structure then i n t i=number o f subtrees of n; i f i-»=number o f s u b f i e l d s of apost then e r r o r ( " i n c o r r e c t l e n g t h of s t r u c t u r e d i s p l a y " ) e l s e f o r j to i do 30 node t:=(subtree of n ) [ j ] ; md m: = f i e l d mode of (sub f i e l d of a p o s t ) [ j ] ; tour (strong,t,m) end f i e l s f modetype of apost=row or modetype of apost=rowof then md m:=submode of apost; f o r i to number of subtrees of n do begin node t:=(subtree of n ) [ i ] ; tour(strong,t,m) end e l s e e r r o r ("display must be v o i d , row or s t r u c t u r e " ) 4.4. S l i c e s The mode of a s l i c e i n ALGOL 68 depends upon the mode of i t s primary, and the number of trimmers i n the s l i c e . There are r e a l l y two types of s l i c i n g , one'done on values of mode ROWS of MODE, and one done on values of' mode r e f e r e n c e to ROWS of MODE. The f o l l o w i n g examples i l l u s t r a t e t h i s : mode of a s l i c e # of trimmers mode of s l i c e a[1,2] 0 i n t [ r ] i n t a[ 1:2,3] 1 [ l i n t [ > liJQt a[ 1:2,3:4 ] 2 [ • li£t r e f [ , ] i n t a[ 1,2 ] 0 r e f i n t r e f [ , ] i n t a[ 1:2,3] 1 r e f [ ] i n t r e f [ , ] i n t a[ 1:2,3:4 ] 2 r e f [ , l i n t The p r e c i s e connection between the modes and the number of 31 trimmers i s d e f i n e d i n the Revised Report {5.3.2.1} as f o l l o w s : REFETY M0DE1 NEST s l i c e : weak REFLEXETY ROWS 1 of M0DE1 NEST PRIMARY, ROWS 1 l e a v i n g EMPTY NEST indexer STYLE bracket, where <REFETY> i s de r i v e d from <REFLEXETY>; where <MODE1> i s <R0WS2 of M0DE2>, weak REFLEXETY R0WS1 of M0DE2 NEST PRIMARY, ROWS 1 l e a v i n g R0WS2 NEST indexer STYLE b r a c k e t , where <REFETY> i s d e r i v e d from <REFLEXETY>. row ROWS l e a v i n g R0WSETY1 R0WSETY2 NEST i n d e x e r : row l e a v i n g ROWSETY1 NEST indexe r , comma token, ROWS l e a v i n g R0WSETY2 NEST indexer. row l e a v i n g EMPTY NEST indexer: NEST s u b s c r i p t . row l e a v i n g row NEST indexer: NEST trimmer; NEST new lower bound o p t i o n . NEST s u b s c r i p t : meek i n t e g r a l NEST u n i t . NEST trimmer: NEST lower bound o p t i o n , up t o token, NEST upper bound o p t i o n , NEST new lower bound o p t i o n . NEST new lower bound: at token, NEST lower bound. Each time a s l i c e node i s encountered during the tour of a program t r e e , the number of trimmers i n the t r i m s c r i p t l i s t i s counted. T h i s , together with the mode of the primary i s used to c a l c u l a t e the mode of the s l i c e . In a d d i t i o n , the t o t a l number of t r i m s c r i p t s i n the s l i c e i s checked a g a i n s t the mode of the primary. The f o l l o w i n g a l g o r i t h m i s used: £roc at a s l i c e = (ref node n, r e f md a ) v o i d : begin i n t t s , t ; rod m; ts:=number of t r i m s c r i p t s ( t r i m s c r i p t s of n) ; t:=number of trimmers ( t r i m s c r i p t s of n) ; #find new mode of s l i c e # i f mode type of a = r e f e r e n c e then f o r i to t do begin m:=refsub o f a; i f mode type of m=rowoftype and i < t then 32 error("too many trimscripts i n s l i c e " ) ; goto exit I i ; ~ a:=refrowsub of m end; / m:=refsub of a else for i to t do begin i f modetype of a=rowoftype and i<t then error("too many trim s c r i p t s in s l i c e " ) ; goto e x i t f i ; ~ " a:=rowsub of a end; m :=a l i ; # check number of trimscripts # for i to t s - t do begin i f modetype of m=rowoftype and i<t then error ("too many tr i m s c r i p t s in s l i c e " ) ; goto e x i t e l s f modetype of m->=rowof type and i-1 then error ("too few tri m s c r i p t s i n s l i c e " ) ; goto e x i t f i ; m:=rowsub of m end; e x i t : ski£ end 4.5. I d e n t i f i c a t i o n of I d e n t i f i e r s A l l mode and label i d e n t i f i e r s must be i d e n t i f i e d during the mode checking pass through the program tree. During the mode independent parse of the program, a l l defining occurences of a given i d e n t i f i e r are placed i n a linked l i s t . The items in th i s l i s t contain range information and mode information about that i d e n t i f i e r . The l i s t i s ordered from highest range number 33 (youngest range) to lowest range number (oldes t range) to make lookup more e f f i c i e n t . As the program t r e e i s toured, a c t i v e ranges are placed on a range stack when a range i s entered and are removed from t h i s stack when the range i s l e f t . The d e c l a r a t i o n i d e n t i f i e d i s the one with the hi g h e s t numbered (youngest) range which i s c u r r e n t l y on the range stack. A p o i n t e r t o t h i s d e c l a r a t i o n i s put i n the i d e n t i f i e r node of the program t r e e f o r use by l a t e r passes. The f o l l o w i n g a l g o r i t h m i s used: jgroc i d e n t i f y i d e n t i f i e r s = (ref node n) b o o l : begin d e f l i s t d : = i d e n t i f i e r d e f i n i t i o n s [ t a g of n ] ; i n t t:=top of range s t a c k ; i n t a c t i v e range:=range s t a c k [ t ] ; i n t d e f i n i t i o n range:=range of d; b o o l can i d e n t i f y : = a c t i v e r a n g e = d e f i n i t i o n range; while -ican i d e n t i f y rep_ while a c t i v e r a n g e > d e f i n i t i o n range re£ " t - : = 1; i f t=0 then e r r o r e x i t f i ; a c t i v e range:=range s t a c k [ t ] £§r; while a c t i v e r a n g e < d e f i n i t i o n range rejD d:=next of d; i f d : = : n i l then e r r o r e x i t f i ; d e f i n i t i o n range:=range of d can i d e n t i f y : = a c t i v e r a n g e = d e f i n i t i o n range ' E§.r; tag of n:=d; goto e; e r r o r e x i t : e r r o r ( " i d e n t i f i e r cannot be i d e n t i f i e d " ) ; e: can i d e n t i f y end 34 4.6. I d e n t i f i c a t i o n of S e l e c t o r s During the mode checking pass, a l l s e l e c t i o n s must be i d e n t i f i e d with the a p p r o p r i a t e f i e l d of a s t r u c t u r e . The i n c l u s i o n i n ALGOL 68 of m u l t i p l e s e l e c t i o n s [7], makes i t necessary to do some s e a r c h i n g f o r a mode with row p r e f i x e s . T h i s i s done by the procedure «findmode». The f o l l o w i n g a l g o r i t h m i s used to i d e n t i f y s e l e c t i o n s : p_roc i d e n t i f y s e l e c t o r s = (ref node n, r e f md a) b o o l : begin b o o l can i d e n t i f y : = f a l s e ; i n t num refs:=0, num rows:=0; md m; i f mode type o f a=reference then a:=refsub of a; num refs+:=1; f i ; while modetype of a=row or modetype of a=rowof re_p_ a:=rowsub of a; num rows+:=1 E££; f o r i t o number of submodes of a while -*can i d e n t i f y rep, m:= ( s t r u c t s u b of a ) [ i ] ; can i d e n t i f y : = f i e l d t a g of m=tag of n £er; i f can i d e n t i f y then f i e l d of n:=m; a:=findmode(num refs,num rows,a) e l s e e r r o r ( " s e l e c t i o n cannot be i d e n t i f i e d " ) ; £i; can i d e n t i f y end 35 4.7. I d e n t i f i c a t i o n of C a l l s and S l i c e s U n t i l mode checking has been done, there i s no way to t e l l whether a c o n s t r u c t i o n such as «if b then cs e l s e goto 1 fi{1,2)« i s a c a l l or s l i c e . T h e r e f o r e , the implementer must balance some modes without even knowing the s o r t of the balance. What i s known, however, can be used to f i n d the s o r t of the balance q u i c k l y . Since the c o n s t r u c t i o n i n v o l v e d must be e i t h e r a c a l l or a s l i c e , the balance must be e i t h e r meek t c procedure with parameters, or weak. To t e s t whether a meek balance to procedure with parameters i s p o s s i b l e , attempt to coerce the f i r s t non-hip, n o n - d i s p l a y mode to procedure with parameters. I f t h i s succeeds, then the balance must be meek or there i s no p o s s i b l e balance. I f i t f a i l s , then the balance must be weak or not be p o s s i b l e , nroc i d e n t i f y c a l i c e s = ( i n t num modes, [: ]md m, r e f i n t t y p e ) v o i d : begin md p:=some procp mode; f o r i t o num modes do i f m[i]-i=a hip or m[ i ]-»=collateral modes then i f coerce (meek, m[ i ], p) then t y p e : = c a l l e l s e t y p e : = s l i c e f i * . goto f ; I i ; e r r o r ( " c a l l or s l i c e cannot be i d e n t i f i e d " ) ; f : s k i p end; 36 4.8. V i c t a l Checking D e c l a r e r s i n ALGOL 68 are of three types: v i r t u a l , a c t u a l , and f o r m a l . Since i t i s i n c o n v e n i e n t to check these types dur i n g the mode independent parse, they are checked during the mode checking pass. Formal and v i r t u a l rows may not c o n t a i n bounds, and a c t u a l rows must have them. Thus the f o l l o w i n g examples are i n c o r r e c t : r e f [ 1 : 1 0 ] i n t a=loc[1:10 ] i n t ; r e f [ ] i n t a=loc[ ] i n t ; And must be w r i t t e n ; r e f [ Tint a=loc[1:10 l i n t ; | The d e c l a r e r •yoid« i s r e s t r i c t e d i n use to void c a s t s , c o n s t i t u e n t s of u n i t e d modes, and the modes y i e l d e d by procedures. The v i c t a l check c o n s i s t s merely of examining a l l d e c l a r e r s i n e i t h e r of the s t a t e s v i r t u a l , a c t u a l , or formal and checking t h a t they have a p p r o p r i a t e bounds. The s t a t e s are determined by the r u l e s of the Revised Report {4.6}. 4.9. E r r o r Recovery I f one p a r t of a c o n s t r u c t i o n i s i n c o r r e c t , what should be done about mode checking the r e s t of i t ? For example, i n the a s s i g n a t i o n of " i n t 2=1; z:=3.0«, the l e f t hand s i d e i s examined and found to be i n e r r o r (the mode of »z« must begin with a 37 r e f ) . What then should be the a c t i o n taken on the r i g h t hand s i d e of the a s s i g n a t i o n ( i t a l s o would be i n e r r o r i f the mode of mzm were r e f i n t ) ? Two p o s s i b i l i t i e s would be: 1. assume the mode of the r i g h t hand s i d e i s i n t , and proceed as always. 2. Do not even c o n s i d e r the r i g h t hand s i d e , s i n c e the l e f t hand s i d e i s i n e r r o r . Neither of these methods i s good, i n g e n e r a l . The f i r s t approach, t o make assumptions about the modes, i s d i f f i c u l t i n ALGOL 68 because of the l a r g e number of p o s s i b l e modes. I t would tend t o produce many e r r o r messages where no e r r o r e x i s t s and i s would be d i f f i c u l t to separate them from the r e a l e r r o r s . The second method does not g i v e the programmer as much i n f o r m a t i o n about h i s program as i s p o s s i b l e . T h i s can be seen from the example: jaroc i n t i=ski£; [1:3 ]rea 1 y; i n t z=2; i : = (ski£ J y[1,2] | z: = 2) Even though the l e f t hand s i d e , of t h i s a s s i g n a t i o n i s i n c o r r e c t , t h e r e are t h r e e e r r o r s on the r i g h t hand s i d e that would b e / e r r o r s no matter what the l e f t hand s i d e would be. The method of d e a l i n g with t h i s problem i n the Vancouver compiler i s to examine the r i g h t hand s i d e i n a s p e c i a l e r r o r s t a t e . While no e r r o r s are d e t e c t e d i n t h i s e r r o r s t a t e , i t i s p o s s i b l e to get i n t o a known s t a t e i n a p a r t of a c o n s t r u c t i o n t h a t i s being c o n s i d e r e d i n the e r r o r s t a t e . In the above 38 example, i t i s s t i l l p o s s i b l e to de t e c t e r r o r s i n «ski£« (no meek c o e r c i o n to b o o l ) , *y[1,2]« (too many t r i m s c r i p t s ) , and •z:=2« (z does not begin with a r e f ) even though nothing i s checked of the modes of the s l i c e , «y[1»2]«, and of the a s s i g n a t i o n , •z:=2«. T h i s method has the f o l l o w i n g p r o p e r t i e s : 1. No e r r o r messages are generated because of assumptions about e a r l i e r e r r o r s . 2. A l l " c e r t a i n " e r r o r s i n s u b - c o n s t r u c t i o n s of erroneous c o n s t r u c t i o n s can be de t e c t e d . There i s an unfortunate consequence of the method of mode checking an ALGOL 68 program. One hundred e r r o r s , a l l the same ( r e a l cannot be coerced t o i n t ) , are found i n a c o n s t r u c t i o n • [ a = ( 1 . 0 , . . . , 1 0 0 . 0 ) There i s c l e a r l y only one co n c e p t u a l e r r o r here, and we f e e l j u s t i f i e d i n making a s m a l l e f f o r t to avoid p r i n t i n g out 100 error,messages. The f o l l o w i n g a l g o r i t h m i n the e r r o r p r i n t i n g r o u t i n e i n s u r e s t h a t an e r r o r that occurs numerous times separated by only one c o o r d i n a t e (comma or go on symbol — see [11]) w i l l be p r i n t e d only 3 times: i f t h i s e r r o r = l a s t e r r o r and t h i s coor = l a s t coor+1 then e r r o r count +:=1 e l s f e r r o r count>3 then p r i n t ( ( " p r e v i o u s e r r o r d e t e c t e d " , e r r o r c o u n t , " t i m e s " ) ) ; error count:=1 se error count;=1 » error count<3 then p r i n t ( t h i s error) st error:=this error; l a s t coor:=this 40 Chapter 5. I | B a l a n c i n g and Operator I d e n t i f i c a t i o n I 5.1. D e f i n i t i o n o f Bal a n c i n g In ALGOL 68, c o n s t r u c t i o n s such as s e r i 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 have a mode a s s o c i a t e d with them. T h i s makes i t p o s s i b l e to w r i t e c o n s t r u c t i o n s l i k e • r e a l x, r e f r e a l y; (Plxjy) : = 1.0« and • i n t i , j ; a[ 1: (p | i | j) ]•• . The mode of the c l a u s e may be d e r i v e d from the c o n s t i t u e n t modes i n the c l a u s e and the p o s i t i o n o f the c l a u s e i n the program or may be known without examining the modes wi t h i n the c l a u s e . Thus, i n the f i r s t example, " r e f e r e n c e to r e a l " can be d e r i v e d from the modes of x and y, and i n the second example, " i n t e g r a l " i s known to be the mode of the c l a u s e , whatever i and j might be. In e i t h e r case, the language makes the same requirement to i n s u r e that the program "makes sense": t h a t one of the c o n s t i t u e n t modes of a SORT c l a u s e be SORTly c o e r c e a b l e to the a p o s t e r i o r i mode of the c l a u s e , and t h a t the other modes of the c l a u s e be s t r o n g l y c o e r c a b l e to t h a t same mode of the c l a u s e . T h i s requirement means t h a t the a p o s t e r i o r i mode of the c l a u s e , d i s r e g a r d i n g c o e r c i o n s of a given SORT, w i l l be the same as one of i t s 41 c o n s t i t u e n t modes. The s e l e c t i o n of t h i s mode from the c o n s t i t u e n t s o f a c l a u s e i s known as ba l a n c i n g . 5.2. The Need f o r E f f i c i e n t B a l a n c i n g ' Neither the Report nor the Revised Report g i v e s any h i n t of how the SORT p o s i t i o n of a balance can be found, other than by a process of t r i a l and e r r o r . While t h i s approach may be f i n e f o r the c l a u s e • (p|x|y): = 1.0«, i n ge n e r a l t r i a l and e r r o r i s too expensive to use. In a case c l a u s e l i k e the f o l l o w i n g , each time a candidate f o r the SORT p o s i t i o n , y£ i ], i s examined, n s t r o n g c o e r c i o n attempts may be made before one f a i l s (assuming the c a n d i d a t e s are chosen i n o r d e r ) : [1:n ] r e f i n t y; i n t x; case i i n • • • out x esac:=1. T h i s i s because f o r each i , only the mode of x ("reference to i n t e g r a l " ) cannot be s t r o n g l y coerced to the mode of y£i] ("reference to r e f e r e n c e t o i n t e g r a l " ) . Before the c o r r e c t c a n d i d a t e x i s chosen, an embarrassing amount of time may be spent i f the value of n i s l a r g e . U 2 5.3. The Development of Balancing Beige S c h e i d i g [ 3 ] i n h i s d o c t o r a l t h e s i s of 1970 presented a quick method f o r determining the s o f t and weak p o s i t i o n s f o r s o f t and weak balances. T h i s method i n v o l v e d counting the r e f and row p r e f i x e s which are at the beginning of a mode. For s o f t balances, S c h e i d i g showed that the c o n s t i t u e n t mode of the balance with the minimal number of r e f p r e f i x e s (and maximal number of row p r e f i x e s i f two modes had the same number of r e f p r e f i x e s ) must be the mode i n the s o f t p o s i t i o n of the balance. For weak balances, the mode with the maximal number of row p r e f i x e s must be the one i n the weak p o s i t i o n of the balance. In 1972, S c h e i d i g [ 6 ] s t a t e d (without g i v i n g a method) t h a t the f i r m p o s i t i o n of a f i r m balance could be found i f the p o s i t i o n s of c o l l a t e r a l c l a u s e s i n the language were r e s t r i c t e d . He pointed out t h a t these r e s t r i c t i o n s were a l s o necessary to avoid ambiguity i n the i d e n t i f i c a t i o n of o p e r a t o r s . In September, 1972, IFIP Working Group 2.1 approved e x t e n s i v e changes to the language ALGOL 68 [ 7 ] , [ 8 ] . Among these changes were two that a f f e c t e d b a l a n c i n g : C58 (more meekness) and 033 (strong d i s p l a y s ) . The a d d i t i o n of more meek p o s i t i o n s , e s p e c i a l l y the UNITED ch o i c e i n the conformity c l a u s e , made i t necessary to do meek b a l a n c i n g . The r e s t r i c t i o n of d i s p l a y s to a str o n g context c l e a r e d up operator ambiguity problems (see chapter 4) and a l s o made i t p o s s i b l e to do a f a s t f i r m balance. 43 E a r l y i n 1973, H. J . Hansen proposed a b a l a n c i n g f u n c t i o n h, a c t i n g on a mode and y i e l d i n g an i n t e g e r value, that c o u l d be used to f i n d the f i r m p o s i t i o n of a balance. Numerous m o d i f i c a t i o n s to t h i s f u c t i o n were made a t the U n i v e r s i t y of B r i t i s h Columbia and the U n i v e r s i t y of a l b e r t a (Edmonton) to make i t handle meek, weak, and s o f t b a l a n c i n g as we l l as f i r m b a l a n c i n g . Hendrik Boom [ 9 ] i n June, 1973 put forward an improved f u n c t i o n h, a c t i n g on a mode and y e i l d i n g a r a t i o n a l v a l u e , that c o u l d be used f o r any SORT of c o e r c i o n . Since t h a t time, some s i m p l i f i c a t i o n s (due to L. Meertens) have been made i n the f u n c t i o n making i t e a s i e r to d e s c r i b e . The f o l l o w i n g r e s u l t using the bala n c i n g f u n c t i o n to order modes s o l v e s the problem of e f f i c i e n t b a l a n c i n g (some problems may a r i s e i f a suggested change f o r c e s b a l a n c i n g of t r a n s i e n t s , see the Revised Report {3.2.1.k}): General B a l a n c i n g Theorem L e t m1,...mn be n modes (n>1). Let m i n {m1,...,mn} be such t h a t : h(m)>h(mi) f o r a l l i=1,...n. Then i n any SORT balance of o b j e c t s of modes m1,...,mn together with some h i p s and some d i s p l a y s , m may be i n the SORT p o s i t i o n of the balance. 44 5.4. General B a l a n c i n g Theorem 5.4.1. D e f i n i t i o n of h The f o l l o w i n g d e f i n i t i o n of h i s one given by 1. Meertens. The f u n c t i o n h has an i n t e g r a l p a r t H and a f r a c t i o n a l p a r t d e r i v e d from a f u n c t i o n r th a t keeps tr a c k of the number of r e f s . T h i s s e p a r a t i o n i s necessary to i n s u r e t h a t the number of r e f s , a count necessary f o r s o f t c o e r c i o n , can s a f e l y be ignored f o r non-soft c o e r c i o n . h (m)=H (m) +2** (-r (m)) H (ref ROWS of m)=H(ROWS of m) -1 H (ref m) =H (proc m)=H (m) H (L r e a l ) =2 H (L com£l)=4 . H(rows of m)=2n+H(m) where there are n rows i n ROWS H (union (ml ,...mn) )=2n+max{H (ml) ,...H (mn) } H(m)=0 i n a l l other cases r ( r ef m) =r (m) +1 r (proc I) =r (m) r(m)=0 i n a l l other cases Table 5.1. h Function 5.4.2. P r o p e r t i e s of h The numerical values of h on a mode are unimportant provided t h a t the f o l l o w i n g p r o p e r t i e s are preserved. They w i l l be r e f e r e n c e d l a t e r i n the pr o o f s of the General Balancing Theorem. (H1) A s e r i e s of c o e r c i o n s c o n t a i n i n g a strong or f i r m (but not meek) c o e r c i o n , except v o i d i n g , ( i . e . , rowing, widening, u n i t i n g ) i n c r e a s e the value of h by at l e a s t 1. They i n c r e a s e H by a t l e a s t 1. F u r t h e r , i f the c o e r c i o n i s not to r e f ROWS of m, then h i s i n c r e a s e d by at l e a s t 2 (since H i s ) . (H2) A s e r i e s of meek c o e r c i o n s a f f e c t the value of h by l e s s 1 than 2. T h i s i s because the value of H may be a f f e c t e d by only 1 ( f i r s t r u l e ) and the value of 2**(-r) w i l l be a f f e c t e d by l e s s than 1. Fu r t h e r , a s e r i e s of meek c o e r c i o n s to r e f ROWS of m i n c r e a s e h by l e s s than 1 (since the f i r s t r u l e f o r H cannot a p p l y ) . (H3) h i s u n a f f e c t e d by s o f t c o e r c i o n . Neither H nor r i s . 46 (H4) A l l non-soft c o e r c i o n s to r e f e r e n c e to mode i n c r e a s e the value of h. T h i s i s because r decreases (hence 2**(-r) V i n c r e a s e s ) while H i s u n a f f e c t e d , s i n c e the f i r s t r u l e cannot apply. 5.4.3. C o e r c i o n P r o p e r t i e s The f o l l o w i n g p r o p e r t i e s of c o e r c i o n are used to prove the General B a l a n c i n g Theorem. The a p p r o p r i a t e syntax of the Revised Report i s giv e n to i n d i c a t e how these p r o p e r t i e s have been d e r i v e d . (C1) No s t r o n g (but not meek) c o e r c i o n can occur before u n i t i n g . T h i s i s c l e a r from the r u l e : {6.4.1} un i t e d to UNITED FORM: MEEK MOID FORM, where MOID u n i t e s to UNITED. (C2) No meek c o e r c i o n can occur a f t e r u n i t i n g . T h i s i s because d e r e f e r e n c i n g and deproceduring are the meek c o e r c i o n s , and they must be on r e f e r e n c e to and procedure modes r e s p e c t i v e l y : {6.2.1} dereferenced to MODE 1 FORM: MEEK REF to M0DE2 FORM, where M0DE2 d e f l e x e s to MODEL {6.3.1} deprocedured to MOID FORM: MEEK procedure y i e l d i n g MOID FORM. 47 (C3) The only meek (but not weak) coercion i s dereferencing to STOWED (structured or rowed). This i s clear from the rules: {6.1.d} weak BEFETY STOWED FORM coercee: MEEK REFETY STOWED FORM, unless <MEEK> i s <dereference to> and <REFETY> i s <EMPTY>. 5.4.4. Mode Ordering Theorem Mode Ordering Theorem Let a, b, and c be modes such that: a can be strongly coerced to c. a cannot be SORTLY coerced to c. b can be SORTLY coerced to c. c i s not void. Then h (a) <h (b) . Proof of Mode Ordering Theorem case 1 SORT=firm no strong coercion can occur before uniting (C1) 48 => {since a can be s t r o n g l y , - i f i r m l y coerced to c) c cannot be a u n i t e d mode no meek c o e r c i o n can f o l l o w u n i t i n g (C2) => (since b can be f i r m l y coerced t o non-united c) b can be meekly coerced to c => t h i s case reduces to SORT=meek case 2 SORT=meek a. c i s r e f [ ]m s t r o n g or f i r m c o e r c i o n s i n c r e a s e h by at l e a s t 1 (H1) => h (a)<h (c)-1 meek c o e r c i o n s to r e f [ ]m i n c r e a s e h by l e s s than 1 (H1) => h ( c ) - K h (b) t h e r e f o r e , h(a)<h(b) b. c i s not r e f [ ]m stro n g or f i r m c o e r c i o n s i n c r e a s e h by at l e a s t 2 (H1) => h (a) <h (c)-2 meek c o e r c i o n s to non r e f f ]m i n c r e a s e h by l e s s than 2 (H2) = > 49 h (c)-2<h (b) t h e r e f o r e , h (a) <h (b) case 3 SORT=weak a. a can be s t r o n g l y or f i r m l y , but not meekly coerced to c T h i s case i s the same as above. b. a i s meekly, but not weakly coerced to c the one meek, ->weak c o e r c i o n i s d e r e f e r e n c i n g to STOWED (C3) => a=prgf ... £ref r e f c and c i s STOWED => h (a) <h ( r e f c) = h (c) -1 b can be weakly dereferenced and deprocedured to c = > b-£ref ... £ref £jcoc c or b=c => h ( c ) - K h (b) t h e r e f o r e , h(a)<h(b) A case 4 SORT=soft h i s u n a f f e c t e d by s o f t c o e r c i o n (H3) => h(b)=h(c) s o f t c o e r c i o n i s only t o a r e f e r e n c e to mode => 50 c=ref m a l l non-soft c o e r c i o n to r e f e r e n c e to mode i n c r e a s e s h (H4) => h (a)<h (c) =h (b) 5.4.5. Proof of General Balancing Theorem General Balancing Theorem Let m1,...mn be n modes (n>1). Le t m i n {m1,...,mn} be such t h a t : h (m) >h (mi) f o r a l l i=1,...n. Then i n any SORT balance of o b j e c t s of modes m1,...,mn together with some h i p s and some d i s p l a y s , m may be i n the SORT p o s i t i o n of the balance. Proof of General Balancing Theorem case SORT=strong m may be i n the st r o n g p o s i t i o n , s i n c e every p o s i t i o n i s a st r o n g p o s i t i o n . case SORT-«=strong v o i d can only be the mode of a balance i n a strong p o s i t i o n , t h e r e f o r e the c o e r c i o n v o i d i n g i s excluded f o r t h i s case. 51 Assume m may not be i n the SORT p o s i t i o n of the balance. => (from the d e f i n i t i o n of balancing) There must be a mode £ i n {ml,...,mn } t h a t i s i n the SORT p o s i t i o n of the balance, and th e r e must be a mode 3 such t h a t : £ can be SORTLY coerced to 3, and m can be s t r o n g l y , but not SORTLY coerced to 3 => (from the Mode Ordering Theorem) h{J3)<h(£) but t h i s i s im p o s s i b l e because of the way i n which m i s chosen, t h e r e f o r e the assumption must be i n c o r r e c t and m may be i n the SORT p o s i t i o n of the balance 5.5. Meek, Weak, and S o f t B a l a n c i n g Algorithms As a r e s u l t of the General B a l a n c i n g Theorem, the f o l l o w i n g a l g o r i t h m may always be used to f i n d the mode i n the SORT p o s i t i o n of a balance: £roc s o r t mode= ( i n t num modes, [:] md m)md: begin i n t max:=0, po s i t i o n : = 1 ; f o r i to num modes do i f " m[ i ]-i=a hip and m[ i ]-»=collateral modes and h of m[i]>max then max:=h of m [ i ] ; p o s i t i o n : = i i i ; m [ p o s i t i o n ] end Meek, weak, and s o f t balances are a l l s l i g h t l y d i f f e r e n t . 52 Depending on the SORT, the mode of the balance may be completely known, or only i t s type may be known. I f onl y the type i s known, then the mode of the balance must be returned by the ba l a n c i n g a l g o r i t h m . The f o l l o w i n g t a b l e g i v e s a l l types of balances: T ; 1 SORT of balance I t.J£e i n f o r m a t i o n I context I ~ ~ I s o f t | r e f e r e n c e t o | l h s a s s i g n a t i o n , | | i d e n t i t y r e l a t i o n I I weak ( s t r u c t with FIELDS | s e l e c t i o n |ROWS of MODE | s l i c e I I meek I i n t e g r a l I i n t CHOICE, bound jboolean Jboolean CHOICE |UNITED |UNITED CHOICE |proc with PARAMETERS | c a l l I I L L Table 5.2. B a l a n c i n g The f o l l o w i n g a l g o r i t h m can be used f o r meek, weak, and s o f t balances. The type which i s passed to t h i s a l g o r i t h m i s the type demanded by the context of the balance, as o u t l i n e d by the p r e v i o u s t a b l e . p_roc m w s balance= ( i n t s o r t , type, num modes, [:] md m, r e f md p ) b o o l : begin # f i n d s o r t p o s i t i o n # md sm:=sortmode(num modes,m) ; bo o l can balance; # get mode of balance i n p I can balance:= case s o r t i n s o f t coerce (sm, p) , weak coerce(sm,p,type), 53 meek coerce(sm,p,type) esac; f o r i to num modes while can balance do 1 can balance:=coerce (strong,m[i],p) ; i f -ican balance then error("modes cannot be balanced") can balance end 5.6. Operator I d e n t i f i c a t i o n and Firm Balancing When an a p p l i e d occurrence of an operator i n d i c a t i o n i s used i n a formula, i t must be determined which of the operator d e f i n i t i o n s i s i d e n t i f i e d . To do t h i s , ALGOL 68 r e q u i r e s t h a t the operands of the operator must be f i r m l y balanced to the c o r r e s p o n d i n g mode i n the d e f i n i t i o n . The General B a l a n c i n g Theorem s t a t e s a method of f i n d i n g the f i r m p o s i t i o n of the balance without knowing the mode of the balance. T h i s method, together with the f a c t t h a t the o n l y f i r m p o s i t i o n s i n ALGOL 68 are the operands of formulas, can be used to speed up the i d e n t i f i c a t i o n of o p e r a t o r s by combining the a l g o r i t h m s of f i r m b a l a n c i n g and o p e r t o r i d e n t i f i c a t i o n . T h i s avoids a r e p e t i t i o n of f i n d i n g the f i r m p o s i t i o n of the balance f o r each operator d e f i n i t i o n t h a t i s t e s t e d . The syntax of the Revised Report has changed the i d e n t i f i c a t i o n of o p e r a t o r s s l i g h t l y from what i t was i n the Report. A r e s t r i c t i o n , commonly r e f e r e d to as the Dresden 2 c o n d i t i o n can be s t a t e d , [ 9 ] page 4, as f o l l o w s : " I f an a p p l i e d occurrence A of an operator symbol S 54 i d e n t i f i e s a d e f i n i n g occurrence D i n range R, then there s h a l l be no other d e f i n i n g occurrence D' f o r S i n any range R« w i t h i n R and c o n t a i n i n g A whose operand modes are r e l a t e d to those of D." Here " r e l a t e d " i s used i n the same sense as the Report, i . e . two modes are r e l a t e d i f both can be f i r m l y coerced from the same mode. T h i s would mean that i n the f o l l o w i n g program, the a p p l i e d occurrence of • ? • would i d e n t i f y no d e f i n i n g occurrence, although a c c o r d i n g t o the 1968 Report the f i r s t d e c l a r a t i o n of •?• would be i d e n t i f i e d , begin o_p ? = ( i n t a) i n t : skij>; begin o£ ? = (ref i n t a ) i n t : s k i p ; ? 1 end end The f o l l o w i n g a l g o r i t h m i d e n t i f i e s monadic o p e r a t o r s (dyadic o p e r a t o r s are handled s i m i l a r l y ) : proc i d e n t i f y monadic operators= (ref node f , r e f md a, [: ] md m, i n t num modes) b o o l : begin b o o l can i d e h t i f y : = f a l s e ; d e f l i s t d: = mbnadic operator d e f i n i t i o n s [ o p of f ]; i n t t:=top of range s t a c k ; i n t d e f i n i t i o n range:=range of d; i n t a c t i v e range:=range s t a c k [ t ] ; md f i r m mode: = sortmode (num modes,m); # f i n d a d e f i n i n g occurrence # while ->can i d e n t i f y re£ while a c t i v e r a n g e > d e f i n i t i o n range re£ ~ t-:=1; i f t=0 then goto e r r o r e x i t f i ; a c t i v e range:=range s t a c k [ t ] while a c t i v e r a n g e < d e f i n i t i o n range rep d;=next of d; i f d:=:nil then goto e r r o r e x i t f i ; d e f i n i t i o n range:=range of d ££E; while active range=definition range and - i c a n / i d e n t i f y can identify:=coerce(firm,firm mode,md of d) ; for i to num modes while can i d e n t i f y do can identify:=coerce(strong,m[i],md of d) ; E^r; # check Dresden 2 # d e f l i s t e: = monadic operator definitions[op of f ]; bool related:=false; while e:-i=:d and -irelated rep_ related:=check (md of e,md of d) ; e:=next of e £er; i f related then ~ error ("violation of Dresden 2 condition") f i ; e r r o r e x i t : i f can i d e n t i f y then op of f:=d; a:=delivered md of d else error("cannot i d e n t i f y monadic operator") Hi ; can i d e n t i f y end 56 Chapter 6. 1 I C o e r c i o n | I i 6.1. I n t r o d u c t i o n Coercion i n a programming language may be definded as the t r a n s f o r m a t i o n of one data type (or mode) i n t o another. ALGOL 68 pr o v i d e s a l a r g e number of p r i m i t i v e data types, and a l l o w s a programmer t o d e f i n e any number of data types that may be b u i l t from these p r i m i t i v e s . In a d d i t i o n , the orthogonal design of the language a l l o w s the programmer to use the data types he has d e f i n e d i n a l a r g e number of d i f f e r e n t c o n t e x t s . T h i s r e s u l t s i n a complicated c o e r c i o n process, and a number of d i f f e r e n t SORTs of c o e r c i o n f o r use i n d i f f e r e n t c o n t e x t s . The SORTS: s t r o n g , f i r m , meek, weak and s o f t are ordered i n the f o l l o w i n g way: 57 st r o n g I f i r m I meek 1 weak I s o f t , F i g u r e 6.1 Meaning t h a t a l l s o f t c o e r c i o n s a re a l s o weak c o e r c i o n s , and a l l weak c o e r c i o n s are meek c o e r c i o n s , e t c . The f o l l o w i n g syntax of the Revised Report {6.1} shows t h i s o r d e r i n g of the SORTS of c o e r c i o n : STRONG:: FIRM; widened t o ; rowed t o ; voided t o . FIRM:: MEEK; u n i t e d t o . MEEK:: unchanged from; dereferenced t o ; deprocedured t o . SOFT:: unchanged from; s o f t l y deprocedured t o . In these r u l e s , FORM can be thought of as a c o n s t r u c t i o n (known as a coercend) to which the c o e r c i o n s apply. For ease of d e s c r i p t i o n , a pseudo c o e r c i o n ••hipping*' has been invented to e x p l a i n the t r a n s f o r m a t i o n s on MODES th a t take p l a c e i n the f o l l o w i n g r u l e s : {5.5.2} s t r o n g MOID NEST s k i p : s k i p token. {3.3.1.d} s t r o n g ROWS of MODE NEST c o l l a t e r a l c l a u s e : EMPTY PACK. {5.2.4} strong r e f e r e n c e to MOST n i h i l : n i l token. {5.4.4} s t r o n g MOID NEST jump: goto token o p t i o n . 58 l a b e l NEST a p p l i e d i d e n t i f i e r with TAG. I t i s a l s o u s e f u l to d i s t i n g u i s h between the two forms of rowing t h a t may occur. The c o e r c i o n " r e f - r o w i n g " i s t h a t which takes p l a c e when the "REFETY" i n the f o l l o w i n g r u l e i s " r e f t o " : {6.6} rowed to REFETY ROWS 1 of MODE FORM: where <R0WS1> i s <row>, STRONG REFLEXETY MODE FORM, where <REFETY> i s d e r i v e d from <REFLEXETY>; where <R0WS1> i s <row R0WS2>, STRONG REFLEXETY R0WS2 of MODE FORM, where <REFETY> i s d e r i v e d from <REFLEXETY>; The f o l l o w i n g t a b l e i s a summary of what we c o n s i d e r to be c o e r c i o n s : i 1 1 1 » : i | s t r o n g | f i r m J meek | weak j s o f t | Jvoid |unite |dereference|dereference|deprocedure j widen |+ a l l meek |deprocedure| ( r e s t r i c t ) | Jhip J c o e r c i o n s | I deprocedure| I row | | | | jref-row I I I I 1+ a l l f i r m I I I 1 j c o e r c i o n s j j | | I L L 1 1 J T a b l e 6.1. Coercion The next t a b l e i l l u s t r a t e s where i n the program the c o e r c i o n s of a p a r t i c u l a r s o r t are i n i t i a t e d : 59 | strong j . assignation| (rhs) actual parameter routine cast i d e n t i t y declaration I firm monadic formula dyadic formula meek I | c a l l I |bound I |integral |choice I |boolean |choice I |UNITED Ichoice -X I weak s l i c e selection I - 4 -sof t | assignation| (lhs) i d e n t i t y r e l a t i o n Table 6.2. Coercion Contexts 6.2. The Zosel Strong-Firm Coercion algorithm The Zosel algorithm [12] for strong and firm coercion i s described by Peck [5]. This description, and the included model (together with the improved model of Kwan [4]) were used as a basis for the Vancouver implementation. Peck describes the problem of coercion as a problem of finding a path ("coercion sequence") through a graph from one node ("the a p r i o r i mode") to another ("the a p o s t e r i o r i mode"). This graph has as i t s nodes the modes of the program, and as i t s arcs the "coercion steps" of the language. The coercion algorithm searches down two trees in t h i s graph ("the a p o s t e r i o r i route" and "the a p r i o r i route"), which have as the i r roots the " a p o s t e r i o r i " and "a p r i o r i " modes. If 60 these two trees meet somewhere, then a coercion path has been found. If they do not, then no coercion path ex i s t s between the two modes. Harking the a p o s t e r i o r i route {•'posting") i i s done f i r s t . Then the a p r i o r i route i s followed u n t i l a marked node i s encountered. The coercion path can then be e a s i l y picked up, since a marked node always contains a li n k back to i t s parent in the tree. jDroc coerce= (int sort, ref md a p r i o r i , apost,ref cs c)bool: begin md m; bool can coerce:=false; post(sort,apost); m:=apriori; a: i f f l a g [ c l a s s of m] then can coerce:=true; f i n i s h i f modetype of i = proc then l i n k of m:=submode of m; coercion of m:=deproc; m:=submode of m; goto a . I i ; i f modetype of m=ref then l i n k of m:=submode of m; coercion of m:=deref; m:=submode of m; goto a f i ; f i n i s h : ' i f can coerce then c:=buildcoercionseq ( a p r i o r i , apost) , I i ; can coerce end firoc post= (int s o r t , r e f md apost)void: begin md a,b; case sort in # firm # i f apost-*= void then , f l a g [ c l a s s of apost]:=true f i ; i f modetype of apost=united then for i to numberofsubmodes of apost re£ 61 a:= (submode of apost) [ i ] ; i f a-«= void then f l a g ! class of a]: = true; coercion of a:=uniting; l i n k of a:=apost I i ; jjer f±7 •strong # i f apost=L compl then flag[L compl ]:=flag[L r e a l ]: = f lag[L i n t ] : = true; coercion of L real:=coercion of L int:=widening; link of L int:=L r e a l ; l i n k of L real:=L compl e l s f apost=L r e a l then flag[L r e a l ]:=f lag[ L i n t ] : = true; coercion of L i n t : = widening; l i n k of L int:=L r e a l e l s f apost=rowof bool then flag[rowof bool ]:=£lag[L bits]:=true; coercion of L b i t s : = widening; li n k of L bits:=rowof bool e l s f apost=rowof char then flag[rowof char ]: = f lag£L bytes ]: = true; coercion of L bytes:=widening lin k of L bytes:=rowof char e l s f modetype of apost=united then post (f irm,apost) e l s f modetype of apost=row or modetype of apost=rowof then f l a g [ c l a s s of apost ]: = true; a:=submode of apost; coercion of a:=rowing; l i n k of a:=apost; post (strong,a) e l s f modetype of apost=ref then f l a g [ c l a s s of apost ]: = true; a: = submode of apost; i f modetype of a=row or modetype of a=rowof then b:=refsubmode of a; fl a g [ c l a s s of b ]:=true; coercion of b: = refrowing; l i n k of b: = apost; post (strong,b) f i f i esac end 6.3. Heek, Weak, and Soft Coercion Soft coercion involves deproceduring a given mode u n t i l a reference to mode i s found: 62 p_roc s o f t coerce= (ref md a p r i o r i , a p o s t , r e f c s c) b o o l : begin md m; a p o s t : = p r i o r i ; while modetype of apost=procedure do begin m:=submode of apost; l i n k of apost:=m; c o e r c i o n of apost:=deproc; apost:=m end; i f modetype of apost=reference then c : = b u i l d c o e r c i o n s e g ( a p r i o r i , a p o s t ) ; t rue e l s e f a l s e f i end For weak c o e r c i o n , the g i v e n mode i s deproced and dereferencedured as long as p o s s i b l e . The r e s u l t i n g mode should be of a given type ( e i t h e r row, rowof, or s t r u c t u r e d ) or r e f e r e n c e to t h i s given type: jjroc weak coerce= (ref md a p r i o r i , apost, i n t t , r e f cs c ) b o o l : begin md m; a: a p o s t : = a p r i o r i ; while modetype of apost=procedure do begin m:=submode of apost; l i n k of apost:=m; c o e r c i o n of apost:=deproc; apost:=m end; i f modetype of apost=reference then while m:=submode of apost; modetype of m=reference do begin l i n k of apost:=m; c o e r c i o n of apost:=deref; apost:=m end; e l s e ra:=apost Hi ; i f modetype of m=procedure then goto a f i ; 63 i f modetype of m=t then c : = b u i l d c o e r c i o n s e g ( a p r i o r i , a p o s t ) ; t r u e e l s e f a l s e f i end There are two types of meek c o e r c i o n : one i n which the a p o s t e r i o r i mode i s g i v e n , and one i n which i t i s known th a t the a p o s t e r i o r i mode i s e i t h e r of type union or of type procedure with parameters. In e i t h e r case, the g i v e n mode i s dereferenced or deprocedured as long as p o s s i b l e : jaroc coerce meek unknown= (ref md a p r i o r i , apost, i n t type, r e f cs c ) b o o l : begin md m; i n t t ; a p o s t : = a p r i o r i ; while t:=modetype of apost; t=reference or t=procedure m:=submode of apost; l i n k of apost:=m; c o e r c i o n of apost:= ( t = r e f e r e n c e | d e r e f \ d e p r o c ) ; apost:=m i f modetype of apost=type then c : = b u i l d c o e r c i o n s e g ( a p r i o r i , a p o s t ) ; t r u e e l s e f a l s e f i end _proc coerce meek known= (ref md a p r i o r i , apost, r e f c s c ) b o o l : begin md m,a; i n t t ; a : = a p r i o r i ; while t:=modetype of a; t=reference or t=procedure rep_ ra:=submode of a; l i n k of a:=m; c o e r c i o n of a:= (t=reference|deref|deproc) ; a: = m i f a=apost then c : = b u i l d c o e r c i o n s e q ( a p r i o r i , a p o s t ) ; t r u e e l s e f a l s e 64 f i end 6.4. Examples of Coercion Paths Some examples of the a p o s t e r i o r i and a p r i o r i t r e e s through the mode t a b l e f o l l o w . The method of i l l u s t r a t i n g these t r e e s and the f i r s t example are adapted from Peck [ 5 ] . The f i r s t example shows the lengthen i n g c o e r c i o n s (rowing and u n i t i n g ) i n the a p o s t e r i o r i t r e e , and the s h o r t e n i n g c o e r c i o n s ( d e r e f e r e n c i n g and deproceduring) i n the a p r i o r i t r e e . The t r e e s meet at the mode i n t : a p o s t e r i o r i mode: [ ] union ( i n t , r e a l ) a p r i o r i mode: proc r e f i n t a p o s t e r i o r i t r e e : [ l u n i o n ( i n t , r e a l ) I | (rowing) I u n i o n ( i n t , r e a l ) r__I L , | I ( u n i t i n g ) I I i n t r e a l a p r i o r i t r e e : proc r e f i n t I | (deproceduring) I r e f i n t 1 (dereferencing) 65 I i n t Figure 6.2 The following example shows the neccessity for the "reverse r a v e l l i n g " of united modes. "Reverse r a v e l l i n g " consists of placing pointers i n a united mode to a l l other united modes i n the program whose submodes are a subset of the given united mode. For example, a pointer to union (int,real) would be placed i n the mode union (int,real,bool During the posting part of coercion, t h i s pointer i s needed i n order to fl a g iJ£i2£ (i£t#real) when the a p o s t e r i o r i mode i s union(int,real,bool): a p o s t e r i o r i mode: union(int,real,bool) a p r i o r i mode: ref union(int,real) a p o s t e r i o r i tree: union (int,real,bool) . 1 .j | | 1 | (unitxng) I I I I i n t r e a l bool union (int,real) a p r i o r i tree: ref union (int,real) I | (dereferencing) I union(int,real) Figure 6.3 This example i l l u s t r a t e s the (somewhat strange) coercion "ref-rowing". Note also i n t h i s example that the a p r i o r i tree 66 i s o n l y f o l l o w e d u n t i l a f l a g g e d mode i s found, even though the mode r e f r e a l can s t i l l be "de r e f e r e n c e d " . a p o s t e r i o r i mode: r e f [,] r e a l a p r i o r i mode: r e f r e f r e a l a p o s t e r i o r i t r e e : a p r i o r i t r e e : r e f [,] r e a l I 1 (ref-rowing) I r e f [ ] r e a l I 1 (ref-rowing) I r e f r e a l r e f r e f r e a l T | (dereferencing) I r e f r e a l F i g u r e 6.4 6.5. Lengthening and Shortening The authors and e d i t o r s of ALGOL 68 have put much e f f o r t i n t o a l l o w i n g a programmer to write v a r i o u s c o n s t r u c t i o n s as b r i e f l y as p o s s i b l e . For example, the c o n d i t i o n a l c l a u s e «if x>0 then x e l s e 0 fi« cou l d a l s o be w r i t t e n as •(x>0|x|0)«, and the s e r i a l c l a u s e •begin i n t i ; read (i) ; i=0 end» c o u l d be w r i t t e n as • ( i n t i ; r e a d ( i ) ; i=0)«. Coercions are another mechanism t h a t a l l o w s the programmer to write h i s program 67 b r i e f l y . •rea1 x: = r e a l ( i ) • may be w r i t t e n u r e a l x:=i«. Why the programmer cannot a l s o w r i t e : •long r e a l x: = 1« i n s t e a d of "lon g r e a l x:=long 1«, or • T1:99 l s h o r t i n t a= (1,..,,99)• i n s t e a d of •[1:99 ]short i n t a= (short 1,,..,short 99) •, or s h o r t i n t s; f o r i to n do s+:=i; i n s t e a d of • s h o r t i n t s; f o r i to n do s+:=shorten i« i s one of the g r e a t e s t s u r p r i s e s i n the language. These c o n s t r u c t i o n s c o u l d be allowed i f the two c o e r c i o n s lengonening and s h o r t e n i n g were i n c l u d e d i n the language. The j u s t i f i c a t i o n f o r e x c l u d i n g them i s a p o s s i b l e , undesired l o s s of p r e c i s i o n when an unknowing programmer w r i t e s such as • long r e a l xz-2.1• when he should have w r i t t e n • long r e a l x:=long 2.1«. Another i s some p o s s i b l e a m b i g u i t i e s t h a t may a r i s e e.g., •+ i f t r u e then 1 e l s e long 1 fi». The Vancouver implementation a l l o w s these c o e r c i o n s , but warns the programmer that they are not i n the language, and t h a t they may r e s u l t i n a l o s s of p r e c i s i o n . The l e n g t h e n i n g and s h o r t e n i n g c o e r c i o n s are onl y allowed i n a str o n g p o s i t i o n and are r e s t r i c t e d i n the f o l l o w i n g ways: 1. No l e n g t h e n i n g or s h o r t e n i n g may f e l l o w widening. 2. No s h o r t e n i n g may f o l l o w l e n g t h e n i n g . 3. No lengthe n i n g may f o l l o w s h o r t e n i n g . These r e s t r i c t i o n s e l i m i n a t e ambiguous c o e r c i o n paths and 68 guarantee maximum p r e c i s i o n i n the c o e r c i o n . For example, the path: i n t — 1 — > l o n c [ i n t — w — > l o n g r e a l i s allowed, but the path i n t — w — > r e a l — 1 — > l o n g r e a l i s not, s i n c e the lengthening c o e r c i o n f o l l o w s the widening c o e r c i o n . The l a t t e r path i s l e s s d e s i r a b l e , s i n c e p r e c i s i o n may be l o s t due to of the i n e x a c t r e p r e s e n t a t i o n of a f l o a t i n g p o i n t number i n a computer. The lengthening and s h o r t e n i n g c o e r c i o n s i n the Vancouver compiler are implemented i n a manner suggested by the f o l l o w i n g r u l e s : STRONG:: FIRM; widened t o ; rowed t o ; voided t o ; shortened t o ; lengthened t o . SLEEK::MEEK; shortened t o ; lengthened t o . widened t o SIZETY r e a l FORM: SLEEK SIZETY i n t e g r a l FORM, widened to SIZETY s t r u c t u r e d with l e t t e r r l e t t e r e has SIZETY r e a l f i e l d l e t t e r i l e t t e r m has SIZETY r e a l f i e l d FORM: SLEEK SIZETY r e a l FORM; widened t o SIZETY r e a l FORM, lengthened to MODE FORM: where <MODE> i s <long M0DE1>, lengthened to M0DE1 FORM or a l t e r n a t i v e l y MEEK M0DE1 FORM; unle s s MODE begins with l o n g , lengthened to s h o r t MODE FORM or a l t e r n a t i v e l y MEEK s h o r t MODE FORM, shortened to MODE FORM: where <MODE> i s <short M0DE1>, 69 shortened t o M0DE1 FORM or a l t e r n a t i v e l y MEEK MODE 1 FORM; un l e s s MODE begins with s h o r t , shortened to long MODE FORM or a l t e r n a t i v e l y MEEK long MODE FORM. i 70 C o n c l u s i o n T h i s t h e s i s has d i s c u s s e d some problems of co m p i l i n g ALGOL 68 programs t h a t are concerned with c o e r c i o n , b a l a n c i n g and operator i d e n t i f i c a t i o n . S o l u t i o n s that are being used s u c c e s s f u l l y i n the Vancouver compiler were presented. The purpose and nature of a data s t r u c t u r e c a l l e d ' t h e Program Tree was e x p l a i n e d . A b r e i f d i s c u s s i o n of how the Program Tree i s b u i l t was followed by a d e t a i l e d e x p l a n a t i o n of how the i d e n t i f i c a t i o n and mode checking r o u t i n e s of an ALGOL 68 compiler i n t e r a c t with i t . ' The h i s t o r y of b a l a n c i n g was t r a c e d , and a general method of b a l a n c i n g (any SORT) was given and shown to be c o r r e c t . The c o e r c i o n models of Peck and Kwan were adapted so t h a t they can be used i n an ALGOL 68 compiler. Some extended c o e r c i o n s were implemented t h a t may ease some of the w r i t i n g burden o f f the programmer. 7 1 B i b l i o g r a p h y [ I ] WBssner, H. On i d e n t i f i c a t i o n of o p e r a t o r s i n ALGOL 68, ALGOL 68 Implementation, Peck (Ed.), North-holland P u b l i s h i n g Company, Amsterdam, 1971, pp. 111-1189 [ 2 ] van wijngaarden, A., M a i l l o u x , B. J . , Peck, J . E. L., and Koster, C. H. A. Report on the a l g o r i t h m i c language ALGOL 68, Mathematisch Centrum, MR101, Amsterdam, Oct., 1969, and Numerische Mathematik, 14, 1969. [ 3 ] S c h e i d i g , H. Anpassungsoperationen i n ALGOL 68, Technischen Hochschule MUnchen, 1970. Pp 54-56. [ 4 ] Kwan, Ying T h e s i s , U n i v e r s i t y of B r i t i s h Columbia, Vancouver, 1972. [ 5 ] Peck, J . E. L. Some ste p s i n co m p i l i n g ALGOL 68, G e s e l l s c h a f t f l l r I n f o r matik, B e r i c h t Nr. 4, Saarbrllcken, 7-9 March, 1972. [ 6 ] S c h e i d i g , H. Coercions and operator i d e n t i f i c a t i o n i n ALGOL 68, A paper presented at an i n f o r m a l ALGOL 68 implementors conference, Vancouver, J u l y , 1972. [ 7 ] Lindsey, C. H. (Ed.) Report on Considered Improvements to ALGOL 68, IFIP Working Group 2.1, A l g o l B u l l e t i n No. 34, Manchester, 1972. [ 8 ] Lindsey, C. H. (Ed.) F u r t h e r Report On Improvements to ALGOL 68, IFIP Working Group 2.1, A l g o l B u l l e n t i n No. 35, Manchester, 1972. [ 9 ] Boom, H. Note on c o e r c i o n i n ALGOL 68, A p r e s e n t a t i o n made a t an i n f o r m a l ALGOL 68 implementers conference, Edmonton, June 1973. [10] Ramer, D. C o n s t r u c t i o n of LR (k) P a r s e r s with a p p l i c a t i o n to ALGOL 68, U n i v e r s i t y of B r i t i s h Columbia, September, 1973. [ I I ] Ramer, D., Manis, V. A User's Guide to ALGOL 68, U n i v e r s i t y of B r i t i s h Columbia, Vancouver, 1973. [12] Z o s e l , M. A formal grammer f o r the r e p r e s e n t a t i o n of modes and i t s a p p l i c a t i o n to ALGOL 68, U n i v e r s i t y of Washington, October, 1971. 72 Appendix 1. Sample Runs A number of program examples showing the program t r e e a f t e r the mode checking pass f o l l o w . The c o e r c i o n sequences that are a s s o c i a t e d with a program t r e e node can be seen. A l s o i t can be seen t h a t o p e r a t o r s and i d e n t i f i e r s have been - i d e n t i f i e d . The output has been taken d i r e c t l y from the compiler and squashed so t h a t i t w i l l f i t on one page. U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE COORD COUNT CRRL 0 1 4 5 6 1 'PR LIST,AMS,dartmouth,pass(4,3) jar begirt # SOFT COERCION AND BALANCING # mode a = joroc r e f i n t ; a x = s k i p ; a y,z; case 0 i n Z , #~DEREFERENCED, DEPROCEDURED # X, f DEPROCEDURED # y # DEREFERENCED, DEPROCEDURED I out s k i n # HIPPED # esac:= ~x:=1 # ASSIGNATION IS DEREFERENCED end 0.48 SECONDS FOR~PASS 1 0.01 SECONDS FOR PASS 2 PARSE SUCCESSFUL 0.34 SECONDS FOR PASS 3 PROGRAM TREE: |SERIAL CLAUSE J DECLARATION PROLOGUE |MODE DECLARATION I A | MODE 98 |TAG DECLARATION LIST |TAG DECLARATION | MODE 98 I X | SKIP ICOERCION SEQUENCE: |TAG DECLARATION LIST |TAG DECLARATION |MODE 99 I * |TAG DECLARATION |MODE 99 IZ HIP, TO MODE 98 | ASSIGNATION ICOERCION SEQUENCE: JCASE CLAUSE |DENOTATION ICOERCION I |UNIT LIST VOID, TO MODE 18 SEQUENCE: 0 74 U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE 2 | TAG ICOERCION SEQUENCE: DEREF, DEPROC, TO MODE 23 |TAG DECLARATION |MODE 99 |Z | TAG jCOERCION SEQUENCE: DEPROC, TO MODE 23 |TAG DECLARATION |MODE 98 | X | SKIP |COERCION SEQUENCE: HIP, TO MODE 20 | TAG ICOERCION SEQUENCE: DEREF, DEPROC, TO MODE 23 |TAG DECLARATION |MODE 99 |Y JSKIP ICOERCION SEQUENCE: HIP, TO MODE 20 |ASSIGNATION |COERCION SEQUENCE: DEREF, TO MODE 1 | TAG |COERCION SEQUENCE: DEPROC, TO MODE 23 |TAG DECLARATION |MODE 98 I X | SKIP ICOERCION SEQUENCE: HIP, TO MODE 98 |DENOTATION |COERCION SEQUENCE: I 1 0.48 SECONDS FOR PASS 4 0.00 SECONDS FOR PASS 5 1.31 SECONDS FOR TOTAL COMPILATION(S) 75 0 B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE COORD COUNT 0 CRRL 0 1 3 4 5 8 * 9 10 13 1 * PR LIST,AMS, d a r t mouth, pass (4,3) jar begin # WEAK COERCION AND BALANCING # # SLICES # (/1:2/) r e a l x; (/1:2/) r e a l y-ski£; case 0 i n X, # DEREFERENCE # y, # NO COERCION # (1,2) # WIDEN 1 AND 2 # out ski£ # HIP # esac(/ 1 : 2 / ) ; # STRUCTURES # s t r u c t ( r e a l i,j)a=ski£; i of case 0 i n a, # NO COERCION # (1,2) # WIDEN 1 AND 2 # out skijD # HIP # esac end 0.42 SECONDS FOR PASS 1 0.02 SECONDS FOR PASS 2 PARSE SUCCESSFUL 0.33 SECONDS FOR PASS 3 PROGRAM TREE: JSERIAL CLAUSE |DECLARATION PROLOGUE |TAG DECLARATION LIST |TAG DECLARATION |MODE 99 IX |TAG DECLARATION LIST |TAG DECLARATION |MODE 100 I* | SKIP |COERCION SEQUENCE: HIP, |SERIES WITH DEFS | SLICE |COERCION SEQUENCE: VOID, |CASE CLAUSE I DENOTATION TO MODE 100 TO MODE 18 U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE I 0 | UNIT LIST | TAG |COERCION SEQUENCE: DEREF, TO MODE 100 |TAG DECLARATION |MODE 99 I X | TAG ICOERCION SEQUENCE: |TAG DECLARATION |MODE 100 I Y | SKIP ICOERCION SEQUENCE: HIP, TO MODE 100 |COLLATERAL CLAUSE |DENOTATION |COERCION SEQUENCE: WIDEN, TO MODE 3 I 1 |DENOTATION ICOERCION SEQUENCE: WIDEN, TO MODE 3 I 2 | SKIP ICOERCION SEQUENCE: HIP, TO MODE 100 |TRIMSCRIPT LIST JTRIMSCRIPT |DENOTATION ICOERCION SEQUENCE: I 1 | DENOTATION ICOERCION SEQUENCE: I 2 |TAG DECLARATION LIST |TAG DECLARATION |MODE 102 |A | SKIP |COERCION SEQUENCE: HIP, TO MODE 102 |SELECTION ICOERCION SEQUENCE: VOID, TO MODE 18 |CASE CLAUSE |DENOTATION ICOERCION SEQUENCE: I 0 J UNIT LIST | TAG |COERCION SEQUENCE: |TAG DECLARATION |MODE 102 77 0 B C ALGOL 68 V COMPILES 13:30:14 17 JUL 1973 PAGE 3 I A | SKIP |COERCION SEQUENCE: HIP, TO MODE 102 JCOLLATERAL CLAUSE |DENOTATION |COERCION SEQUENCE: WIDEN, TO MODE 3 I 1 |DENOTATION |COERCION SEQUENCE: WIDEN, TO MODE 3 I 2 I S K I P |COERCION SEQUENCE: HIP, TO MODE 102 0.49 SECONDS FOR PASS 4 0.00 SECONDS FOR PASS 5 1.26 SECONDS FOR TOTAL COMPILATION (S) i 78 0 B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE 1 COORD CRRL COUNT 0 0 |*PR LIST,AMS,dartmouth,pass(4,3) £V I begin 1 | # FIRM COERCION, OPERATOR IDENTIFICATION # I i n t x , r e a l y; 2 . J case 0 i n 3 | ~ X, # DEREFERENCE, WIDEN # 3 . | y, # DEREFERENCE # 4 | 1 # WIDEN # • • I out 4 | s k i p # HIP # | esac + # IDENTIFY OP (REAL,REAL)REAL # 1 | i f t r u e then 6 | 1.0 # NO~COERCION # I e l s e 7 I s k i p # HIP # I I i 1 lend 0.48 SECONDS FOR PASS 1 0.01 SECONDS FOR PASS 2 PARSE SUCCESSFUL 0.29 SECONDS FOR PASS 3 PROGRAM TREE: |SERIAL CLAUSE |DECLARATION LIST |TAG DECLARATION LIST |TAG DECLARATION |MODE 23 IX |TAG DECLARATION LIST |TAG DECLARATION |MODE 25 |Y (DYADIC FORMULA ICOERCION SEQUENCE: VOID, TO MODE 18 |OP DECLARATION |MODE 3 |MODE 3 |MODE 3 I * |CASE CLAUSE |DENOTATION ICOERCION SEQUENCE: I 0 |UNIT LIST 79 U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE | TAG j COERCION SEQUENCE: DEREF, WIDEN, TO MODE |TAG DECLARATION |MODE 23 I X | | TAG ICOERCION SEQUENCE: DEREF, TO MODE 3 |TAG DECLARATION |MODE 25 I * |DENOTATION ICOERCION SEQUENCE: WIDEN, TO MODE 3 I 1 |SKIP |COERCION SEQUENCE: HIP, TO MODE 20 |CONDITIONAL CLAUSE |DENOTATION ICOERCION SEQUENCE: | TRUE |DENOTATION |COERCION SEQUENCE: |+0.100000000000000e+01 ISKIP ICOERCION SEQUENCE: HIP, TO MODE 3 0.49 SECONDS FOR PASS 4 0.00 SECONDS FOR PASS 5 1.27 SECONDS FOR TOTAL COMPILATION(S) U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE 1 COORD CRRL COUNT 0 0 I 'PR LIST,AMS,dartmouth £r begin 1 |~ ft IDENTIFICATION ERRORS # # UNDEFINED IDENTIFIER # ale p h ; # MULTIPLY DEFINED IDENTIFIER # i n t i ; r e a l i ; # UNDEFINED OPERATOR # + bo o l (skijD) ; # VIOLATION OF DRESDEN 2 # o£ + = (ref i n t a) i n t : s k i j j ; +1; # UNDEFINED FIELD SELECTOR # s t r u c t ( i n t i , j) x; k of x; s k i p end 0.44 SECONDS FOR PASS 1 0.02 SECONDS FOR PASS 2 <ERROR: 302><SEV:9> 2 1 THE IDENTIFIER «I» IS MULTIPLY DEFINED. I THE FIRST DEFINITION IS USED. PARSE SUCCESSFUL 0.43 SECONDS FOR PASS 3 <ERROR: 401><SEV:8XCOOR:0XCRRL:1> THE IDENTIFIER * ALEPH * IS UNDEFINED. <ERROR: 402XSEV:8XCOOR:3XCRRL:1> THE OPERATOR • + • IS UNDEFINED. <ERROR: 430XSEV:8XCOOR:5XCRRL: 1> THE OPERATOR » + » CANNOT BE IDENTIFIED, SINCE THE DRESDEN CONDITION IS VIOLATED. <ERROR: 403XSEV:8XCOOR:8XCRRL: 1> 'K OF X» IS AN INVALID SINCE SELECTION, SINCE THERE IS NO FIELD SELECTOR »K' IN *REF STRUCT(INT I,INT J)». 0.07 SECONDS FOR PASS 4 0.96 SECONDS FOR TOTAL COMPILATION (S) U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE 1 COORD COUNT CRRL 0 0 | 'PR LIST,AMS,dartmouth pr begin 1 f #~BALANCING ERRORS # # SOFT # i n t i ; (1|i:=1,1): = 2; # WEAK TO ROW # (/1:6/)int a; (truej a| 1.0) (/1/) ; # WEAK TO STRUCTURE # s t r u c t ( i n t i , j) x ; i of (truej xl 1) ; # MEEK TO BOOL # i f . (true!1|skip) then s k i p f i ; # MEEK TO UNITED # £^se (true 11 1 skip) i n ( i n t h ) : 1 , ( r e a l i ) :2 esac; s k i p end 0.41 SECONDS FOR~PASS 1 0.02 SECONDS FOR PASS 2 PARSE SUCCESSFUL 0.36 SECONDS FOR PASS 3 <ERROR : 406XSEV:8XCOOR:2XCRRL: 1> THESE MODES OF ' AN ASSIGNATION CANNOT BE BALANCED TO A 'REF*: »INT« (FROM »1«) •REF INT» (FROM »I:=1 f) •SKIP' (FROM 'SKIPM <ERROR: 407XSEV:8XCOOR:4XCRRL: 1> INVALID SLICE. THESE MODES CANNOT BE WEAKLY BALANCED TO A ROW: • REAL * (FROM ' + 1.0') • REF ()INT» (FROM «A») <ERROR: 408XSEV:8XCOOR:7XCRRL:1> THESE MODES CANNOT BE WEAKLY BALANCED TO A STRUCTURE: •INT" (FROM • 1 ') •REF STRUCT (INT I,INT J) • (FROM «X f) <ERROR: 410XSEV:8XCOOR:8XCRRL:1> THESE MODES CANNOT BE MEEKLY BALANCED TO 'BOOL*: 'SKIP• (FROM 'SKIP') •INT' (FROM '1') <ERROR: 41 1XSEV:8XCOOR:9XCRRL:1> THESE MODES CANNOT BE MEEKLY BALANCED TO A UNION: •SKIP' (FROM 'SKIP') 82 U B C ALGOL 68 V COMPILES 13:30:14 17 JUL 1973 PAGE •INT' (FROM '1') 0.19 SECONDS FOR PASS 4 0.00 SECONDS FOR PASS 5 0.98 SECONDS FOR TOTAL COMPILATION(S) < U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE 1 COORD COUNT 0 1 CRRL 0 1 •PR LIST,AMS,dartmouth jar begin # COERCION ERRORS # # INVALID CALL OR SLICE # s t r u c t ( i n t i , j ) x; x(1); # INCORRECT DISPLAY # i n t e; e:= (1,2); # INVALID STRONG COERCION # i n t b; b:=1.0; # INVALID WEAK COERCION # (1:10)int a; i of a; (x:= (10,1) ) (/1/) ; skija end 0.45 SECONDS FOR PASS 1 0.02 SECONDS FOR PASS 2 PARSE SUCCESSFUL 0.30 SECONDS FOR PASS 3 <ERROR: 404XSEV:8XCOOR:2XCRRL:1> »X' CANNOT BE THE PRIMARY OF A CALL OR SLICE, SINCE IT IS OF MODE 'REF STRUCT (INT I,INT J) <ERROR: 426XSEV:8XCOOR:4XCRRL: 1> THE DISPLAY '(1,2)' CANNOT BE OF MODE »INT». <ERROR: 416XSEV:8XCOOR:7XCRRL: 1> '+1.0' (OF MODE 'REAL') CANNOT BE STRONGLY COERCED TO 'INT', <ERROR : 4 18XSEV: 8XCOOR : 9XCRRL: 1 > 'A' CANNOT BE THE SECONDARY OF A SELECTION, SINCE ITS MODE, • REF ()INT', CANNOT BE WEAKLY COERCED TO A STRUCTURE. <ERROR: 419XSEV: 8XCOOR ; 11XCRRL: 1 > 'X:=(10,1)' CANNOT BE THE PRIMARY OF A SLICE, SINCE ITS MODE, 'REF STRUCT (INT I,INT J ) ' , CANNOT BE WEAKLY COERCED TO A ROW. 0.17 SECONDS FOR PASS 4 0.00 SECONDS FOR PASS 5 0.94 SECONDS FOR TOTAL COMPILATION(S) 84 U B C ALGOL 68 V COMPILER 13:30:14 17 JUL 1973 PAGE COORD CRRL COUNT . 0 0 1 7 11 16 •PR LIST,AMS,dartmouth pr begin # BAD COUNTS # # INCORRECT NUMBER OF ARGUMENTS # proc p = ( r e a l u, v) v o i d : s k i p ; p(1,2,3); # INCORRECT NUMBER OF TRIMSCRIPTS # (/1:2,3:4/) i n t d=skip; d(/1:2/); d (/1:2,3:4,5:6/) ; # INCORRECT DISPLAY LENGTH # s t r u c t ( i n t i , j ) x; x:=(1,2,3); s k i p end 0,38 SECONDS FOR PASS 1 0.01 SECONDS FOR PASS 2 PARSE SUCCESSFUL 0.29 SECONDS FOR PASS 3 <ERROR: 421><SEV:8XCOOR:2XCRRL:1> THE CALL •P(1,2,3)« HAS AN INCORRECT NUMBER OF ACTUAL PARAMETERS. <ERROR : 423XSEV: 8XCOOR:7XCRRL: 1> THERE ARE TOO FEW TRIMSCRIPTS IN THE SLICE '0(1:2)». <ERROR: 422XSEV:8XCOOR:8XCRRL: 1> THERE ARE TOO MANY TRIMSCRIPTS IN THE SLICE 'D (1:2,3:4,5:6) ', <ERROR: 427XSEV:8XCOOR:13XCRRL: 1> THE STRUCTURE DISPLAY •(1,2,3)' HAS AN INCORRECT NUMBER OF FIELDS. 0.19 SECONDS FOR PASS 4 0.00 SECONDS FOR PASS 5 0.87 SECONDS FOR TOTAL COMPILATION (S) D B C ALGOL 68 V COMPILES 13:30:14 17 JUL 1973 PAGE COORD CRRL COUNT 3 5 8 11 15 0.36 0.02 PARSE 0.35 <ERROR 0 1 1 end SECONDS FOR PASS SECONDS FOR PASS SUCCESSFUL SECONDS FOR PASS 'PR LIST,AMS,dartmouth £r begin # ERROR RECOVERY # i n t i=sjcij); (1:3) r e a l y; i n t z=2; i:= ( s k i r j y (/1.2/)"| z:=2) ; # LIMIT ERROR MESSAGES # (1:10)int a:= (1.0,2.0,3.0, 4.0,5.0,6.0, 7.0,8.0,9.0,10.0) ; s k i p 417XSEV:8XCOOR:3XCRRL: 1> »I» CANNOT BE ON THE LEFT HAND SIDE OF AN ASSIGNATION, SINCE ITS MODE, * INT *, DOES NOT BEGIN WITH * REF 1 <ERROR: 415XSEV:8XCOOR:3XCRRL: 1> CANNOT BE MEEKLY COERCED TO 'BOOL'. •SKIP' (OF MODE 'SKIP') <ERROR: 422XSEV:8XCOOR:3XCRRL: 1> THERE ARE TOO MANY TRIMSCRIPTS IN THE SLICE 'Y(1,2) '. <ERROR: 417XSEV:8XCOOR:4XCRRL: 1> 'Z' CANNOT BE ON THE LEFT HAND SIDE OF AN ASSIGNATION, SINCE ITS MODE, 'INT', DOES NOT BEGIN WITH 'REF <ERROR: 416XSEV:8XCOOR:4XCRRL: 1> •+1.0« (OF MODE 'REAL •) CANNOT BE STRONGLY COERCED TO 'INT'. <ERROR: 416XSEV:8XCOOR:5XCRRL:1> «+2.0» (OF MODE 'REAL') CANNOT BE STRONGLY COERCED TO 'INT'. <ERROR: 416XSEV:8XCOOR:6XCRRL: 1> ' + 3.0' (OF MODE 'REAL') CANNOT BE STRONGLY COERCED TO * INT *. <NOTEXSEV:0XCOOR:15XCRRL: 1> THE PREVIOUS ERROR HAS OCCURRED 7 MORE TIMES. 0.32 SECONDS FOR PASS 4 0.00 SECONDS FOR PASS 5 1.05 SECONDS FOR TOTAL COMPILATION(S) 86 Appendix 2. Program Tree Bodes The following are a l l of the program tree nodes that may be b u i l t . The grammar from which they are derived i s given i n [ 1 0 ] , Declarer. 1 Temporary —I | temp | 1 h I dn | mn [ cw | h | L ) f l a g s I l i n k H I H —> >mode declaration Declarer.2 Primitive r — I i prim 1 1 1 1 V— dn 1 mn acc # 88 Declarer.3 Reference r r i I ref I 1 | | dn | mn | [ cw j h ] I x 1 | flags | | l i n k | «l • -> >submode Declarer.U Rowof —>pair l i s t or n i l —>submode —>ref submode 89 Declarer.5 Row row an 4 mn cw fla g s l i n k I 1 h I 1 I 1 I -J +-1 +-r — • | s t r i c t f l e x either | - H —H—>-—I —>pair l i s t or n i l -->submode —>ref submode Declarer.6 Union J unxon \ n | | dn | mn | I cw j h i | fla g s | j . 1 I l i n k | j ^ | • 1 — > >submode 1 V 1 I . . . I | • -J—> >submode n L 1 Declarer.7 Struct 1 1 struct 1 J. n j I 1 1 dn 1 x mn 1 1 1 1 cw I 1 1 h j 1 1 1 flags i i T 1 L l i n k 1 i ^—> >f i e l d 1 1 -I -> >field n Declarer.8 Proc Type proc dn cw f— 1 mn fl a g s l i n k -j h I I 1 --j.—> >submode 91 D e c l a r e r . 9 Procp procp | n+1 I dn | L mn 1 1 1 cw | 1 , JL,_ h 1 | f l a g s | l i n k i —1 1 . . . ~ \ 1 • — — — + — —1 I ->par mode 1 ->submode Declarer.10 F i e l d f i e l d "T-I .X- 1 dn | mn | cw | h j f l a g s | l i n k | J 1 +-->--r tag acc # j —>xref —>mode ~> r e f mode 92 Coercend.1 Routine r o u t i n e | L. "J range # | coor # | J _ > -j +—>-+ — > c o e r c i o n sequence — > f o r m a l p. p. or n i l — > u n i t mode — > n u n i t " — > r o u t i n e mode Coercend.2 A s s i g n a t i o n assig range # j coor # | . _ j , . .\—>-1 . +__>_. j ^ j — > c o e r c i o n sequence — > " t e r t i a r y " —>"unit» 93 Coercend.3 I d e n t i t y I s R e l a t i o n i d e n t i s | L. range # | coor # Y — I~ -j — > c o e r c i o n sequence — > " t e r t i a r y " 1 — > " t e r t i a r y " 2 Coercend.4 I d e n t i t y I s Not R e l a t i o n — > c o e r c i o n sequence — > " t e r t i a r y " 1 —>«tertiary" 2 Coercend.5 Cast cast -L ] range # | coor # | x 1 —I >-—I ~ + — > — ->coercion sequence ->mode of c a s t >"unit» 1 94 Coercend.6 Dyadic Formula \ formula"! 4 ~ J J. L 1 | range # | coor # | I i H—> >coercion sequence | op acc # | {—>op dec) \ • 1 H—> >left operand H H—> >right operand Coercend . 7 Monadic Formula T monadic | L-I | range # | coor I -+—> >coercion sequence r 1 | op acc # J (—>op dec) j | • -f—> >"operand" L ; J Coercend.8 Local Generator 1 loc gen 1 2 | , ~t 1 | range # \ coor # | I • .j.—> >coercion sequence | • —|—> >mode of generator Coercend.9 G l o b a l Generator | g l o gen | j. x. | range # | coor # f x : • + — > — —>coercion sequence ->mode of generator Coercend.10 S e l e c t i o n s e l e c t | -X. 4 range # | coor # | ^— tag acc # s e l e c t i o n mode -4—> >coercion sequence H I ( — > f i e l d mode) H -+—> >•'secondary" H i Coercend.11 Goto goto | range # | coor # | I J — > c o e r c i o n sequence tag acc # I (—>tag d e c l a r a t i o n ) Coercend.12 Tag r T 1 I tag | 2 | I- L 1 | range # | coor # 1 | • 4—> >coercion sequence 1 tag acc # | (—>tag d e c l a r a t i o n ) . j Coercend.13 Skip >coercion sequence Coercena.14 N i l r T — i I n i l j 1 | | range # | coor # | | • 4—> >coercion sequence L I Coercend.15 Vacuum J vacuum | 1 | | range # | coor # | I 4—> >coercion sequence Coercend.16 Known Denotation —>coercion sequence —>denotation mode Coercend.17 S l i c e | s l i c e | 4 | I J -i | range # | coor # | J" . H — > -1 1 • H — > — ->coercion sequence -> nprimary" >trimscript l i s t s l i c e mode Coercend.18 C a l i c e 1 c a l i c e | range # | coor # c a l i c e mode — > >coercion sequence — > >«»primary" — > >trimment l i s t Coercend.19 C a l l I c a l l I | range # j. coor # j -| I I y— . H — > — c a l l mode —I —>coercion sequence —>"primary" —>argument l i s t Structural.20 Label Sequence 99 r 1 | label seq| n | range # | coor # tag acc #1 h | tag acc #n Structural.21 Program I T 1 | program | 2 | | range # | coor # | I • H — > — I . - | — > — —>label seq. or n i l —>"enclosed clause 100 S t r u c t u r a l . 2 2 Loop | loop 6 l | range # | coor # l .j. | }~ I H I I j . — H >— +-->-4—>-->tag d e c l a r a t i o n ->«unit" (from) ->»unit» (by) ->"unit" (to) — > s e r i a l c l a u s e ->"unit" (do) S t r u c t u r a l . 23 Trimmer trimmer | ! L -range # | coor x H — > — -j - H — > -i >"bound M 1 or n i l ->"bound» 2 or n i l ->"bound" 3 or n i l 101 Structural.24 Pair I pair J I range # | coor | -L I- - H A — > ->',bound" 1 or n i l ->»'bound" 2 or n i l Structural.25 Parameters L i s t j par l i s t j n j Y ± A I range # | coor # | | • +—> >tag dec 1 I . . . I | • -f-—> >tag dec n Structural.26 C o l l a t e r a l Clause | c o l l c l | n | | range # j coor # | I • 4—>-j. + I . . . I —I ->"unit» 1 | • H—> >"unit" n 102 Structural.27 Conditional Clause cond c l I range # 1 coor # | 1 1 .>— -4-- > w s e r i a l clause" 1 ->"serial clause" 2 - > M s e r i a l clause" 3 Structural.28 Case Clause | case c l | 3 | j range # | coor # | I 1 1 H — > -— > s e r i a l clause a —>unit l i s t — > s e r i a l clause b j Structural.29 Conformity Case Clause ->serial clause a ->alternative l i s t — > s e r i a l clause b 103 Structural.30 Alternative I a l t e r I | j range f | coor # I , . - \ — > -Y 1 I • . , — > _ Y _ J ~>mode ->tag or n i l ->"unit" Structural.31 S e r i a l Clause | s e r i a l c l | 1 - L -1 j | range # | coor # | j. J -I I — H — > -—^  +-->-i —>declaration prologue —>parade Structural.32 Train — > u n i t seri e s 1 — > u n i t seri e s n S t r u c t u r a l . 3 3 U n i t S e r i e s 104 u n i t s e r | n j range # | coor # | H— > —->"unit" 1 -4 L » +—> >"unit" n S t r u c t u r a l . 3 4 D e c l a r a t i o n Prologue r T 1 dec p r o l | n | range # | coor # | J — > u n i t or dec l i s t 1 [—> >unit or dec l i s t n S t r u c t u r a l . 3 5 S i n g l e D e c l a r a t i o n L i s t ^ r T s. d. 1. | n V range # | coor # | • H—> >single declaration 1 r 1 . . . I . ^ • -|—> >single declaration n Structural.36 Tag L i s t 1 0 5 i ~t~ tag l i s t | n range # j coor # tag acc #1 (—> decblk 1) tag acc #n (—> decblk n) Structural.37 Trimscript L i s t t . s c . l i s t | x. n I range # | coor # > >"trimscript" 1 i ->"trimscript" n Structural.38 Trimment L i s t trim, l i s t | n | range # | coor # | x j H—> >"trimment" 1 —j » x—> >"trimment" n j Structural.39 Argument L i s t arg. l i s t | I L-n range # | coor # L — > >"argument" 1 +__>. i —Vargument" n Structural.40 Unit L i s t unit l i s t l n I range # | coor # | L , I * . « • H — > >"unit" 1 -> >"unit" n Structural.41 Alternative L i s t a l t . l i s t j n | range # | coor # | ^ —>alternative 1 —>alternative n 1 0 7 Structural.42 Parade parade | n | range # | coor # | , 1 1 H—> >train 1 — + — > -i — > t r a i n n Declaration.1 Mode Dec Type mode dec range # | coor # | ~ «- 1 • 1—>--I -+—>--mode dec acc # | 1 ->ind link ->xref link — j - — > >mode dec value i D e c l a r a t i o n . 2 Tag Dec Type tag dec | 6 Li. range # | coor # L tag dec acc # heap vs. l o c +~> > i n d l i n k > x r e f l i n k >tag dec mode -> >tag dec value j D e c l a r a t i o n . 3 Op Dec Type op dec range # op dec I 1 coor #' | acc # -4 H—>-- H —i > -1 >--I -I >-->indlink ->xref l i n k >op dec 1 mode >op dec r mode >op dec d mode >op dec value Declaration.4 Prio Dec Type i r 1 | prio dec | 4 | J. .-X .j | range # | coor # | L _ i ^ I • H—> >indlink | • H—> >xref link j. ! |p.dec.acc.| p.dec.p. | u i J Format3. 1 C o l l e c t i o n L i s t | c o l . l i s t | n | f" -»• i I range # | coor # | ,. -L J I • 4—> >"collection" 1 I . . . 1 I • 4!—> >"collection" n Format.2 C o l l e c t i o n 1 T : 1 I c o l l e c t i o n | 4 | I range # | coor # | j. x -I I • 4—-> >insertion or n i l I J I • H—> >replic or n i l I • H—> >collection l i s t or fr i n i l or c o l l e c t i o n I • -j—> >insertion or n i l 1 i 1 I 110 Format.3 Integral Pattern | i n t patt J I-I ± , \ range # | coor # | j. x -4—>-H -+—>-.J ->sign mould ->integral mould Format.4 Integral Mould i r | i n t mouldj 2 Y | range # | coor # L ^ I— —I —H—> -> >simple i n t mould >insertion Format. 5 Integral Insertion Pattern | i n t i pat| 2 | J range # | coor # | y _j -J j . J ~ . +_>_. — > i n t choice patt —>insertion Format.6 Integral Choice Pattern r T 1 |int ch pat| 2 | , j , | range # | coor # | L L H | • -4—> > insertion I • -j-—> > l i t e r a l l i s t « 1 Format.7 Sign Hould r T 1 | sign mid | 2 | j _ 1 4 | range # | coor # | J. :X j H—> >1 r zero frame j A j • 4—> >sign frame c j Format.8 Loose Replicatable Zero Frame [ 1 r z frml 2 | | range # | coor # | , x 1 | • H—> >insertion or ni i ^ | • H—> R e p l i c a t i o n 112 Format.9 Simple I n t e g r a l Mould | s i n t mid| I- u-n j -I | range # | coor # j ± L L| I • H — > -I 4 -4—>-— > 1 r s d frame 1 ->1 r s d frame n Format.10 Loose R e p l i c a t a b l e S u p p r e s s i b l e D i g i t Frame | 1 r s d f j 2 | | range # | coor # | \ > — > i n s e r t i o n — > r s d frame Format.11 R e p l i c a t a b l e S u p p r e s s i b l e D i g i t Frame j rep s d f j 2 1 range # J j coor # | •— i i •— — i i ^ r e p l i c a t i o n ->sup r frame 113 Format.12 Suppressible D i g i t Frame j sup d f r | 1 | j J. ^ | range # | coor # | j J. ^ | • -|—> >digit frame Format.13 D i g i t Frame, | dig frame) 1 | h - j . j | range # | coor # | , !4. , | l e t t e r z,u,v,d J i , i Format.11 Sign Frame I T 1 J sign f r | 1 J | L , J range # I coor # | •j, J , l • or - | i : i Format.15 L i t e r a l L i s t r l i t l i s t " T i ~ range # | coor -> > l i t e r a l 1 • -|—> > l i t e r a l n Format.16 L i t e r a l | l i t e r a l | j. x. range # | coor # h I I— I L + . -j +. -> >string denotation -> >rep l i t sequence Format. 17 Replicated L i t e r a l Sequence I— r l i t seq| 2n range # | coor # | —i -1 -) >. -I ^ r e p l i c a t i o n 1 ->string deno 1 ->replication n ->string deno n 115 Format.18 B i t s Pattern I b i t s pat | j. -X. I 1 | range # | coor # | y ± + - I — > _ . ] —>radix mould —> i n t e g r a l mould Format.19 Radix Mould | radix mld| l range # j L 2 coor 4 # I 1 H — > --1 — I — > -— ^ i n s e r t i o n — > i n t e g r a l denotation Format.20 Real Pattern | r e a l pat | 2 y -L | range # | coor j. _ J —I -> >sign mould -> >real mould 1 1 6 Format.21 Real Mould I I T | r e a l mould) 2 t j. | range # | coor # | j ± . j , • +• +__>. i — > i n t e g r a l mould — > i n t e g r a l mould Format.22 Real F r a c t i o n a l Mould i 1 1 |r f r a c mld| 2 | f- L 1 ( | range # | coor # J | • H—> > i n s e r t i o n j + j • -j—> > i n t e g r a l mould i i Format.23 F l o a t i n g P o i n t Mould [ f l pt m l d i 3 1 | range # j coor # | | • -|—> >stagnant mould I 1 | • 1—> >sign mould , j | • -|—> > i n t e g r a l mould i i Format.24 Stagnant Mould | s t a g mid | j x. I J range # | coor # | j L \ + ^ >— ->— ->sign mould - > r e a l / i n t e g r a l mould Format. 25 Boolean P a t t e r n I T~ |bool mouldj ^ -»•-I 1 | range # | coor # | L — j - ^ H — > > >simple bool pat > i n s e r t i o n Format.26 Simple Boolean P a t t e r n s b pat | I | range # I coor # | ->insertion or n i l ->boolean c h o i c e mid Format.27 Boolean Choice Mould I T 1 | b ch mid | 2 | y J. , | range # j coor # | v x , I • -|—> >true l i t e r a l y ._. ^ I •- -j—> >false l i t e r a l ». 1 Format.28 Complex P a t t e r n r T 1 | complex p| 2 | V x | range # | coor # \ j L , I * +—> >real p a t t e r n y. ^ I • H—> >real p a t t e r n Format.29 S t r i n g P a t t e r n | s t r pat | 2 | t L 1 | range # | coor # | I • H—> >pattern or f r a | • H—> > i n s e r t i o n L : j 119 Format. 30 Simple S t r i n g P a t t e r n s p l s t r p| n | range # | coor # j J. .j H — > >1 r s c f r 1 ~ j — > >i r s c f r n i Format.31 Loose R e p l i c a t a b l e S u p p r e s s i b l e Charater Frame 1 I T |1 r s c f r j 2 | | range # | coor # | I . H—>-L 1 ->insertion ->rep s ch frame Format.32 R e p l i c a t a b l e S u p p r e s s i b l e Character Frame | r s ch f r | y x. | range # | coor # | L 1 1 - > r e p l i c a t i o n ->supp ch frame 120 Format.33 Loose String Frame i r 1 | 1 s t r f r | 1 | j . 1 + | range # J coor # | j . L , I • 1—> >insertion j Format.34 Loose General Frame | 1 gen f r j 1 ] | range # j coor # | | • -j—> >insertion L : I Format.35 Insertion r T 1 | i n s e r t i o n | 2 1 j J . 1 | range # | coor # | j . J. 1 | » +—> > l i t e r a l » -j-—> >insert sequence \ 1 2 1 Format.36 Insert Sequence I-ins seq | n range # | coor I - H —+—> >insert 1 —I I -—1 —-|—> >insert n i Format.37 Insert ins e r t range # T " t coor # | -I \-I I — > — ->rep laign or n i l ->alignment or n i l - > l i t e r a l or n i l Format.38 Alignment r T r 1 I align I 1 | | range # | coor # | i 4 | l e t t e r k,x ry,l,p | i j 

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

Comment

Related Items