MathObjects.mesa
Copyright © 1989 by Xerox Corporation. All rights reserved.
Arnon, August 28, 1989 1:42:36 pm PDT
DIRECTORY
SafeStorage,
IO,
Atom,
Rope,
Basics,
Imager,
MathExpr;
MathObjects: CEDAR DEFINITIONS
= BEGIN
Types From Imported Interfaces
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;
Object Types
Object: TYPE = REF ObjectRec;
ObjectRec: TYPE = RECORD [
class: Object ← NIL,
data: REFNIL
];
We expect that .class of an "Element" is a Domain or View, .class of a Domain or View is a Category, and .class of a Category = NIL.
Method Types
The following data gets moved into IMPL, to be stored in global AList of method types and applicator functions
MethodType: TYPE = {Value, SideEffect, TrueNullaryOp, NullaryOp, UnaryOp, BinaryOp, BinaryMixedOp, TernaryOp, TernaryMixedOp, QuaternaryOp, LegalFirstCharOp, ReadOp, FromRopeOp, ToRopeOp, ToExprOp, FromExprOp, FromBOOLOp, FromINTOp, UnaryPredicate, BinaryPredicate, CompareToZeroOp, BinaryCompareOp, StructuredToGroundOp, ElementRankOp, UnaryImbedOp, BinaryImbedOp, ListImbedOp, MatrixImbedOp, StructureFromSetConstructor, VectorStructureConstructor, SequenceStructureConstructor, MatrixStructureConstructor, PolynomialStructureConstructor};
Properties can be implemented as Methods of type "Value"; but really should be stored using fields or a property list in the class's .data
Method: TYPE = REF MethodRec;
MethodRec: TYPE = RECORD [
staticType: ATOM,
name of method's "static signature", which is a specification of the numbers (arities) of its inputs and outputs, and some information about their "types". I.e. static signatures denote families of similar methods. Used for "dispatch on name of static signature" invocation of methods (following verfication that actual parameters conform to this method's "dynamic signature", which is computed afresh at each invocation of this method) via a global Alist of method types and corresponding method apply procs. The actual ATOM here is a selector into that global AList.
Static signatures themselves typically appear as a type declaration in some Cedar interface. Hence if some of this method's args are Cedar types (rather than Structures), that can automatically be expressed in a static signature.
Should the system be able to "verbalize" static signatures, so e.g. an external client can get them?
ApplyToObject: PROC [method: REF, structure: Object, argList: LIST OF Object, recast: BOOL] RETURNS[value: Object];
m: Method;
ok: BOOLTRUE;
IF NARROW[method, Method] THEN m ← method ELSE m ← LookupMethodInStructure[method, structure]; -- FALSE => method arg is actually an ATOM methodSelector; use it to lookup the method
IF recast THEN [ok, outArgs] ← RecastArgs[m, structure, argList] ELSE outArgs ← argList;
IF ok THEN
Using m.type, search global AList of method types and applicator functions; when found, pass m and outArgs to applicator; it will make appropriate extracts from outArgs, handling Cedar types and Objects appropriately in so doing, and pass the finalized input args to the dereferent of the appropriate narrowing of m.value.
ELSE ERROR;
attributes: Atom.PropList,
"constant" attributes stored e.g. as [$commutative, $commutative]; NIL value field would confuse with absence of attribute
dynamicType: REF UnaryToTwoListsOp ← NIL,
PROC [Structure] RETURNS [args: LIST OF arg Structures, results: LIST OF result Structures]
Dynamic type checking of Object args to this method; none done if = NIL.
Point of passing in a Structure (usually the Structure to which this method belongs) is that dynamic signatures are typically (uniquely) parametrized by it.
Construed as "desired" arg Structures: assume, for example, that the args of this method are expected to be Elements (and not Structures). Here is the processing we will do to RecastArgs. Consider arg A with Structure S (S is either a Domain or View). If desired Structure Q is a Domain, and Q # S, we try to convert A into Q by first trying Q's Widen and Narrow procs (for direct Sub or Super Domain relations), then try to find a path from S to Q in the global Domain lattice. We may fail and exit. If Q is a Category, let C be S's Category. First check Q = C, or Q is a superCategory of C via "basic" inheritance, or via the global Category lattice. If success, create a (new Structure which is a) View V of S as Q, and create a new Object whose class is V and whose data is A.data. Suppose Q is a View, with underlying Domain D. Suppose S is a Domain. Then, as above, see if S can be converted to D; if so, then make the appropriate new Object in Q corresponding to A. If S is a View, then let D' be its underlying Domain, see if D' can be converted to D as above; if so, make the appropriate new Object in Q corresponding to A.
Note that there are two ways to "widen" or "narrow" a View: one is to change its Domain, the other to change its Category.
If one or more args are expected to be Domains or Views, then their desired Structures must be Categories.
Perhaps want some way to selectively turn off the check for individual args. Note that can pass Domains like "GeneralExpressions" or "DomainAndViewElements" to be very permissive about args.
Perhaps want some way to specify Cedar types in Dynamic Signatures, e.g. REF, ROPE, or INT. Perhaps can have something like CedarType[INT], or CedarType[REF], in Dynamic Signatures. Then can either do no checking of Cedar-typed args, or actually try to do some kind of checking for them (perhaps whatever checking Cedar Interpreter can do).
If output LIST OF arg Structures has i < n = (# args this method) Structures, then args i, i+1, ..., n expected to belong to last (ith) Structure of the list (useful e.g. for vector and matrix constructors).
Should the system be able to "verbalize" dynamic signatures, so e.g. an external client can get them?
value: REF -- REF Proc
The "impl" of the method
];
MethodDictionary: TYPE = Atom.PropList;
Should MethodDictionary's, or some portion of the info in them, be "externalizable" , or Objects, so that a domain or category can report info about itself?
A method's methodKey, i.e. methodSelector, should serve as the method's "name" for any external purpose, e.g. user menu entry, or "logging" of a method application; should be identical to what some parser expects to be able to construct a MethodApplication object.
Note that we need to plan NOW for universal names, so we don't get into $sum, $Sum, $add confusions.
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];
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.