Revised report on the algorithmic language Algol-68

Section662 van Wijngaarden, et al.

6.5.2. Semantics

The yield W of a widened-to-MODE-FORM F is determined as follows:let V be the yield of the direct descendent of F;

Case A: MODE is some SIZETY real :

W is the real number widenable from f2.1.3.1.eg V;

Case B: MODE is some structured with SIZETY real letter r letter e SIZETY real letter i letter m mode :

W is fthe complex number which isg a structured value whose elds are respectively V and the real number 0 of the same size f2.1.3.1.bg as

V; Case C:

W is the fonlyg eld of V.

6.6.Rowing

fRowing permits the building of a multiple value from a single element.

If the latter is a name then the result of rowing may also be a name referring to that multiple value.

Example:

[ 1: 1] real b1 := 4.13 g

6.6.1. Syntax

a) rowed tof61Ag REFETY ROWS1 of MODE FORM :

where (ROWS1) is (row), STRONGf61Ag REFLEXETY MODE FORM, where (REFETY) is derived from (REFLEXETY)f531b,c,-g ;

where (ROWS1) is (row ROWS2),

STRONGf61Ag REFLEXETY ROWS2 of MODE FORM, where (REFETY) is derived from (REFLEXETY)f531b,c,-g.

fExamples:

a)4.13 (in [1: 1] real b1 := 4.13) x1 (in [ 1:1, 1: n] real b2 := x1) g

6.6.2.Semantics

a) The yield W of a rowed-to-REFETY-ROWS1-of-MODE-FORM F is determined as follows:

let V be the yield of the STRONG-FORM of F; Case A: REFETY is EMPTY :

W is the multiple value \built" fbg from V for ROWS1 ; Case B: REFETY is REF to :

If V is nil,

101

Section ALGOL 68 Revised Report 671

then W is a nil name;

otherwise, W is the name \built" fcg from V for ROWS1 .

b) The multiple value W \built" from a value V, for some ROWS1 , is determined as follows:

Case A: ROWS1 is row :W is composed of

(i)a descriptor ((1; 1)),

(ii)fone elementg V;

Case B: ROWS1 is some row ROWS2 :

let the descriptor of V be ((l1; u1); : : : ; (ln; un));

W is composed of

(i)a descriptor ((1; 1); (l1; u1); : : : ; (ln; un)),

(ii)the elements of V:

the element selected by an index (i1; : : : ; in) in V is that selected by (1, i1; : : : ; in) in W.

c)The name N1 \built" from a name N, for some ROWS1 , is determined as follows:

N1 is a name fnot necessarily newly createdg, equal in scope to N and referring to the multiple value built fbg, for ROWS1 , from the value referred to by N;

Case A: ROWS1 is row :

the fonlyg subname of N1 is N;

Case B: ROWS1 is some row ROWS2 :

the subname of N1 selected by (1, i1; : : : ; in) is the subname of N selected by (i1; : : : ; in).

6.7. Voiding

fVoiding is used to discard the yield of some unit whose primary purpose

t = int: entier(random 100); t;, the applied-identi er t is voided after a deproceduring, which prescribes the calling of a routine.

Assignations and other COMORFs are voided without any deproceduring so that, in proc void p: p := nish, the assignation p := nish does not prescribe an unexpected calling of the routine nish.g

6.7.1. Syntax

A) NONPROC :: PLAIN ; STOWED ; REF to NONPROC ; procedure with PARAMETERS yielding MOID ; UNITED.

102

a)voided tof61Ag void MORF : deprocedured tof63ag NONPROC MORF ; unchanged fromf61fg NONPROC MORF.

b)voided tof61Ag void COMORF : unchanged fromf61fg MODE COMORF.

fExamples:

a)random (in skip; random;)

next random(last random) (in skip; next random(last random);)

b)proc void(pp) (in proc proc void pp = proc void: (print(1); void: print(2)); proc void(pp);) g

6.7.2.Semantics

The elaboration of a voided-to-void-FORM consists of that of its direct descendent, and yields empty.

7. Modes and nests

fThe identi cation of a property in a nest is the static counterpart of the dynamic determination (4.8.2.b) of a value in an environ: the search is conducted from the newest (youngest) level towards the previous (older) ones.

Modes are composed from the primitive modes, such as boolean , with the aid of HEAD s, such as structured with , and they may be recursive. Recursive modes spelled in di erent ways may nevertheless be equivalent. The syntax tests the equivalence of such modes by proving that it is impossible to nd any discrepancy between their respective structures or component modes.

A number of unsafe uses of properties are prevented. An identi er or mode-indication is not declared more than once in each reach. The modes of the operands of a formula do not determine more than one operation. Recursions in modes do not cause the creation of dynamic objects of unlimited size and do not allow ambiguous coercions.g

7.1. Independence of properties

fThe following syntax determines whether two properties (i.e., twoPROP s), such as those corresponding to real x and int x, may or may not be enveloped by the same LAYER .g

103

7.1.1. Syntax

A)PREF :: procedure yielding ; REF to.

B)NONPREF :: PLAIN ; STOWED ;

procedure with PARAMETERS yielding MOID ; UNITED ; void.

C) *PREFSETY :: PREF PREFSETY ; EMPTY. fPROP :: DEC ; LAB ; FIELD.

QUALITY :: MODE ; MOID TALLY ; DYADIC ; label ; MODE eld. TAX :: TAG ; TAB ; TAD ; TAM.

TAO :: TAD ; TAM.g

a)WHETHER PROP1 independent PROPS2 PROP2fa,48a,c,72ag : WHETHER PROP1 independent PROPS2fa,cg and PROP1 independent PROP2fcg.

b)WHETHER PROP independent EMPTYf48a,c,72ag : WHETHER true.

c)WHETHER QUALITY1 TAX1 independent QUALITY2 TAX2fa,48a,c,72ag : unless (TAX1) is (TAX2), WHETHER true ; where (TAX1) is (TAX2) and

(TAX1) is (TAO), WHETHER QUALITY1 independent QUALITY2fdg.

d)WHETHER QUALITY1 independent QUALITY2fcg :

where QUALITY1 related QUALITY2fe,f,g,h,i,j,-g, WHETHER false ; unless QUALITY1 related QUALITY2fe,f,g,h,i,j,-g, WHETHER true.

e)WHETHER MONO related DUOfdg : WHETHER false.

f)WHETHER DUO related MONOfdg : WHETHER false.

g)WHETHER PRAM related DYADICfdg : WHETHER false.

h)WHETHER DYADIC related PRAMfdg : WHETHER false.

i)WHETHER procedure with MODE1 parameter MODE2 parameter yielding MOID1 related procedure with MODE3 parameter MODE4 parameter yielding MOID2fdg : WHETHER MODE1rmly related MODE3fkg and MODE2 rmly related MODE4fkg.

j)WHETHER procedure with MODE1 parameter yielding MOID1 related

procedure with MODE2 parameter yielding MOID2fdg : WHETHER MODE1 rmly related MODE2fkg.

k) WHETHER MOID1 rmly related MOID2fi,jg :

WHETHER MOODS1 is rm MOID2fl,mg or MOODS2 is rm MOID1fl,mg, where (MOODS1) is (MOID1) or (union of MOODS1 mode) is (MOID1), where (MOODS2) is (MOID2) or (union of MOODS2 mode) is (MOID2).

l)WHETHER MOODS MOOD is rm MOIDfk,lg :

WHETHER MOODS is rm MOIDfl,mg or MOOD is rm MOIDfmg.

104

Section711 van Wijngaarden, et al.

m) WHETHER MOID1 is rm MOID2fk,l,n,47fg :

WHETHER MOID1 equivalent MOID2f73ag or MOID1 unites to MOID2f64bg or MOID1 deprefs to rm MOID2fng.

n) WHETHER MOID1 deprefs to rm MOID2fmg :

where (MOID1) is (PREF MOID3), WHETHER MOID5 is rm MOID2fmg, where MOID3 de exes to MOID5f47a,b,cg ;

where (MOID1) is (NONPREF), WHETHER false.

fTo prevent the ambiguous application of indicators, as in real x, int x; x:=0, certain restrictions are imposed on de ning-indicators contained in a given reach. These are enforced by the syntactic test for \independence" of properties enveloped by a given LAYER (rules a, b, c). A su cient condition, not satis ed in the example above, for the independence of a pair of properties, each being some QUALITY TAX , is that the TAX s di er (rule c). For TAX s which are not some TAO , this condition is also necessary, so that even real x, int x; skip is not a serial-clause.

For two properties QUALITY1 TAO and QUALITY2 TAO the test for independence is more complicated, as is exempli ed by the serial-clause

op + = (int i )bool: true, op + = (int i , j )int: 1, op + = (int i, bool j )int: 2,

prio + = 6;

0 + + 0 /c = 2 /c . Ambiguities would be present in

prio + = 6, + = 7; 1 + 2 3 /c 7 or 9 ? /c ,

in

op z = (int i )int: 1, mode z = int;

z i /c formula or declaration? /c ; skip,

and in

op ? = (union(ref real, char) a)int: 1, op ? = (real a)int: 2; ?loc real /c 1 or 2 ? /c .

In such cases a test is made that the two QUALITY s are independent (rules c, d). A MOID TALLY is never independent of any QUALITY (rule d). A MONO is always independent of a DUO (rules d, e, f) and both are independent of a DYADIC (i.e., of a priority PRIO ) (rules d, g, h). In the case of two PRAM s which are both MONO or both DUO , ambiguities could arise if the corresponding parameter modes were \ rmly related", i.e., if some (pair of) operand mode(s) could be rmly coerced to the (pair of) parameter mode(s) of either PRAM (rules i, j). In the example with the two de nitions of ?, the two PRAM s are related since the modes speci ed by

105

Section ALGOL 68 Revised Report 721

union (ref real, char) and by real are rmly related, the mode speci ed by ref real being rmly coercible to either one.

It may be shown that two modes are rmly related if one of them, or some component MOOD of one of them, may be rmly coerced to the other (rules k, l), which requires a sequence of zero or more meek coercions followed by at most one uniting (6.4.1.a). The possibility or otherwise of such a sequence of coercions between two modes is determined by the predicate isrm (rules m, n).

A PROP1 also renders inaccessible a PROP2 in an outer LAYER if that PROP2 is not independent of PROP1 ; e.g.,

begin int x;

begin real x; /c here the PROP1 is reference to real letter x /c skip

end end

and likewise

begin op ? = (int i )int: l, int k:=2; begin op ? = (ref int i )int: 3;

?k /c delivers 3, but ? 4 could not occur here because its operator is inaccessible /c

end .g

7.2. Identi cation in nests

fThis section ensures that for each applied-indicator there is a corresponding property in some suitable LAYER of the nest.g

7.2.1. Syntax

fPROPSETY :: PROPS ; EMPTY. PROPS :: PROP ; PROPS PROP. PROP :: DEC ; LAB ; FIELD.

QUALITY :: MODE ; MOID TALLY ; DYADIC ; label ; MODE eld. TAX :: TAG ; TAB ; TAD ; TAM.g

a)WHETHER PROP identi ed in NEST new PROPSETYfa,48b,542ag : where PROP resides in PROPSETYfb,c,-g, WHETHER true ; where PROP independent PROPSETYf71a,b,cg,

WHETHER PROP identi ed in NESTfa,-g.

b)WHETHER PROP1 resides in PROPS2 PROP2fa,b,48dg : WHETHER PROP1 resides in PROP2fc,-g or PROP1 resides in PROPS2fb,c,-g.

106

c) WHETHER QUALITY1 TAX resides in QUALITY2 TAXfa,b,48dg :

where (QUALITY1) is (label) or (QUALITY1) is (DYADIC) or (QUALITY1) is (MODE eld), WHETHER (QUALITY1) is (QUALITY2) ;

where (QUALITY1) is (MOID1 TALLETY) and (QUALITY2) is (MOID2 TALLETY), WHETHER MOID1 equivalent MOID2f73ag.

fA nest, except the primal one (which is just new ), is some NEST LAYER (i.e., some NEST new PROPSETY ). A PROP is identi ed by rst looking for it in that LAYER (rule a). If the PROP is some label TAX or DYADIC TAX , then a simple match of the PROP s is a su cient test (rule c). If the PROP is some MOID TALLETY TAX , then the mode equivalencing mechanism must be invoked (rule c). If it is not found in the LAYER , then the search continues with the NEST (without that LAYER ), provided that it is independent of all PROP s in that LAYER ; otherwise the search is abandoned (rule a). Note that rules b and c do double duty in that they are also used to check the validity of applied- eld-selectors (4.8.1.d).g

7.2.2. Semantics

a) If some NEST-range R f3.0.1.fg contains an applied-indicator I f4.8.1.bg of which there is a descendent where-PROP-identi ed-in-NEST-LAYER, but no descendent where-PROP-identi ed-in-NEST, then R is the \de ning range" of that I. fNote that NEST is always the nest in force just outside the range.g

b) A QUALITY-applied-indicator-with-TAX I whose de ning NEST-range fag is R \identi es" the QUALITY-NEST-LAYER-de ning-indicator-with-TAX contained in R.

fFor example, in

(/c 1 /c real i = 2.0; (/c 2 /c int i = 1; (/c 3 /c real x; print(i ) /c 3 /c ) /c 2 /c ) /c 1 /c )

there are three ranges. The applied-identi er i in print(i ) is forced, by the syntax, to be an integral-NEST-new-real-letter-i-new-integral-letter-i-new-reference- to-real-letter-x-applied-identi er-with-letter-i (4.8.1.b). Its de ning range is the NEST-new-real-letter-i-serial-clause-de ning-new-integral-letter-i (3.2.1.a) numbered /c 2 /c, it identi es the de ning-identi er i contained in int i (not the one in real i), and its mode is integral .g

fBy a similar mechanism, a DYADIC-formula (5.4.2.1.a) may be said to \identify" that DYADIC-de ning-operator (4.8.1.a) which determines its priority.g

c) The environ E \necessary for" a construct C in an environ E1 is determined as follows:

If E1 is the primal environ f2.2.2.ag,

107

then E is E1;

otherwise, letting E1 be composed of a locale L corresponding to somePROPSETY and another environ E2,

If C contains any QUALITY-applied-indicator-with-TAX

which does not identify fbg a de ning-indicator contained in C,

which is not a mode-indication directly descended from a formalor virtual-declarer, and

which is such that the predicate where QUALITY TAX resides in PROPSETY f7.2.1.bg holds,

then E is E1;

otherwise, fL is not necessary for C andg E is the environ necessary for

C in E2.

fThe environ necessary for a construct is used in the semantics of routine-texts (5.4.1.2) and in \establishing" (3.2.2.b). For example, in

/c 2 /c proc void pp; int n; (/c 1 /c proc p = void: print(n); pp := p)

if E1 and E2 are the environs established by the elaboration of the serialclauses marked by the comments /c 1 /c and /c 2 /c, then E2 is the environ necessary in E1 for the routine-text void: print(n), and so the routine yielded by p in E1 is composed of that routine-text together with E2 (5.4.1.2). Therefore, the scope of that routine is the scope of E2 (2.1.3.5.c) and hence the assignment (5.2.1.2.b) invoked by pp := p is well de ned.g

108

7.3. Equivalence of modes

fThe equivalence or nonequivalence of MOID s is determined in this section. For a discussion of equivalent MOID s see 2.1.1.2.g

fOne way of viewing recursive modes is to consider them as in nite trees. Such a \mode tree" is obtained by repeatedly substituting in some spelling, for each MU application , the MODE of the corresponding MU de nition of MODE . Thus, the spelling mui de nition of structured with integraleld letter i reference to mui application eld letter n mode would give rise to the following mode tree:

Two spellings are equivalent if and only if they give rise to identical mode trees. The equivalence syntax tests the equivalence of two spellings by, as it were, simultaneously developing the two trees until a di erence is found (resulting in a blind alley) or until it becomes apparent that no di erence can be found. The growing production tree re ects to some extent the structure of the mode trees.g

D)PARTS :: PART ; PARTS PART.

E)PART :: FIELD ; PARAMETER.

a)WHETHER MOID1 equivalent MOID2f64b,71m,72cg : WHETHER safe MOID1 equivalent safe MOID2fbg.

b)WHETHER SAFE1 MOID1 equivalent SAFE2 MOID2fa,b,e,i,j,ng :

where (SAFE1) contains (remember MOID1 MOID2) or (SAFE2) contains (remember MOID2 MOID1), WHETHER true ;

unless (SAFE1) contains (remember MOID1 MOID2) or (SAFE2) contains (remember MOID2 MOID1),

WHETHER (HEAD3) is (HEAD4) and remember MOID1 MOID2 SAFE3 TAILETY3 equivalent SAFE4 TAILETY4fb,d,e,k,q,-g, where SAFE3 HEAD3 TAILETY3 develops from SAFE1 MOID1fcg and SAFE4 HEAD4 TAILETY4 develops from SAFE2 MOID2fcg.

c)WHETHER SAFE2 HEAD TAILETY develops from SAFE1 MOIDfb,cg : where (MOID) is (HEAD TAILETY), WHETHER (HEAD) shields SAFE1 to

SAFE2f74a,b,c,d,-g ; where (MOID) is (MU de nition of MODE), unless (SAFE1) contains (MU has), WHETHER SAFE2 HEAD TAILETY

develops from MU has MODE SAFE1 MODEfcg ;

where (MOID) is (MU application) and (SAFE1) is (NOTION MU has MODE SAFE3) and (NOTION) contains (yin) and (NOTION) contains (yang),

WHETHER SAFE2 HEAD TAILETY develops from SAFE1 MODEfcg.

d)WHETHER SAFE1 FIELDS1 mode equivalent SAFE2 FIELDS2 modefbg : WHETHER SAFE1 FIELDS1 equivalent SAFE2 FIELDS2ff,g,h,ig.

e)WHETHER SAFE1 PARAMETERS1 yielding MOID1 equivalent

SAFE2 PARAMETERS2 yielding MOID2fbg :

WHETHER SAFE1 PARAMETERS1 equivalent SAFE2 PARAMETERS2 ff,g,h,jg and SAFE1 MOID1 equivalent SAFE2 MOID2fbg.

f)WHETHER SAFE1 PARTS1 PART1 equivalent SAFE2 PARTS2 PART2fd,e,fg : WHETHER SAFE1 PARTS1 equivalent SAFE2 PARTS2ff,g,h,i,jg

and SAFE1 PART1 equivalent SAFE2 PART2fi,jg.

g)WHETHER SAFE1 PARTS1 PART1 equivalent SAFE2 PART2fd,e,fg : WHETHER false.

h)WHETHER SAFE1 PART1 equivalent SAFE2 PARTS2 PART2fd,e,fg : WHETHER false.

i)WHETHER SAFE1 MODE1 eld TAG1 equivalent SAFE2

MODE2 eld TAG2fd,fg : WHETHER (TAG1) is (TAG2) and SAFE1 MODE1 equivalent SAFE2 MODE2fbg.

110