new GP functions varhigher / varlower

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

Hi pari-dev,

I spent some time with Bill to allow variables of arbitrary priorities
in libpari, then GP. There were discussions on pari-dev, originating e.g. in

  http://pari.math.u-bordeaux.fr/archives/pari-dev-0609/msg00009.html

then various partial patches proposed (by Bill and Jeroen Demeyer) to cater for
specific needs, but no global semantic had been agreed upon.

Here's what I came up with, focusing on the GP interface, and the current
'master' branch. (The status of libpari programming is easier and now mostly
satisfactory in 'master': historical bugs involving MAXVARN are now gone.)

GP has 2 concepts of "variables", unfortunately mixed up since the dawn
of time:

 - a symbol known to the interpreter; associated to a value via assignments
   such as foobar = 1;

 - polynomial variables used to implement polynomial rings. They are
   associated to a variable number and
   * a character string used for to display monomials,
   * a priority (a long integer: larger values correspond to higher priority).

A statement such as

  foobar = 1

BOTH creates a symbol "foobar" (to which we associate the value '1': foobar
evaluates to 1 in an expression) AND a polynomial variable displayed as
"foobar" character string, and a priority strictly lower than any existing
polynomial variable.

  'foobar^2 + 'foobar + 1

actually returns a t_POL in variable 'foobar (displayed as "foobar").
This allows to input polynomials "just by typing them", as in Maple,
without prior cumbersome definitions of polynomial rings, as in Magma
or Sage.

On the other hand, variable ordering becomes a shaky concept:

On startup, symbols 'x' and 'y' are created, with x > y. [ Historically,
'x' was guaranteed to always have maximal priority; but no longer. ]

Then, since the parser automatically creates new variables as needed, variable
ordering becomes impredictable, depending on the exact session history. This
can be very annoying:

  /* session 1 */
  ? t + z;  \\ now t > z
  ? rnfequation(t^2+1,z^2-t)
    ***   at top-level: rnfequation(t^2+1,z^
    ***                 ^--------------------
    *** rnfequation: incorrect priority in rnfequation: variable t >= t

  /* session 2 */
  ? z + t;  \\ now z > t
  ? rnfequation(t^2+1,z^2-t)
  %2 = z^4 + 1

Due to the rigidity of most functions regarding variable ordering, there were
historical recomendations to be very wary of variables, e.g. not to define
number fields using the variable 'x' (otherwise you could no longer define
polynomials over that field), etc.


I implemented functions allowing to create variables with predictable,
arbitrary priorities:

  varhigher(name, {v}): return a variable 'name' whose priority is higher than
  the priority of v (of all existing variables if v is omitted).

  varlower(name, {v}): return a variable 'name' whose priority is lower than
  the priority of v (of all existing variables if v is omitted.

Now

   ? t = varlower("t", 'z);
   ? rnfequation(t^2+1, z^2-2)

works in all sessions, independently of the session history. And it
is no longer mandatory to avoid a particular "name" (e.g. x) for variables
of a certain type.


The global semantic should then be as follows:

  1) when encountering a new symbol the GP interpreter should only create a new
  polynomial variable (a new variable number) when actually synthetizing a
  t_POL or a t_SER   [ THIS IS NOT IMPLEMENTED YET ]

  E.g. the following statements should no longer create the polynomial
  variable 'z':
    z = 1
    z() = 1
    issquare(1, &z)
    z++      \\  should raise an exception (current returns 'z+1)
    z *= 2   \\  should raise an exception (current returns 2*'z)

  2) When an expression triggers an exception, then an error recovery,
  no new polynomial variables should be created in the process
  [ symbols are still defined ]

    z = 1; 1/0

  should not create 'z (but may still add "z" to our table of symbols).

  3) We may have different variables [ different priorities ] displayed using
  the same caracter string.

  ?  z = varhigher("x",x)
  %1 = x
  ? variable()
  %2 = [x, x, y, z]

  - the symbol "z" contains a monomial in the variable "x" of highest priority
  - the symbol "x" still contains a monomial in the variable "x" of lower
    priority (this is the one you get with 'x).


Known issues:

0) [BUG] The gp interpreter currently creates polynomial variables in many
cases where it shouldn't.

1) [WONTFIX] variables created via varhigher / varlower can not be accessed by
typing their name (or the quote operator 'foo). This is by design: the same
(display) string can be associated to many variables. A given symbol can be
associated to only one of them.

2) [WONTFIX] varhigher / varlower are usually incompatible with copy-paste
(hence write / read)

  ? t = varhigher("x",x);
  ? t * x
  %2 = x*x

This bivariate polynomial makes perfect sense in computations, although the
display is mildly confusing. But copy-pasting this will yield x^2, of course.

3) [BUG] objects in binary form (writebin) may not be compatible with other
sessions (we need to create the necessary variables with the right priorities
when importing polynomials and rewrite the object). This is not a new bug:
pari-stable has

  \\ session 1 
  ? writebin(file,'foobar);

  \\ session 2 
  ? read('foobar);
  %1 = #<3>    \\ variable number 3 has no associated character string

But with varhigher/varlower we can actually import invalid objects that may
crash the session. (Multivariate polynomials whose internal structure
contradict the sessions variable priorities.)

4) [FIXME?] We have a finite (small) number of variable numbers (2^16),
there is no mechanism to "kill" a variable, and varhigher / varlower can
easily use up all slots:

  ? while(1, varlower("x"))
  *** varlower: no more variables available.

If as above the sequence creating all those variables aborts with an error, we
have no problem (error recovery kills the variables). On the other hand
something like

  ? for(i=1,2^16-11, varlower("x"))

will succeed but essentially kill the session: no new variable can be created
from that point on:

  ? u
  ***   at top-level: u
  ***                 ^-
  ***   no more variables available.

This is not much different than the old 

  ? for(i=1,2^16,eval(Str("x",i)))

which kills pari-stable, though.

5) [FIXME?] I decided that varhigher / varlower was enough, and not to implement
"varinbetween" (priority simultaneously higher than ... / lower than ...).
Easy to do but I see no real use-case...

6) [TODO] We need a variables(T) function that returns the list of
variables used in T: with variable(T) we can get the variable of highest
priority occuring in T, but it's very hard to get the variable of lowest
priority. It's useful to obtain e.g. a variable of lower priority than
all variables occuring in T without using up a variable number to create
a *new* variables with guaranteed lowest priority.


Please test and suggest improvements (to the documentation as well) !

Cheers,

    K.B.

P.S. variable() allows to see which polynomial variables have been
defined so far, ordered by decreasing priority.

--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`