Re: group identification patch

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Wed, Apr 02, 2003 at 12:52:38PM -0800, Ilya Zakharevich wrote:
> On Wed, Apr 02, 2003 at 03:05:49PM +0200, Bill Allombert wrote:
> > Hello PARI-dev,
> > 
> > Here a (large) patch that add a feature similar to GAP IdGroup
> > function for weakly super-solvable group.
> 
> > +GEN
> > +groupelts_center(GEN S)
> > +{
> 
> This looks like a part of a very sad story.  It looks like different
> (complicated) algorithms used for implementation of particular PARI
> functions have tons of small C helper functions.  Some of these helper
> functions have a signature good for importing to PARI.  Some of these
> helper functions provide algorithms of general interest (I remember
> seeing something like a knapsack algo etc., now some algorithms for
> group manipulation).
> 
> But all these goodies are sitting there undocumented - and as a
> consequence, unused!  Should not we keep a list of "semi-supported"
> importable toolbox-functions in PARI core?

Having small C helper function is a major win in design compared to the
old monolithic design. This is not a loss.

The point of the description system is to be able to document functions
that are not GP function, and to be able to just do install(func)
without guessing the prototype.

I thing we should go ahead and use it. It is a zero-code patch.
It will require a huge effort to document all the PARI function
we find interesting, but then better start now!

A different point is to have a naming policy for PARI functions
that help to find them.

It seems we have standardised on
<argument types>_<what it does>

(with some unfortunate exception like polcyclo and matcompanion.

I have even wrote a file sometime ago:

-------------------
This file describe the naming scheme for functions
performing modular computation in PARI.

Here the decription using yacc syntax:


function_name: type exponent '_' func 
             | type exponent '_' function_name
;

type: basering | type letters;

basering: Fp | Fq | Z | Q;

letters:/*empty*/
       | letters X /*polynomial*/
       | letters M /*matrix*/
       | letters V /*vector*/
       | letters Q /*quotient by a polynomial, add a new modulus*/
;
exponent: /*empty*/
        |integer>=2;


func : add /*add*/
     | sub /*substract*/
     | mul /*multiply*/
     | divres
     | div /*divide*/
     | res /*lift*/
     | pow /*power*/
     | compo /*composition*/
     | etc.../*et caetera...*/
;

Func: Each func has its own argument spec, for nonmoduli args:

add:x,y -> x+y;/*commute*/
sub:x,y -> x-y;
mul:x,y -> x*y;/*commute*/
div:x,y -> euclidean quotient of x by y; 
res:x,y -> euclidean residue of x by y;
divres: x,y,*z -> as div but set z to res(x,y);
Type:
If all args of func have the same type, with same moduli, only one is needed and should have empty exponent, else all args must have a type and and exponent so that consecutive types are disctinct.  
If two types correspond to commuting args, they must be sorted by decreasing lexicographic order.

Arguments passing:

Argument are passed in order:
first arg of func, then moduli in the same order than in function_name.
One modulus for the first Fp, one for the first Fq, and one for each Q letter. 

example:

GEN FpXQ_pow(GEN P,GEN n,GEN p,GEN T);

compute P^n mod (p,T) where P is a polynomial.
(formerly Fp_pow_mod_pol)

GEN FpX_Fp_add(GEN P,GEN x, GEN p);

 add the scalar x to the polynomial P
(formerly  Fp_add_pol_scal)

GEN FpX_FpXQ_compo(GEN P,GEN Q, GEN p, GEN T)

compute P(Q) mod (T,p)

example:
GEN FpX_divres(GEN x,GEN y,GEN *z,GEN p)

Cheers,
Bill.