Inter-Office MemorandumToCedar UsersDateMay 20, 1981FromEd SatterthwaiteLocationPalo AltoSubjectCedar 7T7 Language and Compiler ChangesOrganizationCSLXEROX Filed on: [Ivy]Lang>Cedar7T7.BravoDRAFTThere is a new version of the Cedar compiler. This memo summarizes the changes to the languageand compiler that you should know about.Types in CedarThis section sketches some current thinking about the Cedar type system and might help you tounderstand the motivation for some of the changes described below. (See also Lampson, Cedarabstract machine [CedarAM.memo, February 1980].)Types as PredicatesEvery type is characterized by some predicate; a value x has type T iff x satisfies the predicate forT. In general, such predicates are defined in terms of a set of marks (tags, etc.) carried by eachvalue; however, the Mesa type system is designed so that most mark manipulation can be donestatically (by the compiler), and the usual representations of most values do not include explicitmarks.A given expression has some fixed syntactic type that depends upon the form of the expression andthe declared types of constituent identifiers. The value denoted by an expression always satisfies thepredicate characterizing its syntactic type, but such a value will often satisfy predicates characterizingother types as well. In this sense, a Cedar value may have an arbitrary number of types. Forexample:If Thing is a variant record type with a variant red, a reference to a Thing might simultaneouslysatisfy the predicates for REF ANY, REF Thing, and REF Thing[red] (formerly REF red Thing, seebelow).An opaque type and the corresponding concrete type are distinct, even within an exporter of theconcrete type, but the predicates for the two types are identical.Roughly speaking, the primary job of the predicates associated with types is to provide correctanswers to questions about low-level representational conventions so that, e.g., the Cedar garbagecollector can operate correctly.The form ISTYPE[x, T] returns the result of applying the predicate characterizing T to the value x.In Cedar 7T7, ISTYPE has been redefined to work in a somewhat more general and uniform way,and the operations of NARROWing and (type-based) SELECTion have been defined in terms of ISTYPE.]gpi c8q]rX -q7Br ]q]r-q7Br Yq]r'-q 7BrSsr MqF-?u Gr-2 Et( ARv >rG <\"5w :r 5wX 2pr -wr wrwr 0wr"@ /!$7 -zE + ("w r1 &!F %5j #> ! kwr)wrwr qrqrwrqrwrwr qrwrwr  [ B (7 H ] qrwrwr>wr wr g qr) qrqrqr y>^0Cedar 7T7 Changes2Types as Clusters of OperationsIn addition, a cluster of operations (sometimes called a group) can be associated with a type. Themain purposes of this grouping are to provide a number of packaging conveniences and to supportso-called "object oriented" notation. If x has (syntactic) type T, x.Op[args] means Op[x, args] whereOp is found by looking in the cluster associated with T. Two types may be characterized by thesame predicate but have different associated clusters; in current Cedar, this is true of, e.g., anopaque type and the corresponding concrete type.Each of the type constructors in Cedar supplies a standard and implicitly defined cluster for eachtype that it constructs. The only mechanism currently available for the explicit construction of sucha cluster is the interface module, and previous versions of Cedar have limited support of thismechanism to opaque types. If T is an opaque type declared by, e.g., T: TYPE;in some interface Defs, operations (procedures) declared in Defs become components of the clusterassociated with T and may be invoked using object notation. Cedar 7T7 extends this support toallow construction of similar clusters for record types. If T is declared in Defs by T: TYPE = RECORD [ ... ];the operations declared in Defs become part of the cluster associated with T. In this case, however,they augment the operations already supplied for T by the RECORD type constructor.Defining clusters in this way has some drawbacks. The use of interfaces as the units of groupingsomewhat overloads the existing notion of an interface; note that all operations declared in aninterface become parts of the clusters of all types declared in that interface. Also, requiring a typeand the operations in its cluster to be defined in the same interface occasionally conflicts with othercriterea for partitioning interfaces. On the other hand, this method of defining clusters seems tocover the important cases well enough to be acceptable in practice. In addition, there is a fairlywell worked-out plan for supporting clusters in a comprehensive, uniform way and for using themto explain parts of the Cedar abstract machine. We therefore recommend the following styleguidelines for your Cedar programming:Partition interfaces so that a single interface defines both a main type T (record or opaque) andall the operations to be provided in the cluster of T (or REF T). Define multiple main typeswithin an interface only if the sets of meaningful operation names for those types are disjoint.Use object notation in clients of interfaces designed to support it; i.e., use x.Op[args] inpreference to Defs.Op[x, args].(For Humus veterans) Avoid interface designs that require clients to write x.Op[x, args],x.ops.Op[x, args] or the like. Use an inline definition of Op within Defs to achieve such aneffect. LANGUAGE CHANGESSyntax for Discriminated TypesIf V is a type expression designating some variant record type with variant a, V[a] is a typeexpression designating the discriminated type. Thus forms such asObject[red] Object[red][short] Object[red][long][80]are equivalent to the old formsred Object short red Object long red Object[80]. fvG bwX ^rwr#wr ](-2 [*wrwrwrwrwrwrwrwr Ywrwr( X26, V0 S<Y Qa O&8 NFwr% Lwrqr Jwr&wr! IPwrM G=wrwr Fwrqrqr DZwrwr B1wrqr ?dD =7( <-: :n\ 8c 76- 5xT 3&5 2)& /Iwr .3wrqrwr ,_` )Jwrwrwr (= wrwrwrwr %7wrwrwrwr $wrwrwrwrwr,wrwr  "s }v [  rwrHwrwrwr eA wrwrXwrwrwrwrwrwrwr  owrXwrwrwrwrwrwrwrwr (=XCedar 7T7 Changes3In Cedar 7T7, both forms are acceptable, but you will eventually have to convert to the former asCedar moves toward a unified syntax for expressions and type expressions.Type DiscriminationCedar 7T7 unifies the mechanisms for discriminating variant records with those for discriminatingvalues with type REF ANY. This unification affects the operators ISTYPE and NARROW as well asdiscriminating selection.Type TestingThe primitive function ISTYPE tests whether a given value satisfies the predicate characterizing aspecified type. You will probably have little direct use for ISTYPE; its importance lies in its use todefine other, more common operations as described below. Let x be an expression with syntactictype S. In Cedar 7T7, the value of ISTYPE[x, T] is determined as follows, where V is any variantrecord type:(1) It is TRUE (at compile time) ifS and T are equivalent types; orS is an opaque type and T is the corresponding concrete type; orS is a concrete type exported as the opaque type T.The last two cases are recognized only within program modules that export the concrete type.(2) It is determined dynamically by a test of the value x, yielding TRUE or FALSE, ifS is REF ANY and T is REF U for any U except ANY; orS is equivalent to V and T is equivalent to V[a]; orS is equivalent to REF V and T is equivalent to REF V[a]; orS is equivalent to (LONG) POINTER TO V and T is equivalent to (LONG) POINTER TO V[a];where V[a] is a particular variant of V, perhaps discriminated to several levels. Note that the resultis TRUE if the value of x is NIL.(3) In all other cases, ISTYPE is unimplemented and is treated as a compile-time error.Subsequent versions of Cedar will provide a more general definition and implementation of ISTYPE.Note in particular that ISTYPE cannot currently be used to test a value for membership in asubrange.NarrowingNARROW[x, T] allows a value x to be viewed as a value of type T and succeeds iff ISTYPE[x, T] isTRUE. More precisely, NARROW[x, T] has (syntactic) type T, and its value is given byIF ISTYPE[x, T] THEN x ELSE ERROR where isRTTypesBasic.NarrowRefFault[x, CODE[T]]if ISTYPE[x, REF ANY]RTTypesBasic.NarrowFault[]otherwise. fvG bra `vI \Tv Yr;& W^qrqrqr U PwX Mrrqr& K.qr# J#8wr H|wr qrwrwr"wr F CX qrMA wrwrM?dwrwr'M=wr0wrM;etF\ 89rX8wr qrqrM5wrqFrXwrqrwrwrqrM4wrwrwrwrwrM2pwrqrwrwrqrwrwrM0wrqFrXwrwrqF rXwrwr .Mwrwrwr@ ,qrwrqr )Wqr9 & Dqr $aqr- " w uqrwrwrwrwrqrwrwr qrqrwrwrwr SqFrwrXwrqrwrqFrX  ]w rw rwrqrwr'qrwrqFr w rw r'  o>XCedar 7T7 Changes4The following situations correspond to the three cases enumerated in the definition of ISTYPE above:(1) NARROW[x, T] is guaranteed (at compile time) to succeed.(2) NARROW[x, T] may succeed or fail at run time.(3) NARROW[x, T] is unimplemented.Case (2) arises only when the syntactic type of x is related to T in one of the ways described abovefor ISTYPE. In Cedar 7T7, case (3) is treated as a compile-time type error. Fine point: NARROW[x, T] isalso considered a compile-time error if the only possible value of x yielding TRUE is NIL. Use x = NIL instead.In case (1), NARROW is an identity operation but can be useful to change the (syntactic) type of xwithout using a LOOPHOLE or requiring any code to be executed. Example:Defs: DEFINITIONS = { T: TYPE; R: TYPE = RECORD [g: REF T, ... ]; Pn: PROC [r: REF R]; ... }.Impl: PROGRAM EXPORTS Defs = { T: PUBLIC TYPE = RECORD [n: NAT, ...]; Pn: PUBLIC PROC [r: REF Defs.R] = { r.g.n _ 0; -- invalid; r.g^ is opaque, with no field selection operations NARROW[r.g, REF T].n _ 0;-- valid (because Impl exports Defs) ...}; }.As before, NARROW[x, T] may be written as NARROW[x] when the target type T is implied bycontext.Discriminating SelectionThe syntactic form of WITH ... SELECT that is currently used for REF ANY discrimination has beenextended to discriminate any value for which ISTYPE performs a dynamic test of that value (see case(2) in the discussion of ISTYPE). The formWITH v SELECT FROM v1: T1 => s1; v2: T2 => s2; ... vn: Tn => sn; ENDCASE => se;is, by definition, equivalent tou: T = v;IF u # NIL AND ISTYPE[u, T1] THEN {v1: T1 _ NARROW[u]; s1}ELSE IF u # NIL AND ISTYPE[u, T2] THEN {v2: T2 _ NARROW[u]; s2} ...ELSE IF u # NIL AND ISTYPE[u, Tn] THEN {vn: Tn _ NARROW[u]; sn}ELSE se;where T is the (syntactic) type of v. The tests against NIL are omitted if T does not have a NILvalue. fvG br#4qr _Xqrwrwr- ]qrwrwr" \Tqrwrwr Ywrwr# X2qr 9t qtxtxt VCxt qtqtxtqt Sr qrJw Qrqr0 O`wrXq r Mwrqr Lwrqrqrwrqrwr Jjwrqrwrqrwr H FHwrqFrXwr DwrqF rXqrwrqr BwrqF rXwrqrwr ARwrwrwr wrwr/ ?qrwrwrqrwrwr wrwr > <\ 9 qrwrwrqrwrwr 7f 2pwX /!rqrqr -zqr0 +qr ){qrXwrqF 'rXwrwrwr &swrwrwr $q #jrwrwrwr !qrwr  @wrXwrwr qFwrXqF wrXwrqrwrwrqrwrwr 8qFwrXqF wrXwrqrwrwrqrwrwr q 0FwrXqF wrXwrqrwrwrqrwrwr qFwr 1wrwrqrwrq rt B=WCedar 7T7 Changes5Note that this form always copies the discriminated value. Thusr: REF V;. . .WITH r SELECT FROM x: REF V[a] => { ... x ...};-- x is a copy of r with type REF V[a] ... ENDCASE;WITH r^ SELECT FROM x: V[a] => { ... x ...};-- x is a copy of r^ with type V[a] ... ENDCASE;Contrast these with the old form of variant record discrimination, which does not copy thediscriminated value and reevaluates the discriminating expression each time that it is used:WITH x: r SELECT FROM a => { ... x ... };-- x is a synonym for r^ (but with syntactic type V[a]) ... ENDCASE;The new forms are easier to make type-safe, and you should use them whenever possible.Unfortunately, the old form is still required, at least outside the checked language, for dealing with computed variantsand with pointers having non-standard dereferencing operations, such as the current relative pointers).Interaction with Opaque TypesIf T is any exported type, REF T must have the "standard" implementation of type discrimination.We impose this requirement in anticipation of making REF ANY discrimination work correctly withopaque types (it still doesn't in 7T7). As a consequence, discriminated variant record types cannotbe exported as the concrete values of opaque types.Object NotationIn Cedar, the form x.Op[args] is interpreted as Defs.Op[x, args] if the type of x is (REF | POINTERTO)* T for some opaque type T declared in an interface, the principal instance of which is Defs. Inother words, all the operations defined in Defs become part of the cluster of the type T.In Cedar 7T7, this convention applies within the corresponding DEFINITIONS module (for writinginlines, etc.) as well as within importers of such modules. This is only a notational extension; thebindings of implicitly imported values are determined as before.The clustering mechanism has also been extended in Cedar 7T7 so that all operations declared in aninterface become components of the clusters of any record types defined in that interface. With thisextension, Op can be inline in more interesting ways. In addition, you may now be able to useobject notation more extensively to invoke operations in existing interfaces, many of which arewritten in terms of (concrete) record types.Note that every operation declared in an interface module becomes part of the cluster of every(record or opaque) type declared in that interface. Although the type of a particular operationnormally will make it a useful component of only one cluster, its name appears in every othercluster and potentially hides or precludes a more appropriate definition of that name for thatcluster. You therefore should define more than one main type per interface only if the sets ofmeaningful operation names for those types are disjoint. fvG br@ _wrXqrwr ]qF []rXwrqF YrXwrqrwrwr wrwr wr qrwrwr XUq Vrqr TyqrwrqF RrXwrwrwr wrwr wr wr Qqq Orqr L2( J\ H|qrXwrqrq Frwr wrwrwrwrwr E-q CFrXqr A ++ ?tf >&g 9TwX 6rwrqrwr@ 4^qr# 2d 13 ,v )rwrwrwrwrwrwrwrwrqrq 'rwrwr5wr &Owr(w #r-q r !YE @ cH .7  wr> mP , wE ` )Q 1- 8' 38 >^Cedar 7T7 Changes6Other points to note when using this convention with record types include the following:When looking up Op, the field identifiers declared in T take precedence over the identifiersdeclared in the interface Defs.A value x with a record type T having a single component can be coerced to a value with thetype of that component. In the form x.id, the lookup of id considers first the field identifier ofthe single component, then identifiers declared in the interface defining T, and finally anyinterpretation given to id by applying the coercion. You abuse this feature at your own risk(but see the discussion of clusters above). Example:Defs1: DEFINITIONS = { ... T1: TYPE = RECORD [f1: REF Defs2.T2]; ... OpN: PROC [self: T1, ...]; ...}.Defs2: DEFINITIONS = { ... T2: TYPE = RECORD [ ... ]; ... OpM: PROC [self: REF T2, ...]; OpN: PROC [self: REF T2, ...]; ...} r1: Defs1.T1; r2: REF Defs2.T2; ... r1.OpN[...] means Defs1.OpN[r1, ...]-- from the cluster defined by Defs1 ... r1.OpM[...] means Defs2.OpM[r1.f1, ...]-- from the cluster defined by Defs2 (after coercion) ... r2.OpN[...] means Defs2.OpN[r2, ...] ... r1.f1.OpN[...] means Defs2.OpN[r1.f1, ...]-- dubious styleRope LiteralsThe Cedar 7T7 compiler recognizes and correctly translates rope literals. Such a literal is denotedby a quoted string, e.g., "This is a rope literal". Its value is a reference to a rope object in thestandard (counted) zone provided by the Cedar system.The target type established by the context in which a quoted string literal appears determines theinterpretation of that literal. There are three cases:If the target type is Rope.Ref, the quoted string denotes a rope literal and has type Rope.Ref.If the target type is any other REF type, the literal has type REF TEXT.Otherwise, the literal has type STRING.In the first case, the test is actually for equivalence between the target type and REF Rope.RopeRep. The matching isperformed on the names of the interface (Rope) and referent type (RopeRep), not on the structure of the referent type.Since this is a loophole in the type checking, use nonstandard versions of the Rope interface very cautiously. fvG brX ^wrwr% ]nwr ZCwrwr- X%wrwrwr( W; @wr Uwr@ T35 QwrXq r O Mwrqrqrwrqrwrwr L{ Jwrqrwrwr Is Fkwrq r D Ccwrqrqr A @[wrqrwrqrwr >wrqrwrqrwr =S :Kwrwrwr 8wrqrwrwr 5wrwr wrwrwr){w 4:rwrwr wrwrwrwr){wr 2wrwr wrwrwr 12wrwrwr wrwrwrwr){ -v )rY (R &s5 #$S !}7 Xwrwr8wrwr qrqFr  Xqr tTqtxtxt  xtxt- Gxt >TCedar 7T7 Changes7COMPILER CHANGESVersion StampsIn its intermodule type checking, Cedar uses so-called version stamps to identify independentlycompiled modules. The version stamps computed by the Cedar 7T7 compiler are functions of theidentity of that compiler and of its inputs. You can now recompile the same source file, with thesame included modules, the same compiler and the same switch settings to get an object file withthe same version stamp.This stamp, which is essentially a 48 bit hash, is computed recursively as follows. Assume that anyexisting derived object (including the compiler itself) has a version stamp. The stamp for a newderived object is a hash ofthe creation time of the source filethe version stamp of each bcd mentioned in the DIRECTORY clausethe version stamp of the compilerthe compiler switches (with those controlling only compile-time feedback masked off)There is also a 7T7 binder that computes version stamps for its output in the same way.NoteIn the past, the version stamp has been a concatenation of a machine identifier and the creationtime of the derived object. Many existing utility programs therefore print the version stampformatted as a machine and network number, a date and a time. These programs give strange-looking output but, as far as we know, will perform correctly. (Be sure to update DescribeBcd,from Eric Schmidt, before using it with 7T7 object files).Compiler SwitchesThe Cedar compiler is no longer able to generate object code for an Alto (or D-machine emulatingan Alto). The switches /a and /l are ignored.There is a Cedar switch /c; if it is set (the default), the code for FORK and JOIN assumes theavailability of the Cedar runtime. If you plan to run your program directly under Pilot, compilewith /-c. If you are in doubt about how your processes will interact with the Cedar runtime,consult a wizard.Type Table EntriesThe 7T7 compiler guarantees that, for every type T that is an argument of NEW (for a countedzone), an entry for REF T appears in the run-time type table. (This is a temporary concession, madeuntil the run-time type system has a mechanism for building new types on demand.)Distribution:CedarLWGCedar Users fvG b ] Zr>! YL W^C U5+ T P"B O;& Mr JGX$ H/qr G?! ET BW ?dw