[Indigo]<QuantifierElimination>SamplePointsImpl.mesa!1

SamplePointsImpl.mesa

Last Edited by: Arnon, July 19, 1985 2:54:46 pm PDT

DIRECTORY

Rope,

Atom,

IO,

Convert,

MathExpr,

MathConstructors,

AlgebraClasses,

Ints,

BigRats,

RatIntervals,

Variables,

Polynomials,

AlgebraicNumbers,

ExtensionFields,

Points,

SamplePoints;

SamplePointsImpl: CEDAR PROGRAM

IMPORTS Rope, Atom, IO, AlgebraClasses, RatIntervals, Polynomials, AlgebraicNumbers, ExtensionFields, MathConstructors, Variables, Points

EXPORTS SamplePoints =

BEGIN OPEN AC: AlgebraClasses, BR: BigRats, RI: RatIntervals, VARS: Variables, AN: AlgebraicNumbers, PTS: Points, POL: Polynomials, AN: AlgebraicNumbers, EF: ExtensionFields, SamplePoints;

Errors

SyntaxError: PUBLIC ERROR [reason: ATOM] = CODE;

BadElementStructure: PUBLIC ERROR [elementStructure: AC.Structure] = CODE;

TypeError: PUBLIC ERROR [message: ATOM ← $Unspecified] = CODE;

Class for SamplePoint Structures

ClassPrintName: AC.PrintNameProc = {

data: SamplePointStructureData ← NARROW[structure.instanceData];

RETURN[Rope.Cat[

"Sample Points over",

data.inputPolynomialRing.class.printName[data.inputPolynomialRing],

" and ",

data.minPolyRing.class.printName[data.minPolyRing]

] ];

};

ClassShortPrintName: AC.PrintNameProc = {

data: SamplePointStructureData ← NARROW[structure.instanceData];

RETURN[Rope.Cat[

"SP(",

data.inputPolynomialRing.class.shortPrintName[data.inputPolynomialRing],

" , ",

data.minPolyRing.class.shortPrintName[data.minPolyRing],

")"

] ];

};

ClassIsElementOf: AC.ElementOfProc = {

Assumes that if item is a samplePoint, then it really belongs to the domain pointed to by its structure field.

IF NOT structure.class.structureEqual[structure, item.structure] THEN RETURN[FALSE];

RETURN[ TRUE ]

};

ClassLegalFirstChar: AC.LegalFirstCharOp = {

SELECT char FROM

'[ , '(=> RETURN[TRUE];

ENDCASE;

RETURN[FALSE];

};

ClassToExpr: AC.ToExprOp = {

samplePointStructureData: SamplePointStructureData ← NARROW[in.structure.instanceData];

minPolyRing: AC.Structure ← samplePointStructureData.minPolyRing;

RealAlgebraicNumbers: AC.Structure ← AN.MakeFieldOfAlgebraicNumbers[samplePointStructureData.minPolyRing, TRUE];

inData: SamplePointData ← NARROW[in.data];

outColumn, tail: LIST OF MathExpr.EXPR ← NIL;

colLength: CARDINAL;

IF inData=NIL THEN {

out ← MathConstructors.MakeVector[1, LIST[MathConstructors.MakeVariable["NILSAMPLEPOINT"]], FALSE];

RETURN;

};

IF inData.basePoint # NIL THEN {

pointStructure: AC.Structure ← inData.basePoint.structure;

definingPolynomial: AC.Object ← inData.definingPolynomial;

pointStructureData: PTS.PointStructureData ← NARROW[inData.basePoint.structure.instanceData];

extensionFieldData: EF.ExtensionFieldData ← NARROW[pointStructureData.coordinateStructure.instanceData];

outColumn ← tail ← LIST[MathConstructors.MakeVariable["EXTENDEDSAMPLEPOINT"] ];

tail ← tail.rest ← LIST[MathConstructors.MakeVariable["PRIMITIVEELEMENT"] ];

tail ← tail.rest ← LIST[RealAlgebraicNumbers.class.toExpr[extensionFieldData.primitiveElement] ];

tail ← tail.rest ← LIST[MathConstructors.MakeVariable["BASEPOINT"] ];

tail ← tail.rest ← LIST[pointStructure.class.toExpr[inData.basePoint] ];

tail ← tail.rest ← LIST[MathConstructors.MakeVariable["DEFININGPOLYNOMIAL"] ];

tail ← tail.rest ← LIST[definingPolynomial.structure.class.toExpr[definingPolynomial] ];

tail ← tail.rest ← LIST[MathConstructors.MakeVariable["ISOLATINGINTERVAL"] ];

tail ← tail.rest ← LIST[RI.RatIntervals.class.toExpr[inData.isolatingInterval] ];

colLength ← 9;

}

ELSE {

pointStructure: AC.Structure ← inData.point.structure;

pointStructureData: PTS.PointStructureData ← NARROW[pointStructure.instanceData];

extensionFieldData: EF.ExtensionFieldData ← NARROW[pointStructureData.coordinateStructure.instanceData];

outColumn ← tail ← LIST[MathConstructors.MakeVariable["PRIMITIVESAMPLEPOINT"] ];

tail ← tail.rest ← LIST[MathConstructors.MakeVariable["PRIMITIVEELEMENT"] ];

tail ← tail.rest ← LIST[RealAlgebraicNumbers.class.toExpr[extensionFieldData.primitiveElement] ];

tail ← tail.rest ← LIST[MathConstructors.MakeVariable["POINT"] ];

tail ← tail.rest ← LIST[pointStructure.class.toExpr[inData.point] ];

colLength ← 5;

};

out ← MathConstructors.MakeVector[colLength, outColumn, FALSE];

};

samplePointStructureOps: SamplePointOps ← NEW[SamplePointOpsRec ← [

cell: Cll,

basePoint: BasePt,

definingPolynomial: DefPoly,

isolatingInterval: IsolInt,

point: Pt

] ];

samplePointProp: Atom.DottedPair ← NEW[Atom.DottedPairNode← [$SamplePointStructure, samplePointStructureOps]];

samplePointStructureClass: PUBLIC AC.StructureClass ← NEW[AC.StructureClassRec ← [

category: set,

printName: ClassPrintName,

shortPrintName: ClassShortPrintName,

structureEqual: AC.defaultStructureEqualityTest,

isElementOf: ClassIsElementOf,

legalFirstChar: ClassLegalFirstChar,

read: Read,

fromRope: FromRope,

toRope: ToRope,

toIndexRope: ToIndexRope,

write: Write,

toExpr: ClassToExpr,

integralDomain: FALSE,

gcdDomain: FALSE,

euclideanDomain: FALSE,

propList: LIST[samplePointProp]

] ];

SamplePoint Structure Constructor

MakeSamplePointStructure: PUBLIC PROC [inputPolynomialRing, minPolyRing: AC.Structure] RETURNS [samplePointStructure: AC.Structure] ~ {

samplePointStructureData: SamplePointStructureData ← NEW[SamplePointStructureDataRec ← [

inputPolynomialRing: inputPolynomialRing,

minPolyRing: minPolyRing

] ];

RETURN[ NEW[AC.StructureRec ← [

class: samplePointStructureClass,

instanceData: samplePointStructureData

] ] ];

};

Extract SamplePoint Operations from Class Record Property Lists

IsSamplePointStructure: PUBLIC PROC [structure: AC.Structure] RETURNS [BOOL] ~ {

IF Atom.GetPropFromList[structure.class.propList, $SamplePointStructure] # NIL THEN RETURN[TRUE] ELSE RETURN[FALSE];

};

Cell: PUBLIC PROC [structure: AC.Structure] RETURNS [AC.UnaryOp] ~ {

IF IsSamplePointStructure[structure] THEN {

samplePointOps: SamplePointOps ← NARROW[ Atom.GetPropFromList[structure.class.propList, $SamplePointStructure] ];

RETURN[samplePointOps.cell];

}

ELSE ERROR;

};

BasePoint: PUBLIC PROC [structure: AC.Structure] RETURNS [AC.UnaryOp] ~ {

IF IsSamplePointStructure[structure] THEN {

samplePointOps: SamplePointOps ← NARROW[ Atom.GetPropFromList[structure.class.propList, $SamplePointStructure] ];

RETURN[samplePointOps.basePoint];

}

ELSE ERROR;

};

DefiningPolynomial: PUBLIC PROC [structure: AC.Structure] RETURNS [AC.UnaryOp] ~ {

IF IsSamplePointStructure[structure] THEN {

samplePointOps: SamplePointOps ← NARROW[ Atom.GetPropFromList[structure.class.propList, $SamplePointStructure] ];

RETURN[samplePointOps.definingPolynomial];

}

ELSE ERROR;

};

IsolatingInterval: PUBLIC PROC [structure: AC.Structure] RETURNS [AC.UnaryOp] ~ {

IF IsSamplePointStructure[structure] THEN {

samplePointOps: SamplePointOps ← NARROW[ Atom.GetPropFromList[structure.class.propList, $SamplePointStructure] ];

RETURN[samplePointOps.isolatingInterval];

}

ELSE ERROR;

};

Point: PUBLIC PROC [structure: AC.Structure] RETURNS [AC.UnaryOp] ~ {

IF IsSamplePointStructure[structure] THEN {

samplePointOps: SamplePointOps ← NARROW[ Atom.GetPropFromList[structure.class.propList, $SamplePointStructure] ];

RETURN[samplePointOps.point];

}

ELSE ERROR;

};

Conversion and IO

Read: PUBLIC AC.ReadOp ~ {

samplePointStructureData: SamplePointStructureData ← NARROW[structure.instanceData];

polyRingData: POL.PolynomialRingData ← NARROW[samplePointStructureData.inputPolynomialRing.instanceData];

V: VARS.VariableSeq ← polyRingData.allVariables;

dimension: NAT ← V.lengthPlus1 - 1;

token: Rope.ROPE;

RealAlgebraicNumbers: AC.Structure ← AN.MakeFieldOfAlgebraicNumbers[samplePointStructureData.minPolyRing, TRUE];

primitiveElement: AN.AlgebraicNumber;

basePoint: PTS.Point;

definingPolynomial: POL.Polynomial;

isolatingInterval: RI.RatInterval;

point: PTS.Point;

numberField, algebraicPolynomialsRing: AC.Structure;

outData: SamplePointData;

token ← in.GetID[];

IF Rope.Equal[token, "NILSAMPLEPOINT"] THEN

RETURN[NEW[AC.ObjectRec ← [structure: structure, data: NIL] ] ]

ELSE IF Rope.Equal[token, "EXTENDEDSAMPLEPOINT"] THEN {

basePointStructure: AC.Structure;

token ← in.GetID[];

IF NOT Rope.Equal[token, "PRIMITIVEELEMENT"] THEN ERROR;

primitiveElement ← RealAlgebraicNumbers.class.read[in, RealAlgebraicNumbers];

numberField ← EF.MakeExtensionField[primitiveElement];

token ← in.GetID[];

IF NOT Rope.Equal[token, "BASEPOINT"] THEN ERROR;

basePointStructure ← PTS.MakePointStructure[numberField, dimension - 1];

basePoint ← PTS.Read[in, basePointStructure];

token ← in.GetID[];

algebraicPolynomialsRing ← POL.MakePolynomialStructure[numberField, VARS.MainVariable[V] ];

IF NOT Rope.Equal[token, "DEFININGPOLYNOMIAL"] THEN ERROR;

definingPolynomial ← NARROW[algebraicPolynomialsRing.class.read[in, algebraicPolynomialsRing] ];

token ← in.GetID[];

IF NOT Rope.Equal[token, "ISOLATINGINTERVAL"] THEN ERROR;

isolatingInterval ← RI.RatIntervals.class.read[in, RI.RatIntervals];

outData ← NEW[SamplePointDataRec ← [

basePoint: basePoint,

definingPolynomial: definingPolynomial,

isolatingInterval: isolatingInterval

] ];

}

ELSE IF Rope.Equal[token, "PRIMITIVESAMPLEPOINT"] THEN {

pointStructure: AC.Structure;

token ← in.GetID[];

IF NOT Rope.Equal[token, "PRIMITIVEELEMENT"] THEN ERROR;

primitiveElement ← RealAlgebraicNumbers.class.read[in, RealAlgebraicNumbers];

numberField ← EF.MakeExtensionField[primitiveElement];

token ← in.GetID[];

IF NOT Rope.Equal[token, "POINT"] THEN ERROR;

pointStructure ← PTS.MakePointStructure[numberField, dimension];

point ← PTS.Read[in, pointStructure];

outData ← NEW[SamplePointDataRec ← [

point: point

] ];

}

ELSE ERROR;

RETURN[NEW[AC.ObjectRec ← [structure: structure, data: outData] ] ];

};

FromRope: PUBLIC AC.FromRopeOp ~ {

out ← Read[IO.RIS[in], structure];

};

ToIndexRope: AC.ToRopeOp ~ {

out ← "SP";

};

ToRope: PUBLIC AC.ToRopeOp ~ {

samplePointStructureData: SamplePointStructureData ← NARROW[in.structure.instanceData];

minPolyRing: AC.Structure ← samplePointStructureData.minPolyRing;

RealAlgebraicNumbers: AC.Structure ← AN.MakeFieldOfAlgebraicNumbers[samplePointStructureData.minPolyRing, TRUE];

inData: SamplePointData ← NARROW[in.data];

out ← "";

IF inData=NIL THEN {

out ← Rope.Concat[out, "NILSAMPLEPOINT\n"];

RETURN;

};

IF inData.basePoint # NIL THEN {

pointStructureData: PTS.PointStructureData ← NARROW[inData.basePoint.structure.instanceData];

extensionFieldData: EF.ExtensionFieldData ← NARROW[pointStructureData.coordinateStructure.instanceData];

out ← Rope.Concat[out, "EXTENDEDSAMPLEPOINT\n"];

out ← Rope.Concat[out, "PRIMITIVEELEMENT\n"];

out ← Rope.Cat[out, RealAlgebraicNumbers.class.toRope[extensionFieldData.primitiveElement], "\n"];

out ← Rope.Concat[out, "BASEPOINT\n"];

out ← Rope.Cat[out, PTS.ToRope[inData.basePoint], "\n"];

out ← Rope.Concat[out, "DEFININGPOLYNOMIAL\n"];

out ← Rope.Cat[out, POL.PolyToRope[inData.definingPolynomial], "\n"];

out ← Rope.Concat[out, "ISOLATINGINTERVAL\n"];

out ← Rope.Cat[out, RI.RatIntervals.class.toRope[inData.isolatingInterval], "\n"];

}

ELSE {

pointStructureData: PTS.PointStructureData ← NARROW[inData.point.structure.instanceData];

extensionFieldData: EF.ExtensionFieldData ← NARROW[pointStructureData.coordinateStructure.instanceData];

out ← Rope.Concat[out, "PRIMITIVESAMPLEPOINT\n"];

out ← Rope.Concat[out, "PRIMITIVEELEMENT\n"];

out ← Rope.Cat[out, RealAlgebraicNumbers.class.toRope[extensionFieldData.primitiveElement], "\n"];

out ← Rope.Concat[out, "POINT\n"];

out ← Rope.Cat[out, PTS.ToRope[inData.point], "\n"];

};

Write: PUBLIC AC.WriteOp ~ {

stream.PutRope[ToRope[in] ]

};

Operations

SetCell: PUBLIC PROC [samplePoint, cell: AC.Object] ~ {

data: SamplePointData ← NARROW[samplePoint.data];

data.cell ← cell;

};

Cll: PUBLIC AC.UnaryOp ~ {