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

[William Sit]

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 x1, ...,
xn, means that x1, ..., xn are algebraically independent over S; in particular,
they are NOT elements of S. If you really want 1/x x to mean 1, the two x must
live in the same domain. Either you put 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 1/x x in FRAC S (assuming S has INTDOM).

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' none the less. 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:

(1) -> y:=x[1,2,3,4]

 Function Selection for x
      Arguments: LIST PI
   -> no function x found for arguments LIST PI

 Function Selection for elt
      Arguments: (VARIABLE x,LIST PI)

 [1]  signature:   (SYMBOL,LIST OUTFORM) -> SYMBOL
      implemented: slot $$(List (OutputForm)) from SYMBOL


 Function Selection for elt
      Arguments: (VARIABLE x,LIST PI)

 [1]  signature:   (SYMBOL,LIST OUTFORM) -> SYMBOL
      implemented: slot $$(List (OutputForm)) from SYMBOL


 Function Selection for map by coercion facility (map)
      Arguments: ((PI -> OUTFORM),LIST PI)
      Target type: LIST OUTFORM

 [1]  signature:   ((PI -> OUTFORM),LIST PI) -> LIST OUTFORM
      implemented: slot (List (OutputForm))(Mapping (OutputForm) (PositiveIntege
r))(List (PositiveInteger)) from LIST2(PI,OUTFORM)


   (1)  x
         1,2,3,4
                                                                 Type: Symbol

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

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

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

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

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

> > 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"?

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.

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

>  (iii) Users should not use the same identifier for two
> > different objects.
> 
> I think that this is simply not possible in Axiom.
> 
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