AlgebraClasses.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Arnon, March 4, 1986 12:02:24 pm PST
DIRECTORY
SafeStorage,
IO,
Atom,
Rope,
Basics,
Imager,
MathExpr;
AlgebraClasses: CEDAR DEFINITIONS
= BEGIN
Types From Imported Interfaces
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;
EXPR: TYPE = MathExpr.EXPR;
Object Types
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.ROPENIL, -- Structure => nonNIL
class: Object ← NIL, -- StructureElement => Structure; Structure => Class; Class => Class (the superclass)
data: REFNIL -- StructureElement => value; Structure => instanceData; Class => Method Dictionary
];
Method (and Property) Dictionary Types
Properties are thought of as Methods of type Value
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: BOOLTRUE, -- 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
];
Method Operations
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];
Does method lookup
DefaultDesiredArgStructures: UnaryToListOp;
RETURN[ LIST[structure] ]; (arg is expected to be a Structure)
GetMethodAndRecastArgs: PROC [methodSelector: ATOM, structure: Object, inArgs: LIST OF Object] RETURNS [ok: BOOL, method: Method, outArgs: LIST OF Object ← NIL];
Lookup method in structure, and recast args
RecastArgs: PROC [method: Method, structure: Object, inArgs: LIST OF Object] RETURNS [ok: BOOL, outArgs: LIST OF Object ← NIL];
Try to recast args
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];
LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]].
Error if anything at all goes wrong.
ApplyPredLkpRecast: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[BOOL];
ApplyNoLkpNoRecastRef: PROC [method: Method, argList: LIST OF Object] RETURNS[value: REF];
Apply method from structure. It is assumed that method exists, and that correct number and types of args are supplied.
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];
LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]].
Error if anything at all goes wrong.
ApplyLkpRecastRef: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: REF];
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.
ApplyNoLkpNoRecastObject: PROC [method: Method, argList: LIST OF Object] RETURNS[value: Object];
ERROR if method output type is not imbeddable as an 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];
LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]].
Error if anything at all goes wrong.
ApplyLkpRecastObject: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: Object];
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.
ApplyNoLkpNoRecastExpr: PROC [method: Method, argList: LIST OF Object] RETURNS[value: EXPR];
RETURN[NARROW[ApplyNoLkpNoRecastRef]].
Error if anything at all goes wrong.
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];
LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]].
Error if anything at all goes wrong.
ApplyLkpNoRecastExpr: PROC [methodSelector: ATOM, structure: Object, argList: LIST OF Object] RETURNS[value: EXPR];
LookupMethodForStructure, RETURN[NARROW[ApplyNoLkpNoRecastRef]].
Error if anything at all goes wrong.
Object (all Flavors) Operation Types
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];
Class Operations
MakeClass: PROC [name: Rope.ROPE, superClass: Object, methodDictionary: MethodDictionary ← NIL] RETURNS[class: Object];
Typically a class is created with MethodDictionary = NIL, then MethodDictionary loaded with AddMethodToClass
AddMethodToClass: PROC [methodSelector: ATOM, method: Method, class: Object];
Existing method, if any (generally there shouldn't be), is replaced
SetSuperClass: PROC [object: Object, superClass: Object];
Sets class field of a Class, or class.class field of a Structure
LookupMethodInClass: PROC [methodSelector: ATOM, class: Object] RETURNS[method: Method];
Look up method in this class and its superclasses.
BuildClassOperators: PROC [class: Object] RETURNS[opNames: LIST OF ROPE, operators: LIST OF Method];
Structure Categories
Category: TYPE ~ {set, lattice, group, ring, field, module, vectorSpace, algebra, divisionAlgebra};
Structure Operation Types
PrintNameProc: TYPE = PROC [structure: Object] RETURNS [Rope.ROPE]; -- redundant with ToRopeOp
Identify the particular structure to the world.
StructureToExprOp: TYPE = PROC [structure: Object] RETURNS [out: EXPR];
StructureEqualityTest: TYPE = PROC [thisStructure, otherStructure: Object] RETURNS [BOOL];
Test whether some other structure is the same algebraic domain as this one
StructureRankOp: TYPE = PROC [structure: Object] RETURNS [CARDINAL];
For things like ring characteristic (smallest positive integer k such that k*1 = 0; 0 if k infinite) and vector space dimension.
ReportOpsProc: TYPE = PROC [structure: Object] RETURNS [opNames: LIST OF Rope.ROPE, refOps: LIST OF REF];
Report structure operations to outside world, e.g. a user interface
Should be made a concrete proc to be applied to method dictionaries
BinaryStructureLUBOp: TYPE = PROC [firstStructure, secondStructure: Object] RETURNS [LUBStructure: Object];
If either Structure NIL, return other
Structure Constructor Types
StructureFromSetConstructor: TYPE = PROC [set: Object] RETURNS [structure: Object];
Make a Structure whose (finite) underlying set is the given argument.
VectorStructureConstructor: TYPE = PROC [coordinateStructure: Object, dimension: NAT, row: BOOLTRUE] RETURNS [vectorStructure: Object];
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.
SequenceStructureConstructor: TYPE = PROC [elementStructure: Object, row: BOOLTRUE] RETURNS [sequenceStructure: Object];
A particular sequence structure is defined by its elementStructure, which can be any Structure, and whether its elements are displayed as rows or columns.
MatrixStructureConstructor: TYPE = PROC [elementStructure: Object, nRows, nCols: NAT] RETURNS [matrixStructure: Object];
A particular matrix structure is defined by its elementStructure and its nRows, nCols. elementStructure can be a ring, field, algebra, or divisionAlgebra.
PolynomialStructureConstructor: TYPE = PROC [coeffRing, variableSeq: Object] RETURNS [polynomialStructure: Object];
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
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];
RETURN[structure1.name = structure2.name]
LookupMethodInStructure: PROC [methodSelector: ATOM, structure: Object] RETURNS[Method];
LookupMethodInClass[structure.class]
LookupMethodInAllStructures: PROC [methodSelector: ATOM] RETURNS[method: Method, structure: Object];
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.
ResetStructureRegistry: PROC[];
InstallStructure: PROC[structure: Object];
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.
LookupStructure: PROC[name: ROPE] RETURNS[structure: Object];
effects: Returns the Structure Object associated with name.
returns NIL if not found
KillStructure: PROC[name: ROPE];
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
LegalFirstCharOp: TYPE = PROC [char: CHAR, structure: Object] RETURNS [BOOL];
True if char is legal first char in an external rep of a structure element.
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];
Since no object arg, need a hook to structure
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];
For things like determinant and coefficient extraction
ElementRankOp: TYPE = PROC [arg: Object] RETURNS [CARDINAL];
For things like degree functions in euclidean domains, rank of matrices
Display2DOp: TYPE = PROC [object: Object, context: Imager.Context, dotWidth, segmentWidth: REAL];
Display an object in a 2D context.
StructureElement Operations
Copy: UnaryOp;
ElementOf: PROC [object: Object, structure: Object] RETURNS [BOOL];
True if object is an element of structure. (check equality of its structure's name with this structure's name)
StructureElement Creation Types
UnaryImbedOp: TYPE = PROC [in: Object, structure: Object] RETURNS [out: Object];
Imbed in as an element of structure
BinaryImbedOp: TYPE = PROC [data1: Object, data2: REF, structure: Object] RETURNS [out: Object];
Construct an element of structure from data1 and data2.
Sample use: constructing a term of a polynomial.
ListImbedOp: TYPE = PROC [data: LIST OF Object, structure: Object] RETURNS [out: Object];
Construct an element of a point, sequence, or vector Structure from data
MatrixImbedOp: TYPE = PROC [elements: LIST OF Object, structure: Object] RETURNS [out: Object];
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.ROPENIL,
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: BOOLTRUE,
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: BOOLFALSE, -- 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: BOOLFALSE,
complement: UnaryOp ← NIL,
Ordered structure ops (rings, fields, modules, vectorSpaces, algebras, divisionAlgebras only)
ordered: BOOLFALSE,
sign: CompareToZeroOp ← NIL,
abs: UnaryOp ← NIL,
compare: BinaryCompareOp ← NIL,
Common varieties of rings (and algebras) and their ops
integralDomain: BOOLFALSE,
gcdDomain: BOOLFALSE,
gcd: BinaryOp ← NIL, -- gcdDomains only
euclideanDomain: BOOLFALSE,
remainder: BinaryOp ← NIL, -- euclideanDomains only
degree: ElementRankOp ← NIL, -- euclideanDomains only
Common varieties of fields (and divisionAlgebras) and their ops
completeField: BOOLFALSE,
realField: BOOLFALSE,
realClosedField: BOOLFALSE,
algebraicallyClosedField: BOOLFALSE,
propList: Atom.PropList ← NIL
];
END.