DIRECTORY SafeStorage, IO, Atom, Rope, Basics, Imager, MathExpr; AlgebraClasses: CEDAR DEFINITIONS = BEGIN ROPE: TYPE = Rope.ROPE; STREAM: TYPE = IO.STREAM; EXPR: TYPE = MathExpr.EXPR; ObjectFlavor: TYPE = {StructureElement, Structure, Class, NoFlavor}; Object: TYPE = REF ObjectRec; ObjectRec: TYPE = RECORD [ flavor: ObjectFlavor, -- 3/87 unclear this field needed; even if so, could bundle it into name field; all in all, redundant. name: Rope.ROPE _ NIL, -- Structure => nonNIL class: Object _ NIL, -- StructureElement => Structure; Structure => Class; Class => Class (the superclass) data: REF _ NIL -- StructureElement => value; Structure => instanceData; Class => Method Dictionary ]; MethodDictionary: TYPE = Atom.PropList; MethodType: TYPE = {Value, SideEffect, TrueNullaryOp, NullaryOp, UnaryOp, BinaryOp, BinaryMixedOp, TernaryOp, TernaryMixedOp, QuaternaryOp, NaryOp, LegalFirstCharOp, ReadOp, FromRopeOp, ToRopeOp, ToExprOp, FromExprOp, FromBOOLOp, FromINTOp, UnaryPredicate, BinaryPredicate, CompareToZeroOp, BinaryCompareOp, StructuredToGroundOp, ElementRankOp, UnaryImbedOp, BinaryImbedOp, ListImbedOp, MatrixImbedOp, StructureFromSetConstructor, VectorStructureConstructor, SequenceStructureConstructor, MatrixStructureConstructor, PolynomialStructureConstructor}; Method: TYPE = REF MethodRec; MethodRec: TYPE = RECORD [ type: MethodType, operator: BOOL _ TRUE, -- TRUE if this method is an Operator, as opposed to a Constructor. Only Operators are offered in a user menu of a Structure's methods value: REF, -- REF proc if type # Value; should never be NIL, since confuses with absence of method. If don't care about Value, set value _ methodKey desiredArgStructures: REF UnaryToListOp _ NIL, -- Proc[Structure -> LIST OF Structure]; if ouptut LIST contains only one Structure, then expected that all args belong to it (useful e.g. for vector and matrix constructors). doc: ROPE ]; MakeMethod: PROC [type: MethodType, operator: BOOL, value: REF, desiredArgStructures: REF UnaryToListOp, doc: ROPE] RETURNS[Method]; DesiredArgStructures: PROC [methodSelector: ATOM, structure: Object] RETURNS[LIST OF Object]; DefaultDesiredArgStructures: UnaryToListOp; GetMethodAndRecastArgs: PROC [methodSelector: ATOM, structure: Object, inArgs: LIST OF Object] RETURNS [ok: BOOL, method: Method, outArgs: LIST OF Object _ NIL]; RecastArgs: PROC [method: Method, structure: Object, inArgs: LIST OF Object] RETURNS [ok: BOOL, outArgs: LIST OF Object _ NIL]; ApplyLegalFirstCharMethod: PROC [method: Method, char: CHAR, structure: Object _ NIL] RETURNS[BOOL]; ApplyFromRopeMethod: PROC [method: Method, in: ROPE, structure: Object _ NIL] RETURNS[Object]; ApplyReadMethod: PROC [method: Method, in: STREAM, structure: Object _ NIL] RETURNS[Object]; ApplyFromExprMethod: PROC [method: Method, in: EXPR, structure: Object] RETURNS[Object]; ApplyCompareToZeroMethod: PROC [method: Method, arg: Object] RETURNS[Basics.Comparison]; ApplyBinaryCompareMethod: PROC [method: Method, firstArg, secondArg: Object] RETURNS[Basics.Comparison]; ApplyBinaryImbedMethod: PROC [method: Method, data1: Object, data2: REF, structure: Object] RETURNS[Object]; ApplyMixedMethod: PROC [method: Method, objectArgs: LIST OF Object, refArg: REF] RETURNS[Object]; ApplyPredNoLkpNoRecast: PROC [method: Method, argList: LIST OF Object] RETURNS[BOOL]; ApplyPredNoLkpRecast: PROC [method: Method, structure: Object, argList: LIST OF Object] RETURNS[BOOL]; ApplyPredLkpNoRecast: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[BOOL]; ApplyPredLkpRecast: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[BOOL]; ApplyNoLkpNoRecastRef: PROC [method: Method, argList: LIST OF Object] RETURNS[value: REF]; ApplyNoLkpRecastRef: PROC [method: Method, structure: Object, argList: LIST OF Object] RETURNS[value: REF]; ApplyLkpNoRecastRef: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: REF]; ApplyLkpRecastRef: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: REF]; ApplyNoLkpNoRecastObject: PROC [method: Method, argList: LIST OF Object] RETURNS[value: Object]; ApplyNoLkpRecastObject: PROC [method: Method, structure: Object, argList: LIST OF Object] RETURNS[value: Object]; ApplyLkpNoRecastObject: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: Object]; ApplyLkpRecastObject: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: Object]; ApplyNoLkpNoRecastExpr: PROC [method: Method, argList: LIST OF Object] RETURNS[value: EXPR]; ApplyNoLkpRecastExpr: PROC [method: Method, structure: Object, argList: LIST OF Object] RETURNS[value: EXPR]; ApplyLkpRecastExpr: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: EXPR]; ApplyLkpNoRecastExpr: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: EXPR]; SideEffect: TYPE = PROC [] RETURNS []; TrueNullaryOp: TYPE = PROC [] RETURNS [result: Object]; UnaryOp: TYPE = PROC [arg: Object] RETURNS [result: Object]; UnaryPredicate: TYPE = PROC [arg: Object] RETURNS [BOOL]; UnaryInPlaceOp: TYPE = PROC [arg: Object]; UnaryToListOp: TYPE = PROC [arg: Object] RETURNS [result: LIST OF Object]; BinaryOp: TYPE = PROC [firstArg, secondArg: Object] RETURNS [result: Object]; BinaryPredicate: TYPE = PROC [firstArg, secondArg: Object] RETURNS [BOOL]; EqualityOp: TYPE = PROC [firstArg, secondArg: Object] RETURNS [BOOL]; -- redundant BinaryInPlaceOp: TYPE = PROC [firstArg: Object, secondArg: REF]; BinaryMixedOp: TYPE = PROC [firstArg: Object, secondArg: REF] RETURNS [result: Object]; BinaryToPairOp: TYPE = PROC [firstArg: Object, secondArg: REF] RETURNS [firstResult, secondResult: Object]; TernaryOp: TYPE = PROC [firstArg, secondArg, thirdArg: Object] RETURNS [result: Object]; TernaryMixedOp: TYPE = PROC [firstArg, secondArg: Object, thirdArg: REF] RETURNS [result: Object]; QuaternaryOp: TYPE = PROC [firstArg, secondArg, thirdArg, fourthArg: Object] RETURNS [result: Object]; NaryOp: TYPE = PROC [args: LIST OF Object] RETURNS [result: Object]; MakeClass: PROC [name: Rope.ROPE, superClass: Object, methodDictionary: MethodDictionary _ NIL] RETURNS[class: Object]; AddMethodToClass: PROC [methodSelector: ATOM, method: Method, class: Object]; SetSuperClass: PROC [object: Object, superClass: Object]; LookupMethodInClass: PROC [methodSelector: ATOM, class: Object] RETURNS[method: Method]; BuildClassOperators: PROC [class: Object] RETURNS[opNames: LIST OF ROPE, operators: LIST OF Method]; Category: TYPE ~ {set, lattice, group, ring, field, module, vectorSpace, algebra, divisionAlgebra}; PrintNameProc: TYPE = PROC [structure: Object] RETURNS [Rope.ROPE]; -- redundant with ToRopeOp StructureToExprOp: TYPE = PROC [structure: Object] RETURNS [out: EXPR]; StructureEqualityTest: TYPE = PROC [thisStructure, otherStructure: Object] RETURNS [BOOL]; StructureRankOp: TYPE = PROC [structure: Object] RETURNS [CARDINAL]; ReportOpsProc: TYPE = PROC [structure: Object] RETURNS [opNames: LIST OF Rope.ROPE, refOps: LIST OF REF]; BinaryStructureLUBOp: TYPE = PROC [firstStructure, secondStructure: Object] RETURNS [LUBStructure: Object]; StructureFromSetConstructor: TYPE = PROC [set: Object] RETURNS [structure: Object]; VectorStructureConstructor: TYPE = PROC [coordinateStructure: Object, dimension: NAT, row: BOOL _ TRUE] RETURNS [vectorStructure: Object]; SequenceStructureConstructor: TYPE = PROC [elementStructure: Object, row: BOOL _ TRUE] RETURNS [sequenceStructure: Object]; MatrixStructureConstructor: TYPE = PROC [elementStructure: Object, nRows, nCols: NAT] RETURNS [matrixStructure: Object]; PolynomialStructureConstructor: TYPE = PROC [coeffRing, variableSeq: Object] RETURNS [polynomialStructure: Object]; IsCategory: PROC [structure: Object, category: Category] RETURNS [BOOL]; HasProperty: PROC [structure: Object, property: ATOM] RETURNS [BOOL]; MakeStructure: PROC [name: Rope.ROPE, class: Object, instanceData: REF] RETURNS[structure: Object]; StructureEqual: PROC [structure1, structure2: Object] RETURNS [BOOL]; LookupMethodInStructure: PROC [methodSelector: ATOM, structure: Object] RETURNS[Method]; LookupMethodInAllStructures: PROC [methodSelector: ATOM] RETURNS[method: Method, structure: Object]; ResetStructureRegistry: PROC[]; InstallStructure: PROC[structure: Object]; LookupStructure: PROC[name: ROPE] RETURNS[structure: Object]; KillStructure: PROC[name: ROPE]; LegalFirstCharOp: TYPE = PROC [char: CHAR, structure: Object] RETURNS [BOOL]; ReadOp: TYPE = PROC [in: IO.STREAM, structure: Object _ NIL] RETURNS [out: Object]; FromRopeOp: TYPE = PROC [in: Rope.ROPE, structure: Object _ NIL] RETURNS [out: Object]; ToRopeOp: TYPE = PROC [in: Object] RETURNS [out: Rope.ROPE]; WriteOp: TYPE = PROC [stream: IO.STREAM, in: Object]; FromExprOp: TYPE = PROC [in: EXPR, structure: Object] RETURNS [out: Object]; ToExprOp: TYPE = PROC [in: Object] RETURNS [out: EXPR]; FromBOOLOp: TYPE = PROC [in: BOOL, structure: Object _ NIL] RETURNS [out: Object]; FromINTOp: TYPE = PROC [in: INT, structure: Object _ NIL] RETURNS [out: Object]; NullaryOp: TYPE = PROC[structure: Object] RETURNS [result: Object]; CompareToZeroOp: TYPE = PROC [arg: Object] RETURNS [Basics.Comparison]; BinaryCompareOp: TYPE = PROC [firstArg, secondArg: Object] RETURNS [Basics.Comparison]; StructuredToGroundOp: TYPE = PROC [structuredElt: Object] RETURNS [groundElement: Object]; ElementRankOp: TYPE = PROC [arg: Object] RETURNS [CARDINAL]; Display2DOp: TYPE = PROC [object: Object, context: Imager.Context, dotWidth, segmentWidth: REAL]; Copy: UnaryOp; ElementOf: PROC [object: Object, structure: Object] RETURNS [BOOL]; UnaryImbedOp: TYPE = PROC [in: Object, structure: Object] RETURNS [out: Object]; BinaryImbedOp: TYPE = PROC [data1: Object, data2: REF, structure: Object] RETURNS [out: Object]; ListImbedOp: TYPE = PROC [data: LIST OF Object, structure: Object] RETURNS [out: Object]; MatrixImbedOp: TYPE = PROC [elements: LIST OF Object, structure: Object] RETURNS [out: Object]; END. !€AlgebraClasses.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Arnon, March 4, 1986 12:02:24 pm PST Types From Imported Interfaces Object Types Method (and Property) Dictionary Types Properties are thought of as Methods of type Value Method Operations Does method lookup RETURN[ LIST[structure] ]; (arg is expected to be a Structure) Lookup method in structure, and recast args Try to recast args LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]]. Error if anything at all goes wrong. Apply method from structure. It is assumed that method exists, and that correct number and types of args are supplied. LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]]. Error if anything at all goes wrong. ApplyNoLkpNoRecastRef[GetMethodAndRecastArgs]; It is assumed that method exists, that correct number of args are supplied, and that args are recastable to desiredArgStructure. Error if anything at all goes wrong. ERROR if method output type is not imbeddable as an Object LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]]. Error if anything at all goes wrong. ApplyNoLkpNoRecastObject[GetMethodAndRecastArgs]; It is assumed that method exists, that correct number of args are supplied, and that args are recastable to desiredArgStructure. Error if anything at all goes wrong. RETURN[NARROW[ApplyNoLkpNoRecastRef]]. Error if anything at all goes wrong. LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]]. Error if anything at all goes wrong. LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]]. Error if anything at all goes wrong. Object (all Flavors) Operation Types Class Operations Typically a class is created with MethodDictionary = NIL, then MethodDictionary loaded with AddMethodToClass Existing method, if any (generally there shouldn't be), is replaced Sets class field of a Class, or class.class field of a Structure Look up method in this class and its superclasses. Structure Categories Structure Operation Types Identify the particular structure to the world. Test whether some other structure is the same algebraic domain as this one For things like ring characteristic (smallest positive integer k such that k*1 = 0; 0 if k infinite) and vector space dimension. Report structure operations to outside world, e.g. a user interface Should be made a concrete proc to be applied to method dictionaries If either Structure NIL, return other Structure Constructor Types Make a Structure whose (finite) underlying set is the given argument. A particular vector structure is defined by its coordinateStructure, which can be any Structure, its dimension, and whether its elements are displayed as rows or columns. A particular sequence structure is defined by its elementStructure, which can be any Structure, and whether its elements are displayed as rows or columns. A particular matrix structure is defined by its elementStructure and its nRows, nCols. elementStructure can be a ring, field, algebra, or divisionAlgebra. A particular polynomial structure is defined by its coeffRing and its variables. coeffRing can be a ring, field, algebra, or divisionAlgebra. variableSeq is a sequence of any length, and the right thing happens. Structure Operations RETURN[structure1.name = structure2.name] LookupMethodInClass[structure.class] Linear search of StructureRegistry, LookupMethodForStructure until found or EOF. If found, then structure is Structure where found. Returns [NIL, NIL] if not found. Structure Registry Structures have nonNIL names. Mathematically different Structures have different names. A central registry of Structures is kept, and we never have more than one instance of a given mathematical structure in existence. effects: Installs structure in global StructureRegistry database. Replaces existing occurrence of a Structure with same name, if any, and otherwise places structure at the tail of StructureRegistry. effects: Returns the Structure Object associated with name. returns NIL if not found effects: delete structure from global StructureRegistry DataBase, if present. Only needed when want to delete a given Structure name entirely, not if just want to replace. StructureElement Operation Types True if char is legal first char in an external rep of a structure element. Since no object arg, need a hook to structure For things like determinant and coefficient extraction For things like degree functions in euclidean domains, rank of matrices Display an object in a 2D context. StructureElement Operations True if object is an element of structure. (check equality of its structure's name with this structure's name) StructureElement Creation Types Imbed in as an element of structure Construct an element of structure from data1 and data2. Sample use: constructing a term of a polynomial. Construct an element of a point, sequence, or vector Structure from data Construct an element of a matrix Structure from data. Assumes that correct number of elements supplied, in correct order, and that each element supplied belongs to structure.elementStructure *Old* Structure Class Record Defn Category: TYPE = {set, lattice, group, ring, field, module, vectorSpace, algebra, divisionAlgebra}; ClassData: TYPE = REF ClassDataRec; ClassDataRec: TYPE = RECORD [ Structure properties and operations category: Category, flavor: Rope.ROPE _ NIL, Flavor identifies outermost constructor (if any) used to build objects of this structure. Is a rope to allow expansion without interface changes. Examples: "Ints" "BigRats" "Points" "Polynomials" "Matrices" "Quotients" "Structures" printName: PrintNameProc, longNameGenerator: PrintNameProc, shortPrintName: PrintNameProc, -- if none, should be set to printName shortNameGenerator: PrintNameProc, -- if none, should be set to printName code: Rope.ROPE, -- for quick checks of structure equality structureEqual: StructureEqualityTest, -- should use codes characteristic: StructureRankOp _ NIL, -- rings, fields, modules, vector spaces, algebras, divisionAlgebras only dimension: StructureRankOp _ NIL,-- modules, vector spaces, algebras, divisionAlgebras only reportOps: ReportOpsProc _ NIL, Test whether a given item belongs to this structure (run-time typechecking): check equality of its structure's code with this structure's code. isElementOf: ElementOfProc, I/O and Conversion of Structure elements legalFirstChar: LegalFirstCharOp, read: ReadOp, fromRope: FromRopeOp, toRope: ToRopeOp, write: WriteOp, fromExpr: FromExprOp _ NIL, toExpr: ToExprOp _ NIL, toIndexRope: ToRopeOp, -- print short object key (for use in sequences of objects) recast: UnaryImbedOp _ NIL, -- convert an element of a structure that conforms to this one (should be a noop on elements of this structure). Should use fastest available determination of structure, e.g. hashCode or shortPrintName. Addition (lattices, rings, fields, vectorSpaces, algebras, divisionAlgebras only) add: BinaryOp _ NIL, negate: UnaryOp _ NIL, subtract: BinaryOp _ NIL, zero: NullaryOp _ NIL, Multiplication (lattices, groups, rings, fields, algebras, divisionAlgebras only) multiply: BinaryOp _ NIL, -- assumed associative; commutative or noncommutative ok commutative: BOOL _ TRUE, invert: UnaryOp _ NIL, divide: BinaryOp _ NIL, -- (lattices only) set difference operation goes here if appropriate one: NullaryOp, Equality testing equal: EqualityOp _ NIL, -- need not be present in sets and lattices Module ops rightModule: BOOL _ FALSE, -- modules are left modules by default Scalar multiplication (modules, vectorSpaces, algebras, divisionAlgebras only) scalarMultiply: BinaryOp _ NIL, -- unless rightModule, this is left multiplication, i.e. scalar * vector. The underlying field of a vector space may be commutative or noncommutative. Lattice ops booleanAlgebra: BOOL _ FALSE, complement: UnaryOp _ NIL, Ordered structure ops (rings, fields, modules, vectorSpaces, algebras, divisionAlgebras only) ordered: BOOL _ FALSE, sign: CompareToZeroOp _ NIL, abs: UnaryOp _ NIL, compare: BinaryCompareOp _ NIL, Common varieties of rings (and algebras) and their ops integralDomain: BOOL _ FALSE, gcdDomain: BOOL _ FALSE, gcd: BinaryOp _ NIL, -- gcdDomains only euclideanDomain: BOOL _ FALSE, remainder: BinaryOp _ NIL, -- euclideanDomains only degree: ElementRankOp _ NIL, -- euclideanDomains only Common varieties of fields (and divisionAlgebras) and their ops completeField: BOOL _ FALSE, realField: BOOL _ FALSE, realClosedField: BOOL _ FALSE, algebraicallyClosedField: BOOL _ FALSE, propList: Atom.PropList _ NIL ]; Κš– "Mesa" style˜codešœΟc™Kšœ Οmœ1™