Chapter 1. IntroductionThis manual describes the Cedar language. It is organized into three major parts:Chapter 2: A description of a much simpler kernel language, in terms of which the currentCedar language is explained. This description includes a precise definition ( 2.2), and a lessformal explanation of the ideas of the kernel and the restrictions imposed by current Cedar( 2.3-2.9). 2.1 contains an overview or glossary, in which the major technical terms usedin the kernel are briefly defined.Chapter 3: The syntax and semantics of the current Cedar language. The semantics is givenprecisely by a desugaring into the kernel. It is also given more informally by English text.This chapter also contains a number of examples to illustrate the syntax.Chapter 4: The primitive types and procedures of Cedar. For each one, its type is given aswell as an English definition of its meaning. This chapter is organized according to the classhierarchy of the primitive types ( 4.1).In addition, there is a one-page grammar, and a two-page language summary which includes thegrammar, the desugaring, and the examples from Chapter 3, The document you are reading is a draft. Most of Chapter 2 is missing, and a numberof other sections are incomplete.Error reports and comments on the presentation are most welcome.!_pj \jqMZ$rqXZW FU NTQ1!P&r q:NELJ&-JTrIBq FG D3 A!s? ?V ;@&TVk(CEDAR LANGUAGE REFERENCE MANUAL: INTRODUCTIONDRAFT OF JULY 20, 19822Table of ContentsChapter 1. IntroductionChapter 2. The kernel language2.1Overview2.1.1Doing computations2.1.2The type system2.1.3Writing programs2.1.4Conveniences2.1.5Miscellaneous2.2Kernel definition2.2.1The core2.2.1.1Application2.2.1.2Lambda and environments2.2.1.3Groups2.2.1.4Bindings2.2.1.5Declarations2.2.1.6Types and type-checking2.2.2Conveniences2.2.2.1Expression syntax2.2.2.2Declaration and binding constructors2.2.3Imperatives2.2.4Exceptions2.2.5Kernel primitives2.3Doing computations2.3.1Application2.3.2Values2.3.3Variables2.3.4Groups2.3.5Bindings2.3.6Arguments2.3.7Declarations2.4The type system2.4.1Types2.4.2Type predicates and type-checking2.4.3Marks2.4.4Clusters and dot notation2.4.5Classes2.5Programs2.5.1Structure of programs2.5.2Names2.5.3Expressions2.5.4Scope2.5.5Constructors2.5.6Recursion f2tG?Gq#_pj Z U RuyyPrTX yO/TyMdTyKT yIT GvuyyErTTDKv TBTAT@(T> T=fy;rT T:;vT8$y73rT y5hT y3TX 1Euyy/rT y-Ty,Ty*=Ty(rTy&Ty$T "uyy rTyT!yGTy|TyT YuyyrTyTyT yQTyT y TvTVk(CEDAR LANGUAGE REFERENCE MANUAL: INTRODUCTIONDRAFT OF JULY 20, 198232.6Conveniences2.6.1Coercion2.6.2Finalization2.6.3Safety2.6.4Concurrency2.7Miscellaneous2.8Relations among groups, types, declarations and bindings2.9Incompatibilities with current CedarChapter 3. Syntax and semantics3.1Notation3.1.1Notation for the grammar3.1.2Notation for desugaring3.2The lexical structure of programs3.3Modules3.3.1Modules and instances3.3.2Applying modules3.3.2.1Initializing an implementation instance3.3.3Parameters to modules: DIRECTORY and IMPORTS3.3.4Interface module bodies3.3.4.1Opaque types3.3.4.2Interface variables3.3.5Implementation module bodies3.3.6PUBLIC, PRIVATE and SHARES3.4Blocks, OPEN and ENABLE3.4.1Scope of names and initialization3.4.2OPEN3.4.3ENABLE and EXITS3.4.3.1ENABLEFinalizationSignals3.4.3.2EXITS3.4.4Safety3.5Declaration and binding3.5.1PROC bindings3.6Statements3.7Expressions3.8IF and SELECT3.9Types f2tG?Gq _uy y^4rTy\iT yZTyXT V{uy T#yX/ Qy$ Lpj IuyyH&rTXyF[T Duy! Ayy@rTy>9TT<& <0 :( 9G3JTVk(nCEDAR KERNEL, TEMPORARYDRAFT OF JULY 19, 19826Chapter 2. The kernel languageThis document describes the Cedar language in terms of a much simpler kernel language. Cedardiffers from the kernel in two ways:It has a more elaborate syntax. The meaning of each construct in Cedar is explained bygiving an equivalent kernel program. Often the kernel program is longer or less readable; the Cedar construct can be thought of as an idiom whichconveniently expresses a common operation. Sometimes the Cedar construct has no real advantage, and thedifference is the result of backward compatibility with the ten-year history of Mesa and Cedar.It has a large number of built-in types and procedures. In the kernel language all of thesecould in principle be programmed by the user, though in fact most are provided by specialcode in the Cedar compiler. In general, you can view these built-in facilities much like alibrary, selecting the ones most useful for your work and ignoring the others.Unfortunately, the kernel language is not a subset of the current Cedar langauge. Many importantobjects (notably types, declarations and bindings) which are ordinary values in the kernel languagethat can be freely passed as arguments or bound to variables, are subject to various restrictions inCedar: they can only be written in literal form, cannot be arguments or results of procedures, orwhatever. The long-term goal for evolution of the Cedar language is to make it a superset of thekernel defined here. In the meantime, however, you should view the kernel as a concise andhopefully clear way of describing the meaning of Cedar programs. To help in keeping the kerneland current Cedar separate, keywords and primitives of the kernel which are not available incurrent Cedar are written in SANS-SERIF SMALL CAPITALS, rather than the ROMAN SMALL CAPITALSused for keywords of current Cedar. Operator symbols of the kernel which are not in current Cedarare not on the keyboard.The kernel is a distillation of the essential properties of the Cedar language, not an entirely separateinvention. Most Cedar constructs have simple translations into the kernel. Those which do not (e.g.,many of the features of OPEN) are considered to be mistakes, and should be avoided in newprograms. 2.2 defines the syntax and semantics of the Cedar kernel language, the former with a grammar,and the latter by explaining how to take a program and deduce the function it computes and thestate changes it causes. The remainder of the chapter explains the concepts behind the kernel. Italso gives the restrictions imposed by the current Cedar language on the full generality describedhere; for more on this subject, see Chapter 3. The meaning of the various built-in primitives isgiven in Chapter 4. 2.9 describes the incompatibilities between the kernel language and currentCedar, i.e., the constructs in Cedar which would have a different meaning in a kernel program. Forthe most part, these are bits of syntax which do not have consistent meanings in current Cedar;future evolution of the language will replace them with their kernel equivalents.Usually, terms are defined and explained before they are used, but some circularity seems to beunavoidable. 2.1 gives a brief summary of each major idea which may be helpful as a reminder.Both this and the explanations in 2.3-2.7 are given under five major headings, as follows:Doing computations: Application Value Variable Group Binding Argument The type system: Type Type-checking Mark Cluster DeclarationPrograms: Name Expression Scope Constructors RecursionConveniences: Coercion Exception Finalization Safety ProcessMiscellaneous: Allocation Static PragmaThe kernel definition in 2.2 follows the ordering of the kernel grammar. f2tG)Gq%_pj \jq%rq ZX!3W TtgS <R} UP%qPN@MSKF Hn ; FH Ef9' CV B^W @P ?VB =L Grq rq *tq F;|qtqO Cuqrqrq' Arq.rq @-r q% > tq6 =V 9uqrq+{q 8Q 5&uqrqrqr q 3{qtq{qtqtq {q{qtqtv tq{q 2{q{q{q .uq +s 'rX $WuqH "C !O*, )2 G (rqtq rq{q@{qtqrq1!d {q{q"{q{q }{q{q //{ q{q {}{q{qr q}{q rq 6 #7 x TVk(CEDAR KERNEL, TEMPORARYDRAFT OF JULY 19, 19828Mark: Every value carries a set of marks (e.g., INT or ARRAY; think of them as little flags stuck ontop of the value). The predicate HASMARK tests for a mark on a value; it is normally used to writetype predicates. The set of all possible marks is partially ordered. The set of marks carried by a value must have a largest member m, and it must include every mark smaller than m.Hence all the marks on a value can be represented by the single mark m; we can say that m is the mark on the value.Type-checking: The purpose of type-checking is to ensure that the arguments of a proc satisfy thepredicate of the domain type; this is a special kind of pre-condition for executing the proc. Theproc body can then rely on the fact that the formal parameters satisfy their type predicates. It mustestablish that the results satisfy the predicate of the range type; this is a special kind of post-condition which holds after executing the proc. Finally, the caller can rely on the fact that theresults satisfy their type predicate. In summary:Callerestablish pre-condition: arguments have the domain type;rely on post-condition: results have the range type.Bodyrely on pre-condition: formals have the domain type;establish post-condition: returns have the range type.Declaration: A declaration is an ordered set of [name, type] pairs, often denoted like this: [x: INT, y:BOOL]. A declaration can be instantiated (e.g., on block entry) to produce a binding in which eachname is bound to a variable of the proper type; instantiating the previous example yields [x: VAR INT~(VAR INT).NEW, y: VAR BOOL~(VAR BOOL).NEW]. If d is a declaration, a binding b has type d if it has the same set of names, and for each name n thevalue b.n has the type d.n. A binding b matches d if the values of b can be coerced to yield a bindingb( which has type d.2.1.3 ProgramsName: A name appearing in the program denotes the value bound to the name in the scope that thename appears in (unless the name is before a colon (declaration) or tilde (binding), or after a dot).An atom is a value that can be used to refer to a name; a literal atom is written like this: $alpha.Expression: In the program a value is denoted by an expression, which is:a literal value (3 or "Hello"), ora name (x or salary), or an application of a proc to other values(Sin[90] or GetProperties[directory, ReadFileName[input]]), ora l-expression, which yields a proc value (l [x: INT] IN (IF x<0 THEN x ELSE x) ), ora constructor for a declaration or binding ([x: INT~3, y: REAL~3.14].If a value is known for each name in the expression, then the expression can be evaluated toproduce a value. Thus an expression is a rule for computing a value.Scope: A scope is a region of the program in which the value bound to a name does not change(although the value might be a variable, whose contents can change). For each scope there is abinding which determines these values. A new scope is introduced (in the kernel) by IN or by a [...]constructor for a declaration or binding; e.g., LET x~3 IN x+5;LET fact~l [n: INT] IN IF n=0 THEN 1 ELSE n*fact[n1].Constructors;IncompleteRecursion:Incomplete f2tG)Gq _uqrqtqtq( ^Wyq . \A Zt<~t-~t Y@~t~tvt VYu qO T+- SQ:' Q., PI8 N*)MA X/ K4)J9 4 H6 Eu qr q(rq{qtq{q Dtqr q: BV @{qXytGqytqtqX{qytGqytqtqX ?z{q{q {q4{q ={q{q {qrq{q{qrq yqX{qyq{q yq{q|q{qtqyqtq{qtqtq{q{q{q u q s uq s  rTVk(CEDAR KERNEL, TEMPORARYDRAFT OF JULY 19, 198292.1.4 ConveniencesCoercion: Each type cluster contains To and From procedures for converting between values of thetype and values of other types (e.g., Float: PROC[INT]_[REAL]). One of these procedures is appliedautomatically if necessary to convert or coerce an argument value to the domain type of a proc; thisapplication is a coercion. Each coercion has an associated atom called its tag (e.g., $widen forINT_REAL or $output for INT_ROPE); several coercions may be composed into a single one if theyhave the same tag.Exception: There is a set of exception values. An expression e denotes a value which is either oftype De or is an exception. Whenever an exception value turns up in evaluating an expression, itimmediately becomes the value of the whole expression, unless (in the kernel) the expression hasthe form e BUT {...}. The {...} tests for exception values and can supply an ordinary value, oranother exception, as the value of the BUT expression. An exception value may contain an ordinaryvalue, so that arbitrary information can be passed along with an exception.Finalization: When a variable is no longer accessible, the storage it occupies is freed (automaticallyin the safe language). Before this is done, a finalization proc in the cluster of the variable's type iscalled to do any other appropriate resource deallocation. The local variables of a proc or otherscope may also be finalized (using UNWIND).Safe: The safety invariant says that all references are legal, i.e., each REF T value is NIL or refers toa variable of type T. A proc is safe if it maintains the safety invariant whenever it is applied toarguments of the proper types. If a proc body (l-expression) is checked, the compiler guarantees that it is safe, and the proc value is safe;trusted, the programmer asserts that it is safe (but the compiler makes no checks), and theproc value is safe;unchecked, the compiler makes no checks and the proc value is unsafe. It is best to write checked code whenever possible. However, checked code cannot call unsafe procs(since the compiler then cannot guarantee safety). Process: Concurrency is obtained by creating a number of processes. Each process executes a singlesequential computation, one step at time. They all share the same address space. Shared data(touched by more than one process) can be protected by a monitor; only one process can executewithin any proc of the monitor at a time. Thus monitor procs can read and write shared data safely.A process can wait on a condition variable within a monitor; other processes can then enter themonitor. The waiting process runs again when the condition is notified, or after a timeout.2.1.5 MiscellaneousAllocationIncompleteStaticIncompletePragmaIncompleteThe remainder of Chapter 2 is not released in this draft. f2tG)Gq _rX \uq{qrq r q [, {qtqtq}qtq& Y rq5 X$ rq2rq{q Vt}tq{qt}tq9 U Quqrq{q  Pm}{qV N < Me{qyq@ Kyq7 J]E G2u q-, E,r q+ D*Z Btq ?{uqrq0tq{q tq ={q rq< <;9tqtq74 4 #1/Y - * %uX #~q[ !!= v   vq", E C C ! uq ;uq  uq X  3uq y uqq +uq q uqTVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 1982113.1.1 Notation for the grammarThe grammar is written in a variant of BNF:Bold parentheses are for grouping: ( interface | implementation).Item | item means choose one.?item means zero or one occurrences of item.item; ... means zero or more occurrences of item separated by ";". The separator may also be ",",ELSE, IN, or OR, or it may be absent. If the separator is ";", a trailing ";" is optional. item; !.. is just like item; ... but there is at least one occurrence.A terminal is a punctuation character other than bold ()?| or any character underlined, or a word inSMALL CAPS. Note that [] and {} are terminals, and do not denote optional occurrence and repetition as they do in manyother variants of BNF.The rules are numbered sequentially, and each use of a non-terminal not defined just below is cross-referenced with a small superscript number. marks an unsafe feature, an obsolete one; a feature needed only for machine-dependent work; an efficiency hack.3.1.2 Notation for desugaringThe right-hand column is desugaring into the Cedar kernel language. This is a purely syntactictransformation; i.e., it is done on the text of the program, not on the values. The rewriting is doneone rule at a time; a single step of rewriting involves elements from exactly one rule. Thedesugaring is specified by slightly informal but straightforward rewriting rules, in which:An occurrence of a non-terminal (written in bold) denotes the text produced by that non-terminal in the grammar rule.Alternation reflects a corresponding alternation in the grammar rule, ? reflects acorresponding optional item in the grammar rule, and bold parentheses are for grouping asin a grammar rule. As in grammar rules, literal parentheses are underlined.Everything else is taken literally.An underlined non-terminal in the right column means that the desugaring specified for that non-terminal must be done in order to obtain a legal program. Otherwise the transformations can bedone in any order, yielding a legal program at each step.Every occurrence of expression and type in the desugaring should be enclosed in parentheses, sothat the desugared program parses as the rewriting rule indicates. These parentheses are omitted forclarity.For type options like PACKED, the desugaring of the construct in which they appear is a call on abuilt-in a type constructor which takes a corresponding BOOLEAN argument defaulting to FALSE; ifthe attribute is present, the argument is supplied with the value TRUE.Examples: the following rule for subranges:subrange ::= ( typeName | ) (( [ e1 .. e2 ] | [ e1 .. e2 ) ) |(INT | typeName).MKSUBRANGE[e1, ( e2 | PRED[e2] ) ] ) |( ( e1 .. e2 ] | ( e1 .. e2 ) ) )(INT | typeName).MKSUBRANGE[SUCC[e1], ( e2 | PRED[e2] ) ] )generates these desugaringsIndex [ 10 .. 20 ]Index.MKSUBRANGE[10, 20]Index [ 10 .. 20 )Index.MKSUBRANGE[10, PRED[20] ]( 1 .. 100 )INT.MKSUBRANGE[SUCC[1], PRED[100] ]Names introduced in the desugaring are written with one or more trailing dash ("(") characters.Such names cannot be written in a Cedar program, and hence they are safe from name conflicts. f2tG4G?q _rX \q( [,Xuq uquq Yuq X$uq, VuqY UtqytqtqL Suquq& R6uq 8Qw? R PtGqXtG&vt= OR MqXa LJ+ Jc IB ECr Bq@r @qrqrq ?J = Q;4797X ./1uq 5 >4PI1# /F .rqN ,5 )mu quq5 '@ &e #:tqD !0tqtq 2?tq + uXquq uqtGu XuqXXqXqXqXq yXuqu*utququqy quXququXquqtquXquququ jq 2ydjjqjq2yjjqjq<2yjuqu*utququqy qtqujququjquqtqujququ q X *y q c*y qtq *tqy qtqtq C}q 0Y XTVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198212The desugaring is constructed so that the ordinary scope rules prevent multiple uses of these namesfrom being confused.3.2 The lexical structure of programs56 name ::= letter (letter | digit)...-- But not one of the reserved words in Table ???.57 literal ::= num ?( D | d | B | b ) ?num |-- WHOLENUMBER, decimal if radix omitted or D, octal if B |digit (digit |A|B|C|D|E|F) ... ( H | h ) ?num |-- WHOLENUMBER in hex.. |?num . num ?exponent | -- REAL as a scaled decimal fraction; note no trailing dot. |num exponent |-- With an exponent, the decimal point may be omitted. |' extendedChar | digit !.. C |-- CHAR literal; the C form specifies the code in octal |" extendedChar ... " ?L |[ ('extendedChar), ...] -- Rope.ROPE, TEXT, or STRING |$ n-- ATOM literal58 exponent ::= (E | e) ?(+ | ) num-- Optionally signed decimal exponent59 num ::= digit !..60 extendedChar ::= space | \ extension |printingCharExceptQuoteOrBackslash 61 extension ::= digit1 digit2 digit3 |-- The character with code digit1 digit2 digit3 B |(n | N | r | R) | (t | T) | (b | B) | -- CR, '\015 | TAB, '\011 | BACKSPACE, '\010 | (f | F) | (l | L) | \ | ' | "-- FORMFEED, '\014 | LINEFEED, '\012 | \ | ' | "m, x1, x59y, longNameWithSeveralWords: INT;n: INT~1+12D+2B9+2000000000B +1H+0FFH;r1: REAL~0.1+.1+1.0E1 +1E1;a1: ARRAY [0..3] OF CHAR~['x, '\n, '\', '\141];r2: ROPE~"Hello.\n...\nGoodbye\F";a2: ATOM~$NameInAnAtomLiteral;The main body of the grammar (rules 1-55) treats a program as a sequence of tokens. Rules 56-61give the syntax of most tokens. A token is:A literal57. More information about literals of type T can be found in Chapter 4, as part ofthe treatment of type T.A name56.A reserved word, which is a string of uppercase letters that appears in the list of reservedwords in Table ???. A reserved word may not be used as a name, except in an ATOM literal.One of the following two-character symbols (used in the grammar rules indicated):~=not equal19 30<=less than or equal22~=greater than or equal22~>not greater than19 30=>chooses8 17 30 31 33 35>RETURNS43..subrange constructor25 48~~bind by name6 34A punctuation symbol: any printing character not a letter or digit, and not part of one ofthe two-character sequences above. The punctuation symbols are: !@#$~*-+=|(){}[]_^;:'",.<>/. The following ASCII characters are not punctuation symbols (and areillegal in a program except in an extendedChar60): %&\?. Note that Cedar uses a variant ofASCII which includes the characters _ (instead of the underbar ) and ^ (instead of thecircumflex ). f2tG4G?q _/1 ^W YuX" VY>utuXquququ*q2 T>uXquq+TJTuqRTTuqyT`TuqhT/Tuququ*qy q,u SQququqSSQuqSS:SQuqSSQuqSSQuq_SFSQuqSSQuququqS SQuq S!zSQuququ*qy q u Qq uquq*tq5u PIq u*q7u Nquq fNdNu*qtq1u MAququq6M MAu*ququq tqtqtqu Kq*tq J9>uXquqJJ9uqJHJ9uquququq*% H>uXq G1>u Xquq u Eq# D)>uXqCD)qCD)qCD)qu*quCD)quCD)quCD)qu B;uq BZB;uqbB#B;uqBB;uqB "B;uququq BoB;uqB~B;uququq|BCB;uqKB2B;uquq*tqutGqXuqtquq @uq @y @uq@@uququq@c\@uqd@K@uquququq*tquqtquququq ='tq <tqy: 9tq 7| 5tqtGqX 4ttq uq 2tq /Hrq .A'+,/+q*{q*e{q( (S( q%C$1Gtq!Q U*X >q*X Mq*>q*X Eq*>q*=q*tq*X >5q*X{>q1(Y%tq0 Q$  Qq* tq8 Z:-  I w l I TTVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198213A comment is not a token and may appear between any pair of tokens; it is a token delimiter, andhence cannot appear in the middle of a token.The program is parsed into tokens by starting at the beginning and successively taking from thefront the longest sequence of characters which forms a token according to the rules above, after firstdiscarding any amount of initial whitespace or comment. Whitespace is a space, tab, and carriage return.A comment is a sequence of characters beginning with --, not containing -- or a carriagereturn, and ending either with -- or with a carriage return.Whitespace and comments thus do not affect the meaning of the program except:When they delimit a token.Within a CHAR literal or a ROPE literal, where they are taken literally. Thus ' is equal to'\040, and "Iam --not--" is equal to "I\Nam --not--" and different from "I\Nam ".Both reserved words (Table ???) and names with predefined meanings (Table 45) are made upentirely of upper case letters. These names may not be rebound by the program.Note: Semi-colons are used to separate declarations, bindings and statements in a body, and toseparate choices in a statement. Commas are used to separate declarations in fields (i.e., in a procdomain or range, a recordTC or a unionTC), bindings in an application, choices in an expression orin a unionTC. In general these sequences may be empty, and an extra separator at the end isharmless except when the sequence is bracketed with [].The braces which delimit a block4, interface body2, choices in an enable7, or MACHINE CODE body13may be replaced by BEGIN and END brackets. BEGIN replaced "{" and END replaces "}". If onebrace is replaced, its matching partner must also be replaced. The braces delimiting an enumTC45may not be replaced by BEGIN ... END.3.3 Modules 1 module ::= DIRECTORY (nd (: TYPE (nt | ) | ) l [ (nd( : ( (TYPE nt | TYPE nd) | TYPE nd), ... ] IN ?(USING [ nu, ... ] ) ), ... ; LET (nd(~RESTRICT[nd(, [$nu, ... ] ] ), ... ( interface | implementation )IN ( interface | implementation ) 2 interface ::= nm : ?CEDAR DEFINITIONSLET (nit((~nit), ... IN l [((niv | nit):nit((), ...]=>?(IMPORTS ( (niv : | ) nit ), ...) [nm: TYPE nm] IN?(SHARES ns !..) -- access to PRIVATE names from ns allowed in the module~ ?access12 { ?open6 db10; ... } .open [ db, ... ] 3 implementation ::= nm, !.. : ?CEDAR LET (nit((~nit), ... IN l [( ( niv | nit ):nit((), ...] =>?RESIDENT ( PROGRAM drType43 | [(ne: ne , ... , nm: TYPE nm , CONTROL: PROGRAM] ] IN MONITOR drType43 LET LOCK~MONITORLOCK.NEW , ( | LOCKS e ( | USING nu: t)) ) lock(~lall IN (l IN LOCK | (l IN e | l [nu : t] IN e)) IN?(IMPORTS ( (niv: | ) nit), ...) ?(EXPORTS ne, ...)LET b(~NEWPROGINSTANCE[block].UNCONS IN?(SHARES ns, !..) [ (ne~BINDDFROM[ne, b(] ), ... , nm~b( ]~ ?access12 block . where the body of the block is desugared to a decl thus: [ db, ... , nm: PROGRAM drType={s; ...} ]DIRECTORY Rope: TYPE USING [ROPE, Compare], -- There should always be a USING clause CIFS: TYPE USING [OpenFile,Error,Open,read],-- unless most of the interface is usedIO: TYPE IOStream, f2tG4G?q _&9 ^W( [,!; Y#> X$ r qrqU0Strq3Q5 OMM@Jtq tq2 IdGD DE C1F @G >D <@ ;zC 9/ 676q76q76qtqtq7 5Gqtqtq tqtq 3?4  2?qtqtq -luX *A>uXqtquq)~*Aquqtquq)~*Aququququ*q|quq)~*A}ququtqu)~*Aquqtqu)~*Auquqtqu)~*AuquqytGqX (Sutq'~(Sququququq*yquq'~(S}qyqu'~(S}qu'~(Squququq &euq uqu*yququququ qu $>uXq$T~$qutqt *yquq$T~$}qu$T~$uquqyq|qu$T~$ququ$T~$uqu$T~$}uquq "utququq"f~>"qXuquq"f~"ququ2Mqu"f~"qtqu"f~"qyG !utqX x~!quq* tq u x~!q uq]quq]q]quq*uququqtG >u Xq~qutqtG*yqXu~}qu~uquqyq|quququ~ququ~ququ~}uquq uqtquqtqqu*qu~qu~ququ~qtqu~qtqtqy tG$qXq*yGtqt qtqX 3utGuqXtququqtq~3ququ*q}q|~3qtqu|qyqtququ|qyququq|qu~3quqyquqy Eutquq~Equq~Euququtq~Equ*yq}qyqu:^ .=Eqyqy Wuqutq~Wquq*u~Wqyqu~Wq}quququ~Wq}q iuqiq*8*uququX~qtquququq tG  |qXtGqXtq *tq  tGqX*'  ttq  TVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198214Buffer: TYPE;-- or it is exported.BufferImpl: MONITOR [f: CIFS.OpenFile] -- Implementations can have arguments.LOCKS Buffer.GetLock[h]^ -- LOCKS only in MONITOR, to specifyUSING h: Buffer.Handle-- a non-standard lock.IMPORTS Files: Files: CIFS, IO, Rope-- Note the absence of semicolons.EXPORTS Buffer-- EXPORTS in PROGRAM or MONITOR.~ { -- module body -- } . -- Note the final dot.Modules serve a number of functions (which might perhaps better be disentangled, but are not):A file of text (BufferImpl.mesa, or its translation into object code, BufferImpl.bcd).The unit handled by the editor, named in DF files and models, and accepted by thecompiler, the binder, and the loader.A set of related structures (types, procedures, variables) which are freely accessible to eachother, hiding irrelevant information from other modules.A procedure which can accept interface types and bindings as arguments, and returnsinterface values as results.The first two uses are not relevant to the language definition, and are not discussed further here;see ???. The others are the subject of this section. There are two kinds of modules: interface modules (written with DEFINITIONS) and implementations(written with PROGRAM or MONITOR). They have the same header (except that interfaces have noRESIDENT option or EXPORTS list); it defines the parameters and results of the module viewed as aproc ( 3.3.1) and specifies the name nm of the module. The bodies (following the ~) are different. The remainder of this section deals in turn with:Modules as procedures, and the interface or instance values obtained by applying them (3.3.1).How modules are applied ( 3.3.2).Module parameters: the DIRECTORY and IMPORTS lists; USING clauses ( 3.3.3).Interface module bodies and interfaces ( 3.3.4).Implementation module bodies; the EXPORTS list ( 3.3.5).SHARES and access12 ( 3.3.6).The meanings of the other parts of a module header are discussed elsewhere:CEDAR in 3.4.4.MONITOR is CONC.???.RESIDENT in ???.3.3.1 Modules and instancesA module is a proc which takes two kinds of arguments:Interfaces, declared in the DIRECTORY list. These arguments are supplied by the model (oron the command line for the compiler),Interface instances, declared in the IMPORTS list. These arguments are also supplied by themodel (or in a config file passed to the binder, or implicitly by the loader). 3.3.3 discusses the types of these arguments and how they are declared. In addition, an f2tG4G?q _t*qX \ tq*& [,tq*tGqXtq yYtq* X$tq*" Vtq*tqtqtq U* QWO{q'{ qMA AKIeCG2E8D @R ?V2 <+7t q :tqtq< 9#tq tq1 7"{7~7q< 4t12rqrq$0.@+tqtqtq)1'8"tq$tq %&$q !K]tq tqtq rX q5+ tq0t#q Orqtq/ tvt8q s#5 TVk(KCEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198215implementation may take PROGRAM arguments declared in the drType following PROGRAM orMONITOR. These are ordinary values; they are discussed in 3.3.2.1.When a module is applied to its arguments, the resulting value isFor an interface module, an interface, also called an interface type.For an implementation module, a binding whose values are instances: one interface instancefor each interface it exports, plus one for the program instance, also called a global frame.This application cannot be written in the program, only in the model; it is described in 3.3.2.An interface or interface type is a type, as the latter name suggests. This type is a declaration(obtained from the declarations which constitute the module body), with an extended cluster whichincludes all the bindings in the module body that don't use declared names ( 3.3.4). A value whosetype is an interface is an interface instance; such values are the results of instantiatingimplementation modules.A program instance or a global frame is a frame, as the latter name suggests, i.e., a binding obtainedfrom the bindings and declarations of the module body, just like any proc frame ( 3.3.5).Normally the part of the program outside the module does not deal with the instance directly, butonly with the exported interface values.In most cases, there is:Exactly one application of each module, and hence exactly one interface or one instance. Only one module which exports an interface.Only one interface exported by a module. Only one argument of the proper type for each module parameter ( 3.3.3), so that it isredundant to write the arguments explicitly. When these conditions hold, there is a close correspondence among the following four objects: an interface module;the interface which it returns (since the arguments need not be written explicitly); the implementation module which exports the interface;its instance (again, since the arguments need not be written explicitly).The distinctions made earlier in this section then seem needless; it is sufficient to simply considerthe interface and implementation modules, and identify them with the files which hold their text. Inmore complicated situations, however, it is necessary to know what is really going on.Need an example3.3.2 Applying modulesA module is not applied to all its arguments at once. Instead, the arguments are supplied in twostages:A module is applied to its interface (DIRECTORY) arguments by compiling it; the result is aBCD (represented by a .bcd file). The bcd is still a proc, with instance parameters. Like anyproc, a module can be applied to different arguments (i.e., different versions of theinterface arguments) to yield different BCDs.A BCD is applied to its instance (IMPORT) arguments by loading (or binding) it; the result isa program instance, together with any interface instances exported by the module. Again,the BCD can be applied to different arguments (i.e., different interface instances) to yielddifferent instances. Indeed, because an instance may include variables, even two applicationsto the same arguments yield different instances. f2tG4G?q _ tqtq ^Wtq< [,AXrqr qV|;T-rqr q Ra Ourqr q2 M< LmM J$rq%- Ie  F:rqr qB D2% C24% A$ ><+Y9+7{)5#?3$ 1G^/.?U,6+7I )P (/&; &R #9s :rX qF 3 tq,tq{q {q4+ CtqOtqtq#PGtqO > ?. hTVk(HCEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198216These two stages are separated for several reasons:All the type-checking of a module can be (and is) done in the first stage, by the compiler.The only type errors possible in the second stage are supplying an unsuitable argument.Compiling is much slower than loading, and a module needs to be recompiled only whenits interface arguments change, not when the interface values change. The latter are changesin the implementations of the interfaces, and are much more common.Other reasons. History.3.3.2.1 Initializing a program instanceA program instance PI may be uninitialized, because no code in the module is executed when theinstance is made. It is the job of the PROGRAM proc PP to initialize PI, perhaps using the PROGRAMarguments if there are any. Until PP has been called, PI is not in a good state. It would be better tosupply the PROGRAM arguments along with the imported instances, and call PP as part of makingPI, so that PI is never accessible in its uninitialized state. But it isn't done that way; hence theprogrammer must ensure that PP is called (using the START construct, 4.4.1) before any use ismade of PI. Note that PP also contains the initialization code for any variables or non-static valuesin the instance; e.g., if x: INT_3, the value of x will not be 3 until after PP has been called.There is some error detection associated with this kludge. If a proc in the instance is called beforethe instance has been initialized by START, a start trap occurs. At this point, if PP takes noarguments it is called automatically, and the original call then proceeds normally; if PP does takearguments, there is a Runtime.StartFault ERROR.Caution: If the module is a monitor, PP runs without the monitor lock; if another process calls intothe module while PP is running, it will not wait, but will run concurrently with PP. This is unlikelyto be right. It is unwise to rely on a start trap to initialize a monitor module; call PP explicitly.Caution: If a variable in the instance is referenced before the instance has been initialized, no erroris detected, and the uninitialized value will be obtained. PP can still be called to initialize theinstance, and may still be called automatically by a start trap.3.3.3 Parameters to modules: DIRECTORY and IMPORTSThe interface parameters of a module are declared in the DIRECTORY list. An interface I has typeTYPE n, where n is any one of the names given before DEFINITIONS in the header of the interfacemodule that produced I it. The use of these names provides a clumsy check that the properinterface is supplied as an argument. An interface is a type which can only be used:Before a dot ( 4.14), to obtain a value from the type's cluster, which simply consists of thebindings in the interface module body ( 3.3.4).In an IMPORTS list as the type of an instance parameter to a module. The USING clause in the DIRECTORY, if present, restricts the cluster of the interface to contain onlyitems with the names nu, ... Thus in the example, only ROPE and Compare are in the cluster of Ropein the BufferImpl module. This means that Rope.ROPE and Rope.Compare are legal, but Rope.n for anyother n will be an error. Note that USING affects only the cluster of the parameter; it does not affectthe clusters of any types or the bodies of any INLINE procs obtained from the interface. Thus withinRope, Compare might be bound byCompare: PROC[r1, r2: ROPE]_[BOOL]~INLINE {IF Length[r1~=Length[r2] THEN ... }A call of Rope.Compare in BufferImpl is perfectly all right, even though Rope.Length would be anerror. f2tG4G?q _.]F[TY0X#M VATGuT hTGq PHrX Mq{q+ Ktq{q{qt Jq{q{q. Htq7{q  G {q{q)- E {qtq& D{q {q&' B{qtq{q{q ?VR ="tqr q{q },tq( {q{qy u{Otq{qX{qtq}qtqtG qX{q{q{q{qtG mq{ q{ q{ q $TVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198217In the example, CIFS, IO, and Rope are interfaces. They are the types of three IMPORTS parametersnamed Files, IO, and Rope (if the IMPORTS clause gives no name for the parameter, the name of theinterface is recycled). An actual argument for an IMPORT parameter must be an interface instance,i.e., a value whose type is an interface type. Such a value is obtained from one or more moduleswhich export the interface ( 3.3.5). An instance is a binding; in this binding the value of a namedeclared in the interface is provided by the exporter; the value of a name bound in the interface(such as Compare) is just the value that the interface binds to the name (in this case, the INLINEproc). This rule has two effects:The client can ignore the distinction between names bound and declared in the interface,since both appear in the instance binding and are referenced uniformly with dot notation.This means that the client is not affected, for example, when a proc is moved from anINLINE in the interface to an ordinary definition in an implementation.The client can often ignore the distinction between the interface and the instance, since allthe values in the interface are also in the instance, with the same names. This is themotivation for the shorthand which allows the name of an IMPORT parameter to default tothe name of the interface; the interface is no longer accessible, but Rope.Compare has thesame meaning whether Rope is the interface or the instance.Restriction: An interface module may not import more than one instance of a given interface I. If an implementationmodule P imports more than one instance of I, the principal instance of I is the one with no name in the IMPORTS list(which is therefore named I by default). If P imports only one instance of type I, then that instance is the principalinstance.Restriction: Often an interface module has no IMPORTS, because it only needs access to the static values (type, inlines andconstants) bound in its interface parameters, and does not need values for any names declared there (ordinary procs andinterface variables). If an interface module does have IMPORTS, however, and there is more than one instance of anyimported interface around, then there is a restriction on the argument values. Suppose that Int1 imports Int2, and that aprogram module P imports Int1. Then Int1 may only import one instance of Int2, and if P also imports Int2, the principalinstance of Int2 in P must be the same as the value of Int2 imported by the Int1 imported by P. For example, withDIRECTORY Int2; Int1: DEFINITIONS IMPORTS Int2V: Int2 ...DIRECTORY Int1, Int2; P: PROGRAM IMPORTS Int1V: Int1, Int2V: Int2 ...we must have in P that Int1V.Int2V=Int2.3.3.4 Interface module bodiesThe body of an interface module I is a collection of bindings (e.g., y: INT~7) and declarations (e.g.,x: INT). There are restrictions on what may follow the ~ in one of the bindings11:If it is an expression, it must be static ( ???).If it is a block (providing the body of a proc), it must be INLINE.It may not be CODE.The values of the bindings can be accessed directly by dot notation (e.g., I.y, which is equal to 7here). The declarations cannot be accessed directly (I.x is an error). The result of applying an interface module is an interface ( 3.3.2), which is a type. This type issimply the declaration obtained by collecting the declarations in the body, with a cluster which isextended to include all the bindings of the body. The bindings may not refer to names introducedin the declaration, except that:Any declared name may be usedin the body of an INLINE, or after a "_" in a defaultTC40 in the fields44 of a transferTC41 which is the type of adecl in the interface's db.A declared type may be used anywhere.The declarations in an interface module are not quite like ordinary declarations. They are of threekinds, depending on whether the type of a declaration is: f2tG4G?q _ {q{q{q&tq ^W{q{q{qtq, \)tq [OG Yrq3$ XGH V{qGt U?qR JQc,(O;N[tqAL(2J$/H /tqGwC{q{qE{q" Cv tP~t A~t#~tvt~txt @~t~t#~t ?T T  0rq 6tq q qq8 % $< 13TVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198218A transfer type; this is just like a declaration of a transfer parameter to an ordinary proc,except that it is readonly. TYPE or TYPE[e]; this is an opaque type or exported type, discussed in 3.3.4.1 below. Theexpression e must be static. These types are not allowed in an ordinary declaration.VAR T, or READONLY T for any other type T; this is an interface variable; discussed in 3.3.4.2 below. T can be written for VAR T, which is not allowed in an ordinary declaration.An interface instance II has the interface type I if for each item n: T in the interface, there is anitem n~v in the instance, and v has type T. This is the same rule which determines that a bindinghas the type of a declaration; e.g., that a proc argument has the domain type. In this respect there isnothing special about an interface.Note that a name can be declared PRIVATE in an interface, even though it must be declared PUBLICin the exporter. This can be useful if the name is used in a type constructor or inline proc in theinterface, but its value should not be accessible to the client.3.3.4.1 Opaque typesAn opaque type declaration in an interface is the only way to declare a type parameter (except forthe interface parameters declared in the DIRECTORY). Not surprisingly, any type has type TYPE; thusany type can be supplied as the argument for an opaque type declared T: TYPE. T is called fullyopaque. A type V has type TYPE[n] if:SIZE[T]=n.V has standard NEW, INIT, ASSIGN, EQUAL and ISTYPE procs. All the assignable primitivetypes do except the RC types ( 4.5.1), bound variant types ( 4.6.2), and types produced bya defaultTC40.Representation: The standard NEW proc allocates n words. The standard INIT does nothing. The standard ASSIGNcopies n words. The standard EQUAL compares n words bitwise. The standard ISTYPE compares the mark of thevalue with a single mark associated with the type.Only such a type V can be supplied as the argument for an opaque type declared U: TYPE[n]. U iscalled n-opaque.The cluster of a fully opaque type T is empty: it provides no operations. A T value cannot bepassed as a parameter, and there are no VAR T variables. Thus you cannot use T as the type in adeclaration. The only thing to do with T is use it as the range of a reference type such as REF T.The cluster of an n-opaque type U has VAR, NEW, INIT, ASSIGN, EQUAL and ISTYPE procs (the last notyet implemented). Thus these operations can be done on a U value. As a consequence, a U valuecan be passed as a parameter and declared.Restriction: All instances of any interface produced by applying an interface module which declares an opaque type Tmust supply the same type value for T if they supply any value at all; this value is called the standard implementation ofT. Because of this restriction, clients can safely interassign values of type T, no matter how obtained. In addition, it issafe for any exporter of T to convert a value of type T to a value of the argument type, and conversely. The restrictionarises from the fact that the current implementation cannot properly distinguish among the different instances, so that thedifferent values for T can get mixed up. If there is only one value, a mixup cannot compromise type safety. Two type values are the same in this sense only if they come from the same type constructor (presumably in someshared interface module, usually one which is private to the two implementors of T).It is not necessary to import an interface to refer to an opaque type declared in that interface(because of the above restriction).Within an implementation P which exports an opaque type T declared in interface I, D.T and P.T(simply T within P) imply each other. However, they have different clusters, and are not equivalent.You can convert from one to the other using NARROW ( 4.3.1). f2tG4G?q_/-^W[tqtq{q r qr qZ{ {qHX#tq{qtq{q{q rq V{qtq{q2 St{q{q{q{q Q{q{q{q {q7 Pl>& N Ktq2t J9qa H 6 DrX AqE @tq'tq >3{qtq{q r <q{q tq{q:tq{q{q8O{q tqyqyqyqtq$695G 55Gq36v t xt~tTVk(5$36pqp1qrqpq rqsq0- .bt ut&utqtutut ,vt )ut(ut (/wtutut & ut4qtut # ut utwtqtwtwtwtqt !#utut x' x qfr Uq xqrq,xq rqLrq& rqrq5 p ] rqV x\ :Krq t> qt `ututututu tutut> X)qt FTVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198219Performance: This conversion costs nothing at runtime.3.3.4.2 Interface variablesAn interface variable gives clients of an interface direct access to the variable in a program modulewhich is exported to provide its value This is the only kind of variable parameter in current Cedar.. If you use the obsolete shorthand of T for VAR T in an interface variable declaration, you cannotdeclare a transfer type variable as an interface variable, since that already means passing the transfervalue.Caution: the variable which is exported to provide the value for an interface variable is notinitialized until its module is initialized ( 3.3.2.1). However, there is nothing to stop it from beingaccessed.Performance: An interface variable can be read and (if not READONLY) set directly, which issignificantly faster that Get and Set procs. Of course, the implementor gives up some control. It isnot quite as fast as access to an ordinary variable, since there is an extra level of indirection whichcosts one or two extra instructions each time. There is also one pointer per interface variable permodule which refers to it.You can get direct access to all the variables of a module by using a POINTER TO FRAME type (4.5.3), but this is not recommended.3.3.5 Implementation module bodiesThe body of an implementation module Imp is simply a block. This block plays two roles. On theone hand, it is an ordinary block, the body of an almost ordinary proc PP called the PROGRAMproc, which has parameters and results like any other. PP is special in one way: it has a PROGRAMtype rather than a PROC type. When PP is applied (using the special construct START; see 4.4.1),its declarations and bindings are evaluated, its statements are executed, and its results are returnedas with any proc. The only difference is that the values bound to the names introduced in the block(i.e., PP's frame) are retained after the proc returns; in fact, forever (unless Runtime.Unnew is used tofree the frame). Procs local to the block can access these values in the usual way, and values ofexported names can also be accessed through interfaces, as explained below.As with any proc ( 3.5.1), PP's frame includes the parameters and results from Imp's drType as wellas the names introduced in the block's db. It also includes an additional nameImp: PROGRAM T~PPwhere Imp is the name of the module, T is its drType, and PP is the proc described above.The body of Imp has a second role: to supply values for the names declared in the interfacesexported by Imp. For each interface Ex which Imp exports, an interface value ExI of type Ex isconstructed. Each name n in ExI acquires a value as follows:If n: T is in Ex and n~x in the body of Imp, then n~x in ExI. This is a slightly peculiarkind of binding, and like ordinary binding, x must be coerceable to T ( 4.13). Also, n musthave PUBLIC access ( 3.3.6) in the body.If n is declared in Ex and not bound in the body of Imp, then n~UNBOUND in ExI.UNBOUND is a special value with the following properties:For a proc P, it causes a Runtime.UnboundProcedure signal on any aplication of P.For a variable v, it causes a Runtime.PointerFault error on any reference to v.For a type T, it causes an error on any application of T.ISTYPE (including NARROWand WITH ... SELECT). Other uses of T are perfectly all right. f2qG4G?t _v t* [vX Xt\ W-a T#utwtut& R~_ P Mvt4! LK O J Gv t/qt F utut( D^ C S A >a.qtqtqt < 8vX 5tut6 4/>ut q 2t2utq 1'tqt utqt /Z .+6 ,ut=u t +D )C &hut2ut $Ly#`utXqtutu !tututut ut,! -ut utututut  ututQututututut utututut(utut utIqtututututwtutmwt2\ ut ututKut utut :ut+utqt q tqtqtut BTVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198220If n~x in Ex, then n~x in ExI. Thus any names bound in the interface are bound the sameway in any interface value.Caution: A name can be exported to several interfaces without any warning, if it has a suitable type.This is unlikely to be what is wanted.The result of instantiating Imp is a binding B with:One item for each exported interface Ex, namely Ex: Ex~ExI, where ExI is the interfacevalue constructed above. Here Ex is the name nd given to the interface in the DIRECTORY.One item for Imp itself, namely Imp: POINTER TO Imp~programInstance, whereprogramInstance is the program instance, i.e., the frame of the module's body. This binding is accessible in a model, where it can be used to get access to the interface and frameinstances. What is the current story on executable NEW? prog from DIR: gets file name & loads.Or, copy from imported prog or PTF.Where do we put impl in DIR?3.3.6 PUBLIC, PRIVATE and SHARESCedar has a rather complicated mechanism for controlling access to names. Most uses of it are nowconsidered to be obsolete, with the following exceptions:Names to be exported must be declared PUBLIC.Names included in an interface for use in inline procs etc., but not intended for use byclients, should be declared PRIVATE.Acess to a name is declared by writing PUBLIC or PRIVATE right after the colon in a declaration of aname:x: PUBLIC TIn the Cedar syntax these colons occur in the declarations11 and bindings13 in bodies9, fields44, 47,and interface modules2, and in the tag50 of a unionTC. You can set a default access for all thenames in a module2, 3 or record46 by writing PUBLIC or PRIVATE just before the { or RECORD; this isoverridden by accesses inside. By default, an interface is PUBLIC and an implementation is PRIVATE. A PRIVATE name defined in module M can only be referenced:from within M;from a module which SHARES M; avoid this feature unless you export M.This does not mean that the name is invisible if, e.g., M is OPENed, but that it is an error to use it.Thus inx: INT; {OPEN M; f[x]}if x is bound in M (and not suppressed by a USING clause), the call of f is equivalent to f[M.x]regardless of whether x is PUBLIC or PRIVATE. It is illegal if x is PRIVATE, but it never refers to thex declared by the x: INT. Furthermore, if a record has any PRIVATE components, a constructor or extractor for the record islegal only in a module where use of the PRIVATE names is legal. f2qG4G?t_utututututut'^W [,vtF Y" V}ut utT%!utututututRut uRrRtqtPIl ututmqtqtututNutA LmZ J  Gwy$vy vy E B: >;vXxvxvx ;tC 9 /74&qt4!23Xqt 0-"qtqt' .y-%utXqGu +t$+z+t +z+t +z+t+z+t **cz*t*cz*t! ( (z(t (z(t qtqtqt ' 1qtqt #qtut! ut:qtut'ut vt+utqt& ^yutXqtqtututut Vut utqtututut  utqtqtutqt Nututqt # qt9 #qt TVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 1982213.4 Blocks, OPEN and ENABLE 4 block ::= attributes { ?open ?enable bodyopen LET n((, ... : EXCEPTION~NEWLABEL[] , ...?(EXITS (n, !..=>s); ...) } IN ( body enable ) BUT { (n((, ... => s ); ... } In 3, 13, 15.-- n(( is not visible in s. 5 attributes ::= ( CHECKED | UNCHECKED | TRUSTED ) ... 6 open ::= OPEN ( n ~~ e | e ), ... ;( LET n~lopen IN e.DEREF | --The final IN is a separator.In 2, 4, 17. The ~~ may be written as :. LET BINDN[D(e.DEREF).NAMES, OPENPROCS[D(e.DEREF).NAMES, l IN e.DEREF] ] ) IN ... 7 enable ::= ENABLE (eChoice | {eChoice; ...});BUT ( { eChoice } | { eChoice; ... } )In 4, 17. 8 eChoice ::=(e | ANY), !.. => s(e | ANY), ... => { s; REJECT }In 7, 26. 9 body ::= ?( db; ... ;) s; ...LET NEWFRAME[ [db, ...] ].UNCONS IN { s; ...} In 4, 17.10 db ::= d | bIn 2, 9.CHECKED { -- Unnamed OPEN OK for exportedOPEN Buffer, Rope; -- interface or one with a USING clause.ENABLE Buffer.Overflow=>GOTO HandleOvfl;-- A single choice needn't be in {}.stream: IO.Stream~IO.CreateFileStream["B"];-- Use a binding if a name's value is fixed.x: INT_7; -- Better to initialize declared names.{OPEN b~~GetBuffer[stream];-- A statement may be a nested block. ENABLE {-- Multiple enable choices must be in {}.CIFS.Error[--error, file--]=>{-- ERRORs can have parameters.stream.Put[IO.rope[error]]; ERROR Buffer.Error["Help"] };-- Choices are separated by semicolons.ANY=>{ x_12; GOTO AfterQuit } };-- ANY must be last. ENABLE ends with ;.y: INT_9; ... };-- Other bindings, decls and statements.x_stream.GetInt; ...-- Other statements in the outer block.EXITS-- Multiple EXIT choices are not in {}.AfterQuit=>{...};-- AfterQuit, HandleOvfl declared here, HandleOvfl=>{...} };-- legal only in a GOTO in the block.The main function of a block is to establish a new scope ( 2.3.4) and to allow for the allocation ofvariables declared in the block, as in Algol or Pascal. A Cedar block has four other features:attributes5: CHECKED, UNCHECKED and TRUSTED are treated in 3.4.4 on safety.open6: a combination of sugar for LET and call by name; see 3.4.2.enable7: catches signal and error exceptions in the body; see 3.4.3.1.EXITS: catches GOTO exceptions in the body or enable; see 3.4.3.2.Note that the braces around a block may be replaced by BEGIN and END ( 3.2).3.4.1 Scope of names and initializationThe names introduced in the block body's db (i.e., appearing before a : or ~) are known in thebody with the values supplied by the db, except in inner scopes where they are reintroduced; theyare not known elsewhere in the block. The frame of the block is a binding with a value for eachsuch name.Actually, the frame is a value of an opaque type which has a coercion (called UNCONS) to this binding. As the desugaringfor body indicates, the frame is constructed (by NEWFRAME), and then a LET makes the names in the binding known inthe statements of the body. f2qG4G?t _{X|{| \z>{tX{t {t{t *{*\x,\twt{}t{twtwt{ [,qt{t{t{t*wt,+Zy,[,{,Z/[,t{0Z3[,t44Zy4[,wt{}t{t{t{t{t YqG *tX}t{t X$z>{ Xt{tqt{tqt{t VqG{q{ Uz>{Xqt{t{t{t{t*{twt{t~TrUtwqG{twtX{twt S.qG'*wtXwtwt}t2Ry2S.{twt7?Ry7S.wtqG*QtXqGtXwt}{tw{twt~twt{twqG{tXwqG{q P&z>{Xtqt{t{t {t{t*wt{t{.yO34P&t{t{6LO;P&t{t{ NqG Mdz>{Xt{tq{t *{t{tq{t{t{tqt L&qG Jz>{Xt{t{t{t{*wtwt{t{twtwt{t{t IdqG Gz>{Xt{t FqG CwtX* qt Aqt*qt @oqtqt *$ >+*, =gqt*'y;qt*%y:_qt*)8*qt:7W:5qt*'4Oqt qt*qtqt y2qt{t*( 1G{*t' /q*t qt vty.? {t*utu ty, {t*qt )F ( U% %z%tqtqtqt"#\#z#\twt!!Jz!tAqt qt1 7qtqt vX" WtD A O'vt  qEpq# .pq pq% j ~TVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198222Anomaly: A name introduced by a binding, n: T~e, has the value of e throughout the body if e isstatic. If e is not static, it is evaluated after all preceding db's, but before any following ones. Thismeans that n is trash in all the db's before its binding. Symmetrically, if e refers to a nameintroduced in a following decl or non-static binding, it will get a trash value. Compiling with the ???switch will cause a warning in this case. Note that only attempts to obtain the value of n yield trash;n may appear anywhere in a l-expression, and all will be well as long as the l-expression is notapplied before n's binding is evaluated.A name introduced by a declaration, n: T, is bound to a new VAR T. The variable bound to n isallocated, and its INIT proc executed (to set a REF or transfer value to NIL) before anything in theblock is executed (this is done by the NEWFRAME proc in the desugaring). Anomaly: However, any initialization specified by a defaultTC40 in T is done at the same time thata non-static binding would be evaluated. As with a binding, n is trash before this time.Furthermore, any (unwise) assignment to n before this time will be overriden by the defaultTC.The expression in a binding or defaultTC should be functional, or at least it should have onlybenign side-effects. There is no enforcement of this recommendation, unfortunately. In currentCedar such an expression is evaluated exactly once, at the time described above. This may changein the future, however.The variables created by a declaration are deallocated when execution of the block is complete,unless the block's frame is retained. Currently only an implementation's block3 has its frameretained. There are two ways to hang on to a variable v after execution of the block is complete:Obtain a pointer to v with @; this pointer value can survive the block.Obtain a proc value for a local procedure which refers to v; this proc value can survive theblock.In the checked language both these dangling references are impossible: the @ operator, beingunsafe, is forbidding, and ASSIGN for proc values gives an error unless the proc is local to aprogram instance (which has a retained frame). An unchecked program can get into trouble,however.Performance: There is no overhead associated with block entry or exit, even if the block has anopen, enable or EXITS. The only cost is for initializing its names. It is good style to use blocks freelyto limit the scope of names.3.4.2 OPENThere are two forms of open. The first, n~~e, binds the name n to lopen IN e.DEREF. This is just likel IN e.DEREF, except that there is a coercion from n to n[]. In other words, every time n appears, itsvalue is obtained by evaluating e.DEREF. The effect is exactly like call by name in Algol; the ~~ isto remind you that this is not ordinary value binding. The value of e.DEREF is e if the cluster of Dedoes not have a DEREFERENCE proc, or e^.DEREF if it does. In other words, a reference value isdereferenced, repeatedly if necessary, to obtain a non-reference value. In an open, e.DEREF must bea record, interface or instance.The scope of an open is all the rest of the block, including any enable and any EXITS. A singleopen may have several bindings. These are applied sequentially, so that the names bound by earlierones are known to the later ones as well as to the rest of the block.The second, nameless, form of open gives an expression without binding it to a name: { OPEN e;...}; e must evaluate to a binding b:A record value has a corresponding binding (returned by UNCONS in the desugaring) whichhas the names of the record fields are bound to the field values (or variables, for a VARrecord). f2qG4G?t _vt!ututut utut ^Wut%8 \ut 4ut [O F YI ut XGut~t1~t Vut S"ututwtutut R wtqtqt P"wt Mevt&MzMetut K;ut J] ut5 G2V EA D*; B ?{O = vt*>=z=t . If ANY appears, it must be in the last eChoice. If the exception is equal to one of these values,or if ANY appears, the statement after the => is executed. Control leaves this statement in one ofthe following ways:A REJECT statement causes the exception to be the value of the block; it will then bepropagated within the enclosing block, or if the block is a proc body it will be propagatedto the application.A GOTO statement sends control to the matching choice in the EXITS. There are threespecial cases:A RETURN is not allowed in an eChoice.A CONTINUE statement ends execution of the current statement (in this case theblock); execution continues with the next statement following. If the block is a procbody, the effect is the same as RETURN. You cannot write CONTINUE in a body'sdb.A RETRY statement begins execution of the current statement (in this case theblock) over again at the beginning. You cannot write RETRY in a body's db.The semantics of CONTINUE and RETRY follow from the desugaring of statement14.A RESUME statement (signals only) is discussed below.If the statement finishes normally, a REJECT statement is then executed.If a single expression with value v appears before the =>, then within the eChoice statement thenames in v.DOMAIN are declared and initialized to the arguments of the exception. With multipleexpressions, or ANY, the arguments are inaccessible. The use of ANY is not recommended. f2qG4G?t_5 ]utut~\r]t [ utwtyZutXqGtutXqtutqtututyXqtut W utut =u Utut RZvt9 P -) OR0% M4 IvXxvx Ftqtqt&q E t2qt CqtP B5 >vXx :tJ 9j:9z9jt 7 45z4t2qt 37qtF 1qt!8 0/-qt2,S F *(wqt6qt&$qt"qt$!MIqtqt E4qt </qtqsqsq(+sqtqt-5'qt  ut! utwt1  qt.qt JTVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198224FinalizationYou are supposed to think of an ERROR as an unusual value ev which can be returned from anyapplication; this value immediately stops the evaluation of the containing application, whichlikewise returns ev as its value. This propagation is stopped only by an enable choice which catchesthe ERROR. As each application is stopped, it is finalized. Aside from invisible housekeeping,finalization confusingly consists of executing the statement in an eChoice which catches the ERRORUNWIND. The programmer can write any cleanup actions he likes in this statement. If thefinalization raises another ERROR which it does not catch, it will itself be stopped, with veryconfusing consequences. It isn't very useful to know exactly what happens then: avoid this situation. Caution: In fact, things are a bit more complicated. When a signal or error is propagated, theeChoice statement is called as a proc from the SIGNAL or ERROR which raises the exception. Whencontrol leaves the statement by a GOTO (or CONTINUE, RETRY or LOOP), the finalization is done.This means that the eChoice statement is executed before any finalization. This is useful for signals,which often resume. In some cases, however, notably if finalization would release monitor locks, thiscan cause trouble. Avoid the problem by exiting from the enable immediately with a GOTO.Caution: An eChoice can raise a second exception ex2 and fail to catch it. This will probably resultin confusion, and should be avoided. If it happens, ex2 is propagated just like the first exceptionex1; all the eChoices which saw ex1 will see ex2. This is because the eChoice statement for ex1 wascalled as a proc. Unless ex2 is a signal which is resumed, the eChoice which caught ex1 will befinalized and abandoned.Caution: ANY unfortunately catches UNWIND, and hence its statement will be taken as thefinalization. It is better not to use ANY. Also, it is possible to raise UNWIND explicitly; don't.SignalsIncomplete3.4.3.2 EXITSAn EXITS construct (confusingly called REPEAT in a loop) declares one or more exceptions which arelocal to its block, and also catches them. The syntax is just like an enable. However, names calledlabels appear before the => rather than expressions, and the EXITS introduces these names in ascope which includes the block body and any enable, but not an open and not the statements in theEXITS itself. A label may only be used in a GOTO statement.Anomaly: Actually labels have their own name space, disjoint from the other names known in theblock. Hence it is possible to declare a label n and still to refer to another n in the block. Avoid thisfeature.Like the raising of any exception, a GOTO n stops execution of the current statement. The statementassociated with n is executed. If it finishes normally, execution continues after the block in which nwas declared. If it raises an exception, that exception becomes the value of the block.3.4.4 SafetyA SAFE proc has the property that if the safety invariants hold before it is called, they also holdafterwards. Roughly, these invariants ensure that the value of every expression has the syntactic typeof the expression, and that addresses refer only to storage of the proper type ( 4.5.1). An unsafeproc may lack this property. Hence a safe proc type implies the corresponding unsafe one.We want to have confidence that the safety invariants hold. To this end, we want to have: f2qG4G?t _v \tqtut [, /" YutQ X$qtvt$ V &+q Ut%+ S qt( R] Nvt: Me(qtqt! Kqtqtqtqt J](vt. HT GUPqt D*vt ut1 B2ut A"utut ut-ut ?ut8ut > :vtqtqt. 9k qtqt 5lv 1y -vXx *tqtqt5 )LG 'vt7qt &DV $qt'qt !vt$2 )ut ut  bqtut8  utTu ZtT [vX 0tqt";  !: (10 U yY TVk(CEDAR SYNTAX AND SEMANTICS, PART 1DRAFT OF JULY 20, 198225as few unsafe procs as possible;a mechanical guarantee that a proc is safe, if possible.Clearly, a proc whose body calls only safe procs will be safe. Applying this observation, Cedar provides three attributes which can be applied to a block:CHECKED: the compiler allows only safe procs to be applied; hence the block isautomatically safe, and any proc with the block as its body is safe.UNCHECKED: there are no restrictions on the block, and it is unsafe.TRUSTED: there are no restrictions on the block, but the programmer guarantees that itpreserves the safety invariants; the compiler assumes that the block is safe. This is arestricted form of LOOPHOLE.These attributes are defaulted as follows. A block is checked if its enclosing block is checked; otherwise it is unchecked.If CEDAR appears in the module header, the outermost block is checked, and a transfer typeconstructor anywhere in the module defaults the SAFE option to TRUE. Hence the resultingtype will be safe, and its initialization must be safe or there is a type error.Otherwise, the outermost block is unchecked, and a transfer type constructor anywhere inthe module defaults the SAFE option to FALSE. Hence the resulting type will be unsafe, andthere is no safety restriction on its initialization.Of course you can override these defaults by writing CHECKED, UNCHECKED or TRUSTED on anyblock, and SAFE or UNSAFE on any transferTC. The defaults are provided to make it convenient to:write new programs in the safe language;continue to use old, unsafe programs without massive editing. An unsafe proc value cannot be bound to a name declared with a safe type. This applies to enablechoices and signals as well as to procs. In both cases, the body must be checked or trusted if thetype is safe. ERRORs (including UNWIND) are treated differently, however, because of the view thatan ERROR is a value returned from an application, unlike a signal which calls the eChoiceexpression. Hence the eChoice for an ERROR is treated just like any statement in its enclosing block,and is not considered to be bound to a proc when the ERROR is raised.The following primitive procs are unsafe:@, DESCRIPTOR and BASE.^ or FREE applied to a pointer, and all pointer arithmetic.withSelect34.APPLY for process and port types (JOIN and port calls).LOOPHOLE which produces a RC value ( 4.5.1).APPLY of a sequence or sequence-containing record.The fields of an OVERLAID union.ASSIGN of:An unspecified type to anything other than the same unspecified type ( 4.9).A union or variant record.A proc, if the value being assigned is local to another proc, rather than to animplementation. Such a proc value also cannot be passed as an argument to FORK. f2qG4G?t_]8 [+> X\Uqt9 T$ 7Qqt;Otqt DM3Ll qt IA+FPDqtRC $qt qtAL?1 6=qt qt #<)0 93qtqtqt 8MqtqtG5(3> 0r5) .L -j qt qt; +qt@vt *b qt+ (2qt %)#[q tqt!qt2 ztSwtqtqt%wt-KqtwtM K <;qt TVk(8 CEDAR DESUGARING TEXT, PART 2JULY 18, 1982263.5 Declaration and binding11 declaration::= n, ... : ?access varTC39( n: varTC ), ...In 10, 44. READONLY only for interface variable.12 access ::= PUBLIC | PRIVATEIn 2, 3, 11, 13, 46, 47, 50.13 binding ::= n1 ?( , n2, ...) : ?access (( -- The desugaring for n2 is at the end.t ~ e |n1: t~e |TYPE ~ t2 | n1 : TYPE ~ t2 -- Same as e except for conflicting syntax. |t ~ CODE |n1 : t ~ NEWEXCEPTIONCODE[] --tgSIGNAL or ERROR | t ~ (ENTRY | INTERNAL | INLINE)... block4 | n1 : t~l [d(: t.DOMAIN] IN LET rb(~NEWFRAME[t.RANGE] IN (LET rb( IN {t.DOMAIN~d(; block; RETURN} BUT {RETURN(=>rb(}) |t ~ MACHINE CODE { (e, ...); ... }n1 : t~MACHINECODE[(BYTESTOINSTRUCTION[e, ...]), ...])) ?( , (n2: t~n1), ... ) -- e is evaluated only once.Block or MACHINE CODE only for proc types. In 10. The ~ may be written as =. ENTRY and INTERNAL may be written before t.HistValue: TYPE;-- An exported type in an interface.Histogram: TYPE~REF HistValue;-- A type binding.baseHist: READONLY Histogram;-- An exported variable in an interface.AddHists: PROC[x, y: Histogram] -- An exported proc in an interface.RETURNS [Histogram];LabelValue: PRIVATE TYPE~RECORD[-- PRIVATE only for private stuff in an int. first,last:INT,s:ROPE,x:REAL,f,g:INT,r:REF INT];Label: TYPE~REF LabelValue;Duration: PROC[l:Label] RETURNS[INT]~-- An inline proc binding in an interface.INLINE { RETURN [l.lastl.first] };-- Decls in an implementation of this interface.H: TYPE~Histogram11; Size: INT~10;-- A TYPE and an INT binding.HistValue: PUBLIC TYPE~ARRAY [0..Size]OF INT;-- PUBLIC only for exported names.baseHist: PUBLIC H_NEW[HistValue_ALL[17]];-- An exported variable with initialization.x, y: HistValue_[ 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0];Setup: PROC[bh: Handle4, a: INT, b: LIST OF H]~ENTRY {...};-- An entry proc.FatalError: ERROR[reason: ROPE]~CODE;-- Binds an error.i,j,k: INT_0; p,q: BOOL; lb: Label; main: Handle;Declarations are explained in 2.3.7. Their peculiarities in the different contexts where they canappear are explained elsewhere:interfaces in 3.3.4;blocks in 3.4.1;fields in:domains and ranges in 4.4;records in 4.6.1;unions in 4.6.3.Bindings are explained in 2.2.5. There are several special forms of binding given in rule 13,however, which are defined here. See also 3.7 on argument bindings.A TYPE binding is the only way in which a type value can be bound to a name, since typescannot be passed as parameters. Unlike other bindings, this one expects a type36 rather thanan expression19 after the ~. f2qG,G?t _{X \z>{q {tX{t{t \z*\{t{t{t{t{ [rqG. Yz>{Xtqt{tq XG W,z>{q{XtVzW,t{tVzW,t{t{t{*{tVzW,t U>{*{TzU>t{t{t{ SPqtRzSPt{t*{RzSPtqt{1 Sy1RzSPt {t{ Qbtqt{*{PzQbt{twt}qtqt{ Ott{qt{tqt{tq{qGtOzOttX{t*{NzOtt{t~t}t{twtwtwt}twt{twtwqGtXqG*Mt*MNy+MwtX}twt{twt}t{tqtwqGtw}t}tPIMNyPMX{ LtqGtX{t{t{t*{KuzLt{tw t{wt{t{t{t{t J{*{t{t{IzJt{t{IzJ{t{t{t H&qGtXqG F# E, Bt Xqt*$ @ qtqt * ?w qt *( = qt*$ q/<=!s +}N )U (u(qt &qt %m~t0 #qt qtqtwtqtutu :t%qtwt O v t/( `N W X\ &  qtqtqt %  qt1 vA" H n7qtTVk( CEDAR DESUGARING TEXT, PART 2JULY 18, 198228It may not be recursive.It may not be used as a proc value except in an application. Thus you cannot, for example,assign it to a proc variable.It may not be the argument of FORK.It may not be exported.It may not be accessed from the cluster of a POINTER TO FRAME type.Performance: Excessive use of inline procs will result in much larger compiled code and muchlarger data structures in the compiler. The following cases are efficient:An inline proc in an implementation which is called exactly once.An inline proc which has a simple body, no locals, no named results, and no side effects.3.6 Statements14 statement ::= sS{SIMPLELOOP {sS; CONTINUE; EXITS RETRY((=>NULL};In 4, 9, 17, 19. EXITS CONTINUE((=>NULL } 15 sS ::= e1_e2 | e | block4 | control | loop | NULL[e1_e2].TOVOID | e --must yield VOID-- | --all yield VOID--16 control ::= GOTO n | GO TO n | EXORVAL[exception[code~ n((, args~ NIL]] |EXIT | CONTINUE | LOOP | RETRY |GOTO (EXIT | CONTINUE | LOOP | RETRY ) |REJECT | (RETURN | RESUME) e | THISEXCEPTION[] |{VALUEOF[rb(]_e;(RETURN|RESUME)}|(RETURN | RESUME) | EXORVAL[exception[code~(RETURN|RESUME),args~NIL]] |e _ STATEDUMPSTATE[e]17 loop ::= (iterator | ) { ( iterator ; | done(~FALSE, Next(: PROC~{}; )(WHILE e | UNTIL e | ) Test(~l IN (NOT e | e | FALSE);DO ?open6 ?enable7 body9 { open SIMPLELOOP { IF Test([] OR done( THEN GOTO FINISHED; { enable body EXITS LOOP=>NULL }; Next([] }?(REPEAT (n, !..=>s); !..) ENDLOOP EXITS EXITgNULL; (n, !..=>s);!..; FINISHEDgNULL}}18 iterator ::= THROUGH e | FOR x(: e IN e |FOR (n : t | n) ( n: t; | ) ( ( | DECREASING) IN e | done(: BOOL; Range(: TYPE~e; Next(: PROC~{ IF n ( >LAST | RETURN[0]; []_f[3]; ...};-- or a block,IF i>3 THEN RETURN[25] ELSE GOTO NotPresent;-- or an IF or a control statement,FOR t:INT DECREASING IN [0..5) UNTIL f[t]>3 DO -- or a loop. Try to declare t in the FOR asu: INT_0; ... ; u_t+4; ...-- shown. Avoid OPEN, ENABLE after DO REPEAT Out=>{...}; FINISHED=>{...} ENDLOOP;-- (use a block). FINISHED must be last.THROUGH [0..5) DO ... ENDLOOP;Cedar makes a distinction between expression and statements. This distinction is most easilyunderstood in terms of a special type called VOID. This is the range type of a PROC [...]_[], and it isalso the type of a block, control, loop or NULL statement. An expression whose value is a VOID can f2qG,G?t_]P[YqtWOT-qtqtqt Qv t#- PHDMAKY F{X Cz>{q{Xt*w t{tqtqGtXw}tqt BqG *tXqtw}tqt @z>{Xt@z@t@z@t{t{t@z@t{t{t{tq*t{@z@t{@z@twt{t{t qt{t qt >z>{Xtqt{tqGtX{t*wt{}tqt{ = qt{tqt{tqt{tqt{*qG{wtX{twt{twt{twt{t{ ;qt{t{qt{tq{t{t*w t{twt}t{t{q{q{t{ :qt{tq{t{t*wt{w{w{tqt{ 8tq*wt{t 5iz>{Xt{t{t{t*{t{+51m0P5it{t}tqt}tqt{ 3qt{tqt{t{t*}t~twt{qt{t{t{t{tq{t 2aqt{t2z2at{t2z2at2z2at*{,2).2atw t*0 qt}tqt}tqtqtqt*/Y{t{tqtwtqt}t -{t{qt{t{t{tq*tqtw}qt{t{tq}qt *z>{Xtqt{t*qt**rq-y*}t{tqt{-*r1*t{ )&qt{t{t{t*{t{t{t{t{ 't{t{t{tq {tqt{t*}tqt}tqt{t*&}tqtqG{tX{tqt{tqt{t}t*$qt}tqtqG{t{qtX{tq{t{t*#{t{qt{tq{t}t}t{tqGtX}t{ !t!z!t!z!{*t}tqtqt}tqt{t{!z!t{t{!z!t{t qG^ tX * <qt{t* qt qt{t* 4qtqtqtqtqt *qt  qtqtq tqtqtqt* qtqGutXqt qt{t {*tqtqtqt qGtXqt{tq t{tqt*qt qtqt{tqt H ' #wt qt}t 'qt(wt TVk( CEDAR DESUGARING TEXT, PART 2JULY 18, 198229be used as a statement, and cannot be used as an ordinary value in a binding (since it wouldn'thave the right type). If you want to call a proc which returns values as a statement, you must assignthe results to an empty group:[]_f[...]Assignment is a special case; an assignment can be used as a statement even though its value is thevalue of the right operand. This is explained in the desugaring15 using a special proc TOVOID in thecluster of every assignable type; it takes a value of the type and returns a VOID.Anomaly: In a select29 which is a statement (i.e., returns VOID), the choices are separated bysemicolons; in an ordinary select expression they are separated by commas.Anomaly: If you write an expression whose value is a proc taking no arguments as a statement, theproc gets applied. ThusP;is the same asP[];This is the only situation in which an ordinary proc gets applied by coercion (but see 3.4.2 foropen procs).A statement14 is actually a more complicated construct than you might think, as the desugaringshows. This is because of the CONTINUE and RETRY statements, which respectively terminate andrepeat the current statement. The desugaring shows exactly what this means in various obscurecases. CONTINUE and RETRY are legal only in an enable choice ( 3.4.2), and they may not appear ina declaration at all. RETRY should be avoided everywhere, since it introduces a loop into theprogram is a distinctly non-obvious way.Control16 consists mainly of the various flavors of GOTO (including EXIT, CONTINUE, LOOP, RETRY,RETURN and RESUME) which raise a local exception bound in an EXITS; this is explained in 3.4.3.2.REJECT is explained in 3.4.3.1. Anomaly: Note that you cannot use a GOTO to escape from a proc body, even though the body iswithin the scope of the label. Only normal completion, or a RETURN or ERROR exception (or aSIGNAL which is not resumed) can terminate a proc body.A loop17 is repeated indefinitely until stopped by an exception, or by the iterator18 or the WHILE orUNTIL test. It has a body, bracketted by DO and ENDLOOP, which is almost like a block, but withsome confusing differences: You catch GOTO exceptions with REPEAT, which is exactly like EXITS in a block immediatelyaround the loop,except for the different delimiting reserved word. Note that the scope ofthe labels does not include the iterator or the test, even though these are evaluatedrepeatedly during execution of the loop. This feature is best avoided, but unfortunately isnecessary if you want to catch the FINISHED exception explained below.You can write an open or enable. This is also best avoided, since the scope is confusing. Itis better to write a block explicitly inside the DO if you need these facilities.There are three special exceptions associated with loops:EXIT is equivalent to GOTO EXIT, where EXIT is a label automatically declared in the REPEATof every loop. Its enable choice does nothing. Thus EXIT simply terminates the smallest loopthat encloses it.FINISHED is raised when the iterator or the WHILE/UNTIL test terminates the loop. It can bedeclared in the REPEAT like any label, but it must come last. If it is not declared, a nullenable choice is supplied for it. Anomaly: You cannot write GOTO FINISHED.LOOP causes the next repetition of the loop to start immediately. f2qG,G?t _7& ^W:' \y[Out X$ "vt4 V:VzVtwt UFwt Qvt R7zQtwt Pm ? MBvt L KyJ:ut H yG2ut E5) D* @ AEz@t8 ?{qtqt- =< last. DECREASING reverses the orderin which the elements of the subrange are used. The subrange need not be static. Note thatthe subrange is evaluated only once, before execution of the loop begins.FOR v: T_first, next ...; v is initialized to first, and set to next after each repetition. Thisiterator never stops the loop. Note that the expression next is reevaluated each time aroundthe loop. The usual application is something like FOR v: List_header, v.next UNTIL v=NIL.Note that the WHILE test is made with v equal to its value during the next repetition, and that bothtests are made before the first repetition, so that zero repetitions are possible.3.7 Expressions19 expression ::= n | literal57 | (e) | application26 |e . n |LOOKUP Z [De, $n] [e] |builtIn [ e1 ?( , e2, !..) ] | funnyAppl e |e1 . builtIn ?( [e2, ...] ) | e . funnyAppl( |prefixOp e | e1 infixOp e2 | e1 NOT relOp e2 |e . prefixOp | e1 . infixOp[e2] | NOT (e1 . relOp[e2] ) |e1 AND e2 | e1 OR e2 | IF e1 THEN e2 ELSE FALSE | IF e1 THEN TRUE ELSE e2 |e ^ | STOP | ERROR |e . DEREFERENCE | STOP[] | ERROR NAMELESSERROR |[ argBinding27 ] | s |--Binding must coerce to a record, array, or local string-- |subrange | if | select | safeSelect |withSelect Precedence is noted in bold in the operator rules. All operators associate to the left except _, which associates to the right. ^, . and application have higher precedence than any Op. AND has precedence (2) and OR has precedence (1). Subrange only after IN. s only in IF28 and in SELECT29 choices.20 prefixOp ::= @ (8) | (7) | (~ | NOT) (3)VARTOPOINTER | UMINUS | NOT21 infixOp ::= * | / | MOD (6) | + | (5) | relOp (4) | _ (0)TIMES | DIVIDE | REM | PLUS | MINUS | relop | ASSIGN22 relOp ::= = | # | < | <= | > | >= | IN -- In 19, 21, 30.EQUAL | NOT = | LESS | NOT > | GREATER | NOT < | IN23 builtIn ::= -- These are enumerated in Table 45.24 funnyAppl ::= FORK | JOIN | SIGNAL | ERROR | NEW | START | RESTART | WAIT | NOTIFY | BROADCAST | RETURN WITH ERROR |TRANSFER WITH | RETURN WITH25 subrange ::= (typeName37 | ) (LET t(~(typeName | INT) IN (( [ e1 .. e2 ] | [ e1 .. e2 ) ) | t(.MKSUBRANGE[e1, (e2 | PRED[e2] )] BUT {BoundsFault=>t(.MKEMPTYSUBRANGE[e1]} |( ( e1 .. e2 ] | ( e1 .. e2 ) ) ) t(.MKSUBRANGE[SUCC[e1], (e2 | PRED[e2] )] BUT In 19, 39, 55 {BoundsFault=> t(.MKEMPTYSUBRANGE[SUCC[e1]] } )26 application ::= e [argBinding LET map(~e, args(~[ argBinding ] IN ( ?( ! eChoice8; ...)] (map(. APPLY Z args( ) ?( BUT { eChoice; ... } ) )27 argBinding ::= (n ~ (e | | TRASH )), ... |(n ~ (e | OMITTED | TRASH) ), ... |(e | TRASH | ), ...(e | OMITTED | TRASH ), ... f2qG,G?t _`!z_tvtut< ^W ut? \)ut/ [OY Y V$THqt)qtutR utPlqtututqtutututut qtutN &u}utq tMd?KFIqtutututututut utH0utF/DqtXutututututqtutqt A qtutvt @MM ;z{X 8Oz>{q{Xt{t8z8Ot{t$8y8OB8y8O{t 8z8Ot{ 6t{*wt}t}{t{t{t{ 5Gt 4z5Gt{t4z5Gt{t{t {*{4z5Gt{t{t{4z5Gt{t{t{t{t{}t{ 3Yt {t2z3Yt 2z>3YtX{t2z3Ytqt2z>3YtX{*{t{+3!503Yt{t{2z3Yt{43!z83Yt{2z3Yt{tqt>V3!y>3Y{2z3Yt{@3!\DR3Yt{2z3YtF3!yG 3Y{ 1kt0z1ktqt0z>1ktX{t0z1ktqt0z>1ktX{t*qt{0z1ktqt{0z1ktqtqt{tqG{0z1ktXqtqtqG{0z1ktX{ /}t{tqt{tqt{*{tqGw tX{twt{tqGw tX{ -t .?z-t{t{*t={ ,ut{t{t{t {t +7q Gi )\|q ( |q')z(q )z(q %z>{Xtq|qt{tq|qt{t{t{tq{tq|q*w t{twt{tw $ z>{Xt "{t{tqtq|qt{t{tq|qt{tq|qt{tq|q*wt{twt{twt{twt{twt{t{?"PB"t{tw !z>{Xt {t{t{t{t{t{tqtqG*wtX{tqt.H73{twt{tqt7H;{{twt{tqtBHFi{tw z>{Xt& xz>{Xtqt{tqt{tqt{tqt{tqt{tqt{tqt{tqt{tqt{t qt{tqG tX{tqGtX{tqG z>{Xt{tzt{t{tqG{*wtX}t{t{tq{qGwq{ EtXzEtzEt{tzEtzEt yE{t{*t}tw t{zEt{zEt{tqt{zEt{twt*W}twt{zWt{ it 1ydizitzit{t1yizitzit<1yi{t{*t}tw tqt{zit{zit{tqt{zit{twt {qG *tX}twtqt{z{t{ Pz>{ Xt*wt}t{t}t{ 67 s< Ptwt? y@ P  {t z t{t*+h y+ }tqGwtX}t}t7 y8` {twt{= B t{t{tF y Hz>{ Xt{t{t{t{tqt{t{t{*{t{t{twt{tw{qG{tX{t{ t{tqt{t{t{*{t{twt{twqG{tX{ jTVk(e CEDAR DESUGARING TEXT, PART 2JULY 18, 198231In 19, 26. The ~ may be written as :. TRASH may be written as NULL.lv: LabelValue13_[ i, 3, "Hello", 31.4E1, (i+1),-- A constructor with some sample g[x]+lb.f+PRED[j] ];-- expressions.p1: PROCESS RETURNS [INT]_FORK f[i, j];-- FunnyAppls take one unbracketted arg;ERROR NoSpace; WAIT bufferFilled;-- many return no result, so must be stats.RT: RTBasic.Type_CODE[LabelValue13];h[3, NOT(i>j), i*j, i_3, i NOT >j, p OR q, lb.r^];-- An application with sample expressions.lv19_[first~0, last~10, x~3.14, g~2, f~5];-- Short for lv_LabelValue13[...].[first~i, last~j]_lv19;-- Assignment to a VAR binding (extractor).b: BOOL_i IN [1..10]; FOR x: INT IN (0..11) DO ...;-- Subrange only in types or with IN.b_( c IN Color45(red..green] OR x IN INT[0..10) );-- The INT is redundant.fh_Files.Open[name~lb.s, mode~Files.read-- Keywords are best for multiple args.! AccessDenied=>{...}; FatalError=>{...}];-- Semicolons separate choices.(GetProcs[j].ReadProc)[k];-- The proc can be computed.file.Read[buffer~b, count~k];-- WFile.Read[file, b, k] (object notation).f[i~3, j~ , k~TRASH]; f[i~3, k~TRASH];-- j and k may be trash (see defaultTC40).f[3, , TRASH];-- Likewise, if i, j, and k are in that order.Most of the forms of expression are straightforward sugar for application: prefix, infix and postfixoperators, explicit application of a primitive function, or the funnyAppl24 in which the firstargument follows the proc name without any brackets. All of these constructs desugar into dotnotation ( 2.4.4, 4.14); this means that the procs come from the cluster of the first argument. Theexceptions to this rule are ALL, CONS for variant records and lists, LIST, and the single-argumentforms of LOOPHOLE and NARROW; all of these get the proc from the target type of the expression (4.2.4). All the primitive procs are described in Chapter 4.Note that AND and OR are not simply sugar for application. Rather, they are sugar for an ifexpression, since the second operand is evaluated only if the first one is TRUE or FALSE respectively.Rules 19-21 give the precedence for operators: @ is highest (binds most tightly) and _ is lowest.All are left-associative except _, which is right-associative. The ^, . and [] (application) constructshave still higher precedence. These rules are sufficiently complex that it is wise to parenthesizeexpressions which depend on subtle differences in precedence.The first operand of assign can be an argBinding27 whose value is a variable group or binding, i.e.,one whose elements are variables; this is sometimes called an extractor. The second argument willtypecheck if it coerces to a group or binding with corresponding elements which can be assigned tothe variables. Usually the second argument is either an application which returns more than oneresult or a record constructor.Anomaly: In the second case, the fact that the order of evaluation in an expression is not defined isover-exploited: some of the variables may be changed before all the elements of the constructor areevaluated.A funnyAppl which takes more than one argument has the extra arguments written inside bracketsin the usual way; e.g., START P[3, "Help"]. Anomaly: Enable choices are legal only for the following: FORK JOIN RESTART START STOP WAIT.You can write empty brackets if neccessary to get a place for the eChoices.A subrange25 denotes a subrange type. Standard mathematical notation for open and closedintervals is used to indicate whether the endpoints are included in the subrange. A subrange canalso be used after IN in an expression or iterator; in these contexts it need not be static. f2qG,G?t `"q' ^ [tX [z[t!*" Z5 qt* Xqtqtqtqt*( W-qt qt *+ Uqt UzUt T%qtqtqt ** RRzRt&* utu RzRt{t QQczQt*qt Mqtqt qtqtqtqt*"qt LnqtLzLnt qtqtqt *qt IC(*' G{t* F;* D*}ututututut C3 qt qt*ututCyzC3t Aqt*ututut >E = ?=Fz=t ;|Q 9#; 8t qtqt qt 6qtqt%v t 5l4 2Aqtqtvt? 0 @qtqt -> ,H *)5 ) 2 %&!z%t2 $W;vt "F !O'5  vt:# ,(  m5( qtut vtqtqtqtqtqtqt :H  Uz tE 7 qtGFTVk( CEDAR DESUGARING TEXT, PART 2JULY 18, 198232You can write enable choices8 after a ! inside the brackets of an application26. See 3.3.2 for thesemantics of this. Note that only an exception returned by the application is caught by thesechoices, not one resulting from evaluating the proc or arguments.An argBinding27 denotes a binding for the arguments of an application. You can omit a [name,value] pair n~e in the binding if the corresponding type has a default, or you can write the namewithout the value expression (e.g., n~ ) with the same meaning. You can also write TRASH (orNULL) for the value; this supplies a trash value for the argument ( 4.11).3.8 IF and SELECT28 if ::= IF e1 THEN e2 (ELSE e3 | )IF e1 THEN e2 ELSE (e3 | NULL)29 select ::= SELECT e FROM LET selector(~e IN choice; ... endChoice choice ELSE ... endChoice The separator written ";" is "," in an expression.ELSE is a separator for repetitions of the choice.30 choice ::= (( |relOp22|NOT relOp22) e1), !..=>e2IF ( (selector( (= | relOp | NOT relOp) e1) OR ... ) THEN e231 endChoice ::= ENDCASE ( | => e)ELSE (NULL | e)In 29, 32, 34.32 safeSelect ::= WITH e SELECT FROMLET v(~e IN safeChoice; ... endChoice30 safeChoice ELSE ... endChoice33 safeChoice ::= n : t => eIF ISTYPENOTNIL[v(, t] THEN LET n : t_NARROW[v(, t] IN e34 withSelect ::= WITH (n1 ~~ e1 | e1 )OPEN v(~~e1 IN LET n(~($n1 | NIL), type(~De1,SELECT ( | e2) FROM selector(~(e1.TAG | e2) IN withChoice ELSE ... endChoice withChoice; ... endChoice30-- e2 must be defaulted except for a COMPUTED variantThe ~~ may be written as :.35 withChoice ::= n2 => e |IF selector(=n2 THEN OPEN n2, n2, !.. => e (BINDN[n(,LOOPHOLE[v(,type([n2]] ] | BINDN[n(, v(] ) IN ei_(IF j<3 THEN 6 ELSE 8);-- An IF with results must have an ELSE.IF k NOT IN Range THEN RETURN[7];SELECT f[j] FROM-- SELECT expressions are also possible.<7=>{...};-- Wt:INT~f[j]; IF t<7 THEN {...} ELSE ... IN [7..8]=>{...};-- 7, 8=> or =7, =8=>{...} is the same. NOT<=8=>{...};-- ENDCASE=>{...} is the same here.ENDCASE=>ERROR;-- Redundant here: choices are exhaustive.WITH r SELECT FROM-- Assume r: REF ANY in this example.rInt: REF INT=>RETURN[Gcd[rInt^, 17]];-- rInt is declared in this choice only.rReal: REF REAL=>RETURN[Floor[Sin[rReal^]]];ENDCASE=>RETURN[IF r=NIL THEN 0 ELSE 1]-- Only the REF ANY r is known here.nr: REF Node49~...; WITH dn~~nr SELECT FROM-- See rule 49 for the variant record Node.binary=>{nr_dn.b};-- dn is a Node[binary] in this choice only.unary=>{nr_dn.a};-- dn is a Node[unary] in this choice only.ENDCASE=>{nr_NIL};-- dn is just a Node here.The kernel construct if28 evaluates the expression e1 to a BOOL value test, and then evaluates e2 iftest=TRUE, or e3 if test=FALSE. In the expressionIF test1 THEN IF test2 THEN ifTrue2 ELSE ifFalse2the grammar is ambiguous about which IF the ELSE belongs to. It belongs to the second one.A select29 is a sugared form of if which is convenient when one of several cases is chosen based ona single value. The selector expression e is evaluated once, and then each of the choices is tested inturn. Within each choice, each expression e1 preceding the => is compared in turn with the f2qG,G?t _`!z_t0`!z_t ^WD \9 Y YzYtM X$utut)) Vut.qt UqtF PI{X|{| Mz>{XtqtLzMtqtLzMt{qtLzMt{t{*qt{LzMtqt{LzMtqt{LzMt{tq{ K0z>{Xtqtqt*wt}t{tw It {t *{,It/Itqt{t{4It&:It HnqG0*2 Fz>{Xt{t{tG0zF{qtG0zF{tF]zF{tqtF]z*Fqt{qG{t}tX{t{t{t{tqt{t{F]zF{tqt{t{tqt{F]z D>{Xtqt{t{t{*qt{qt{t{ CqG @z>{ XtqtqG*wtX}t{tw ?t{t ?Uz*?t{ +>h2(?tqt{t{7>& =z>{ Xt *qtw t}t{tqGtXwt{t{tqt}t{tqt{ <z>t{ Xtqt{t;zz<t;zz<t{t;zz<t{*wt}t{;zz<twqGwtX}t{t{;zz<t{tq{t}t}{;zz<q :t{t{t9z:{tqt*qGt}t{9z:twtX{t{9z:{twt{ 9h9?:tqt{t{D9& 8+t{t 8qz*8+t7z8+tqt 6qG 5z>t{ Xt4sz5t{*qt}t{4sz5qGtXqG 3t2z3tX2z3t *qG{wt}tqt}t}t{2z3tX{qGwt}tX}tqG{tXwt{ /tqtqtqt*qtqt .cqtqGtXqtqt ,qtq*tqt +[ *}utqtututqtutqt{tqt{t )qt*{t (Sqt *qt{t &qtqt** #qtqG*tXutqGtX " qGtqt X*ut!  qGtqt qtqtqtXqtqtqt* qGtXut qtztqtqG*tX$u  is evaluated to yield thevalue of the select. If no comparison succeeds, the next choice is tried. If no choice succeeds, theexpression e following the ENDCASE is evaluated to yield the value of the select; e defaults to NULL,and hence must be present when the select is not a statement to prevent a type error.The comparison is selector relop e1 if e1 is preceded by a relop; otherwise it is selector=e1.Style: It is good practice to arrange the tests so that they are disjoint and exhaust the possiblevalues of the selector. ENDCASE should be used to mean "in all other cases"; often the appropriatee2 raises an error. Don't use ENDCASE when you mean another specific selector value which youdon't bother to mention.Performance: If the e2 are static and select disjoint subsets of the selector values, and the averagesize of these subsets is not too large, a select compiles into an indexed jump, which executes in atime independent of the number of choices. This also happens if a contiguous subset of the choiceshas this property.A safeSelect32 is a special form for discriminating cases of unions or ANY. The selector must be avalue for which ISTYPE can be evaluated dynamically ( 4.3.1): REF ANY, PROC ANY_T, PROCT_ANY, V or REF V, where V is a variant record. Each choice specifies one possible type that theselector might have, and declares a name which is bound to the selector value if it has that type.Thus, the example tests for r having the types REF INT and REF REAL. If it has REF INT, the firstchoice's e is evaluated; within e, rInt is bound to the selector, and has type REF INT. Likewise forREF REAL and the second choice. As with an ordinary select, the ENDCASE expression is evaluated(with no new names known) if none of the other choices succeeds. Note that safeSelect doesordinary binding by value, not the binding by name done in open and withSelect.A withSelect34 is an unsafe and rather tricky construction for discriminating cases of unions. Itsuse should be avoided unless a safeSelect can't do the job; this is the case for a COMPUTED tag, orif the call by name feature of withSelect is required.It incorporates an open ( 3.4.2) of the e1 being discriminated. This means that e1 isdereferenced to yield a variant record value. It also means that this value is not copied, andhence it can change its type during execution of a choice, either by assignment to thevariant part of a variant record (itself an unsafe operation), or by a change in the value ofe1. If the union has a COMPUTED tag, the selector value to be used for the discrimination mustbe given as e2 in the withSelect. It is entirely up to the programmer to supply a meaningfulvalue. If the tag is not COMPUTED, e2 must be omitted and the selector value is e1.TAG. The n2 preceding => in a choice are literals of the (enumerated) type ( 4.7.1.1) which isthe tag type of the union ( 4.6.3). They are compared with the selector, and if one matches,the e following => is evaluated as with an ordinary select. If exactly one is given, then thee following => is in the scope of OPEN n1~~LOOPHOLE[e1.DEREF, V[n2]];or simplyOPEN LOOPHOLE[e1.DEREF, V[n2]]if no n1~~ followed the WITH. If several n2 are given, then there is no discrimination, andthe e following => is in the scope ofOPEN n1~~e1.DEREF or OPEN e1.DEREF f2qG,G?t _)u_Nz_t+ ]\ \i utqt0utqt ZR WututuW-zWtuW-zWtututuW-zWt Tvt6& S qtC QuPzQtqt4 O/ Lv tuKwzLt D JQ H8& G C D)zCt%qt B_ qt)qtqtqtq}utq @u}qtutqtututF ?W? =utqtqtqtqtqtqt {qtX{t {t {t Tz>{XtTlzTt{tTlzT{t{tTlzTt{t*TlzTt{tTlzT{t{t{t{t{TlzTt{t{tTlzTt SRqG P'z>{ Xt* N{qt{qt{tq{t{tqt{tqt{tqt{tqt{tqt{t Mqt{tq t{tqt{t{q GtX{t{qG Kd Hz>{XtHzHt{tHzH{t{ G2tGxzG2t{t GxzG2t{t GxzG2t{t EEzEt{tEzEt{tEzEt{tEzEt{tEzEt{ D*t DpzD*t{tDpzD*t{tDpzD*t{t DpzD*t{t Dpz @qGtX ?{?z?{t* =qtqtqt*qtqt : qt * 9H qt9z9Ht* 6z{t{t{t{tqG{tXqt{t{t{tq{*{tqt{tqG{tXqt{t{t{t{tq{ 4qGG 1z>{X*w t{t{ 00t{2Mt qtqt{ .t{2Mt qt~twt{tqt{ -(tqt{2Mt qt~twt{tqt{ +tq2Mt qtqt{ *fqG+*z*fq ))Kz)q{q{q! ' $tX[ #qGt*X( !qt*ututut ut  qt*ut qt*ututut ut qt{tqt*utututqt{tut qtqt*ututut ut Yz>{ Xqt*w t{1!"6Yt{ t z>{ Xq{q{q{ Qqt{qGtX{tqt{tq{ z>{Xt{t@zt{qt@z{t*{@zt{@z &qG z>{Xt{t{t{t{tq dG 9t Xqty  `TVk(% CEDAR DESUGARING TEXT, PART 2JULY 18, 198235p: PROC[x: REF ANY] RETURNS [stop: BOOL]] RETURNS [stopped: BOOL];p2:PROCESS RETURNS[i:INT]_FORK stream.Get;failed: ERROR [reason: ROPE]~CODE;45 enumTC ::= { n, !.. } |MKENUMERATION[ [$n, ...] ] |MACHINE DEPENDENT {( (n | ) ?((e)) ), !.. }MKMDENUMERATION[ [ [($n | NIL), e], ... ] ]Op: TYPE~{plus, minus, times, divide };Color: TYPE~MACHINE DEPENDENT{-- A Color value takes 4 bits; greenW1.red(0), green, blue(4), (15)}; c: Color;46 recordTC ::=?access12 ?MONITORED RECORD fields44 |MKRECORD[ fields] | ?access12 MACHINE DEPENDENT RECORD ( mdFields | fields44 )MKMDRECORD[( mdFields | fields )] Any unionTC in fields must come last.47 mdFields ::= [( (n pos), ... : ?access12 varTC39), ...] MDFIELDS[ ( [ ([$n, (pos | NIL)] ), ... ] , t ), ... ]In 46, 49.48 pos ::= ( e1 ?(: e2 .. e3) )MKPOSITION[firstWord~e1, firstBit~e2, lastBit~e3]In 47, 50.Cell: TYPE~RECORD[next: REF Cell, val: ATOM];Status: TYPE~MACHINE DEPENDENT RECORD [-- Don't omit the field positions.channel (0: 8..10): [0..nChannels),-- nChannels < 8.device (0: 0..3): DeviceNumber,-- DeviceNumber held in < 4 bits.stopCode (0: 11..15): Color, fill (0: 4..7): BOOL,-- No gaps allowed, but any ordering OK.command (1: 0..31): ChannelCommand ];-- Bit numbers >16 OK; fields can cross-- word boundaries only if word-aligned.49 unionTC ::= SELECT tag FROM MKUNION[selector~tag, variants~[ [ labels~[ $n, ...], ( n, ... => ( fields44 | mdFields47 | NULL) ), ... value~fields ], ...] ] ?, ENDCASE Legal only as last decl in a recordTC or unionTC.50 tag ::= (n ?pos48 : ?access12 | [ [ ( $n, pos | $COMPUTED( | $OVERLAID( ) ] , COMPUTED | OVERLAID ) (t | *) ( t | TYPEFROMLABELS ) ]In 49, 51a.Node: TYPE~MACHINE DEPENDENT RECORD [-- rands is a variant part or union.type (0: 0..15): TypeIndex, -- This is the common part.rator (1: 0..13): Op45,rands (1: 14..79): SELECT n (1: 14..15): * FROM-- Both union and tag have pos.binary=>[a (1:16..47), b (1:48..79): REF Node],-- At least one variant must fill 1: 14..79.unary=>[a (1: 16..47): REF Node],-- Can use same name in several variants.nonary=>[] ENDCASE ];-- Type of n is {binary, unary, nonary}.51 arrayTC ::= ?PACKED ARRAY ?t1 OF t2MKARRAY[domain~t1, range~t2]51.1seqTC ::= ?PACKED SEQUENCE tag50 OF tMKSEQUENCE[domain~tag, range~t] Legal only as last decl in a recordTC or unionTC.52 descriptorTC ::= ?LONG DESCRIPTOR FOR varTC39MKARRAYDESCR[arrayType~varTC] |The varTC must be an array type.Vec: TYPE=ARRAY [0..maxVecLen) OF REF TEXT;v: Vec~ALL[NIL]; f2qG,G?ty_XqtqGtXqtqt ^Wqt qt \qtqtqtqt [Oqt qtqt X$z>{tX{t {*w t{t{t{ Vqtqt{t{t{t{t{t IVhy V!gVhy!V{t{t*wt{t{t{tq{t{t{t Suqt QqtqG t*XuOtXu}t Pm( MBz>{X K{tLzKt{qtqtLzKt{*wt{15K4MKt{ J:t{tJzJ:tqG tX Hqt{t {tHzHt{*w t{t{3iH~J8Ht{t{9H~{Xt Dp{t{t{t{t{tDzDptDzDp{t{t*wt{t{t{t{t{tq{t{t{t{t{t{t C2qG Az>{XtAvyMAA!zAt{tA!zAtA!zA{tuAvy*Aw t {A!zAt {A!zAt {A!zAt @qG {Xtqtqt*wt {t{t{t /{t{t{t/[z/t{t/[z/t{tq{t{t{t*{t{t -{tq{ , tqG, *z>{Xt{t{t*z*t{t*z*t{t*{t{t{t{tw}t{tw}t{t )qt{tqt{t{t{t{*t{t{t{tw t{t 'qG $tXqtqGtX*ut #* !!z!t  qtq*tyqGtX qtqt*,yqt*)y qt* utututut Yz>{Xt{tqtqt{tzYtqtz*Ywt{zYt{zYt kz{t{tqtqtzktqt*w t{t{t{t qG, cz>t{ Xt {qtq GtX%z*w t {t{ [tqG 0tXqtqtqtqGt Xqtqt TVk(t CEDAR DESUGARING TEXT, PART 2JULY 18, 198236Chars: TYPE~RECORD [text: PACKED SEQUENCE-- A record with just a sequence in it. len: [0..LAST[INTEGER]] OF CHAR]; ch: Chars;-- ch.text[i] or ch[i] refers to an element.dV: DESCRIPTOR FOR ARRAY OF REF TEXT~53 refTC ::= REF (varTC39 | )MKREF[range~(varTC | ANY )]54 listTC ::= LIST OF varTC39MKLIST[value~varTC]ROText: TYPE~REF READONLY TEXT;-- NARROW[rl.first, ROText]^ is aRL: TYPE~LIST OF REF READONLY ANY; rl:RL;-- READONLY TEXT (or error).55 pointerTC ::= ?LONG ?ORDERED ?BASE MKPOINTER[range~varTC] | POINTER ?subrange25 ?(TO varTC39) |POINTER TO FRAME [ n ]xxx |Subrange only in a relativeTC; no typeName on it.55.1relativeTC ::= t2 RELATIVE t1MKRELATIVE[range~t1, baseType~t2]t1 must be a pointer or descriptor TC, t2 a typeName for a base pointer.UnsafeHandle: TYPE~LONG POINTER TO Vec51; f2qG,G?t _XqtqtqG*tX% ^W qtqtqGtX *ututututut \q Gt Yz>{Xtqt{tYzYt{t{*wt{t{tqt{t X$z>{XtqGtXjz*X$wt{t TXqtqG*tXqtutuqGutX SuqtqGtXqG tX*qGtX{t PJz>t{Xt{qG{tqtX{qt*wt{t{ NtqG{tO zNq{qtXO zN{t{ MBqGtX*{t{ LqG) Jzt{ XtIzJtqtIz*Jw t{IzJt {IzJq HHLzHqG&HLzHq Et XqtqG tEzEtTTVk(FCEDAR TYPES, PART 1DRAFT OF JULY 20, 198237Chapter 4. Primitive types and type constructors This chapter gives detailed information about the primitive types and type-returning procs (typeconstructors). It should be read after 2.3, which defines a Cedar type and explains the basic ideasunderlying the type system. The implies relations on primitive types are summarized in 4.12, andthe coercions in 4.13. 4.1 gives the partial ordering called the class hierarchy that is used to classify the primitive types. 4.2 lists all the primitives of Cedar. 4.3-4.10 give the declarations and semantics for all theprimitive classes and types. These descriptions are ordered according to the class hierarchy in Table41. Each one specifies:The constructor for types in the class.Any literals or basic constructors for values of types in the classThe declarations in the class that are not in any bigger class.Anomalies and facts about performance.4.1 The class hierarchyA useful way of organizing a set of types is in terms of the properties of their clusters. Since acluster is a binding, its type is a declaration; we call such a declaration a class. For example, theclass NUMERIC is[T: TYPE; PLUS: PROC[T, T]_[T]; MINUS: PROC[T, T]_[T];. . . -- Declarations for other arithmetic procs. LESS: PROC[T, T]_[BOOL];. . . -- Declarations for many other procs. ]By convention, the name T in a cluster denotes the type to which the cluster belongs.A type T is in a class C if T.CLUSTER has the type C; we also say that T is a C type, e.g., INT is inclass NUMERIC, or is a numeric type. To make this explicit, we give the type CLASS a cluster proccalled TYPE, such that every type T in class C has type C.TYPE. For example, INT has typeNUMERIC.TYPE. Thus, T is a C typeWT in C WT has type C.TYPEW(C.TYPE).PREDICATE[T]=TRUEA value satisfies the predicate for C.TYPE if it is a type, and its cluster satisfies the declaration whichdefines C. E.g., INT satisfies the predicate for NUMERIC.TYPE because it is a type, and its clustercontains procs for PLUS, MINUS, LESS etc. with the right types. Precisely, (C.TYPE).PREDICATE is l [T: ANY] IN TYPE.PREDICATE[T] & C.PREDICATE[T.CLUSTER]A class C is a subclass of another class D if CgD. Recall the implies relation for declarations meansthat Each name n in C is also in D.n's type in D implies n's type in C.Precisely, (AnBC.names) nBD.names & (D.ToBinding.ngC.ToBinding.n)For example, the class ORDERED includesLESS: PROC[T, T]_BOOLEvery subclass of ORDERED must also declare a LESS proc which takes two T's to a BOOL. If we hada richer assertion language, there would also be axioms defining LESS to be an ordering relation.Similarly, every ORDERED type (e.g., INT) must have such a LESS proc in its cluster.The subclass relation defines a class hierarchy, i.e., it gives a partial ordering on classes. Table 41gives the class hierarchy for the primitive classes of Cedar. It is presented as a tree: a node N withsons N1, N2, ..., Nk is written f2qG%G?t,TVk(M_pj* \jqVr Z qK Yb ; W T rq0 S/_ Q P P'M'KwCI?F& AuX >qa =EGrq  ;yq :={qXtq 8yqtq{q{q}q{q 75yqtq{q{q}q{q 51 4-yqtq{q{q}qtq 2- 1%{q< -{qrq{q{qyq {q{qrq{q tq ,vyq?yq *tq{q {q {tqtq )nyqtq '{qX{q}{q{q}{q {t}q{qtqyq{qt &fq#{qtq/ ${qtqyqyq #^ yqyqyq({qtqyq !|qX{qyqyqtqyq{q}q{yq{yq {qrq{q{}{q4 + X{q{q {q #{q {q{q {q  }{}{q{qX{}{q{q}q{q{q{}{q{q{q yq yqXtq{q{q}t q yqyq{qtq  @yq  yq tqyq \>' S{q T{ Tq{ Tq{~ Tq , TVk()CEDAR TYPES, PART 1DRAFT OF JULY 20, 198238NN1 | N2, |... | Nkand if any of the Ni are not leaves, they are defined on following indented lines:NiNi1 | Ni2, |...In fact, however, the class hierarchy is not a tree but a partially ordered set; hence some classesappear more than once in the table, with appropriate cross-references. Classes produced by Cedartype constructors are named by the constructors; other, more general classes are given suggestivenames, sometimes lower-case versions of the constructor names. Each primitive type also appears inthe table, under its class in the tree. f2tG%G?q _{{_N_qX{_N_q{_N~ ]q{]`~]q>y[{[r~[{[r~[qX{[r~[q XN WPH U@ TH!; R$RTVk(yCEDAR TYPES, PART 1DRAFT OF JULY 20, 198239 Class Subclasses or typesallgeneral* | TYPE 4.8 | fully opaque 4.3.4 | SEQUENCE_rowgeneral 4.3.1assignable* | variable 4.3.3 | PORT_transfer | MONITORLOCK 4.9 | CONDITION 4.9 | ARRAY_row, RECORD or union with a non-assignable componentassignable 4.3.2-- everything not mentioned separately under all or general, i.e.:--n-opaque 4.3.4 | transfer_map | descriptor_map | address | RELATIVE | ordered | unspecified | ARRAY_row, RECORD or union without a non-assignable component.has NIL 4.3.3variable_general | address | transfer_mapmap 4.4transfer* | row* | descriptor*/address | BASE POINTER/pointer | TYPE_alltransfer 4.4.1PROC | PORT | PROGRAM | PROCESS | SIGNAL | ERRORrow 4.4.2ARRAY 4.2.1 | SEQUENCE/union--second class-- 4.2.2J(TEXT | StringBody )descriptor 4.4.3LONG DESCRIPTOR | DESCRIPTOR/addressaddress 4.5reference* | descriptor_map | ZONE 4.5.2 | POINTER TO FRAME 4.5.3reference 4.5.1REFJ(LIST | ATOM) 4.5.1.1 | pointer* pointer/ordered 4.5.1.2LONG POINTERJLONG STRING | POINTERJSTRING | BASE POINTER_mapRELATIVE 4.5.4RELATIVE POINTER | RELATIVE DESCRIPTORrecord --painted-- 4.6RECORD 4.6.1 | variant 4.6.2union --second class-- 4.6.2ordered 4.7discrete* | numeric* | pointer_address | subrange 4.7.3discrete 4.7.1whole number_numeric | enumeration --painted-- 4.7.1.1J(BOOLWBOOLEAN | CHARWCHARACTER)numeric 4.7.2whole number*/discrete | REAL 4.7.2.2whole number long number=(INTWLONG INTEGER | LONG CARDINAL) | short number* 4.7.2.1short numberINTEGERJNAT | CARDINALJNATCONDITION | MONITORLOCK | unspecified 4.9J(UNSPECIFIED | LONG UNSPECIFIED )--kernel only-- exception | DECL | BINDING 4.10Notation:n*n is further specified in one of the indented lines below.nn is a type, rather than a class.n_mn has its main definition under (and implies) class m.n/mn also appears under (implies) class m.n=e | ...n includes (is implied by) the e classes, which together exhaust n.nJe | ...n includes (is implied by) the e classes, which are special cases.Table 41: The class hierarchy4.2 Type-related primitivesThe tables in this section summarize the primitive and predeclared types, type constructors andprocs of Cedar. f2tG%G?q `3 *_ *`3 _  `3_!}`3*_*(`3_/`3_6`3_=0`3_D7`3_ ^WrX r ]i *F]i F ]iF!}]i*F(]iF/]iF6]iF=0]iFD7]iF Z{q tqtGqXtGqXtTVk(8wZ{pq XrqGr X qGrXqpqrWsq GrXqGrXUqpqrqr)yTk qGrXBRsrqGrX pqr pqr qrQcOqpqrqr- MqGrpqrXpq J\rqGrXqrqGrXqrpq HrqGqrXqrqrqrqrq GTrqGq rXqGtrqrXs r E qGqrXq rq DL BrqGr X pqrqGrXqGrXqG ADrqqtrqrXqrqG rX qGy?r)>qG crqrX c=isr(qrqr c;sr(qGrXsr(:aqrqrqGrX 8qrqG crX! 6v1r 5q rqG crXqrqG 3}rXqG crX# 1qGrXqG cr2w1rXqr 0uqG cr1w0urXqrqr .v ,rs cr1 +qrqrqG crqrXqGs )rs q crX c( vr c&sr(qr c%srqrqr c#sr(qGrXqGrX !q G crX"  yqG crXqGr cXqGrXqr D *q *D q Dq!}D*q*(Dq/Dq6Dqrv* s Hr P 6- @O  Rx r Y qr |TVk(CEDAR TYPES, PART 1DRAFT OF JULY 20, 198241 Name DomainClass of result Rule MKSUBRANGE[FIRST: T, LAST: T]subrange 25 4.7.3-- T is the DISCRETE base type, which has a MKSUBRANGE type constructor in its cluster. CHANGEDEFAULT[type: TYPE, proc: (PROC[]_type), allowTrash: BOOL]general40 4.3.1MKXFERTYPE[flavor:{PROC,PORT,PROCESS,SIGNAL,ERROR,PROGRAM}, transfer41 4..4.1 domain, range: DECL_NIL, safe: BOOL_ISCEDAR]MKPROC[domain, range: DECL_NIL, safe: BOOL_ISCEDAR]PROC41 4..4.1~MKXFERTYPE[domain, range, PROC, safe]MKENUMERATION[LIST OF ATOM]enumeration 45 4.7.1.1MKMDENUMERATION[LIST OF RECORD[ATOM, NAT]]enumeration45 4.7.1.1MKRECORD[fields: DECL, RECORD 46 4.6.1or MKMDRECORD access: {PUBLIC, PRIVATE}_CURRENTACCESS, monitored: BOOL_FALSE]MKPOSITION[firstWord: NAT, firstBit: NAT_0, lastBit: nat_15]48 4.6.1MKUNION[selector: TAG, variants: ?????union49 4.6.3MKSEQUENCE[domain: TAG, range: TYPE, packed: BOOL_FALSE]SEQUENCE51 4.4.2.2MKARRAY[domain: DISCRETE.TYPE_CARDINAL, range: TYPE, ARRAY51 4.4.2.1 packed: BOOL_FALSE]MKARRAYDESCR[arrayType: ARRAY.TYPE, DESCRIPTOR52 4.4.3 long: BOOL_FALSE, readOnly: BOOL_FALSE]MKREF[range: TYPE, REF53 4.5.1.1 base: BASE_WORLD, readOnly, uncounted: BOOL_FALSE] MKLIST[componentType: TYPE, readOnly: BOOL_FALSE]LIST54 4.5.1.1MKPOINTER[range: TYPE_UNSPECIFIED, pointer55 4.5.1.2 long, readOnly, ordered, base: BOOL_FALSE]~MKREF[range~range, readOnly~readOnly, uncounted~TRUE, base~(IF long THEN WORLD ELSE MDS)]. MKRELATIVE[range: TYPE, baseType: BASE.TYPE] RELATIVE55 4.5.4Table 43: Primitive type constructors4.2.2.1 OptionsThe built-in type constructors take an assortment of optional BOOLEAN arguments, as indicated intheir declarations. In the current syntax these are specified by writing options in the typeconstructor. When an option appears in a type constructor, the argument of the same name has thevalue TRUE; if it is missing, the argument has the value FALSE. The effect of these arguments on thetype produced by the constructor is given as part of the description of its result class. Table ??? liststhe options and the constructors for which each is appropriate. f2qG%G?r `3 *_ *`3 _  `3_!}`3*_*(`3_/`3_6`3_=0`3_D7`3_ ]vX v<rvr \ *F\ F \F!}\*F(\F/\F6\F=0\FD7\F Z{x rqrsrqrsr< EG Xsrxrx r" Wsx rsrqrsrqrtsrs rqr<EG Ux rsrxyxyxyxyxyxr<rEGTksrsrxrqrsrqrxr RxrsrXsrxrqrsrqrxr<qErG Qcx rsrsrxrsr Ox rqGrXqr< EG N[xrqGrXqrqrqr< EG Lxrsrxr<qrEG KSx rsrxqGxrx rXIsrqrqr HKx rsrqrsrqrsrsr<EG Fxrsrxrsr<EG ECx rsrxrsrqrsqGrqr<qErGX Cxrsrxrqrqrsrqr<qErGB;sqGrqr @x rsrXxrqr<q ErG?3sOrXqrqrsrqrqr =xrsrqr<qErG<+srxrxrsrsrqrqr :xrs rqrsrqrqr<qErG 9#xrsrqrq r<EG7srsrsrsrqrqr 6xrsrsrsrsrsrqrsrqGsrXqrxrqrxr 4x rsrqrsrxrqr<xErG 3 *3 *3 3 33!}3*3*(33/33633=033D733/v& + 'r;qr &f$vr $ T #^qrqr& ! Y V<~TVk(WCEDAR TYPES, PART 1DRAFT OF JULY 20, 198242OptionConstructorsBASEMKPOINTERLONGMKPOINTER, MKARRAYDESCR, INTEGER, CARDINALMONITOREDMKRECORDORDEREDMKPOINTERPACKEDMKARRAY, MKSEQUENCE, MKARRAYDESCRIPTORPUBLIC, PRIVATEMKDECL, MKRECORDREADONLYMKVAR, MKREF, MKLIST, MKPOINTER, MKARRAYDESCR, MKDECL (interface vars only)SAFEMKXFERTYPEUNSAFEMKXFERTYPETable 44: Type options and their constructors4.2.3 Primitive procsThe primitive procs and other values of Cedar are listed in Table 45. All of the procs in the Cedarlanguage except the type constructors (see Table 43) appear here.The Name column gives the name of the value in the cluster. The Classes column gives the classesin which the [name, value] pair appears; the primitive classes of Cedar are summarized in Table41. The Type column gives the type with which it is declared in those classes. The type may referto other names of the class; see the detailed class descriptions in 4.3-4.10 for more information.The Notes column gives information about how a proc is applied or a non-proc value is denoted incurrent Cedar. In the kernel a proc named P from the cluster of type T is applied to a value x oftype T by the expression x.P (if there is only one argument) or x.P[y, ...] if there are several. Incurrent Cedar, however, very few primitives can be applied or denoted by dot notation. Instead,there are three ways of applying a primitive proc:It may be an operator with a symbol listed in the Notes column. If it takes two arguments,the operator is infix. Thus for a proc named P with operator symbol 4, you write x4yinstead of x.P[y]. If it takes one argument the operator is usually prefix; you write 4xinstead of x.P. The ^ operator is postfix; you write x^ instead of x.DEREFERENCE.It may be a built-in proc named P, in which case you usually write P[x] or P[x, y, ...] insteadof x.P or x.P[y, ...]. Other ways of applying a built-in are indicated in the Notes column.It may be a funny application proc named P, in which case you write P x or P x[y, ...]instead of x.P or x.P[y, ...].The three kinds of primitive proc are listed in that order, and alphabetically within each kind.Primitive values which are not procs (ABORTED, FALSE, FIRST, LAST, NIL, SIZE, TRUE) are listed withthe built-in procs, and the syntax for them is given explicitly.A few primitive procs cannot be desugared so simply into dot notation. These cases are indicated inthe Notes column, and are described here:ABORTED, FALSE, NIL and TRUE are globally known names.Some PROC [T]_[U] are coercions: CONS, FROMGROUND, LONG, TOGROUND, VALUEOF. Thismeans that they may be invoked automatically when typechecking demands a U and anexpression has syntactic type T; see 4.13 for details. Some involve target typing: ALL, CONS, LIST, LOOPHOLE, NARROW; they are marked TT.For these the proc does not come from the cluster of the type of the first argument.Instead, it comes from the cluster of the so-called target type. An application of one of f2qG%G?r `3 *_ *`3 _  `3_!}`3*_*(`3_/`3_6`3_ ^Wv~v ]i *F]i F ]iF!}]i*F(]iF/]iF6]iF [Orq~x Yq~xrXx rqrq XG~x Vrq~x U?rq~xrx rx Sqrq~xqGx R7q~xrXxrxrxrx r~Pxr O/q~x Mq~x L *L' *L L' LL'!}L*L'*(LL'/LL'6LL'}H(v. D) @rCvr ?z: orderedPROC[T, T]_[BOOL]~same as NOTDEREF-^(postfix)referencePROC[r: T]_[RANGE]ERENCEININorderedPROC[T, SUBRANGE]_[BOOL]REMMODwhole numberPROC[T, T]_[T]NOTNOT(prefix) BOOLPROC[BOOL]_[BOOL]Built-in procs (applied with P[x] instead of x.P, except as noted)ABORTEDABORTEDSIGNALSIGNALABSnumericALLTTARRAYPROC[x: RANGE]_[T]BASErowPROC[a: VAR T]_[LONG POINTER TO UNSPECIFIED]descriptorPROC[a: T]_[LONG POINTER TO UNSPECIFIED]CODETYPEPROC [T: TYPE]_[RTT.Type]CONST[...]; coercionARRAYPROC[g: RANGE X ...]_[T]T[...]; coercionRECORDPROC[b: FIELDS]_[T]a[...]; TT for aunionPROC[b: FIELDS]_[T[a]]z.CONS[...]; TTLISTPROC[z: ZONE_SafeStorage.GetSystemZone, x: VALUE, y: T]_[T]DESCRIPTORrow, variant recordPROC[r: VAR T]_ [LONG DESCRIPTOR FOR ARRAY T.DOMAIN of T.RANGE]xxxdescriptorPROC[base: LONG POINTER TO UNSPECIFIED, length: CARDINAL, t: TYPE]_[LONG DESCRIPTOR FOR ARRAY CARDINAL OF t]FALSEFALSEBOOLTFIRSTFIRST[T]discreteTfirstl.firstLISTPROC[l: T]_[VAR VALUE]FREEz.FREE[..]ZONEUNSAFE PROC[z: T, p: NEWTYPE[NEWTYPE[u]]]_[]FROMGROUND T[...]; coercionsubrangePROC[x: GROUNDTYPE]_[T]ISTYPEgeneralPROC[x: T, U: TYPE]_[BOOL]LASTLAST[T]discreteTLENGTHARRAY, descriptorPROC[a: T]_[CARDINAL]LISTz.LIST[...]; TTLISTPROC[z: ZONE g: VALUE X ...]_[T]LONGcoercionshort numberPROC[p:T]_[LONG T]coercionPOINTERPROC[p:T]_[LONG POINTER TO T.RANGE]coercionDESCRIPTORPROC[p:T]_[LONG DESCRIPTOR FOR ARRAY OF T.RANGE]LOOPHOLETT for UgeneralUNSAFE PROC[tx T, U: TYPE]_[U]MAXorderedPROC[T, ...]_[T]MINorderedPROC[T, ...]_[T]NARROWTT for UgeneralPROC[x: T, U: TYPE]_[U]NEWz.NEW[..]ZONEPROC[z: T, U: TYPE]_[r: NEWTYPE[U]]NILNIL[T] or NILvariable, address, T or NILTYPEtransfer f2qG%G?r `3 *_ *`3 _  `3_!}`3*_*(`3_/`3_6`3_=0`3_ ^WvvRv* ]i *F]i F ]iF!}]i*F(]iF/]iF6]iF=0]iF [OvX YxyrR*qGrsrtrxrsrsrxrXsrxr XGx VrR*qrsrsrsrsrtrqr U?xrR *qrsrxysrsrsrtrsr SxrR*qrsrsrtrsrR7rRqr *qrsrqrtrsr PxrR*qrsrsrtrsrO/rRqr *qrsrsrtrqrM*qrsrqrtrsr L'xrR*qrsrsr JxrR*qrsrsrtrsr IxrR*qrsrsrtrsr GxrR*qrsrsrtrqr FxrR*qrsrsrtrqrDqRrq Cxr R*qrsqGsrtrxr Ax @qRr*qrsrXxrtrqr >xqRr *qrsrsrtrsr #v u rG FJ GvX r srXq*r qrq*r&s*rqrsr  qrqrsrsrsrqrtrqr* qrsr sr  qrqrsrsrsrqrtrsr* srsr*  sr0TVk(CEDAR TYPES, PART 1DRAFT OF JULY 20, 198246LOOPHOLE: UNSAFE PROC[x: T, U: TYPE]_[U]-- Returns the bits representing x as a U.INIT: PROC[STORAGEBLOCK[SIZE]]_[VAR T]-- Can't be called directly.NEW: PROC[z: ZONE_SafeStorage.GetSystemZone-- Denoted NEW[T] or z.NEW[T]. T: TYPE]_[r: REF T]PREDICATE: PROC[x: T]_[PROCANY_BOOL]-- The predicate of the type.CLUSTER: PROC[x: T]_[BINDING]-- The cluster of the type.All types are in this class except TYPE and fully opaque types.Anomaly: For NARROW and LOOPHOLE the second argument may be defaulted to the target type.In current Cedar the value of ISTYPE[x, T] is determined as follows:1)It is TRUE statically if:Dx and T have the same predicate, orone of Dx and T is an opaque type, and the other is the corresponding concretetype (only in an implementation that exports the opaque type).2)It is tested dynamically if (with V any variant record type without a COMPUTED tag, and athe name of a particular variant):Dx is REF ANY and T is REF U for any U except ANY, orDx and V have the same predicate, and T is equal to V[a], orDx and REF V have the same predicate, and T is equal to REF V[a], orDx is equal to (LONG) POINTER TO V and T is equal to (LONG) POINTER TO V[a].Note that the result is TRUE if x=NIL.3)It causes a static error in all other cases, even if it is statically false. In current Cedar, NARROW[x, T] isIF ISTYPE[x, T] AND (x~=NIL OR ISTYPE[x, REF ANY]) THEN x ELSE ERROR e where e isRTTypesBasic.NarrowRefFault[x, CODE[T.RANGE]] if ISTYPE[x, REF ANY];RTTypesBasic.NarrowFault[] otherwise.Note that NARROW[x, T] gives a static error if ISTYPE[x, T] does (case (3) above), and that it fails ifx=NIL unless Dx is REF ANY.Two types may be unequal and yet have the same predicate if they have different clusters.Currently, the cluster can only be changed by CHANGEDEFAULT.The INIT proc converts a block of storage into a legal variable of type T. It is currently a no-opexcept forRC types ( 4.5); these are set to NIL. Bound variants; the tag field is set appropriately.INIT cannot be supplied by the user and can only be called indirectly from NEW.The NEW proc calls on the zone z to obtain a block of storage of size T.SIZE ( 4.5.2), and appliesT.INIT to convert the block into a VAR T; call it x. Then if T.DEFAULT exists, NEW calls it and assignsthe result to x. CHANGEDEFAULT can take any type and produce a new one which is identical except for theDEFAULT which determines how default values are supplied when a binding is coerced to adeclaration; see 4.11 for details.DEFAULT: PROC[]_[T] f2qG%G?r _qrXqGrsrXsrsrqrtrsr*!srsr ^Wxrqrx rxrtrxrsr* \xrqrsrqrs*r qrsrsrqrsr [Osrqrtrsrqrsr Yxrqrsrsrtrqtqr* XGxrqrsrsrtrxr* Uqr Rvrqrqr9 Oqrsrsr#MAqrK0tsrsrItsrsr6G:#ECsr#qr sCrAtsrqrqrsrqsrsrqr?tsrsrsr srsr=tsrqrsrsrsr qrsrsr;{tsr qrqrqrsrsr qrqrqrsrsr9#qrsrqr#6M 3qrsrsr 2qGrsOrXqrsrqrqrqrsOqGrXqGsrXqGrXsr 0sr /srsrXqrsrxrqrsrqGr -srX , qrsrsrqrsr ! *srqrtsrqrqr ']V % $x r "xr 2sr !*#qrz3 "xrGqr qrsr&srqr ssrxrxysr sr srxrqr  sr x rF @xrP   8xrXqrtrsr TVk(DCEDAR TYPES, PART 1DRAFT OF JULY 20, 198247Every general type has an EQUAL proc except a variant record or union type. A variant record typehas EQUAL only if its variant part is a union in which all the cases are the same size. Note that abound variant does have EQUAL, unless it is itself a variant record. EQUAL is denoted by the infixoperator =.EQUAL: PROC[x: T, y: T]_[BOOL]-- TRUE iff the bits representing x and y are identical.Anomaly: If v is a variant record and bvis one of its bound variants, the expression v=bv applies theEQUAL proc of the bound variant.Representation: Addresses in the representation of a value are compared, not dereferenced, in doingthe comparison. Thus types like STRING and ZONE which are represented by addresses arecompared by comparing the addresses.4.3.2 Assignable typesMost types (see Table 41 for exceptions) have a proc (denoted by the right-associative infixoperator _):ASSIGN: PROC[x: VAR T, y: T]_[T]-- Returns y after storing it in x.As explained in 3.7, groups and bindings with variable elements are assignable. Since you cannotwrite these types in declarations, you have to write the constructors explicitly on the left of the _;they are called extractors. Representation: Since it involves a VAR, such a proc cannot be written in current Cedar. Theprimitive ASSIGN procs simply copy the bits of y's representation into the variable x, unless some ofthem represent REFs. In this case the assignment involves reference-counting if x is in countedstorage; see ??? for details.4.3.3 Variable typesFor every non-variable type T there are corresponding variable types:VAR TREADONLY TSHORT VAR TSHORT READONLY T You cannot denote these types in current Cedar, but they are fundamental to an understanding ofhow it works nonetheless. The basic facts about variables in Cedar are given in 2.2.3.The var class has names:RANGE: TYPE;-- (VAR T).RANGE=TLONG: BOOLEAN;-- FALSE for short varsREADONLY: BOOLEAN;-- TRUE for readonly varsVARTOPOINTER: UNSAFE PROC[T]_-- Apply by prefix @ [MKPOINTER[range~T.RANGE, long~LONG]];VALUEOF: PROC[T]_[T.RANGE];-- A coercion.Furthermore, T inherits the cluster of T.RANGE. The procs are not modified, since the VALUEOFcoercion provides them with T.RANGE arguments where needed.The VAR constructor should be in the cluster. f2qG%G?r _xr= ^WxrX \xr xr [O YxrXqrsrsrsrsrtrqr*qrsrsr*XG Uvrsrsr srsr Sxr Pmv rK N qrqr' Me IfvX F;rA D C3xrXqrsrxysrsrsrtrsr* srsr @?! >D = v r 9v rxr 8Qxrsr sr 6 qr>sr 5I 1JvX .rsr(+xys)oxys'xyxrs$xyxrsr "gY U  4xrXqr*xrsrxrs xrqr*qr ,xrqr*qr x rqGrsrt*rX $ xrsrsrxrsrxr xrqrsrtrsrxr*  srsrxr(x rsrxr &{v{& TVk(CEDAR TYPES, PART 1DRAFT OF JULY 20, 1982484.3.4 Opaque typesIncomplete. Currently treated in 3.3.4.14.4 Map typesThe map class isDOMAIN: TYPE;-- Domain type for the mapping.RANGE: TYPE;-- Range type for the mapping.APPLY: PROC[map: T, arg: DOMAIN]_[RANGE]-- map[arg] is sugar for map.APPLYZarg.Usually DOMAIN and RANGE are declarations, so that bindings can be used for the arguments andresults. Application is denoted by brackets: map[arg]; for transfer types the syntactic form APPLY (see ???) can also be used.There are several subclasses of map in Cedar, each with its own APPLY proc. These are summarizedhere, and treated in detail in the sections on the various subclasses.Primitives (since you can't get hold of the value of the primitive, these can be applied onlywith the various special syntactic forms summarized in Table 45).Transfer types: procs, and their close friends signals, errors, ports and programs; applying atransfer type executes the body of some l-expression ( 4.4.1). 2.2.1 and 2.6 tell all aboutapplying procs.Row and descriptor types: applying an array, sequence (or sequence-containing record), orarray descriptor to an index value yields a VAR of the component type ( 4.4.2).BASE POINTER types: applying a base pointer to a value which is relative to that base yieldsa (non-relative) pointer; this is unsafe ( 4.4.3).Reference types: if the base type T has APPLY, then the reference type inherits it composedwith DEREFERENCE, so that a[arg] is the same as a^[arg] ( 4.5.1).TYPE: Many subclasses of TYPE have APPLY procs with assorted meanings ( 4.8).4.4.1 Transfer typesThe subclasses of transfer are PROC, PORT, PROGRAM, PROCESS, SIGNAL, and ERROR. These typesare constructed by transfer type constructors which begin with those words, or in the kernel by theMKTRANSFERTYPE constructor. What they have in common is that application executes the body ofsome l-expression, but the transfer class adds no names to the map class.One transfer type T implies another U if The subclass is the same (or if T is a SIGNAL and U is an ERROR). T.RANGE implies U.RANGE.U.DOMAIN implies T.DOMAIN.See 2.3.2 and 4.12. One declaration D implies another E if:They have the same names, or each has only one name, and The corresponding types imply each other. I.e.If n: T is in D and n: U is in E, then TgU.If D=[m: T] and E=[n: U], then TgU.D implies a cross type T if D.STRIPNAMES implies T; in this case T also implies D. f2qG%G?r _vX \i{  WuX Tkr RxrXqr* Qcxrqr* Oxrqrsrysrsrxrtrxr*srsrsrxts Mrxrxr3 L srsr)qr J GT6xr EACx HA>?V>|r"<:<)-8'xr!6`qrqrI422srxr.1x r srsrsrsr .qrqrxr& *vX '~rqrqrqrqrqrqr %\ $vx rL "|rC srsrosrqrsrqrsrxrsrxrsrxrsrxr g(srsr9.srsrsrsrsrsrstsr srsrsrsrsrsrstsr =srsrsrx rsrsr sr TVk( CEDAR TYPES, PART 2DRAFT OF JULY 20, 198249Representations for transfer types are given in the PrincOps interface.PROC typesThe PROC class has no additional names. In the kernel, a new proc value is made by evaluating a l-expression. In current Cedar, it is made by a binding of the formP: T~{. . .}in a block, where T is a proc type; see 3.5.1 for details.PORT typesIncomplete.PROGRAM typesThe syntax for applying a program P is START P[args]The START may be omitted, so that it looks like an ordinary application. This expression's type isDP.RANGE. The program class also has procsSTOP: PROC[]_[]-- Apply by STOP. Legal only if RANGE=[].RESTART: PROC[T]_[]-- Apply by RESTART P. Legal only if RANGE=[].NEW: PROC[p: T]_[T]-- Apply by NEW P; makes a copy of p's implementation. Their use is not recommended; for details, consult a wizard. For more on implementations, see ???.PROCESS typesA process always has DOMAIN=[]. The syntax for applying a process P is JOIN PThe JOIN may be omitted, so that it looks like an ordinary application. This expression's type isDP.RANGE.The only way to make a new process is withFORK: PROC[PROC[DOMAIN]_[RANGE]]_[PROC[DOMAIN]_[PROCESS []_[RANGE]]]The syntax for using this is FORK P[args].The FORK P returns a proc when when applied to args creates a new process, starts it running, andreturns it. You cannot write FORK P alone to get hold of the process-creating proc.Anomaly: Note the peculiar parsing (FORK P)[args]. Of course, you can't get your hands on the proc(FORK P).There are no other names in the process class, but Process.Abort[P] raises the ERROR ABORTED in P. CONC describes Cedar's facilities for concurrent programming. SIGNAL and ERROR typesThe syntax for applying a error (signal) E is ERROR (SIGNAL) E[args], or ERROR (SIGNAL) E if thereare no arguments. For a signal, this expression's type is DE.RANGE; for an error, its type is ANY(since control can never return). If there are arguments, the ERROR or SIGNAL is optional; avoidthis feature. f2qG,G?r _%sr [}vX XrqrX|r W- 6yUsrXsr T%sr) P&}vX L{ H}v ErsryDqrXsrsr BqrQ @tsrxr! ?zxrXqrtr* qrxr =xrqrsrtr* qrsrxr (qr6 =# 9qrG 8ttr : 6# 3 2Aq rXqrsrxzOsrtr*Xsr 0qGxrXqrxr -q r$xr ,E (vrq r qrq rsr xr '_- $4v rxr)qrqr "xr qrsrxr7 !,qrsrxrqrqr srxrstr ~q~ q}qr qr$ } Q P u'4   qr= B qrqr) xr !qr. : v rB 3qr% A /qr TVk( CEDAR TYPES, PART 2DRAFT OF JULY 20, 1982514.4.2.1 ARRAY typesAn array is a row with an element for each value in the domain; its APPLY proc is a total function.The advantages of this are that no space is needed to store the length of an array, and any boundschecking on a subscript is done against constant values (as part of narrowing the subscript to thedomain type, which is usually a subrange). The disadvantages are that a given proc, written to dealwith a given array type, cannot be used on other arrays of different lengths, since there is no way incurrent Cedar to parameterize the proc with a type. In this case it is better to use a sequence ( ???).The array class has the procs:CONS: PROC[g: RANGE X ...]_[T]-- A coercion from the group.ALL: PROC[x: RANGE]_[T]-- Returns an array with each element =xLENGTH: PROC[a: T]_[CARDINAL]-- Returns the cardinality of DOMAIN.BASE: PROC[a: VAR T]_[LONG POINTER TO UNSPECIFIED] -- Returns the address of a's first element.CONS takes a group of values, one for each element of the array, into an a array value. Theargument of CONS may have omitted values, which are filled in if possible by the defaultingcoercion for g. If the index type is enumerated, CONS takes a binding, with one element named n oftype T.RANGE for each index value n. In current Cedar you can't write T.CONS. Instead you write Titself; i.e., T[...] for T.CONS[...]. Because CONS is a coercion from group to array, you can omit the Twhenever the group appears as an argument or in a binding; see ???. Examples:I: TYPE~INT_0; B: TYPE~BOOLEAN_TRUEA: TYPE~ARRAY [0..5) OF I;a1: A~[0, 1, 2, 3, 4];-- OK to omit A here.a2: A~[ , 1, 2, 3, 4];-- Same as a1, by defaulting.i: INT~A[4, 3, 2, 1, 0][1];-- i=3. The A is required here.E: TYPE~ARRAY {red, blue, green} OF B;e1: E~[TRUE, FALSE, TRUE];e2: E~[blue~FALSE];-- Same as e1.Anomaly: ALL replicates its argument in all the elements of an array. In current Cedar you can'twrite T.ALL. Instead you just write ALL; it must be in an argument or binding. Unlike most built-ins, ALL is not sugar for dot notation. If the range type permits it, you can write ALL[NULL] to trashall the elements.a3: A~ALL[3];-- Same as [3, 3, 3, 3, 3]BASE returns the address of its VAR array argument. It is mostly useful for writing storage allocators.The resulting LONG POINTER TO UNSPECIFIED can also be passed to DESCRIPTOR to yield adescriptor for a different type of array. If the VAR is short, the result can be narrowed to a POINTER.Anomaly: An array may be declared with a domain type which is an empty subrange. The effect isto suppress the bounds checking in APPLY. If a pointer p to such an array is constructed (with aLOOPHOLE), then p^[i] (you can also write p[i], because p inherits APPLY) will never give anBoundsFault. This kludge is sometimes useful for obtaining arrays whose size is not static. However,beware that operations on the array other than subscripting (e.g., equality tests, assignment andparameter passing) will believe the type declaration and do the wrong thing. It is generally better touse a sequence or a descriptor.4.4.2.2 SEQUENCE typesA sequence is like an array, but each sequence value includes a tag value which specifies thenumber of elements in that sequence, i.e. the values of the domain type for which APPLY is defined.If the domain type is T and the tag value is v, then APPLY is defined for [FIRST[T]..v). Usually T isNAT, so that v is the number of elements in the sequence, and the elements are indexed by 0, 1, ...,v1. f2qG,G?r _vX}v \rAxr [,2- YE X$(5 V#? Ua Q PmxrXqrsrxrtrtrsr*q Nrqrsrxrtrsr*'s Meqrqrsrsrtrqr*xr KqrqrsrxrsrtrqGrXsr Hxr< G2xr< Esr#xr(sr D*srxrsr#srxrs Brsr srxrxr5s A"rGy?srXqrqrsrqrqrqy>srqrqrqrsry[val: [0..1000)],long=>[val: LONG CARDINAL],extended=>[val: SEQUENCE length: NAT OF CARDINAL]ENDCASE];rs1: REF StackRep_NEW[StackRep[100]];-- rs1.top=1, rs1[i] is trash.rs2: REF StackRep_NEW[StackRep[100]]_[top~3, item_NULL];-- rs2.top=3, rs2[i] is trash. f2qG,G?r _5, ^W ^w^Wr(vr# \B [Oxrq r= Y$ V srsr# UJUwUr ST%wSr T%wSr(sr R0. P O xrXq*rxr Mxrq*rxr Lxrqrsrsrsrxrtrxr* Jqrsxrsr Hq rqrsrxrsrtrqGrXxqGxr Gx|qrq rsr*X& E Bsr@q-qrsr> srsrs ;rsrsrxrq ;|U 9T 8t.2 6%xr 3L 0v rxr /|rsrysrsrxrqr -qrqrsrqrqrqrsrqrqr,qrqrqrsrxr *srxrqrxrxrqrqr %uX "rZ !4 qrXs*r0 srxr qrsrq |r$qr Q/, // I'qr PmG v r4 qr7v 9r !"qr] |r  2TVk( CEDAR TYPES, PART 2DRAFT OF JULY 20, 198255NEW returns the address of a block of at least SIZE[T] words, none of which is partof an already reachable variable. Evaluating a l-expression L returns a closure ( 2.2.1), which includes the addressof the frame in which L was evaluated. This frame provides the properenvironment for binding free variables in L. A frame in turn is made only by aNEW proc for that frame type.A counted value always addresses counted storage, which is made only by such a NEW proc.It is called counted because of the implementation of the test for reachability; see ???. The storage representing a counted variable is reclaimed (by the garbage collector) onlywhen it is no longer reachable. These three invariants ensure that within the safe language a REF T always addresses a VAR T whichdoes not intersect any other variable. The second invariant is guaranteed entirely by the allocator(given the other two invariants). IncompleteFurthermore, a VAR REF T v must never be equal to a VAR U for any U=REF T. Otherwise a Ucould be assigned to the VAR, incorrectly making a new REF T value which can be retrieved byv.VALUEOF. The third invariant requires an implementation which can compute reachability. Cedar has two: One does reference counting, and hence must know about every assignment to a REF.The other scans all the reachable variables, starting with the process array and frames.Both need to be able to find all the REFs in a variable. Thus to maintain the safety invariants, it is necessary to ensure that no other value is mixed up witha value containing a REF. Such a value is called REF-containing, or RC for short. The followingclasses have RC values:REF (which includes LIST and ATOM)record, union or array with a RC component.transfer (not counteddeficiency).To define the safety invariants for non-reference addresses, it is necessary to define all the valueswhich can contain such addresses. Such values are called pointer-containing, or PC for short. Thefollowing classes have PC values:pointer (which includes POINTER TO FRAME and string);descriptor;record, union or array with a PC component.Inconplete. Notes:AC types (6T5/12):pointers to RC: dangerous but allowed.type encoding: none, prefix, quantum is in zone.4.5.1 Reference types This class has the following names:RANGE: VAR.TYPEDEREFERENCE: PROC[r: T]_[T.RANGE]-- Denoted by r^APPLY: PROC[r: T, arg: T.RANGE.DOMAIN]_-- Inherited from the range type. [T.RANGE.RANGE]f: PROC[r: T, arg: T.RANGE.f.DOMAIN]_-- Inherited from the range type. [T.RANGE.f.RANGE] f2qG,G?r_qr,qrsr^W\F |r sr#Z)sr.Y> sr#WqrUb vr'qrSZQ>P M9qrsr xrsr L&:% J G0{ Dr xyqrsrsrxysrstqrsr s Brxrqrsr @srxr =^;zMqr9"X 6%qr 3 V 2qrqrv r 0y/qrXqrqry-+y, " )/4 (/( vr &y%'XqGrX y# y"+ {  UrX & M0 Nv #r xrXxrq x qGrsqsrtrsrxr*X sr  xrqrsqGsrXsrsrxrxrt*r! srxrxr  srqrsqGsrXsrsrxrsrxrt*r! srxrsrxr ,TVk( CEDAR TYPES, PART 2DRAFT OF JULY 20, 198256The range of a reference type T may be any VAR type VAR U. If T is READONLY, then T.RANGE isREADONLY also; this means that assignment to the dereferenced address is impossible.Dereferencing a T yields a VAR U (which can then be coerced to a U value if appropriate).Dereferencing NIL causes the error Runtime.PointerFault.If the range has an APPLY, WAIT, NOTIFY or BROADCAST proc, or any record field procs in its cluster,these are inherited by the reference type (except that APPLY is not inherited by a BASE POINTER,which has its own APPLY; see 4.4.3). The value of an inherited f isl [r: T, arg: T.RANGE.f.DOMAIN] IN r^.f[arg]In other words, the address is dereferenced, and then the range's f is applied. The effect is that areference to an array or proc can be applied without explicit dereferencing, a reference to acondition can be used to do a WAIT or whatever, and a reference to a record can be used to select afield. This does not work for procs which get into a cluster by being in an interface instance.4.5.1.1 REF typesA REF value can be created only by a NEW proc. Every general type except union has one of these( 4.3.1). There are no additional names in the REF class. The type VAR ANY may be the range of a REF; it cannot appear anywhere else except as the domainor range of a proc type. This REF type is denoted REF ANY. It is implied by every REF type. ISTYPEcan be used to test the particular REF type of a REF ANY value, and NARROW can be used toconvert a REF ANY value into a REF T value ( 4.3.1). These two operations are combined in aconvenient way by the WITH ... SELECT construction ( ???). REF ANY does not have a DEREFERENCEproc, and of course there are no procs for it to inherit from the range.LIST typesThe LIST class has names:VALUE: TYPE;first: PROC[l: T]_[VAR VALUE];-- Denoted l.first, not first[l]rest: PROC[l: T]_[T];-- Denoted l.rest, not rest[l]CONS: PROC[z: ZONE_SafeStorage.GetSystemZone,-- Denoted z.CONS[x, y] or CONS[x, y]. x: VALUE, y: T]_[T]LIST: PROC[z: ZONE_SafeStorage.GetSystemZone,-- Denoted z.LIST g or LIST g. g: VALUE X ...]_[T]The RANGE type R of a list type T is opaque, but it may be thought of as an unpainted record [first:VALUE, rest: T]; thus a list value is a REF to an R. The first and rest procs return the fields of an R. CONS is NEW[R_[x, y]]; the optional zone tells where to do the NEW. LIST does a series of CONSes,yielding a list such that LIST[x0, ..., xn].resti.first=xiThe g argument of LIST may have omitted values, which are filled in if possible by the defaultingcoercion for g. Examples:L: TYPE~LIST OF INT_0;l: L~LIST[0, 1, 2, 3, 4];m: L~LIST[ , 1, 2, 3, 4];-- Same as l, by defaulting.The type ATOMAn ATOM is a REF to an opaque type which is exported from AtomsPrivate as AtomRec: TYPE~RECORD[printName: Rope.ROPE,propertyList: REF ANY_NIL, f2qG,G?r _sr xrxrsrsrqrsrxr ^WqrL=M \ sr xrsr!sr [O qrsr X$ xrxrxrqr0 V$ xrqrqr U xr*sryS|rXsqGsrXsrsrxrsrxrxrsrsrsr R@sr! P H O qrA MZ IvX}v F^rqr qr7 D.qr Axyxrqr5 @+qrqrqrqrq >rqr qrqr qr =#qrqrqrsr8 ; qrqrqrqrx :rC 6}vX 2rqr 1mxrXqr /srqrsrsrtrxyxr* srsrsrsr .esrqrsrsrtrsr* srsrsrsr ,qrqrsrqrsr* srqrsOrXqrsOr +]X srxrsrsrtrsr )qrqrsrqrsr* srqrsrqrsr (U srxrtrtrsr %*xrsrsr+sr #xrsrsrqrsrsrsrsr {qrqrsrsr,qrqr qr  sqrswsrXssrssrsrs rsr xr*! sr y}srXqrqrqrqrysrsrqryusrsrqr* sr vv} Krqrqr*s r  srXqrqry Csrsrqy s rqGrqr NTVk( CEDAR TYPES, PART 2DRAFT OF JULY 20, 198257link: ATOM_NIL]There are no additional names in ATOM's cluster; the useful operations on ATOMs are provided bythe ListsAndAtoms interface. However, the language does provide ATOM literals for atoms which haveCedar names as their printnames, with the syntax $ n. Examples:$red$VeryLongAtomMadeUpOfSeveralWordsNote that you cannot put any spaces in an ATOM literal.4.5.1.2 Pointer typesThere are two flavors of pointer: short and long. Short pointers occupy one word, and point onlywithin the 64k word main data space where frames are allocated. Long pointers occupy two wordsand point anywhere.Pointer dereferencing is unsafe; hence all the inherited procs are also unsafe. Dereferencing apointer may cause an address fault if it points to storage which is not mapped by the operatingsystem; this is about the least disastrous thing that can happen if an unsuitable value gets into apointer.Long pointer types have the following dubious names:PLUS: PROC[T, LONG INTEGER]_[T]-- Denoted by infix +.MINUS: PROC[T, LONG INTEGER]_[T]-- Denoted by infix .DIFF: PROC[T, T]_[LONG INTEGER]-- Also denoted by infix .Anomaly: The infix "" cannot be desugared into dot notation, since there are two procs denotedby an infix "" whose first argument is a pointer. The choice between MINUS and DIFF is based onthe type of the second argument.Short pointer types have the same procs without the LONG. They also have the following coercion,called lengthening:LONG: PROC[p:T]_[LONG POINTER TO RANGE]-- Apply by LONG[p]Note that VAR types have a VARTOPOINTER proc (denoted by prefix @) ; this turns a long VAR Tinto a LONG POINTER TO T or a short VAR T into a POINTER TO T ( 4.5.4).4.5.2 Zone typesThe zone class has the names:NEWTYPE: PROC[U: TYPE]_[A: REFERENCE.TYPE];NEW: PROC[z: T, U: TYPE]_[r: NEWTYPE[U]];FREE: PROC[z: T, p: VAR NEWTYPE[u]]_[];-- For a ZONE.FREE: UNSAFE PROC[z: T, -- For an uncounted zone. p: NEWTYPE[ NEWTYPE[u]]]_[];Currently there are exactly three zone types:ZONE, with NEWTYPE=l [U: TYPE] IN MKREF[range~U];UNCOUNTED ZONE, with NEWTYPE=l [U: TYPE] IN MKPOINTER[range~U, long~TRUE];MDSZone, with NEWTYPE=l [U: TYPE] IN MKPOINTER[range~U, long~FALSE].In other words, a ZONE deals in REFs, an UNCOUNTED ZONE in LONG POINTERs, and an MDSZonein POINTERs. The latter two are called uncounted zone types.NEW is explained in 4.3.1. FREE takes a variable (or pointer to a variable, for an uncounted zone) vcontaining a reference r to a variable fv. The reference r must be supplied by the NEW proc of thesame zone; this is checked for a ZONE. FREE sets v (or v^) to NIL. In addition: f2qG,G?ry_srXqrqr ^Wqr!qr \s r/qr [O:yYyXG! V*qr RvX OrV NP L If? G v r- F^U D A0 @+yxrXqrsrqGrtrsr*X >yxrqrsrqGrtrsr*X =#yxrqrsrsrtrqGr*X 9vr'0 8tAxrxr 6 3/qr" 2Av r 0qrXqrsrsrtrqG xr*X qrsr -xr x r*xrs ,rqrqrqrsr xrsrqrqrsr (vX $r #`xrXqrsrqrtrsrxrqr !qrqrsrsrsrqrtrsrxrsr  XqrqGrsrXsrsrxrxrsrtr*qr qrqG rsrXsr* PzO$srXxrxrsrtr %$qrxr|rsrqrxyxrsrsruqrqrxr|rsrqrxyxrsrsrsrqrsrxr|rsrqrxyxrsrsrsrqr  qr qrqrqrqrqr s Arqr2 qr qrDs r srsrsrqr qrqrsrsrqr  vTVk(M CEDAR TYPES, PART 2DRAFT OF JULY 20, 198258For a ZONE, FREE sets all the REF variables of fv to NIL; this helps to break circularstructures, but only the collector actually reclaims storage. Hence FREE for a ZONE is safe.For an uncounted zone, FREE reclaims the storage for fv by calling the Dealloc proc of thezone (see below); hence FREE is unsafe for an uncounted zone; the safety invariantdemands that FREE not be called with a pointer unless the variable will not be used any more. It is best if no other pointers to fv exist. New zones can be obtained, and other aspects of storage allocation monitored and controlled, usingthe procs in SafeStorage (for ZONEs) or UnsafeStorage (for uncounted zones). It is also possible,though not recommended, to make up your own UNCOUNTED ZONE using a type like this:UncountedZoneRep: TYPE~LONG POINTER TO MACHINE DEPENDENT RECORD [procs (0: 0..31): LONG POINTER TO MACHINE DEPENDENT RECORD [Alloc (0): PROC[zone: UncountedZoneRep, size: CARDINAL]_[LONG POINTER],Dealloc (1): PROC[zone: UncountedZoneRep, object: LONG POINTER]-- possibly followed by other fields-- ],data (2: 0..31): LONG POINTER-- Optional; see below-- possibly followed by other fields-- ];The same structure serves for a MDSZone, with all the LONGs dropped and the field positionsadjusted accordingly. You must use a LOOPHOLE to turn one of these Rep values into an uncountedzone value.If z is an uncounted zone, the code generated for z.NEW[T] isz^.procs^.Alloc[z, SIZE[T]]and the code generated for z.FREE[p] is{temp: LONG POINTER~p^; p^_NIL; z^.procs^.Dealloc[z, temp] }Usually p is @q, for some variable q which holds the pointer being freed. Within this framework, you may design a representation of zone objects appropriate for yourstorage manager. In general, you should greate an instance of a UncountedZoneRep for each zoneinstance. The procs record can be shared by all zones with the same implementation; the datapointer normally references the state information for a particular zone.4.5.3 POINTER TO FRAME typesIncomplete. Notes:POINTER TO FRAME: Construct with implementation (and NEW?)can put impl p in DIRECTORY as well as interfimporting pi: p gives pi the same type as PTF[p]there is a coercion from pi to the PROGRAM type for the implPTR TO FRAME by NEW on PROG or PTR TO FRAME, or by import.4.5.4 RELATIVE typesSometimes it is convenient to have addresses which are relative to the base of some region. Suchpointers can be shorter than ordinary pointers. Also, the entire collection of variables in the regioncan be moved in storage simply by changing the base; in fact, it can be written out and later readin to a possibly different place, and any relative pointers stored in it will still be valid. Cedarprovides some (unsafe) support for this facility, in the form of RELATIVE types. A RELATIVE typehas a range type which is an ordinary pointer or descriptor. The RELATIVE type has noDEREFERENCE or APPLY proc. The only useful thing to do with a RELATIVE value is to apply asuitable BASE POINTER to it ( 4.4.4). To indicate the desired size of a RELATIVE POINTER value, the type constructor can specify asubrange of CARDINAL. There are coercions between RELATIVE POINTER types which differ only intheir subranges; these are just like the coercions between subranges of CARDINAL ( 4.7.3). f2qG,G?r_qrqrqr srqr^W 9qrqr[qrsrsrZ{qr6XqrFWs)sr THD Rs rqrs r, Q@&qrqr OsrXqrqG$rXyN8sr qG$rXLsrqrsrsrsrqrtrqGrK0srXqrsrsrsrqGrIX'yH(sr qG*rXyF) E srqr  Cqrsr B >sr.srqrsr =isrsrsrsrXqrsr ;srqrsr :asrXqGrsrXsrqrsrsrsrsOrX 8srsrsr& 5A 4.4sr 2srEs 1&rA -'vX}v}v}v ){  &qrqrqr%qry%X srqry# srsrsrqrsry!srqry zqGrXqrqrqGrX {v}v Pr.vr! 8& H7+ 01 @, qr qr  (qr 8x rqr qr qrqr qrqr* qrqrqr Cqr  TVk(& CEDAR TYPES, PART 2DRAFT OF JULY 20, 198259This class has names:BASE: TYPE;-- The type of the base pointer.SUBRANGE: SUBRANGE.TYPE-- The subrange type; only for pointers.RANGE: TYPE;-- If b: BASE and rp: T then b[rp] has type RANGE.4.6 Record and union typesRecord types are Cedar's facility for grouping values of different types (since group and bindingtypes cannot be denoted). Unions are closely related to records because they must be embeddedwithin records in current Cedar.4.6.1 Record types The MKRECORD type constructor takes one argument called fields: a declaration or cross type. If fieldsis a cross type, it is rebound to a decl with secret names. If fields=[n1: T1, n2: T2, ..., nk: Tk],MKRECORD produces a type with the clusterni: PROC[T]_Ti-- One for each name in the decl.FIELDS: DECLCONS: PROC[b: FIELDS]_[T]-- Apply by T[b]; a coercion from the binding.UNCONS: PROC[T]_[fields]-- No denotation; a coercion to the binding.Cross type fields are not very useful, since there is no way to name the field procs. The values of theni procs are not accessible; they can only be applied with dot notation. Thus if r is a record value,r.ni denotes its ith field.A record type T with a single component or type U inherits all of U's cluster. There is also acoercion from T to U. The effect is that a T value behaves just like a U value, but not vice versa.A sequence-containing record also inherits some procs from the sequence type ( 4.4.2.2).If v is a VAR U returned by a field proc, you can only apply @ to it if SIZE[U]>1, or U'srepresentation occupied an entire word, or by accident v happens to occupy a whole word in therecord representation.Record types in interfaces are painted: each type produced by RECORD[...] (i.e., by MKRECORD orMKMDRECORD) in an interface has a unique mark. Thus two occurrences of a record type constructorin an interface always produce two different types. In this respect, recordTCs are likeenumerationTCs, and differ from all other type constructors. In a program module, however, recordtypes are not painted; this is so that old values will still be useful after module replacement. Sincethe painting of record and enumeration types is the only way to generate unique marks, it is theonly way that an implementation can guarantee that its types cannot be forged. In practice, however, the protection afforded by opaque types ( 4.3.4) is usually adequate.Representation: A record variable is represented by a contiguous block of words, in which the bitsrepresenting each field are contiguous and do not cross a word boundary unless they fill a block ofwords, but are otherwise arranged at the discretion of the compiler. It is not possible to obtain aREF to a row element; this is because the implementation of both reference counting and ref anydiscrimination requires more information about each VAR than is available for a record field. Unlessa field fills one or more words, it is not possible to obtain a pointer to the field either (using @);this is because addresses point to words.A MACHINE DEPENDENT RECORD type constructor can specify the exact arrangement of the fields ina record, using the syntax of rules 46-48. Examples are given with the rules. Fields must bearranged according to the following rules.A pos48 (w) means that the field occupies word w, or bits 16w through 16w+15, of therecord variable; (w: f..l) means that it occupies bits 16w+f through 16w+l (0v rN  !6 60- qrRs .r &xr  Y &% qrqrqr' wA "  (w rsr%sr sr sr  srsrsrsrsr srsrtstsrsr srsrsr TVk(2 CEDAR TYPES, PART 2DRAFT OF JULY 20, 198260The pos must be large enough to hold a variable of the field type U: if SIZE[U]>1, it mustcompletely fill at least SIZE[U] words; if SIZE[U]=1 and U is a discrete, row, or record typerepresented in less than 16 bits, it need only be as large as the representation, but may notcross a word boundary. Union fields are treated specially ( 4.6.2).Fields may not overlap, and together they must completely fill an integral number ofwords. The order of fields is not important.If any field has a pos, each must have one. A machine dependent record may have no pos.This form is not recommended. If it is used, the fields are arranged consecutively, and theconstructor must be such that that the rules about word alignment and boundary crossingare not violated by this arrangement.Note that a pos is really an explicit specification of the field proc, written in a rather restrictivespecial language.4.6.2 Variant record typesThere are two classes, unions ( 4.6.3) and sequences ( 4.4.2.2), whose types are not first-class typevalues, but can only appear as the type of the last field of a record or union. A record whose lastfield is one of these types is a variant record, and its last field is a variant field. The other propertyshared by a union and a sequence type is that each is a generalization of a number of special cases;there is a single value called the tag which identifies the special case. For a union, the special cases are unrelated, and the tag is a value from an enumeration. For a sequence, the special cases are rows of different length, and the tag is a value fromthe row's domain. The tag50 is treated as a field of the containing variant record. This field is readonly. For a union itcan be changed only by assigning to the entire variant part or the entire variant record; if either oldor new variant is RC this is unsafe. There is no way to change the tag field of a sequence. A tag ofCOMPUTED or OVERLAID means that there is no tag field; instead, the tag value must be supplied byan expression in a withSelect34 when it is needed for specialization. Tags of * and OVERLAID areonly for unions, and are explained in 4.6.3.The cluster of a variant record has the following items:The usual procs for the record fields (including the variant field itself, and the tag), and any procsinherited by the record type.TAGTYPE: TYPE-- The type of the tag.TAG: TAGTYPE;-- Another proc for the tag field.VARIANTTYPE: TYPE-- The (union or sequence) type of the variant field.VARIANTPART: PROC[T]_[VARIANTTYPE]-- Another proc for the variant field.SPECIALIZE: PROC[n: CARDINAL]_[BT: TYPE]-- A bound variant of T; denoted T[n].Specialization yields a record type called a bound variant in which the type of the variant field isone of the special cases of the union or sequence. The bound variant lacks SPECIALIZE, its tag fieldis readonly, and its VARIANTTYPE is the special case. Note that if the special case is itself a union orsequence, the bound variant is still a variant record; otherwise it is an ordinary record.Anomaly: A variant record type has EQUAL only if it does not have a SEQUENCE field, and for anytwo tag values a and b, SIZE[T[a]]=SIZE[T[b]]. Even if not all sizes are equal, however, EQUAL isallowed if one of the operands is a bound variant.The special properties of the subclasses of variant records are given in the sections on unions (4.6.3)and sequences (4.4.2.2). f2qG,G?r_?srqrsr^W qrsr qrsrsr#\ N[O@XNWs&UUS,+R '%P" Md] K GvX DrQ C22* Av rv r @*C >vr$ symbols of the SELECT in turn. If the tag type is given explicitly,any enumeration values which don't appear preceding a => symbol have empty fields.A record type T containing a union field is a variant record. T is a first-class type which can beused like any other Cedar type. The only operations in the cluster of T are the ones of the variantrecord class. The fields of the union cases are not in the cluster of the variant. However, the fieldsof the selected case in a bound variant are in the cluster (e.g., Node[binary] has procs for a and b, inthe example of rule 49). The names declared in a field must not be the same as any name declaredin the containing record. However, the same name may be declared in more than one case of theunion. NULL following => is an obsolete synonym for [].Anomaly: A constructor for a union value has the form a[...], where a is one of the enumerationliterals of the tag type, and [...] is an ordinary binding for the fields of case a. The literal a may notbe omitted. Thusn: Node_[rator~plus, rands~binary[a~NIL, b~NIL]]Anomaly: If n is the name of the variant field, and r: T, r.n is legal only as the first operand of _.In all other cases, only a constructor can denote a union.The primitive ISTYPE can be used to distinguish the case of a variant record value x, and NARROWcan be used to obtain a value bx of the bound variant type from x; see 4.3.1. The safeSelect32construct is a useful and efficient combination of ISTYPE and NARROW which deals systematicallywith any number of cases. The withSelect34 construct is an unsafe version of safeSelect which canbe used with any union type, and is the only alternative when the tag is COMPUTED or OVERLAID.See 3.8 for discussion of these forms.If the tag is OVERLAID, any field name that appears in exactly one case of the union has a proc inthe cluster of the variant record. When such a proc is applied to a value x, there is no checking thatx is the proper case of the union. Obviously this is not typesafe, and if the field is RC it is unsafe. f2qG,G?r _vX \rqrqr#sr [,sZw[,rsZ[,r#sr Y>sXY>rqrqrVqrsrqrqr.Tqrsrqrqrqrqr qrsr R6<O5qrxrNZ$/L J~Mqrqr H&M D#EwDr0vr CwY A34 @o) =D1qr ; /sr :< srsrsr1s 8rA9Ew8r 74.qr. 5O 2 sr/sr# 1Bsr /}G -@srsrsrsr ,u8% *W )mqr, &Bvrsr sr $Jsr sr #: !srXsrsrsrsrsrsrqrsrqr vrsr'srsrsr 8  qr?srq Xrsrsrw r*qrqr PwPr7 Bqrqr H% qrL ?sr srgvTVk( CEDAR TYPES, PART 2DRAFT OF JULY 20, 198262A union has machine-dependent fields if and only if its containing record is machine-dependent.The union field must be last both in the fields and in the representation. Its pos includes the tag. Itneed not be word-aligned, though its tag and each field in each case must obey the alignment rulesfor record fields ( 4.6.1). If the union field is <16 bits in size, all cases must be the same size.Otherwise, all cases must be a multiple of 16 bits in size, and at least one case must exactly fill thespace for the union field.4.7 Ordered typesOrdered types can be compared, and they have subranges. The subclasses are discrete, numeric,pointer, and subrange. The class has namesLESS: PROC[T, T]_[BOOL];-- Apply by infix <. See rules 19, 22.GREATER: PROC[T, T]_[BOOL];-- Apply by infix >. See rules 19, 22.IN: PROC[T, SUBRANGE]_[BOOL];-- Apply by infix IN. See rules 19, 22.MAX: PROC[T_FIRST[T], ...]_[T];-- Apply by MAX[x, y, ...].MIN: PROC[T_LAST[T], ...]_[T];-- Apply by MIN[x, y, ...].All these procs do just what you expect. MAX and MIN accept more arguments than you can write.Pointers have these procs only if ORDERED=TRUE.The cluster also has names:SUBRANGE: CLASS;-- The class of subrange types of T.MKSUBRANGE: PROC[first, last: T]_[SUBRANGE];-- See rule 25 for denotations.MKEMPTYSUBRANGE: PROC[first: T]_[SUBRANGE]-- See rule 25 for denotations.These are discussed in 4.7.3 4.7.1 Discrete typesThe discrete types are those which have a useful bijection into an interval of the natural numbers:whole numbers and enumerations. These are the types that can be used as domains for row types (4.4.2). The class has names:FIRST: T-- Denoted FIRST[T]LAST: T-- Denoted LAST[T]PRED: PROC[x: T]_[T]-- Predecessor, apply by PRED[x]. May cause a bounds fault.SUCC: PROC[x: T]_[T]-- Successor, apply by SUCC[x]. May cause a bounds fault.Whole numbers are discussed in 4.7.2 as a subclass of numeric.4.7.1.1 Enumeration typesAn enumeration type is isomorphic to a [0..k] subrange of the integers, without any of thearithmetic operators. The values are named by literals which have the same syntax as names. Theenumeration type {n0, , ..., nk} has in its clustern0: T;-- Denoted T[n0]. . .nk: T-- Denoted T[nk]Procs to convert between T and INT are lacking.Enumeration types in interfaces are painted; each type produced by {...} (i.e., by MKENUMERATIONor MKMDENUMERATION) in an interface has a unique mark. Thus two occurrences of anenumerationTC always produce two different types unless both are in implementations and aretextually identical. In this respect, enumerationTCs are like recordTCs and differ from all other typeconstructors. f2qG,G?r _X ^W,8 \X [OF Y > XG StuX PIrV N" MAxrXqrsrsrtrqr*& Kxrqrsrsrtrqr*& J9xrqrsrxrtrqr*qr Hqrqrsrqrsrtrsr* qrsrsr G1qrqrsrqrsrtrsr* qrsrsr Eqrqr* D)qrqr @ ?zxrXxr*"s =x rqrsrsrsrtrxr* T =#) 9!qrqr 8t9w8tr9w8tr2qr 6qr' 5l( s r 3s rqr 0vr<#.e3#, tr,w, rvr0*qrqr9)Dq'r(w'r(w'r)(w'r%qr/qrsr sr $y:"sOrX:!qsrqrsrsr:srqrqrsrsir srsr(srsrqrqr Tb9 ' 2.S# R$9 & RTVk( CEDAR TYPES, PART 3DRAFT OF JULY 20, 198265Note that literals are always non-negative; a static negative value can be obtained by arithmetic;e.g., 1.Performance: Short values are represented in one word; other INT values require two words. Therepresentation is twos complement, with one more negative than positive value. Arithmetic is lessefficient on subranges with FIRST=0 (except for INTEGER, which is efficient). Widening a shortvalue to INT is more efficient if FIRST=0. Multiply and divide are quite slow when the argumentsare not short. Short divide is faster when FIRST=0 than for INTEGER. Cardinal typesThe type LONG CARDINAL has elements in the range [0..232); CARDINAL is the subrange [0..216).The arithmetic procs produce answers modulo 232 (or modulo 216 if all arguments are shortcardinals). Use of these types is not recommended, mainly because there are confusing coercions toand from INT. If you program so that these coercions are never invoked, by never mixingCARDINAL and INT values, you will avoid thses problems; in the future Cedar will not have thesecoercions, and cardinal types will be harmless.ComplicationsCurrent Cedar attempts to do the "right" thing when subranges of INT are mixed with subranges ofLONG CARDINAL in an arithmetic proc, by supplying various coercions which may lose information.Do not use these features (unfortunately, the compiler won't check for their non-use); if you needto understand them, consult a wizard.4.7.2.2 The type REALCedar uses the IEEE standard 32-bit floating point arithmetic for REALs. There are REAL literals withsyntax given in rule 57; they are rounded to the nearest representable number. The exponent, ifpresent, indicates the power of 10 by which the number or fraction should be multiplied. A literalthat overflows the representation is a static error; one that underflows is replaced by itsdenormalized approximation. Note that a REAL literal can begin, but not end, with a decimal point.Exceptions? Changing modes, etc? Is there an interface?4.7.3 Subrange typesEach discrete type U has a MKSUBRANGE type constructor; its application is denoted by the syntax inrule 25. The first and last arguments specify the first and last elements of the subrange; the FIRSTand LAST items in the subrange cluster have these values. The number of values in the subrangetype is lastfirst+1. The subrange is empty if lastsrqrsr "x r wtsrwrXqrsrsrtrwr d; x rXqr*x r*\x rsr xrqrsrsrtrx r*  Tx rqrsrx rtrsr** s r srsr LM  .s r DTVk( CEDAR TYPES, PART 3DRAFT OF JULY 20, 198266subrange. Subranges also inherit all the procs of the ground type unchanged; these procs still takethe same arguments, and the coercions make it convenient to apply them to subrange values. Thereare no special arithmetic or comparison procs for subranges. Representation: If T is a subrange type, FIRST[T] is represented the INT 0 (except for INTEGER,which has 0 represented by 0), and LAST[T] by the INT (LAST[T]FIRST[T]+1). The number of bitsrequired to represent a T value is the n such that 2n1<(LAST[T]FIRST[T]+1)<2nIn current Cedar, a subrange value always fits in one word, because a subrange may not have morethan 216 values.4.8 TYPE typesAll type values have type TYPE. TYPE is not a general type; it lacks SIZE, NEW and the other generalprocs nearly all types have. Furthermore, in current Cedar a type can't be passed as a parameter,with two exceptions:An interface type parameter can be declared in a DIRECTORY statement, and the resultinginterface type can be used to declare an interface parameter in an IMPORTS clause. Theargument for this parameter is supplied by an implementation which exports the interfacetype.An opaque or exported type can be declared in an interface module. An implementation ofthe interface provides the actual argument.A type also can't be returned as a result, with two parallel exceptions:an interface type is returned by an interface module;an exported type is returned by an instance of an implementation. The other possible uses of a type value are these:Certain primitives take type arguments: CODE, DESCRIPTOR, ISTYPE, LOOPHOLE, NARROW,NEW, SIZE and a number of type constructors. A type value appears in a declaration, after a colon; e.g., i: INT.A type value appears as a value bound to a type name; e.g., T: TYPE~INT.In current Cedar, type expressions and ordinary expressions do not have the same syntax. Thesevere restrictions on where types can be used ensure that the parser can distinguish the cases wherea type is expected. There are a few cases where this is not true, and type names (rule 37) must bewritten instead of general expressions: subrange type constructors, ???.The runtime type system (ref ???) provides complete facilities for manipulating types duringexecution of the program (but currently not for constructiong them). The type values it manipulateshave the type RTT.Type, rather than TYPE. A RTT.Type can be obtained from a TYPE using theprimitive:CODE: PROC [T: TYPE]_[RTT.Type].In a number of cases the syntax T[x] (applying a type value) can be used. Depending on the class ofT, the meaning varies. The cases are summarized here, and described in detail in the appropriatesection above:TYPE applied to a static integer n yields an opaque type of size n ( 4.3.3).An array or record type applied to a group or binding yields a record value; this is called arecord constructor ( 4.4.2.1, 4.6.1).A sequence-containing record type applied to a not necessarily static CARDINAL yields arecord type containing a sequence of definite length, which can only be used in NEW andSIZE ( 4.4.2.2). f2qG,G?r _Z ^W> \: Yv rsrqrsrqrqr X$qrsrqrqrsrqrsr Vsr sr UXUwUrqrsrqrsrtrU SrP RRwRr MAuX Jrqrqrqrqr HB GD/qr C2)qr A1@*=vrvr= qrqr  *TVk( CEDAR TYPES, PART 3DRAFT OF JULY 20, 198267A variant record type applied to a static tag value yields a bound variant type ( 4.6.2);An enumerated type applied to a name which is one of the enumeration literals yields thecorresponding enumeration value ( 4.7.1.1).A subrange type (including NAT, INTEGER, or CARDINAL) applied to a value of its groundtype yields a subrange value ( 4.7.3);What about TYPE n?4.9 Miscellaneous typesCONDITION | MONITORLOCK |UNSPECIFIED | LONG UNSPECIFIEDIncomplete4.10 Kernel-only types --kernel only-- exception | DECL | BINDINGIncompletenotes followexceptionsNEWEXCEPTIONCODEVALUE: TYPE=RECORD[ SELECT tag: {normal, exception, hiddenException} FROMnormal => [v: *T],exception => [code: EXCEPTION[*A, *R], args: *A]hiddenException => [ex: VALUE[exception] , depth: INT]ENDCASE ]CURRENTEXCEPTIONEval[e]W WITH BasicEval[e]. SELECT FROMe: normap => n,ex: exception => ex,hex: hiddenException => IF hex.depth=1 THEN hex.ex ELSE [hiddenException[hex.ex, hex.depth-1]ENDCASE4.11 DefaultsA default in a type cluster provides a value which is supplied automatically in a binding where novalue is explicitly given. Example: PutInt: PROC[i: INT, radix: [0..100]_10]makes PutInt[i~x] short for PutInt[i~x, radix~10]. This is very convenient for infrequently-usedarguments, or if arguments are added to a widely-used proc. In summary, the usual cases for defaults and bindings are: f2qG,G?r_Y]"4[ Y qrqrqr"X## T{ v{ OuX Mqrq rq rqG J8{ EeuX C1qGrX qrq ?{ >;r sr(x=!rsrsr:srqrtrsrsr 9E sr%s7rB6= xr 3x r," 2a5y0x rXqrsqGrXsrqGrtrsrXsrqrtrsrqr /Ysr'sr -s rsrsrqrsrsr+})%s rsrsrsrqr srsr 's rqr $vMsr "sr \ Cxrsr!srxrg s rxrsrsrsrsrxrsr sr_.sr=xr?qr3srqr#qr.$ 7 8TVk( CEDAR TYPES, PART 3DRAFT OF JULY 20, 198269The effect of these rules is that binding [n1~e1 ...] to [n1: T1 ...] has the same effect as binding any of[n1~ ...], [...], or [ , ...] to [n1: T1_e1 ...] (assuming that any free variables have the same bindings inboth cases).Primitive types and those returned by primitive type constructors (except CHANGEDEFAULT) have aTrash proc and a Default proc equal to the Trash proc, with the following exceptions:CONDITION, MONITORLOCK and PORT have no Trash or Default; they do have an INIT procwhich sets any variable to NIL.REF and PROC types have no Trash and a NIL Default.Bound variant records have no Trash and a Default which sets the tag value appropriately.Record and array types have a Trash or Default if all their component types do; it is theobvious concatenation of the component procs.Including the various dangerous uses of TRASH which omit initializations, we get a larger and moreconfusing summary table which should be ignored except by efficiency hackers.:Default type constructor|T_T_eT_e | TRASHT_TRASHT in domain/ range declDefault|l [] IN el [] IN eT.TrashTrash|T.TrashT.TrashDeclaration|n: T_n: T_en: T_e |TRASHn:T_TRASHn: TBinding short for|n~xn~x|xxxxxn~ or nothingn~OMITTED|ERROReeT.Trash[]ERRORn~TRASHn~TRASH|ERRORERRORT.Trash[]T.Trash[]ERRORTable 47: Complete cases for defaults4.12 ImpliesA type T implies another type T( (TgT( for short) if for any value x, T.PREDICATE[x]gT(.PREDICATE[x]In other words, if any value that has type T (satisfies T's predicate) also has type T(, then T impliesT(. A consequence is that a proc with domain type T( can safely be given a value of type T, sincethis value must also have type T(, as required by the proc. We also say that a T value is as good asa T( value.If T's predicate includes a test for some mark, then any type which implies T must test for the samemark or a bigger one. For instance, if R is a variant record type with variants a, b, and c, thenR[a]gR if SIZE[R[a]]=SIZE[R]. In fact, the predicate for R[a] tests for R's mark and for a tag equalto a. In other words, a bound variant value is as good as an unbound one.From the implementation's viewpoint (and after all, it is the implementation of an abstraction thatis responsible for attaching marks), two values should have the same mark only if they both haverepresentations with all the properties implied by that mark: occupy at least that much space, havethe proper fields interpreted in the proper way, etc. This is the rationale for marks: to distinguishvalues which are not acceptable to the same primitives. Of course this is not an enforceable rule:nothing prevents an implementation from unwisely allowing the marks it controls to be applied tounsuitable values. f2qG,G?r _(s_Nw_rs_Nw_rs_Nw_rs_Nw_r+ ]s]`w]rsrs]`w]rs]`w]rs]`w]r5 [ X8x r WPsr srsr%Tqrq rqrsrsrxrStqsQqrqrsrqrsNrsrsr(Ll srsr+J& G qr5 F9E Cf *C *Cf C  CfC!}Cf*C*(CfC/Cf C 9 Cf+C+@8CfC A !}sr(srs/srsrq9 srq@8sr @8@ ?;0 >s r!}(|rqrs/|rqrs9 @8r ^W@ \M [Oa Y9& XGtstrtstr Usr strsrstrsr S T R>sr P stsr@ O Z M/3 L= J GU7DJB$qr stsrtrststrstsrA!ststr6ststrstr ?strstsrsr srsr*> strsr; qrstqrsrstsr:=+qr%sr8sr'qrsrqrsr75sr*qr5 /qr4-qsrsrtrsr,2" /~E -B TVk(Z CEDAR TYPES, PART 3DRAFT OF JULY 20, 198271 In current form In kernel formThese typesImply these typesRemarksThese typesImply these types[n: T , ...][n: T( , ...]if TgT([n: T , ...][n: T( , ...]Pointwise extension to bindings. Likewise for groups.TU declared by U: TYPETFULLYOPAQUE is fully opaque.TU declared by U: TYPE[n]if SIZE[T]=n ...TOPAQUE[n]... and T has the standard NEW, INIT, ASSIGN and EQUAL procs. U is n-opaque.READONLY TVAR TREADONLY TREADONLY TREADONLY T(if TgT(READONLY TREADONLY T(PROC/ERROR/...PROC/ERROR/...if T(gTMKXFERTYPE[MKXFERTYPE[ [T] [T(]and domain~T, domain~T(, RETURNS [U] RETURNS [U(]UgU( range~U] range~U(]Note the reversed implication for the domain type.SAFE PROC/ERROR/...UNSAFE PROC/ERROR/...MKXFERTYPE[MKXFERTYPE[ safe~TRUE] safe~FALSE]ARRAY ... OF TARRAY ... OF T(if TgT(MKARRAY[range~T]MKARRAY[range~T(]If PACKED=FALSE or SIZE[T]>1. If PACKED=TRUE and SIZET]=1, the number of bits required torepresent a T and to represent a T( must be equal when rounded up to the next power of 2. Likewisefor SEQUENCE and DESCRIPTOR.REF TREF READONLY TMKREF[range~T, MKREF[range~T, readOnly~FALSE]readOnly~TRUE]and likewise for POINTER and LIST.REF READONLY T REF READONLY T(if TgT(MKREF[range~T,MKREF[range~T(, readOnly~TRUE] readOnly~TRUE]and likewise for POINTER and LIST.REF TREF ANYMKREF[range~T]MKREF[range~ANY]ORDERED POINTER TO TMKPOINTER[range~T, MKPOINTER[range~T, POINTER TO T ordered~TRUE] ordered~FALSE]BASE POINTER POINTERand vice versaMKPOINTER[ MKPOINTER[base~TRUE] base~FALSE]T[tag: x]Tif SIZE[T[tag: x]=?????? SIZE[T]A bound variant implies the unbound variant.RECORD[n: T]T1-element recordMKRECORD[fields~[n: T]] Tand likewise for MACHINE DEPENDENT RECORD.(PROC[A]_[n: T]).RANGE T1-element binding[n: T]T(PROC[A]_[T]).RANGET1-element groupCROSS[[T]]TT[x...y] etc.TT.MKSUBRANGE[x, y]Tif T.FIRST=x and SIZE[T[x...y]]=SIZE[T].T[x...y] etc.T([x...y] etc.T.MKSUBRANGE[x, y]T(.MKSUBRANGE[x, y]if T.FIRST=T(.FIRST and T.LASTt'G5pqr@r = < = < 'G= < 5= < A=E<Ea8vX# 4){ 0t5# /z%-"ututututut+u+tut )F&ututututut $"= # ut5}utututwtututututut utwtu ztu ztu ztu ztu rtu rtut~tu ztu ztu rtu rtwututuzturt R ut!ut" ut utuAztuArt utututuSztuSrt( #ut $; C/ut( }utR ;LTVk( CEDAR TYPES, PART 3DRAFT OF JULY 20, 198274Object notation is the most general, since any opaque or record type T defined in an interfaceacquires a user-defined a cluster by this method. The current implementation is rather clumsy: allthe procs in the interface I from which T comes are added to T's cluster, with the names they havein I, except those whose names are already in T's cluster. Of course, an element of this cluster isonly useful if it takes a T as its first argument.The interface I from which P is obtained is normally an interface instance I (which is imported),not an interface type IT (declared in the DIRECTORY clause), because only the instance provides aproc value for P. Of course if P is bound to an INLINE in IT this is not true. See 3.3 for more ininterfaces.Restriction: In current Cedar, the value for P always comes from the principal imported instance ofIT (see 3.3.3). This is of no concern if only one IT value is imported. If more than one IT value isimported, however, confusion can result. If it does, consult a wizard.The cluster for a record type R is formed automatically by the record type constructor, and simplycontains a procedure for each field f: Tf, which takes an R and returns a Tf. There are similarclusters for VAR R and READONLY R, in which the procedures take VAR or READONLY R and returnVAR or READONLY Tf.An interface type yields a binding, which contains those names which are bound in the interfacerather than simply declared (usually constants and types, sometimes inline procs). An interface value(imported interface) can also be thought of as a binding, with a value for each name in theinterface. Actually it is more like a record; its cluster contains a proc for each name declared in the interface, whichreturns the exported value when applied to the interface value. f2qG,G?t _$ut ^WFv \tut ut ut$ [Out)ut4 Yut V ut ut&vtut U vtut qt. S ututqtut R Nv t!ut ( Meut-ut%ut K= HutC G2utuFrG2tutuFrG2t EDqtutqtutqtqtut CqtqtuC3rCt @G ?O =; < q76 :8.TVk( CEDAR TYPES, PART 3DRAFT OF JULY 20, 198275CaseSource for nDe.ne.ne.n[p2~x, ...]Meaningcan't write this(De).n[e](De).n[e][p2~x, ...] orliterally.(De).n[p1~e, p2~x, ...] Object n:PROC[self:T_TI.n WI.n[e], since*notationdeclared in same nWI.n(De must interface I as De. Useless unless De coerces to T.be record or opaquen: PROC[self: T, I.n No (can't get theWI.n[self~e, p2~x, ...]type).p2: T2, ...] declaredvalue of the curried proc).in same I as De. Useless unless De coerces to T.RecordRECORD [..., n: T, ...]No (can't get theWa VAR T for *record selector field n of record e.value).Imported IT: DEFS{...; n: T;...};No (can't get theW the value exported*interfaceDIRECTORY IT: TYPE; interface selector as n in the e instanceIMPORT e: IT;value).of IT.Interface IT: DEFS{...; n: T~v;...]No (it would Wv (need a binding *typeDIRECTORY e: TYPE IT;be TYPE.n).for n, not just n: T).* Only if T is a proc type with the right domain.Table 410: Cases for dot notation in current Cedar f2qG,G?t `3!_!`3L_L#$`3 _ 0`3 _ >`3E_EF`3E_E ^W{{tu#$}utu0utu>ututu]z^Wtut [{#$t0}ututut>}utututu[rz[tut #$Z >}ututuYzZtutuYzZtut X!FXLF#$X F0X F>XEFFXEF Vvtutqtutu}u#$utut0}utut> Uvt#$0u}u St}ut ut}ut}ut u Rt Putqtutut#$utut0>}ututututuPzPtut NuNzNtuNzNt0Lut}ut}ut u Ivqtutut#$0}tqtut>#$H0ut ut#$F CUvtutqtutut#$0}t> Avqtutqt#$0utut@Mqtutut#$0ut ="vtutqtututut#$ 0}ut> ;vqtutqtut#$qtut0ut utut 8s ut& 7!6!7L6L#$7 6 07 6 >7E6EF7E6E2vX.TVk(, TimesRoman  TimesRoman  TimesRoman  TimesRoman  TimesRoman TimesRoman  TimesRoman TimesRoman TimesRoman  Helvetica  Helvetica   TimesRoman  Hippo  Math  TimesRoman TimesRoman Helvetica TimesRoman TimesRoman TimesRoman TimesRoman  TimesRoman  TimesRoman  Helvetica TimesRoman  TimesRoman   TimesRoman  TimesRoman   TimesRoman Math Hippo MathMath TimesRoman TimesRoman  TimesRoman Math  TimesRoman  TimesRoman  TimesRoman Helvetica  Helvetica   TimesRoman   TimesRoman  Hippo   TimesRoman TimesRoman TimesRoman TimesRoman TimesRomanr   ,& /7> H mR 4]d m w 9D $ [ n J O t <    % /3 <? H0P Y ebe DoMv K_E   w  B m    T     $& >/4 6= GN IX_ jpuj/|Ly0CLRM.bxLampsonJuly 21, 1982 12:42 AM