[Indigo]<CaminoReal>AlgebraClasses.mesa!1

AlgebraClasses.mesa

Arnon, March 4, 1986 12:02:24 pm PST

DIRECTORY

SafeStorage,

IO,

Atom,

Rope,

Basics,

MathExpr;

AlgebraClasses: CEDAR DEFINITIONS

= BEGIN

Objects

Object: TYPE = REF ObjectRec;

ObjectRec: TYPE = RECORD [

name: Rope.ROPE ← NIL, -- hook onto this particular object

structure: Structure,

propList: Atom.PropList ← NIL,

data: REF ← NIL

];

Structures

Structure: TYPE = REF StructureRec;

StructureRec: TYPE = RECORD [

class: StructureClass,

instanceData: REF ← NIL

];

Structure Classes

Category: TYPE = {set, lattice, group, ring, field, module, vectorSpace, algebra, divisionAlgebra};

StructureClass: TYPE = REF StructureClassRec;

StructureClassRec: TYPE = RECORD [

Structure properties

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"

printName: PrintNameProc,

shortPrintName: PrintNameProc, -- if none, should be set to printName

hashCode: CARDINAL ← 0, -- for quick checks of structure equality

structureEqual: StructureEqualityTest,

characteristic: StructureRankOp ← NIL, -- rings, fields, modules, vector spaces, algebras, divisionAlgebras only

dimension: StructureRankOp ← NIL,-- modules, vector spaces, algebras, divisionAlgebras only

Test whether a given item belongs to this structure (run-time typechecking)

isElementOf: ElementOfProc,

I/O and Conversion

legalFirstChar: LegalFirstCharOp,

read: ReadOp,

fromRope: FromRopeOp,

toRope: ToRopeOp,

write: WriteOp,

fromExpr: FromExprOp ← NIL,

toExpr: ToExprOp ← NIL,

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

Modules

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,

Some common varieties of rings (and algebras)

integralDomain: BOOL ← FALSE,

gcdDomain: BOOL ← FALSE,

gcd: BinaryOp ← NIL, -- gcdDomains only

euclideanDomain: BOOL ← FALSE,

remainder: BinaryOp ← NIL, -- euclideanDomains only

degree: ElementRankOp ← NIL, -- euclideanDomains only

Some common varieties of fields (and divisionAlgebras)

completeField: BOOL ← FALSE,

realField: BOOL ← FALSE,

realClosedField: BOOL ← FALSE,

algebraicallyClosedField: BOOL ← FALSE,

propList: Atom.PropList ← NIL

];

Operations on Structures

PrintNameProc: TYPE = PROC [structure: Structure] RETURNS [Rope.ROPE];

Identify the particular structure to the world.

StructureEqualityTest: TYPE = PROC [thisStructure, otherStructure: Structure] RETURNS [BOOL];

Test whether some other structure is the same algebraic domain as this one

defaultStructureEqualityTest: StructureEqualityTest;

StructureRankOp: TYPE = PROC [structure: Structure] RETURNS [CARDINAL];

For things like ring characteristic (smallest positive integer k such that k*1 = 0; 0 if k infinite) and vector space dimension.

StructureCategoryToRope: PROC [category: Category] RETURNS [rope: Rope.ROPE];

GetProperty: PROC [structure: Structure, prop: ATOM] RETURNS [val: REF];

Retrieve from property list

Operations on Elements of Structures

ElementOfProc: TYPE = PROC [item: Object, structure: Structure] RETURNS [BOOL];

True if item is an element of the structure.

defaultElementOfProc: ElementOfProc;

LegalFirstCharOp: TYPE = PROC [char: CHAR, structure: Structure] RETURNS [BOOL];

True if char is legal first char in an external rep of a structure element.

ReadOp: TYPE = PROC [in: IO.STREAM, structure: Structure] RETURNS [out: Object];

FromRopeOp: TYPE = PROC [in: Rope.ROPE, structure: Structure] RETURNS [out: Object];

ToRopeOp: TYPE = PROC [in: Object] RETURNS [out: Rope.ROPE];

WriteOp: TYPE = PROC [stream: IO.STREAM, in: Object];

FromExprOp: TYPE = PROC [in: MathExpr.EXPR, structure: Structure] RETURNS [out: Object];

ToExprOp: TYPE = PROC [in: Object] RETURNS [out: MathExpr.EXPR];

NullaryOp: TYPE = PROC[structure: Structure] RETURNS [result: Object];

Since no object arg, need a hook to structure

UnaryOp: TYPE = PROC [arg: Object] RETURNS [result: Object];

BinaryOp: TYPE = PROC [firstArg, secondArg: Object] RETURNS [result: Object];

EqualityOp: TYPE = PROC [firstArg, secondArg: Object] RETURNS [BOOL];

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

Construct an element of one Structure from element(s) of another

UnaryImbedOp should suffice in most instances (e.g. diagonal matrix); BinaryImbedOp is e.g. for constructing a term of a polynomial.

UnaryImbedOp: TYPE = PROC [in: Object, structure: Structure] RETURNS [out: Object];

Imbed in as an element of structure

BinaryImbedOp: TYPE = PROC [data1: Object, data2: REF, structure: Structure] RETURNS [out: Object];

Construct an element of structure from data1 and data2

END.