[Axiom-developer] [#270 integrating UTS] 1/x x = 1 is a feature(?)

[wyscc]

Changes http://wiki.axiom-developer.org/270IntegratingUTS/diff
--
> 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.

I have examined this simplification more closely. As discussed in another 
email, this is actually done by invoking a   substitution map: briefly, the x 
in ULS is being substituted by the x in FRAC POLY INT. I think this is 
unwarranted "smartness" by the Interpreter (this is a "lesser crime" than a 
"bug"). Of course, as Tim said above, this is   secondary error due to an error 
by the user. It would be a legitimate substitution if a user initiated it. I 
believe     the automatic substitution would not be done in the compiler (that 
is, the coercion would be flagged).

The Axiom compiler, as far as I can tell, scoped the two x's correctly. It is 
the automatic substitution by the Interpreter due to a request to coerce that 
yields the answer 1. Whether you call this a feature or a bug is up to you. 
Users beware.

William

>From email referred to above: (edited for Wiki) ::

  Date: Fri, 24 Feb 2006 07:14:24 -0500
  From: William Sit <address@hidden>
  To: address@hidden


Bill::

  > 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.

There never is anything simple in Axiom. By its nature every function is
parametrized and categorical. Clearly, this issue will recur as new users
stumbles onto these constructions.

As you know, a polynomial ring $R$ over a ring $S$ in the indeterminates 
$x$<sub>1</sub>, ...,
$x$<sub>n</sub>, means that $x$<sub>1</sub>, ..., $x$<sub>n</sub> are 
algebraically independent over $S$; in particular,
they are *not* elements of $S$. If you really want $\frac{1}{x}x$ to mean 1, 
the two $x$'s must
live in the same domain. Either you put $\frac{1}{x}$ in the coefficient domain 
$S$ and then
err on using the same identifier for a transcendental over $S$, or you should
simply use the $x$ from $S$ in forming $\frac{1}{x}x$ in the quotient field of 
$S$ (assuming $S$ is an integral domain).

When you write 'UP(x, FRAC POLY INT)', you specifically told Axiom that 'x' 
(more
precisely, the indeterminate ? with an identifier 'x') is transcendental over 
'FRAC
POLY INT'. So you should *not* use 'x' in 'FRAC POLY INT'. The fact that Axiom 
cannot
disallow you to do that is not a license to violate this mathematical
definition! In any computer language, there are always unforseen constructions
that a compiler cannot diagnose and sometimes, such *abuse* may be used for
tricky programming, but they are *abuse* nonetheless. For old FORTRAN
programmers, this is similar to core to core I/O where you can turn an integer
into a real with the same binary representation. FORTRAN allows this, but you
can't possibly say mathematically the two are the same! When a programmer
deliberately violates the rules of construction that cannot be caught by the
compiler, it is a bug of the compiler.

However, no matter how buggy a computer algebra system is, we are using it to do
**mathematics** and so *no* mathematical rules should be violated in the 
computations.

As to your quibble to my separating "identifier", let me emphasize:
identifiers are external strings what a user in the interpreter use to refer
to objects that are internal to Axiom. 'Symbol' and 'Variable' are domains in 
Axiom
and their objects are internal. The fact that we use the same identifier string
as the representation string for a 'Symbol' object is only a convenience. As you
pointed out, a 'Symbol' object need *not* be a simple string and can be adorned 
with
all sorts of scripts. You would not want to keep inputting a symbol adorned in a
complicated way in its full detail (note the linear form to enter such a symbol
is a function, not the representation). So if I say

\begin{axiom}
)set mess bot on
y:=x[1,2,3,4]
\end{axiom}

then::

   y is the identifier I use (y is NOT the symbol),
   x[1,2,3,4] the linear function with signature
      elt: (VARIABLE x, LIST PI)->SYMBOL, and
   the symbol is x with [1,2,3,4] as subscript
   x itself is a Symbol and is different (as far as Axiom goes) from
   the x in the domain Variable(x)

Just to emphasize the fine distinctions, the output you see, is an element of
'OUTPUTFORM'! (another string representing some internal object of the domain
'Symbol').

Bill Page wrote::

  > 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)

I am trying to explain the coercion using 'UP(x,R)' as a generic representative.
Sure, you can violate the rule of construction using any of the polynomial
domains in Axiom. The short answer is, any indeterminate you use in the
construction of a polynomial domain is transcendental over the coefficient
domain and should NOT be coercible to the coefficient domain! I am saying, the
above design goal is flawed in illegal constructions like these, but makes sense
in the legal construction::

  coerce: UP(x,R) -> POLY R

when 'R' does not contain 'x' (and it shouldn't contain 'x', and if it does, 
wrongly,
in concept, then 'x' should not be instantiated there). 
<pre>
  > > 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.
</pre>
You are missing the point.

I don't care how the Interpreter performs the illegal coercion (except that I
was trying to explain the design goal that leads to the illegal coercion). The
coercion is simply WRONG. Period. It is an error built on a user error. (Don't
we know that compilers are famous for that when reporting error messages?) In
such cases, a user is supposed to remove the original error, not argue about the
validity or invalidity of subsequent errors. 
<pre>
  > 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)
  [additonal output snipped]
</pre>
These are legal coercions since mathematically, 'POLY FRAC INT' is a subring of
'FRAC POLY INT' and similarly, 'UP(x, FRAC INT)' is a subring of 'FRAC UP(x, 
INT)'.
The design goal I mentioned above is *not* involved. If you had taken 'x/2' in 
'FRAC
POLY INT' or in 'POLY FRAC INT' and coerce this to 'UP(x, FRAC INT)', then the 
design
goal is applied and the Interpreter (not the compiler) will oblige by
identifying the
the variable 'x' of 'POLY FRAC INT' with the main variable ? of 'UP(x, FRAC 
INT)'
because the user used the identifier 'x' for ?.  This feat is accomplished only
with the help of 'UP2(x,POLY FRAC INT,x,FRAC INT)', which explicitly maps the 
'x' in
'POLY FRAC INT' to the 'x' (or ?) of 'UP(x, FRAC INT)'. It is equivalent to a
*substitution* map. There is *no* general coercion from 'POLY FRAC INT' to 
'UP(x, FRAC
INT)'. 
<pre>
  > > 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"?
</pre>
When one constructs 'POLY POLY INT', one tells Axiom to use 'Symbol' as the 
variable
set over 'POLY INT'. Thus the 'Symbol' in the outer construction should be in a
different lexicon scope so that this *copy* of 'Symbol' can be a family of
algebraically independent elements over 'POLY INT'.  I don't want to go into the
details of how domains are constructed (I probably don't know anyway), but *if* 
we
modify whatever will be used as symbols in 'POLY INT' by attaching a context
prefix, say 'POLYINT-x' for what we normally use 'x', then we can distinguish
another symbol 'x' in this *copy* for the external 'POLY' construction by using
'POLYPOLYINT-x'. Apparently, the Interpreter allows a *substitution* of
'POLYPOLYINT-x' by 'POLYINT-x', giving the user the *impression* that the two 
are
identified, and this is the flaw I was discussing. The Interpreter should not do
that with coercion. A substitution should be *explicitly* requested by the 
user. A
coercion should not involve a hidden substitution.

Let me repeat this mathematically. Let $R$ be a ring, $S$ a set and $$X =
\{x_s\}_{s \in S}$$ be a family of algebraic indeterminates over $R$. Then we 
can
construct the polynomial ring $R[X]$. If we like, we can let $$Y = \{y_s\}_{s 
\in S}$$
be another family of algebraic indeterminates over $R[X]$ and construct
$R[X][Y]$.  We can make substitution maps $y_s \mapsto x_s$, but we should NEVER
identify $y_s$ with $x_s$ and say $R[X][Y] = R[X]$ simply because $X$ and $Y$
are indexed by the same set $S$.
No one would argue that $x_s + y_s = 2x_s$ is correct, or the derivative of 
$x_s + y_s$ with respect to $x_s$ is 2 and not 1.

You can substitute $R$ by 'Integer' and $S$ by 'Symbol'. The problem with the 
computer
algebra case is that 'Symbol' is like the set of *all* symbols **in concept**, 
and *a
priori* prevents construction of any other symbol outside 'Symbol'. This is a 
very
bad restriction. We want to be able to talk about unknowns over 'EXPR INT', say 
in
differential equations. In reality, only finitely many symbols are instantiated
and hence we can solve the problem using context-prefix (scope separation). So
while this all encompassing concept may be convenient, it should be taken with a
grain of salt. Mathematica for example uses context-prefixes in their packages.

The construction of 'FRAC FRAC INT' is similar, except that in this case, there 
is
no argument that if $R$ is an integral domain, and $Q(R)$ its quotient field, 
then
$Q(Q(R))$ is isomorphic to $Q(R)$. But it is precisely that the *sets* 
$Q(Q(R))$ and
$Q(R)$ are *not* the same set, but just isomorphic (even canonically), that 
requires
the implelmentation of the isomorphism in computer algebra. One simply cannot
"identify" the two sets in computer algebra because they do have different data
representations. In order to implement the isomorphism, one must be able to
distinguish when $x \in R$ is regarded as $x/1 \in Q(R)$ or 
$(x/1)/(1/1) \in Q(Q(R))$. One way would be to use context-prefix. To the naive 
users, this seems
really much ado about nothing: Axiom relies on users not to construct (or
explicitly disallows in the Interpreter) such towers.  However, this is only ok
up to a point. When one can write routines that return domains, this naive
design forces a case by case examination of the returned domains to screen out
"trivial" (I would prefer the adjective "boundary") cases (for example, if I
want to construct 'FRAC R' where 'R' is a run-time computed domain, then I need 
to
use something like 'if R has FIELD then R' in 'FRAC R' construction).
Unfortunately, the pedantic (isomorphism) way is very inefficient so a
compromise was taken.

A big big question in computer algebra should be how to handle "canonically
isomorphic" mathematical objects. Mathematicians assume these identifications
without a thought in most cases, but there are occasions where distinction is
important. For example, they would rarely identify two vastly differently
defined finite sets just because they have the same cardinality.
<pre>
  > > (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.

Agreed.
<pre>
  >  (iii) Users should not use the same identifier for two
  > > different objects.
  >
  > I think that this is simply not possible in Axiom.
</pre>
I am not talking about spad code, where there are multiple scopes. In the
interpreter, unless you use a different frame, all *identifiers* the user uses 
are
in one scope. If you use 'x' for 'UP(x, POLY INT)', then you should not use 'x' 
in
'POLY INT'. May be you can give me an example where you MUST use (or at least it
is desirable to use) the same identifier for two different objects in an
Interpreter session?

William

<hr>

The following is verbatim quote from Email by Bill Page:
<pre>
-------- Original Message --------
Subject: Re: 1/x x = 1 is a bug!
Date: Fri, 24 Feb 2006 00:58:19 -0500
From: "Page, Bill" <address@hidden>
Reply-To: <address@hidden>
To: "William Sit" <address@hidden>
CC: <address@hidden>, <address@hidden>,"Martin Rubey" <address@hidden>,"Ralf 
Hemmecke" <address@hidden>, <address@hidden>

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.
</pre>


--
forwarded from http://wiki.axiom-developer.org/address@hidden