[Axiom-developer] Re: Mixing up variables: (was Re: conditionally defined functions)

[William Sit]

Martin Rubey wrote:
 
>  > Axiom cannot possibly rule out such user behavior because each operation
>  > (x::UP(x,?), x::EXPR INT, and /) is correctly performed. To do so would
>  > require Axiom to "look ahead" when processing x::UP(x,?). This is
>  > unreasonable as well as impossible -- how far ahead? what if the x::EXPR 
> INT
>  > is something returned by another routine?
> 
> I don't understand: it can! Well, I mean: it could. One possibility is the
> following: every domain that has (named) variables should have a function 
> vars:
> R -> List Symbol and isvar?: Symbol -> Boolean. (I think the latter is not
> strictly necessary: it should return true if the Symbol could be a variable in
> the domain) Then coercions could be done as I suggested:
> 
> if any?(isvar?, vars(thing))
> 
> then thing cannnot be regarded as a coefficient.

But the two functions vars and isvar? are kind of available, perhaps not named
that way, but surely there are functions similar that serve the same purpose, if
all you want is to test whether a domain has "variables." For example, monomial,
degree, freeOf? You may have to do a more complicated test, but you can test
these right now. But I still do not see how the above test can rule out a
construction like EXPR EXPR INT. It's a catch-22 situation. I don't see any
action can be taken at compile time of the EXPR constructor other than put in
the code for the if-statement to run at instantiation (run) time. If EXPR EXPR
INT is encountered by the compiler, an outer version of the if-statment will be
compiled.  So say your test returns false, assuming this test is executed at run
time when EXPR EXPR INT is instantiated, what is the then-clause? Can you first
instantiate the domain and then uninstantiate it? I think a simple error message
after this outer if-statement fails at instantiation time is not sufficient to
undo the instantiation; halting on error is not as good as catching this
construction at compile time. This would mean putting the rules for construction
into the grammar for the parser -- but the grammar does not know anything about
EXPR (or any specific constructor for that matter)!

> 
> I do admit that to integrate SUP into this picture might be tricky.
> 
It sure would be. Even for the others, you have to make sure preventing
"illegal" towers will not break any code. "There is no such thing as a simple
job."

>  > I see no reason to allow POLY EXPR INT or similar constructs **as Axiom now
>  > stands.** Unfortunately, the general and categoric constructs in Axiom make
>  > it difficult to "exclude" specific domains (POLY(R) is valid for any ring 
> R;
>  > the user is allowed to construct POLY(R) for whatever R, even if R is
>  > POLY(S). In fact, I don't know of any Axiom mechanism to exclude specific
>  > domains in a constructor's parameters. (Axiom allows declaring domains to
>  > HAVE certain attributes, but I believe does not allow them to NOT HAVE
>  > certain attributes).
> 
> As it now stands, the way to do things is simple: don't use towers of domains
> with variables. (One exeption is polynomials with coefficients that are
> expressions not containing variables: we have to use POLY EXPR INT here...)

That's a good example we have to be careful if we prohibit certain towers. But
that is not the only example.

>  > Below, I'll try to analyse where the present problem lies and propose a way
>  > to correct the problem. Even if you agree with my analysis, whether the
>  > correction should be implemented or not is still subject to discussion.
> 
> Do I understand correctly: You propose (roughly) that variables should carry a
> tag that tells which domain they belong to. 

Yes. However, the tag is tied to the coefficient domain (which may have old
variables of its own), not the domain with (the new) variables. This corresponds
better to the mathematical notion of the "variables" ("algebraic indeterminates"
is the precise term) being algebraically independent over the coefficient
domain.
 
>  > Let me say that there is perhaps a role for constructs like POLY POLY INT 
> or
>  > POLY EXPR INT.  Examples: computing syzygies of polynomials generating an
>  > ideal, or more generally the defining set of algebraic polynomial
>  > (equations) for algebraic functions -- a (non-linear) system of 
> differential
>  > equations is simply algebraic equations for functions and their
>  > derivatives.
> 
> Could you give an example here? I do not understand.

Let's say I am hunting for two polynomials f(x), g(x) and I know they satisfy
some algebraic relations with coefficents that are polynomials. The polynomials
expressing these algebraic relations would then be in POLY POLY INT, such as 

h = a(x) y^3 + b(x) z^2 - c(x) 

where a, b, c are in POLY INT, and y, z when substituted by f, g would give
zero. Mathematically, it would be natural to view h as in POLY POLY INT. Of
course, we know it would be better to use specified variables and work in
DMP([y,z], DMP(x, INT)), but we are talking about "lazy" users. Now, we CAN
carry out these computations in POLY INT alone, but the more natural setting is
POLY POLY INT (for example, we may want to compute the grobner basis of the h's
in POLY POLY INT with POLY INT as coefficient domain. Relations like  h(f,g) = 0
are called a syzygies of (f,g) and are important computational objects in
algebraic geometry. If g(x) = df/dx, then h(f,g)=0 is a differential equation on
f(x).

> 
>  > Unfortunately, the current convention is not "outer domain takes all the
>  > variables."
> 
> Hmmm? I didn't say that it was. By the way, "the outer domain takes all the
> variables" is an inprecise summary. That's why I added "it can" from time to
> time...

Sorry, I misquoted.

> For example: (x*y)::UP(x, POLY INT) should be OK, in my opinion. x would be a
> variable of the outer domain, y a coefficient. No confusion can arise.

Yes, but you would disallow the prior use of x in POLY INT, which is where we
started! I would interpret, when a user uses UP(x, POLY INT), that (s)he wants a
new indeterminate x over POLY INT. Tagging would distinguish this x from any
possible prior use of x.

> Maybe it would be better to say "a variable that can be taken by an outer
> domain, cannot appear as a coefficient". To explain that (1/x)::POLY(EXPR INT)
> should yield an error, note that the variable is x, not (1/x).
> 
>  > )clear all
>  > a:=monomial(1,1)$UP(x, INT)
>  >   x
>  >
>  > a::SUP INT
>  >   ?
> 
> Note that this does not work in the compiler. You have to use makeSUP
> expressively. And in fact, I think it shouldn't work in the interpreter 
> either.

I don't know the mechanics of how the interpreter handles ::. We have seen it
uses at least more than one way (that is, it may use coerce, convert, and here,
makeSUP). I often don't know what map is used since ")set mess bot on" does not
always give output on "simple" things like this. However, we all know that the
compiler needs precise information, so if the interpreter is smart enough to use
makeSUP when :: is used, what's wrong with that?
 
>  > a::SUP UP(x,INT)
>  >   x
> 
>  > Even though a tower of polynomial rings is involved in the above, these are
>  > legitimate mathematical constructs (and correctly done) -- the unspecified
>  > variable is intended to be transcendental over ANY coefficient domain, and
>  > is often used to work with minimal polynomial of an element algebraic over
>  > the coefficient domain. Here it shows that in coercing a variable into
>  > SUP(R), the interpreter first try to coerce it into R, and failing that, to
>  > to unspecified variable. So in this case, SUP only takes a variable when
>  > necessary.
> 
> As an aside: towering SUP's is also an interesting issue. Consider
> 
> makeSUP(y::UP(y,SUP INT)*x::UP(x,INT)) giving
>    (20)  ? ?
>           Type: SparseUnivariatePolynomial SparseUnivariatePolynomial Integer
> 
> Well, you know that.

If we tag the variables, there will be no need for SUP using unspecified
variables and printing out ? all the time and the above I/O problem will go
away.

>  > > I would like to have a mapping from maths to axiom as clear as possible.
>  > > And given the convention that the "outermost" domain "takes" all the
>  > > variables (it can), EXPR POLY INT and EXPR INT would be the same
>  > > mathematically, since any polynomial is an EXPR. Of course, the
>  > > representations could be different in the two domains.
> 
>  > See above discussion on indexed method constructing polynomial rings.
> 
> I agree that your proposal (if I understood it) is also clean.

Thanks. I probably wrote too much!
 
>  > > Thus I think the direction to go is to put these checks into the 
> compiler.
> 
>  > I don't know enough about compilers: Can a compiler single out (12) to
>  > disallow it? For now, just don't use the same symbol for two different
>  > things, and perhaps fix the error message with a warning instead.
> 
> I meant to say: "put these checks into the algebra." This is clearly possible.

Not clear to me at all! Perhaps I am missing the obvious. I believe it is going
to be a mess even if it is possible. It would be difficult to specify precisely
what towers are allowed or not. I think we should allow all towers and variables
should not be mixed (in any solution) and it is easier to do so with tags than
with tests. Tests are inefficient because it is a run-time penalty; while tags,
except at compile time, do not exert a penalty at all -- the symbol hash table
is the same, just the identifiers are longer.

William