--* From BMT%WATSON.vnet.ibm.com@yktvmh.watson.ibm.com Tue Jul 13 09:51:02 1993 --* Received: from yktvmh.watson.ibm.com by radical.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA15065; Tue, 13 Jul 1993 09:51:02 -0400 --* Received: from watson.vnet.ibm.com by yktvmh.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 9614; Tue, 13 Jul 93 09:51:57 EDT --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Tue, 13 Jul 93 09:51:55 -0400 --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 0603; Tue, 13 Jul 1993 09:51:53 EDT --* Received: from cyst.watson.ibm.com by yktvmh.watson.ibm.com (IBM VM SMTP V2R3) --* with TCP; Tue, 13 Jul 93 09:51:50 EDT --* Received: from spadserv.watson.ibm.com by cyst.watson.ibm.com (AIX 3.2/UCB 5.64/900528) --* id AA30064; Tue, 13 Jul 1993 09:52:06 -0400 --* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA19347; Tue, 13 Jul 1993 09:55:13 -0400 --* Date: Tue, 13 Jul 1993 09:55:13 -0400 --* From: bmt@spadserv.watson.ibm.com --* X-External-Networks: yes --* Message-Id: <9307131355.AA19347@spadserv.watson.ibm.com> --* To: asbugs@watson.ibm.com --* Subject: asharp -M no-warnings catdef77.as gives sementation violation [catdef77.as][29.2 (current)] --@ Fixed by: SSD Wed Jun 29 16:43:13 EDT 1994 --@ Tested by: none --@ Summary: Bug no longer appears in v0.36.0 --Copyright The Numerical Algorithms Group Limited 1991. #include "aslib.as" #library DemoLib "asdem" import DemoLib Boolean ==> Bit SmallInteger ==> SingleInteger Object ==> Type SetCategory ==> BasicType -- temporary def PositiveInteger ==> NonNegativeInteger --% attributes unitsKnown: Category == with --% Basic AXIOM Categories --% StepThrough +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A class of objects which can be 'stepped through'. +++ Repeated applications of \spadfun{nextItem} is guaranteed never to +++ return duplicate items and only return "failed" after exhausting +++ all elements of the domain. +++ This assumes that the sequence starts with \spad{init()}. +++ For infinite domains, repeated application +++ of \spadfun{nextItem} is not required to reach all possible domain elements +++ starting from any initial element. +++ +++ Conditional attributes: +++ infinite\tab{15}repeated \spad{nextItem}'s are never "failed". StepThrough: Category == SetCategory with --operations init: () -> % ++ init() chooses an initial object for stepping. nextItem: % -> Partial % ++ nextItem(x) returns the next item, or "failed" if domain is exhausted. --% SemiGroup +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ the class of all multiplicative semigroups, i.e. a set +++ with an associative operation \spadop{*}. +++ +++ Axioms: +++ \spad{associative(*:(%,%)->%)}\tab{30}\spad{ (x*y)*z = x*(y*z)} +++ +++ Conditional attributes: +++ \spad{commutative(*:(%,%)->%)}\tab{30}\spad{ x*y = y*x } SemiGroup: Category == SetCategory with --operations *: (%,%) -> % ++ x*y returns the product of x and y. ^: (%,PositiveInteger) -> % ++ x^n returns the repeated product ++ of x n times, i.e. exponentiation. --% Monoid +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The class of multiplicative monoids, i.e. semigroups with a +++ multiplicative identity element. +++ +++ Axioms: +++ \spad{leftIdentity(*:(%,%)->%,1)}\tab{30}\spad{1*x=x} +++ \spad{rightIdentity(*:(%,%)->%,1)}\tab{30}\spad{x*1=x} +++ +++ Conditional attributes: +++ unitsKnown\tab{15}\spadfun{recip} only returns "failed" on non-units OldMonoid: Category == SemiGroup with --operations 1: % ++ 1 is the multiplicative identity. one?: % -> Boolean ++ one?(x) tests if x is equal to 1. ^: (%,NonNegativeInteger) -> % ++ x^n returns the repeated product of x ++ n times, i.e. exponentiation. recip: % -> Partial % ++ recip(x) tries to compute the multiplicative inverse for x ++ or "failed" if it cannot find the inverse (see unitsKnown). --% Group +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The class of multiplicative groups, i.e. monoids with +++ multiplicative inverses. +++ +++ Axioms: +++ \spad{leftInverse(*:(%,%)->%,inv)}\tab{30}\spad{ inv(x)*x = 1 } +++ \spad{rightInverse(*:(%,%)->%,inv)}\tab{30}\spad{ x*inv(x) = 1 } Group: Category == Monoid with --operations inv: % -> % ++ inv(x) returns the inverse of x. /: (%,%) -> % ++ x/y is the same as x times the inverse of y. ^: (%,Integer) -> % ++ x^n returns x raised to the integer power n. unitsKnown ++ unitsKnown asserts that recip only returns ++ "failed" for non-units. conjugate: (%,%) -> % ++ conjugate(p,q) computes \spad{inv(q) * p * q}; this is 'right action ++ by conjugation'. commutator: (%,%) -> % ++ commutator(p,q) computes \spad{inv(p) * inv(q) * p * q}. --% AbelianSemiGroup +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ the class of all additive (commutative) semigroups, i.e. +++ a set with a commutative and associative operation \spadop{+}. +++ +++ Axioms: +++ \spad{associative(+:(%,%)->%)}\tab{30}\spad{ (x+y)+z = x+(y+z) } +++ \spad{commutative(+:(%,%)->%)}\tab{30}\spad{ x+y = y+x } AbelianSemiGroup: Category == SetCategory with --operations +: (%,%) -> % ++ x+y computes the sum of x and y. *: (PositiveInteger,%) -> % ++ n*x computes the left-multiplication of x by the positive integer n. ++ This is equivalent to adding x to itself n times. --% AbelianMonoid +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The class of multiplicative monoids, i.e. semigroups with an +++ additive identity element. +++ +++ Axioms: +++ \spad{leftIdentity(+:(%,%)->%,0)}\tab{30}\spad{ 0+x=x } +++ \spad{rightIdentity(+:(%,%)->%,0)}\tab{30}\spad{ x+0=x } -- following domain must be compiled with subsumption disabled -- define SourceLevelSubset to be EQUAL OldAbelianMonoid: Category == AbelianSemiGroup with --operations 0: % ++ 0 is the additive identity element. zero?: % -> Boolean ++ zero?(x) tests if x is equal to 0. *: (NonNegativeInteger,%) -> % ++ n * x is left-multiplication by a non negative integer --% CancellationAbelianMonoid +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: Davenport & Trager I +++ Description: +++ This is an \spadtype{AbelianMonoid} with the cancellation property, i.e. +++ \spad{ a+b = a+c => b=c }. +++ This is formalised by the partial subtraction operator, +++ which satisfies the axioms listed below: +++ +++ Axioms: +++ \spad{c = a+b <=> c-b = a} CancellationAbelianMonoid: Category == AbelianMonoid with --operations subtractIfCan: (%,%) -> Partial(%) ++ subtractIfCan(x, y) returns an element z such that \spad{z+y=x} ++ or "failed" if no such element exists. --% AbelianGroup +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The class of abelian groups, i.e. additive monoids where +++ each element has an additive inverse. +++ +++ Axioms: +++ \spad{-(-x) = x} +++ \spad{x+(-x) = 0} -- following domain must be compiled with subsumption disabled OldAbelianGroup: Category == CancellationAbelianMonoid with --operations -: % -> % ++ -x is the additive inverse of x. -: (%,%) -> % ++ x-y is the difference of x and y ++ i.e. \spad{x + (-y)}. -- subsumes the partial subtraction from previous *: (Integer,%) -> % ++ n*x is the product of x by the integer n. --% Rng +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of associative rings, not necessarily commutative, and not +++ necessarily with a 1. This is a combination of an abelian group +++ and a semigroup, with multiplication distributing over addition. +++ +++ Axioms: +++ \spad{ x*(y+z) = x*y + x*z} +++ \spad{ (x+y)*z = x*z + y*z } +++ +++ Conditional attributes: +++ \spadnoZeroDivisors\tab{25}\spad{ ab = 0 => a=0 or b=0} Rng: Category == Join(AbelianGroup,SemiGroup) --% LeftModule +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of left modules over an rng (ring not necessarily with unit). +++ This is an abelian group which supports left multiplation by elements of +++ the rng. +++ +++ Axioms: +++ \spad{ (a*b)*x = a*(b*x) } +++ \spad{ (a+b)*x = (a*x)+(b*x) } +++ \spad{ a*(x+y) = (a*x)+(a*y) } LeftModule(R:Rng):Category == AbelianGroup with --operations *: (R,%) -> % ++ r*x returns the left multiplication of the module element x ++ by the ring element r. --% RightModule +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of right modules over an rng (ring not necessarily with unit). +++ This is an abelian group which supports right multiplation by elements of +++ the rng. +++ +++ Axioms: +++ \spad{ x*(a*b) = (x*a)*b } +++ \spad{ x*(a+b) = (x*a)+(x*b) } +++ \spad{ (x+y)*x = (x*a)+(y*a) } RightModule(RR:Rng):Category == AbelianGroup with --operations *: (%,RR) -> % ++ x*r returns the right multiplication of the module element x ++ by the ring element r. --% Ring +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of rings with unity, always associative, but +++ not necessarily commutative. OldRing: Category == Join(Rng,Monoid,LeftModule(% pretend Rng)) with --operations characteristic: () -> NonNegativeInteger ++ characteristic() returns the characteristic of the ring ++ this is the smallest positive integer n such that ++ \spad{n*x=0} for all x in the ring, or zero if no such n ++ exists. --We can not make this a constant, since some domains are mutable coerce: Integer -> % ++ coerce(i) converts the integer i to a member of the given domain. -- recip: % -> Partial(%) -- inherited from Monoid unitsKnown ++ recip truly yields ++ reciprocal or "failed" if not a unit. ++ Note: \spad{recip(0) = "failed"}. --% BiModule +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A \spadtype{BiModule} is both a left and right module with respect +++ to potentially different rings. +++ +++ Axiom: +++ \spad{ r*(x*s) = (r*x)*s } BiModule(R:Ring,S:Ring):Category == Join(LeftModule(R pretend Rng),RightModule(S pretend Rng)) with leftUnitary ++ \spad{1 * x = x} rightUnitary ++ \spad{x * 1 = x} --% EntireRing +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ Entire Rings (non-commutative Integral Domains), i.e. a ring +++ not necessarily commutative which has no zero divisors. +++ +++ Axioms: +++ \spad{ab=0 => a=0 or b=0} -- known as noZeroDivisors +++ \spad{not(1=0)} EntireRing:Category == Join(Ring,BiModule(% pretend Ring,% pretend Ring)) with noZeroDivisors ++ if a product is zero then one of the factors ++ must be zero. --% CharacteristicZero +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ Rings of Characteristic Zero. CharacteristicZero:Category == Ring --% CharacteristicNonZero +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ Rings of Characteristic Non Zero CharacteristicNonZero:Category == Ring with charthRoot: % -> Partial(%) ++ charthRoot(x) returns the pth root of x ++ where p is the characteristic of the ring. --% CommutativeRing +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of commutative rings with unity, i.e. rings where +++ \spadop{*} is commutative, and which have a multiplicative identity. +++ element. CommutativeRing:Category == Join(Ring,BiModule(% pretend Ring,% pretend Ring)) with commutative(*) ++ multiplication is commutative. --% Module +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of modules over a commutative ring. +++ +++ Axioms: +++ \spad{1*x = x} +++ \spad{(a*b)*x = a*(b*x)} +++ \spad{(a+b)*x = (a*x)+(b*x)} +++ \spad{a*(x+y) = (a*x)+(a*y)} Module(R:CommutativeRing): Category == BiModule(R,R) --% Algebra +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of associative algebras (modules which are themselves rings). +++ +++ Axioms: +++ \spad{(b+c)::% = (b::%) + (c::%)} +++ \spad{(b*c)::% = (b::%) * (c::%)} +++ \spad{(1::R)::% = 1::%} +++ \spad{b*x = (b::%)*x} +++ \spad{r*(a*b) = (r*a)*b = a*(r*b)} Algebra(R:CommutativeRing): Category == Join(Ring, Module R) with --operations coerce: R -> % ++ coerce(r) maps the ring element r to a member of the algebra. --% IntegralDomain +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: Davenport & Trager I +++ Description: +++ The category of commutative integral domains, i.e. commutative +++ rings with no zero divisors. +++ +++ Conditional attributes: +++ canonicalUnitNormal\tab{20}the canonical field is the same for all associates +++ canonicalsClosed\tab{20}the product of two canonicals is itself canonical IntegralDomain: Category == Join(CommutativeRing, Algebra(% pretend CommutativeRing), EntireRing) with --operations exquo: (%,%) -> Partial(%) ++ exquo(a,b) either returns an element c such that ++ \spad{c*b=a} or "failed" if no such element can be found. unitNormal: % -> Record(unit:%,canonical:%,associate:%) ++ unitNormal(x) tries to choose a canonical element ++ from the associate class of x. ++ The attribute canonicalUnitNormal, if asserted, means that ++ the "canonical" element is the same across all associates of x ++ if \spad{unitNormal(x) = [u,c,a]} then ++ \spad{u*c = x}, \spad{a*u = 1}. unitCanonical: % -> % ++ \spad{unitCanonical(x)} returns \spad{unitNormal(x).canonical}. associates?: (%,%) -> Boolean ++ associates?(x,y) tests whether x and y are associates, i.e. ++ differ by a unit factor. unit?: % -> Boolean ++ unit?(x) tests whether x is a unit, i.e. is invertible. --% GcdDomain +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: Davenport & Trager 1 +++ Description: +++ This category describes domains where +++ \spadfun{gcd} can be computed but where there is no guarantee +++ of the existence of \spadfun{factor} operation for factorisation into irreducibles. +++ However, if such a \spadfun{factor} operation exist, factorization will be +++ unique up to order and units. OldGcdDomain: Category == IntegralDomain with --operations gcd: (%,%) -> % ++ gcd(x,y) returns the greatest common divisor of x and y. -- gcd(x,y) = gcd(y,x) in the presence of canonicalUnitNormal, -- but not necessarily elsewhere lcm: (%,%) -> % ++ lcm(x,y) returns the least common multiple of x and y. -- lcm(x,y) = lcm(y,x) in the presence of canonicalUnitNormal, -- but not necessarily elsewhere --% UniqueFactorizationDomain +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A constructive unique factorization domain, i.e. where +++ we can constructively factor members into a product of +++ a finite number of irreducible elements. UniqueFactorizationDomain: Category == GcdDomain with --operations prime?: % -> Boolean ++ prime?(x) tests if x can never be written as the product of two ++ non-units of the ring, ++ i.e., x is an irreducible element. -- squareFree : % -> Factored(%) ++ squareFree(x) returns the square-free factorization of x ++ i.e. such that the factors are pairwise relatively prime ++ and each has multiple prime factors. squareFreePart: % -> % ++ squareFreePart(x) returns a product of prime factors of ++ x each taken with multiplicity one. -- factor: % -> Factored(%) ++ factor(x) returns the factorization of x into irreducibles. --% PrincipalIdealDomain +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of constructive principal ideal domains, i.e. +++ where a single generator can be constructively found for +++ any ideal given by a finite set of generators. +++ Note that this constructive definition only implies that +++ finitely generated ideals are principal. It is not clear +++ what we would mean by an infinitely generated ideal. PrincipalIdealDomain: Category == GcdDomain --% EuclideanDomain +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A constructive euclidean domain, i.e. one can divide producing +++ a quotient and a remainder where the remainder is either zero +++ or is smaller (\spadfun{euclideanSize}) than the divisor. +++ +++ Conditional attributes: +++ multiplicativeValuation\tab{25}\spad{Size(a*b)=Size(a)*Size(b)} +++ additiveValuation\tab{25}\spad{Size(a*b)=Size(a)+Size(b)} EuclideanDomain: Category == PrincipalIdealDomain with --operations sizeLess?: (%,%) -> Boolean ++ sizeLess?(x,y) tests whether x is strictly ++ smaller than y with respect to the \spadfunFrom{euclideanSize}{EuclideanDomain}. euclideanSize: % -> NonNegativeInteger ++ euclideanSize(x) returns the euclidean size of the element x. ++ Error: if x is zero. divide: (%,%) -> Record(quotient:%,remainder:%) ++ divide(x,y) divides x by y producing a record containing a ++ \spad{quotient} and \spad{remainder}, ++ where the remainder is smaller (see \spadfunFrom{sizeLess?}{EuclideanDomain}) ++ than the divisor y. quo : (%,%) -> % ++ x quo y is the same as \spad{divide(x,y).quotient}. ++ See \spadfunFrom{divide}{EuclideanDomain}. rem: (%,%) -> % ++ x rem y is the same as \spad{divide(x,y).remainder}. ++ See \spadfunFrom{divide}{EuclideanDomain}. extendedEuclidean: (%,%) -> Record(coef1:%,coef2:%,generator:%) -- formerly called princIdeal ++ extendedEuclidean(x,y) returns a record rec where ++ \spad{rec.coef1*x+rec.coef2*y = rec.generator} and ++ rec.generator is a gcd of x and y. ++ The gcd is unique only ++ up to associates if \spadatt{canonicalUnitNormal} is not asserted. ++ \spadfun{principalIdeal} provides a version of this operation ++ which accepts an arbitrary length list of arguments. extendedEuclidean: (%,%,%) -> Partial(Record(coef1:%,coef2:%)) -- formerly called expressIdealElt ++ extendedEuclidean(x,y,z) either returns a record rec ++ where \spad{rec.coef1*x+rec.coef2*y=z} or returns "failed" ++ if z cannot be expressed as a linear combination of x and y. multiEuclidean: (List(% pretend BasicType),%) -> Partial List(% pretend BasicType) ++ multiEuclidean([f1,...,fn],z) returns a list of coefficients ++ \spad{[a1, ..., an]} such that ++ \spad{ z / prod fi = sum aj/fj}. ++ If no such list of coefficients exists, "failed" is returned. -- redundant declarations to help out the new compiler for now zero?: % -> Boolean euclideanSize: % -> NonNegativeInteger divide: (%,%) -> Record(quotient:%, remainder:%)