Initial population.

1 files changed, 1132 insertions, 0 deletions

diff --git a/src/algebra/xpoly.spad.pamphlet b/src/algebra/xpoly.spad.pamphlet
new file mode 100644
index 00000000..6ff416b1
--- /dev/null
+++ b/src/algebra/xpoly.spad.pamphlet
@@ -0,0 +1,1132 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra xpoly.spad}
+\author{Michel Petitot}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{domain OFMONOID OrderedFreeMonoid}
+<<domain OFMONOID OrderedFreeMonoid>>=
+)abbrev domain OFMONOID OrderedFreeMonoid
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++    The free monoid on a set \spad{S} is the monoid of finite products of
+++ the form \spad{reduce(*,[si ** ni])} where the si's are in S, and the ni's
+++ are non-negative integers. The multiplication is not commutative.
+++ For two elements \spad{x} and \spad{y} the relation \spad{x < y}
+++ holds if either \spad{length(x) < length(y)} holds or if these lengths
+++ are equal and if \spad{x} is smaller than \spad{y} w.r.t. the lexicographical
+++ ordering induced by \spad{S}.
+++ This domain inherits implementation from \spadtype{FreeMonoid}.
+++ Author: Michel Petitot (petitot@lifl.fr)
+
+OrderedFreeMonoid(S: OrderedSet): OFMcategory == OFMdefinition where
+    NNI ==> NonNegativeInteger
+    REC ==> Record(gen:S, exp:NNI)
+ 
+    OFMcategory == Join(OrderedMonoid, RetractableTo S) with
+        "*":    (S, %) -> %
+          ++ \spad{s * x} returns the product of \spad{x} by \spad{s} on the left.
+        "*":    (%, S) -> %
+          ++ \spad{x * s} returns the product of \spad{x} by \spad{s} on the right.
+        "**":   (S, NNI) -> %
+          ++ \spad{s ** n} returns the product of \spad{s} by itself \spad{n} times.
+        first: % -> S
+          ++ \spad{first(x)} returns the first letter of \spad{x}.
+        rest:  % -> %
+          ++ \spad{rest(x)} returns \spad{x} except the first letter.
+        mirror: % -> %
+          ++ \spad{mirror(x)} returns the reversed word of \spad{x}.
+        lexico: (%,%) -> Boolean
+          ++ \spad{lexico(x,y)} returns \spad{true} iff \spad{x} is smaller than \spad{y}
+          ++ w.r.t. the pure lexicographical ordering induced by \spad{S}.
+        hclf:   (%, %) -> %
+          ++ \spad{hclf(x, y)} returns the highest common left factor 
+          ++ of \spad{x} and \spad{y},
+          ++ that is the largest \spad{d} such that \spad{x = d a} and \spad{y = d b}.
+        hcrf:   (%, %) -> %
+          ++ \spad{hcrf(x, y)} returns the highest common right 
+          ++ factor of \spad{x} and \spad{y},
+          ++ that is the largest \spad{d} such that \spad{x = a d} and \spad{y = b d}.
+        lquo:   (%, %) -> Union(%, "failed")
+          ++ \spad{lquo(x, y)} returns the exact left quotient of \spad{x}
+          ++  by \spad{y} that is \spad{q} such that \spad{x = y * q},
+          ++ "failed" if \spad{x} is not of the form \spad{y * q}.
+        rquo:   (%, %) -> Union(%, "failed")
+          ++ \spad{rquo(x, y)} returns the exact right quotient of \spad{x} 
+          ++ by \spad{y} that is \spad{q} such that \spad{x = q * y},
+          ++ "failed" if \spad{x} is not of the form \spad{q * y}.
+        lquo:   (%, S) -> Union(%, "failed")
+          ++ \spad{lquo(x, s)} returns the exact left quotient of \spad{x} 
+          ++ by \spad{s}. 
+        rquo:   (%, S) -> Union(%, "failed")
+          ++ \spad{rquo(x, s)} returns the exact right quotient 
+          ++ of \spad{x} by \spad{s}.
+        "div":   (%, %) -> Union(Record(lm: %, rm: %), "failed")
+          ++ \spad{x div y} returns the left and right exact quotients of
+          ++ \spad{x} by \spad{y}, that is \spad{[l, r]} such that \spad{x = l * y * r}.
+          ++ "failed" is returned iff \spad{x} is not of the form \spad{l * y * r}.
+        overlap: (%, %) -> Record(lm: %, mm: %, rm: %)
+          ++ \spad{overlap(x, y)} returns \spad{[l, m, r]} such that
+          ++ \spad{x = l * m} and \spad{y = m * r} hold and such that 
+          ++ \spad{l} and \spad{r} have no overlap,
+          ++ that is \spad{overlap(l, r) = [l, 1, r]}.
+        size:   % -> NNI
+          ++ \spad{size(x)} returns the number of monomials in \spad{x}.
+        nthExpon:  (%, Integer) -> NNI
+          ++ \spad{nthExpon(x, n)} returns the exponent of the 
+          ++ \spad{n-th} monomial of \spad{x}.
+        nthFactor: (%, Integer) -> S
+          ++ \spad{nthFactor(x, n)} returns the factor of the \spad{n-th} 
+          ++ monomial of \spad{x}.
+        factors: % -> List REC
+          ++ \spad{factors(a1\^e1,...,an\^en)} returns \spad{[[a1, e1],...,[an, en]]}.
+        length: % -> NNI
+          ++ \spad{length(x)} returns the length of \spad{x}.
+        varList: % -> List S
+          ++ \spad{varList(x)} returns the list of variables of \spad{x}.
+
+    OFMdefinition == FreeMonoid(S) add
+        Rep := ListMonoidOps(S, NNI, 1)
+        
+      -- definitions
+        lquo(w:%, l:S) == 
+          x: List REC := listOfMonoms(w)$Rep
+          null x        => "failed"
+          fx: REC := first x
+          fx.gen ^= l  => "failed"
+          fx.exp = 1   => makeMulti rest(x)
+          makeMulti [[fx.gen, (fx.exp - 1)::NNI ]$REC, :rest x]
+       
+        rquo(w:%, l:S) ==
+          u:% := reverse w
+          (r := lquo (u,l)) case "failed" => "failed"
+          reverse_! (r::%)
+
+        length x == reduce("+" ,[f.exp for f in listOfMonoms x], 0)
+
+        varList x ==
+          le: List S := [t.gen for t in listOfMonoms x]
+          sort_! removeDuplicates(le)
+ 
+        first w ==
+          x: List REC := listOfMonoms w
+          null x => error "empty word !!!"
+          x.first.gen
+
+        rest w ==
+          x: List REC := listOfMonoms w
+          null x => error "empty word !!!"
+          fx: REC := first x
+          fx.exp = 1 => makeMulti rest x
+          makeMulti [[fx.gen , (fx.exp - 1)::NNI ]$REC , :rest x]
+
+        lexico(a,b) ==         --  ordre lexicographique
+            la := listOfMonoms a
+            lb := listOfMonoms b
+            while (not null la) and (not null lb) repeat
+                la.first.gen > lb.first.gen => return false
+                la.first.gen < lb.first.gen => return true
+                if la.first.exp = lb.first.exp then
+                    la:=rest la
+                    lb:=rest lb
+                else if la.first.exp > lb.first.exp then
+                    la:=concat([la.first.gen,
+                           (la.first.exp - lb.first.exp)::NNI], rest lb)
+                    lb:=rest lb
+                else
+                    lb:=concat([lb.first.gen,
+                             (lb.first.exp-la.first.exp)::NNI], rest la)
+                    la:=rest la
+            empty? la and not empty? lb
+
+
+        a < b ==               --  ordre lexicographique par longueur
+            la:NNI := length a; lb:NNI := length b
+            la = lb =>  lexico(a,b)
+            la < lb 
+
+        mirror x == reverse(x)$Rep
+
+@
+\section{category FMCAT FreeModuleCat}
+<<category FMCAT FreeModuleCat>>=
+)abbrev category FMCAT FreeModuleCat
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++   A domain of this category 
+++   implements formal linear combinations
+++   of elements from a domain \spad{Basis} with coefficients
+++   in a domain \spad{R}. The domain \spad{Basis} needs only
+++   to belong to the category \spadtype{SetCategory} and \spad{R}
+++   to the category \spadtype{Ring}. Thus the coefficient ring
+++   may be non-commutative.
+++   See the \spadtype{XDistributedPolynomial} constructor
+++   for examples of domains built with the \spadtype{FreeModuleCat}
+++   category constructor.
+++   Author: Michel Petitot (petitot@lifl.fr)
+
+FreeModuleCat(R, Basis):Category == Exports where
+   R: Ring
+   Basis: SetCategory
+   TERM ==> Record(k: Basis, c: R)
+   
+   Exports == Join(BiModule(R,R), RetractableTo Basis) with
+        "*"                : (R, Basis) -> %
+          ++ \spad{r*b} returns the product of \spad{r} by \spad{b}.
+        coefficient        : (%, Basis) -> R
+          ++ \spad{coefficient(x,b)} returns the coefficient 
+          ++ of \spad{b} in \spad{x}.
+        map                : (R -> R, %) -> %
+          ++ \spad{map(fn,u)} maps function \spad{fn} onto the coefficients
+          ++  of the non-zero monomials of \spad{u}.
+        monom              : (Basis, R) -> %
+          ++ \spad{monom(b,r)} returns the element with the single monomial
+          ++  \spad{b} and coefficient \spad{r}.
+        monomial?          : % -> Boolean
+          ++ \spad{monomial?(x)} returns true if \spad{x} contains a single 
+          ++ monomial.
+        ListOfTerms        : % -> List TERM
+          ++ \spad{ListOfTerms(x)} returns a list \spad{lt} of terms with type
+          ++ \spad{Record(k: Basis, c: R)} such that \spad{x} equals
+          ++ \spad{reduce(+, map(x +-> monom(x.k, x.c), lt))}.
+        coefficients       : % -> List R           
+          ++ \spad{coefficients(x)} returns the list of coefficients of \spad{x}.
+        monomials          : % -> List %
+          ++ \spad{monomials(x)} returns the list of \spad{r_i*b_i}
+          ++ whose sum is \spad{x}.
+        numberOfMonomials  : % -> NonNegativeInteger
+          ++ \spad{numberOfMonomials(x)} returns the number of monomials of \spad{x}.
+        leadingMonomial    : % -> Basis
+          ++ \spad{leadingMonomial(x)} returns the first element from \spad{Basis}
+          ++ which appears in \spad{ListOfTerms(x)}.
+        leadingCoefficient : % -> R
+          ++ \spad{leadingCoefficient(x)} returns the first coefficient
+          ++ which appears in \spad{ListOfTerms(x)}.
+        leadingTerm        : % -> TERM 
+          ++ \spad{leadingTerm(x)} returns the first term which
+          ++ appears in \spad{ListOfTerms(x)}.
+        reductum           : % -> %
+          ++ \spad{reductum(x)} returns \spad{x} minus its leading term.
+
+      -- attributs
+        if R has CommutativeRing then Module(R)
+
+@
+\section{domain FM1 FreeModule1}
+<<domain FM1 FreeModule1>>=
+)abbrev domain FM1 FreeModule1
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++   This domain implements linear combinations
+++   of elements from the domain \spad{S} with coefficients
+++   in the domain \spad{R} where \spad{S} is an ordered set
+++   and \spad{R} is a ring (which may be non-commutative).
+++   This domain is used by domains of non-commutative algebra such as:
+++       \spadtype{XDistributedPolynomial},
+++       \spadtype{XRecursivePolynomial}.
+++   Author: Michel Petitot (petitot@lifl.fr)
+
+FreeModule1(R:Ring,S:OrderedSet): FMcat == FMdef where
+  EX ==> OutputForm
+  TERM ==> Record(k:S,c:R)
+
+  FMcat == FreeModuleCat(R,S) with
+    "*":(S,R) -> %
+      ++ \spad{s*r} returns the product \spad{r*s}
+      ++ used by \spadtype{XRecursivePolynomial} 
+  FMdef == FreeModule(R,S) add
+    -- representation
+      Rep := List TERM  
+
+    -- declarations
+      lt: List TERM 
+      x : %
+      r : R
+      s : S
+
+    -- define
+      numberOfMonomials p ==
+         # (p::Rep)
+
+      ListOfTerms(x) == x:List TERM 
+
+      leadingTerm x == x.first
+      leadingMonomial x == x.first.k
+      coefficients x == [t.c for t in x]
+      monomials x == [ monom (t.k, t.c) for t in x]
+
+      retractIfCan x ==
+         numberOfMonomials(x) ^= 1 => "failed"
+         x.first.c = 1 => x.first.k
+         "failed"
+
+      coerce(s:S):% == [[s,1$R]]
+      retract x ==
+         (rr := retractIfCan x) case "failed" => error "FM1.retract impossible"
+         rr :: S
+
+      if R has noZeroDivisors then
+         r * x  ==
+             r = 0 => 0
+             [[u.k,r * u.c]$TERM for u in x]
+         x * r  == 
+             r = 0 => 0
+             [[u.k,u.c * r]$TERM for u in x]
+       else
+         r * x  ==
+             r = 0 => 0
+             [[u.k,a] for u in x | not (a:=r*u.c)= 0$R]
+         x * r  ==
+             r = 0 => 0
+             [[u.k,a] for u in x | not (a:=u.c*r)= 0$R]
+
+      r * s ==
+        r = 0 => 0
+        [[s,r]$TERM]
+
+      s * r ==
+        r = 0 => 0
+        [[s,r]$TERM]
+
+      monom(b,r):% == [[b,r]$TERM] 
+
+      outTerm(r:R, s:S):EX ==
+            r=1  => s::EX
+            r::EX * s::EX
+
+      coerce(a:%):EX ==
+            empty? a => (0$R)::EX
+            reduce(_+, reverse_! [outTerm(t.c, t.k) for t in a])$List(EX)
+
+      coefficient(x,s) ==
+         null x => 0$R
+         x.first.k > s => coefficient(rest x,s)
+         x.first.k = s => x.first.c
+         0$R
+
+@
+\section{category XALG XAlgebra}
+<<category XALG XAlgebra>>=
+)abbrev category XALG XAlgebra
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++   This is the category of algebras over non-commutative rings.
+++   It is used by constructors of non-commutative algebras such as:
+++       \spadtype{XPolynomialRing}.
+++       \spadtype{XFreeAlgebra}
+++   Author: Michel Petitot (petitot@lifl.fr)
+
+XAlgebra(R: Ring): Category == 
+  Join(Ring, BiModule(R,R)) with
+    --operations
+      coerce: R -> %
+          ++ \spad{coerce(r)} equals  \spad{r*1}.
+    -- attributs
+      if R has CommutativeRing then Algebra(R)
+      -- if R has CommutativeRing then Module(R) 
+-- add
+--  coerce(x:R):% == x * 1$%
+
+@
+\section{category XFALG XFreeAlgebra}
+<<category XFALG XFreeAlgebra>>=
+)abbrev category XFALG XFreeAlgebra
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++    This category specifies opeations for  polynomials
+++    and formal series with non-commutative variables.
+++ Author: Michel Petitot (petitot@lifl.fr)
+
+XFreeAlgebra(vl:OrderedSet,R:Ring):Category == Catdef where
+   WORD   ==> OrderedFreeMonoid(vl)          -- monoide libre
+   NNI    ==> NonNegativeInteger
+   I      ==> Integer
+   TERM   ==> Record(k: WORD, c: R)
+
+   Catdef == Join(Ring, XAlgebra(R), RetractableTo WORD) 
+     with
+       "*": (vl,%) -> %
+         ++ \spad{v * x} returns the product of a variable \spad{x} by \spad{x}.
+       "*": (%, R) -> %                 
+         ++ \spad{x * r} returns the product of \spad{x} by \spad{r}.
+         ++ Usefull if \spad{R} is a non-commutative Ring.
+       mindeg: % -> WORD                
+         ++ \spad{mindeg(x)} returns the little word which appears in \spad{x}.
+         ++ Error if \spad{x=0}.
+       mindegTerm: % -> TERM 
+         ++ \spad{mindegTerm(x)} returns the term whose word is \spad{mindeg(x)}.
+       coef  : (%,WORD) -> R            
+         ++ \spad{coef(x,w)} returns the coefficient of the word \spad{w} in \spad{x}. 
+       coef  : (%,%) -> R
+         ++ \spad{coef(x,y)} returns scalar product of \spad{x} by \spad{y},
+         ++ the set of words being regarded as an orthogonal basis.
+       lquo  : (%,vl) -> %              
+         ++ \spad{lquo(x,v)} returns the left simplification of \spad{x} by the variable \spad{v}.
+       lquo  : (%,WORD) -> %            
+         ++ \spad{lquo(x,w)} returns the left simplification of \spad{x} by the word \spad{w}.
+       lquo  : (%,%) -> %
+         ++ \spad{lquo(x,y)} returns the left simplification of \spad{x} by \spad{y}.
+       rquo  : (%,vl) -> %
+         ++ \spad{rquo(x,v)} returns the right simplification of \spad{x} by the variable \spad{v}.
+       rquo  : (%,WORD) -> %
+         ++ \spad{rquo(x,w)} returns the right simplification of \spad{x} by \spad{w}.
+       rquo  : (%,%) -> %
+         ++ \spad{rquo(x,y)} returns the right simplification of \spad{x} by \spad{y}.
+       monom : (WORD , R) -> %
+         ++ \spad{monom(w,r)} returns the product of the word \spad{w} by the coefficient \spad{r}.
+       monomial? : % -> Boolean
+         ++ \spad{monomial?(x)} returns true if \spad{x} is a monomial
+       mirror: % -> %                   
+         ++ \spad{mirror(x)} returns \spad{Sum(r_i mirror(w_i))} if \spad{x} writes \spad{Sum(r_i w_i)}. 
+       coerce : vl -> %
+         ++ \spad{coerce(v)} returns \spad{v}.
+       constant?:% -> Boolean
+         ++ \spad{constant?(x)} returns true if \spad{x} is constant.
+       constant: % -> R   
+         ++ \spad{constant(x)} returns the constant term of \spad{x}.
+       quasiRegular? : % -> Boolean  
+         ++ \spad{quasiRegular?(x)} return true if \spad{constant(x)} is zero. 
+       quasiRegular : % -> %
+         ++ \spad{quasiRegular(x)} return \spad{x} minus its constant term.
+       if R has CommutativeRing then
+          sh :(%,%) -> %
+             ++ \spad{sh(x,y)} returns the shuffle-product of \spad{x} by \spad{y}.
+             ++ This multiplication is associative and commutative.
+          sh :(%,NNI) -> %
+             ++ \spad{sh(x,n)} returns the shuffle power of \spad{x} to the \spad{n}.
+       map   : (R -> R, %) -> %
+         ++ \spad{map(fn,x)} returns \spad{Sum(fn(r_i) w_i)} if \spad{x} writes \spad{Sum(r_i w_i)}.
+       varList: % -> List vl
+         ++ \spad{varList(x)} returns the list of variables which appear in \spad{x}.
+
+     -- Attributs
+       if R has noZeroDivisors then noZeroDivisors
+
+@
+\section{category XPOLYC XPolynomialsCat}
+<<category XPOLYC XPolynomialsCat>>=
+)abbrev category XPOLYC XPolynomialsCat
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++   The Category of polynomial rings with non-commutative variables.
+++   The coefficient ring may be non-commutative too. 
+++   However coefficients commute with vaiables.
+++ Author: Michel Petitot (petitot@lifl.fr)
+
+XPolynomialsCat(vl:OrderedSet,R:Ring):Category == Export where
+  WORD ==> OrderedFreeMonoid(vl)
+
+  Export == XFreeAlgebra(vl,R) with
+    maxdeg: % -> WORD 
+      ++ \spad{maxdeg(p)} returns the greatest leading word in the support of \spad{p}.
+    degree: % -> NonNegativeInteger 
+      ++ \spad{degree(p)} returns the degree of \spad{p}. 
+      ++  Note that the degree of a word is its length. 
+    trunc : (% , NonNegativeInteger) -> %
+      ++  \spad{trunc(p,n)} returns the polynomial \spad{p} truncated at order \spad{n}.
+
+@
+\section{domain XPR XPolynomialRing}
+<<domain XPR XPolynomialRing>>=
+)abbrev domain XPR XPolynomialRing
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++ This domain represents generalized polynomials with coefficients
+++ (from a not necessarily commutative ring), and words
+++ belonging to an arbitrary \spadtype{OrderedMonoid}.
+++ This type is used, for instance, by the \spadtype{XDistributedPolynomial} 
+++ domain constructor where the Monoid is free.
+++ Author: Michel Petitot (petitot@lifl.fr)
+
+XPolynomialRing(R:Ring,E:OrderedMonoid): T == C where
+  TERM   ==> Record(k: E, c: R)
+  EX     ==> OutputForm
+  NNI    ==> NonNegativeInteger
+
+  T == Join(Ring, XAlgebra(R), FreeModuleCat(R,E)) with
+    --operations
+      "*": (%,R) -> %
+        ++ \spad{p*r} returns the product of \spad{p} by \spad{r}.
+      "#": % -> NonNegativeInteger
+        ++ \spad{# p} returns the number of terms in \spad{p}.
+      coerce: E -> %
+        ++ \spad{coerce(e)} returns \spad{1*e}
+      maxdeg: % -> E
+        ++ \spad{maxdeg(p)} returns the greatest word occurring in the polynomial \spad{p}
+        ++ with a non-zero coefficient. An error is produced if  \spad{p} is zero.
+      mindeg: % -> E
+        ++ \spad{mindeg(p)} returns the smallest word occurring in the polynomial \spad{p}
+        ++ with a non-zero coefficient. An error is produced if  \spad{p} is zero.
+      reductum : % -> %   
+        ++ \spad{reductum(p)} returns \spad{p} minus its leading term.
+        ++ An error is produced if  \spad{p} is zero.
+      coef  : (%,E) -> R
+        ++ \spad{coef(p,e)} extracts the coefficient of the monomial \spad{e}.
+        ++ Returns zero if \spad{e} is not present. 
+      constant?:% -> Boolean
+        ++ \spad{constant?(p)} tests whether the polynomial \spad{p} belongs to the
+        ++ coefficient ring.
+      constant: % -> R
+        ++ \spad{constant(p)} return the constant term of \spad{p}.
+      quasiRegular? : % -> Boolean
+        ++ \spad{quasiRegular?(x)} return true if \spad{constant(p)} is zero.
+      quasiRegular : % -> % 
+        ++ \spad{quasiRegular(x)} return \spad{x} minus its constant term.
+      map   : (R -> R, %) -> %
+        ++ \spad{map(fn,x)} returns \spad{Sum(fn(r_i) w_i)} if \spad{x} writes \spad{Sum(r_i w_i)}.
+      if R has Field then "/" : (%,R) -> %
+        ++ \spad{p/r} returns \spad{p*(1/r)}.
+
+    --assertions
+      if R has noZeroDivisors then noZeroDivisors
+      if R has unitsKnown then unitsKnown
+      if R has canonicalUnitNormal then canonicalUnitNormal
+          ++ canonicalUnitNormal guarantees that the function
+          ++ unitCanonical returns the same representative for all
+          ++ associates of any particular element.
+
+
+  C == FreeModule1(R,E) add
+    --representations
+       Rep:=  List TERM
+    --uses
+       repeatMultExpt: (%,NonNegativeInteger) -> %
+    --define
+       1  == [[1$E,1$R]]
+ 
+       characteristic  == characteristic$R
+       #x == #$Rep x
+       maxdeg p == if null p then  error " polynome nul !!"
+                             else p.first.k
+       mindeg p == if null p then  error " polynome nul !!" 
+                             else (last p).k
+       
+       coef(p,e)  ==
+          for tm in p repeat
+            tm.k=e => return tm.c
+            tm.k < e => return 0$R
+          0$R
+
+       constant? p == (p = 0) or (maxdeg(p) = 1$E)
+       constant  p == coef(p,1$E)
+
+       quasiRegular? p == (p=0) or (last p).k ^= 1$E
+       quasiRegular  p == 
+          quasiRegular?(p) => p
+          [t for t in p | not(t.k = 1$E)]
+
+       recip(p) ==
+           p=0 => "failed"
+           p.first.k > 1$E => "failed"
+           (u:=recip(p.first.c)) case "failed" => "failed"
+           (u::R)::%
+ 
+       coerce(r:R) == if r=0$R then 0$% else [[1$E,r]]
+       coerce(n:Integer) == (n::R)::%
+ 
+       if R has noZeroDivisors then
+         p1:% * p2:%  ==
+            null p1 => 0
+            null p2 => 0
+            p1.first.k = 1$E => p1.first.c * p2
+            p2 = 1 => p1
+--            +/[[[t1.k*t2.k,t1.c*t2.c]$TERM for t2 in p2]
+--                   for t1 in reverse(p1)]
+            +/[[[t1.k*t2.k,t1.c*t2.c]$TERM for t2 in p2]
+                   for t1 in p1]
+        else
+         p1:% * p2:%  ==
+            null p1 => 0
+            null p2 => 0
+            p1.first.k = 1$E => p1.first.c * p2
+            p2 = 1 => p1
+--            +/[[[t1.k*t2.k,r]$TERM for t2 in p2 | not (r:=t1.c*t2.c) =$R 0]
+--                 for t1 in reverse(p1)]
+            +/[[[t1.k*t2.k,r]$TERM for t2 in p2 | not (r:=t1.c*t2.c) =$R 0]
+                   for t1 in p1]
+       p:% ** nn:NNI  == repeatMultExpt(p,nn)
+       repeatMultExpt(x,nn) ==
+               nn = 0 => 1
+               y:% := x
+               for i in 2..nn repeat y:= x * y
+               y
+              
+       outTerm(r:R, m:E):EX ==
+            r=1 => m::EX
+            m=1 => r::EX
+            r::EX * m::EX
+
+--       coerce(x:%) : EX ==
+--         null x => (0$R) :: EX
+--         le : List EX := nil
+--         for rec in x repeat
+--           rec.c = 1$R => le := cons(rec.k :: EX, le)
+--           rec.k = 1$E => le := cons(rec.c :: EX, le)
+--           le := cons(mkBinary("*"::EX,rec.c :: EX,
+--             rec.k :: EX), le)
+--         1 = #le => first le
+--         mkNary("+" :: EX,le)
+
+       coerce(a:%):EX ==
+            empty? a => (0$R)::EX
+            reduce(_+, reverse_! [outTerm(t.c, t.k) for t in a])$List(EX)
+
+ 
+       if R has Field then
+          x/r == inv(r)*x
+
+@
+\section{domain XDPOLY XDistributedPolynomial}
+Polynomial arithmetic with non-commutative variables has been improved
+by a contribution of Michel Petitot (University of Lille I, France).
+The domain constructor
+{\bf XDistributedPolynomial} provide a distributed
+representation for these polynomials. It is the non-commutative
+equivalent for the 
+{\bf DistributedMultivariatePolynomial} constructor.
+<<domain XDPOLY XDistributedPolynomial>>=
+)abbrev domain XDPOLY XDistributedPolynomial
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++   This type supports distributed multivariate polynomials
+++ whose variables do not commute.
+++ The coefficient ring may be non-commutative too.
+++ However, coefficients and variables commute.
+++ Author: Michel Petitot (petitot@lifl.fr)
+
+XDistributedPolynomial(vl:OrderedSet,R:Ring): XDPcat == XDPdef where
+
+  WORD ==> OrderedFreeMonoid(vl)
+  I    ==> Integer
+  NNI  ==> NonNegativeInteger
+  TERM ==> Record(k:WORD, c:R)
+
+  XDPcat == Join(FreeModuleCat(R, WORD), XPolynomialsCat(vl,R))
+
+  XDPdef == XPolynomialRing(R,WORD) add
+
+       import( WORD, TERM)
+
+    -- Representation
+       Rep  :=  List TERM
+
+    -- local functions
+       shw: (WORD , WORD) -> %    -- shuffle de 2 mots
+
+    -- definitions
+
+       mindegTerm p == last(p)$Rep
+
+       if R has CommutativeRing then
+         sh(p:%, n:NNI):% ==
+            n=0 => 1
+            n=1 => p
+            n1: NNI := (n-$I 1)::NNI
+            sh(p, sh(p,n1))
+
+      
+         sh(p1:%, p2:%) ==
+           p:% := 0 
+           for t1 in p1 repeat
+             for t2 in p2 repeat
+                p := p + (t1.c * t2.c) * shw(t1.k,t2.k) 
+           p
+
+       coerce(v: vl):% == coerce(v::WORD)
+       v:vl * p:% ==
+         [[v * t.k , t.c]$TERM for t in p]
+
+       mirror p == 
+         null p => p
+         monom(mirror$WORD leadingMonomial p, leadingCoefficient p) + _
+               mirror reductum p
+
+       degree(p) == length(maxdeg(p))$WORD
+
+       trunc(p, n) ==
+         p = 0 => p
+         degree(p) > n => trunc( reductum p , n)
+         p
+
+       varList p ==
+         constant? p => []
+         le : List vl := "setUnion"/[varList(t.k) for t in p]
+         sort_!(le)
+
+       rquo(p:% , w: WORD) == 
+         [[r::WORD,t.c]$TERM for t in p | not (r:= rquo(t.k,w)) case "failed" ]
+       lquo(p:% , w: WORD) ==
+         [[r::WORD,t.c]$TERM for t in p | not (r:= lquo(t.k,w)) case "failed" ]
+       rquo(p:% , v: vl) ==
+         [[r::WORD,t.c]$TERM for t in p | not (r:= rquo(t.k,v)) case "failed" ]
+       lquo(p:% , v: vl) ==
+         [[r::WORD,t.c]$TERM for t in p | not (r:= lquo(t.k,v)) case "failed" ]
+
+       shw(w1,w2) ==
+         w1 = 1$WORD => w2::%
+         w2 = 1$WORD => w1::%
+         x: vl := first w1 ; y: vl := first w2
+         x * shw(rest w1,w2) + y * shw(w1,rest w2)
+ 
+       lquo(p:%,q:%):% ==
+         +/  [r * t.c for t in q | (r := lquo(p,t.k)) ^= 0] 
+
+       rquo(p:%,q:%):% ==
+         +/  [r * t.c for t in q | (r := rquo(p,t.k)) ^= 0] 
+
+       coef(p:%,q:%):R ==
+         p = 0 => 0$R
+         q = 0 => 0$R 
+         p.first.k > q.first.k => coef(p.rest,q)
+         p.first.k < q.first.k => coef(p,q.rest) 
+         return p.first.c * q.first.c + coef(p.rest,q.rest)
+
+@
+\section{domain XRPOLY XRecursivePolynomial}
+Polynomial arithmetic with non-commutative variables has been improved
+by a contribution of Michel Petitot (University of Lille I, France).
+The domain constructors {\bf XRecursivePolynomial} 
+provides a recursive for these polynomials. It is the non-commutative
+equivalents for the {\bf SparseMultivariatePolynomial} constructor.
+<<domain XRPOLY XRecursivePolynomial>>=
+)abbrev domain XRPOLY XRecursivePolynomial
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++   extend renomme en expand
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++   This type supports multivariate polynomials
+++ whose variables do not commute.
+++ The representation is recursive.
+++ The coefficient ring may be non-commutative.
+++ Coefficients and variables commute.
+++ Author: Michel Petitot (petitot@lifl.fr)
+
+XRecursivePolynomial(VarSet:OrderedSet,R:Ring):  Xcat == Xdef where
+  I      ==> Integer
+  NNI    ==> NonNegativeInteger
+  XDPOLY ==> XDistributedPolynomial(VarSet, R)
+  EX     ==> OutputForm
+  WORD   ==> OrderedFreeMonoid(VarSet)
+  TERM   ==> Record(k:VarSet , c:%)
+  LTERMS ==> List(TERM) 
+  REGPOLY==> FreeModule1(%, VarSet) 
+  VPOLY  ==> Record(c0:R, reg:REGPOLY)
+
+  Xcat == XPolynomialsCat(VarSet,R) with
+       expand: % -> XDPOLY
+         ++ \spad{expand(p)} returns \spad{p} in distributed form.
+       unexpand : XDPOLY -> %
+         ++ \spad{unexpand(p)} returns \spad{p} in recursive form.
+       RemainderList: % -> LTERMS
+         ++ \spad{RemainderList(p)} returns the regular part of \spad{p}
+         ++ as a list of terms.
+
+  Xdef == add
+       import(VPOLY)
+
+    -- representation
+       Rep     := Union(R,VPOLY)
+
+    -- local functions
+       construct: LTERMS -> REGPOLY
+       simplifie: VPOLY -> %
+       lquo1: (LTERMS,LTERMS) -> %        ++ a ajouter
+       coef1: (LTERMS,LTERMS) -> R        ++ a ajouter
+       outForm: REGPOLY -> EX
+
+    --define
+       construct(lt) == lt pretend REGPOLY
+       p1:%  =  p2:%  ==
+         p1 case R =>
+             p2 case R => p1 =$R p2
+             false
+         p2 case R => false
+         p1.c0 =$R p2.c0 and p1.reg =$REGPOLY p2.reg
+
+       monom(w, r) == 
+         r =0 => 0
+         r * w::%
+
+--       if R has Field then                  -- Bug non resolu !!!!!!!!
+--         p:% / r: R == inv(r) * p
+ 
+       rquo(p1:%, p2:%):% ==
+         p2 case R => p1 * p2::R
+         p1 case R => p1  * p2.c0
+         x:REGPOLY := construct [[t.k, a]$TERM for t in ListOfTerms(p1.reg) _
+                         | (a:= rquo(t.c,p2)) ^= 0$% ]$LTERMS
+         simplifie [coef(p1,p2) , x]$VPOLY
+
+       trunc(p,n) ==
+         n = 0 or (p case R) => (constant p)::%
+         n1: NNI := (n-1)::NNI
+         lt: LTERMS := [[t.k, r]$TERM for t in ListOfTerms p.reg _
+                        | (r := trunc(t.c, n1)) ^= 0]$LTERMS
+         x: REGPOLY := construct lt
+         simplifie [constant p, x]$VPOLY
+
+       unexpand p ==
+         constant? p => (constant p)::%
+         vl: List VarSet := sort(#1 > #2, varList p)
+         x : REGPOLY := _
+           construct [[v, unexpand r]$TERM for v in vl| (r:=lquo(p,v)) ^= 0]
+         [constant p, x]$VPOLY
+
+       if R has CommutativeRing then
+         sh(p:%, n:NNI):% ==
+            n = 0 => 1
+            p case R => (p::R)** n
+            n1: NNI := (n-1)::NNI
+            p1: % := n * sh(p, n1)  
+            lt: LTERMS := [[t.k, sh(t.c, p1)]$TERM for t in ListOfTerms p.reg]
+            [p.c0 ** n, construct lt]$VPOLY
+ 
+         sh(p1:%, p2:%) ==
+            p1 case R => p1::R * p2
+            p2 case R => p1 * p2::R 
+            lt1:LTERMS := ListOfTerms p1.reg ; lt2:LTERMS := ListOfTerms p2.reg
+            x: REGPOLY := construct [[t.k,sh(t.c,p2)]$TERM for t in lt1]
+            y: REGPOLY := construct [[t.k,sh(p1,t.c)]$TERM for t in lt2]
+            [p1.c0*p2.c0,x + y]$VPOLY
+
+       RemainderList p == 
+           p case R => []
+           ListOfTerms( p.reg)$REGPOLY
+ 
+       lquo(p1:%,p2:%):% ==
+         p2 case R => p1 * p2
+         p1 case R => p1  *$R p2.c0
+         p1 * p2.c0 +$% lquo1(ListOfTerms p1.reg, ListOfTerms p2.reg)
+
+       lquo1(x:LTERMS,y:LTERMS):% ==
+         null x => 0$%  
+         null y => 0$%
+         x.first.k < y.first.k => lquo1(x,y.rest)
+         x.first.k = y.first.k => 
+             lquo(x.first.c,y.first.c) + lquo1(x.rest,y.rest)
+         return lquo1(x.rest,y)
+
+       coef(p1:%, p2:%):R ==
+         p1 case R => p1::R * constant p2
+         p2 case R => p1.c0 * p2::R
+         p1.c0 * p2.c0 +$R coef1(ListOfTerms p1.reg, ListOfTerms p2.reg)
+
+       coef1(x:LTERMS,y:LTERMS):R ==
+         null x => 0$R
+         null y => 0$R
+         x.first.k < y.first.k => coef1(x,y.rest)
+         x.first.k = y.first.k =>
+             coef(x.first.c,y.first.c) + coef1(x.rest,y.rest)
+         return coef1(x.rest,y)
+
+       --------------------------------------------------------------
+       outForm(p:REGPOLY): EX ==
+          le : List EX :=  [t.k::EX * t.c::EX for t in ListOfTerms p]
+          reduce(_+, reverse_! le)$List(EX)
+
+       coerce(p:$): EX ==
+          p case R => (p::R)::EX
+          p.c0 = 0 => outForm p.reg
+          p.c0::EX + outForm p.reg 
+
+       0 == 0$R::%
+       1 == 1$R::%
+       constant? p ==  p case R
+       constant p == 
+          p case R => p
+          p.c0
+
+       simplifie p ==
+         p.reg = 0$REGPOLY => (p.c0)::%
+         p
+
+       coerce (v:VarSet):% ==
+         [0$R,coerce(v)$REGPOLY]$VPOLY
+
+       coerce (r:R):% == r::%
+       coerce (n:Integer) == n::R::%
+       coerce (w:WORD) == 
+         w = 1 => 1$R
+         (first w) * coerce(rest w)
+ 
+       expand p ==
+         p case R => p::R::XDPOLY
+         lt:LTERMS := ListOfTerms(p.reg)
+         ep:XDPOLY := (p.c0)::XDPOLY
+         for t in lt repeat
+           ep:= ep + t.k * expand(t.c)
+         ep
+                
+       - p:% ==
+         p case R => -$R p
+         [- p.c0, - p.reg]$VPOLY
+ 
+       p1 + p2 ==
+         p1 case R and p2 case R => p1 +$R p2
+         p1 case R => [p1 + p2.c0 , p2.reg]$VPOLY
+         p2 case R => [p2 + p1.c0 , p1.reg]$VPOLY 
+         simplifie [p1.c0 + p2.c0 , p1.reg +$REGPOLY p2.reg]$VPOLY
+ 
+       p1 - p2 ==
+         p1 case R and p2 case R => p1 -$R p2
+         p1 case R => [p1 - p2.c0 , -p2.reg]$VPOLY
+         p2 case R => [p1.c0 - p2 , p1.reg]$VPOLY
+         simplifie [p1.c0 - p2.c0 , p1.reg -$REGPOLY p2.reg]$VPOLY
+ 
+       n:Integer * p:% ==
+         n=0 => 0$%
+         p case R => n *$R p
+         -- [ n*p.c0,n*p.reg]$VPOLY
+         simplifie [ n*p.c0,n*p.reg]$VPOLY
+
+       r:R * p:% ==
+         r=0 => 0$%
+         p case R => r *$R p
+         -- [ r*p.c0,r*p.reg]$VPOLY
+         simplifie [ r*p.c0,r*p.reg]$VPOLY
+
+       p:% * r:R ==
+         r=0 => 0$%
+         p case R => p *$R r
+         -- [ p.c0 * r,p.reg * r]$VPOLY
+         simplifie [ r*p.c0,r*p.reg]$VPOLY
+
+       v:VarSet * p:% == 
+          p = 0 => 0$%
+          [0$R, v *$REGPOLY p]$VPOLY
+ 
+       p1:% * p2:% ==
+         p1 case R => p1::R * p2
+         p2 case R => p1 * p2::R
+         x:REGPOLY := p1.reg *$REGPOLY p2
+         y:REGPOLY := (p1.c0)::% *$REGPOLY p2.reg  -- maladroit:(p1.c0)::% !!
+         -- [ p1.c0 * p2.c0 , x+y ]$VPOLY
+         simplifie [ p1.c0 * p2.c0 , x+y ]$VPOLY
+
+       lquo(p:%, v:VarSet):% ==
+         p case R => 0
+         coefficient(p.reg,v)$REGPOLY
+
+       lquo(p:%, w:WORD):% ==
+         w = 1$WORD => p
+         lquo(lquo(p,first w),rest w)
+
+       rquo(p:%, v:VarSet):% ==
+         p case R => 0
+         x:REGPOLY := construct [[t.k, a]$TERM for t in ListOfTerms(p.reg)
+                         | (a:= rquo(t.c,v)) ^= 0 ]
+         simplifie [constant(coefficient(p.reg,v)) , x]$VPOLY 
+        
+       rquo(p:%, w:WORD):% ==
+         w = 1$WORD => p
+         rquo(rquo(p,rest w),first w)
+ 
+       coef(p:%, w:WORD):R ==
+         constant lquo(p,w)
+
+       quasiRegular? p == 
+         p case R => p = 0$R
+         p.c0 = 0$R
+
+       quasiRegular p ==
+         p case R => 0$%
+         [0$R,p.reg]$VPOLY
+
+       characteristic == characteristic()$R
+       recip p ==
+         p case R => recip(p::R)
+         "failed"
+
+       mindeg p ==
+         p case R =>
+           p = 0 => error "XRPOLY.mindeg: polynome nul !!"
+           1$WORD
+         p.c0 ^= 0 => 1$WORD
+         "min"/[(t.k) *$WORD mindeg(t.c) for t in ListOfTerms p.reg] 
+
+       maxdeg p ==
+         p case R => 
+            p = 0 => error "XRPOLY.maxdeg: polynome nul !!"
+            1$WORD
+         "max"/[(t.k) *$WORD maxdeg(t.c) for t in ListOfTerms p.reg] 
+
+       degree p == 
+          p = 0 => error "XRPOLY.degree: polynome nul !!"
+          length(maxdeg p)
+
+       map(fn,p) ==
+         p case R => fn(p::R)
+         x:REGPOLY := construct [[t.k,a]$TERM for t in ListOfTerms p.reg
+                         |(a := map(fn,t.c)) ^= 0$R]
+         simplifie [fn(p.c0),x]$VPOLY
+
+       varList p ==
+         p case R => []
+         lv: List VarSet := "setUnion"/[varList(t.c) for t in ListOfTerms p.reg]
+         lv:= setUnion(lv,[t.k for t in ListOfTerms p.reg])
+         sort_!(lv)
+
+@
+\section{domain XPOLY XPolynomial}
+<<domain XPOLY XPolynomial>>=
+)abbrev domain XPOLY XPolynomial
+++ Author: Michel Petitot petitot@lifl.fr
+++ Date Created: 91
+++ Date Last Updated: 7 Juillet 92
+++ Fix History: compilation v 2.1 le 13 dec 98
+++   extend renomme en expand
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References:
+++ Description:
+++   This type supports multivariate polynomials
+++ whose set of variables is \spadtype{Symbol}.
+++ The representation is recursive.
+++ The coefficient ring may be non-commutative and the variables 
+++ do not commute.
+++ However, coefficients and variables commute.
+++ Author: Michel Petitot (petitot@lifl.fr)
+
+XPolynomial(R:Ring) == XRecursivePolynomial(Symbol, R)
+
+@
+\section{License}
+<<license>>=
+--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+--All rights reserved.
+--
+--Redistribution and use in source and binary forms, with or without
+--modification, are permitted provided that the following conditions are
+--met:
+--
+--    - Redistributions of source code must retain the above copyright
+--      notice, this list of conditions and the following disclaimer.
+--
+--    - Redistributions in binary form must reproduce the above copyright
+--      notice, this list of conditions and the following disclaimer in
+--      the documentation and/or other materials provided with the
+--      distribution.
+--
+--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+--      names of its contributors may be used to endorse or promote products
+--      derived from this software without specific prior written permission.
+--
+--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+@
+<<*>>=
+<<license>>
+
+<<domain OFMONOID OrderedFreeMonoid>>
+<<category FMCAT FreeModuleCat>>
+<<domain FM1 FreeModule1>>
+<<category XALG XAlgebra>>
+<<category XFALG XFreeAlgebra>>
+<<category XPOLYC XPolynomialsCat>>
+<<domain XPR XPolynomialRing>>
+<<domain XDPOLY XDistributedPolynomial>>
+<<domain XRPOLY XRecursivePolynomial>>
+<<domain XPOLY XPolynomial>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}