[Indigo]<AlgebraStructures>AlgebraClasses.mesa!3

AlgebraClasses.mesa

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.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

];

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: 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

];

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: BOOL ← TRUE] 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: BOOL ← TRUE] 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.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

];

END.