Karim Belabas on Wed, 26 Nov 2014 19:12:11 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
new GP functions varhigher / varlower |
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] `