DIRECTORY Rope, AlgebraClasses, ASVariableSequences; ASOrchardStructure: CEDAR DEFINITIONS ~ BEGIN Orchard: TYPE = AlgebraClasses.Object; OrchardData: TYPE = LIST OF OrchardTerm; OrchardTerm: TYPE = REF OrchardTermRec; TermRec: TYPE = RECORD [ coefficient: AlgebraClasses.Object - expected to be either an Int or a Real tree: Tree, ]; Tree: TYPE = AC.Object; TreeData: TYPE = REF TreeDataRec; TreeDataRec: TYPE = RECORD [ parent: Tree _ NIL, -- parent tree; NIL iff this node is root children: LIST OF Tree _ NIL, -- NIL iff this node is a leaf label: ASVariables.Variable _ NIL, -- nonNIL iff this is a labeled tree key: ACInts.Int _ NIL -- nonNIL iff this is a heap-ordered tree ]; OrchardStructureData: TYPE = REF OrchardStructureDataRec; OrchardStructureDataRec: TYPE = RECORD [ coeffRing: AlgebraClasses.Object, -- expected to be either Ints or Reals labels: ASVariableSequences.VariableSequence _ NIL, -- NIL labels iff these are unlabeled trees heapOrdered: BOOL ]; MakeOrchardStructure: AlgebraClasses.OrchardStructureConstructor; MakeNameStructureData: PROC [data1, data2] RETURNS [structure: Object]; MakeNameStructure: PROC [data1, data2] RETURNS [structure: Object]; GetNameStructureData: AlgebraClasses.GetStructureDataProc; Data1: AlgebraClasses.UnaryOp; Data2: AlgebraClasses.UnaryOp; Flavor: AlgebraClasses.FlavorOp; StructureToRope: AlgebraClasses.ToRopeOp; StructureName: AlgebraClasses.ToRopeOp; StructureLBKey: AlgebraClasses.ToRopeOp; StructureData: AlgebraClasses.UnaryToListOp; IsNameStructure: AlgebraClasses.UnaryPredicate; MakeOrchard: AlgebraClasses.ListImbedOp; MakeElementNameData: PROC [field1, field2] RETURNS [elementData: ElementNameData]; GetNameElementData: AlgebraClasses.GetElementDataProc; Field1: AlgebraClasses.UnaryOp; Field2: AlgebraClasses.UnaryOp; WidenOther: AlgebraClasses.BinaryOp; CanWidenOther: AlgebraClasses.BinaryPredicate; NarrowOther: AlgebraClasses.BinaryOp; CanNarrowOther: AlgebraClasses.BinaryPredicate; WidenThis: AlgebraClasses.UnaryOp; NarrowThis: AlgebraClasses.UnaryOp; WidenToGeneralExpression: AlgebraClasses.UnaryOp; LegalFirstChar: AlgebraClasses.LegalFirstCharOp; ElementRead: AlgebraClasses.ReadOp; ElementFromRope: AlgebraClasses.FromRopeOp; ElementToRope: AlgebraClasses.ToRopeOp; ElementLBKey: AlgebraClasses.ToRopeOp; ElementWrite: AlgebraClasses.WriteOp; Select: AlgebraClasses.BinaryOp; Insert: AlgebraClasses.BinaryOp; Length: AlgebraClasses.UnaryOp; UnaryOp: AlgebraClasses.UnaryOp; END. 4ASOrchardStructure.mesa Last Edited by Arnon: May 16, 1989 4:03:10 pm PDT Structure Constructor: make a Structure whose underlying set is an orchard of (possibly labeled, possibly labeled heap-ordered) rooted n-ary trees Element Representation Distributed representation, modelled on a distributed polynomial rep. The terms of a nonNIL Orchard are sorted in order of increasing hash code. The Nil Orchard is represented by OrchardData = NIL. Structure Representation Structure Constructors Arguments are the fields of a Structure Instance Data. RETURN[AlgebraClasses.MakeObject[class, MakeNameStructureData[data1, data2] ] ] Structure Selectors AlgebraClasses.GetStructureDataProc: TYPE = PROC [structure: Object] RETURNS [StructureData: REF ANY]; output is a NameStructureData Input is a structure, output is the data1 field of its StructureData (assuming this field is an Object) Input is a structure, output is the data2 field of its StructureData (assuming this field is an Object) Structure Operations AlgebraClasses.FlavorOp: TYPE = PROC [object: Object] RETURNS [flavor: Flavor]; AlgebraClasses.flavor: TYPE = { StructureElement, Structure, Class}; Looks (with ISTYPE) for ElementNameData and NameStructureData. Should be in both StructureElement and Structure class records. A functional expression that can be parsed and evaluated to reconstruct the structure A short identifying name, e.g. "Q" for the rational numbers LoganBerry primaryKey attribute value, for searching for this object in a LoganBerry db. Such keys are generated when an Object is to be offlined. selector: returns LIST[data1, data2] of a Name Structure Element Constructors Arguments are a list of OrchardTerms, assumed to be correctly ordered by hash code. Element Selectors AlgebraClasses.GetElementDataProc: TYPE = PROC [structureElement: Object] RETURNS [ElementData: REF ANY]; output is a ElementNameData Input is a structure, output is the field1 field of its ElementData (assuming this field is an Object) Input is a structure, output is the field2 field of its ElementData (assuming this field is an Object) Element Conversion and IO Previously called "Recast" Arguments are a StructureElement and a Structure. firstArg is intended to be an element of a "narrower" Structure than the one being defined by this interface, and secondArg is intended to be a Structure of the kind being defined by this interface. We attempt to widen firstArg to be an element of secondArg. If CanWidenOther[firstArg], then either we return firstArg unchanged (it is already an element of secondArg), or we create and return a new Object belonging to secondArg, i.e. we never modify the input Object. Previously called "CanRecast" Arguments are either a StructureElement and a Structure, or two Structures. firstArg is intended to be an element of, or be, a "narrower" Structure than the one being defined by this interface, and secondArg is intended to be a Structure of the kind being defined by this interface. Returns true if firstArg can be widened to be an element of secondArg. Arguments are a StructureElement and a Structure. firstArg is intended to be an element of a "wider" Structure than the one being defined by this interface, and secondArg is intended to be a Structure of the kind being defined by this interface. We attempt to narrow firstArg to be an element of secondArg. If CanNarrowOther[firstArg], then either we return firstArg unchanged (it is already an element of secondArg), or we create and return a new Object belonging to secondArg, i.e. we never modify the input Object. Arguments are either a StructureElement and a Structure, or two Structures. firstArg is intended to be an element of, or be, a "wider" Structure than the one being defined by this interface, and secondArg is intended to be a Structure of the kind being defined by this interface. Returns true if firstArg can be narrowed to be an element of secondArg. Argument is a StructureElement belonging to a Structure of the kind being defined by this interface. Either we return it unchanged, or we widen it to be an element of some "wider" Structure. In the latter case, we create a new Object, i.e. don't modify input. However it is expected that only General Expressions could ever be returned unchanged by a WidenThis proc, since it should be possible to widen anything else into a General Expression. For example, an integer can be widened to be a rational number. Usually a (nontrivial) WidenThis proc is written by knowing some tag with which the intended structure can be looked up (so we don't need to mention the Cedar interface that defines it), and then just applying that Structure's WidenOther proc to the argument. The basic AlgebraStructures method lookup procedure is to look for a method in this Object's class and all its superclasses, then set x _ WidenThis[input]; IF x.class.Equal[x, input] then FAIL else recursive call on x. Argument is a StructureElement belonging to a Structure of the kind being defined by this interface. Either we return it unchanged, or we narrow it to be an element of the narrowest possible "narrower" Structure. In the latter case, we create a new Object, i.e. don't modify input. For example, the NarrowThis proc for the rational numbers should return a BigInt for 3/1, but (the unchanged input argument) BigRat for 3/5. Expression evaluators are examples of NarrowThis procs. The fact that typically NarrowThis[V: Variable] looks for a value associated with V in some "environment", and if found, returns value.class.NarrowThis[value], is a detail that is entirely consistent with this assertion. Previously called "ToExpr: AlgebraClasses.ToExprOp"; Optional. A short cut to successive aplication of WidenThis procs until General Expressions reached. The Domain-dependent parser Write out an Element in such a form that the Domain-dependent parser can read it back in. LoganBerry primaryKey attribute value, for searching for this object in a LoganBerry db. Such keys are generated when an Object is to be offlined. Element Operations Args are an Orchard and hash code (an Int), returns the OrchardTerm in that tree with that hash code; return NIL if no such OrchardTerm found. Args are an OrchardTerm and an Orchard, returns the Orchard resulting from inserting that OrchardTerm into the given Orchard. Arg is an Orchard, returns the length (# of terms) in it (an Int). Ê¨˜Jšœ™Jšœ1™1J˜Jšœ’™’J™šÏk ˜ Icodešœ˜Kšœ˜Kšœ˜—Ihead2šÏnœž œœ˜%Jšœ˜headšž™Jšœ œ˜&J˜Jšœ œœœ ˜(J˜Jšœ›Ïcœ!œ™ÇJ˜Jšœ œœ˜'šœ œœ˜Jšœ%Ÿ&˜KJšœ˜Jšœ˜J˜—šœœœ˜J˜—Jšœ œœ ˜!šœ œœ˜JšœœŸ*˜>Jšœ œœœŸ˜J™—Jšžœ ˜1—šœ™šžœ˜(KšœS™SK™—Kšž œ žœœ œ œ œ œœ œ œ˜Z—šœ™šžœ$˜8Kšœ!œœœ™iKšœ œ œ™K™—šžœ˜!Kšœ$ œ œ.™hK™—šžœ˜!Kšœ$ œ œ.™h——šœ™šž œ˜$Jšœ™J™¶JšœÑ™ÑJ˜—šž œ!˜.Jšœ™J™âJ˜—šžœ˜%J™´JšœÒ™ÒJ˜—šžœ!˜/J™àJ˜—šž œ˜"Jšœ¿™¿J™?Jšœ žœâ™ƒJšœŠž œG™ÚJ™—šž œ˜#J™›JšœŒ™ŒJšœ•™•J™—šžœ˜1Jšœ4™4Jšœe™eJ™—šžœ"˜0J˜—šžœ˜#J™J˜—šžœ˜+J˜—šž œ˜'JšœY™YJ˜—šžœ˜&Kšœ”™”K˜—Jšžœ˜%—šœ™šžœ˜ Jšœ™J˜—šžœ˜ Jšœ}™}J™—šžœ˜JšœB™BJ™—šž œ˜"J˜——J˜Jšœ˜—…— à(¼