[Axiom-developer] Re: 1/x x = 1 is a bug!

[Page, Bill]

William,

This thread seems to go on forever ... but I feel compelled
to continue it because: 1) I think understanding how this
works is critical to understanding and using Axiom, 2) I don't
think we have a simple explanation yet of something that really
should be simple in principle, if not in it's application in
certain cases.

As a long term user of Axiom, I really appreciate you input
on this subject. But I think I must take exception to your
conclusion as stated in the subject line. :)

On Thu, 23 Feb 2006 01:07:56 -0600 at

http://wiki.axiom-developer.org/270IntegratingUTS#bottom

You wrote:

> Now Axiom having been forced to output the same identifier
> for two different variables, the first x bound to a variable
> in FRAC POLY INT, and the second x bound to the main variable
> of ULS, should NOT then simplify the expression 1/x x of (3)
> to 1.

First, I would prefer that we try not to introduce new words
like "identifier" since Axiom already calls these by the name
Symbol. Second, I worry that you are using the word "bound"
in a manner that does not really apply to Axiom. And third,
I think the use of the word "variable" in Axiom has to be
applied with some care.

When you say "x bound to a variable in FRAC POLY INT" I
think you mean only that the symbol 'x' is used as a
polynomial variable in this domain. Exactly what a
"polynomial variable" is, is defined by the specific
implementation of 'FRAC POLY INT', but we know for sure
that it will appear in the List of Symbols that is returned
by the function 'variables' when applied to any member of
this domain. And these symbols also play a role in many
other functions exported by this domain.

If I write things below that are completely obvious to you,
please bear with me and consider it just a short review. Of
course also correct me if I get it wrong. I am assuming that
there are other readers who need might this sort of review.

As you know, Symbols themselves form a domain in Axiom:

  )sh Symbol

I think there is a lot of unnecessary confusion between
symbols and variables.

By definition Symbols are constants and can not be assigned
values. Operations like

  = : (Symbol,Symbol) -> Boolean

compare one symbol to another. There are other operations that
construct new symbols possibly with sub/super-scripts etc. It
might be surprising how sophisticated Axiom's Symbol domain is
and how much of it is coded in SPAD:

http://wiki.axiom-developer.org/axiom--test--1/src/algebra/SymbolSpad

But of course ultimately all Symbols are represented and
manipulated by Lisp, e.g.:

    coerce(s:String):%     == VALUES(INTERN(s)$Lisp)$Lisp
    x = y                  == EQUAL(x,y)$Lisp

Variables also form a domain in Axiom:

  )sh Variable

Variables are constructed from Symbols, but not all symbols
are necessarily used for this purpose. Members of the Variable
domain in turn can be assigned values and have associated
types.

It may seem strange but Variables are **not** used to form
polynomials in Axiom.

----------

Let's consider the following somewhat simplified example
where Axiom will coerce '1/x x' to 1:

(1) -> (1/x)$UP(x,FRAC POLY INT)*x

        1
   (1)  - x
        x
   Type: UnivariatePolynomial(x,Fraction Polynomial Integer)

Here '1/x' is a coefficient and polynomial variable 'x' is
written to the right of the coefficient. Both uses of 'x'
represent the same Symbol and neither of these are from the
domain Variable.

There is no operation within the domain 'UP(x,FRAC POLY INT)'
which would allow us to conclude that '1/x x' is identical
to 1 even though these are both members of this domain. We
know intuitively however that this expression should be 1
in some other domain, but showing this formally apparently
involves some rather deep knowledge about "fractional ideals"
that is beyond me.

(2) -> )set message bottomup on
(2) -> )set message autoload on
(2) -> %::FRAC UP(x,POLY INT)

 Function Selection for map by coercion facility (map)
      Arguments: ((POLY INT -> UP(x,POLY INT)),FRAC POLY INT)
      Target type: FRAC UP(x,POLY INT)
   -> no appropriate map found in Fraction Polynomial Integer
   -> no appropriate map found in
        Fraction UnivariatePolynomial(x,Polynomial Integer)
   -> no appropriate map found in
        UnivariatePolynomial(x,Polynomial Integer)
   -> no appropriate map found in Polynomial Integer
   -> no appropriate map found in
        UnivariatePolynomial(x,Polynomial Integer)

 Modemaps from Associated Packages
   [1] ((D7 -> D11),FractionalIdeal(D7,D8,D9,D10)) ->
         FractionalIdeal(D11,D1,D2,D3)
            from FractionalIdealFunctions2(D7,D8,D9,D10,D11,D1,D2,D3)
            if D7 has EUCDOM and D8 has QFCAT D7 and D9 has UPOLYC D8
            and D10 has Join(FramedAlgebra(D8,D9),RetractableTo D8) and
            D11 has EUCDOM and D1 has QFCAT D11 and D2 has UPOLYC D1
            and D3 has Join(FramedAlgebra(D1,D2),RetractableTo D1)
   [2] ((D4 -> D5),Fraction D4) ->
        Fraction D5 from FractionFunctions2(D4,D5)
            if D4 has INTDOM and D5 has INTDOM

 [1]  signature:   ((POLY INT -> UP(x,POLY INT)),FRAC POLY INT) ->
                   FRAC UP(x,POLY INT)
      implemented: slot (Fraction (UnivariatePolynomial x (Polynomial
(Integer))
))(Mapping (UnivariatePolynomial x (Polynomial (Integer))) (Polynomial
(Integer)
))(Fraction (Polynomial (Integer))) from FRAC2(POLY INT,UP(x,POLY INT))

   Loading C:/Program Files/axiom/mnt/windows/algebra/FRAC2.o for
      package FractionFunctions2
   Loading C:/Program Files/axiom/mnt/windows/algebra/QFCAT2.o for
      package QuotientFieldCategoryFunctions2
   Loading C:/Program Files/axiom/mnt/windows/algebra/PGCD.o for
      package PolynomialGcdPackage

   (2)  1
   Type: Fraction UnivariatePolynomial(x,Polynomial Integer)

-----------

William Sit continued:

> This is unfortunately a consequence of the design goal to
> permit elements of UP(x,R) to be coercible to POLY R where
> the main variable is coerced into the variable using the
> identifier x. ...

I don't think that this is the case since we can obtain the
same result above using:

  (1/x)$MPOLY([x],FRAC POLY INT)*x
  %::FRAC MPOLY([x],POLY INT)

> Here R IS FRAC POLY INT, and UP(x, FRAC POLY INT) is first
> coerced into FRAC UP(x, POLY INT) and then further to
> FRAC POLY INT via UP(x, POLY INT) to POLY INT (from map
> from FRAC2(UP(x, POLY INT),POLY INT)

Apparently on the first coercion is sufficient. Moving the
fraction from the coefficient domain to become a fraction
of polynomials:

  UP(x, FRAC POLY INT) +-> FRAC UP(x, POLY INT)

provides a domain in which the two uses of x can cancel.

In fact we can see this same coercion in operation in the
case of going from:

  POLY FRAC INT +-> FRAC POLY INT

(1) -> (1/2*x)$UP(x, FRAC INT)

        1
   (1)  - x
        2
   Type: UnivariatePolynomial(x,Fraction Integer)

(2) -> )set message bottom on
(2) -> %::FRAC UP(x,INT)

 Function Selection for map by coercion facility (map)
      Arguments: ((INT -> UP(x,INT)),FRAC INT)
      Target type: FRAC UP(x,INT)
   -> no appropriate map found in Fraction Integer
   -> no appropriate map found in
        Fraction UnivariatePolynomial(x,Integer)
   -> no appropriate map found in
        UnivariatePolynomial(x,Integer)
   -> no appropriate map found in Integer
   -> no appropriate map found in
        UnivariatePolynomial(x,Integer)

 Modemaps from Associated Packages
   [1] ((D7 -> D11),FractionalIdeal(D7,D8,D9,D10)) ->
                    FractionalIdeal(D11,D1,D2,D3)
            from FractionalIdealFunctions2(D7,D8,D9,D10,D11,D1,D2,D3)
            if D7 has EUCDOM and D8 has QFCAT D7 and D9 has UPOLYC D8
            and D10 has Join(FramedAlgebra(D8,D9),RetractableTo D8) and
            D11 has EUCDOM and D1 has QFCAT D11 and D2 has UPOLYC D1
            and D3 has Join(FramedAlgebra(D1,D2),RetractableTo D1)
   [2] ((D4 -> D5),Fraction D4) -> Fraction D5 from
        FractionFunctions2(D4,D5)
            if D4 has INTDOM and D5 has INTDOM

 [1]  signature:   ((INT -> UP(x,INT)),FRAC INT) -> FRAC UP(x,INT)
      implemented: slot (Fraction (UnivariatePolynomial x
(Integer)))(Mapping (U
nivariatePolynomial x (Integer)) (Integer))(Fraction (Integer)) from
FRAC2(INT,U
P(x,INT))

   Loading C:/Program Files/axiom/mnt/windows/algebra/FRAC2.o for
      package FractionFunctions2
   Loading C:/Program Files/axiom/mnt/windows/algebra/QFCAT2.o for
      package QuotientFieldCategoryFunctions2
   Loading C:/Program Files/axiom/mnt/windows/algebra/HEUGCD.o for
      package HeuGcd
   Loading C:/Program Files/axiom/mnt/windows/algebra/INMODGCD.o for
      package InnerModularGcd
   Loading C:/Program Files/axiom/mnt/windows/algebra/EMR.o for domain
      EuclideanModularRing
   Loading C:/Program Files/axiom/mnt/windows/algebra/MDDFACT.o for
      package ModularDistinctDegreeFactorizer
   Loading C:/Program Files/axiom/mnt/windows/algebra/MODRING.o for
      domain ModularRing

        x
   (2)  -
        2
   Type: Fraction UnivariatePolynomial(x,Integer)

> and the Interpreter probably simplified POLY POLY INT to
> POLY INT). In other words, we have ((1/x ?)::(?/x)::(x/x)=1.
> The bug therefore probably lies in the identification of
> POLY POLY INT with POLY INT where the outer ? (or x) is
> identified with x of the inner POLY.

I don't see this happening anywhere above. On the contrary this
calculation seems to me to demonstrate the extraordinary power
of the generic algorithms that are part of the Axiom library.

> Conclusion: (i) Any simplification of towers which makes
> sense in mathematics probably would not make sense in
> computer algebra (due to scope problems for one). Other
> examples could be FRAC FRAC INT to FRAC INT and EXPR EXPR
> INT to EXPR INT.

I don't understand this comment. What do you mean by
"scope problems"?

> (ii) Users should be alert to the order in which an input is
> scanned and the consequences, and break a long input into
> simpler steps.

I agree that simple steps are easier to analyze. I also
think it is a mistake to write something like:

  (x+1)::POLY INT

or

  x+1::POLY INT

when

  (x+1)$POLY INT

will do. In the first two cases the interpreter will do
some extra computation by default before it applies the
coercion operation and the result of coercion is harder
to analyze than the simple package call.

> (iii) Users should not use the same identifier for two
> different objects.

I think that this is simply not possible in Axiom.

Regards,
Bill Page.