IntsImpl.mesa
Last Edited by: Arnon, July 19, 1985 2:54:46 pm PDT
DIRECTORY
Rope,
IO,
Basics,
Atom,
Convert,
AlgebraClasses,
MathConstructors,
Bools,
Ints;
IntsImpl: CEDAR PROGRAM
IMPORTS IO, Convert, Rope, AlgebraClasses, MathConstructors
EXPORTS Ints
= BEGIN OPEN Ints, Convert, AC: AlgebraClasses;
Types
IntsError: PUBLIC SIGNAL [reason: ATOM ← $Unspecified] = CODE;
bitsPerWord: CARDINAL = Basics.bitsPerWord;
CARD: TYPE = LONG CARDINAL;
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;
Object: TYPE = AC.Object;
Method: TYPE = AC.Method;
TypeError: PUBLIC ERROR [message: ATOM ← $Unspecified] = CODE;
Miscellaneous Procs
PrintName: PUBLIC AC.ToRopeOp = {
RETURN["Ints"];
};
ShortPrintName: PUBLIC AC.ToRopeOp = {
RETURN["Z"];
};
Characteristic: PUBLIC AC.StructureRankOp = {
RETURN[ 0 ]
};
I/O and Conversion
Recast: PUBLIC AC.BinaryOp = {
IF NOT AC.StructureEqual[firstArg.class, Ints] THEN RETURN[NIL] ELSE RETURN[firstArg];
};
CanRecast: PUBLIC AC.BinaryPredicate = {
firstArgStructure: Object ← IF firstArg.flavor = StructureElement THEN firstArg.class ELSE IF firstArg.flavor = Structure THEN firstArg ELSE ERROR;
SELECT TRUE FROM
AC.StructureEqual[firstArgStructure, Ints] => RETURN[TRUE];
ENDCASE;
RETURN[FALSE];
};
ToExpr: PUBLIC AC.ToExprOp = {
data: IntData ← NARROW[in.data];
RETURN[MathConstructors.MakeInt[Convert.RopeFromInt[data^] ] ];
};
LegalFirstChar: PUBLIC AC.LegalFirstCharOp = {
SELECT char FROM
IN ['0..'9] => RETURN[TRUE];
ENDCASE;
RETURN[FALSE];
};
Read: PUBLIC AC.ReadOp ~ {
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← IO.GetInt[in] ]
] ] ];
};
FromRope: PUBLIC AC.FromRopeOp = {
stream: IO.STREAM ← IO.RIS[in];
RETURN[ Read[stream] ];
};
ToRope: PUBLIC AC.ToRopeOp = {
data: IntData ← NARROW[in.data];
RETURN[ Convert.RopeFromInt[data^] ];
};
Write: PUBLIC AC.WriteOp = {
IO.PutRope[ stream, ToRope[in] ]
};
FromINT: PUBLIC AC.FromINTOp = {
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← in]
] ] ];
};
ToINT: PUBLIC PROC [int: Int] RETURNS [INT] = {
data: IntData ← NARROW[int.data];
RETURN[data^];
};
Arithmetic
Zero: PUBLIC AC.NullaryOp = {
RETURN[ IntZero ]
};
One: PUBLIC AC.NullaryOp = {
RETURN[ IntOne ]
};
Add: PUBLIC AC.BinaryOp ~ {
firstData: IntData ← NARROW[firstArg.data];
secondData: IntData ← NARROW[secondArg.data];
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← firstData^ + secondData^ ]
] ] ];
};
Negate: PUBLIC AC.UnaryOp ~ {
data: IntData ← NARROW[arg.data];
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← - data^ ]
] ] ];
};
Subtract: PUBLIC AC.BinaryOp ~ {
firstData: IntData ← NARROW[firstArg.data];
secondData: IntData ← NARROW[secondArg.data];
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← firstData^ - secondData^ ]
] ] ];
};
Multiply: PUBLIC AC.BinaryOp ~ {
firstData: IntData ← NARROW[firstArg.data];
secondData: IntData ← NARROW[secondArg.data];
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← firstData^ * secondData^ ]
] ] ];
};
ObjectAndIntDesired: PUBLIC AC.UnaryToListOp ~ {
RETURN[ LIST[arg, Ints] ]; -- arg assumed to be a Structure
};
Power: PUBLIC AC.BinaryOp ~ { -- this simple algorithm is Structure independent
power: INT ← ToINT[secondArg];
structure: Object ← firstArg.class;
one: Object ← AC.ApplyLkpNoRecastObject[$one, structure, LIST[structure] ];
productMethod: Method ← AC.LookupMethodInStructure[$product, structure];
IF power < 0 THEN {
invertMethod: Method ← AC.LookupMethodInStructure[$invert, structure];
temp: Object;
IF invertMethod = NIL THEN ERROR;
temp ← Power[firstArg, FromINT[ABS[power] ] ];
RETURN[AC.ApplyNoLkpNoRecastObject[invertMethod, LIST[temp] ] ];
};
IF power = 0 THEN RETURN[one];
result ← firstArg;
FOR i:INT IN [2..power] DO
result ← AC.ApplyNoLkpNoRecastObject[productMethod, LIST[firstArg, result] ];
ENDLOOP;
};
Remainder: PUBLIC AC.BinaryOp ~ {
firstData: IntData ← NARROW[firstArg.data];
secondData: IntData ← NARROW[secondArg.data];
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← firstData^ MOD secondData^ ]
] ] ];
};
Gcd: PUBLIC AC.BinaryOp ~ {
gcd: Int;
IF Equal[firstArg, IntZero] AND Equal[secondArg, IntZero] THEN gcd ← IntZero
ELSE {
r: Int;
UNTIL Equal[secondArg, IntZero] DO
r ← Remainder[firstArg, secondArg];
firstArg ← secondArg; secondArg ← r;
ENDLOOP;
gcd ← Abs[firstArg];
};
RETURN[gcd ];
};
Totient: PUBLIC AC.UnaryOp ~ {
totient: INT ← 0;
IF Equal[arg, IntZero] THEN RETURN[IntZero];
FOR i:INT IN [1.. ToINT[arg] ] DO
IF ToINT[Gcd[FromINT[i], arg] ] = 1 THEN totient ← totient + 1;
ENDLOOP;
RETURN[FromINT[totient] ];
};
Divides: PUBLIC AC.BinaryOp ~ {
returns 1 if secondArg divides firstArg, 0 if not
first: INT ← ToINT[firstArg];
second: INT ← ToINT[secondArg];
IF first MOD second = 0 THEN RETURN[FromINT[1] ] ELSE RETURN[FromINT[0] ];
};
Paren: PUBLIC AC.UnaryOp ~ {
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: arg.data
] ] ];
};
Comparison
Sign: PUBLIC AC.CompareToZeroOp = {
data: IntData ← NARROW[arg.data];
SELECT data^ FROM
< 0 => RETURN[less];
= 0 => RETURN[equal];
ENDCASE => RETURN[greater];
};
Abs: PUBLIC AC.UnaryOp ~ {
data: IntData ← NARROW[arg.data];
RETURN[NEW[AC.ObjectRec ← [
flavor: StructureElement,
class: Ints,
data: NEW[INT ← ABS[data^] ]
] ] ];
};
Compare: PUBLIC AC.BinaryCompareOp ~ {
firstData: IntData ← NARROW[firstArg.data];
secondData: IntData ← NARROW[secondArg.data];
SELECT firstData^ FROM
< secondData^ => RETURN[less];
= secondData^ => RETURN[equal];
ENDCASE => RETURN[greater];
};
Equal: PUBLIC AC.BinaryPredicate ~ {
firstData: IntData ← NARROW[firstArg.data];
secondData: IntData ← NARROW[secondArg.data];
RETURN[ firstData^ = secondData^ ]
};
TestLoop: PUBLIC AC.UnaryOp ~ {
firstData: IntData ← NARROW[arg.data];
num: INT ← firstData^;
string: ROPE ← "298749823749823749";
c: CHAR;
FOR i:INT IN [1..num] DO
c ← Rope.Fetch[string, 3];
ENDLOOP;
RETURN[ FromRope[ Rope.FromChar[c]] ]
};
Standard Desired Arg Structures
IntsDesired: PUBLIC AC.UnaryToListOp ~ {
Name Ints explicitly, instead of using AC.DefaultDesiredArgStructures, so that if a Ints method found by lookup from a subclasss, then will recast its args correctly (i.e. to Ints)
RETURN[ LIST[Ints] ];
};
Start Code
IntClass: AC.StructureClass ← NEW[AC.StructureClassRec ← [
category: ring,
flavor: "Ints",
printName: ClassPrintName,
shortPrintName: ClassShortPrintName,
structureEqual: AC.defaultStructureEqualityTest,
characteristic: ClassCharacteristic,
isElementOf: AC.defaultElementOfProc,
legalFirstChar: ClassLegalFirstChar,
read: Read,
fromRope: FromRope,
toRope: ToRope,
write: Write,
toExpr: ClassToExpr,
toIndexRope: ToRope,
add: Add,
negate: Negate,
subtract: Subtract,
zero: ClassZero,
multiply: Multiply,
commutative: TRUE,
one: ClassOne,
equal: Equal,
ordered: TRUE,
sign: Sign,
abs: Abs,
compare: Compare,
integralDomain: TRUE,
gcdDomain: TRUE,
gcd: Gcd,
euclideanDomain: TRUE,
remainder: Remainder,
] ];
intsClass: Object ← AC.MakeClass["intsClass", NIL, NIL];
Ints: PUBLIC Object ← AC.MakeStructure["Ints", intsClass, NIL];
IntOne: Int ← FromINT[1]; -- Do after Ints set, so structure field gets nonNIL value
IntZero: Int ← FromINT[0];
categoryMethod: Method ← AC.MakeMethod[Value, FALSE, NEW[AC.Category ← ring], NIL, "category"];
groundStructureMethod: Method ← AC.MakeMethod[Value, FALSE, NIL, NIL, "groundStructure"];
shortPrintNameMethod: Method ← AC.MakeMethod[ToRopeOp, FALSE, NEW[AC.ToRopeOp ← ShortPrintName], NIL, "shortPrintName"];
recastMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Recast], NIL, "recast"];
canRecastMethod: Method ← AC.MakeMethod[BinaryPredicate, TRUE, NEW[AC.BinaryPredicate ← CanRecast], NIL, "canRecast"];
toExprMethod: Method ← AC.MakeMethod[ToExprOp, FALSE, NEW[AC.ToExprOp ← ToExpr], NEW[AC.UnaryToListOp ← IntsDesired], "toExpr"];
legalFirstCharMethod: Method ← AC.MakeMethod[LegalFirstCharOp, FALSE, NEW[AC.LegalFirstCharOp ← LegalFirstChar], NIL, "legalFirstChar"];
readMethod: Method ← AC.MakeMethod[ReadOp, FALSE, NEW[AC.ReadOp ← Read], NIL, "read"];
fromRopeMethod: Method ← AC.MakeMethod[FromRopeOp, TRUE, NEW[AC.FromRopeOp ← FromRope], NIL, "fromRope"];
toRopeMethod: Method ← AC.MakeMethod[ToRopeOp, FALSE, NEW[AC.ToRopeOp ← ToRope], NIL, "toRope"];
fromINTMethod: Method ← AC.MakeMethod[FromINTOp, FALSE, NEW[AC.FromINTOp ← FromINT], NIL, "fromINT"];
integerMethod: Method ← AC.MakeMethod[FromRopeOp, FALSE, NEW[AC.FromRopeOp ← FromRope], NIL, "integer"];
zeroMethod: Method ← AC.MakeMethod[NullaryOp, FALSE, NEW[AC.NullaryOp ← Zero], NIL, "zero"];
oneMethod: Method ← AC.MakeMethod[NullaryOp, FALSE, NEW[AC.NullaryOp ← One], NIL, "one"];
parenMethod: Method ← AC.MakeMethod[UnaryOp, FALSE, NEW[AC.UnaryOp ← Paren], NIL, "paren"];
sumMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Add], NEW[AC.UnaryToListOp ← IntsDesired], "sum"];
negationMethod: Method ← AC.MakeMethod[UnaryOp, TRUE, NEW[AC.UnaryOp ← Negate], NEW[AC.UnaryToListOp ← IntsDesired], "negation"];
differenceMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Subtract], NEW[AC.UnaryToListOp ← IntsDesired], "difference"];
productMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Multiply], NEW[AC.UnaryToListOp ← IntsDesired], "product"];
commutativeMethod: Method ← AC.MakeMethod[Value, FALSE, NIL, NIL, "commutative"];
powerMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Power], NEW[AC.UnaryToListOp ← ObjectAndIntDesired], "power"];
euclideanDomainMethod: Method ← AC.MakeMethod[Value, FALSE, NIL, NIL, "euclideanDomain"];
remainderMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Remainder], NEW[AC.UnaryToListOp ← IntsDesired], "remainder"];
gcdMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Gcd], NEW[AC.UnaryToListOp ← IntsDesired], "gcd"];
totientMethod: Method ← AC.MakeMethod[UnaryOp, TRUE, NEW[AC.UnaryOp ← Totient], NEW[AC.UnaryToListOp ← IntsDesired], "totient"];
dividesMethod: Method ← AC.MakeMethod[BinaryOp, TRUE, NEW[AC.BinaryOp ← Divides], NEW[AC.UnaryToListOp ← IntsDesired], "divides"];
equalMethod: Method ← AC.MakeMethod[BinaryPredicate, TRUE, NEW[AC.BinaryPredicate ← Equal], NEW[AC.UnaryToListOp ← IntsDesired], "equals"];
orderedMethod: Method ← AC.MakeMethod[Value, FALSE, NIL, NIL, "ordered"];
signMethod: Method ← AC.MakeMethod[CompareToZeroOp, TRUE, NEW[AC.CompareToZeroOp ← Sign], NEW[AC.UnaryToListOp ← IntsDesired], "sign"];
absMethod: Method ← AC.MakeMethod[UnaryOp, TRUE, NEW[AC.UnaryOp ← Abs], NEW[AC.UnaryToListOp ← IntsDesired], "abs"];
compareMethod: Method ← AC.MakeMethod[BinaryCompareOp, TRUE, NEW[AC.BinaryCompareOp ← Compare], NEW[AC.UnaryToListOp ← IntsDesired], "compare"];
testLoop: Method ← AC.MakeMethod[UnaryOp, TRUE, NEW[AC.UnaryOp ← TestLoop], NEW[AC.UnaryToListOp ← IntsDesired], "testLoop"];
AC.AddMethodToClass[$category, categoryMethod, intsClass];
AC.AddMethodToClass[$groundStructure, categoryMethod, intsClass];
AC.AddMethodToClass[$shortPrintName, shortPrintNameMethod, intsClass];
AC.AddMethodToClass[$recast, recastMethod, intsClass];
AC.AddMethodToClass[$canRecast, canRecastMethod, intsClass];
AC.AddMethodToClass[$toExpr, toExprMethod, intsClass];
AC.AddMethodToClass[$legalFirstChar, legalFirstCharMethod, intsClass];
AC.AddMethodToClass[$read, readMethod, intsClass];
AC.AddMethodToClass[$fromRope, fromRopeMethod, intsClass];
AC.AddMethodToClass[$toRope, toRopeMethod, intsClass];
AC.AddMethodToClass[$integer, integerMethod, intsClass];
AC.AddMethodToClass[$fromINT, fromINTMethod, intsClass];
AC.AddMethodToClass[$zero, zeroMethod, intsClass];
AC.AddMethodToClass[$one, oneMethod, intsClass];
AC.AddMethodToClass[$paren, parenMethod, intsClass];
AC.AddMethodToClass[$sum, sumMethod, intsClass];
AC.AddMethodToClass[$negation, negationMethod, intsClass];
AC.AddMethodToClass[$difference, differenceMethod, intsClass];
AC.AddMethodToClass[$product, productMethod, intsClass];
AC.AddMethodToClass[$commutative, commutativeMethod, intsClass];
AC.AddMethodToClass[$pow, powerMethod, intsClass];
AC.AddMethodToClass[$euclideanDomain, euclideanDomainMethod, intsClass];
AC.AddMethodToClass[$remainder, remainderMethod, intsClass];
AC.AddMethodToClass[$gcd, gcdMethod, intsClass];
AC.AddMethodToClass[$totient, totientMethod, intsClass];
AC.AddMethodToClass[$divides, dividesMethod, intsClass];
AC.AddMethodToClass[$eqFormula, equalMethod, intsClass];
AC.AddMethodToClass[$ordered, orderedMethod, intsClass];
AC.AddMethodToClass[$sign, signMethod, intsClass];
AC.AddMethodToClass[$abs, absMethod, intsClass];
AC.AddMethodToClass[$compare, compareMethod, intsClass];
AC.AddMethodToClass[$testLoop, testLoop, intsClass];
AC.InstallStructure[Ints];
END.