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 (І÷32.2), and aless formal explanation of the ideas of the kernel and the restrictions imposed by currentCedar (ІІ÷32.3-2.9). І÷32.1 contains an overview or glossary, in which the major technicalterms used in 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 (І÷34.1).In addition, there is a one-page grammar for the full language, a shorter grammar for the safelanguage, and a two-page language summary which includes the grammar, the desugaring, and theexamples from І÷3, The document you are reading is nearly complete. A fe missing sections containparagraphs in the style of this one.Н!ДО_∙pТjНЇО\jqТ─ПMНґОZТ▌П$rqТ▐НґОX▌ТґТўП?НґОW Т╔П'ТіП/НґОU├Т╡П8ТЁНґОTТ─П(НґОQ╙Т┬П1Т┴П!НґОP&Т²r qТ·П:НґОN╒Т─П#rqНґОLJТ■rqП6Т∙НґОJфТ┐ПTТ└rНґОIBqТ─П!НЇОFТЎТ©ПIНЇОD⌠Т≤Т≥ПEНЇОCТ─НЇО?²sТУПCТЖНЇО=р Т─Ъ TVk(≥THE KERNEL LANGUAGEІ÷22Chapter 2. The kernel languageThis document describes the Cedar language in terms of a much smaller language, which we willusually call the kernel or the Cedar kernel. Cedar differs from the kernel in two ways:ЇIt has a more elaborate syntax (І÷3). The meaning of each construct in Cedar is explainedby giving 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 (І÷4). In the kernel language all ofthese could in principle be programmed by the user, though in fact most are provided byspecial code in the Cedar compiler. In general, you can view these built-in facilities muchlike a library, selecting the ones most useful for your work and ignoring the others.Unfortunately, the current Cedar language is not a superset of the kernel language. Many importantobjects (notably types, declarations and bindings) which are ordinary values in the kernel that canbe freely passed as arguments or bound to variables, are subject to various restrictions in Cedar:they can only be written in literal form, cannot be arguments or results of procedures, or whatever.The long-term goal for evolution of the Cedar language is to make it a superset of the kerneldefined here. In the meantime, however, you should view the kernel as a concise and hopefullyclear way of describing the meaning of Cedar programs. To help in keeping the kernel and current Cedar separate, reserved words and primitives of thekernel which are not available in current Cedar are written in SANS-SERIF SMALL CAPITALS, ratherthan the SERIF SMALL CAPITALS used for these symbols in current Cedar. Operator symbols of thekernel which are not in current Cedar are 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.,some 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 is a commentary which explains the conceptsbehind the kernel. It also gives the restrictions imposed by the current Cedar language on the fullgenerality described here; for more on this subject, see І÷3. The meaning of the various built-inprimitives is given in І÷4. І÷2.9 describes the incompatibilities between the kernel language andcurrent Cedar, i.e., the constructs in Cedar which would have a different meaning in a kernelprogram. For the most part, these are bits of syntax which do not have consistent meanings incurrent 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:Values and computations: Application Value Variable Group Binding Argument The type system: Type Type-checking Mark Cluster Declaration ClassPrograms: Name Expression Scope Constructors RecursionConveniences: Coercion Exception Finalization Safety ProcessMiscellaneous: Allocation Static PragmaН⌡Оf2tТGУНGNНЇqН%О_∙pТjНЇОY?qТёПAТєНЇОW╩Т─rqП@Н°ОUcНґТ²ПAТ·НґОSъТ─П&НґОQнtТ┼ПgНґОP░ТґП<ТўНґОOR Т─ПUН°ОLЗqНґТ²Т·ПMНґОKvТ°П8Т²НґОIРП/Т·П,НґОHnТ─ПQНЇОEC Т└П$Т┘П0НЇОC©Т²П5Т·П'НЇОB;Т╛П2ТґП.НЇО@ЇТ▄Т█ПTНЇО?3ТаТбПGНЇО=╞Т╡ТЁПPНЇО<+Т─П2НЇО9Т╡ТЁПWНЇО7|Т╒П8ТёuvuvuvuqНЇО5ЬТ√tqtqtqТ≈П<НЇО4tТ─П8НЇО1IТ└ПSТ┘НЇО/е Т▄rqТ█НЇО.AТуТжtqП=НЇО,ҐНЇО)▓ТїПZНЇО(Т÷ Т═ПMНЇО&┼Т⌠П!Т■П;НЇО%Т≥Т ПNНЇО#┌ Т╣ПWНЇО!Ч ТгПSТхНЇО zТйПJТкНЇОЖТ╪П9ТҐНЇОrТ─ПYНЇОGТ╟ПWНЇОцТ°Т²ПGНЇО?Т─ПYНґОГrqП4НґО▐rqП3НґО7rqП.НґО ъrqП0НґО┤rqєTVk(fІ÷2THE KERNEL LANGUAGE3The kernel definition in І÷2.2 follows the ordering of the kernel grammar given there.2.1 OverviewThis section gives a brief summary of the essential concepts on which the Cedar language is based.The explanations are informal and incomplete. For more precise but more formal definitions, seeІ÷2.2; for more explanation, see І÷2.3-2.8.2.1.1 Values and computationsApplication: The basic mechanism for computing in Cedar is applying a procedure (proc for short) toarguments. When the proc is finished, it returns some results, which can be discarded or passed asarguments to other procs. The application may also change the values of some variables. In theprogram an application is denoted by (the denotation of) the proc followed by square bracketsenclosing (the denotation of) the arguments: f [first~x, last~y]. There are special ways of writingmany kinds of application: x+1, person.salary, IF x<3 THEN red ELSE green, x: INT_7.Value: An entity which takes part in the computation (i.e., acts as a proc, argument or result) iscalled a value. Values are immutable: they are not changed by the computation. Examples: 3, TRUE,"Hello", l x IN x+3; actually these are all expressions which denote values in an obvious way.Variable: Certain values, called variables, can contain other values. The value contained by avariable (usually called the value of the variable) can change when a new value is assigned to thevariable. In addition to its results, a proc may have side-effects by changing the values of variables.Nearly every type T has a corresponding variable type VAR T; values of type VAR T contain valuesof type T. Every VAR type has a NEW proc which creates a variable of the type. A variable is usuallyrepresented by a single block of storage; the bits in this block hold the representation of its value.Group: A group is an ordered set of values, often denoted by a constructor like this: [3, x+1,"Hello"]. Like everything else, a group is itself a value.Binding: A binding is an ordered set of [name, value] pairs, often denoted by a constructor like this:[x: INT~3, y: BOOL~TRUE], or simply [x~3, y~TRUE]. If b is a binding, b.n denotes the value of thename n in b. Argument: A group or binding constructor written explicitly after an expression denotes applicationof the value P denoted by the expression to the value a denoted by the constructor, called theargument. P is usually a proc, and a is a group or binding, which is bound to its domain declarationD to get the argument which is passed. In making this binding a is coerced, if necessary, to matchthe declaration: If it is a group, the names from D are attached to its elements to turn it into a binding.If a name in D is missing from a, a default value is supplied.If a value in a doesn't have the type required by D, it is coerced into another value which does.2.1.2 The type systemType: A type defines a set of values by specifying certain properties of each value in the set (e.g.,integer between 0 and 10); these properties are so simple that the compiler can make sure that procarguments have the specified properties. A value may have many types; i.e., it may be in many ofthese sets. A type also collects together some procs for computing with the value (e.g., add andmultiply).More precisely, a type is a value which is a pair:Its predicate, a function from values to the distinguished type BOOL. A value has type T ifT's predicate returns TRUE when applied to the value.ЪНЇОf2tН3EТGУНGОqНЇО_шТ─ПSНЇО[wТXНЇОWщqТ▐П!Т░П=НЇОVYТїТ╗ПBНЇОTуТ─П%НЇОPжrТXНЇОM╚w qТ─ Т│П%rqrqrq НЇОL'rqТ≈Т≤ rqП%НЇОJёТЇП)Т╦П,НЇОIТаТбПDНЇОG⌡ТЇП$xqxqxqxqxqП$НЇОFТ─xqxqtqxqtqxqtqxqxqtqНЇОBЛwqТ╛ТґП>НЇОAhТ┴rqrq Т┼П*tqНЇО?ДТ─yqtqПOНЇО<╧wqТАrqТБrqП'НЇО;5Т═Т║rqП.rqНЇО9╠Т▓П-rqТ⌠П%НЇО8-Т≈xqП#uqxq Т≤uqxqНЇО6╘Т┌xquqtqТ┐П<НЇО5% Т─П[НЇО1ЗwqТбrqП#Тц r qxqНЇО0vТ─П1НЇО-KwqТ└rqП)rqТ┘П*НЇО+гxqТ▌tqxqtqtq xqxqtqtqxqТ▐ xqНЇО*CТ─xqxqНЇО'wqТ▌Т▐П;НЇО%■Т╩ xqП(xqТ╪ НЇО$Т│xqxqТ┌НЇО"▄xqТ≥П=xqrqТ НЇО!Т─ Н О└ТXxqП8Н ОxqxqrqН О| xqП#xqП.НЇО}rНЇОRwqТ≥Т ПHНЇОнТ┘Т├ПCНЇОJТ▌ПUТ▐НЇОфТ╣П)ТІП2НЇОB НЇОТ─П.НґО ©Т≤rqТ≥tq rqxqНґО;xqТ─tq √TVk(АTHE KERNEL LANGUAGEІ÷24Its cluster, a binding in which each value is usually a proc taking one argument of the type.The expression e.f denotes the result of looking up f in the cluster of e's syntactic type De,and applying the resulting proc to the value of e.A proc's type depends on the types of its domain and range; a proc with domain (argument type) Dand range (result type) R has the type D_R. Every expression e has a syntactic type denoted De,e.g., the range declared for its outermost proc; in general this may depend on the arguments. Thevalue of e always has this type (satisfies this predicate); of course it may have other types as well.Mark: 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.This does not imply a total ordering on the marks.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 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:Caller²establish pre-condition: arguments have the domain type;rely on post-condition: results have the range type.Body²rely on pre-condition: parameters 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]. If d is a declaration, a binding b has type d if it has the same set of names, and foreach name n the value b.n has the type d.n. A binding b matches d if the values of b can be coercedto yield a binding b( which has type d.A declaration can be instantiated (e.g., on block entry) to produce a binding in which each name isbound to a variable of the proper type; instantiating the previous example yields [x: VAR INT~(VAR INT).NEW, y: VAR BOOL~(VAR BOOL).NEW]. Class: A class is a declaration for the cluster of a type. For instance, the class Ordered is [LESS:PROC[T, T]_[BOOL], . . .]. C is a subclass of D if (loosely) C includes at least all the [name, type]pairs in D.2.1.3 ProgramsName: A name (sometimes called an identifier) appearing in a program denotes the value bound tothe name in the scope that the name appears in (unless the name is in a pattern before a colon(declaration) or tilde (binding), or after a dot or $). An atom is a value that can be used to refer toa name; a literal atom is written like this: $alpha.Expression: In a program a value is denoted by an expression, which is one of:a literal value (3 or "Hello");a name (x or salary); an application of a proc to other values(Sin[90];GetProperties[directory, ReadFileName[input]]);a l-expression, which yields a proc value (l [x: INT] IN (IF x<0 THEN ²x ELSE x) );a constructor for a declaration or binding ([x: INT~3, y: REAL~3.14]).If a value is given for each free name in an expression, then it can be evaluated to produce a value.Thus an expression is a rule for computing a value.Н⌡Оf2tТGУНGNНЇqНґО_шТ┘rqП1Т├П!НґО^WТ▓xqxqП"xqxqТ⌠zxqНґО\сТ─П-xqНЇОZ{Т│П/Т┌П/xНЇОXВqТ╒xq xzxqr qxqr qТёzxqНЇОWsТ⌡rqП?Т°НЇОUОТ─xqП\НЇОRдwqТ█Т▌rqtqtqП(НЇОQ@Т∙uqТ√П.НЇОO╪Т─ПAНЇОM╚tТ÷П<{tП-Т═{tНЇОLmТ█ Т▌П2{t{t|tНЇОK/Т─|tП%НЇОHwqТ°ПOТ²НЇОF─ТўП+Т╞П-НЇОDЭТрТсПDНЇОCxТфП.ТгП,НЇОAТТЎТ©П8НЇО@pТ─П*Н)О>ЛН ТXП/Н О=hП4Н)О;ДН П7Н О:`П6НЇО75w qТЫr qП(rqТЗНЇО5╠xqtqxqtqТ┘xqxqТ├xqП)НЇО4-Т▀xq xq xqТ▄ xqrqxqxqrНЇО2╘qТ─xzqxqНЇО/~Т▄rqП5Т█НЇО-ЗТ─ПMН О,vxqТXutТGqutqtqТXxqutТGqutqtqТXНЇО)KwqТЄrqПExqТ╣uqНЇО'гtqxqТ║xqzqtqТ╒xqrqxq xqП'НЇО&CТ─xqНЇО"DrТXНЇОwqТ▐rq Т░П@rqНЇО∙ТґrqП%ТўП$НЇОТ▀П.rqТ▄НЇО█Т─П-xqНЇОbw qП(r qН ОчТXrqН ОZrqxqxqН Ожr qxqН КОRxqxqxqxqН Онyr qyqxqtqtqtqxqtqxqtqxqН ОJr qxqtqxqtqНЇОфТ┤ПEТ┬rqНЇОBТ─П/Ъ0TVk(2І÷2.1OVERVIEW5Scope: 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 called ENV (for environment) which determines these values. A new scope is introduced (inthe kernel) by IN (after LET or l) or by a REC [...] 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[n²1].Constructors: Brackets delimit explicit constructors for group, declaration or binding values. Theyall have the form [x1, x2, ...], and are distinguished by the form of the xi: an expression for a group;n: e for a declaration;n~e or n: e~e for a binding.Recursion: When names are introduced in a constructor in Cedar, this is done recursively: If v is bound to n in a binding constructor, then in expressions in the constructor n has the value v,rather than its value in the enclosing scope. Exception: argument bindings are non-recursive.If n is declared in a declaration constructor, then it may not be used in the constructor, unless there isan ordering of the declarations in the constructor such that a name is used only by later declarations.Exception: declared names may be used in the bodies of l-expressions in the constructor (seeІ÷3.3.4)In the kernel, however, constructors are non-recursive unless preceded by RECDot notation: The form e.n looks up n in some binding associated with e, and does something withthe result. There are three cases:If e is a binding, e.n is just the value paired with n in e.If e is a type, e.n is e.Cluster.n.Otherwise, e.n is (De.n)[e], and e.n[more args] is usually (De.n)[e, more args].In all cases you are supposed to think of n as some property or behavior associated with e; e.ndenotes that property or evokes that behavior.2.1.4 ConveniencesCoercion: Each type cluster contains To and From procs for converting between values of the typeand values of other types (e.g., Float: PROC[INT]_[REAL]; this would be a To proc in REAL and afrom proc in INT). One of these procs is applied automatically if necessary to convert or coerce anargument value to the domain type of a proc; this application is a coercion. Each coercion has anassociated atom called its tag (e.g., $widen for INT_REAL or $output for INT_ROPE); severalcoercions may be composed into a single one if they have the same tag. The tags thus serve toprevent unexpected composition of coercions.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, called the argument of the exception, so that arbitrary information can be passed along withan 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 НЇОf2tН;─НGОqНЇО_шwqТ÷УТ═ПIНЇО^WТ╧Т╨rqП'НЇО\сТ⌠uqТ■r qП>НЇО[OТ─uqtqyq uqП7Н ОYкuqТXxquqxqН ОXGuqxqyqxqtquqtqxqtqtqxqxqxqНЇОUwqТ╘ПIТ╙НЇОS≤Т─xОS}ОS≤qxОS}ОS≤qП1xОS{ОS≤qН ОQ╙ТXН ОP&xqxqН ОN╒xqxqxqxqxqНЇОKwwqТ─ПCr qН ОIСТXxqxqПBxqxqН КОHoП]Н ОFКxqПfН КОEgПgН КОCЦП7yqП$Н КОB_НЇО@шТ─ПHuНЇО=╟wТ▌q xq xqП!xqТ▐НЇО<,Т─Н О:╗ТXxqxqxqxqН О9$xqxqxqxqxqН О7═ xqxqzxqxqxqxqxqzxqxqxqНЇО6ТЇП(xqТ╦xqxНЇО4≤qТ─П'НЇО0≥rТXНЇО-nwqТ xqrq r qТ⌡НЇО+ЙТ║Т╒ xqtqtqzqtqxqtqНЇО*fxqТ²tqТ·П*rqНЇО(БТ²П)Т·rqНЇО'^ ТХrqТИxqtztqxqtztq НЇО%зТЁТЄПDНЇО$VТ─П%НЇО!+wqТ╘rqxq Т╙НЇОїТ║zxqТ╒ПVНЇО# ТіТїП<НЇО÷ТцxquqТдП@НЇОТ▐Т░uqП7НЇО≈Т■rqТ∙ПFНЇОТ─ НЇОХwqТ▓П-Т⌠П,НЇОdТ√П,rqП+Т≈НЇОЮТ©ПZНЇО\Т─tqНЇО 1wqТ▄rqП0tqxq tqТ█ НЇОґТ╞xqrqП<Т╟НЇО )Т─П&yq`TVk(,THE KERNEL LANGUAGEІ÷26checked, the compiler guarantees that the proc value is safe;trusted, the programmer asserts that it is safe (but the compiler makes no checks), and the proc valueis treated as 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 a 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 the procs of the monitor at a time. So that each process can know what to rely on, it isnecessary to establish an invariant for the monitored data which is established whenever a monitorproc returns or waits. A process can wait on a condition variable within a monitor; other processescan then enter the monitor. The waiting process runs again when the condition is notified, or after atimeout.2.1.5 MiscellaneousAllocation: Cedar has standard facilities for allocating new variables of any type (the NEWprimitive); related variables can be allocated in the same zone. Normally, variables are deallocatedautomatically by the garbage collector when they can no longer be referenced; such variables canonly be referred to by REFs. It is also possible to have variables which are deallocated explicitly byFREE, but this is unsafe.Static: An expression whose value is computed without executing the program is called static.Literals are static, as are names bound to literals, and any expression with static operands. Procbodies are never static unless they are inlinePragma: Some language constructs do not affect the meaning of the program (except possible tomake a legal program illegal), but only its time and space costs; these are called pragmas. Examplesare INLINE for proc bodies and PACKED for arrays.2.2 Kernel definitionThis section gives the syntax and semantics of the Cedar kernel language. Motivation, and anexplanation of the relation between the kernel and the current Cedar language, can be found inІІ÷2.3-2.7. The kernel is subdivided into A rather austere core; everything can be desugared into this, but it isn't very readable.A set of conveniences; with these, readable programs can be written.Imperative constructs: statements and loops.Exception handling.The format of this section interleaves grammar rules which give the syntax of the language with textwhich gives the meaning. The meaning of the core is given in English. For other parts of thekernel, it is given by desugaring rules which show how to rewrite each construct in terms of others;if rewriting is done repeatedly, the result is a core program, which may invoke some primitives. Themeaning of these is also given in English. There is also some English explanation of the desugaring,but this is only a commentary and does not have the force of law.See І÷3.1 for the notation used in the grammar and desugaring.ЪН⌡Оf2tТGУНGNНЇqН О_шrqТXП5Н О^WrqП_Н КО\сН О[OrqП=НЇОYкТ┴П1Т┼П/НЇОXGТ─П-НЇОUwqТ▄П$Т█rqНЇОS≤ Т╩Т╪П9НЇОRТ÷П.Т═rqНЇОP░Т╟Т╠ПLНЇОOТ√Т≈rqП?НЇОM┬Т≤П!rqrqТ≥ НЇОLТ└ПNrqНЇОJ─rqНЇОF│rТX НЇОCVw qТЧТЪП/tНЇОAрq Т²П0rqТ·НЇО@NТїrqП:НЇО>йТ░tqПIТ▒НЇО=FtqТ─НЇО:wqТнПDТо rqНЇО8≈Т╦Т╧ПNНЇО7Т─П(НЇО3ХwqТґП3ТўП#НЇО2dТ┴ПOrqТ┼НЇО0ЮТ─tqtqНЇО, wТXНЇО(БqТпП;ТяНЇО'^ Т╟П9Т╠НЇО%з Т─НґО#┌rqПDНґО!*rqП/НґОрr qП"НґОzrq НЇОOТ│Т┌ПRНЇОкТцП"ТдП5НЇОGТ┬Т┴ПZНЇОцТ┐П.Т└П4НЇО?Т┤ПJТ┬НЇО╩Т─П>НЇО░П>Ъ*TVk(VІ÷2.2.1THE CORE72.2.1 The coreIn the core, there is syntax only for names, literals, application, l-expressions, a basic and arecursive binding construction, and syntactic type; everything else is done with primitives. We neverwrite anything in the core, however, except to show the desugaring of a kernel construct. Thus thereader need not struggle with programs in the ugly core syntax.SyntaxSyntactic typeMeaningexpression ::=n |DnENV[$n].valliteral |Dliterale1 Z e2 |(De1.RANGE)[e2]-- Standard application. |l d1=> d2 IN e |d1_d2-- Standard proc constructor. |L d1=> d2 IN e |d1_d2-- Unchecked standard proc constructor. |[(n~e), ...][(n: De), ...]-- Vanilla binding constructor. |FIX d ~ e |d-- Recursive binding constructor. |D e TYPE-- Syntactic type. type ::= eDe --gTYPE---- A type is syntactically just an expression.decl ::= eDe --gDECL---- A decl is syntactically just an expression.name ::= letter (letter | digit)...(DENV).n-- Appears as an e or in a pattern.literal ::= $ n |ATOM-- ATOM literal. |primitiveDprimitiveprimitive ::= ARROW |[d: DECL, p: (d_DECL)]_[a: --arrow--TYPE] DOMAIN | RANGE |*[a: --arrow--TYPE]_[t: TYPE]MKPAIR | [t1:: TYPE, first: t1, t2:: TYPE, rest: t2]_[v: t1Xt2]GROUP |[t1: TYPE]_[t: TYPE] --tgTYPEMKCROSS | [g: GROUP[TYPE]]_[c: --cross--TYPE] CDOTG |*[t: --cross--TYPE]_[g: GROUP[TYPE]]MKBINDD |[d: DECL, v: d.T]_[b: d] BDOTD | BDOTV |[b: BINDING]_[d: DECL] | [d:: DECL, b: d]_[v: d.T ]MKBINDP |[p: PATTERN, t:: TYPE, v: t]_[b: MKDECL[p, t]] --=MKBINDD[d~MKDECL[p, t], v~v]LOOKUP | [d:: DECL, b: d, n: ATOM]_[v: DTOB[d].n]THEN | [d1:: DECL, b1: d1, d2:: DECL, b2: d2]_[v: d1 THEND d2 ]ENV | *BINDINGMKDECL |*[p: PATTERN, t: TYPE]_[d: DECL] DDOTP |*[d: DECL]_[p: PATTERN] DDOTT |*[d: DECL]_[t: TYPE]DTOB | *[d: DECL]_[b: BINDING]--=MKBINDP[p~d.P, v~d.T.G] ]BTOD | *[b: BINDING]_[d: DECL]--=MKDECL[p~b.D.P, t~MKCROSS[b.V] ]THEND | [d1: DECL, d2: DECL]_[v: DECL] --=BTOD[DTOB[d1] THEN DTOB[d2]] BOOL | ATOM | TYPETRUE | FALSE | BOOL TYPE | DECL | BINDING |TYPE-- DECLgTYPE, BINDINGgTYPEPATTERN |TYPE--=GROUP[ATOM]ANYTYPE -- TgANY for any type TIn the kernel we dress up the primitives as follows: A primitive denoted xDOTy is in the cluster of the type of its argument under the name y. A parameter to a primitive declared with :: is the type of some other argument; theargument for this parameter may be omitted in an application of the primitive.ЪНЇОf2tН;ИТGУНGОqНЇО_шrТXНЇО\╟qТшПByqТэНЇО[,Т└П=Т┘НЇОY╗Т⌠П.Т■П/НЇОX$Т─П9НЇОTЫrНЮТXН*НЇОQнwtwН ОPJqwНЮzqН*uqwqН ОNфwНЮzqН ОMBОL╣}ОMBqzqОL╣}ОMBqwНЮqzqОL╣}ОMBquqОL╣}ОMBqН*wН ОKTyqОJг}ОKTqОJг}ОKTquqwНЮqОJг}ОKTzqОJг}Н*ОKTqwН ОIfyqОHы}ОIfqОHы}ОIfquqwНЮqОHы}ОIfzqОHы}Н*ОIfqП(wН ОGxqwqwqНЮwqzqwqН*wН ОEТuqwНЮqН*П"wН ОDpzqНЮtН*qНЇОBЛwtwqНЮzqztqН*П.НЇОAhwtwqНЮzqzuqН*П.НЇО>=wtwqН О<╧wqwqwНЮqzuqН*П#НЇО;5w qН О9╠wНЮtН*qtq wН О8-qНЮzqНЇО6╘wqН О5%uqwНЮqxquqxqwzuqzqxq tqН О3║uqwquqwНЮqxq tqzqxqtqН О2uqwqНЮxО1░}О2qtqxqwО1░}О2qxО1░}О2qtqxqwО1░}О2qzqxqwО1░}О2zwО1░}О2qН О0/uqwНЮqxО/╒}О0/qtqzqxqtqН*xztН О.AuqwqНЮxquqtqzqxq tqН О,ҐuqwНЮqxq tqzqxquqtqН О+9uqwНЮqxquqxqwquqzqxqwqН О)╣uqwquqwНЮqxquqzqxquqwqxquqxqwqzqxqwquqН О(1uqwНЮqxquqxqtqxqwqzqxquqwqwquqxquqwqwqxqxqН О&ґuqwqНЮxquqxqwqxqtqzqxquqwqwqН О%)uqwqНЮxО$°}О%)quqxО$°}О%)qwО$°}О%)qxО$°}О%)quqxО$°}О%)qwО$°}О%)qzqxqwО$°}О%)wuqwО$°}О%)qН О#;uqwqНЮuН О!ЇqwНЮqxquqxqtqzqxquqН О 3uqwНЮqxquqzqxquqН О╞uqwНЮqxquqzqxqtqН О+uqwqНЮqxquqzqxquqН*uqxqxquqxqxuquqН ОїuqwqНЮqxquqzqxquqН*uqxqxquqxquqxquqН О#uqwqНЮxО√}О#quqxО√}О#quqzqxquququqxО√}О#qwtquqxО√}О#qН О5tqwqtqwqНЮtН О╠qwqtqwqНЮtqН О-tqwuqwquТGwНЮtН*qТXuztquztН О╘uqwНЮtН*quqtqН О%tНЮtqН*xztq xНЇОЗqТ─П3НґО╒xuxqП>xqНґО JТжП"ТвП0НґОфТ─ПF fTVk(KERNEL DEFINITIONІ÷2.28A name not in a literal (or pattern, in the kernel) denotes the value to which it is bound in thecurrent environment ENV (A below). An ATOM literal is a value which stands for a name in theprimitives which deal with declarations and bindings. A literal denotes a value according to a rule which depends on its syntax. The core has onlynumeric and ATOM literals, and the primitives enumerated above.An expression denotes a value according to a rule which depends on its syntax. If the expression isa name or literal, the value is the value of the name or literal. The remaining cases are discussed inthe following sub-sections. Most of these cases define the value of the expression in terms of thevalue of its sub-expressions. The sub-expressions may be evaluated in any order. A. The current environment ENVThe current environment ENV is a binding. The value of the expression n is ENV.n. ENV for a sub-expression is the same as ENV for its containing expression, except that:For the b of a closure being applied, ENV is computed according to B below.For the e of a FIX, ENV is computed according to E below.Thus applying a closure and evaluating a FIX are the only ways to change ENV. B. ApplicationThe value of a standard application is obtained by evaluating e1 and e2 to obtain v1 and v2, andapplying v1 to v2. There are two cases for application:v1 is a primitive. The value of the application is a function of v2 given in the definition ofthe primitive. v1 is a closure c (C below), with domain declaration d, body b and environment E. Thevalue of the application is the value of the expression b in the environment MKBINDD[d, v2]THEN E (D below). Note that if the closure was made with L, the body must be type-checked when it is applied; a closure made with l was type-checked when it was made (Cbelow).An application type-checks if De2 implies De1.DOMAIN (G below).C. LambdaThe value of a l-expression is a closure, which has three parts:A domain declaration d, equal to the value of d1.A body b, which is the expression e (not the value of e).An environment E, equal to the current environment ENV.A l-expression type-checks if d1 evaluates to a declaration d.For any x of type d.T, De implies d2.T in the environment MKBINDD[d, x] THEN E.A L-expression type-checks if d1 evaluates to a declaration; type-checking of the body is deferreduntil the closure is applied.Н⌡Оf2tТGУ НF{НЇqНЇО_шТ╘ПSТ╙НЇО^WТ╡uqtqП&ТЁНЇО\с Т─П,НЇОY╗ТлП'ТмП4НЇОX$Т─tqП/НЇОTЫТ█П%Т▌П<НЇОSuТ┬Т┴П]НЇОQЯТіП=ТїП"НЇОPmТ─ПLНЇОLnrТX|НЇОICqТ²uqП+xqТ·uqxquq НЇОG© Т─uqП,НґОEgxquqП"НґОCxququqП"НЇО@ЇП)uquqНЇО<╦rТXНЇО9█qТ╟П;xО9}О9█qТ╠xО9}О9█q xО9}О9█qxО9}О9█qНЇО7÷rqТ─xО7}О7÷qxО7}О7÷qП&НґО5GxО4╨}О5GqТ≈Т≤П%xО4╨}О5GqНґО3YТ─НґО1xО0t}О1qТІ xq ТЇxqxqxqНґО/Т≥П3xquqxqТ xО.├}О/qНґО-%uqТ╩xqТ╪yqНґО+║Т░П)yqП"Т▒НґО*НЇО'еТ─zxО'8}О'еqzxО'8}О'еquq НЇО#фrТXНЇО ⌡qТ─yqrqНґОCxqxОІ}ОCqНґОКxqxqrq xqНґО⌠xqП#tqНЇОhyqНґОxО┐}ОqxqНґО╦xqxquqzxqxО+}О╦ququqxqxquqxqНЇО█Т╒yqxО}О█qТёП5НЇО÷Т─Ъ bTVk(╩І÷2.2.1THE CORE9D. Pairs, groups and cross typesA pair is the basic structuring mechanism. MKPAIR[x, y] yields the pair . Bigger structures aremade, as in Lisp, by making pairs of pairs. When we are interested in the leaves of such a structure,we call it a group and call the leaves its elements. A group has type GROUP[T] if all its elementshave type T or are NIL. A flat group is a pair in which first is not a group, and rest is a flat group orNIL. The type of a pair is a cross type: MKPAIR[x, y] has type TXU iff x has type T and y has type U.Cross types are made with MKCROSS, which turns a GROUP[TYPE] into a cross type in the obviousway:MKCROSS[NIL]=???MKCROSS[T]=T if T is a type.MKCROSS[ MKPAIR[x, y] ]=MKCROSS[x]XMKCROSS[y]Note that MKCROSS of a flat group is flat. CDOTG goes the other way, turning a cross type into aGROUP[TYPE] in which no element is a cross type. Thus MKCROSS is the inverse of CDOTG, but notnecessarily the other way around.E. BindingsA binding is either NIL, or an tuple, or a tuple. The primitiveMKBINDD constructs a binding from a declaration d and a matching value v, i.e. (as the type ofMKBINDD indicates), one with the type d.T. The resulting binding has type d, and consists of thenames from d paired with the corresponding values from v. Example:MKBINDD[ [x: INT, b: BOOL], [3, TRUE] ] = [x~3, b~TRUE]= < <$x, 3>, < <$b, TRUE>, NIL > >In this example, d.T is INTXBOOL. The declaration and group in this example is written using the syntax of І 2.2.2; in the core they would beMKDECL[p~[$x, $b], t~MKCROSS[[INT, BOOL]] ] and MKPAIR[first~3, rest~MKPAIR[first~TRUE, rest~NIL]], where we have writtenthe arguments of these primitives in the kernel syntax.The primitives BTOD and BTOV return the arguments of the MKBINDD primitive that made thebinding. MKBINDP is redundant; it is like MKBINDD, but takes a type instead of a declaration, andhence accepts any v with the right structure.LOOKUP returns the value of the name n in the binding. THEN combines two bindings, givingpriority to the first one in case of duplicate names. It works only for flat bindings, in which the firstelement of each tuple is an tuple, and the second element isanother tuple or NIL. The value of b1 THEN b2 is another flat binding, obtainedby first replacing any tuple <, b> in b2 where a is equal to an atom in b1 by b, and then usingthis binding to replace the final NIL in b1. The binding constructor [(n~e), ...] has the value MKBINDP[p~[n, ...], v~[e, ...] ]. FIX makes a recursive binding: the value of FIX d1~e is MKBINDD[d, v], where d is the value of d1 inENV and v is the value of e in the environment (LET FIX d~e IN d~e) THEN ENV. Of course in generalthis computation may not terminate; normally the names in d occur in e only with l-expressions,and in this case it does terminate. Is this really right? The FIX typechecks if De in the latterenvironment implies DTOT[d]. ЪНЇОf2tН;ИТGУНGОqНЇО_шrТXНЇО\╟qТ≈П*uqxqxqТ≤xqxqНЇО[,Т│ПNТ┌НЇОY╗Т╚ Т╛rqrquqxqНЇОX$Т│xqtqrq Т┌xqxqНЇОV═tqТ─НЇОSuТ÷П!uqxqxq xzxqxq xqxqТ═xqНЇОQЯТ║uquqtqТ╒НЇОPmНґОNuqtqНґОKҐuqxqxqТ─xq НґОIeuquqxqxquqxqzuqxqНЇОG Т╒uquqП$ТёНЇОE┴uqtqТ√П*Т≈uquqНЇОD Т─НЇО@rТXНЇО<шqТўТ╞ tqПIНЇО;WuqТЎП(Т©xqxqНЇО9сuqТЇxquqП!xqТ╦НЇО8OТ─xqП+xq НyО6кuqТXxqtqxqtqtqxqxqtqН)О5Gxq xqtqtqНЇО3цТ─xuqtztqНЇО1╡tТыП)ТзП?НЇО0t~t{t{tТ≤{t{t~ttt~t{t{t~t{t{ttТ≥НЇО/6Т─П4НЇО,qТжuququq Тв НЇО*┤ТґuquqТўНЇО)Т─xqНЇО%ьuqТсxqТт uqНЇО$TТ┌Т┐ПHНЇО"пТ©ТюПDНЇО!LТ≤Т≥ tqxО ©}О!LquqxО ©}О!LqП"НЇО^Т▀xqxqxqxОя}О^qxqТ▄xОя}О^qxqНЇОpТ─tqxОЦ}ОpxqНЇОEН#О ЧyН°ОExqxqНшО ЧyНTОEuqxqxqxqxq НЇОuqТ∙П)uqxО█}ОqxquvxqxqxqТ√ xО█}ОqНЇО,uqТ┤xqТ┬xquvuqxqxquqxqxququqНЇО╗Т╒Тёxq xq yqНЇО$ТпТяrН"гОЛЧ3Н.ЗО$quqzxq НЇО═ Т─uqxq╦TVk(│KERNEL DEFINITIONІ÷2.210F. DeclarationsA declaration is either NIL, or an tuple, or a tuple. Theprimitive MKDECL constructs a decl from a pattern p and a value t of type GROUP[TYPE]. A pattern isa GROUP[ATOM], i.e., either NIL, or an atom, or a pair of patterns; the ATOM elements must all bedifferent. An application of MKDECL typechecks if t matches p, i.e., ifboth p and t are NIL, orp is an atom and t has type TYPE, orp is a pair [p1, p2] and t is a cross type t1Xt2 and p1 matches t1 and p2 matches t2.The resulting declaration consists of the names from p paired with matching type values from t. The primitives DDOTP and DDOTT return the arguments of the MKDECL primitive that made thedeclaration. ThusDDOTT[NIL]=???; DDOTT[<$n, T>]=T; DDOTT[]=DDOTT[d1]XDDOTT[d2]DTOB is redundant; it converts a declaration to a binding in which each name has the correspondingtype as its value. Thus DTOB[[x: INT, y: REAL]]=[x~INT, y~REAL]. The inverse is BTOD, alsoredundant; it is defined only if all the values in the binding are types. THEND combines twodeclarations just as THEN combines two bindings: D(b1 THEN b2)=Db1 THEND Db2G. Types and type-checkingA type is a value consisting of a pair:the predicate, a function from values to BOOL.the cluster, a binding.A value v has type T if T's predicate applied to v is TRUE. T implies U iff (Ax) T.Predicate[x]gU.Predicate[x].Typechecking consists of ensuring that the argument of an application has the type specified by thedomain of the proc (B above). The body of a l-expression can then be type-checked (or theimplementation of a primitive constructed) independently, assuming that the parameter satisfies thedomain predicate. Symmetrically, the result of an application can be assumed to have the typespecified by the range of the proc.To complete the induction, it is also necessary to check that the value of the body of a l-expressionhas the range type (C above).The primitive types in the kernel are:BOOL, with two values TRUE and FALSE.ATOM, with values denoted by literals of the form$n.TYPE, a predicate satisfied by any type value.ANY, a precidate satisfied by any value.DECL, the type of a declaration (F above).BINDING, the type of any binding.Н⌡Оf2tТGУ НF{НЇqНЇО_шrТXНЇО\╟qТ╩tqТ╪П2НЇО[,Т┌uqП"xqТ┐xquqtqНЇОY╗Т⌡uqtqtqП)tq Т°НЇОX$ Т─uqxqxq НґОUлxqxqtqНґОStxqxq tqНґОQxqxОP▐}ОQqxОP▐}ОQqxqxОP▐}ОQzxОP▐}ОQqxОP▐}ОQqxОP▐}ОQqxОP▐}ОQqxОP▐}ОQqНЇОNдП5xqП'xqНЇОLlТбuquqТцuqНЇОJХТ─НґОH░uqtqНґОF8uqxqxqxНґОCЮuqxОCS}ОCЮqxОCS}ОCЮquqxОCS}ОCЮqzuqxОCS}ОCЮqНЇО@╣uqТ┌П(Т┐П6НЇО?1ТФuqxqtqxqtqxqtqxqtqТГuqНЇО=ґ ТжП4ТвuqНЇО<)Т─uqzqxО;°}О<)quqxО;°}О<)qzxО;°}О<)quqzxО;°}НЇО8*rТXНЇО4ЪqТ─П&НґО2їrqtqНґО0OrqНЇО-ВxqrqxqxqxqtqНЇО*лxqrxqzxqxqxqxqzxqxqxqНЇО'║Т┼ПWНЇО&ТнП&yqП,НЇО$≥ Т▒ПQТ▓НЇО#ТдПRТеНЇО!▒Т─НЇОfТ┌Т┐ПJyq НЇОБТ─НЇОЇП&НґО_tqtqtqНґОtqП.xqНґО╞tqП*НґОWtqП%НґО ЪuqП&НґОїuqЪпTVk(АІ÷2.2.1THE CORE11Arrow types, the types of procs (C above). An arrow type has a domain type and a rangetype.Cross types, the types of pairs (D above). GROUP[T], the type of any pair in which all the elements have type T.Declarations, the types of bindings (E and F above). There are no non-trivial implications among any of these types, except as follows:DECLgTYPE; BINDINGgTYPE; GROUP[T]gTYPE.ANYgT for any type T.T1XT2gU1XU2 iff T1gU1 and T2gU2.GROUP[T]gGROUP[U] iff TgU.T1_T2gU1_U2 iff U1gT1 and (Ax: U1) (l T1 IN T2)[x]g(l U1 IN U2)[x]. Note thereversal of the domains.d1gd2 for declarations iff d1.P=d2.P and DTOB[d1].ngDTOB[d2].n for each n in d1.P.ЪНЇОf2tН;ИТGУНG?qНґО_шТ·П:rq Т÷rНґО^WqНґО[ЪТ─П&НґОYїuqxqПDECL IN d2] l ( | e1) ( | => e2) IN e3 |-- The domain defaults to [], the range to x: De3 |LET e1 IN e2 |( l De1 IN e2 ) Z e1.V -- e1 a binding |LET b, ... IN e |LET [b, ...] IN e|IF e1 THEN e2 ELSE e3 |( IFPROC[De2, e1, l IN e2, l IN e3] ) [] |e . n |IF DegBINDING THEN LOOKUP Z [De, $n] ELSE IF DegTYPE THEN LOOKUP Z [De.cluster, $n] ELSE ( LOOKUPC Z [De.cluster, $n] ) Z [e] |e1 [ b, ... ] | e1 [ e2, ... ] |e1 . APPLY Z [b, ...] | e1 . APPLY Z MKBINDD[De1.DOMAIN, [e2, ...] |e1 infixOp e2 |e1 . infixOp[e2] |e1 AND e2 | e1 OR e2 |IF e1 THEN e2 ELSE FALSE | IF e1 THEN TRUE ELSE e2 |[ ] | [ e1 ( | e2, !.. )] |NIL | MKPAIR[e1, [ ( | e2, !.. ) ]-- Group constructor. |PATT p |-- Pattern constructor; see the rule for p below. |[ b, ... ] |b PLUS ... PLUS NIL |REC [ (p : t ~ e), ... ] |FIX [p, ...] : MKCROSS[[t, ...]]~[e, ...] |[ d, ... ] |d PLUS ... PLUS NIL |XX |xxxxxx | --Also recursive d maps into this?statements | simpleLoop | -- See І÷2.2.3but-- See І÷2.2.4.infixOp ::=XMKCROSSPLUSTHENliteral ::= coreLiteral |digit digit ... |INT-- Numeric literal, giving the decimal representation.declaration ::=-- A d is not an e; a d must be before ~ or after LET or DECL.p: t |MKDECL[ PATT p, t] |[(p: t), ... ][p, ...]: MKCROSS[[t , ...]]-- to separate names and typesbinding ::=-- Only the [...] form is an e; a b must be written after LET. |p ~ e |MKBINDP[PATT p, e] |d ~ e |MKBINDD[d, e] pattern ::= -- Note: a pattern is not an e; it can appear only before ~ or :, or after PATT in the kernel.n |-- PATT n=$n [p1, ...] -- PATT [p1, ...]=[PATT p1, ...]primitive ::= corePrimitive |LOOKUP | LOOKUPC |-- Fill in typesPLUS |IFPROC |The precedence of operators in e is: (highest) [], Z, infixOps (all the same), BUT, IN (lowest). All areleft associative.2.2.2.1 Expression syntaxMost of this is straightforward sugar. LET adds the binding e1 to ENV in evaluating e2. The separatecase for b, ... simply allows the [] which normally enclose a binding constructor to be omitted in thiscase; see І÷2.2.2.2. IF wraps e2 and e3 in l's so that they don't get evaluated; the IFPROC primitivechooses the one to evaluate and applies it.The dot notation has three cases. ЪН⌡Оf2tТGУ НF{НЇqНЇО_шrТXНЇО\╟wtwqwН О[,qОZ÷}О[,qzqОZ÷}О[,qwН*uqzqОZ÷}О[,qyqОZ÷}О[,ququqОZ÷}О[,qН ОY>yqwqОX╠}ОY>wqОX╠}ОY>wquqОX╠}ОY>qwН*qП+xqzqОX╠}ОY>qwН ОWPuqОVц}ОWPquqОVц}ОWPqwН*qН*ОWЧyН*│ОWPyqzwОVц}ОWPqtqwОVц}ОWPqН1ЛОWЧyН2eОWPzqwОVц}ОWPquqОVц}ОWPq wН ОUbuqwquqwН*uqwtqwquqwН2MwН ОSчtqОSQ}ОSчqtqОSQ}ОSчqtqОSQ}ОSчqwН*qН*ОSіЧyН*│ОSчuqzwОSQ}ОSчqwОSQ}ОSчqyquqwОSQ}ОSчqyquqwОSQ}ОSчqН=іОSіЧyН>ОSчwН ОQПqwН*tqzqzuqtquqzqzwqwqН*ОPltТGzqztqТXtquqzqzwqxqwqН*ОNХtТGqТXН-qОN╟ЧyН-ЙОNХuqzqzwqxqwqН>ОN╟ЧyН>yОNХzqwqwН ОMdqОLв}ОMdqwqwqОLв}ОMdqОLв}ОMdqwqwН*wОLв}ОMdquqzqwqwqwqwОLв}ОMdquqzquqzwОLв}ОMdquqwОLв}ОMdqwqwН ОKvqОJИ}ОKvq ОJИ}ОKvqwН*wОJИ}ОKvqwН,/ОK>ЧzН0╘ОKvqwОJИ}ОKvqwН ОI┬qОHШ}ОI┬qtqОHШ}ОI┬qwqОHШ}ОI┬qtqОHШ}ОI┬qwН*tqОHШ}ОI┬qtqОHШ}ОI┬qtТGqТXwqtqОHШ}ОI┬qtqtqtТGqОHШ}ОI┬qТXwН ОG qwqОG }ОG qwqwqОG }ОG qwqwqwН*tqwquqwОG }ОG qwqwqwОG }ОG qwqwqН:▓wН ОE╛uqwН*qП2wН ОD(q wН*wquqwquqtqwН ОBєuТGqТXwqwqwqwН*uqwquqwqwqwН ОA q wН*wquqwquqtqwН О?°zqwН*qwqП#Н О> wqwqН* Н О<■Н*НЇО;w Н О9▄zН*uН О8Н О6└НЇО5w qwН О3|qwqwН*tН2MqП6НЇО1Ьwt wН*qП2uquqН О0twН*uquqwqwqwН О.ПqwqwqwqН*wqwquqwqwqН:▓НЇО-lwtwН*qwqП*uqwН О+ХqwН*uquqwqwqwН О*dqwН*uqwН/▌О*,Ч╟Н0>О*dqwqНЇО(ЮwqwqН*rqП(Н*О'\uqН О%ьwН*quqwqwqН О$TО#г}О$TqwqН*uqwО#г}О$TqwquqwО#г}О$TwqwqНЇО"fwqwqwН О БuqwquqwН*qН О^uqwН ОзuqwНЇО╞qТ┼П+Т▀zququqНЇО+Т─НЇО,rТXНЇОqТ⌠П#uqxОt}Оquq Т■xОt}Оq НЇОТ┌xqП3Т┐П*НЇО▐Т°tqxО}О▐qxО}О▐qyqП)uqТ² НЇО║Т─П$НЇО vП"ЪДTVk(-І÷2.2.2CONVENIENCES13For a binding it just looks up n in the binding. For a type it looks up n in the type's cluster.For anything else, it looks up n in the cluster of De and applies the result to e. The specialLOOPUPC primitive does something special if it finds a proc which takes more than oneargument: it splits the proc into one which takes the first argument and returns a proctaking the remaining arguments. This ensures that if De.n is such a proc P, the expressione.n[a, b] will desugar into something equivalent to P[e, a, b]. The usual syntax for application is a proc e1 followed by an explicit binding constructor. The kindof application may depend on the type of e1, via the APPLY element of its type; for a proc appliedby the standard apply operator Z, APPLY is the identity. If e1 is followed by an group rather than abinding constructor, the argument is obtained by binding the group to the declaration which is e1'sdomain.Infix operators desugar straightforwardly into application; note that the choice of proc is determinedby the type of the first operand only. AND and OR are not ordinary infix operators, since theyevaluate no more than necessary; this is expressed by the desugaring into IF.The remaining expression syntax is various constructors, described in the next section, andimperative and exception features described in later sections.2.2.2.2 Group, binding and declaration constructorsA bracketted sequence of expressions (e.g., [1, 2, 3]) denotes a flat group with its elements in thesame order (e.g., MKPAIR[1, MKPAIR[2, MKPAIR[3, NIL]]]. Thus a group constructor is just like theLIST function in Lisp. A pattern is a similar construct, except that it contains names which standfor the corresponding ATOM literals; PATT yields the group obtained by replacing each name n bythe literal $n. After desugaring a pattern always appears after PATT and hence is always desugaredinto an atom or a GROUP[ATOM].Brackets are also used to delimit binding and declaration constructors. They are distinguished fromeach other, and from group constructors, by the presence of ~ in each element of a bindingconstructor, and : in each element of a declaration constructor. The elements of a binding ordeclaration constructor are sugar for applications of the MKDECL, MKBINDP and MKBINDD primitives.The constructor itself strings the resulting declarations into a big one using the PLUS operator,which is just like THEN except that it does not allow duplicate atoms; the motivation for this is toallow the names and corresponding types or values to be written together, instead of factored as theprimitives require. As a result, values made from constructors are always flat.Note that these constructors do not nest, except that a d can be [(p: t), ... ]. This is intended for thed~e form of binding; e.g., if DivRem returns two INTs, you can write [d: INT, r, INT]~DivRem[...]instead of [d, r]: INTXINT~DivRem[...].The REC binding constructor is sugar for FIX which exactly parallels the non-recursive one.2.2.3 ImperativesThese constructs are generally used together with non-functional procs.statements ::= { e; ... }IF (ISVOID[e]) AND ... THEN [] ELSE ERROR -- Ordering by non-prompt evaluation.simpleLoop ::= SIMPLELOOP statementsLET REC [loop(~(l IN { statements; loop([] } ) ] IN loop([]-- Only an exception (such as EXIT) will terminate the loop.НЇОf2tН8░НG?qНґО_шТ─УxqНґО]┐xqНґО[+Т▀xqzxqxqТ▄НґОYїuqТ╨ПJТ╩НґОX#Т╪П"ТҐП,НґОV÷Т П/zxqТ⌡xqНґОUxqxТ─qП,xqxqНЇОQПТ√П(xОQc}ОQПqТ≈П6НЇОPТ⌠П&Т■xОOu}ОPq uqП(НЇОNТ▐zquqТ░ xОM┤}ОNqП&НЇОL&Т▒ПBТ▓xОK≥}ОL&qНЇОJ8НЇОG Т│ПaНЇОE┴Т╪ТҐtqtqП-НЇОDТ─ПBtqНЇО@зТПBТНЇО?V Т─П4НЇО;WrТXП,НЇО8,qТ╒П1ТёП2НЇО6╗Тю uqТаuquqtqП.НЇО5$Т═ПCТ║НЇО3═Т÷tq uqП'Т═ xqНЇО2Т² xqП2uqТ·НЇО0≤Т─ uqtqНЇО-mТ▓ПHТ⌠НЇО+ИТяП7ТрНЇО*eТоП8ТпНЇО(А Т⌡Т°uququqНЇО']ТиП6Тйuq НЇО%ыТ°Т²uqПMНЇО$UТ┘ Т├ПQНЇО"я Т─ПEНЇОіТ┬П>wxqxwqwqТ┴НЇО"xqxqТЇxqtqxqТ╦tqxqtqxqНЇО·Т─xqxqtztqxqНЇОsuqП"uqП/НЇОtrТXНЇОIqТ─ПBНЇОw qТXwqwqН*tqwuqwqwqtqwqtqtqtqН*О П%НЇОw qu q Н*uquqzqН3}ОчЧyН3ЖОyquqw qzqНDOОчЧyНDхОuqzqН*О ▓tq ,TVk(ЭKERNEL DEFINITIONІ÷2.214Each e in the statements must evaluate to VOID; this is to catch mistakes like writing x+1 as astatement. The definition of AND ensures that the e's are evaluated left-to-right.The simpleLoop is the standard way to express a loop in terms of recursion. You are supposed touse an exception to get out of this loop; Cedar provides a number of convenient ways to do this,such as EXIT and RETURN.2.2.4 ExceptionsAn exception is treated as a special value returned from an application. The exception valuecontains an exception code and an args value which may be of any type. When an application seesan exception value, it immediately abandons the application and returns the exception value; thusapplication is strict. There has to be some way to stop this, or the first exception would be the valueof the program. The HIDE primitive takes any value and returns a variant record of type HEX. Itturns:a normal value into the normal variant, with the value in its v field;an exception into the exception variant, with the code in its code field and the arguments inits args field.UNHIDE takes a HEX value and returns the original unhidden value.An exception code has the type EXCEPTION[T], where T is a declaration which is the type of theargs; it is the domain of the exception, and (DEXCEPTION[T]).DOMAIN=T. An exception value isconstructed by the primitiveRAISE: [T:: TYPE, code: EXCEPTION[T], args: T]Thus the args always has the type demanded by the code.This is dressed up with the following syntax. but ::= e BUT { butChoice; ... }LET v(~HIDE[e] IN ( IF ISTYPE[v(, HEX.normal] THEN UNHIDE[v(] ELSE IF ISTYPE[v(, HEX.exception] THEN LET h(~NARROW[v(, HEX.exception ] IN LET selector(~h(.code IN butChoice ELSE ... ELSE UNHIDE[v(] ELSE ERROR )butChoice ::= e1 => e2 |IF selector(=e1 THEN LET MKBINDD[De1.DOMAIN, h(.args] IN e2 |e1 , e1, !.. => e2 |IF (selector(=e1) OR ... THEN e2 |ANY => e2 IF TRUE THEN e2A BUT expression evaluates e. If it is a normal value, that is the value of the BUT. If it is anexception, each butChoice in turn gets a look at it. If one of them likes it, then it supplies the valueof the BUT; otherwise the exception is the value.The e1 in a butChoice must evaluate to an exception code. If there is just one, and it matches codein the exception, then args in the exception is bound to the domain of the code, and e2 is evaluatedin that environment. If there is more than one, then e2 is just evaluated in the current environment.An ANY butChoice matches any exception, but of course doesn't bind the arguments.ЪН⌡Оf2tТGУ НF{НЇqНЇО_шТ╦xqП$uqП(Т╧xqНЇО^W Т─tqxqНЇО[,Т≥П,Т П0НЇОY╗Т°Т²ПPНЇОX$Т─tqtqНЇОT%rТX НЇОPЗqТэТщПMНЇОOvТ■Т∙rqxqП9НЇОMРТ÷ПIТ═НЇОLn Т─rq Т│ПGНЇОJЙТ╠uqП@uqНЇОIfНґОGТ─xqxqНґОDІТ▓xq Т⌠xqНґОC2Т─xqНЇО@зuquqП/НЇО>┌Т╞Т╟uqxqxqП*НЇО<ЧТд ТеrqzuqxquqxqНЇО;z Т─Н О9ЖuqТXxqtqxquqxqxqxqНЇО8rТ─xqП%xqНЇО5GП.НЇО2wТXquq wqН*uqzquqwquqН4╟О1ДЧyН*О0≤tqtqzquqtquqzqН*О/tТG qzqТXuqtН*О-░quqzqtqzququТGН*О,qТXzqzquqwН:оО+тЧЗН@иО,qtqwqtquqzqН*О*┬qtqtqН2⌡О*PЧyНЇО)wqО(w}О)qО(w}О)qwН*tqzqwО(w}О)qtququqzqО(w}О)quqzquqwО(w}О)qwН О'qО&┴}О'qО&┴}О'qwqО&┴}О'qwН*tqwqzqwО&┴}О'wqtqwqtqwО&┴}О'qwН О%(tТGqТXО$⌡}О%(qН*tqtqtqwО$⌡}НЇО!ЩqТеuqxqП4uqНЇО y Т┐ПHТ└НЇОУТ─uqП'НЇОйТ▓xО=}ОйqПDТ⌠xНЇОэqТ┴xqП9Т┼xОO}ОэqНЇОНТ┤П#Т┬xОa}ОНqП.НЇОТ─tqПKЪ TVk(@І÷2.3DOING COMPUTATIONS152.3 Doing computationsThis section describes the basic mechanisms for doing computations, and the kinds of values whichcan be manipulated by Cedar programs.2.3.1 ApplicationThe basic mechanism for computing in Cedar is applying a proc to argument values. A proc is amapping from argument values and the state of the computation, to result values, and a new state of the computation.The state is the values of all the variables.A proc is implemented in one of two ways:By a primitive supplied as part of the language (whose inner workings are not open toinspection).By a closure, which is the value of a l-expression whose body in turn consists of anexpression, which may contain further applications of procs to arguments, e.g., l [x: INT] INx+3. When a closure is applied, the parameters declared after the l are bound to thearguments, and then the body after IN is evaluated in the new environment thus obtained.In Cedar, each parameter value thus obtained is used to initialize a variable, which is the objectnamed by the parameter in the body. Thus the body can assign to the parameters. Use of thisfeature is not recommended.Note that when a l-expression is evaluated to obtain a closure its body is not evaluated, but issaved in the closure, to be evaluated when the closure is applied. Some constructs (IF, SELECT, AND,OR) are defined (see І÷2.2.2 and І÷3.8) by wrapping l-expressions around some arguments, and thenapplying them only when certain conditions hold; e.g., IF b THEN f÷[x] ELSE g÷[y] evaluates f÷[x] iff bis TRUE and g÷[y] iff b is FALSE.Application is denoted in programs by expressions of the form f÷[arg, arg, ...]. If the value of f is aclosure, this expression is evaluated by evaluating f and all the arg's, and then evaluating the bodyof the closure with the formal parameters bound to the arguments (unless an exception value turnsup; see І÷2.6.2). Thus to evaluate (l [x: INT] IN x+3)[4]:evaluate the l-expression to obtain a closure;evaluate the argument 4 to obtain the number 4;evaluate x+3 with x bound to 4 to obtain the number 7.The first two evaluations can be done in either order.To evaluate a primitive application such as x+3, evaluate the arguments, and then invoke theprimitive on those arguments to obtain the result and any state change. With a few exceptions (e.g.,assignment and dereferencing or following references), primitives are functions and can be thoughtof as tables which enumerate a result value for each possible combination of arguments. Invoking aprimitive can therefore be viewed as a simple table lookup using the arguments as the table index.Actually there may be one more step in an application. If an argument doesn't have the typeexpected by the proc, the argument is coerced to the proc's domain type if possible. If no coercioncan be found, there is a type error. Coercion is discussed further in І÷2.6.1 and І÷4.13. Most procs take a binding as argument, in which the various parts of the argument are named. E.g.,OpenFile: PROC[name: ROPE, mode: Files.Mode] takes a binding with two values named name and mode.It might be applied like this: P[name~"Budget.memo", mode~$read]. If the names are missing, thereНЇОf2tН4ТGУНG?qНЇО_шwТXНЇО\╟qТ▐ПMТ░НЇО[,Т─П"НЇОW-rТXНЇОTqТёП'ТєП3НЇОR~Т─НґОP&rqrqНґОMнrqП,НЇОKvП-НЇОIП)НґОFфТаrqП7ТбНґОEBНґОBЙТпrqТяyqП-НґОAf Т┐Т└П+yqxqtqtНґО?БxqТцr qТд yqНґО>^ Т─ rquqП3НЇО<ТґТўПDНЇО:┌Т╩П'Т╪П/НЇО8ЧТ─НЇО5сТЄ Т╣yqП9rqНЇО4OТ┐П4Т└tqtqtqНЇО2кtqТ┤П1yqП,НЇО1GТ▓П/tqxqtqxqxqtqxqxqxqxqxНЇО/цqТ─tqxqxqxqtqНЇО,≤ Т≥Т П0xqxqxqxqНЇО+Т≤П,xqxqНЇО)░Т░П_НЇО(Т─П!yqxqtqtqxqНґО%ЄyqНґО#\П/НґО!xqxqП#НЇО╛П6НЇО│ТиП)ТйxqП/НЇОЩТ┤Т┬ПXНЇОy Т√ПXНЇОУТ┼П#Т▀П=НЇОqТ─ПYНЇОFТхТиП8НЇОбТ▓rqТ⌠П3НЇО>Т─ПWНЇОТ┐Т└ПXНЇО ▐xqТ┘tqxqtqТ├xqx qП(xqxqНЇО Т▐xqxqxqxqТ░Ъ└TVk(╞THE KERNEL LANGUAGEІ÷2.316is a positional coercion which supplies them left-to-right, see І÷2.3.6. There is also a defaultingcoercion that supplies missing parts of the binding; see І÷4.11. If f is neither a primitive nor a closure, the meaning of applying it is defined by the APPLY proc forits type; this case is discussed further in І÷4.4.There are many ways of writing applications other than f÷[x]. In fact, many Cedar primitives cannotbe the values of expressions, and can only be applied by writing some other construct. Thedesugaring rules show how large parts of the Cedar syntax denote various special kinds ofapplication. In each case, the meaning is defined by the standard meaning of application and thespecific meaning of the primitives involved; see І÷4.1.This is partly because of history, and partly because specialized syntax makes the program more readable. Futureevolution of the language will improve the situation. Functions and order of evaluationAn expression is functional ifits value does not depend on the state, but only on the values bound to its free variables,andevaluating it does not change the state.As a consequence of this definition,Two identical functional expressions in the same scope will always have the same value. A proc is a function if every application of it is functional. It doesn't matter when or how manytimes a function is applied; the order of evaluation doesn't matter for functions. Thus Cedarfunctions can be thought of as mathematical functions for many purposes. Note that a constant canbe regarded as an application of a function of no arguments.Non-functional procs, on the other hand, are more complicated objects. Cedar makes no formaldistinction, either in syntax or in the type system, between functions and procs. However, it doesnot define the order of evaluation in an expression, except that: all arguments are evaluated before a proc is applied;because of the desugaring of IF, SELECT, AND and OR into l-expression, the order ofevaluation for these expressions is determined by the first rule;statements separated by semi-colons are evaluated in the order they are written.As a consequence, two applications of non-functions should not be written in the same statementunless they don't affect each other; if this is done the effect of the program is unpredictable. An expression is guaranteed to be functional if it only applies functions; thus if f is a function, p anon-functional proc, and x a variable, f÷[3] is functional and p[3] and p[x] may not be. Furthermore,f÷[x] may not be functional, because it is sugar for f÷[x.VALUEOF], and VALUEOF is not a function. Thevalue of a l-expression is a function if its body is functional. There are more complicated ways ofguaranteeing that an expression is functional, just as for any other interesting property.Because the values of variables constitute the state, it is only the existence of variables that allowsnon-functional procs to exist. In particular, the VALUEOF proc which returns the value of a variableis non-functional (because its result depends on the state), and the ASSIGN proc which changes thevalue of a variable is non-functional (because it changes the state). Н⌡Оf2tТGУНF{НЇqНЇО_шТнr qПHТоr НЇО^WqТ─П9НЇО[,Т┘xqПDТ├tqНЇОY╗Т─П/НЇОV}Т▌П2xqxq Т▐НЇОTЫТА ТБПMНЇОSu ТТТУП4НЇОQЯТ╔П=ТіНЇОPmТ─П/НЇОM┬tТф ТгПbНЇОLJТ─П-НЇОHKrТXНЇОE qТ─r qНґОBхТ⌡П$Т°П4НґОADНґО>Л Т─НЇО<■П$НґО:ТіНЇО,RТ─П?НґО)ЗП5НґО'╒ТрtqtqtqТсtqyqНґО& Т─П7НґО#фПPНЇО!nТ╔П]НЇОЙТ─П[НЇО©Т▐П*Т░П'xqxqНЇО; Т█ xqxqТ▌xqxqxqНЇОЇxqxqТ├П0xqxququqТ┤НЇО3Т■yqТ∙ПGНЇО╞Т─ПNНЇО└Т°Т²ПHНЇО Т⌠П$uqП+НЇО|Т≈Т≤П+uqНЇОЬТ─ПAЪ┌TVk(aІ÷2.3DOING COMPUTATIONS172.3.2 ValuesA Cedar program manipulates values. Anything which can be denoted by a name or expression inthe program is a value. Thus numbers, arrays, variables, procedures, interfaces, and types are allvalues. In the kernel language, all values are treated uniformly, in the sense that each can be:passed as an argument, bound to a name, or returned as a result. These operations must work on all values so that application can be used as the basis forcomputation and l-expressions as the basis for program structure. In addition, each particular kindor type of value has its own primitive operations. Some of these (like assignment and equality) aredefined for most types. Others (like addition or subscripting) exist only for certain specific types(numbers or arrays). None of these operations, however, is fundamental to the language. Formally,assignment or equality has the same status as any operation on an abstract type supplied by itsimplementor; thus INTEGER.ASSIGN has the same status as IO.GetInt. In practice, of course, specialsyntax is usually used to invoke these operations, and the implementations are not Cedar programsopen to inspection by the editor or debugger. A complete description of the primitives supplied bythe language can be found in Chapter 4, organized by the type of the main operand. Table 4²5 isan alphabetized index of these descriptions.Restrictions: In current Cedar, however, there are restrictions on values which are types, declarationsor bindings: they can only be arguments or results of modules, and hence are first-class values onlyin the modelling language, and not within a module. Also, declarations and bindings cannot beconstructed or bound to identifiers within a module. Unions are also restricted: they can onlyappear inside records. Nonetheless, it is simplest to emphasize the uniform treatment of all values,and consider separately the restrictions on types, declarations, bindings and unions. Future evolutionwill improve this situation.Restriction: In current Cedar you can only use dot notation for some operations of built-in clusters:the procs which access record fields, and others as noted in Table 4²5. As a substitute, there arevarious syntactic forms which are sugar for dot notation: infix, prefix and postfix operators, built-infunctions, and funny applications. These desugarings are given in rules 20-24 of the Cedargrammar in І÷3.2.3.3 VariablesCertain values, called variables, can contain other values. A variable containing a value of type Thas type VAR T. If the variable doesn't allow the value to be changed, the type is READONLY T; thisis not the same as T, because there may be a VAR T value which is the same container. The valuecontained by a variable (usually called the value of the variable) can be changed by assigning a newvalue to the variable. The set of all variables accessible from the process array constitutes the stateof the computation; these are all the variables which can be reached from any process, and avariable which cannot be reached cannot affect the computation. Note that a variable value is acontainer, which like all values is immutable; it may help to think of it as (the address of) a blockof storage. The contents of a variable can be changed by assignment. Thus the value of a variablecan change, even though the value that is the variable is immutable.A suitable abstract representation for a VAR T is a value of type [Get: []_T, Set: T_[]]. Thisrepresentation is not used in Cedar, but it clarifies the way in which variables fit into the typesystem: VAR TgVAR U only if T and U have the same predicate, because the Get proc requiresTgU and the Set proc requires UgT. READONLY T corresponds to [Get: []_T] and a write-onlyvariable type would be [Set: T_[]].There is a coercion (an automatically applied conversion; see І÷2.6.1) from VAR T to T, so that avariable can be passed without fuss as an argument to a proc which expects a value.НЇОf2tН4ТGУНG?qНЇО_шrТXНЇО\╟qТ√Т≈ПUНЇО[,Т╡ТЁПRНЇОY╗Т─ПYНґОWPНґОTЬНґОR═НЇОOuТППPТЯНЇОMЯ Т▒yqТ▓П5НЇОLmТ√rqП\НЇОJИТ╟Т╠ПFНЇОIeТ∙ПYНЇОGА Т╦ПUНЇОF]Т═tquqТ║xqП!НЇОDыТ▒ПHТ▓НЇОCUТ░П[Т▒НЇОAяТ█П!Т▌П;НЇО@MТ─П*НЇО="rqТ│П?НЇО;·Т┼ПJТ▀НЇО:Т╩П1Т╪П*НЇО8√ ТлТмП;НЇО7Т≤Т≥ПWНЇО5▌Т─Т│ПKНЇО4 Т─НЇО0ъr qТ┬П3Т┴П&НЇО/[Т·П9Т÷П&НЇО-вТ▀Т▄ПFНЇО,S ТХТИП9НЇО*оТ─НЇО&пrТX НЇО#╔qТіТїПAxНЇО"!qТ├uqxqП)Т┤tqxqНЇО ²Т≤xqТ≥ uvxqП-НЇОТ┘П)rqТ├НЇО∙Т≤Т≥П.rqНЇОТхП#ТиП7НЇО█ТЁТЄП?НЇО rqТ■П?Т∙НЇО┘Т°Т²rqПНЇОU?Т─П'tqtqНЇОRТ▓ПLТ⌠НЇОP░Т╘uqТ╙П/xqrqНЇОOТ┴xqxqxqТ┼uqНЇОM┬Т─НґОK0xqxqtqxq xqxqxqНЇОHьТ┌rq xqxqТ┐uqxq xqxqxqНЇОGTТ╧Т╨П>xqxqНЇОEпТ─П&НЇОB╔ПLНЇО>іrТXНЇО;{qТцП"ТдП4НЇО9ВТ÷П9r qrqТ═НЇО8sxqТ■П;xqТ∙НЇО6ОТюП:ТаП!НЇО5kТ©r qТюП2НЇО3ГТ┤ПRТ┬ НЇО2cxqТ xqtqxqtqzqxqxqxqТ⌡tqxqtq НЇО0ъТ─xqxqxqНЇО-ЄТ│r qxqТ┌xqxq xqНЇО,0ТйxqТк xzxqzqxО+ё}О,0qxО+ё}О,0qzxО+ё}О,0zxО+ё}О,0zqzqНЇО*B Т▄ПSТ█xО)╣{НЇО(TqТ÷П#uqxО'г}О(TqxО'г}О(Tq xО'г}О(TzxО'г}О(TzqТ═НЇО&fТ─П"НЇО#;r qП/Т│П'НЇО!ЇТ⌡П-tqtqtqzqtqtqТ°НЇО 3Т╙ПCТ╚НЇО╞Т┌Т┐П]НЇО+ Т≤Т≥П&zqНЇОїuqТ─ПWНЇО╗rТXНЇО}qТ┬Т┴ПYНЇОЫТ─П)Н°О║НґТ∙П)xq Т√ tqxqtqxqtqНґОТ╘xqxqtqТ╙НґО ≥xqxqТ·xqtqП,rТ÷qНґОТ─Н°О ҐНґuqП9uq░TVk(YІ÷2.3DOING COMPUTATIONS19LET i~3, b~TRUE IN (IF b THEN i+5 ELSE 0)has the value 8. Current Cedar doesn't have LET expressions, but a binding at the beginningof a block has the same effect. See І÷2.5.4 on scopes for details.ЇAs a way of collecting and naming a set of related values. A value can be extracted fromthe set using dot notation. Thus if b is the binding [i~3, b~TRUE], the value of b.i is 3. Incurrent Cedar this only works for interfaces; see І÷3.3.4 and І÷4.14 for details.A binding is usually denoted by a constructor, which takes the form[i~3, b~TRUE]or redundantly (if there are no coercions)[i: INT~3, b: BOOL~TRUE]in which the types are specified explicitly (but you can't write the second form as the argument ofan application). See І÷2.5.5 on constructors for details.2.3.6 ArgumentsWhen a group or binding is bound to a declaration (d~v), there are various conversions calledcoercions which may be applied to the values. This usually happens when the arguments of a procapplication are bound to the parameter declaration.First, if v is a group rather than a binding, it is coerced to a binding by attaching the names from dto the elements of v in order. Thus in[a: INT, b: REAL]~[2, 3.14]the group constructor is coerced to [a~2, b~3.14].Next, if v is shorter than d, elements of the form n~OMITTED are appended, where n is thecorresponding name from the declaration. Thus in[a: INT, b: REAL]~[2]the group constructor is coerced to [a~2, b~OMITTED].Now the items of the binding are matched by name with the items of the declaration. There is anerror unless the names match exactly. The remaining coercions are done on individual items, n: tfrom the declaration and the corresponding n~v from the binding. If v has type t, all is well.Otherwise, if there is a sequence of coercions from the type of v to t, these are applied to v. If nosuch sequence exists, there is an error. In particular, there is a coercion from OMITTED to the defaultvalue for t, if any. Thus in[a: INT_0, b: REAL_1.1]~[b~3.14]the group constructor is coerced to [a~0, b~3.14], and in[a: INT_0, b: REAL_1.1]~[]it is coerced to [a~0, b~1.1]. Coercions are discussed in І÷2.6.1 and І÷4.13, defaulting in І÷4.14.An important special case is constructors for record and array values. A record type has aconstruction proc; e.g., R: TYPE=RECORD[a: INT, b: REAL_0.]has a proc R.CONS of type PROC[a: INT, b: REAL_0.]_[R]. Thus R.CONS[a~2, b~3.1416] constructs arecord value. There is also a coercion from BINDING to the particular binding type RB which is thedomain type of R.CONS, so that r1: R_[a~2, b~3.1416]is short forr1: R_R.CONS[a~2, b~3.1416].Composing the positional coercion from GROUP to RB with R.CONS makes r1: R_[2, 3.1416]also short for the previous line.The same scheme works for arrays, but only an array indexed by an enumeration has acorresponding binding which can be written; the elements of an array indexed by numbers don'thave names which can be written in a binding. However, the group constructor still works.ЪНЇОf2tН4ТGУНG?qН⌡О_шuqТXxqxqtquqtqxqtqxqtqНґО^WТ┌П)uqП,НґО\сТ─П@Н°ОZ{НґТ÷П@Т═НґОXВТ≤П!xqxqxqtqxqxqТ≥НґОWsТ─ПJНЇОTHПCН ОRдxqТXxqtqНЇОQ@Т─П(Н ОO╪xqТXtqxqtqtqНЇОN8Т⌠Т■ПCНЇОLЄТ─П7НЇОH╣rТX НЇОE┼qТбП/xqxqТцП%НЇОDrqТ∙П>Т√НЇОB┌ Т─П(НЇО?WТ├xqТ┤ПZxНЇО=сqТ─xqН О┌ТкП)rqТлП%НґО<ЧТ├ПCТ┤НґО;zТПП:ТЯНґО9Ж Т─ПKНЇО7·П>НґО5FТ┤ПYНґО3бТЁП;ТЄНґО2> Т─rq НґО/ФТЎТ©П?НґО.bТ─П?rq НЇО, Т═П7Т║П%НЇО*├Т─xqП"Н О)xqТXtqxНЇО'~qТ▄xqxqТ█xqxqxqП*xqНЇО%ЗТьТыП@НЇО$v ТкПAТлНЇО"Р Т┼Т▀ПRНЇО!nТ─НЇОCrqТ xqП$xqxqНЇО©ТаТб xqП/НЇО; НЇОr qТ─П:tqНЇОrТXП"НЇОФqТТП5ТУНЇОbТ≈ПIТ≤НЇО чТ─ПFН ОZxqТXtqtqtqtqН О жxqtqxqxqН О RxqxqxqxqЪLTVk(║І÷2.4THE TYPE SYSTEM21there must be a check that i>0 and i<10 just before the expression a[i] is evaluated. This is calleda bounds check; if it fails there is an exception called Runtime.BoundsFault. Where did this checkcome from? Note that a[i] is short for Da.APPLY[a, i], and Da.APPLY is SUBSCRIPT, the subscriptprocedure for ARRAY [0..10] OF INT. The type of SUBSCRIPT is PROC[array: ARRAY [0..10] OF INT,index: [0..10]]_[VAR INT]. So when i is passed as the index argument, the declaration of SUBSCRIPTsays it must have the type [0..10]. The predicate for this type is l [x: ANY] IN HASMARK[x, INT] AND LET y: INT~x IN y>=0 AND y<=10.Leaving the HASMARK term for later discussion, we see that the rest of the predicate is the same asthe bounds check.The type system is designed, however, so that most assertions can be checked statically (i.e., proved),by examining the text of the program without running it. Static checking has three obviousadvantages:It reports any errors after a single examination of the programming, leaving none (of thiskind) to be discovered later in Peoria.It introduce no cost in time or space for run-time checking.The compiler can take advantage of the assertions to generate better code.Of course, there is a corresponding drawback: the assertions made by parameter declarations mustbe simple enough that the compiler can reliably prove or disprove them. The proofs done for typechecking have exactly the same form as program correctness proofs basedon preconditions and postconditions. Consider a proc whose value is the l-expression l [x: T]=>[y: U] IN e. The domain declaration [x: T] is a precondition for the body e. This means that any application ofthe proc must satisfy this condition. As a consequence, the body e can be analysed on theassumption that the precondition holds, i.e., that x has type T. Similarly, the range declaration [y: U]is a postcondition for the body. This means that given the precondition, any evaluation of e mustproduce a value y which has type U. In summary, for the body we assume the precondition andmust establish the postcondition.To make this hang together, each application must establish the precondition; this means that theargument must have the domain type. In return, the application can assume the postcondition; thismeans that the result of the application has the range type. Thus we have a linkage:argumentgdomaingrangegresultThe result in turn will be the argument of another application. In this way the proof is extended tolarger and larger expressions, and finally to the whole program. In summary:Application²establish pre-condition: arguments have the domain type;rely on post-condition: results have the range type.Body²rely on pre-condition: parameters have the domain type;establish post-condition: returns have the range type.These proofs require showing that an expression always has a particular type T. This is done byobserving that every expression has a unique syntactic type U, which is the type of every evaluationof that expression; e.g., an application always has the range type of its proc (see below for a moredetailed discussion of syntactic type). If every value of type U has type T, we are done. Hence theusefulness of type implication. One type implies another, TgU, iff (Ax) T[x]gU[x]. If two typesare equal, each implies the other. However, there are many other useful cases of implication. Forinstance, VAR INT implies READONLY INT. The type implications in current Cedar are given inІ÷4.12.Of course, not all arguments are applications. The kernel grammar gives the other possible forms ofargument expressions, and we enumerate the proof rules for each:A literal is like a zero-argument proc: it has a known range (e.g., 3 has type INT, 'A hastype CHAR). НЇОf2tН7UТGУНG?qНЇО_шТ▐xzqТ░xzqxqxqНЇО^WТ╣rqТІxqНЇО\сТЇxqxqzxqtqxqxqzxqtquqНЇО[OТ╘tqtqtqТ╙uqtqxqtqtqtqНЇОYкxqТ zquvtq xqxqТ⌡uНЇОXGqТ─П?Н ОVцyqТXxqtqtquqxqtqtquqxqtqxquqxqtqxqНЇОU?Т▓uqТ⌠П2НЇОS╩Т─ НЇОP░Т┐ПIТ└r qrqНЇОOТХПJТИ НЇОM┬ НґОK0Т╒ТёПEНґОI╛Т─П"НґОGTП<НґОDЭПJНЇОBєТ⌡П/Т°П/НЇОA Т─ПFНЇО=УТ⌠Т■ПPНЇО[y: U] IN e has the type [x: T]_[y: U]. This works for the reasondiscussed in the next paragraph.A binding constructor [x~e, y~f] has the type of the corresponding declaration, [x: De, y:Df].There is one more link in the chain. An application f÷[x] has an arbitrary expression for f, notnecessarily a l-expression. The requirement is that f must have a proc type, say D_R; D is thedomain type and R the range type. Since the type of l D=>R IN e is D_R, satisfying theprecondition D for the application is the same as satisfying the precondition D for the l-expression,and similarly in reverse for the postcondition. The value of f may be a primitive rather than aclosure obtained from a l-expression. In this case, the implementation of the primitive can stilldepend on the precondition and must still establish the postcondition, but since the implementationcannot be examined (within the framework of Cedar) we can say nothing about how this isaccomplished. Example: INT.PLUS, which is implemented by the machines 32-bit add instruction.In a proc type D_R, D and R may be declarations which provide names for the arguments andresults. In general, the expression R may include names declared in D. The range type of anapplication then depends on the argument values. Restriction: In current Cedar only modules have such types; the type returned by an interface, or the interfaces exported by an implementation, may depend on the interface and implementationparameters.As a by-product of the type-checking proof rules just given, a syntactic type is derived for everyexpression e in the program. It is denoted by De, and computed as follows:for a name, the declared type; for a literal, its type;for an application, the range type (which may depend on the argument); for a l the obvious proc type;for a binding constructor, the declaration obtained by pairing the names with the syntactictypes of the value expressions.Typechecking ensures that whenever e is evaluated, the resulting value will have type De (though itmay have other types as well, i.e., it may satisfy other predicates). The main use of syntactic types isin connection with dot notation (see І÷2.4.4).In order to carry out the proofs described above, the compiler must either compute the values of alltypes, including those denoted by complex expressions such as ARRAY [i..j] OF INT, or it must beable to prove the equality of unevaluated type expressions. For the most part, current Cedarrequires the former approach; hence a type expression must have value which the compiler cancompute. Such a value is called static; the rules for static values are given in І÷3.9.1. ЪН⌡Оf2tТGУНF{НЇqНґО_шТ─П<НёО]йТ≈xqТ≤xqxqtqП$НёО\FТ║yqП=xqТ╒ НёОZбТ─xqП%НёОX╠Т└xqxqxqxqtqxqТ┘НёОW-Т─xqНґОTуТ┴yqyqxqxqxqxqtqxqxqxqzqxqxqТ┼НґОSQТ─НґОPЫТ╒xqxqxqxqТёxqzxqxqНґОOuzxqНЇОLJТбП.ТцxqxqП"xqНЇОJф ТґyqТўxqxzxqxqНЇОIBТь xqТыyqxqxqtqxqxzxqНЇОGЎТ┬xqТ┴xqyqНЇОF:Т╪П9ТҐxqП!НЇОDІТ╧yqТ╨П<НЇОC2Т┬Т┴П@НЇОAўТъП3ТЮНЇО@*Т─ tquqП>НЇО<ЪТ╘xzxqxqxqТ╙П$НЇО;{Тяxqxq Тр НЇО9В Т─rqНЇО6лrТ÷qТ═П?Т─НЇО5HТ╧П8Т╨П!НЇО3д НЇО0≥ТґП.Тўr qНЇО/ Т─xqП"zxqНґО,ҐНґО*eНґО( ПGНґО%╣yqНґО#]Т≈ПEТ≤НґО!ыТ─НЇО│Т┼xqП,Т▀zxq НЇОЩТ┐ПeНЇОyТ─П,НЇОNТ┌П3Т┐П/НЇОйТіТїtqxqxqtqtqНЇОFТзП7ТшП!НЇОбТЇП"Т╦П2НЇО>Т─rqП4ЛTVk(мІ÷2.4THE TYPE SYSTEM232.4.3 MarksBy this point you may have thought of asking why the assertions provided by type predicates areworth all this fuss. The reason is simple: they are the basis for authenticating values of an abstracttype, so the implementation can be sure that it is working on properly formed values. Suppose youare the implementer of an abstraction, e.g., Table. You provide operations to Lookup a key in thetable, to Insert a [key, value] pair, and to Enumerate the items in the table. A Table is implemented asa REF to a record containing a sorted array a of items and an INT n which gives the number ofitems. Lookup is implemented by binary search. All three operations are programmed on theassumption that elements 0 through n²1 of a are sorted, and that n is smaller than the size of thearray. They will not work properly if these assumptions are not satisfied, and indeed they may tryto subscript the array with an out-of-bounds index or to violate other requirements of theabstractions they depend on.Here is a lower level, but perhaps more dramatic example. The dereferencing operation ^ for a REFREAL returns a VAR REAL, which can, for instance, be assigned to, as in the program fragmentr: REF REAL_NEW[REAL_1.0];. . .r^ _ 3.14159A REF REAL is represented by the address of a four-byte block of storage which holds a REAL, andthe assignment to r^ stores the four bytes which represent 3.14159 into that block. If somehow aREF BOOL finds its way into r, the assignment will still store four bytes, since it doesn't know anybetter. But the REF BOOL points to a two-byte block; the other two bytes that will be modifiedbelong to some unrelated variable, which will be clobbered without warning. The second example is scarier because the consequences of the bug seem more unpredictable. Inboth cases, however, the fundamental problem is the same: even if the implementation is correct,the wrong thing happens because it is given an improper value to work on. Or to make the samepoint in different words, the implementation cannot be held responsible for bad results from one ofits operations, if it has no control over the validity of the arguments it receives.So that the implementation of an abstraction can take responsibility for correct operation, theremust be a way to authenticate a value of the abstract type. In Cedar this is done by placing a markon the value; think of it as a little flag stuck into the value. The mark uniquely identifies theabstract type, and authority to affix it is under the control of the implementation. A correctimplementation will mark only values which have the properties needed for a representation of anabstract value, and if no one else can affix the mark, the implementation can be sure that everyvalue with the mark has the desired properties.A mark can be thought of as an abbreviation for an assertion or type invariant which characterizes aproper abstract value, such as Table or REF REAL. Such an assertion can be quite complex. In theTable example, it would say that the representation is a record of the proper form, that n is less thanthe array size, and that the first n array elements are sorted. In the REF REAL example, it would saythat the address points to a block of storage such that at least the first four bytes don't overlap anyother blocks. Such assertions are not easy to write down formally, and proving them is certainlybeyond the power of any existing program. So the abbreviations are not a mere convenience, but anecessity.A new mark can be created on demand by the primitive CREATEMARK: PROC[Rep: TYPE, tag: UNIQUEID]_[m: MARK, Affix: [Rep]_[TYPEFROMMARK[m]] ]The primitive HASMARK tests a value for the presence of a mark, so HASMARK[x, m] tests x for thepresence of the mark m. Affix adds the mark to a Rep value. Restriction: MARK, UNIQUEID, CREATEMARK, HASMARK and TYPEFROMMARK are not accessible incurrent Cedar. Record and array type constructors provide some access to CREATEMARK, asdescribed below. The ISTYPE primitive, also described below, is closely related to HASMARK.ЪНЇОf2tН7UТGУНG?qНЇО_шrТXНЇО\╟qТ═Т║ПJНЇО[,Т■Т∙ПRНЇОY╗Т▄Т█ПBНЇОX$ТїП*xqxqТ╗ НЇОV═Т│xqТ┌xqxqНЇОUТ╛tqП'xqtqxqНЇОS≤ТДxqПLНЇОR Т⌠xqТ■xqxqНЇОP░Т≥П5Т П'НЇОOТЬПTТЫНЇОM┬Т─НЇОJ]Т┬П,Т┴П.tНЇОHыqТ─ uqtqПEНyОGUxqТXtТGqtqtqНyОEяТXНyОDMxq НЇОBиТ▌tqtqТ▐П/tqНЇОAEТ╘xqП9Т╙НЇО?аtqТ°tqТ² xqПGНЇО>=Т╣tqtqП0ТІНЇО<╧Т─ПFНЇО9▌Т╘П3Т╙П'НЇО8 ТёПSТєНЇО6├Т²ПZНЇО5Т┘Т├ПJНЇО3~Т─ПQНЇО0SТҐТЎПZНЇО.оТ┼rqП/Т▀rНЇО-KqТюП(ТаП7НЇО+гТщПLТч НЇО*C Т≤П;Т≥НЇО(©Т╛ПXНЇО';Т─П*НЇО$Т┐П;Т└r qНЇО"▄Т═Т║xqtqtqП0НЇО!xqТ│П1Т┌П#xqНЇО└Т┬xqП#tqtqНЇОТ▀Т▄ПPНЇО|Т╟Т╠П?НЇОЬТ▌ПBТ▐НЇОt НЇОIТ─П3НyОеТXu qtqxqtqxquqzqxquqxТOqТXxqzquqxqНЇОAТ² uqТ·uqxqxqНЇОҐТ─xqxqxqНЇО▓r qТГuququ ququqТХНЇО ТП2Тu qНЇО┼Т─tqП8uqЛTVk(THE KERNEL LANGUAGEІ÷2.324With these facilities, it is easy to create a new abstract type. Choose its representation type, andobtain a new mark m. TYPEFROMMARK[m] with an appropriate cluster added is the new abstract type.The implementation must use Affix to mark only values which satisfy the properties it demands.The type returned by TYPEFROMMARK[m] has the predicate l [x: ANY]=>[BOOL] IN HASMARK[x, m]and an empty cluster. Except for subranges and bound unions, all types in current Cedar have apredicate of this form. The built-in types (INT, BOOL etc.) come with such predicates, and the built-in type constructor procs (ARRAY, RECORD etc.) obtain a mark from CREATEMARK. So that twoinvocations of ARRAY [0..10] OF INT will produce the same type, ARRAY and most of the otherconstructors use a canonical encoding of the constructor and its arguments for the UNIQUEID, andhence are functional. RECORD and ENUMERATION produce a different type each time they areinvoked, so they obtain fresh unique identifiers. Since the program cannot invoke CREATEMARKdirectly, we need not explain how to prevent forgery of UNIQUEIDs. Future versions of Cedar will addressthis problem.In current Cedar you make a new abstract type by declaring in as an opaque type in an interface:T: TYPE[ANY]This generates a new mark, and declares T to be a type which has that mark. You get such a typeby explicitly painting some other type, normally in an implementation which exports T to theinterface which declared it:T: PUBLIC TYPE~Interface.T PAINTED RECORD [...].See І÷4.3.4 for more details.The implementation actually stores a mark with each variable allocated by NEW. Such a variable canbe referenced by a REF, and in particular by a REF ANY value. The type of a REF ANY value can betested at runtime using the primitive ISTYPE: PROC[x: ANY, U: TYPE]_[BOOL]If De is REF ANY and RT=REF T, then the value of ISTYPE[e, RT] is TRUE iff the predicate for Tjust tests for mark m, and x^ has the mark VAR m. ISTYPE is described in detail in І÷4.3.1, along withthe WITH ... SELECT construct and the NARROW primitive, which are more powerful operations builtup from ISTYPE.For other values, there is no mark actually stored; instead, types must be computable staticallyusing the methods described in the last section. The AMTypes interface, however, gives a way torefer to any value in a uniform way, and to test its type at runtime.There is only room for one mark on a variable, and this must encode all the marks that the valueactually carries. We arrange for this by imposing a partial order on the marks, and requiring that:The set of marks on a value must have a maximal element.Every mark smaller than the maximal one must be on the value.With these rules, a single mark stored on the value is enough to code all the others.In current Cedar, a value actually has only one mark, since:The only way to create a new mark is with the record or enumeration type constructors, orby declaring an opaque type.When you paint a type T with the mark of an opaque type, T must be a record orenumeration type, and the opaque type mark replaces the mark it had before.Note that VAR T, READONLY T and T are different types with different marks, although VARTgREADONLY T, and there is a coercion VALUEOF from either one to T.ЪН⌡Оf2tТGУНF{НЇqНЇО_шТ╠ПCТ╡НЇО^WТ┌xquqxqП7Т┐НЇО\сТ─xqП=НЇОY╗uqxqНyОX$yqТXxqtqtququqxqxqНЇОV═Т╗ПTТ╘НЇОUТ┼П#tqtq Т▀П%НЇОS≤ТцtqТдtqu qНЇОR Т╩tqtqТ╪tqtqНЇОP░Т╙Т╚П+uqНЇОOТоtqt qТпНЇОM┬ТдТеП5u НЇОLqТ≈П/uqtП%НЇОJ─Т─НЇОGUqП`Н ОEяxqТXtqtqНЇОDMТ⌠П$xqТ■П#НЇОBиТмП.ТнП$xqНЇОAEТ─Н О?аxqТXtТGqx qТXtТGqТXНЇО>=Т─НЇО;Т│ПGtqТ┌НЇО9▌Т┘tqtqtqtqtqНЇО8 Т─НyО6├tqТXtqxqtqxqtqzqtqНЇО5Т·zxqtqtqxqtqxqtqxqxqtqТ÷xНЇО3~qТ┌xqxquqxqtqП)Т┐НЇО1ЗТ┬tqtqtqТ┴НЇО0vТ─tqНЇО-KТаПGТбНЇО+гТЁП0xqТЄНЇО*CТ─П@НЇО'Т√Т≈П>НЇО%■Т─П[НґО#<П8НґО ДrqП8НЇО▄ПUНЇОaП<НґО Т▄Т█П8НґО┘Т─НґО-ТуxqП!xqТжНґО╘ Т─rqНЇО~ТсtqxqtqxqxqТтtНЇОЗxztqТ─xquqxqчTVk(ГІ÷2.4THE TYPE SYSTEM252.4.4 Clusters and dot notationIt is convenient to associate with a type the procs supplied by its implementor for dealing withvalues of the type. This is done by putting these procs into the type's cluster. The cluster is simply abinding which is part of the type value (the predicate is the other part). There are no rules enforcedabout what goes into the cluster. However, there is a special dot notation which makes it desirableto populate T's cluster with procs which take a T as their first argument. The usual effect is likethis: t.n is sugar for Dt.n[t], and t.n[other args] is sugar for Dt.n[t, other args]. For example, if t has type T, and a proc [T, INT]_[BOOL] is in T's cluster under the name P, thenthe proc can be applied by an expression like t.P÷[3], which is sugar for Dt.P÷[t, 3]. The name P islooked up only in T's cluster, not in the current scope. If Q: [T]_[INT] is also in the cluster, it canbe applied with t.Q, which is sugar for Dt.Q÷[t].The general rule that makes this work is the following: t.n is sugar for LOOKUPC[Dt, $n][t].LOOKUPC[Dt, $n] is just Dt.n, except that if Dt.n is a proc that takes several arguments, it is splitinto a proc that takes the first argument and returns a proc taking the remaining ones. ThusLOOKUPC[Dt, $n][t] will be a proc taking the remaining arguments, and t.n[other args]=LOOKUPC[Dt,$n][t][other args] will be the same as Dt.n[t, other args].Dot notation can also be used to obtain values from a binding or from the cluster of a type withoutany application: T.P would be the proc named P in the previous example. The possible cases of dotnotation in current Cedar are described in detail in І÷4.14.Restriction: There is currently no way to explicitly construct clusters. The built-in types and typeconstructors have clusters; they are described in detail in І÷4. In addition, there is a clumsy way toprovide a cluster for an opaque or record type in an interface: every proc name in the interface isput into the type's cluster. For a record, the procedures supplied by the record constructor are alsoin the cluster, and they win if there are name conflicts. There is one of these clusters for each typein each imported interface value; if a module imports more than one value of the same interface,however, there are severe restrictions (see І÷3.3.3).2.4.5 DeclarationsA declaration is the type of a binding. Thus, the binding [x~3, y~3.14] has the type of the decl [x:INT, y: REAL]. All the relationships among types, and between types and values, are carried overelementwise to decls and bindings; the elements are matched up by name rather than by position.A decl itself simply has the type DECL.A decl is made up of two parts: the names or pattern, and the types. The basic operation formaking decls, MKDECL, takes a pattern and a type. Thus MKDECL[ PATT[x, y], INTXREAL]=[x: INT, y:REAL]. In general, a pattern is one of NIL, a simple name, or a pair of patterns, just like a Lisp S-expression. Similarly, a type argument to MKDECL is one of NIL, a type, or a cross type. The typemust decompose in a way which matches the pattern. Normally, as in Lisp, we deal only in flatpatterns, where the first element of a pattern is always a name. Such flat patterns are convenientlydenoted by constructors of the form [x, y, ...]. The reason for defining things in terms of pairs isthat it makes it much simple to write down precise rules for the semantics, using structuralinduction on the values.The main use of a decl is to type-check a binding. The basic binding constructor is MKBIND[d, e],where d is a decl and e is matching group or binding. If e is a binding, then its structure and namesmust match the structure and names of d, and each element of e must have the type demanded bythe corresponding component of d, after a possible coercion. Thus MKBINDD[[x: INT, y: REAL], [x~3,y~3.14]]=[x~3, y~3.14]. This may seem pointless, but it has two important uses:Such a binding is used to bind the argument of a proc to the domain declaration. Eventhough the resulting binding is the same as the argument, the type-checking is essential.ЪНЇОf2tН7UТGУНG?qНЇО_шrТXНЇО\╟qТЇПMТ╦НЇО[,Т─П:Т│П(НЇОY╗Т┌П%Т┐П:НЇОX$Т■ Т∙ПTНЇОV═Т╗ xqТ╘ xqП2НЇОUТ─xq zxqxqxqxqzxqxqxqНЇОQЯТ■Т∙xq xq xqtqzqtqxqxqНЇОPmТ°П+xqxqzxqxqxqТ²xqНЇОNИТ▐xqП)xqxqzqtqТ░НЇОMeТ─ xqzxqxqxqНЇОJ:ТНП5xqТОuqzxqxqxqНЇОHІuqzxqТіxq zxqxqzxqxqТїНЇОG2ТяП)ТрП/НЇОEўuqzxqТ┬xqxqТ┴П/xqvuqzxqНЇОD*xqxqТ─zxqxqНЇО@ЪТ└ПFТ┘НЇО?{Т├ xqxqТ┤xqП3НЇО=ВТ─П4НЇО:лr qТ╚ПOТ╛НЇО9HТ⌠П"Т■П8НЇО7дТ≤П"Т≥rqНЇО6@Т▐ПBТ░НЇО4╪Т█Т▌ПJНЇО38Т÷rqП<Т═НЇО1ЄТ─П-НЇО-╣rТXНЇО*┼qТ▌Т▐П+xqxqП!xqНЇО)tqТўxqtq Т╞ПJНЇО'┌ Т≤Т≥П=НЇО%ЧТ─П!uqНЇО"сТбТц rqП(НЇО!OТ┘Т├uqП#uquqxqxqtztqxqtqxqНЇОкtqТ∙ Т√tqП;НЇОG Тєuq tqТ╔r q НЇОцТґП!ТўП8НЇО?Т∙Т√П>НЇО╩ТіxqТїxqП;НЇО7ТДП.ТЕП*НЇОЁТ─НЇО┬ТіТїПEuqxqxqНЇОТ└xqxqП!Т┘xqП+НЇО─Т░Т▒ xqxqНЇОЭТ░xqТ▒uqxqtqxqtqxqНЇО xxqxqТ─xqП?НґО ТўТ╞П?НґО °Т─ПSЪTVk(VTHE KERNEL LANGUAGEІ÷2.326There may be coercions involved, so that the resulting binding is not the same. Coercionson the component values are discussed in І÷2.6.1. There are also coercions on the bindingitself, which can default missing elements; these are discussed in І÷2.3.6.If e is a group, it is first coerced to a binding by attaching the names from the decl, as discussed inІ÷2.3.6. Thus in MKBINDD[[x: INT, y: REAL], [3, 3.14]] the second argument is coerced to [x~3,y~3.14], and things then proceed as before.Bindings may also be used in LET expressions. Here the types are often redundant, and it is betterto use the MKBINDP primitive to bind the value directly to a pattern. The syntactic type of the resultis the decl whose type is the syntactic type of the value. Thus [x~3, y~3.14] is short forMKBINDP[PATT[x, y], [3, 3.14]]; its syntactic type is MKDECL[[x, y], D[3, 3.14]]=MKDECL[[x, y],INTXREAL]=[x: INT, y: REAL].A decl D in a block is interpreted somewhat differently. It becomes the argument of the NEWFRAMEprimitive, which turns the type of the decl D.T into the corresponding VAR type VT=D.T.MKVAR[],allocates a new value v of type VT, and makes the binding MKBINDP[D.P, v] over the scope of theblock. Thus {x: INT; y: REAL; S} becomesLET [x, y]~[VAR INT, VAR REAL].NEW IN SHere D=[x: INT; y: REAL], VT=[VAR INT, VAR REAL], and v=[VAR INT, VAR REAL].NEW. Note thatthe types might have defaults, which are used to initialize the values as part of the NEW operation.Actually this is a bit oversimplified, since NEWFRAME has to separate the bindings in the block fromthe decls, construct the variable binding just described from the decl, and then combine it with thebinding from the block. Thus {x: INT; y: REAL; z~TRUE; S}becomesLET [x, y, z]~([VAR INT, VAR REAL].NEW PLUS [TRUE]) IN Sor more readablyLET x~VAR INT, y~VAR REAL, z~TRUE IN SAnomaly: In Cedar the names in a block are introduced recursively, so that the d's and b's can referto each other. It is possible for a binding or type to refer to a value which has not yet beeininitialized, with undefined results. See І÷3.4.1 for a further discussion of this point.2.4.6 ClassesAnother important use of a declaration is to characterize the cluster of a type. Since the cluster isjust a binding, it is characterized by its type, which is a decl. When used for this purpose, a decl iscalled a class. See І÷4.1 for further discussion of classes, and an enumeration of the primitive classesof Cedar.2.5 ProgramsThis section describes how meaning is assigned to kernel programs.2.5.1 Structure of programsA kernel program is an expression, which is either atomic (a name or literal), or is an applicationwhich involves sub-expressions: the proc being applied, and the arguments. The concrete syntaxtreats certain kinds of expressions specially: modules, blocks (which introduce new variables andreturn no value), and statements (which return no value). All desugar into simple expressions,however, and are treated identically in the kernel.Н⌡Оf2tТGУНF{НЇqНґО_шТ²Т·П6НґО^WТ÷Т═ПSНґО\сТ─ПDНЇОZ{Т┴xqПIТ┼НЇОXВТуuqxqtqxqtqП/ТжxqНЇОWsxqТ─П#НЇОTHТ∙Т√uqПBНЇОRдТ┤uqП(Т┬П,НЇОQ@ТЬП?xqxqТЫНЇОO╪uquqxqТxqТuqxqxqzq uqxqxqНЇОN8tztqxqТ─tqxqtqНЇОK Т┴xqПPuНЇОI┴q Т÷П"xuqtqТ═xqxuquqНЇОHТєxqxquqxquqxqТ╔НЇОF│Т─Н ОDЩxqТXtqxqtqxqНЇОCyН ОAУuqxТOqtТG qtqТXuqxНЇО@qqТ▀xqxqtqxqtqxqtqtqtqtqТ▄xqtqtqtqtqtq НЇО>МТ─ПStq НЇО;бТ┬Т┴uqП/НЇО:>Т█ПDТ▌НЇО8╨Т─Н О76xqТXtqxqtqxqtqxqНЇО5╡Н О4.uqxТOqТXxqtТG qtqТXtqtquqxНЇО2╙qТ─ Н О1&uqТXxtТGxТOqtТGqТXxqtquqxНЇО-ШrqТ│ПVТ┌НЇО,wТюПWТаНЇО*СТ─ПLНЇО&ТrТXНЇО#иqТ²П^НЇО"EТ█П[Т▌НЇО аТ├rqТ┤ПKНЇО=Т─НЇОjwТXНЇО?qТ─П>НЇО@rТXНЇОqТ·Т÷ПMНЇО▒Т╨П#Т╩П6НЇО ТІПIТЇНЇО┴ТяПXНЇО Т─П+хTVk( І÷2.5PROGRAMS272.5.2 NamesA name is a part of a program which usually serves to denote a value. There are two contexts inwhich the occurrence of a name n denotes a value:It may occur as an expression. Then n denotes the value bound to it in the scope in whichthe expression appears (see І÷2.5.4 for details).It may occur after a dot, as in e.n. Then the expression e.n denotes the binding for nsupplied by e (see І÷2.4.4 and І÷4.14 for details):the value bound to n in e, if e is a binding;the value bound to n in the cluster of e, if e is a TYPE;roughly (De).n[e] otherwise.There are also two defining contexts for a name n (see І÷2.5.5 for details):It may occur before a ~ in a binding constructor, as in n~e. The value of e is the valuebound to n in the binding denoted by the constructor (see І÷2.3.5 for details).It may occur before a : in a declaration constructor, as in n: t. The value of t is the type ofn in the declaration denoted by the constructor (see І÷2.4.5 for details).These constructors are usually recursive in Cedar; that is, the expression n elsewhere in theconstructor denotes the value bound to n in that constructor; see І÷2.5.6 for details. In the kernelthey are non-recursive unless preceded by REC.A name is not a value, but there are values of type ATOM which are related to names. An atom hasa print name which is a rope (an immutable sequence of CHARs). A name following a $ is an atomliteral; $n denotes the atom with print name n. Other properties of atoms are described in І÷4.5.1.1.Caution: Current Cedar has several complications in its treatment of names:ЇIn an argBinding27, n: e may be written instead of n~e. The syntactic context distinguishesthis from a declaration, but this usage is not recommended.An argBinding is not recursive: in {a~1; f[a~3, b~a+1]} b is bound to 2, not to 4.The declaration in an import list is non-recursive: IMPORT M is short for IMPORT M: M,and the second M denotes its binding in the currounding scope (i.e., the binding suppliedby the DIRECTORY). Inside the body of the module, of course, M denotes the importedparameter. Names which appear in an enumerationTC54 are treated specially; see І÷4.7.1.1 for details.2.5.4 ScopeA scope is a region of the program in which all names retain the same meanings (note that manynames denote variables, which can change their values in the same scope, but each name continuesto denote the same variable). In the kernel there are only three constructs which introduce a newscope, l, LET and REC. In current Cedar, these are sugared in a variety of ways: modules, importlists, proc bindings, blocks, exit labels, open, iterators, safeSelects and withSelects. All havestraightforward desugarings, however.2.5.5 ConstructorsThe kernel has constructors, denoted [...], to make expressions which denote group, decl andbinding values more readable. There is one flavor of constructor for each class:A binding constructor is a list of binding elements (b in the kernel syntax) of the form p~eor d~e. The presence of the ~ distinguishes it from the others. Here d is a decl elementЪНЇОf2tН;НG?qНЇО_шrТXУНЇО\╟qТ═П^НЇО[,Т─xqНґОXтТ▌Т▐xqП4НґОWPТ─П.НґОTЬТйxqТкxqxНґОStqТ─xqП&НёОQcxqxqxq НёОORxqxqxqtqНёОMAzxqxqxqНЇОJrqxqНґОGЎТїП6xqxqТ╗ xqНґОF:Т─xqПEНґОCБТ┴П:xqxq Т┼xqНґОB^xqТ─ПIНЇО@ТЛrqТМП#xqНЇО>┌ ТєТ╔xqП<НЇО<ЧТ─П&uqНЇО9сТ┬П3tqТ┴НЇО8OТ░r qП+tq Т▒rНЇО6кqТ─xqП"xqП7НЇО3═rqПDНґО1HТ▀ О1у}О1HqxqxqТ▄xqxqП%НґО/дТ─П7НґО-lП$xqxqxqxqxqxqНґО+ТёТєП%tqxq tqxqxqНґО)░Т²xqП-Т·НґО(Т╩tqТ╪xqНґО&┬ Т─НґО$0П&О$Ґ}О$0qП2НЇО 1rТXНЇОqТ⌡ПMТ°НЇО┌Т░П*rqТ▒П(НЇОЧТ÷ Т═ПTНЇОzТ÷yququqП5Т═НЇОЖТЧПVТЪНЇОrТ─НЇОsrТXНЇОHqТБПYНЇОдТ─ПIНґО lТ░П"rqТ▒xqxНґОХqТ╙xqxqП1Т╚ xqЪTVk(ЁTHE KERNEL LANGUAGEІ÷2.328(not a declaration), and p is a pattern, in which the names are being defined rather thanevaluated.A decl constructor is a list of decl elements (d in the syntax) of the form p: t. The presenceof the : without any ~ distinguishes it from the others. Again, p is a pattern.A group constructor is a list of expressions. Note that decl and binding elements are notexpressions, although constructors are expressions.Constructors are useful for making decls and bindings where the names are literal. This is thenormal case, and in fact the only case in current Cedar. If you want to make them out of otherdecls, for instance to bind an expression to a decl which is tha value of a name dn, you cannot use aconstructor; [dn~e] would bind the value of e to the name dn, not to the decl which is its value.You have to write the decl-constructing primitive directly: MKDECL[d, e].The only kinds of constructor you can write in current Cedar are:Decl constructors for proc domains and ranges, and for records and unions (fields43 in thesyntax).Binding constructors for arguments in an application, or as an expression alone if a recordor array value is needed (argBinding27 in the syntax).2.5.6 RecursionIn the kernel, you get recursive definition of names only if you write REC (or the unsugared formFIX) explicitly. In Cedar, on the other hand, decls and bindings are normally recursive, except forargBindings and import lists.The recursion is legal in a block or interface body (although anomalies are possible in some caseswhen names are used before they are defined; see І÷3.4.1). In fields it is illegal.2.6 Conveniences2.6.1 CoercionA coercion is a proc which is automatically applied under some circumstances to map a value ofone type T (called the source) to a value of another type U (called the dest), e.g. from [0..5) to INT.Coercions are obtained from the clusters of the types involved. The coercion mechanism adds nonew functionality, since the programmer could always write the applications himself, but it isimportant in concealing some of the distinctions made by the type system when they are distractingrather than helpful.There is exactly one (desugared) context in which a coercion is applied: when an expression e ofsyntactic type T appears as an argument in an application which expects a value of type U; thismeans that there is a binding n: U~e. Since nearly all Cedar constructs are desugared to application,coercions are widely applicable. The only (desugared) context in which there is no coercion is forthe first operand of dot, since in that case the cluster of the operand is used to interpret the namewhich is the second operand. Thus in the expression e.n, it is always De, the syntactic type of e, thatis used to look up n, regardless of the fact that this expression may appear as an argument to aparameter of type U. If e is not a type or binding, however, then e.n desugars to P[e], whereP=LOOKUPC[De.Cluster, $n],and in the application of P, e does appear as an argument and can becoerced. Usually the cluster for T is set up with procs which take an argument of type T, so thedomain of P is De and no coercion happens. This isn't always true, though; a subrange T of INTinherits the arithmetic procs of INT, for example, and there is a coercion from T to INT when PLUSis applies.ЪН⌡Оf2tТGУНF{НЇqНґО_шrqТ╙xqП3Т╚НґО^W НґО[ЪТ▄rqТ█xqxq НґОZ{Т─П>xq НґОX#Т╙ПUrНґОV÷qТ─rqНЇОStТфПNТгНЇОQПТ╘П2Т╙П&НЇОPlТ─ПKxqТ│НЇОNХТ╗xqxqxqТ╘xqП%НЇОMdТ─П9uqxqxqНЇОJ9ПAНґОGАТ≤П.Т≥ОHn}ОGАqНґОF]НґОDТ√П!Т≈П3НґОB│Т─П"ОC}ОB│qНЇО>┌rТX НЇО;WqТ П>Т⌡uqНЇО9сuqТёП@ТєНЇО8O Т─НЇО5$Т²ПYТ·НЇО3═Т─ПOНЇО.мwТXНЇО*нr НЇО'ёqТїП2Т╗П+НЇО&Т▌xqrqxqrqТ▐ tqНЇО$⌡ТїПCТ╗НЇО#ТыТзПFНЇО!⌠Т┴ПDТ┼НЇО Т─ НЇОДТ╔ТіПTxqНЇО`Т╞xqП/Т╟xqНЇОэТ│ Т┌ xqxqxqПAНЇОXТ║ПCТ╒НЇОтТ⌠ПLТ■НЇОPТ┐П/xqТ└ zxqxqНЇОлТ╛xqП1ТґНЇОHТлxqxqТмxqxqxqНЇОдxquqzxqxqТ═xqxqxqТ║НЇО@ТїxqП,Т╗xqНЇО ╪ТёxqzxqП1ТєxqtНЇО8qТ░tqП,xqxtquНЇО ЄqТ─ TVk(ЎІ÷2.6CONVENIENCES29If TgU it is sometimes natural to think in terms of a coercion from T to U that is implemented bythe identity function. In fact, implication is stronger than that, since it propagates through manytype constructors, including PROC, when coercion does not. Implication is discussed in І÷2.4.2 andІ÷4.12.There is a rather general rule for finding coercions from the clusters of types, though it is not ofmuch practical importance in current Cedar, since there is no way for the user to define coercions.The rule goes like this. Each cluster may have a From item and a To item. T.From should consist ofpairs with type [tag: ATOM, proc: T_U], and T.To of pairs with type [tag: ATOM, proc: U_T]. Ignorethe tags for the moment. Consider the binding n: U~e, where De=T, and TgU is false. For eachproc P in T.From or U.To we try n: U~P[e]. If P: T_V is in T.From, it maps e to a value of type V, and we have to bind n: U~P[e]. IfVgU we are done; otherwise we can recurse on this sub-problem.If P: V_U is in U.To, we have to bind m: V~e. If TgV we are done; otherwise we canrecurse on this sub-problem.The whole process fails if no path of coercion procs takes us from T to U. The search can terminatewhen all paths have been explored, and a particular path can be abandoned when a type appearson it for the second time. Since the search is done statically (by the compiler), and since the resultsof an attempt to coerece T to U can be cached, the time required for the search is not a problem.There are two obvious difficulties with this scheme. First, it may transform erroneous applicationsinto legal ones, but coercing an argument is ways not intended by the programmer. Second, morethan one path of coercion procs may exist, and different paths may give different results. Thesecond difficulty can be avoided, and the first minimized, if every coercion proc P is chosen so thatit has a (partial) inverse, and P²1[P{x]=x for all x in P.DOMAIN. This says that a coercion does notlose information, and that different paths give the same answer. Sometimes this is not feasible, e.g.for the narrowing coercion from INT to [0..5). The following rule gives the builder of clusters controlover proliferating coercions:If two procs on a coercion path have non-nil tags, they must have the same tag.In general, coercions that don't lose information can have NIL tags, and others should have differenttags. The coercions in current Cedar are described in І÷4.13. All have NIL tags, and none losesinformation except the subrange narrowing. Note that coercions extend componentwise to groupsand bindings.2.6.2 ExceptionsThe basic idea behind exceptions is to extend the value space, so that it includes not only ordinaryvalues, but also a set of exception values. An exception value has the special property that wheneverit appears in an application, it becomes the value of the application, so that it propagates upthrough the control stack of the program until it finally abecomes the value of the whole program.Of course this isn't always what is wanted, so there is a special HIDE construct which is not anordinary application, but takes its argument value, ordinary or exception, and bundles it in a variantrecord which is a normal value. Then ordinary code can be used to test for the exception and takeappropriate action. This construct is sugared to give distinctive ways of catching an exception: in thekernel with BUT (І÷2.2.4), and in Cedar with ENABLE, EXITS and REPEAT (І÷3.4.2). Cedar has twokinds of exception: GOTO labels and ERRORs, which must be raised and caught separately, and haveslightly different semantics. The main point of this treatment is that it does not require continuations or any other baroqueexplanation of how control is transferred to catch an exception. The view is that exceptions aresimply a convenience feature; the same job could be done by returning a slightly larger result fromeach proc, with an appropriate status code.НЇОf2tН8░НG?qНЇО_шТ┘УxzxqП=Т├xqxqНЇО^WТ╟Т╠ПMНЇО\сТ╔tqП2ТіНЇО[OНЇОX$Т╒ТёПBНЇОV═Т▓ПTТ⌠ НЇОUТ▌П-Т▐xqxqxqНЇОS≤Т├xqtqxqxzxqxqxqtqxqxzxqНЇОRТ∙xqП&Т√xqxqxqzxqxqxzxqНЇОP░Т─xqxqxqxqxqxqxqxqxqНґОN8Т▒xqxzxqТ▓xqxq xqxqxqxqxqxqНґОLЄxzxqТ─П;НґОJ\Т║xqxzxqxqxqxqxqxzxqТ╒НґОHьТ─НЇОF─Т┘П@xqxqНЇОDЭТ÷Т═ПEНЇОCxТ┴Т┼ПSНЇОAТТ─xqxqПBНЇО>иТ÷Т═ПVНЇО=EТ°Т²П>НЇО;аТгП*ТхП0НЇО:=Т┬ПFТ┴xqНЇО8╧Т▀xО9F}О8╧qxqxqxqxqxquqТ▄НЇО75Т▓Т⌠ПKНЇО5╠Т│rqtq Т┌П9НЇО4-Т─НґО1уП-xqxqНЇО/}Т┐П9tqТ└П'НЇО-ЫТ─НЇО*нТЫП>tqТЗНЇО)J ТўПRНЇО'фТ─ НЇО#гrТX НЇО °qТ▐ПCТ░НЇОТ┘rq Т├П-НЇО■ТоПDТпНЇОТ▓ПEТ⌠НЇО▄Т╩П7Т╪uqНЇОТ┌Т┐ПQНЇО└Т░Т▒П=НЇО Т│П?rqНЇО|Тўuq Т╞tqtqtqНЇОЬТ├tqtqП2Т┤НЇОtТ─НЇОIТ╣ПTТІНЇОе Т╧П5Т╨НЇОAТ┼Т▀ПFНЇО ҐТ─П'┌TVk(THE KERNEL LANGUAGEІ÷2.330An exception consists of a code and an optional argument value. The type of the code is ERROR T,where T is the type of the argument which does with it. GOTO labels always have empty arguments.The argument is a way of passing some information along in addition to the identity of theexception.A proper treatment of exceptions in the type system would require that each proc range include allthe exceptions that can emerge from an application of the proc. In fact, this is not required or evenpossible in current Cedar.Cedar also has signals, which historically were viewed as a kind of exception but now have a verydifferent interpretation, as a way of obtaining dynamic rather than static scoping for names. Theyare discussed in І÷3.4.3.1.2.6.3 FinalizationThis subject is discussed in І÷3.4.3.1.2.6.5 ConcurrencyThis subject is discussed in І÷4.10, where the Cedar facilities for writing concurrent programs aregiven. Writing good concurrent programs, or even correct ones, is another matter, which is beyondthe scope of this manual to more than hint at. Unfortunately, an adequate reference is lacking.2.7 MiscellaneousThe different kinds of allocation are discussed in І÷4.5. Static values are defined in І÷3.9.1.2.7.1 PragmasA pragma is a construct that does not change the meaning of the program, except perhaps to makesomething illegal which was legal without the pragma. Its purpose is to affect the implementation,generally by requesting optimization to favor one criterion over others. The pragmas in currentCedar are:INLINE, which causes a proc body to be expanded inline when it is applied. See І÷3.5.1 fordetails.PACKED, which causes array components that fit in 8 or fewer bits to be packed, and theexpense of more expensive code to access them.CHECKED, which forbids application of unsafe procs in a block, and adds runtime checkingfor some primitive procs which are otherwise unsafe (in particular, narrowing to a subrange,and assigning a proc).PRIVATE, which forbids access to items in an interface or instance except to modules whichEXPORT (or SHARE) it.MACHINE DEPENDENT, which allows positions of record fields and representation values forenumeration elements to be specified (strictly, it is the absence of MACHINE DEPENDENTthat is the pragma)Н⌡Оf2tТGУНF{НЇqНЇО_шТ▒rqrqТ▓tqxqНЇО^WТ┤xqТ┬tqП$НЇО\сТыПCТзНЇО[O НЇОX$Т▀Т▄ПMНЇОV═Т┬ПbНЇОUТ─НЇОQЯТ≤ rqТ≥П2НЇОPmТ╒П5ТёП$НЇОNИТ─НЇОJЙrТXНЇОG©qТ─П#НЇОCюrТXНЇО@∙qТ╚Т╛ПGНЇО?Т■П;Т∙НЇО=█Т─П\НЇО9▌rТX НЇО6cqТ─П\НЇО2drТXНЇО/9qТ▄ПYТ█НЇО-╣Т°Т²ПGНЇО,1ТбПVНЇО*ґТ─НґО(UtqТ⌠П7Т■НґО&яНґО$ytqТ╒ТёП=НґО"УТ─П'НґО ²tqТ▌П?Т▐НґОТ┌Т┐ПJНґО∙Т─НґО=tqТ▐Т░П4НґО╧tqТ─tqНґОatqТ▐tqТ░П/НґОщ ТЄТ╣П1tqtНґОYqТ─ЪТTVk($І÷2.8RELATIONS AMONG GROUPS, TYPES, DECLARATIONS AND BINDINGS312.8 Relations among groups, types, declarations and bindingsCedar has are four closely related basic ways of building product values from simple values (all aregiven precise meanings in І÷2.2.1 and І÷2.2.2):a group is simply an n-tuple of values (see І÷2.3.4);a X-type is the type of a group (if x: T and y: U then [x, y]: TXU) (see І÷2.4.5);a binding is an n-tuple of [name, value] pairs (see І÷2.3.5);a declaration is the type of a binding, an n-tuple of [name, type] pairs (see І÷2.4.5).Figure 2²1 illustrates the relations among these kinds of objects. In current Cedar most of theseobjects can be constructed and manipulated only as interfaces and instances. In the kernel and themodeller, all of them are first-class citizens. The primitives which go between them are defined inІ÷2.2.[a: Ta~ea, b: Tb~eb]:[a: Ta, b: Tb][a: TYPE~Ta, b: TYPE~Tb] bindingЙuНЭtН"╣uН%5tН3?uН5tН└О=fqН╠О=ЭЧ░FНAО=ЭЧ`FН║О=ЭЧ.FНоО=fpuqpН&yО=ЭЧ0FН'╘О=frН+зО=ЭЧ╘FН-┐О=frН/ЛО=ЭЧmFН1YО=fpqН=0sНфО;БqvО;UxО;БqvО;UxО;БqН╗sН!2vО;UxО;БuvО;UxН1■О;БqvО;UxО;БqvО;UxО;БqНлО9┼sН!ёsН/?sНО5▀yТXП7НЇО0╦sП(НЇО-█qТїП?Т╗НЇО, Т▓Т⌠yqП9НЇО*┘Т─ НґО(-Т▀Т▄П<НґО&╘Т─П2НёО$≤П$vqНёО"┤П7yqНёО vП$yqНґОТ▓vqvqvqТ⌠vqvqvqНґО ТєvqvqТ╔П1НґО Т─П)НґОЎТ┘П!Т├ vqvqvq НґО:ТІvqvqТЇvqvqП0НґОІТ─НЇО▀Т·ПcНЇОТ─П,Ъі╛TVk(■ь┤SYNTAX AND SEMANTICSІ÷332Chapter 3. Syntax and semanticsThis chapter gives the concrete syntax for the current Cedar language, together with an informalexplanation of the meaning of each construct, and a precise desugaring of each construct into thekernel language defined in І÷2. The desugaring, together with the definitions of the kernelprimitives used in it, are the authority for the meaning; the informal explanation is just for yourreading pleasure. However, paragraphs beginning Anomaly or REstriction document properties ofCedar not captured in the desugaring. The primitive procs and types of Cedar are specified in І÷4. In addition to the grammar rules and desugaring, there are examples for each construct. These areintended to illustrate the constructs and do not form a meaningful program. The Cedar Manual haslonger examples which do something interesting, and also illustrate the use of the standard Cedarpackages.There are several summaries which may be useful as references:A two-page summary of all the syntax, desugaring and examples in this chapter(CLRMSumm.press). A one-page summary of the full syntax (CLRMFullGram.press).A shorter and less cluttered summary of the syntax for the safe language; it also omits anumber of constructs which are obsolete or intended only for efficiency hacking(CLRMSafeGram.press). The chapter begins with a description of the notation (І÷3.1) The next sections deal systematicallywith the rules of the grammar, explaining peculiarities of the syntax and giving the semantics:І÷3.2, rules 56-61: The lexical structure of programs. І÷3.3, rules 1-5: Modules.І÷3.4, rules 6-10: Blocks, OPEN, ENABLE, EXITS.І÷3.5, rules 11-13: Declarations and bindings.І÷3.6, rules 14-18: Statements.І÷3.7, rules 19-27: Expressions.І÷3.8, rules 28-35: Conditional constructs: IF and SELECT.І÷3.9 treats various miscellaneous topics. І÷4 deals with the syntax and semantics of types.The order of the grammar rules is: module, block, declaration, statement,expression, conditionaltype, name, literaland top-down within these. ЪН⌡Оf2zТGУ НGNНЇqН╟О_∙{ТjНЇОY?qТґП8ТўП$НЇОW╩ Т║П&Т╒П0НЇОV7ТЩТЧП<НЇОTЁ Т╗П3Т╘П&НЇОS/Т╡П)yqy qНЇОQ╚Т─П^НЇОN─Т≈П[Т≤НЇОLЭТ┤Т┬ПUНЇОKxТ╒ПAТёНЇОIТНЇОFиТ─П9НґОDqТ%П<Т&НґОBМv qТ─НґО@∙П'vqНґО>=ТїТ╗П=НґО<╧Т,П!Т-П(НґО;5vqТ─НЇО8 ТёП"ТєП>НЇО6├Т─П[НґО4.П7НґО1жНґО/~zqzqzqНґО-&П.НґО*нНґО(vНґО&П,zqzqНЇО#фП\НЇО ⌡П#НґОП&НґО⌠НґОНґО▀НЇОЪTVk(ЛІ÷3.1 NOTATION333.1 NotationThis section describes the notation used in the grammar, the desugaring, and the commentary ofthis chapter.3.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. Special symbols mark constructs with special properties:╦=unsafe;Ї=obsolete;╧=machine-dependent;╣=efficiency hack.The grammar is written so that a non-terminal never expands to the empty string. When an elementof a rule is optional, that is always indicated explicitly by "?" or "..." .The following non-terminals are so basic to the language and so frequently used, that they arerepresented in the grammar by abbreviations:b=binding13d=declaration11e=expression19n=name56 (identifier)s=statement14t=type36I'm afraid this means that you must learn the meaning of these six abbreviations in order to readthe grammar.With the exception of these abbreviated non-terminals, each use of a non-terminal is cross-referenced with a small superscript number59, unless the non-terminal is defined in one of the nextfew rules. If a non-terminal (other than e, t or n) is used in more than one rule, then all the rulesthat use it are listed in a comment after its definition. Except for the entries in Table 3²1, a terminal symbol appears in only one rule. These duplicationsdo not lead to ambiguity. In most cases they are harmless, since the symbol has essentially the samemeaning in each case, and the rules are separate only for greater readability, to highlight an unusualuse of a construct, or for historical reasons. In some cases, however, the symbol has quite differentmeanings in different rules. These are marked on the left as followsЇThe rules marked with Ї are obsolete and should be avoided.6In the rules marked with * the symbol has a different meaning than in the others, andconfusion is quite possible. The programmer should bear these cases in mind.0In the rules marked with * the symbol has a different meaning than in the others, but thecontext is sufficiently clear that confusion is unlikely.A superscriptxn indicates that the terminal is repeated n times in that rule.ЪНЇОf2zТGУН;┐НG?qНЇО_шsТXНЇО\╟qТ╛П4ТґП&НЇО[,Т─НЇОW-yТXНЇОTqТ─П(Н ОR~ТXsq sqsqН ОPЗsqН ОOvsqП,Н ОMРsqПYН КОLnzqtzqzqПLН ОJЙsqsqП&Н ОIfП6sq Н9ОI.ЧwН?xОIf Н КОGБzТGqТXzТGП&|zП=Н КОFєН ОE qТXП"Н ОC°П8НыОBНыО@■ НыО?НыО=▄НЇО:aТ│Т┌П@НЇО8щТ─П=sqsqНЇО5╡ТюТаПCНЇО4. Т─П!Н О2╙sqО2ПwН О1&sqО1lwН О/╒sq О/ХwН О.sqО.dwО.qТXН О, sq О,ЮwН О+sqО+\wНЇО)▓qТ²Т·ПLНЇО(Т─НЇО$ЦТЯПPТРНЇО#_ Т▐Т░О#╔wО#_qП7НЇО!шТ⌠П%Т■П=НЇО WТ─П6НЇО,Т┌П]НЇО╗Т└Т┘ПCНЇО$Т┌Т┐П?НЇО═Т⌠ПGТ■НЇОТ─П<Н°ОдНґП;Н.Оl}НґqТЇТ╦ПBНґОХТ─ПCН.О░}НґqТ■ПCТ∙НґО Т─П2НЇО ЄО ЗwxО ЄqП)vq пTVk(}SYNTAX AND SEMANTICSІ÷334SymbolsRulesExplanation0( )19, 25, *51.1, *54expr, subrange, *position in record or enumeration[ ]19, 25, Ї37, 43, 51constructor/built-in/funnyAppl, subrange, application, ЇtypeName, fields, mdFields0{ }2, 6, 8, 13, *54interface body, block, enable, machine code,*enumerationTC,2,÷3, 6, 7, 9, 17, 27, see note in І÷3.2.29,÷30,÷÷32, 34, 35, 43, 51, 52;6, 8,÷10, 17, 27.1, 30,÷see note in І÷3.2.33,÷350:1, 2, 3, 5, Ї7, 11, 13,introducing names with types, except *51.1=position, Ї18, Ї27, 33, Ї34, 51,Ї7=open, Ї27=argBinding Ї34=withSelect*51.1, 53.19, 37dot notation for e is repeated for types0..25x4, *51.1subrange, *positiont0*21, *53infixOp, *tag+21, 58infixOp, exponent²20, 21, 58prefixOp, infixOp, exponentЇ=Ї13, 22Їbinding, infixOp=>6, 9, 17, 31, 33, 35, 52exits, enable, repeat, select choicesx4, unionTC6_14, 16, 18, 21, *55s, e_STATE, iterator, e, *defaultTC0~2, 3, 13, 20, *22, *27interface,implementation,b,argBinding,*unaryOp,*relOp~~7, 34open, withSelect6ANY*9, 40, 43*enable, variableTC, fields6CODE*13, 23*new exception, convert t to eENDCASE31, 52select endChoice, unionTC0ERROR*19, *24, 41.1*expression, *funnyAppl, transferTCIMPORTS2, 3 interface and implementationIN18, 22iterator, relOpLONG38x2, 45.1, 48cardinal/unspecified, pointer, descriptorNOT20, 22prefixOp, relOpЇNULL14, Ї27, Ї52, Ї55statement, ЇargBinding, ЇunionTC, ЇdefaultTCPACKED44, 45array, sequenceSELECT FROM29, 32, 34, 52selectx3, unionTCSHARES2, 3 interface and implementation0SIGNAL*24, 41.1*funnyAppl, transferTCTRASH27x2, 55x2argBinding, defaultTCTRUSTED6, 13block and machine code6USING1, *5directory, *locks0WITH*32, 34*safeSelect, withSelectTable 3²1: Terminal symbols appearing in more than one rule3.1.2 Notation for desugaringThe right-hand column is desugaring into the Cedar kernel language, or in a few cases intocomments describing the meaning in English. This is a purely textual transformation; i.e., it is doneon the text of the program, not on the values. The rewriting is done one rule at a time; a singlestep of rewriting involves elements from exactly one rule. The desugaring is specified by slightlyinformal 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.A | reflects a corresponding alternation in the grammar rule, ? reflects a correspondingoptional item in the grammar rule, and (bold parentheses) are for grouping as in a grammarrule. As in grammar rules, literal parentheses are underlined.Н⌡Оf2zТGУ НGNНЇqНЇО`3Чa█О_шЧaН О`3Ч ╔█О_шЧ ╔НҐО`3Ч х█О_шЧ хН$┘О`3Ч"█О_шЧ"Н(їО`3Ч╡█О_шЧ╡Н хО^zyНН%Ф НЇО]╞ЧFН хО]╞Ч VFНО]╞Ч хFН%ФО]╞Ч"sFНЇО[╦}Н хqТ─НН%ФП2Н хОZWНН%ФП*Н%ФОXЖП(НЇОW∙}Н хqНН%ФП,Н%ФОV4 Н хОTсНН%ФНОSrНОRН хОP╟НН%ФНОOOНЇОMН}Н хqНН%ФП5НЇОL█НН%ФП&НОK,Н хОIкНН%ФП(НЇОHj}Н хqНОH╟wОHjqН%Ф}НЇОG qН хНН хОE╗НН%ФН хОDGН Н%ФНЇОBФН хНН%ФН хОA┘НН%ФП%ОAкwОA┘qНЇО@$}Н хqНН%ФzqНЇО>ц}Н хqНН%ФП5Н хО=bНН%ФНЇО<}Н хzНq Н%ФНЇО:═}Н хzНqН%ФН хО9?zНqН%ФНЇО7ч}Н хzНq Н%ФП#Н хО6}zНqН%ФН хО5zНqН%ФН хО3╩zНqО4wО3╩q Н%ФП)Н хО2ZzНqН%ФНЇО0ЫН хzНqН%ФП,Н хО/≤zНqН%ФН хО.7zqzНq Н%ФО.}wО.7qН хО,жzНqН%ФНЇО+u}Н хzНqН%ФН хО*zНqО*ZwО*qО*ZwН%ФО*qН хО(ЁzНqН%ФНЇО'R}Н хzНqН%ФНЇО%Я}Н хzНqН%ФНЇО%cЧaО$░Чa█Н О%cЧО$░Ч█НО%cЧ хО$░Ч х█Н%ФО%cЧ"sО$░Ч"s█Н&О ▒yТXП6НЇО▓НЇОgqТъТЮП7НЇОЦТ┬Т┴yqП!НЇО_ТєyqyqП#Т╔НЇОшТ╞П,Т╟П2НЇОWТ─П/НґОЪТ·Т÷sqП9НґО{Т─НґО #ТдsqП:sqТеНґО÷Т─Т│sqsqП!НґО Т─П9 ТTVk(eІ÷3.1 NOTATION35Everything 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 e (expression) and t (type) in the desugaring is implicitly parenthesized, so thatthe desugared program parses as the rewriting rule indicates. To reduce clutter, these parenthesesare not written in the desugaring rules.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 BOOL argument defaulting to FALSE; if theattribute is present, the argument is supplied with the value TRUE.Examples: the following rule for subranges:subrange ::= ( typeName | ) (( [ e1 .. e2 ] | [ e1 .. e2 ) ) |(typeName | INT).MKSUBRANGE ( [e1, ( e2 | e2.PRED ) ] ) |( ( e1 .. e2 ] | ( e1 .. e2 ) ) ) [e1.SUCC, ( e2 | e2.PRED ) ] )generates these desugaringsIndex [ 10 .. 20 ]Index.MKSUBRANGE[10, 20]Index [ 10 .. 20 )Index.MKSUBRANGE[10, 20.PRED ]( 1 .. 100 )INT.MKSUBRANGE[1.SUCC, 100.PRED ]Names introduced in the desugaring are written with one or more trailing prime ("(") characters.Such names cannot be written in a Cedar program, and hence they are safe from name conflicts.The desugaring is constructed so that the ordinary scope rules prevent multiple uses of these namesfrom being confused.3.1.3 Notation for the commentaryEach section of the commentary begins with grammar rules, desugaring and examples for part ofthe language. It continues with text which explains the meaning of the constructs. Generally themeaning is fairly clear from the desugaring, and this text is short. For blocks and especially formodules, however, there are many non-obvious implications of the desugaring, and a number ofrestrictions; these constructs have a lot of explanatory text.Some kinds of information are put into specially marked paragraphs, which begin with one of thefollowing italicized words:Anomaly: the meaning of this Cedar construct is not explained by desugaring into thekernel, but by the special rule given here.Caution: here is an implication of the definition which might surprise you.Performance: facts about the time or space required by some construct.Representation: the values of a data type are represented in terms of other types like this.Restriction: a construct is not fully general, and will cause a static error unless theadditional conditions stated here are satisfied.Style: advice about good Cedar style.Symbols written in SANS-SERIF SMALL CAPITALS are in the kernel but not in current Cedar. Thesuperscript notation used to cross-reference non-terminals in the grammar is also used in theexamples, usually to point to a rule whose example introduces a name.ЪНЇОf2zТGУН;┐НG?qНґО_ш Т─НЇО]┐Т≥Н/О]KЧІНЕО]┐П.Т НЇО[ЪТўyqТ╞ПNНЇОZ{Т─П5НЇОWPТ┤sqsqТ┬П>НЇОUлТ╘ПSТ╙НЇОTHТ─П%НЇОQТ zqТ⌡ПDНЇОO≥Т≤П0zqТ≥zqНЇОNТ─П5zqНЇОJЙП+НЇОG©sТXqsqsqzТGsН ОF;sqТXОEўwОF;qОEўwОF;qОEўwОF;qОEўwОF;qНОFЧyН┴ОF;sqsН*sqsqzsqt qsqsОEўwОF;qsqsОEўwОF;qsqsОEўwОF;qzqsqsqsН ОDMqН КОDЧyНdОDMОCюwОDMqОCюwОDMqНОDЧyН√ОDMОCюwОDMqОCюwОDMqН<ОDЧyН╣ОDMsqsН:▓sqsОCюwОDMqzqsqsОCюwОDMqsqsОCюwОDMqzqsqsНЇОAУqТ─НЇО>йТXН*t qНЇО=FН*t qzqНЇО;бН*zqt qzqzqНЇО8≈Т╙ПLuqТ╚НЇО7ТєПYНЇО5▐Т┴П/Т┼П1НЇО4Т─НЇО0yТXНЇО,АqТ╗ПVТ╘НЇО+]Т╡П'ТЁП6НЇО)ыТ╣ПLТІНЇО(UТ╡П4ТЁНЇО&яТ─П1НЇО#іТ⌡ПPТ° НЇО""Т─НґОйyqТлТмП2НґОFТ─П$НґОНyqПDНґО√y qП;НґО>y qПNНґОФy qТСТТП2НґОb Т─П&НґО yqНЇО ъТЄt~t~t~tqТ╣П0НЇО[ ТъПFТЮНЇО вТ─П<ЪNTVk(SYNTAX AND SEMANTICSІ÷336 3.2 The lexical structure of programs56 name ::= letter (letter | digit)...-- But not one of the reserved words in Table 3²2.57 literal ::= num ?( ( D|d | B|b ) ?num ) |-- INT literal, decimal if radix omitted or D, octal if B. |digit (digit |A|B|C|D|E|F) ... ( H|h ) ?num |-- INT literal in hex; must start with digit. |?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 literal.58 exponent ::= (E|e) ?(+ | ²) num-- Optionally signed decimal exponent.59 num ::= digit !..60 extendedChar ::= space | \ extension | anyCharNot'"Or\ 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 | ' | " | \Examplesm, x1, x59y, longNameWithSeveralWords: INT;n: INT~1+12D+2B3+2000B-- = 1+12+1024+1024 +1H+0FFH;-- +1+255r1: REAL~0.1+.1+1.0E²1-- = 0.1+0.1+0.1 +1E²1;-- +0.1a1: 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 І÷4, as part of thetreatment of type T.ЇA name56, not one of the reserved words in Table 3²2. Note that case is significant innames.ЇA reserved word, which is a string of uppercase letters that appears in the list of reservedwords in Table 3²2. A reserved word may not be used as a name, except in an ATOMliteral.ЇA punctuation symbol: any printing character not a letter or digit, and not part of one ofthe two-character sequences below. The legal punctuation symbols in programs are: ! @ # $ ~ * ² + = | ( ) { } [ ] _ ^ ; : ' " , . < > / The following ASCII characters are not legal punctuation symbols (and must notappear in a program except in an extendedChar60): % & \ ? Note that Cedar uses a variant of ASCII which includes the characters _ (instead of the underbar ) and ^(instead of the circumflex ╛ ). Note also that the character written ² here is the ASCII minus character, code55B, and not any of the various dash or typographer's minus characters with other codes, which are not in thestandard ASCII set.ЪН⌡Оf2zТGУ НGNНЇqНЇО_шsТXП&НЇО\╟wТ>szsТXqsqsqsН*qП2НЇО[,wТ>sТXqsqНЧОZТЧНО[,sqНuОZТЧгН<О[,sqНDОZТЧГН+О[,sqН┐ОZТЧгНJО[,sqsqsqsН*qzqП5sН ОY╗qsqsqНСОYpЧНШОY╗sqНSОYpЧГН:ОY╗sqН▓ОYpЧЧН░ОY╗sqНХОYpЧНОY╗sqН_ОYpЧГНFОY╗sqН·ОYpЧГН┘ОY╗sqsqsqН▀ОYpЧ Н╚ОY╗sqН ОYpЧгН йОY╗sqsqsН*qzqП(sН ОX$q sqsqН*zqП4wТ>sН ОV═qТX sН*qП7sН ОUqsqsqНєОTДЧЧН╒ОUsН*qzqП2sН ОS≤qsqsqН|ОS`ЧГНcОS≤sН*qsqsqvqzqzqzqsН ОRqН*zqНЇОP░wТ>sТXqsqНЄОPXЧГН⌡ОP░sqНСОPXЧ╔Н≤ОP░sqsqsqsqН*П&НЇОOwТ>sТXqsНЇОM┬wТ>sТXqsqsqНЇОLwТ>sТXqОKwwОLqОKwwОLqОKwwОLqsН*qsОKwwОLqsОKwwОLqsОKwwОLqsН ОJqsqН#ОIчЧгНЙОJsqНBОIчЧ#НeОJsqНmОIчЧ└НЯОJsqНIОIчЧ НRОJsqsqsqНPОIчЧoН©ОJsqНОIчЧГНЧОJsqsqsqНЭОIчЧгН цОJsqН!ОIчЧГН"ОJsqsqН*zqszТGqТXsqzqsqН ОH▓sqН#ОHZЧyН°ОH▓sqНТОHZЧГНшОH▓sqsqsqНыОHZЧcН<ОH▓sqН■ОHZЧГН{ОH▓sqsqsqsqН*zqsqzqsqsqsqНЇОD⌠yНЇОAhqП'zqНЇО?ДzqН*Н О>`Н* НЇО<эzq Н*Н О;XН*НЇО9тzqzТGqТXНЇО8Pzq sqНЇО6лzqНЇО3║Т√ПHТ≈yqНЇО2Т─П'Н°О/еНґТ╚О0wО/еqП!Т╛vqП$НґО.AТ─vqН°О+ИНґТ╣О,/wО+ИqТІП>НґО*eН°О( НґТ²ПCТ·НґО&┴ТЄ Т╣П9zНґО%qН°О"ґНґТ²П1Т·П(НґО!)Т─ПOНёОП;НёОТ© ТюzqП;НёО┐Т─П'ОиwО┐qНёОrНґОazТ²zТ·НCxО)Ч<НDЄОaНґО#Т■НОНqН(О√О#zТ∙П%zНґО|Т┤ПBТ┬П'НґО>Т─z jTVk(_І÷3.2 THE LEXICAL STRUCTURE OF PROGRAMS37ЇOne of the following two-character symbols (used in the grammar rules indicated):~=not equal22<=less than or equal22~=greater than or equal22~>not greater than22=>chooses8,÷17,÷30,÷31,÷33,÷35,÷52..subrange constructor25,÷51.1~~bind by name6,÷34ЪНЇОf2zТGУН*П!НG?qН°О_шНґТ─ПNН⌡О^WН*ТXО^²wН⌡О\сqН*О]wН⌡О[OqН*О[∙wН⌡ОYкqН*ОZwН⌡ОXGqН*ОX█wН⌡ОVцqН*ОW wН⌡ОU?qН*ОU┘wН⌡ОS╩qН*ОTw2TVk(fSYNTAX AND SEMANTICSІ÷338ABSALLANDANYARRAYATOMBASEBEGINBOOLBOOLEANBROADCASTCARDINALCEDARCHARCHARACTERCHECKEDCODECOMPUTEDCONSCONTINUEDECREASINGDEFINITIONSDEPENDENTDESCRIPTORDIRECTORYDOELSEENABLEENDENDCASEENDLOOPENTRYERROREXITEXITSEXPORTSFINISHEDFIRSTFORFORKFRAMEFREEFROMGOGOTOIFIMPORTSININLINEINTINTEGERINTERNALISTYPEJOINLASTLENGTHLISTLOCKSLONGLOOPLOOPHOLEMACHINEMAXMINMODMONITORMONITOREDNARROWNEWNILNOTNOTIFYNULLOFOPENORORDEREDOVERLAIDPACKEDPAINTEDPOINTERPORTPREDPRIVATEPROCPROCEDUREPROCESSPROGRAMPUBLICREADONLYRECORDREFREJECTRELATIVEREPEATRESTARTRESUMERETRYRETURNRETURNSSAFESELECTSEQUENCESHARESSIGNALSIZESTARTSTATESTOPSTRINGSUCCTEXTTHENTHROUGHTOTRANSFERTRASHTRUSTEDTYPEUNCHECKEDUNCOUNTEDUNTILUSINGWAITWHILEWITHZONETable 3²2: Reserved words and predefined namesThe 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 number of initial whitespace characters or comments. The whitespace characters are space, tab, and carriage return. A Tioga node boundary isalso treated as a whitespace character.A comment is one of:A sequence of characters beginning with --, not containing -- or a carriage return,and ending either with -- or with a carriage return.A Tioga node with the comment property.Note that whitespace and comments are not tokens, but may appear before or after any token; theyare token delimiters, and hence cannot appear in the middle of a token. Whitespace and commentsthus 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 ".Н⌡Оf2zТGУ НGNНЇqНЇО`3Чa█О_шЧaН О`3Ч ╔█О_шЧ ╔НҐО`3Ч х█О_шЧ хН$┘О`3Ч"█О_шЧ"Н(їО`3Ч╡█О_шЧ╡НЇО]їzНЇО\FНЇОZЕНЇОY└НЇОX#НЇОVбНЇОUaНЇОTНЇОR÷НЇОQ>НЇОOщНЇОN|НЇОMНЇОK╨НЇОJYНЇОHЬНЇОG≈НЇОF6НЇОDуНЇОCtНЇОB НЇО@╡ НЇО?QНЇО=П НЇО<▐НЇО;.НЇО9мНЇО8lНЇО7НЇО5╙НЇО4IНЇО2ХНЇО1┤НО]їНО\FНОZЕНОY└НОX#НОVбНОUaНОTНОR÷НОQ>НОOщНОN|НОMНОK╨НОJYНОHЬНОG≈НОF6НОDуНОCtНОBНО@╡НО?QНО=ПНО<▐НО;.НО9мНО8lНО7НО5╙НО4IНО2ХНО1┤Н'GО]їН'GО\FН'GОZЕН'GОY└Н'GОX#Н'GОVбН'GОUaН'GОTН'GОR÷Н'GОQ>Н'GОOщН'GОN|Н'GОMН'GОK╨Н'GОJYН'GОHЬН'GОG≈Н'GОF6Н'GОDуН'GОCtН'GОBН'GО@╡Н'GО?QН'GО=ПН'GО<▐Н'GО;.Н'GО9мН'GО8lН'GО7Н'GО5╙Н'GО4IН'GО2ХН'GО1┤Н5О]їН5О\FН5ОZЕН5ОY└Н5ОX#Н5ОVбН5ОUaН5ОTН5ОR÷Н5ОQ>Н5ОOщН5ОN|Н5ОMН5ОK╨Н5ОJYН5ОHЬН5ОG≈Н5ОF6Н5ОDуН5ОCtН5ОBН5О@╡Н5О?QН5О=ПН5О<▐Н5О;.Н5О9мН5О8lНЇО0ЫЧaО0&Чa█Н О0ЫЧО0&Ч█НО0ЫЧ хО0&Ч х█Н%ФО0ЫЧ"sО0&Ч"s█НоО,'yТXП)НЇО(ЭqТ╟П!Т╠П;НЇО'xТ│П#Т┌П>НЇО%Т Т─y qyqНґО#°Т╠П*Т╡П*НґО"Т─П#НґОюНёО╞Т·П.Т÷П$НёО+Т─П1НёОyq НЇООТ├Т┤ПHНЇОkТ█ПSТ▌НЇОГТ─П1НґО▐НґО7Т√zq zqП2Т≈НґО ЁТ─НґО/ПDTVk(║І÷3.2 THE LEXICAL STRUCTURE OF PROGRAMS39Both reserved words (Table 3²2) and most names with predefined meanings (Table 4²5) are madeup entirely of upper case letters. They should not be rebound by the program; in some but not allcases the compiler forbids their rebinding. All are at least three characters long except thefollowing:DO GO IF IN OF OR TO.A note on lists of items and their separators:Semi-colons are used to separate declarations, bindings and statements in a body10, and toseparate choices in a select statement29,÷32,÷34 or in an exits6, 17 or enable8,÷27.1. Commas are used to separate declarations in fields43,÷51 (i.e., in a proc domain or range, arecordTC or a unionTC), bindings in an application27 or an open7, choices in a selectexpression29,÷32,÷34 or in a unionTC52, expressions in a choice6,÷9,÷17,÷30,÷35,÷52, items in imports,exports or shares lists2,÷3. In general these sequences may be empty, and an extra separator at the end is harmless when thereis some kind of closing bracket, except when the sequence is bracketed with [].The braces which delimit a block6, interface body2, choices in an enable8, or MACHINE CODE body13may be replaced by BEGIN and END reserved words. BEGIN replaces "{" and END replaces "}". Ifone brace is replaced, its matching partner must also be replaced. The braces delimiting anenumTC54 may not be replaced by BEGIN and 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 DEFINITIONS LET r(~[ nm: INTERFACETYPE[[ nm, ...]] ] IN (imports | l=>r() IN?locks (imports | ) ?Ї(SHARES ns, ...)-- SHARES allows access to PRIVATE names in ns.~ ?Їaccess12 { ?open7 (d | b); !.. } .LET REC nm~open [ ?(l(~locks, ) (d | b), ... ] IN MKINTTYPE[nm] 3 implementation ::= nm : ?CEDAR LET r(~REC [(ne: ne) , ... , FRAME: TYPE nm , nm: FRAME,CONTROL: PROGRAM] ?safety ( PROGRAM ?drType42 |IN (imports | l=>r() IN MONITOR ?drType42 ( | locks) )( | ( LET LOCK:MONITORLOCK IN LET l(~(l IN LOCK) IN | ))(imports | ) LET b(~NEWPROGINSTANCE[block].UNCONS IN?(EXPORTS ne, ...) [ (ne~BINDDFROM[ne, b(] ), ... , FRAME~MKINTTYPE[block], ?Ї(SHARES ns, ...) nm~b( , CONTROL~b(.nm] where the block body is desugared:~ ?Їaccess12 block . [( | ( | l(~locks,)) (d | b), ... , nm: PROGRAM drType~{s; ...}]3.1imports ::= IMPORTS ( (niv : | ) nit ), ... --In 2, 3.l [( nit:nit), ...]=>r( IN LET (niv | nit)~ nit PLUS nit.BINDING4 safety ::= SAFE | UNSAFE --In 3, 41.5 locks ::= LOCKS e ?( USING nu: t)l ?( [nu : t] ) IN eЪНЇОf2zТGУН*П!НG?qНЇО_шТ─Т│ПOНЇО^WТ░П_НЇО\сТЖПXНЇО[O НґОXВzqТ─zqzqzqzqzqzqНЇОUлП.НґОSty qТ·Т÷П0ОS╨wОStqНґОQПТ─ОR6w ОQПqОR6wОQПq ОR6wОQПqНґОO≤yqТ╔П,ОOчwОO≤qТіНґОNТнТоОNZwОNq ОNZwОNqНґОL░ ОLжw ОL░qТ╞ОLжwОL░qТ╟ОLжwОL░qНґОKТ─ОKRwОKqНЇОHЄТ┬П@Т┴НЇОG0Т─ПMНЇОDТ┤ОDKwОDqОDKwОDqОDKwОDqzqzqОDKwНЇОB│qТ·Т÷zqzqzqzqНЇО@ЩТЙПUТКНЇО?yО?©wО?yqТ─zqzqНЇО:іsТXНЇО7{wТ>sТXqzqsqО6НxО7{qsqzqsqО6НxО7{qsqsqsqsН*qўTVk(%Н*`О7{yqТXУwО6Н{О7{qwqwtqwО6Н{О7{qwqtqwО6Н{О7{wqwqtqwО6Н{О7{wqwqutТGqТXН О5█П!wtqО5{О5█qwqwqwqwqН*uqwО5{О5█quqwО5{О5█qwО5{О5█qwqwqwqН О3÷wq wqwН*uqwqwqwqw qwНЇО2}Т>wТXqО1▌{О1ЬО2qwqwtqt qН*uqzqwО1▌{О2quqwО1▌{О2qwquТGqТXwqwqyqzwquН О0-wqwqwqwqwqwtqО/═{О0-qwН*qtqtq wО/═{О0-qН О.?wqО.┘}О.?qwqО.┘}О.?qwqwqwqwqН*uТGqТXwО-╡{О.?qwqwqzqwqwqwqwqwqwqtТGuqТXuqwО-╡{О.?qНЇО+}Т>w ТXqО*┤{О+qwtqtТGН*uqТXzquqwО*┤{О+qwО*┤{О+wqwquqtqwО*┤{О+qН*О)&wО(≥{О)&quqtqtqН О'8wqwqtqwqО'~}О'8qwН*uqwqwqyqzwquqП2Н О%ЄtТGqТXwqО%З}О%ЄqwqwqwН*wqwqwquqtqt uТGqТXuqzqНA`О%|ЧyНAыО%ЄyquqtqНGьО%|ЧyНHQО%ЄuqwqwН О$0qwqwqН*uqzquqwН:^О#ЬЧ.Н=▄О$0ququН О"╛wtqО"{О"╛qwН*qwО"{О"╛quqwО"{О"╛qzqwqwququqwНHоО"tЧ.НKЩО"╛qН О ЎwqwtqО 1{О ЎqwН*qwО 1{О ЎqzqtqzqwО 1{О ЎqП$Н ОпwqО}ОпqН*wqwqwqwqzqwqwqwqwqwОC{ОпqtqwqwqwqНЇОБ}w qtqwqwqОU{ОБqwqwqОU{ОБqwqwqtТGН*yqТXwqwОU{ОБqwОU{ОБwqwqzququqwОU{ОБqwqwОU{ОБwqwОU{ОБquqwОU{ОБquНЇОТ}Т>wТXqtqwqtqtТGНЇОp}Т>wТXqtqwqtqОЦ{ОpqwН*yqwqwОЦ{ОpqwqwquqwЪў┬TVk(■ьMODULESІ÷3.340ExamplesDIRECTORY -- For BufferImpl below.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,Buffer: TYPE;-- or it is exported.Buffer: DEFINITIONS ~Handle: TYPE~REF BufferObject;BufferObject: TYPE=Rope.ROPENew: PROC RETURNS[h: Handle];Get: PROC[h: Handle] RETURNS[BufferObject];Put: PROC[h: Handle, o: BufferObject];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: 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 secrets or 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.The others are the subject of this section. There are two kinds of modules: interface modules (written with DEFINITIONS) and implementationmodules (written with PROGRAM or MONITOR). They have the same header (except that interfaceshave no EXPORTS list); it defines the parameters and results of the module viewed as a proc (І÷3.3.1)and specifies the name nm of the module. The bodies (following the ~) are different. Table 3²3summarizes the structure of modules and their types; it omits a number of details which are givenin rules 1-3 and explained in the text.ExampleModuleModule typeResultResult typeDIRECTORY Rope, IO;Interface [Rope: TYPE Rope, IO: TYPE IO]InterfaceTYPE Match Match: DEFINITIONS~{...}module _[TYPE Match]DIRECTORY Match, Rope, IO;Implementation [Match: TYPE Match, ExportedMatch MatchImpl: PROGRAM module IO: TYPE IO, Rope: TYPE Rope, instance IMPORTS R: Rope, I: IO R: Rope, I: IO]_[Match] EXPORTS Match~{...}Table 3²3: Interface and implementation modulesЪН⌡Оf2tНF{НЇqНЇО_шrНЇО\╟tТGУН*qТXtТGx qТXН О[,tТGqТXtqН*tqН ОY╗tqtqН*П)Н ОX$tq Н ОV═tТGН*qТXНЇОSut qН ОQЯtqtq Н ОPm tqtН ОNИqtqtqН ОMetqtqН ОKАtqНЇОHІtqН*П&Н ОG2tqН*tТGqТXtqНyОEўtqН*Н ОD*tqН*П"Н ОBіtqН*tqtqtqНЇОA"Н*НЇО=ВТ─ПWНґО;÷xqП(x qНґО9GТяТрПAНґО7цТ─НґО5kТ≈ПCТ≤НґО3ГТ─П=НґО1▐ТьП8ТыНґО0Т─НЇО,ЮТєПDТ╔НЇО+\Т─П)НЇО(1Т▄Т█П7t qНЇО&ґТ═ Т║tqtqП4НЇО%)Т│tqП%Т┌П1НЇО#╔ТїxО#{О#╔qП;Т╗ НЇО!Ї Т∙П*Т√П-НЇО 3Т─П%НЇО┐ЧЙ█О+ЧЙН║О┐Ч█О+ЧН(їО┐Чо█О+ЧоН=vО┐ЧW█О+ЧWНCмО┐Чh█О+ЧhНЇОїrН║Н(їТXН=vНD НЇО|tqxТOqН║ТXН(їxqtqxqxqtqxqН=vНDtqxНЇОЬqxqt qН║Н(їzqtqxqНЇОмtqxqxТOqН║ ТXН(їxqtqxqН=vНDxНЇОIqxqtqН║Н(їxqtqxqxqtqxТOН=vqНЇОеТXtqxqxТOqТXxqН(їxqxТOqТXxqzqxqНЇОAtqxqНЇОЁЧЙО ЮЧЙ█Н║ОЁЧО ЮЧ█Н(їОЁЧоО ЮЧо█Н=vОЁЧ·О ЮЧ·█НDОЁЧ!О ЮЧ!█Н┼О АrП/ ·TVk(:І÷3.3MODULES41The ensuing sub-sections deal in turn with:І÷3.3.1: Modules as procedures, and the interface or instance values obtained by applyingthem.І÷3.3.2: How modules are applied.І÷3.3.3: Module parameters: the DIRECTORY and IMPORTS lists; USING clauses.І÷3.3.4: Interface module bodies and interfaces.І÷3.3.5: Implementation module bodies; the EXPORTS list.І÷3.3.6: SHARES and access12.The meanings of the other parts of a module header are discussed elsewhere:CEDAR in І÷3.4.4.MONITOR and LOCKS in І÷4.10.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 compiler's command line),Instances of interfaces, declared in the IMPORTS list. These arguments are also supplied bythe model (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, animplementation 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.For an implementation module, a binding whose values are instances: one interface instance for each interface it exports;one for the program instance, also called a global frame;one for the program proc derived from the module body (І÷3.3.2.1), calledCONTROL.This application cannot be written in the program, only in the model; it is described in І÷3.3.2.An interface (sometimes called an interface type) is a type, as the latter name suggests. This type is adeclaration (obtained from the declarations which constitute the module body), with an extendedcluster that includes all the bindings in the module body that don't use declared names (І÷3.3.4). Inthe example, the Buffer interface (obtained by applying the Buffer module to the arguments declaredin its DIRECTORY) has declarations for New, Get, and Put, and its cluster includes values for Handleand BufferObject.An interface instance is a value whose type is an interface; such values are the results ofinstantiating implementation modules. In the example, BufferImpl returns (exports) an instance ofBuffer.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 an implementation (PROGRAM or MONITOR) module body,just like any proc frame (І÷3.3.5). Normally code outside the module does not deal with the instancedirectly, but only with the exported interface instances. In the example, BufferImpl exports aprogram instance for the module and a CONTROL proc.ЪНЇОf2tН;СНG?qНЇО_шТ─УП(НґО]┐ТґrqrqТўНґО[ЪНґОYїТ─НґОWOtqtqtqНґОTВП0НґОR÷П+tqНґОPGtq ОP█}ОPGqНЇОMПKНґОJдtqНґОHltqtq НЇОDmrТXНЇОABqТ─П5НґО>Йr qТ²tqП&Т· tНґО=fТ─qНґО;rqТ≥Т tqП+НґО9┼Т─t|tП8qНЇО72ТП+ТП'НЇО5ў Ты tqТзtqНЇО4*tqТ─П<НЇО0ЪПAНґО.їrqНґО,OПDНёО*>П5НёО(-rqrqНёО&ТТП6НёО$≤tqНЇО"@Т─П]НЇОТ┌rqr qП8НЇО▒ ТґПHТўНЇО Т▀П&Т▄П8НЇО┴Т┤ xqТ┬xqП!НЇОТ≥tqxqxqxqП%Т xНЇО│qТ─xqНЇОVТВ rqП7ТЬНЇОрТІТЇx qП!НЇОNxqНЇО#Т└rqТ┘rqПBНЇО÷Т╞П5tqtqТ╟НЇОТ┌Т┐ПLНЇО ≈ТКП7ТЛ x q НЇОТ─tqЪ ╡TVk(eMODULESІ÷3.342In 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); hence 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 it returns (since its arguments need not be written explicitly); the implementation module which exports the interface;its instance (again, since its 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.In the example at the start of this section, BufferImpl is an implementation module with sevenparameters:Four interface parameters, declared in the DIRECTORY: Rope, CIFS, IO and Buffer.Three instance parameters, declared in the IMPORTS: Files (of type CIFS), IO (of type IO),and Rope (of type Rope). Since the instance parameters are declared in an inner scope, theinstance Rope is the one visible in the module body; the interface Rope is visible only in theheader. The same is true for IO, but both the interface CIFS and the instance Files arevisible in the body.When BufferImpl is compiled, the four interface parameters must be supplied, in the form of(compiled) interface modules named Rope, CIFS, IO and Buffer. When BufferImpl is instantiated(normally by loading it), the three instance parameters must be supplied, i.e. there must be otherinstantiated implementation modules which export the Rope, CIFS, and IO interfaces. Normallythere will be one of each, and the entire program will consist of eight modules: the interface modules Rope, CIFS, IO and Buffer;implementation modules normally named RopeImpl, CIFSImpl, IOImpl and BufferImpl, eachexporting an instance of the corresponding interfaceThe instantiated BufferImpl exports an instance of Buffer, which can then be used as a parameter bysome other module.3.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 interfaces) to yielddifferent 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 will yield different instances.These two stages are separated for several reasons:ЪН⌡Оf2tНF{НЇqНЇО_шТ─УНґО]┐ПYНґО[+П+НґОXсП)НґОV{ТюПKТаНґОTВТ─П$НЇОR÷П^НґОQНґОO≈ПOНґОNП6НґОL▐ПIНЇОKТ·Т÷ПPНЇОI┤Т│П&Т┌П;НЇОHТ─ПRНЇОDьТхТиx qП'НЇОCT НґО@ЭТ─П'tqxqxqxqxqНґО>єТ²Т·tqxq xqxq xqНґО= Т xqТ⌡xqПDНґО;°Т├xqП6xqТ┤НґО:Т╨Т╩ xqxqxqНґО8■Т─НЇО6<Тэx qПIТщНЇО4╦ ТкxqxqxqxqТлx qНЇО34ТєТ╔ПIНЇО1╟ТмП$ТнxqxqxqНЇО0,Т─ПLНґО-тxqxqxqxqНґО+| Т╘Т╙xqxqxqx qНґО)ЬТ─П+НЇО'═Т▐ x qТ░xqП*НЇО&Т─ НЇО"rТXНЇОРqТіТїПFНЇОnНґОТ▀Т▄tqП,НґО▓tqТ≤xq Т≥xqП4НґОТ©ТюПSНґО┼Т─tqНґО2Т┘tqtqП#Т├НґОўТ╘ПPТ╙НґО*ТґtqПOТўНґОіТ─П>Т│НґО"Т─П3НЇО ВП3VTVk(▄І÷3.3.2 APPLYING MODULES43All the type-checking of a module can be (and is) done in the first stage, by the compiler.The only type error possible in the second stage is 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.When there are multiple instances of the same module with the same interface parameters,they automatically get the same code.We've always done it that way.3.3.2.1 Initializing a program instanceThe statements in the body of an implementation module form the body of a proc called theprogram procedure. The function of this proc is to initialize an instance of the module. A programinstance PI may be uninitialized, because no code in the module is executed when the instance ismade. It is the job of the program proc PP( to initialize PI, perhaps using the PROGRAM argumentsif there are any. Until PP( has been called, PI is not in a good state. It would be better to supplythe PROGRAM arguments along with the imported instances, and call PP( as part of making PI, sothat PI is never accessible in its uninitialized state. But it isn't done that way; hence theprogrammer must ensure that PP( is called before any use is made of PI. To confuse things, PP( isnot an ordinary procedure but a PROGRAM, and it must be called using the START construct (seeІ÷4.4.1). Note that in addition to the statements of the module body, PP( also contains the type-specific initialization code for any variables or non-static values in the instance; e.g., if x: INT_3, thevalue 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 isunlikely to be right. It is unwise to rely on a start trap to initialize a monitor module; call PP(explicitly with START.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.The program proc is bound to the name CONTROL in the result of an implementation module if itstype is PROGRAM[] RETURNS[] (otherwise the proc Runtime.ReportStartFault is bound to CONTROL).This allows the modeller (and binder) to get access to PP so as to control the order in whichmodules are started.3.3.3 Parameters to modules: DIRECTORY and IMPORTSThe interface parameters of a module are declared in the DIRECTORY. An interface I has type TYPEn, where n is any one of the names given before DEFINITIONS in the header of the interface modulethat produced I. The INTERFACETYPE primitive in the desugaring takes a list of names and returns atype which implies TYPE n for each n in the list. The reason for allowing several names is to aidconversion of an interface from one name to another; both names can continue in use for a while.The use of these names provides a clumsy check that the proper interface is supplied as anargument. DIRECTORY n: TYPE and DIRECTORY n are both short for DIRECTORY n: TYPE n.An interface is a type which can only be used:ЪНЇОf2tТGУН5╪НG?qНґО_шТ⌠Т■ПFНґО^WТ─ПRНґО[ЪТ²П0Т·НґОZ{Т┘ПMТ├НґОXВТ─ПAНґОV÷Т▒Т▓ПAНґОUТ─П!НґОRцНЇОNдrТXНЇОK≥qТгПRТхНЇОJrТ≥ qПGТ НЇОH▒Т·xqП!Т÷П4НЇОG Т▄Т█xzqxqtq НЇОE┴Т≥Т xzqxqП5НЇОDТ·tqП7xzqТ÷xqНЇОB│ТЭxqП4ТЩП"НЇО@Щ Т⌠xzqТ■xqxzqНЇО?yТіtqП!ТїtqНЇО=УТ╟П=xzq Т╠ НЇОxqtqНЇО:МТ─xqxzqНЇО7бТ√ПRТ≈ НЇО6>ТуП"tqr qТжxzqНЇО4╨Т°П@Т² xzq НЇО36 Т─xqtqНЇО0rqТ┌xzqП"Т┐НЇО.┤Тн xzqП"ТоxzqНЇО-Т╣П'ТІП1xzНЇО+q Т─tqНЇО(TrqТ▀ПIТ▄НЇО&пТюП9xzqТаП&НЇО%LТ─П7НЇО"!Т▀Т▄tqП1НЇО ²Т╠tqtqxqТ╡tqНЇОТдП3xqТеНЇО∙Т─НЇО√rТX|r|НЇОkqТ▀П6tqxqТ▄ tНЇОГxqТ├xqП&t qП&НЇОcТ┬ xquqТ┴П@НЇОъТ╔tqТіxq xqП=НЇО[ Т▓Т⌠ПAНЇОвТшТэПSНЇО SТ─tqxqtqtqxqtqxqtqxqНЇО (П.Ъ°TVk(ЕMODULESІ÷3.344Before a dot (І÷4.14), to obtain a value from its 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] RETURNS [BOOL]~INLINE {IF Length[r1]~=Length[r2] THEN ... }A call of Rope.Compare in BufferImpl is perfectly all right, even though Rope.Length in BufferImplwould be an error.In 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(e.g., x~3) is just the value that the interface binds to the name (in this case, the value 3). This rulehas 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 I.x has the samemeaning (namely 3) whether I is the interface or the instance.Anomaly: Nmaes bound to inline procs in an interface do not appear in the interface binding, butonly in an instance. This somewhat duboius rule ensures that clients won't have to add to theirimports lists if a proc stops being an inline.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 (types andconstants) bound in its interface parameters, and does not need values for any names declared there (procs and interfacevariables). If an interface module does have IMPORTS, however, and there is more than one instance of any importedinterface around, then there is a restriction on the argument values. Suppose that Int1 imports Int2, and that a programmodule P imports Int1. Then Int1 may only import one instance of Int2, and if P also imports Int2, the principal instanceof 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=Int2V.3.3.4 Interface module bodiesThe body of an interface module I is a collection of bindings (e.g., x: INT~3) and declarations (e.g.,y: VAR INT or P: PROC[a: INT] RETURNS [REAL]). Restriction: Only certain things may follow the ~ in one of the bindings13:ЪН⌡Оf2tНF{НЇqНґО_шТьУПMТыНґО^WТ─П(НґО[ЪtqП8НЇОYїТ▌tqtqП*Т▐НЇОX#Т▌xОW√{ОX#qТ▐tqxqxНЇОV5qТ█x qxqtqxqТ▌xqНЇОT╠Т─xqТ│ tqП>НЇОS-Т┐П,tqП(Т└НЇОQ╘xqТ─xqНyОP%xТOtqxqТXxqtqtqtqtТGНыОN║qТXxqxqxqxqtТGНЇОMqТцxqТдx qП%x qx НЇОK≥qТ─НЇОIAТ░ xqxqxqП&Т▒tq НЇОGҐТ┼xqxqxqtqП,Т▀НЇОF9Т²П)tqТ·НЇОD╣Т╒ПGТёНЇОC1Т÷rqП;Т═НЇОAґТ╒ПHТёНЇО@)Т├xqП(Т┤П9НЇО>╔Т─НґОНЇОХТ░Т▒ПB{t {tНЇО╙Т┌{tТ┐{t{tП"{t {t {tНЇОlТ─{t{tП"{t{t {tНyО.tТG{t{t tt{t{t{tНyОПt{t{t{ttt{t{t{t{t{t{tНЇО╡Т─ {t{t{t{t{НЇОЁrТXНЇО┬qТ┤xqП#Т┬xqtqНЇО xqТ─tqtqxqtqxqtqtqtqНЇО ыr qП=О }О ыqЪTVk(`І÷3.3.4 INTERFACE MODULE BODIES45If it is an expression, it must be static (І÷3.9.1).If it is a block (providing the body of a proc), it must be INLINE (because there isn't anyplace to put the compiled code).It may not be CODE.The result of applying an interface module is an interface (І÷3.3.2), which is a type I obtained byapplying the primitive MKINTTYPE to the d's and b's of the body. This type is simply the declarationobtained by collecting the declarations in the body, with a cluster which is extended to include allthe bindings of the body. However, MKINTTYPE omits any inline proc bindings from the type'scluster, instead leaving the proc declarations in I. It puts an extra item BINDING in I's cluster withthe inline procs in it. When an instance Inst of I is imported, the binding actually imported is InstPLUS I.BINDING. This slightly dubious arrangement ensures that clients don't have to change importslists if a proc stops being inline. This policy is not extended to other items, however, even thoughthey might change from being bound in the interface to being interface variables.The interface returned by Red, Blue, Green: DEFINITIONS~...has the types TYPE Red, TYPE Blue, and TYPE Green.The types and expressions in declarations and bindings may refer to other names in the bindings asusual, but they may not refer to names introduced in the declaration, except that:Any declared name may be usedin the body of an INLINE, or after a "_" in a defaultTC55 in the fields43 of a transferTC41 which is the type of adecl in the interface's body.A declared (opaque) type may be used anywhere.For example, if an interface containsI: DEFINITIONS~x: INT~3;y: VAR INT;T: TYPE[ANY]then the following may also appear in the interface:xx: INT~x+1;P: PROC RETURNS[INT]~INLINE {RETURN[x+y]};Q: PROC [INT_y];V: TYPE~RECORD[f: REF T, g: U]but the following are illegal:xy: INT~y+1;U: TYPE~INT_y;W: TYPE~ARRAY [0..y] OF INT;The values of the bindings can be accessed directly by dot notation in any scope in which theinterface value is accessible. Thus if the value of the previous interface module is bound to J, e.g.,because J: TYPE I appeared in the DIRECTORY, then J.x is equal to 3. The declarations cannot beaccessed directly (J.y is an error). 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:A transfer type; this is just like a declaration of a transfer parameter to an ordinary proc,except that it is readonly. TYPE[ANY] or TYPE[e]; the type being declared is an opaque type or exported type, discussedin І÷4.3.4. The expression e must be static. TYPE[ANY] or TYPE[e] is not allowed in anordinary declaration; except in an interface, a type name must be bound to a type valuewhen it is introduced.НЇОf2tТGУН1НG?qНґО_шТ─П2НґО]┐Т·П"Т÷tqНґО[ЪТ─НґОYї tqНЇОV|Т║ПRТ╒xqНЇОTЬТ├ Т┤uqПDНЇОStТ≈Т≤ПYНЇОQПТхТиuqП/НЇОPlТ÷Т═xquqxqНЇОNХТ√П&xqxqП+Т≈xНЇОMduqТ▀xquqПMТ▄НЇОKЮТ≥П=Т П"НЇОJ\Т─ПMНЇОG1Н ОEґxТOqТXt qНЇОD)Т─ tqxtqxqtqxqНЇО@ЧТ┬П*Т┴П5НЇО?zТ─ rqП;НґО="НёО;tqНёО9Т▄ Т█ О9F}О9q О9F}О9qО9F}О9qНёО7|Т─НґО5$П.НЇО2лП%НЇО1HxqТXt qН О/дxqtqН О.@xqtТGqН О,╪xqТXtqtqНЇО+8Т─П0Н О)ЄxqТXtqxqН О(0xqtqtqtqtqtqxqxqН О&╛xqtqtqxqН О%(xqtqtqxqtТGxqТXxqxqНЇО#єТ─Н О" xqТXtqxqН О °xqtqtqxН ОqtqtqxqtТGqНЇОМТ╪П0ТҐП*НЇОiТ√П'Т≈П.xqНЇОЕТ╒xqТёtqxqtqxqxqП*НЇОaТ─ xqНЇО6Т≤П$Т≥П<НЇО╡Т─П3НґОZТ÷П/Т═П-НґОжТ─НґО~tqtqТ▌tqxqП!rТ▐qrq НґО ЗТяxqtqtqtqxqТрНґО vТ╙П6Т╚НґОРТ─ЪTVk(ЭMODULESІ÷3.346VAR T, or READONLY T for any type T except TYPE; this is an interface variable; discussedin І÷3.3.4.1 below. ЇIn an ordinary declaration in a block you can't write VAR T, but mustwrite simply T; you can also write simply T here, but this is not recommendedAn 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 (І÷3.3.6). This can be useful if the name is used in a type constructor or inline procin the interface, but its value should not be accessible to the client.3.3.4.1 Interface variablesAn interface variable v gives clients of an interface direct access to a variable in a program module,namely the variable which is exported to v. This is the only kind of variable parameter in currentCedar.Ї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 sooner.Performance: An interface variable can be read and (if not READONLY) set directly, which issignificantly faster than 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. If you use a private interface variable and inline Get and Set procs, youpay nothing in performance, but retain the option of changing the proc definitions later.ЇYou can get direct access to all the variables of a module by using a POINTER TO FRAME type(І÷4.5.3).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., the frame of PP() are retained after the proc returns; in fact, forever (unless Runtime.Unnew isused to free the frame). Procs local to the block can access these values in the usual way, and valuesof exported names can also be accessed through interfaces, as explained below; see І÷3.3.2.1.As with any proc (І÷3.5.1), the frame of PP( includes the parameters and results from Imp's drType42as well as the names introduced in the block's d's and b's. It also includes an additional item:Imp: PROGRAM T~PP(where Imp is the name of the module and T is its drType.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:Н⌡Оf2tНF{НЇqНґО_шtqТ∙Уxqtqxq xqtqrq НґО^WТ⌡ПHТ°tqxq НґО\сТ─xqxqП"НЇОY╗Т÷xqxqxqxqТ═НЇОX$Т≤xqxqxqТ≥ xqП7НЇОV═Т─П>Т│П&НЇОUТ─НЇОQЯТ┬tqТ┴П2tНЇОPmqТ▌ПIТ▐НЇОNИТ─ПEНЇОJЙrТXНЇОG©qТ▀xqТ▄П1НЇОF;Т²П#xqТ·П2НЇОDЇНЇОA▄Т√П#xqtqxqТ≈П1НЇО@Т│Т┌П_НЇО>└НЇО;YrqТъП4ТЮП!НЇО9у Т≥ Т ПSНЇО8QТ─НЇО5&r qТэП/tqТщНЇО3╒Т≥xqТ xqП?НЇО2Т▓П^Т⌠НЇО0 Т╔ ТіПSНЇО/Т√Т≈П;xqxq НЇО-▓Т─ПVНЇО*gТ╞Т╟П?tqtqtqНЇО(Ц НЇО$ДrТXНЇО!╧qТ≤Т≥xqП6НЇО 5Т╛ПDxzqТґtНЇО╠qТ█П2xzqТ▌tНЇО-qТ∙tqxzqТ√П)tqНЇО╘Т≤ПZТ≥НЇО%Т┐П+Т└П6НЇО║Т xzqП)Т⌡xqНЇОТ│П[Т┌НЇО≥Т─П[НЇОnТ┐П'xzqТ└xqОЄ}НЇОЙqТ─П^НyОfxqТXtqxqxzНЇО БqТ─xqxqНЇО ЇТфxqП,ТгП!НЇО 3ТЁxq ТЄ xqxqxqxqНЇО╞Т─ xqxqЪ@TVk(уІ÷3.3.5 IMPLEMENTATION MODULE BODIES47If n: T is in Ex and n: PUBLIC T~x is in the body of Imp, then n~x is in ExI. This is aslightly peculiar kind of binding; as in an ordinary binding, x must be coerceable to T(І÷4.13). Note that n must have 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 is in ExI.UNBOUND is a special value with the following properties:For a proc P, it causes a Runtime.UnboundProcedure signal on any application of P.For a variable v, it causes a Runtime.PointerFault error on any reference to v.For a type T, it causes no problem.If 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 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 CONTROL: PROGRAM[] RETURNS [], whose value is the program proc PP( if thathas no arguments, and otherwise Runtime.ReportStartFault.ЇOne item for the type of the module's global frame, namely FRAME~TYPE Imp. ЇOne item for Imp itself, namely Imp: FRAME. The value of this item is the programinstance, 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 instances,the program proc, the global frame type, and the program instance. ЇYou can pass FRAME as an argument to a DIRECTORY parameter I: TYPE Imp; like an interface; Iprovides access to constants bound in the module, and allows you to declare an IMPORTS parameterwhose argument will be a program instance of the module. From I you can also obtain a first-classCedar type POINTER TO FRAME[I]; see І÷4.3.5. I's cluster includes a coercion from I to POINTER TOFRAME[I], and the proc COPYIMPLINST (applied by the funnyAppl NEW), which is the same as theproc of the same name in cluster of POINTER TO FRAME[I].ЇYou can import Imp into another module (by writing DIRECTORY Imp ... IMPORTS ImpInst: Imp ...),and obtain access to all the variables and procs of the program instance.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.Access to a name is declared by writing PUBLIC or PRIVATE right after the colon in a declaration ofa name:x: PUBLIC TIn the Cedar syntax these colons occur in the declarations11 and bindings13 in bodies10, fields43,÷51,and interface modules2, and in the tag53 of a unionTC. You can set a default access for all thenames in a module2, 3 or record50 by writing PUBLIC or PRIVATE just before the { or RECORD; this isoverridden by an explicit PUBLIC or PRIVATE inside. By default, an interface is PUBLIC and animplementation is PRIVATE. ЪНЇОf2tТGУН-НG?qНґО_шТїxqxqxqxqtqxqxq Т╗xqxqxqxq НґО^WТЎП6xqТ©xНґО\сqТ─ xq tqНґОZ{ТаxqxqxqТбxquqxqНґОXВuqТ─П2НёОVФ xq xqxqНёОTуxq xqxqНёОRд xqНґОPlТ┬xqxqxqxqxqxqП'Т┴НґОNХТ─НЇОKҐrqПFТ│НЇОJ9Т─П"НЇОGxqНґОDІТ╘П!Т╙xqxqxqxqxqНґОC2Т─xqxОB╔{ОC2qtqНґО@зТ╒tqtqТёtqП%xzqНґО?VТ─xqНґО<ЧПs); ...) } IN ( ( body enable ) BUT { (n((, ... => s ); ... } )--In 3, 13, 15.-- But n(( is not visible in s. 7 open ::= OPEN ( n ~~ e | e ), !.. ;( LET n~lopen IN e.DEREF | --The IN before !.. is a separator.In 2, 5, 17. ЇThe ~~ may be written as :. LET BINDP[D(e.DEREF).P, OPENPROCS[(D(e.DEREF)).P, l IN e.DEREF] ] ) IN !.. IN 8 enable::=ENABLE ( enChoice |BUT ( { enChoice } | {enChoice; ...}); { enChoice; ... } )In 5, 17. 9 enChoice ::=( e, !.. | ANY ) => s( e | ANY ), ... => { s; REJECT; EXITSIn 7, 27.1. Retry(=>GOTO Retry((14; Cont(=>GOTO Cont((14 } 10 body ::= (d | b); !.. ; s; ... | s; !..LET NEWFRAME[ REC [(d | b), ...] ].UNCONS IN { s; ...} In 5, 17. ExamplesCHECKED { -- 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["X"];-- Use a binding if a name's value is fixed.x: INT_7; -- Better to initialize declared names.{OPEN b~~buffer;-- A statement may be a nested block. ENABLE {-- Multiple enable choices must be in {}.Files.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:ЪН⌡Оf2tНF{НЇqНЇО_шТ─УtqxqНґО]┐xqНґО[+tqxqНґОXсtqxqНЇОV{Т²rqП1Т·П$xqНЇОTВtqТ─НyОSsxqТXtqtqxqxqxqНЇОQОТкxqxqtqТлxqxqxqНЇОPk Т▐xqtqtqxqtqТ░НЇОNГxqТ─xqtqНЇОK╪Т⌡Т°tqП9НЇОJ8Т┘П#tqТ├НЇОHЄТ─НЇОCАwТXЪTVk(╗НwОCАpqТXУpНЇО@ІrТ>qsТXqsqtsqstsqstqsН О?2qsqsqsН*qН*О>ЗЧкН,сО?2susqvsqsususqН О=ўtsqsqsqsqsrТ>Н*sТXusН,+О=vЧyН,єО=ўН,ЭО=vЧyН-uО=ўqН-мО=vЧюН0█О=ўsqН0ЕО=vЧхН4ґО=ўsН5О=vЧyН5~О=ўusqvsqsqsqsqsНDnО=vЧyН ОqТXtsqsqsqsqsН*qsusqsxО:;yО:хsutТGqsusТXqstТGutН О8зП)Н*usТXususvsН2О8╒ЧyН2│О8зqsusН7-О8╒ЧyН7іО8зustТGН*О7VsТXtТGsТXusН2╗О7ЧyН3!О7VvqsuqsН9ЖО7ЧyН:oО7VusxsusqsusqsutТGqtuНЇО5рrТ>qtsТXqs qН*usqsqН.yО5 ЧvН3ОО5рsqsН О4NП*qsqsН*qН.─О4ЧvН3ЖО4NsqsqН О3tТGНЇО1▄rТ>qТXsqsqstsqsН*qsqsqstsqsqsqststН О0ТGН*svstsvО0NrО0sТXvstТGsvО0NrО0sТXНЇО.└rТ>qТXsqsqsqsqsqsqtТGsТXqН*usususqsqsqsqsususqsqsН О-FtТGНЇО)GzНЇО&tsТXН* tsН О$≤tsН*tsН О#tstsН*П$Н О!░П+Н*П,Н О tsН*П'НyО┬ts Н*П%НyОtsН*П)НыО─Н*tsН:ОЭН:ОxtsН*П'НыОТts tsН*tstsНyОptsqsН*П(Н ОЛqН*sП'Н ОhtН*stszsНyОДqsН*{s{ sНyО`qsН*ts НЇО5Т▄П)Т█П9НЇО ╠Т─ПUрTVk(■ь÷І÷3.4 BLOCKS, OPEN AND ENABLE49attributes: CHECKED, UNCHECKED and TRUSTED are treated in І÷3.4.4 on safety.open7: a combination of sugar for LET and call by name; see І÷3.4.2.enable8: 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).The statements in a block are evaluated in the order they are written. The initialization expressionsin the d's and b's are also evaluated in the order they are written; this may be important if theyhave side effects, although that should be avoided.3.4.1 Scope of names and initializationThe names introduced in the block body's d's and b's (i.e., appearing before a : or ~) are known inthe body with the values supplied by the d's and b's, except in inner scopes where they arereintroduced; they are not known elsewhere in the block. The frame of the block is a binding witha value for each such 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.Anomaly: 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 d's and b's, but before any following ones.This means that n.VALUEOF is trash in all the d's and b's before its binding. Symmetrically, if erefers to a name introduced in a following decl or non-static binding, it will get a trash value.Compiling with the "u" switch will yield a warning in this case. Note that only attempts to obtainthe value of n get trash; n may appear anywhere in a l-expression, and all will be well as long asthe l-expression is not applied 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 before anything in the block is executed (this is done by the NEWFRAME proc inthe desugaring). Anomaly: However, the INIT proc is executed (to set a REF or transfer value to NIL), and anyinitialization specified by a defaultTC55 in T is done at the same time that a non-static bindingwould be evaluated. As with a binding, n.VALUEOF is trash before this time. Furthermore, any(unwise) assignment to n before this time will be overridden by the defaultTC.Caution: The failure to initialize RC variables is a safety loophole, since the trash can be picked upand used as an address.Style: 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.НЇОf2tТGУН1≥НG?sНґО_ш Т─tststsП"НґО]┐О]иrО]┐susНґО[+О[qrО[+sПAНґОXсts tsП1НЇОU╗П7tstsНЇОR}Т▐Т░ПLНЇОPЫТєПGТ╔НЇОOuТ─П/НЇОKvzТXП"НЇОHKsТ└П)Т┘П7НЇОFгТсП<ТтНЇОECТ▐Т░П#zsНЇОC©Т─НЇО@зtТ┌ПE|tТ┐П#НЇО?°Т√П.|t |tП%Т≈НЇО>^Т─НЇО;3zsТ√П!{s{s{sТ≈ {s{sНЇО9╞Т┼{sПYТ▀НЇО8+ТЇ{susПG{НЇО6їsТЎТ©ПVНЇО5#Т≈П<Т≤НЇО3÷Т≈ {s{sxsТ≤НЇО2Т─xsП"{sНЇО.ПТ╔П"Ті{s{sus{s{sНЇО-l Т∙П)Т√usНЇО+ХТ─ НЇО(ҐzsТй uststsТкНЇО'9 Т╧Т╨ О'rО'9s{sП3НЇО%╣ТмП"{susТнП,НЇО$1Т─{sП6НЇО!zsТ┴П3Т┼П+НЇО┌Т─НЇОWzsП1Т│П/НЇОсТяТрПAНЇОOТ Т⌡П;НЇОкТ─НЇО═Т╨ПOТ╩НЇОТДТЕ zsП*ОbrОs НЇО≤Т─П-{sП*НґО@{sП2НґОХТ▄П3Т█{sП!НґОdЪ .TVk(іBLOCKS, OPEN AND ENABLEІ÷3.450In the checked language both these dangling references are impossible: the @ operator, beingunsafe, is forbidden, and ASSIGN for proc values gives an error unless the proc is local to a programinstance (which has a retained frame). Caution: An unchecked program can get into trouble with dangling references to frames, 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 the variables bound to its names. It is goodstyle to use blocks freely to 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 De does not include DEREFERENCE or UNWRAP;e^.DEREF if it includes DEREFERENCE;e.UNWRAP.DEREF if it includes UNWRAP. In other words, a reference value is dereferenced and a single-component record or bindingreplaced by the component, repeatedly if necessary, to obtain a non-reference value. In an open,e.DEREF must be a record, interface or instance.The second, nameless, form of open gives an expression without binding it to a name: { OPEN e;...}; e.DEREF 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 bound to the field values (or variables, for a VAR record). An application returns a binding, though the call-by-name feature makes it unwise to usean application in an open.An interface or instance value is a binding (І÷3.4.2). The nameless open converts b into another binding bp in which each value is a lopen proc (seeabove), and introduces bp's names in the block with a LET. Thus in the programR: TYPE~RECORD [a: INT_3, b: REAL_3.4]; r: R; { OPEN r; ...}the names a and b are known in the body of the block, and have exactly the same meaning as r.aand r.b.Style: Nameless open should be used with discretion, with the smallest practicable scope, and onlyif the value being opened is very familiar, or heavily used, or both. Nameless open can cause greatconfusion, since it is not obvious from the text of the program where to find the bindings for thenames it makes known. It should never be used when evaluation of e has a side-effect.The scope of an open is all the rest of the block, including any enable and any EXITS. A singleopen may have several bindings or expressions. These are applied sequentially, so that the namesbound by earlier ones are known to the later ones as well as to the rest of the block.ЪН⌡Оf2tТGУНF{НЇsНЇО_шТуП!zsП&НЇО^WТ┘usТ├П,НЇО\сТ─НЇОY╗zsПXНЇОV}z sТ╡П4ТЁНЇОTЫТ√ tsПKТ≈НЇОSuТ─П2НЇОOvzТX}НЇОLKsТ┐П#{s{s{sxОKЎyОLKsus{susНЇОJ]xsТ▀us{susП'{s{sТ▄{sНЇОHыТ▐{susТ░П<НЇОGUТ─ПB{susНґОDЩ{sv{su susНґОB╔{susu sНґО@M{usususНЇО="ТИТЙП9НЇО;·Т╛ТґПFНЇО:{susТ─П)НЇО6ОТ║ПFТ╒ ts{sНЇО5kТ─{sus{sНґО3Т█П7usТ▌НґО1▐Т─ПOus НґО/7ТёП7ТєНґО-ЁТ─НґО+[П7НЇО)Т╨{s{sТ╩xО(vyО)s НЇО'Т─{susНyО%▒{sТXtstТGs{sТXts{sts{s{sНyО$ ts{sНЇО"┴Т≤{s{sТ≥П={НЇО!sТ─{sНЇОзzsТ∙ПSТ√НЇОVТ▐П[Т░НЇОр Т Т⌡ПRНЇОNТ─П<{sНЇО#ТґТўПDts НЇО÷ТіПVТїНЇОТ─ПQЪ$TVk(≥І÷3.4.3 ENABLE AND EXITS513.4.3 ENABLE and EXITSThe ENABLE and EXITS constructs are two forms of sugar for exception handling (І÷2.2.4). ENABLEcatches signals and errors raised in the body (but not the open, enable, or exits). EXITS catchesGOTOs in the body or enable (but not the open or exits). Both are in the scope of the open, if any.Neither is in the scope of any names introduced in the body.3.4.3.1 ENABLEAn enable has a chance to catch any signal or error raised in the block (and not caught at a deeperlevel). A nearly identical construct can appear in an application26; the following explanation coversboth cases. Each enable choice (enChoice9) has a list of expressions with exception values, Їor ANY, before the=>. If ANY appears, it must be the last enChoice. 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 cases16:A RETURN is not allowed in an enChoice.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'sd's or b's.Ї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 d's or b's.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 e appears before the =>, then within the enChoice statement the names inDe.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.Note that an error is caught by an enChoice with a matching exception value, not by one with amatching name. Normally an error E will be declared in some interface, its value will be suppliedby a binding of the form E: PUBLIC ERROR ... ~ CODE, and both the signaller and the enChoice willrefer to this value by the name E. In this case, it is natural to think of the binding as being byname. However, it is possible to have a different name for this exception value, e.g. by writing E1:ERROR ... ~ E. It is also possible to bind some other exception value to E in a scope which includessome enChoice examined when the signal is raised. Thus in the silly programE: ERROR~CODE;F: ERROR~E;{ENABLE E=>{--Handler 1--...};E: ERROR~CODE;{ENABLE E=>{--Handler 2--...};IF switch THEN ERROR F ELSE ERROR E;if switch is true handler 1 will be used, and if it is false handler 2 will be used.НЇОf2tТGУН6²НG?sНЇО_шzТX}z}НЇО\╟sТ²tstsП&Т·tНЇО[,sТ╨П9Т╩tsНЇОY╗tsТ▀ПPТ▄ НЇОX$Т─П5НЇОT%zТX}НЇОPЗsТ┬Т┴ПJНЇОOvТ√П:ОO╪rОOvsТ≈НЇОMРТ─НЇОJгТ▐ОK rОJгsП*Т░tsНЇОICТ■tsТ∙П<НЇОG©Т⌡tsП!Т°П8НЇОF;Т─НґОCЦТеtsП2ТфНґОB_ Т■ПFТ∙ НґО@шТ─НґО>┐ТмtsП6ТнtsНґО<ЪТ─О=ErО<ЪsНёО:НtsНёО8щТЇtsТ╦П$НёО7YТ┐ПIТ└НёО5уТ╔ТіtstsНёО4QТ─НёО2@ТцtsПFНёО0╪Т─П/tsНёО.Яt~t~tП(О/7~О.ЯtНґО,≥stsП-НґО*AП'tsНЇО'Т╔{sПGНЇО%▓v{susТП@Т НЇО$Т─tsП.tsНЇО ЦТёП'ТєzsНЇО_Т°zs{sП(Т²НЇОшТ─{ststsТ│tsП.НЇОWТ╚Т╛ {sПAНЇОсТ▒Т▓П<{sНЇОOtsТ└{sП"Т┘{sНЇОкТ─ПGН ОG{sТXtstН Оц{sts{sН О?ts{szsНyО╩{ststНyО7sts{szsНыОЁts{ststs{ТOtТGsТX{НЇО /sТ─{sПKЪЮTVk(кBLOCKS, OPEN AND ENABLEІ÷3.452FinalizationYou 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 an enChoice which catches the ERROR UNWIND. Theprogrammer can write any cleanup actions he likes in this statement. Caution: If the finalization raises another ERROR which it does not catch, it will itself be stopped,with very confusing consequences. It isn't very useful to know exactly what happens then: avoidthis situation.Anomaly: In fact, things are a bit more complicated. When a signal or error is propagated, theenChoice statement is called as a proc from the SIGNAL or ERROR which raises the exception. Whencontrol leaves the statement by a GOTO (including EXIT, CONTINUE, RETRY or LOOP, but notRETURN, which is forbidden in an enChoice), the finalization is done. This means that the enChoicestatement is executed before any finalization. This is useful for signals, which often resume. In somecases, however, notably if finalization would release monitor locks, this can cause trouble. Avoid theproblem by exiting from the enChoice immediately with a GOTO.Caution: An enChoice 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 enChoices which saw ex1 will see ex2. This is because the enChoice statement for ex1was called as a proc. Unless ex2 is a signal which is resumed, the enChoice which caught ex1 willbe finalized 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.SignalsConceptually, a signal is quite different from an error; in fact, it is very much like an ordinary proccall. The only differences are:The proc to be called is an enChoice which is found exactly as though the signal were anerror. The effect of this is that SIGNAL P[args] binds the proc name P to the proc bodydynamically, by searching up the call stack for a binding of P. This is just the way Lispbinds free variables, except that a binding for P can only be found in an enChoice, not inthe frame of a proc.Actually this is not quite right. Like an error handler, the signal proc is not found by matching names, but bymatching exception values. This point is discussed in detail above.The enChoice can be terminated by a GOTO out of its body, unlike an ordinary proc. TheGOTO exception is treated exactly like a GOTO out of an enChoice for an error; it causes allthe intervening frames to be finalized.The implementation, however, treats errors and signals in a very similar way; the only difference isthat you cannot resume an error (return from the enChoice). In fact, you can invoke a signal withERROR, which prevents it from being resumed; avoid this feature. In the future, however, thedistinction between signals and errors will be reflected more clearly in the implementation. Anomaly: The desugaring gives no explanation of how RESUME works, since it does not turn theenChoice for a signal into a proc at all. This is a defect.Н⌡Оf2tТGУНF{НЇsНЇО_шzНЇО\╟sТєtsТ╔{sНЇО[,ТЬП/ТЫП"НЇОY╗Т▌{sПQНЇОX$ТъtsТЮzsП$НЇОV═ТєПAtstsНЇОU Т─П;НЇОQЯzsТ²Т·tsП4НЇОPmТ╞П&Т╟П5НЇОNИТ─ НЇОKЎzsТ╩П1Т╪П%НЇОJ:Т┌ Т┐tstsП!НЇОHІТшtstsТэtststsНЇОG2tsТ┐П$Т└П7НЇОEўТ├Т┤ zsПJНЇОD*Т└Т┘ПOНЇОBіТ─П1tsНЇО?{zsТ│П'{sП1НЇО=ВТіП2{sТїНЇО 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.Anomaly: A GOTO skips any UNWIND enChoices that intervene between the GOTO and its matchingEXITS. This is the only way to escape from a block without executing the UNWIND. You can avoidthis anomaly by not nesting UNWIND enChoices within blocks that have EXITS.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:as 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 (except ERROR, which is automatically safe). Thedefaults are provided to make it convenient to:ЪНЇОf2tТGУН6²НG?sНЇО_шzТX}НЇО\╟sТ│tstsП5НЇО[,Т Т⌡ПGНЇОY╗zsТ╣П7tsТІНЇОX$Т│Т┌ПVНЇОV═tsТ─П'ts НЇОSuzsТ⌡П$Т°П2НЇОQЯТ│П){sТ┌{sНЇОPmНЇОMBТ├Т┤ts{sП8НЇОKЎ Т█Т▌{sПT{НЇОJ:sТ─ПTНЇОGzsТ▀ts tsП&tsТ▄НЇОE▀tsТ√ПCtsТ≈ НЇОDТ─tsП#tsНЇО@zТXНЇО<щsТ╗tsП"Т╘П;НЇО;Y Т─П!Т│П:НЇО9уТ╔ТіПQНЇО8QТ─ПUНЇО5&ПYНґО2нНґО0vП8НЇО.П>НЇО*СП[НґО(⌡tsТП9ТНґО'Т─П7НґО$©tsП;НґО"gtsТ© ТюПDНґО ЦТщТчП3НґО_ Т─tsНЇО4П+НґОэПPНґО└Т│tsПRНґО Т▓П$Т⌠ts tsНґО|Т─ПLНґО$ Т╒П6ТёНґО═Т┬ts ts Т┴П#НґОТ─П0НЇОдТ╘П3tststsТ╙НЇО@ТЁtstsТЄtsП#НЇО ╪Т─П'Ъ·TVk(pBLOCKS, OPEN AND ENABLEІ÷3.454write new programs in the safe language;continue to use old, unsafe programs without massive editing. An unsafe proc value never has a safe type, and hence cannot be bound to a name declared with asafe type. This applies to enable choices for signals as well as to procs. In both cases, the body mustbe checked or trusted if the type is safe. ERRORs are treated differently, however, because of theview that an ERROR is a value returned from an application, unlike a signal which calls theenChoice expression. Hence the enChoice for an ERROR is treated just like any statement in itsenclosing 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.APPLY of a descriptor (because it involves dereferencing a pointer);a computed sequence;a record containing a computed sequence;a base pointer.APPLY for process and port types (JOIN and port calls).withSelect34.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.LOOPHOLE which produces a RC value (І÷4.5.1).3.5 Declaration and binding11 declaration ::= n, !.. : ?access12 varTC40( n: varTC ), ...In 2, 10, 43. VAR, READONLY only for interface var.12 access ::= PUBLIC | PRIVATEIn 2, 3, 11, 13, 50, 51, 53.13 binding ::= n, !.. : ?access12 t ~ (n, ... ~LET x( : t ~ ( e | e |t2 -- if t=TYPE | t2 -- Same as e except for conflicting syntax. |CODE | NEWEXCEPTIONCODE[] --tgSIGNAL or ERROR |?INLINE ?(ENTRY | INTERNAL) block6 | l [d(: t.DOMAIN] IN LET r(~NEWFRAME[t.RANGE].UNCONS IN (LET r( IN {t.DOMAIN~d(; block; RETURN} BUT {Return(((=>r(}) |╧╦ ?TRUSTED MACHINE CODE {(e, ...); ...} MACHINECODE[(BYTESTOINSTRUCTION[e, ...]), ...])) IN x( -- e is evaluated only once.In 2, 10. ЇThe ~ may be written as =. Block or MACHINE CODE only for proc types. ЇENTRY and INTERNAL can also be before t.Н⌡Оf2tТGУНF{НЇsНґО_шТ─П#НґО]┐П>НЇОZXТ▀ПFТ▄НЇОXтТ┌Т┐П]НЇОWPТ╗ Т╘tsП2НЇОUлТшts ТэП5zsНЇОTHТ╧П'tsП*НЇОRдТ─П=ts НЇОO≥П)НґОMAt stsНґОJИtsП2НґОH▒usНёОF─П;НёОDoНёОB^П(НёО@MНґО=УustsНґО;² О;ЦrО;²sНґО9EtsНґО6МusНёО4эПMНёО2кНґО0stsП%НЇО+═qТXНЇО(urТ>qt sТXqsqsqsО(╩rО(usО(╩rН*О(uqsqsqsqsqН О'7tТG~t~tНЇО%ЁrТ>qТXstsqstН О$uТGНЇО"ЯrТ>qtqТXsqsqsО#7rО"ЯsqН*qsqsusvsqsqsН О!mqН*sqsqН ОИsО\rОИstТG~sТXqsН*qН*╦О╠ЧyН+1О\rОИstТGП)sТXqН ОШt~Т5qsТXН*ustvtТG qН ОwtsТXqtsqstq~Т5tТGsОҐrОwsТXqН*sxsvsqsusususvsusqsususН*ОСtТGutsН,мО╩ЧyН-FОСusТXvsususvsqstsН*ОoutТGsvsvsН8яО7ЧyН9JОoТXqН ОКsqtstТGsТXqsqsqsН*u squsqsqsqsqsН ОgqН*qsusvstТGН О)П&Н О╔~t~sТXtТGН О!s~t~tЪПTVk( І÷3.5DECLARATION AND BINDING55ExamplesHistValue: TYPE[ANY];-- Interface: An exported type.Histogram: TYPE~REF HistValue;-- A type binding.baseHist: READONLY Histogram;-- An exported variable .AddHists: PROC[x, y: Histogram] -- An exported proc.RETURNS [Histogram];LabelValue: PRIVATE TYPE~RECORD[-- PRIVATE only for secret first,last:INT,s:ROPE,x:REAL,f,g:INT,r:REF ANY];-- stuff in an interface.Label: TYPE~REF LabelValue;Next: PROC[l: Label] RETURNS[Label]~-- An inline proc binding.INLINE { RETURN [NARROW[l.r]] };H: TYPE~Histogram11; Size: INT~10;-- Implementation:Binds a TYPE and INT.HistValue: PUBLIC TYPE~HV40.1;-- PUBLIC for exports.baseHist: PUBLIC H_NEW[HistValue_ALL[17]];-- An exported variable x, y: HistValue_[ 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0];-- with initialization.FatalError: ERROR[reason: ROPE]~CODE;-- Binds an error.Setup: PROC [h: Handle3, a: INT]~ENTRY {...};-- Binds an entry proc.i,j,k: INT_0; p,q: BOOL; lb: Label; main: Handle;Declarations are explained in І÷2.2.1F and І÷2.4.5. Their peculiarities in the different contexts wherethey can appear are explained elsewhere:interfaces in І÷3.3.4;blocks in І÷3.4.1;fields in:domains and ranges in І÷4.4;records and unions in І÷4.6;Access is explained in І÷3.3.6.Bindings are explained in І÷2.3.5. There are several special forms of binding given in rule 13,however, which are defined here. See also І÷3.7 on argument bindings. Note that the e in a bindingis evaluated just once, even if several names are bound.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 ~.A name with a signal or error type can be bound to CODE; this use of CODE is not allowedanywhere else. See І÷4.4.1 for details on the meaning of this.╦╧A MACHINE CODE construct can be bound to a name with a proc type. This constructallows machine instructions to be assembled into a proc value. The instructions areseparated by semicolons. Each instruction is assembled from a list of expressions separatedby commas. An expression in the list is evaluated to yield a [0..256) static value whichforms one byte of the instruction; successive expressions form successive bytes.A l-expression derived from a block can be bound to a name with a proc type. Thecomplicated semantics of this construction are explained in the following subsection.3.5.1 PROC bindingsA binding of the form n: T~{...} is the only way to construct a proc value and bind it to a name,since you cannot write a l-expression in current Cedar.There are other ways to construct proc values: ЪНЇОf2tТGУН0тНG?sНЇО_шzНЇО\╟s ТXtstsН* Н5©НЇО[, tsts Н*Н5©НЇОY╗ ts Н*Н5©НЇОX$ tsН*Н5©Н ОV═tsНЇОUtТGstsН*ТXН5©tsНЇОS≤ tststststТGsН*ТXН5©sНЇОRtstsНЇОP░ts tsН*Н5©Н ОOtststsНЇОLЄts ОLЗrОLЄstsН*Н5©tstsНЇОK0 tstsОKvrОK0sН*Н5©tsНЇОI╛ tsts tsН*Н5©НЇОH(П8tН*sН5©НЇОFєtststsН*Н5©НЇОE ts ОEfrОE ststТGsqsН*ТXН5©НЇОC°tstsНЇО@qТ▀П>Т▄НЇО>МТ─П$НґО<∙НґО:=НґО7Е НёО5тНёО3цНЇО1kНЇО.@ТнП$ТоП3НЇО,╪Т┴ПKТ┼НЇО+8Т─П6НґО(ЮТ┤tsТ┬П7НґО'\Т└ПHО'╒rО'\sНґО%ьТ─ О&rО%ьsНґО#─Т┴П%Т┼ts tsНґО!ЭТ─П6НґОєТўtstsПBНґО ТЫТЗПEНґО°Т≈П<Т≤НґОТаТбП=НґО■Т─ПKНґО<ТкxsТлП3НґО╦ Т─ПJНЇО╧zТX}zНЇО▌sТ∙{s{sПAТ√НЇО Т─xsНЇО %tП/Ъ jTVk(©BLOCKS, OPEN AND ENABLEІ÷3.456The expression in a defaultTC55 is turned into a parameterless proc which is bound to Default in the type'scluster (І÷4.11).The expression following ~~ in an open or WITH ... SELECT is turned into a parameterless proc with adeproceduring coercion (І÷3.4.2).The statement in an enable choice for an exception is turned into a proc with domain and range given by theexception type (І÷3.4.3.1).The expression following LOCKS in a module heading is turned into a proc according to a peculiar rule (І÷4.10).The l-expression is constructed from the block in the following way. Its domain and range are thedomain and range of the proc type T. Its body implicitly declares a variable for each item of thedomain and range; these variables have the names of the domain and range items, and their scopeis the entire block, not just the block body. The domain variables are initialized to the parameters,and the range variables in the usual way according to their types. Then the block, with a RETURNtacked on the end, is evaluated. A RETURN exception in the block is caught, and the current valuesof the range variables are the result of the l-expression. The only other way out of the block is toraise an ERROR.A RETURN in the block is sugar for GOTO Return(, which is caught as described. RETURN e assigns eto the range variables and then does a GOTO Return(.Anomaly: It is an error to introduce the same name twice in the domain, range or blockPerformance: A proc call and return is about 30% faster if the proc is local, i.e., denoted by a namewhich was bound to a proc body in the same module as the call. A proc which is local to anotherproc, rather than bound in the body of an implementation, is about 20% slower to call. It alsointroduces some overhead when its parent proc is called, and its access to non-static namesintroduced in its parent proc is slower than access to other names. A call and return for anordinary, non-local proc takes about 10 times as long as the statement x_y+z.The attributes ENTRY and INTERNAL can be used only in a MONITOR; they are discussed in І÷4.10.The attribute INLINE has no effect on the meaning of the program, but it causes the proc body tobe expanded inline whenever it is applied. This saves the cost of a proc call and return andsometimes the cost of argument passing, and it may allow constant arguments to participate in staticevaluation within the proc. Restrictions: An INLINE proc may not be:Recursive.Exported.Used as a proc value except in an application. Thus you cannot, for example, assign it to aproc variable.The argument of FORK.Accessed from the cluster of a POINTER TO FRAME type.Anomaly: An inline proc binding in an interface is not accessible from a DIRECTORY argument; youmust import the interface.Performance: Excessive application of inline procs will result in much larger compiled code.Excessive definition of inline procs will result in much larger data structures in the compiler, andhence in larger symbol table files, and a greater chance of overflowing the compiler's capacity. Thefollowing cases are efficient:An inline proc in an implementation which is called zero or one times.An inline proc which has a simple body, no locals, no named results, and no accesses to theformals after potential side effects.Н⌡Оf2tТGУНF{НЇsНґО`"tТёО`h~О`"tП$Тєyt НґО^ДТ─ НґО\сТдТе~t~tП+НґО[∙Т─НґОY└Т┴ПJТ┼НґОXFТ─НґОV5~tПQНЇОS sТ▐xs Т░ПQНЇОQ├Т╒{sП:ТёНЇОPТ⌠ПYНЇОN~Т■ПMНЇОLЗТ≥Т ПCtНЇОKvsТ▀tsТ▄П(НЇОIРТ▒Т▓xsП6НЇОHnТ─tsНЇОECТ┼tsts{vs Т▀ts{s{НЇОC©sТ─П%ts{vsНЇО@■zsПOНЇО=iz sТ┤Т┬П$zsНЇО;ЕТ■ПFТ∙НЇО:aТ╨Т╩ПGНЇО8щ ТКП.ТЛП#НЇО7Y ТвП9ТьНЇО5уТ─П>{s{s{sНЇО2╙tststsНЇО/Т≤ tsП1Т≥НЇО-ШТрПAТсНЇО,wТ└ПQТ┘ НЇО*С Т─НЇО'хzstsНґО%p НґО#НґО юТ█П*Т▌П-НґО<Т─ НґОДtsНґО▄tststsНЇОazsТ┘Т├П$ts НЇОщТ─НЇО╡z sТЯП+ТРП%НЇО.Т╒П*ТёП1НЇО╙Т▐ Т░ПUНЇО&Т─НґОнПFНґО vТ┌ПBТ┐НґОРТ─ЪЛTVk(▀І÷3.6STATEMENTS573.6 Statements14 statement ::= sS{ SIMPLELOOP {sS; GOTO Cont((; EXITS Retry((=>NULL};In 6, 10, 17, 19. EXITS Cont((=>NULL } 15 sS ::=e1_e2 | e | block6 | escape | loop | NULL[e1_e2].TOVOID | e --must yield VOID-- | --all four yield VOID--16 escape ::= GOTO n | GO TO n | HEX[exception[code~ n((, args~NIL]] |EXIT | CONTINUE | ЇLOOP | ЇRETRY |GOTO ( Exit(17 | Cont(9 | Loop(17| Retry(9) |(RETURN | RESUME) ?e | { ?(r(13_e;) GOTO (Return(13 | Resume(13) } |ЇREJECT | ╦╧e _ STATETHISEXCEPTION[] | DUMPSTATE[e]17 loop ::= (iterator | ) { ( iterator ; | done(~FALSE; Next(: PROC~{}; )(WHILE e | UNTIL e | ) { Test(~l IN (NOT e | e | FALSE);DO ?Їopen7 ?Їenable8 ?body10 { open SIMPLELOOP { IF Test([] OR done( THEN GOTO FINISHED; { enable body EXITS Loop(=>NULL }; Next([] }?(REPEAT (n, !..=>s); ...) ENDLOOP EXITS Exit(gNULL; (n, !..gs); ...; FINISHEDgNULL}}}18 iterator ::= THROUGH e | FOR x(: e IN e | FOR (n : t | ╣n) ( n: t; | ) ( ( | DECREASING) IN e | ( Range(: TYPE~e; done(: BOOL_Range(.ISEMPTY; Next(: PROC~{ IF n ( >Range(.LAST | RETURN[0]; []_f[3]; ...};-- or a block,IF i>3 THEN RETURN[25] ELSE GOTO NotPresent;-- or an IF or an escape statement,FOR t:INT DECREASING IN [0..5) UNTIL f[t]>3 DO -- or a loop. Try to declare t in the FOR u: INT_0; ... ; u_t+4; ...-- as shown. Avoid OPEN or ENABLE REPEAT Out=>{...}; FINISHED=>{...} ENDLOOP;-- after DO (use a block). FINISHED -- must be last.THROUGH [1..5) DO i_i*i ENDLOOP;-- Raises i to the 16th power.FOR i: INT_1, i+2 WHILE i<8 DO j_j+i ...;-- Accumulates odd numbers in [1..8).FOR l: Label_lb, l.Next WHILE l#NIL DO ...;-- Sequences through a list of Labels.Cedar makes a distinction between expressions and statements. This distinction is most easilydefined in terms of a special type called VOID, which is equivalent to the empty declaration []. Thisis the range type of a PROC [...]_[], and it is also the result type of a block, control, loop or NULLstatement. An expression whose value is a VOID can be used as a statement, and cannot be used asan ordinary value in a binding (since it wouldn't have the right type). If you want to call a procwhich returns values as a statement, you must assign the 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. Note that thegrammar is ambiguous here, since there are two parsings of e1_e2 as a statement; the one written inthe rule for statement is preferred.ЪНЇОf2tН: НG?sНЇО_шqТXУ НЇО\╟rТ>qtqТXsН*u sqstТGsvsТXtТGsТXvstsН О[,tТGН*sТXtsvstsНЇОY╗rТ>qТXsОYrОY╗sОYrОY╗sqsqsОYНrОY╗sqsqsqstН*sqОYrОY╗sqОYrОY╗susqsqstТGutsТXqstТG sТXtsНЇОW╨rТ>qТXstsqstТGsТXqsН*usqvstsqН ОV6tsqstsqstsqstsqН*tТGqsТXvОV|rОV6sqsvОV|rОV6sqsvОV|rОV6qsvОV|rОV6qsqН ОT╡tsqstqsqsqsН*qsvОTЬrОT╡sqsqstsqsvОTЬrОT╡sqsvОTЬrОT╡qsqН ОS.stsqstН*usqsusqsНЇОPrТ>qТXsqsqsqsН*qsqН+ЦОOкЧmН0PОPsqsvstsvstsqН ОNtsqstsqsqsН*vsxsusqtsqsqsqsqstqsН ОLШtsqsОMArОLШsqsОMArОLШsqsОMArОLШsН*qН,хОLцЧкН/⌠ОLШsu sН*ОKw tsvstsvstststsН*ОIСqsqstsvstsvsН ОHoqtsqsqsqsqstН*stsvtsqsqvqsqstvtsНЇОEDrТ>qТXstsqsН*tsН*ОEЧqН-yОEDvsqstsqН-яОEЧН1ООEDsqН ОCюtТGsТXqsqsqsН*qsqsqsqsqН ОBНЇОY╗Т─НyОX${sНЇОV═ НyОU{sНЇОS≤Т╘Т╙П[НЇОRТ─НЇОNИТ┼ ОO/rОNИsПUТ▀НЇОMeТВtstsТЬП#НЇОKА Тц ОL'rОKАsП=ТдНЇОJ]Т═tstsП.Т║НЇОHыТ▐П$Т░tsП4НЇОGUТ─П2НЇОD*ОDprОD*sТ═П+ts Т║tstststsНЇОBіtsТчtsП(ТъtsНЇОA" Т─tsНЇО=ВzsТ▌tsП,Т▐НЇОlast. The > case can only occur inFOR v IN ..., when an out-of-range value is assigned to v in the loop body. DECREASINGreverses the order in which the elements of the subrange are used. The subrange need notbe static. Note that the subrange is evaluated only once, before execution of the loopbegins.FOR v: T_first, next ...; v is initialized to first, and set to next after each repetition. Thisiterator never finishes the loop. Note that the expression next is reevaluated each timearound the loop. The usual application is something like FOR v: List_header, v.next UNTIL v=NIL.Note that the WHILE or UNTIL test is made with v equal to its value during the next repetition, andthat both tests are made before the first repetition, so that zero repetitions are possible.3.7 Expressions19 expression ::= n | literal57 | (e) | application26 | (e | typeName37) . (9) n | prefixOp e | e1 infixOp e2 | e . prefixOp | e1 . infixOp[e2] | e1 relOp (4) e2 |( l [x(: De1, y( :De2] IN relop ) [e1, e2] |e1 AND (2) e2 | e1 OR (1) e2 | IF e1 THEN e2 ELSE FALSE | IF e1 THEN TRUE ELSE e2 |e ^ (9) | ЇSTOP | ERROR |e . DEREFERENCE | STOP[] | ERROR NAMELESSERROR |builtIn [ e1 ?( , e2, !..) ?applEn27] | e1 . builtIn ?( [e2, ... ?applEn ] ) | funnyAppl e ?( [?argBinding27 ?applEn27] ) |e . funnyAppl ?( [argBinding ] ) |[ argBinding27 ] | --Binding must coerce to a record, array, or Їlocal string-- |s | subrange25 | if28 | select29 | safeSelect32 | ЇwithSelect34 Precedence is in bold in rules 19-21. All operators associate to the left except _, which associates to the right. Application has highest precedence. Subrange only after IN or THROUGH. s only in if÷28 and select choices30 33 35.20 prefixOp ::= @ (8) | ² (7) | (~ | NOT) (3)VARTOPOINTER | UMINUS | NOT21 infixOp ::= * | / | MOD (6) | + | ² (5) | _ (0)TIMES | DIVIDE | REM | PLUS | MINUS | ASSIGN22 relOp ::= ?NOT ( ?~ (= | < | >) | # | ?NOT ( ?NOT x(.(EQUAL | LESS | GREATER)[y(] | x(~=y( | (<= | >=) | IN) x(=y( OR x( (< | >) y( | x(>=y(.FIRST AND ( x(<=y(.LAST --In 19, 30. BUT {BoundsFault=>FALSE} ) )23 builtIn ::= -- These are enumerated in Table 4²5.24 funnyAppl ::= FORK | JOIN | WAIT | NOTIFY | BROADCAST | SIGNAL | ERROR | RETURN WITH ERROR | ЇNEW | ЇSTART | ЇRESTART |╧╦TRANSFER WITH | ╧╦RETURN WITH25 subrange ::= (typeName37 | ) LET t(~(typeName | INT) , first(~( e1 | e1.SUCC ) IN ( [ | ( ) e1 .. e2 ( ] | ) ) t(.MKSUBRANGE[first(, (e2 | e2.PRED )] BUT --In 19, 39, 48. {BoundsFault=>t(.MKEMPTYSUBRANGE[e1]}26 application ::= e [?argBinding ?applEn]LET m(~e, a(~[argBinding] IN ( (m(. APPLY Za( ) ?applEn )27 argBinding ::= (n ~ (e | | ╣TRASH )), !.. |(n ~ (e | OMITTED | TRASH) ), !.. | (e | | ╣TRASH ), ...(e | OMITTED | TRASH ), ...In 19, 26. ЇTRASH may be written as NULL, ~ as :.27.1applEn ::= ! enChoice9; ...-- In 19, 26.BUT { enChoice; ... }ЪНЇОf2tН: НG?sНЇО_шТ─УНґО]┐tsТ П)ts{sТ⌡НґО[ЪТ─ {sНґОYїtsТ┘{s{sts{s{s{sТ├{sts{sНґОX#Т─Т│{v{sНґОV÷tsТ╟{stsП0{sТ╠t НґОUsТ∙П4Т√НґОS≈ТоТпП5НґОRНґОO╩tsТ╧{sТ╨{s{s{s{s{s{sНґОN7ТнП'То{sНґОLЁТ─П3Н⌡ОK/tsТX{s{s{s{s{sts{stsНЇОHТ┼ tsts{sТ▀zsНЇОF─Т─ПXНЇОAґqТXНЇО>┌rТ>qtqТXsqsО>хrО>┌sqsН$О>JЧyН²О>┌НBО>JЧyН╩О>┌qsО>хrО>┌sqsН О<ЧqsqsО=DrО<ЧqstТGptsТXqsН О;z qsО:МrО;zs О:МrТ>О;zsТXqsН*qsqН+ЄО;BЧ5Н0ИО;zsqsqО:МrО;zsqН4О;BЧzН8▓О;zsqО:МrО;zsqsН О9▄О8ЪrО9▄stТGptsТXО8ЪrТ>О9▄sТXqН*sН*О9TЧyН*│О9▄xsvsvsО8ЪrО9▄svsvsО8ЪrО9▄susqН7ЇО9TЧВН:ўО9▄sН;О9TЧyН;О9▄О8ЪrО9▄sО8ЪrО9▄sqН О7·sО7rО7·stТGptsТXО7rТ>О7·sТXqsО7rО7·stТGptsТXО7rТ>О7·sТXqsН*tsqО7rО7·stsqО7rО7·ststsqstТGqО7rО7·sТXtststТGqО7rО7·sТXqН О5╟stТGptsТXqstsqstsqН*qstТGu sТXqsusqstТGusТXqН О4,s О3÷rО4,sqsО3÷rО4,sqsqsО4rrО4,sqsН*qО3÷rО4,sqsqsqО3÷rО4,sqsqsqsqsН О2>qsqs О2└rО2>sqsО2└rО2>sqsqН*qsqsqsq sqsqН О0╨sО1rО0╨sqsН*П=qН О/6sqsО/|rО/6sqsО/|rО/6sqsО/|rО/6sqs О/|rО/6sqsО/|rО/6sН О-Ьt ТGptПQН О,╨ПarО-О,╨tО-rТ>О,╨tНЇО)▐rqТXstptsqstptsqsqsqstqstptН*usqsusqsuНЇО(rТ>qТXsqsqststptsqsqstptsqstptН*usqsusqsusqsusqsusqsuНЇО&┤rТ>qТXsqtsqsqsqsqsqsqsqsqsН*qtsqsqtsvsqusqsusqsuqsvsqsvtsvsqsН О%tТGП.qsТXqsqsqstqsН*vsvstsvsqsqsqsvsqsvsvststsНBО$кЧyНB▒О%vsvstsН О#tТGН*sТXП*ustsНJО#GЧyНJ█О#qНЇО!ШrТ>qТXsП&НЇО wrТ>qТXstsqstsqstsqstsqstsqsН ОСtsqstsqstТG sТXqsН ОotsqstsqstsqstТGsТXqstТGНЇОDrТ>qТXsqsО┼rОDsqsqstТGН*usТXvsqsqstqsvsqsqОЇrОDtТGqtqОЇrОDstsТXqtТGutН ОVsТXqsqsН√ОЧyНОVqsОиrОVsОиrОVsqsqsНnОЧyНГОVqН*svsu svsqОиrОVsqsqОиrОVstsqsusН ОhtТGН*sТXvsusqОшrОhsНЇО=rТ>q ТXsqs qsН*usvsqsvsq Н2╩ОЧsН9.О=susН;\ОЧyН;уО=Н<-ОЧyН<іО=vstТGusТXvsvsНDьОЧyНEQО=qНFDОЧНJYО=sНJ╠ОЧyНЇО╧rТ>q ТXsqsqsqsqstsqsqsqН*qsqsqsusqstqtТGqsТXqsqН О5sqsqsqstsqsqН*qsqsusqstТGqsТXqН ОВtТGП/НЇО srqТXs О ╧rО ssqtТG Н*usТXqН-іО ;ЧvН3О ssqsчTVk(╗BLOCKS, OPEN AND ENABLEІ÷3.460Exampleslv: LabelValue13_[ i, 3, "Hello", 31.4E°1, (i+1),-- A constructor with some sample g[x]+lb.f+j.PRED, NIL ];-- expressions.p1: PROCESS RETURNS [INT]_FORK f[i, j];-- FunnyAppls take one unbracketted ERROR NoSpace; WAIT bufferFilled;-- arg; many return no result, so RT: RTBasic.Type_CODE[LabelValue13];-- must be statements.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~5,x~3.2,g~2,f~5,r~NIL,s~"1"];-- Short for lv_LabelValue13[...].[first~i, last~j]_lv19;-- Assignment to 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 Color54(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 defaultTC55).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 proc23, or the funnyAppl24 in which the first argumentfollows the proc name without any brackets. All of these constructs desugar into dot notation(І÷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, and VAL; all of these get the proc from the target type of theexpression (І÷4.2.3). All the primitive procs are described in І÷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.The order of evaluation for arguments of an application, and therefore for operands in anexpression is not defined (unless the operator is AND or OR). However, the arguments are evaluatedone at a time, and all arguments are evaluated before the proc is applied. In particular, anassignment which executes completely behaves as though both left and right operands arecompletely evaluated before any assignments are done, even if the left side is a binding such as[a~x, b~y.f].Rules 19-21 give the precedence for operators: ^ and . are highest (bind most tightly) and _ islowest. All are left-associative except _, which is right-associative. Application has still higherprecedence. Style: The precedence rules are sufficiently complex that it is wise to parenthesize expressions whichdepend 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 is a group or binding with corresponding elements which can be assigned to thevariables. Usually the second argument is either an application which returns more than one result,or a record-valued expression. You can omit elements of the left argBinding to discard thecorresponding values; however, you can't write TRASH in the left operand. Note that the rightoperand is fully evaluated before any variables are changed by the assignment.The expresssion ERROR is short for raising a nameless ERROR exception. You should think of it as acall to the debugger, appropriate for a state which "can't occur".Н⌡Оf2tТGУНF{НЇsНЇО_шzНЇО\╟sТX О\ЖrО\╟sП!Н*П"Н О[,tstsН*НЇОY╗tstststsН*П$НЇОX$ts ts Н*П$НЇОV═ts ОVФrОV═sН*НЇОUtststs Н*П*НЇОS≤ОSчrОS≤sП!tsН*{s{ ОSчrОS≤sqsНЇОRОRZrОRsН*tsНЇОP░Н*НЇОMetsts tstststsН*П"tsНЇОKАtsОL'rОKАstststs Н*ts НЇОHІП(Н*П'Н ОG2qsН*НЇОEўН*НЇОD*Н*v{s{s{s{s{sНЇОBі tstsН*{s{sОBЛrОBіsНЇОA"tsН*{s{s{sНЇО=ВТ°Т²ПEНЇО Т─НЇОzsП4Т│П-НЇО▐Т─П%НЇОdТ▐Т░О╙rОdsП2НЇОЮТ°П;zsТ²НЇО\ТЄП8Т╣НЇОь Т▐П5Т░П$НЇОTТНП>ТОНЇОпТйП!ТкtsП)НЇОLТ─ПGНЇО!Т┘tsП!tsП'НЇО ²Т─П>ЪfTVk(І÷3.7EXPRESSIONS61A funnyAppl which takes more than one argument has the extra arguments written inside bracketsin the usual way; e.g., START P÷[3, "Help"]. RETURN WITH ERROR is explained in І÷4.10.Anomaly: The funnyAppl NEW e actually stands for e.COPYIMPLINST. See І÷4.4.1 and І÷4.5.3.Anomaly: Enable choices are legal only for the following funnyAppls: FORK JOIN RESTART STARTSTOP WAIT. You can write empty brackets if necessary to get a place for the enChoices.A subrange25 denotes a subrange type; see І÷4.7.3. Standard mathematical notation for open andclosed intervals is used to indicate whether the endpoints are included in the subrange. A subrangecan also be used after IN in an expression or iterator; in these contexts it need not be static.You can write enable choices9 after a ! inside the brackets of an application26, built-in23, orfunnyAppl24. See І÷3.3.2 for the semantics of this. Note that only an exception returned by theapplication is caught by these choices, 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 thename without the value expression (e.g., n~ ) with the same meaning. You can also write TRASH(Їor NULL) 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 ";" is "," in an expression; also in 32 and 34.-- ELSE is a separator for repetitions of the choice.30 choice ::= ( ( | relOp22 ) e1 ), !..=>e2IF ( (selector( (= | relOp ) e1) OR ... ) THEN e231 endChoice ::= ENDCASE ( | => e3)ELSE (NULL | e3)In 29, 32, 34.32 safeSelect ::= WITH e SELECT FROMLET v(~e IN safeChoice; ... endChoice31 safeChoice ELSE ... endChoice33 safeChoice ::= n : t => e2IF ISTYPE[v(, t] THEN LET n : t_NARROW[v(, t] IN e234 ЇwithSelect ::= WITH (n1 ~~ e1 | Ї e1 )OPEN v(~~e1 IN LET n(~($n1 | NIL), type(~Dv(,SELECT ( | ╦e11) FROM selector(~(e1.TAG | e11) IN withChoice ELSE ... endChoice withChoice; ... endChoice31-- e11 must be defaulted except for a COMPUTED variant.ЇThe ~~ may be written as :.35 ЇwithChoice ::= n2 => e2 |IF selector(=$n2 THEN OPEN n2, n2, !.. => e2 (BINDP[n(, LOOPHOLE[v(,type(.n2] ] | BINDP[n(, v(] ) IN e2ЪНЇОf2tН9Н НG?sНЇО_шТ▓УП5Т⌠П(НЇО^WТ─ts{s tststsНЇО[,zsts{s{stsНЇОXzsТ═П=tstststНЇОV}sТ─tsПMНЇОSRТЄОS≤rОSRsП&Т╣П,НЇОQнТ▌П*Т▐П3НЇОPJТ─tsПGНЇОMТБОMerОMsТЦП*ОMerОMs ОMerОMsНЇОK⌡ОKАrОK⌡sТҐТЎПCНЇОJ Т─ПUНЇОFЛТ ОG2rОFЛsП$Т П"НЇОEhТ∙{s{sП)Т√П$НЇОCДТіП%{sТїП&tНЇОB`sТ─tsПGНЇО=█qТXpqpНЇО:brТ>qТXstsО9уrО:bstsО9уrО:bsqtsО9уrО:bsqsqН*tsqО9уrО:bstsqО9уrО:bstsqО9уrО:bsqstqНЇО8trТ>qТXststsН*usvsqsuН О6Пsqs Н*qН,О6╦ЧхН/ЮО6ПstsqsqН4╨О6╦Ч&Н:ЮО6ПsН О5╡tТGП1Н*П5НЇО4.rТ>qТXsqsqsqsО4trО4.sqsО3║rО4.sqsqsО3║rН*О4.tsqtТGqsvsТXqsqsqsqsqО3║rО4.qstsqsqstsqО3║rНЇО2@Т>qТXstsqsqsО1ЁrО2@qН*tsqtsqsqО1ЁrО2@qН О0≥tТGНЇО-nrТ>q ТXststТGН*usТXvsqsuН О+Йsqs О,0rН*О+Йsq Н+юО+╡ЧhН2(О+ЙstsqsqН7О+╡Ч&НЇО*frТ>q ТXs О)ыrН*О*ftsusvsqstТGsТXusqsqstsvsqstsqО)ыrНЇО(xТ>sq ТXstsqsО'КrО(xsО'КrО(xsqsО'КrО(xsqН*usvsqО'КrО(xsutТGusТXvsqsqО'КrО(xsqstqsvsvsvtН О&┼sqsqsО%ЩrО&┼qstsН*tТGsvsqО%ЩrО&┼susТXqsqО%ЩrО&┼qsusq Н9ЦО&RЧ■Н@wО&┼stsqsqНEQО&RЧ&Н О$°sqs О$БrН*О$°tТGО$rО$°tП1Н О"УНЇО!qrТ>sq ТXsО ДrО!qsО ДrО!qsqН*tsvsqО ДrО!qtТGsТXutТGН О┐sОЖrО┐sТXОЖrО┐sqsОЖrО┐sН*tТGqusvsТXtsvsvsqОЖrО┐sqtТGusvsТXvstТGqsТXusqОЖrЪ ╒TVk(>BLOCKS, OPEN AND ENABLEІ÷3.462Examplesi_(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: 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 Node52~...; WITH dn~~nr SELECT FROM-- See rule 52 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 to yield a value selector(, and then each ofthe choices is tested in turn. Within each choice, each expression e1 preceding the => is comparedin turn with selector(; the comparison is selector( relop e1 if e1 is preceded by a relop; otherwise it isselector(=e1. If any comparison succeeds, the expression e2 following the => is evaluated to yield thevalue of the select. If no comparison succeeds, the next choice is tried. If no choice succeeds, theexpression e3 following the ENDCASE is evaluated to yield the value of the select; e3 defaults toNULL, and hence must be present when the select is not a statement to prevent a type error.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 to mean another specific selector value which you don'tbother to mention. Another acceptable form is SELECT TRUE FROM ..., which selects the first choicethat succeeds, and is sometimes easier to read than a long sequence of ELSE IF's.Performance: If the e2 are static and select subsets of the selector values, the average size of thesesubsets is not too large, and the density of unselected values is not too high, a select compiles intoan indexed jump, which executes in a time independent of the number of choices.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, REF V, or (LONG) POINTER TO V, where V is a variant record. Each choice specifies onepossible type that the selector might have, and declares a name which is initialized to the selectorvalue if it has that type. Thus, the example tests for r having the types REF INT and REF REAL. If ithas REF INT, the first choice's e is evaluated; within e, rInt is a variable initialized to the selector,and has type REF INT. Likewise for REF REAL and the second choice. As with an ordinary select, theENDCASE expression is evaluated (with no new names known) if none of the other choices succeeds.Note that safeSelect does ordinary binding by value, not the binding by name done in open andwithSelect.Н⌡Оf2tТGУНF{НЇsНЇО_шzНЇО\╟stsТXtstsН*tstsНЇО[,tstТGsТXtstsНЇОY╗tstН*stsН ОX$ Н*v{sts{s{sts{stsqstsqsН ОV═tsН*qsН ОUtsН*tsqsН ОS≤tstsН*П%НЇОPmtstТGН*sТX{stТGsТXН ОNИtТGsts ТXН*{sП!Н ОMetТGstsН ОKАtststsТXtststsН*tТGsТX{sНЇОI┴tsОIоrОI┴ststТGН*sТXП${Н ОHsН*{s{s{sН ОF│Н*{s{s{sН ОDЩtstsН*{s {sНЇОAрТёОBrОAрs Тє{ОAErОAрsts{s{ОAErОAрsНЇО?Д{stsТ─{О?WrО?Дs{stsНyО=ЖtsТX{О=irО=Жststs{О=irО=Жsts{О=irО=ЖstТG{О=irНЇО<sТ─П"tstsП*НЇО8щТ▄О9#rО8щsПVТ█НЇО7YТ┘П'{sТ├П${vsНЇО5уТ▓П@{О5HrО5уsТ⌠НЇО3ГТ² {vsТ·{vs{s{О3ZrО3Гs{О3ZrО3Гs{sНЇО1Ы{vs{О1lrО1ЫsТ─П+Т│{О1lrО1ЫsП+НЇО0Т═Т║П\НЇО.┤ Т╧{О-ЗrО.┤stsТ╨П-{О-ЗrО.┤sНЇО,≥tsТ─ПVНЇО)nzsТҐП6ТЎП&НЇО'ЙТ▓tsТ⌠ПCНЇО%Э{О%orО%ЭsТб ТцtsП8НЇО$Т▄П(tststsТ█П$НЇО"┼Т─ПCtstsНЇО_z sТ·{ОрrО_sП%Т÷П+НЇОqТ▓П0Т⌠П/НЇОМТ─ПMНЇОбТ÷ ОrОбsП%Т═tsНЇО>Тм tsТнП)tstststv{stНЇО╨{vtsТ└{sts{stststsТ┘{s{sП/НЇО6Т·П0Т÷П,НЇО╡Т┬Т┴{ststststsНЇО.Т║tsts{sТ╒{s{sП+НЇО╙Т─ tsТ│tststsП7НЇО&tsТ┘П%Т├П4НЇО╒ТіП@ТїНЇО Ъ.TVk(йІ÷3.8IF AND SELECT63Ї╦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 e11 in the withSelect. It is entirely up to the programmer to supply a meaningfulvalue. If the tag is not COMPUTED, e11 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 e2 following => is evaluated as with an ordinary select. If exactly one is given, then thee2 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 e2 following => is in the scope ofOPEN n1~~e1.DEREF or OPEN e1.DEREF3.9 MiscellaneousThis section deals with various topics that are not naturally associated with particular types orgrammar rules.3.9.1 Static valuesAn expression has a static value if the compiler can compute the value. In Cedar, an expression hasa static value (is static for short) if it is:a literal;a name bound to a static value;an application to static arguments of a proc declared INLINE with a static body, or a primitive which is not a loop, a REAL primitive (except unary minus, ABS orINTTOREAL), ASSIGN, @ or NEW. Note that IF and SELECT are evaluated.Performance: The compiler evaluates all static expressions, not just type expressions. This is oftenimportant for efficiency.3.9.2 Size restrictionsCurrent Cedar has the following restrictions on the sizes of values:ЇA record type T must have T.SIZE<216.ЇA row type T must have T.SIZE<228 and T.RANGE.SIZE<216.ЪНЇОf2tН9ТGУ НG?sНЇО_шТ╒ О`!rО_шsПPТёНЇО^WТ░Т▒ПItsНЇО\сТ─П4НґОZ{ТЦТД{ОYНrОZ{sП&{ОYНrОZ{sНґОX█Т┤Т┬П)zsНґОW ТфТгПJНґОU┘Т■ Т∙ПLНґОS≈{ОS rОS≈sТ─НґОQ?Т┼tsП?НґОO╩Т─ {ОO.rОO╩sП%Т│П)НґОMмТ─ts{ОM@rОMмsП+{ОM@rОMмsusНґОKuТє{ОJХrОKusП:Т╔НґОI┤Т─ПQТ│НґОHТ┤{ОGvrОHsПAТ┬НґОF{ОE┬rОFsТ─П!Н⌡ОD'tsТX{ОC rОD'sts{ОC rОD'sus{s{ОC rОD'sНґОB9Т─Н⌡О@╣tsТXts{О@(rО@╣sus{s{О@(rО@╣sНґО>гТ∙{О>:rО>гsts{О>:rО>гsП0НґО<ыТ─{О216 lacks the following procs:ALLASSIGNCONSDESCRIPTORINITNEWЇA subrange type T must have0