Re: [Axiom-developer] about Expression Integer (with Quizzes)

[William Sit]

"Page, Bill" wrote:
> 
> William
> 
> On Friday, February 24, 2006 8:07 AM you wrote:
> >
> > Any scientific literate person, when (s)he wrote down:
> >
> >    2*x + 1/x
> >
> > would mean that there is only ONE x, the x means the same
> > thing throughout the expression.
> 
> Yes.

I'm glad you agreed. So how can you keep arguing that one x lives in one domain,
and the other x in another?

> > So
> >
> > (1) -> (2*x+1/x)::DMP([x], EXPR INT)
> >
> >           2
> >         2x  + 1
> >    (1)  -------
> >            x
> >               Type:
> > DistributedMultivariatePolynomial([x],Expression Integer)
> > (2) -> degree(%)
> >
> >    (6)  [0]
> >
> > is perfectly correctly interpreted by Axiom. The entire
> > expression is a coefficient, in EXPR INT.
> 
> It is a correct interpretation, but it is not the only
> possible interpretation. The reason it is interpreted as
> entirely with 'EXPR INT' is because you used a conversion
> '::' instead of a package call $. Axiom processes what is
> inside the parenthesis first. Since there is no package
> specification there, the interpreter assumes we are talking
> about 'EXPR INT'. Then it applies the coercion from 'EXPR INT'
> to 'DMP([x], EXPR INT)' which simply embeds the expression
> as a term of degree 0.

I kind of agree with your explanation when using a package call (though the
expression goes through FRAC POLY INT before reaching EXPR INT). But
unfortunately, package call is no guarantee and the above is incomplete
explanation (Hint: do the quizzes at bottom).

Aside: Hyperdoc reports that DMP([x], EXPR INT) is an invalid type. (Type the
domain in the search box, click Constructors, then click operations). Yet
another inconsistency in the system.
 
> Try this instead:
> 
> (1) -> (2*x+1/x)$DMP([x], EXPR INT)
> 
>              1
>    (1)  2x + -
>              x
>    Type: DistributedMultivariatePolynomial([x],Expression Integer)
> 
> (2) -> monomials(%% 1)
> 
>             1
>    (2)  [2x,-]
>             x
>    Type: List DistributedMultivariatePolynomial([x],Expression Integer)
> 
> In this case we told Axiom to use only operations from the
> domain 'DMP([x], EXPR INT)'. It sees '2*x' and selects the
> '*' with signature '?*? : (Integer,%) -> %'. The result is
> a term of degree 1. Then it looks at '1/x' and selects
> '?/? : (%,Expression Integer) -> %'. The result is a term
> of degree 0.
> 
> This also is correctly interpreted by Axiom. But these two
> expressions are not equivalent in this domain.

No, Axiom erred in performing a "coercion" from DMP([x], R) into R when
mathematically, it is clear that x does not belong to R. It should only coerce
from DMP([x],R) into POLY R or EXPR R.  You already agreed that the x should
mean the same mathematical object in the expression. Now look at this (I used UP
instead of DMP, but DMP would show almost the same except b would be in List
OVAR [x], and (7) would return 'false' (this is better, but in both the UP and
DMP cases, (6) and (7) should end in error. More of this later.)

(1) -> a:= (2*x+1/x)$UP(x, EXPR INT)

             1
   (1)  2x + -
             x
                             Type: UnivariatePolynomial(x,Expression Integer)
(2) -> b:=variables a

   (2)  ["?"]
                                             Type: List SingletonAsOrderedSet

   
(3) -> c:=coefficient(a, b, [0])


        1
   (3)  -
        x
                             Type: UnivariatePolynomial(x,Expression Integer)

(4) -> d:=retract(c)@(EXPR INT)


         1
   (4)   -
         x
                                                     Type: Expression Integer
(5) -> e:=variables d


   (5)  [x]
                                                            Type: List Symbol

So the two instances of 'x' are not treated as the same mathematical object or
even the same computer object or variable.  Indeed, in Axiom, they live in two
different domains! So Axiom did not interpret the two x's consistently.

Warning, do not let

(6) -> t:Boolean:=(b.1=e.1)
   (6)  true
                                                                Type: Boolean

deceive you into thinking the two variables are the same. The Interpreter
actually tried very hard to please you (too bad, it shouldn't, and should have
complained that there is no = function that is applicable; we are testing
equality, and the Interpreter should not perform ANY coercion in equality tests
because then equality test in the Interpreter are no longer predictable without
a deep understanding of how the Interpreter works). Just )set mess bot on before
(6) to see (its too long to reproduce here). Moreover, this may or may not
surprise you:

(7) -> s:Boolean:=(b.1=(y::Symbol))


   (7)  true
                                                                Type: Boolean

This is not a surprise at all. You see, b.1 is simply a place holder ? and it
can match ANY symbol. The type of b indicates NOTHING about x. The Interpreter
went through the same set of coercions as for (6) to say, "Ah-ha, I found a
common domain where they can be equal. I don't care what the user meant!" (BTW,
the domain is UP(y, INT)).  As mentioned, the case for DMP is better handled, in
which case the type of b, List OVAR [x], does indicate x. Would you have guessed
from what common domain is the equality test function taken?

> >
> > However, I think Axiom is wrong in allowing that, since x,
> > being an indeterminate over EXPR INT, should not be in
> > EXPR INT.
> 
> I suppose what you are saying is that the ring over which
> DMP is defined should not be 'EXPR INT' but rather
> 'SubDomain(EXPR INT, not member?(x::Symbol,variables(#1))'.

No, that is not the same. The above still accepts that the two x are the same
and this is mathematically incorrect. You can have a different x in EXPR INT,
and you can substitute DMP-x for EXPR-x, but they are different. DMP-x is
transcendental over EXPR INT whereas EXPR-x is in the field.

> This is a possible definition but it seems unnecessarily
> complicated. Further it would explicitly prevent the kind
> of coercion that Axiom was apparently carefully designed
> to do (see below).

Quite the contrary. There ARE legitimate use of these construction and they ARE
used in the Axiom library. Just to give you an example, SUP in idecomp.spad

IdealDecompositionPackage(vl,nv) : C == T -- take away nv, now doesn't
                                          -- compile if it isn't there
 where
   vl      :  List Symbol
   nv      :  NonNegativeInteger
   Z      ==>  Integer  -- substitute with PFE cat
   Q      ==>  Fraction Z
   F      ==>  Fraction P
   P      ==>  Polynomial Z
   UP     ==>  SparseUnivariatePolynomial P
   Expon  ==>  DirectProduct(nv,NNI)
   OV     ==>  OrderedVariableList(vl)
   SE     ==>  Symbol
   SUP    ==>  SparseUnivariatePolynomial(DPoly)

   DPoly1 ==>  DistributedMultivariatePolynomial(vl,Q)
   DPoly  ==>  DistributedMultivariatePolynomial(vl,F)

Axiom actually allows other ways to add new indeterminates to a domain that
already uses Symbol as the set of indeterminates, by using a direct product of
say
NNI to the existing EXPON, for example (see definition of POLYCAT and
gbintern.spad for such use). These towers are needed and as far as I can tell,
the Axiom compiler handles them perfectly. Any confusion is caused by "features"
in the Interpreter. The Interpreter is, unfortunately, a main reason why the
learning curve for Axiom is so steep.

I don't think to understand that indeterminates are transcendentals is too
complicated, or an x in one expression must mean the same mathematical object
throughout. These are the only two principles I used.

> There is no danger that Axiom will confuse the two uses of
> 'x' and to the user this result looks perfectly reasonable -
> it looks like just a different way of formatting the
> expression - but of course as "advanced users" we know the
> difference is more subtle than that.

Axiom does confuse the users by performing a substitution for one x and not the
other, thus splitting one x into two. If you goal is to reformat the expression,
then reformat it entirely within EXPR INT (that is, create a "reformat" command
that does that by walking a parse tree for the expression, or create extraction
functions similar to univariatePolynomial in UPS that extracts only monomial
terms from a sum of terms).
 
> >The coercion should simply fail, or end up in
> > FRAC DMP([x], EXPR INT).
> 
> I do not see how it could possibly end of in
> 'FRAC DMP([x], EXPR INT)' in either version of (1) above.

If x is to be the variable in DMP, then 1/x needs to be in FRAC DMP. x is a
transcendental over EXPR INT and should not and cannot be interpreted as ALSO in
EXPR INT. The design to allow Symbol as the set of variables in POLY or EXPR is
ingenious in concept and gives Axiom its power to program categorically without
hardcoding any predefined finite set of symbols. Users should not equate this to
mean no other indeterminates can be constructed over POLY INT or EXPR INT. In
fact, EXPR was constructed over as the quotient field of a polynomial ring where
indeterminates are kernels.

> > Note that even if the following is used, Axiom continues to
> > "retract" the x from 1/x to EXPR INT. This is simply wrong.
> >
> > x:DMP([x], EXPR INT):=x
> > 2*x + 1/x
> > degree(%)
> >           [1]
> >
> 
> It is not wrong. 

No, you are wrong. The Interpreter performs a mathematically unwarranted
coercion (via a substitution). If the Interpreter is allowed to reinterpret an
identifier that I explicitly declared and defined, and coerce an element into a
ring that the element should not belong to in the mathematical sense, how can I
predict what subsequent computations will be? If a user does not declare the
type, yes, the Interpreter would be given the freedom to coerce; otherwise, it
should coerce only with specific directives from the user, or when it is
mathematically correct to do so.

> I agree that it might be unexpected if
> one does not keep in mind the domains from which Axiom will
> select functions. One might (incorrectly) thought that the
> 1/x must be evaluated in 'FRAC DMP([x],EXPR INT)' 

Expecting that 1/x must be evaluated in FRAC DMP is the ONLY mathematically
reasonable expectation when x is the indeterminate in DMP and therefore NOT a
member of its coefficient domain.

> but once
> again Axiom first considers the '/' function defined in
> domain that it already knows: 'DMP([x],EXPR INT)' before it
> attempts anything more complex. 

The error is not in using '/' from DMP but in making an unwarranted and wrong
*substitution*. Indeed, the sequence to parse the expression 2*x + 1/x, as you
noted, is (skipping some obvious ones):

   2*x is in DMP
   1, don't know yet
   x, is in DMP
   / is a function to be looked up
   Ok, I can coerce 1 to be in DMP as its unit
   Ooops, I can't find a / in DMP with signature (%,%)->%
   But there is a / in DMP([x], EXPR INT) with signature (%, EXPR INT)->EXPR
INT     (because EXPR INT has FIELD)
   Ah ha, I'll coerce the denominator into EXPR INT -- wrong step!

As explained in my previous email, this coercion is a *substitution* and is
wrong because there should not be a *coercion* from DMP([x], EXPR INT) to EXPR
INT; there is only a *retractIfCan*.  I repeat: 'x' is transcendental over EXPR
INT and should not and cannot be in EXPR INT. This total disregard of what x is,
is a bug, and demonstrates inconsistency in the Interpreter. In the above setup,
(1/x)*x is not 1 so the denominator x is coerced to EXPR INT, but the other x is
not.  This can cause other problems:

\begin{axiom}
)clear all
y:=DMP([x], EXPR INT):=x
z:=1/y
w:=1/z
t:Boolean:=w=y
\end{axiom}

If you consider this is not a bug, I  don't know what is. Of course, I know how
this came about. If z had been computed in FRAC DMP([x], EXPR INT), as it
should, this problem would not be there.


  
> It discovers that it can
> evaluate 1 in 'DMP([x],EXPR INT)' and that since 'x' is a
> variable of type 'DMP([x],EXPR INT)', it knows that it can
> always coerce such polynomials into 'EXPR INT'. This allows
> it to apply the operator '/' from 'DMP([x],EXPR INT)'.

This is not the whole story as indicated above. The 'x' is a polynomial, but in
this case, it is mathematically incorrect to "coerce" it into the coefficient
domain, even if it happens to be EXPR INT. Moreover, selective substitution is
another evil here (substituting one x and not the other).


> > On the other hand, the following is correct, and should
> > be the case no matter what the coefficient domain is.
> >
> > y:DMP([y], INT):=y
> > 2*y+1/y
> >
> >            2
> >          2y  + 1
> >          -------
> >             y
> >                 Type: Fraction
> > DistributedMultivariatePolynomial([y],Integer)
> >
> > The two cases should not be handled differently.
> 
> I agree that this result is correct but I disagree that
> these two cases can be handled the same way (i.e. by
> selecting the '/' operation in 'DMP([y], INT)'. This is
> not possible because Axiom cannot coerce polynomials of
> type 'DMP([y], INT)' into 'INT'.

Neither should Axiom coerce polynomials of type DMP([y], R) into R for ANY R.

Bill, Axiom is to model mathematics, *categorically*.
It is allowed that a different algorithm is used by tapping into the properties
of the coefficient domain, IF THEY PRODUCE THE SAME RESULT (consistency). The
alternative algorithm should not be allowed when it produces a different answer.
Mathematically, if y is an element of an integral domain, then 1/y is its
reciprocal in the quotient field and 1/(1/y) has to be y itself. The Axiom
interpreter (not Axiom) fails in these examples to uphold a mathematical result.
That is WRONG (even though it originates from user input error: expecting 1/x to
be in DMP([x], EXPR INT) where x is not in EXPR INT).



> > If a user wants to push the result down to the coefficient
> > domain, it should be done with a substitution map,
> > explicitly, and the user should not use x in EXPR INT.
> >
> 
> This sort of coercion is only possible when the coefficient
> domain has 'PDRING Symbol' or at least 'PDRING OVAR vl'
> where 'vl' is polynomial variable list. Apparently Axiom
> attempts to use it during the function selection process.

The Interpreter is designed to coerce polynomials over a ground ring R into EXPR
over the SAME ground ring, and it is an oversight that it actually coerce
polynomials over a ring R into R itself when R is EXPR INT. Had the Interpreter
coerced 1/x into EXPR EXPR INT, in the example where x is in DMP([x], EXPR INT),
that would be correct. But the Interpreter, unfortunately, does not allow EXPR
EXPR INT.

I failed to see why PDRING has anything to do with it. All you are saying is
that if the coefficient domain does NOT have PDRING Symbol, etc, then the
Interpreter will not produce the incorrect coercion, but it does -- see Quizzes.
It should not matter whether the coefficient domain has millions of other
properties or not. The Interpreter should not perform a *partial substitution*
behind my back and call it *coercion*, and worse, by doing so it produces
inconsistent results on a categorical level and is mathematically wrong.

By the way, I don't think it is easy to fix this bug because it involves how
deeply the Interpreter should try to coerce. My suggestion to users is: ignore
these examples, don't use towers involving polynomial rings, and if you really
need these tower constructions, don't do this in the Interpreter since you won't
know what the consequence will be without wasting a lot of time (and we might
still get it wrong).

Here are some quizzes if you have read so far (it does not matter if you agree
with me or not). 

Instructions: What is the output for each of the following?
Do the problems only one at a time. You should write down your answer, its type,
and with explanations and any expected error messages. Then check it (using )set
mess bot off), revise your explanation if necessary, or explain Axiom's output.
Finally, use )set mess bot on to see exactly what the Interpreter did. Then and
only then, advance to the next problem.

Just in case: the function 'variables' returns a list of the variables occurring
in the argument.

)set mess bot off  -- no cheating
(1) variables (2*x+1/x)$DMP([x], EXPR INT)

(Got you, right? It got me too. To understand this, repeat with )set mess bot
on. You must understand what the Interpreter was doing before starting quiz (2))

)set mess bot off
(2) variables (2*y+1/y)$DMP([y], INT)

(Got me again! Repeat with )set mess bot on, read carefully, and compare with
that from (1)). 

)set mess bot off
(3) a:=(2*x + 1/x)$DMP([x], EXPR INT); 
    variables a 

)set mess bot off
(4) b:=(2*y+1/y)$DMP([y], INT);
    variables b

)set mess bot off
(5) x:DMP([x], EXPR INT); 
    variables (2*x+1/x)

)set mess bot off
(6) y:DMP([y], INT);
    variables (2*y+1/y)

For your convenience, the quizzes have been set up at SandBox Polynomials.
Solutions are at SandBoxPolynomialQuiz and you can enter your insights at
SandBoxPolynomialQuizExplained.

Have fun. If you got all 6 perfectly, you are a "guru", congratulations, and let
us know (so we know whom to ask questions next time :-) (Actually, I do have a
few related to these quizzes, but rather than scratching my head again, I'll
wait for the "guru"s to tell me.)

William