pari-doc 2.7.5-1 / usr / share / pari / doc / develop.tex

\def\TITLE{Developer's Guide to the PARI library}
\input parimacro.tex

% START TYPESET
\begintitle
\vskip 2.5truecm
\centerline{\mine Developer's Guide}
\vskip 1.truecm
\centerline{\mine to}
\vskip 1.truecm
\centerline{\mine the PARI library}
\vskip 1.truecm
\centerline{\sectiontitlebf (version \vers)}
\vskip 1.truecm
\authors
\endtitle

\copyrightpage
\tableofcontents
\openin\std=develop.aux
\ifeof\std
\else
  \input develop.aux
\fi
\chapno=0

\chapter{Work in progress}

This draft documents private internal functions and structures for hard-core
PARI developers. Anything in here is liable to change on short notice. Don't
use anything in the present document, unless you are implementing new
features for the PARI library. Try to fix the interfaces before using them,
or document them in a better way.
If you find an undocumented hack somewhere, add it here.

Hopefully, this will eventually document everything that we buried in
\kbd{paripriv.h} or even more private header files like \kbd{anal.h}.
Possibly, even implementation choices! Way to go.

\section{The type \typ{CLOSURE}}\kbdsidx{t_CLOSURE}\sidx{closure}
This type holds closures and functions in compiled form, so is deeply
linked to the internals of the GP compiler and evaluator.
The length of this type can be $6$, $7$ or $8$ depending whether the
object is an ``inline closure'', a ``function'' or a ``true closure''.

A function is a regular GP function. The GP input line is treated as a
function of arity $0$.

A true closure is a GP function defined in a non-empty lexical context.

An inline closure is a closure that appears in the code without
the preceding \kbd{->} token. They are generally associated to the prototype
code 'E' and 'I'. Inline closures can only exist as data of other closures,
see below.

In the following example,
\bprog
f(a=Euler)=x->sin(x+a);
g=f(Pi/2);
plot(x=0,2*Pi,g(x))
@eprog\noindent
\kbd{f} is a function, \kbd{g} is a true closure and both \kbd{Euler} and
\kbd{g(x)} are inline closures.

This type has a second codeword \kbd{z[1]}, which is the arity of the
function or closure. This is zero for inline closures. To access it, use

\fun{long}{closure_arity}{GEN C}

\item \kbd{z[2]} points to a \typ{STR} which holds the opcodes. To access it, use

\fun{GEN}{closure_get_code}{GEN C}.

\fun{const char *}{closure_codestr}{GEN C} returns as an array of \kbd{char}
starting at $1$.

\item \kbd{z[3]} points to a \typ{VECSMALL} which holds the operands of the opcodes.
To access it, use

\fun{GEN}{closure_get_oper}{GEN C}

\item \kbd{z[4]} points to a \typ{VEC} which hold the data referenced by the
\kbd{pushgen} opcodes, which can be \typ{CLOSURE}, and in particular
inline closures. To access it, use

\fun{GEN}{closure_get_data}{GEN C}

\item \kbd{z[5]} points to a \typ{VEC} which hold extra data needed for
error-reporting and debugging. See \secref{se:dbgclosure} for details.
To access it, use

\fun{GEN}{closure_get_dbg}{GEN C}

Additionally, for functions and true closures,

\item \kbd{z[6]} usually points to a \typ{VEC} with two components which are \typ{STR}.
The first one displays the list of arguments of the closure without the
enclosing parentheses, the second one the GP code of the function at the
right of the \kbd{->} token. They are used to display the closure, either in
implicit or explicit form. However for closures that were not generated from GP
code, \kbd{z[6]} can point to a \typ{STR} instead. To access it, use

\fun{GEN}{closure_get_text}{GEN C}

Additionally, for true closure,

\item \kbd{z[7]} points to a \typ{VEC} which holds the values of all lexical
variables defined in the scope the closure was defined. To access it, use

\fun{GEN}{closure_get_frame}{GEN C}

\subsec{Debugging information in closure}\label{se:dbgclosure}

Every \typ{CLOSURE} object \kbd{z} has a component \kbd{dbg=z[5]}
which which hold extra data needed for error-reporting and debugging.
The object \kbd{dbg} is a \typ{VEC} with $3$ components:

\kbd{dbg[1]} is a \typ{VECSMALL} of the same length than \kbd{z[3]}. For each
opcode, it holds the position of the corresponding GP source code in the
strings stored in \kbd{z[6]} for function or true closures, positive indices
referring to the second strings, and negative indices referring to the first
strings, the last element being indexed as $-1$. For inline closures, the
string of the parent function or true closure is used instead.

\kbd{dbg[2]} is a \typ{VECSMALL} that lists opcodes index where new lexical
local variables are created. The value $0$ denotes the position before the
first offset and variables created by the prototype code 'V'.

\kbd{dbg[3]} is a \typ{VEC} of \typ{VECSMALL}s that give the list of
\kbd{entree*} of the lexical local variables created at a given index in
\kbd{dbg[2]}.

\section{The type \typ{LIST}}\kbdsidx{t_LIST}\sidx{list} This type needs to go
through various hoops to support GP's inconvenient memory model. Don't
use \typ{LIST}s in pure library mode, reimplement ordinary lists! This
dynamic type is implemented by a \kbd{GEN} of length 3: two codewords and a
vector containing the actual entries. In a normal setup (a finished list,
ready to be used),

\item the vector is malloc'ed, so that it can be realloc'ated without moving
the parent \kbd{GEN}.

\item all the entries are clones, possibly with cloned subcomponents; they
must be deleted with \tet{gunclone_deep}, not \tet{gunclone}.

The following macros are proper lvalues and access the components

\fun{long}{list_nmax}{GEN L}: current maximal number of elements. This grows
as needed.

\fun{GEN}{list_data}{GEN L}: the elements. If \kbd{v = list\_data(L)}, then
either \kbd{v} is \kbd{NULL} (empty list) or \kbd{l = lg(v)} is defined, and
the elements are \kbd{v[1]}, \dots, \kbd{v[l-1]}.

In most \kbd{gerepile} scenarios, the list components are not inspected
and a shallow copy of the malloc'ed vector is made. The functions
\kbd{gclone}, \kbd{copy\_bin\_canon} are exceptions, and make a full copy of
the list.

The main problem with lists is to avoid memory leaks; in the above setup,
a statement like \kbd{a = List(1)} would already leak memory, since
\kbd{List(1)} allocates memory, which is cloned (second allocation) when
assigned to \kbd{a}; and the original list is lost. The solution we
implemented is

\item to create anonymous lists (from \kbd{List}, \kbd{gtolist},
\kbd{concat} or \kbd{vecsort}) entirely on the stack, \emph{not} as described
above, and to set \kbd{list\_nmax} to $0$. Such a list is not yet proper and
trying to append elements to it fails:
\bprog
? listput(List(),1)
  ***   variable name expected: listput(List(),1)
  ***                                   ^----------------
@eprog\noindent
If we had been malloc'ing memory for the
\kbd{List([1,2,3])}, it would have leaked already.

\item as soon as a list is assigned to a variable (or a component thereof)
by the GP evaluator, the assigned list is converted to the proper format
(with \kbd{list\_nmax} set) previously described.

\fun{GEN}{listcopy}{GEN L} return a full copy of the \typ{LIST}~\kbd{L},
allocated on the \emph{stack} (hence \kbd{list\_nmax} is $0$). Shortcut for
\kbd{gcopy}.

\fun{GEN}{mklistcopy}{GEN x} returns a list with a single element $x$,
allocated on the stack. Used to implement most cases of \kbd{gtolist}
(except vectors and lists).

A typical low-level construct:
\bprog
  long l;
  /* assume L is a t_LIST */
  L = list_data(L); /* discard t_LIST wrapper */
  l = L? lg(L): 1;
  for (i = 1; i < l; i++) output( gel(L, i) );
  for (i = 1; i < l; i++) gel(L, i) = gclone( ... );
@eprog\noindent

\section{Protection of non-interruptible code}

GP allows the user to interrupt a computation by issuing SIGINT
(usually by entering control-C) or SIGALRM (usually using alarm()).
To avoid such interruption to occurs in section of code which are not
reentrant (in particular \kbd{malloc} and \kbd{free})
the following mechanism is provided:

\fun{}{BLOCK_SIGINT_START}{}
  Start a non-interruptible block code. Block both \kbd{SIGINT} and \kbd{SIGARLM}.

\fun{}{BLOCK_SIGALRM_START}{}
  Start a non-interruptible block code. Block only \kbd{SIGARLM}.
This is used in the \kbd{SIGINT} handler itself to delay an eventual pending
alarm.

\fun{}{BLOCK_SIGINT_END}{}
  End a non-interruptible block code

The above macros make use of the following global variables:

\tet{PARI_SIGINT_block}: set to $1$ (resp. $2$) by \kbd{BLOCK\_SIGINT\_START}
(resp. \kbd{BLOCK\_SIGALRM\_START}).

\tet{PARI_SIGINT_pending}: Either $0$ (no signal was blocked), \kbd{SIGINT}
(\kbd{SIGINT} was blocked) or \kbd{SIGALRM} (\kbd{SIGALRM} was blocked).
This need to be set by the signal handler.

Inside a block, a auto variable \kbd{int block} is defined which holds the
value of \kbd{PARI\_SIGINT\_block} when entering the block.

\subsec{Multithread interruptions}

To support multithread, \kbd{BLOCK\_SIGINT\_START} and
\kbd{BLOCK\_SIGALRM\_START} calls \kbd{MT\_SIGINT\_BLOCK(block);}, and
\kbd{BLOCK\_SIGINT\_END} calls \kbd{MT\_SIGINT\_UNBLOCK(block);}.

\tet{MT_SIGINT_BLOCK} and \tet{MT_SIGINT_UNBLOCK} are defined by the
multithread engine. They can calls the following public functions defined by
the multithread engine.

\fun{void}{mt_sigint_block}{void}

\fun{void}{mt_sigint_unblock}{void}

In practice this mechanism is used by the POSIX thread engine to protect against
asychronous cancellation.

\section{Black box groups}

A black box group is defined by a \tet{bb_group} struct, describing methods
available to handle group elements:
\bprog
    struct bb_group
    {
      GEN (*mul)(void*, GEN, GEN);
      GEN (*pow)(void*, GEN, GEN);
      ulong (*hash)(GEN);
      GEN (*rand)(void*);
      int (*equal)(GEN, GEN);
      int (*equal1)(GEN);
      GEN (*easylog)(void *E, GEN, GEN, GEN);
    };
@eprog
\kbd{mul(E,x,y)} returns the product $x\*y$.

\kbd{pow(E,x,n)} returns $x^n$ ($n$ integer, possibly negative or zero).

\kbd{hash(x)} returns a hash value for $x$ (\kbd{hash\_GEN} is suitable for this field).

\kbd{rand(E)} returns a random element in the group.

\kbd{equal(x,y)} returns one if $x=y$ and zero otherwise.

\kbd{equal1(x)} returns one if $x$ is the neutral element in the group,
and zero otherwise.

\kbd{easylog(E,a,g,o)} (optional) returns either NULL or the discrete logarithm
$n$ such that $g^n=a$, the element $g$ being of order $o$. This provides a
short-cut in situation where a better algorithm than the generic one is known.

A group is thus described by a \kbd{struct bb\_group} as above and auxiliary
data typecast to \kbd{void*}. The following functions operate on black box
groups:

\fun{GEN}{gen_Shanks_log}{GEN x, GEN g, GEN N, void *E, const struct bb_group
*grp} \hbadness 10000\break
Generic baby-step/giant-step algorithm (Shanks's method). Assuming
that $g$ has order $N$, compute an integer $k$ such that $g^k = x$.
Return \kbd{cgetg(1, t\_VEC)} if there are no solutions. This requires
$O(\sqrt{N})$ group operations and uses an auxiliary table containing
$O(\sqrt{N})$ group elements.

\fun{GEN}{gen_Pollard_log}{GEN x, GEN g, GEN N, void *E, const struct bb_group
*grp} \hbadness 10000\break
Generic Pollard rho algorithm. Assuming that $g$ has order $N$, compute an
integer $k$ such that $g^k = x$. This requires $O(\sqrt{N})$ group operations
in average and $O(1)$ storage. Will enter an infinite loop if there are no
solutions.

\fun{GEN}{gen_plog}{GEN x, GEN g, GEN N, void *E, const struct bb_group}
Assuming that $g$ has prime order $N$, compute an integer $k$ such that
$g^k = x$, using either \kbd{gen\_Shanks\_log} or \kbd{gen\_Pollard\_log}.
Return \kbd{cgetg(1, t\_VEC)} if there are no solutions.

If \kbd{easy} is not \kbd{NULL}, call \kbd{easy(E,a,g,N)} first and if the
return value is not \kbd{NULL}, return it. For instance this is used over
$\F_q^*$ to compute the discrete log of elements belonging to the prime
field.

\fun{GEN}{gen_Shanks_sqrtn}{GEN a, GEN n, GEN N, GEN *zetan, void *E, const
struct bb_group *grp} \hbadness 10000 returns one solution of $x^n = a$ in a
black box cyclic group of order $N$. Return \kbd{NULL} if no solution exists.
If \kbd{zetan} is not \kbd{NULL} it is set to an element of exact order $n$.

This function uses \kbd{gen\_plog} for all prime divisors of $\gcd(n,N)$.

\fun{GEN}{gen_PH_log}{GEN a, GEN g, GEN N, void *E, const struct bb_group
*grp}
Generic Pohlig-Hellman algorithm. Assuming that $g$ has order $N$, compute
an integer $k$ such that $g^k = x$. Return \kbd{cgetg(1, t\_VEC)} if there
are no solutions. This calls \tet{gen_plog} repeatedly for all prime divisors
$p$ of $N$.

\kbd{easy} is as in \kbd{gen\_plog}.

\fun{GEN}{gen_order}{GEN x, GEN N, void *E, const struct bb_group *grp}
computes the order of $x$. If $N$ is not \kbd{NULL} it is a multiple of the
order, as a \typ{INT} or a factorization matrix.

\fun{GEN}{gen_factored_order}{GEN x, GEN N, void *E, const struct bb_group *grp}
returns $[o,F]$, where $o$ is the order of $x$ and $F$ is the factorization
of $o$. If $N$ is not \kbd{NULL} it is a multiple of the order, as a
\typ{INT} or a factorization matrix.

\fun{GEN}{gen_select_order}{GEN v, GEN N, void *E, const struct bb_group *grp}
$v$ being a vector of possible order of the group, try to find the true order
by checking orders of random points. This will not terminate if there is an
ambiguity.

\fun{GEN}{gen_gener}{GEN o, void *E, const struct bb_group *grp}
returns a random generator of the group, assuming it is of order exactly
$o$ (which can be given by a factorization matrix).

\subsec{Black box groups with pairing}

Theses functions handle groups of rank at most $2$ equipped with a family of
bilinear pairings which behave like the Weil pairing on elliptic curves over
finite field.

The function \kbd{pairorder(E, P, Q, m, F)} must return the order of of the $m$-pairing
of $P$ and $Q$, both of order dividing $m$, where $F$ is the factorisation matrix
of a multiple of $m$.

\fun{GEN}{gen_ellgroup}{GEN o, GEN d, GEN *pt_m, void *E, const struct bb_group *grp,
             GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)}

returns the elementary divisors $[d_1, d_2]$ of the group, assuming it is of order exactly
$o>1$ (which can be given by a factorization matrix), and that $d_2$ divides $d$.
If $d_2=1$ then $[o]$ is returned, otherwise \kbd{m=*pt\_m} is set to the order of the
pairing required to verify a generating set which is to be used with \kbd{gen\_ellgens}.

\fun{GEN}{gen_ellgens}{GEN d1, GEN d2, GEN m, void *E, const struct bb_group *grp,
             GEN pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)}
the parameters $d_1$, $d_2$, $m$ being as returned by \kbd{gen\_ellgroup}, returns a pair
of generators $[P,Q]$ such that $P$ is of order $d_1$ and the $m$-pairing of $P$ and
$Q$ is of order $m$. (Note: $Q$ needs not be of order $d_2$).

\subsec{Functions returning black box groups}

\fun{const struct bb_group *}{get_FpXQ_star}{void **E, GEN T, GEN p}
returns a pointer to the black box group $(\F_p[x]/(T))^*$.

\fun{const struct bb_group *}{get_FpE_group}{void **pt_E, GEN a4, GEN a6, GEN p}
returns a pointer to a black box group and set \kbd{*pt\_E} to the necessary data for
computing in the group $E(\F_p)$ where $E$ is the elliptic curve $E:y^2=x^3+a_4\*x+a_6$,
with $a_4$ and $a_6$ in $\F_p$.

\fun{const struct bb_group *}{get_FpXQE_group}{void **pt_E, GEN a4, GEN a6, GEN T, GEN p}
returns a pointer to a black box group and set \kbd{*pt\_E} to the necessary data for
computing in the group $E(\F_p[X]/(T))$ where $E$ is the elliptic curve $E:y^2=x^3+a_4\*x+a_6$,
with $a_4$ and $a_6$ in $\F_p[X]/(T)$.

\fun{const struct bb_group *}{get_FlxqE_group}{void **pt_E, GEN a4, GEN a6, GEN T, ulong p}
idem for small $p$.

\fun{const struct bb_group *}{get_F2xqE_group}{void **pt_E, GEN a2, GEN a6, GEN T}
idem for $p=2$.

\section{Black box finite fields}

A black box finite field is defined by a \tet{bb_field} struct, describing methods
available to handle field elements:
\bprog
  struct bb_field
  {
    GEN (*red)(void *E ,GEN);
    GEN (*add)(void *E ,GEN, GEN);
    GEN (*mul)(void *E ,GEN, GEN);
    GEN (*neg)(void *E ,GEN);
    GEN (*inv)(void *E ,GEN);
    int (*equal0)(GEN);
    GEN (*s)(void *E, long);
  };
@eprog

Note that, in contrast of black box group, elements can have non canonical forms, and
only \kbd{red} is required to return a canonical form.

\kbd{red(E,x)} returns the canonical form of $x$.

\kbd{add(E,x,y)} returns the sum $x+y$.

\kbd{mul(E,x,y)} returns the product $x\*y$.

\kbd{neg(E,x)} returns $-x$.

\kbd{inv(E,x)} returns the inverse of $x$.

\kbd{equal0(x)} $x$ being in canonical form, returns one if $x=0$ and zero otherwise.

\kbd{s(n)} $n$ being a small signed integer, returns $n$ times the unit element.

A finite field is thus described by a \kbd{struct bb\_field} as above and auxiliary
data typecast to \kbd{void*}. The following functions operate on black box
fields:

\fun{GEN}{gen_Gauss}{GEN a, GEN b, void *E, const struct bb_field *ff}

\fun{GEN}{gen_Gauss_pivot}{GEN x, long *rr, void *E, const struct bb_field *ff}

\fun{GEN}{gen_det}{GEN a, void *E, const struct bb_field *ff}

\fun{GEN}{gen_ker}{GEN x, long deplin, void *E, const struct bb_field *ff}

\fun{GEN}{gen_matcolmul}{GEN a, GEN b, void *E, const struct bb_field *ff}

\fun{GEN}{gen_matid}{long n, void *E, const struct bb_field *ff}

\fun{GEN}{gen_matmul}{GEN a, GEN b, void *E, const struct bb_field *ff}

\subsec{Functions returning black box fields}

\fun{const struct bb_field *}{get_Fp_field}{void **pt_E, GEN p}

\fun{const struct bb_field *}{get_Fq_field}{void **pt_E, GEN T, GEN p}

\fun{const struct bb_field *}{get_Flxq_field}{void **pt_E, GEN T, ulong p}

\fun{const struct bb_field *}{get_F2xq_field}{void **pt_E, GEN T}

\section{Black box algebra}

A black box algebra is defined by a \tet{bb_algebra} struct, describing methods
available to handle algebra elements:
\bprog
struct bb_algebra
{
  GEN (*red)(void *E, GEN x);
  GEN (*add)(void *E, GEN x, GEN y);
  GEN (*mul)(void *E, GEN x, GEN y);
  GEN (*sqr)(void *E, GEN x);
  GEN (*one)(void *E);
  GEN (*zero)(void *E);
};
@eprog

Note that, in contrast with black box groups, elements can have non canonical
forms, but only \kbd{add} is allowed to return a non canonical form.

\kbd{red(E,x)} returns the canonical form of $x$.

\kbd{add(E,x,y)} returns the sum $x+y$.

\kbd{mul(E,x,y)} returns the product $x\*y$.

\kbd{sqr(E,x)} returns the square $x^2$.

\kbd{one(E)} returns the unit element.

\kbd{zero(E)} returns the zero element.

An algebra is thus described by a \kbd{struct bb\_algebra} as above and
auxiliary data typecast to \kbd{void*}. The following functions operate on
black box algebra:

\fun{GEN}{gen_bkeval}{GEN P, long d, GEN x, int use_sqr, void *E,
          const struct bb_algebra *ff, GEN cmul(void *E, GEN P, long a, GEN x)}
$x$ being an element of the black box algebra, and $P$ some black box
polynomial of degree $d$ over the base field,  returns $P(x)$. The function
\kbd{cmul(E,P,a,y)} must return the coefficient of degree $a$ of $P$
multiplied by $y$. \kbd{cmul} is allowed to return a non canonical form.

The flag \kbd{use\_sqr} has the same meaning as for \kbd{gen\_powers}. This
implements an algorithm of Brent and Kung (1978).

\fun{GEN}{gen_bkeval_powers}{GEN P, long d, GEN V, void *E,
 const struct bb_algebra *ff, GEN cmul(void *E, GEN P, long a, GEN x)}
as \tet{gen_RgX_bkeval} assuming $V$ was output by
\tet{gen_powers}$(x, l, E, \var{ff})$ for some $l\geq 1$. For optimal
performance, $l$ should be computed by \tet{brent_kung_optpow}.

\fun{long}{brent_kung_optpow}{long d, long n, long m} returns the optimal
parameter $l$ for the evaluation of $n/m$ polynomials of degree $d$.
Fractional values can be used if the evaluations are done with different
accuracies, and thus have different weights.

\section{Black box free $\Z_p$-modules}

(Very experimental)

\fun{GEN}{gen_ZpX_Dixon}{GEN F, GEN V, GEN q, GEN p, long N, void *E,
                            GEN lin(void *E, GEN F, GEN z, GEN q),
                            GEN invl(void *E, GEN z)}

Let $F$ be a \kbd{ZpXT} representing the coefficients of some abstract
linear mapping $f$ over $\Z_p[X]$ seen as a free $\Z_p$-module, let $V$ be
an element of $\Z_p[X]$ and let $q = p^N$.  Return $y\in\Z_p[X]$ such that
$f(y)=V\pmod{p^N}$ assuming the following holds for $n\leq N$:

\item $\kbd{lin}(E, \kbd{FpX\_red}(F, p^n), z, p^n) \equiv f(z) \pmod{p^n}$

\item $f(\kbd{invl}(E, z)) \equiv z \pmod{p}$

The rationale for the argument $F$ being that it allows \kbd{gen\_ZpX\_Dixon}
to reduce it to the required $p$-adic precision.

\fun{GEN}{gen_ZpX_Newton}{GEN x, GEN p, long n, void *E,
                          GEN eval(void *E, GEN a, GEN q),
                          GEN invd(void *E, GEN b, GEN v, GEN q, long N)}

Let $x$ be an element of $\Z_p[X]$ seen as a free  $\Z_p$-module, and $f$
some differentiable function over $\Z_p[X]$ such that $f(x) \equiv 0
\pmod{p}$. Return $y$ such that $f(y) \equiv 0\pmod{p^n}$, assuming the
following holds for all $a, b\in \Z_p[X]$ and $M\leq N$:

\item $v = \kbd{eval}(E,a,p^N)$ is a vector of elements of $\Z_p[X]$,

\item $w = \kbd{invd}(E,b,v,p^M,M)$ is an element in $\Z_p[X]$,

\item $v[1] \equiv f(a) \pmod{p^N\Z_p[X]}$,

\item $df_a(w) \equiv b \pmod{p^M\Z_p[X]}$

\noindent and $df_a$ denotes the differential of $f$ at $a$. Motivation:
\kbd{eval} allows to evaluate $f$ and \kbd{invd} allows to invert its
differential. Frequently, data useful to compute the differential appear as a
subproduct of computing the function. The vector $v$ allows \kbd{eval} to
provide these to \kbd{invd}. The implementation of \kbd{invd} will generally
involves the use of the function \kbd{gen\_ZpX\_Dixon}.

\section{Public functions useless outside of GP context}

These functions implement GP functionality for which the C language or
other libpari routines provide a better equivalent; or which are so tied
to the \kbd{gp} interpreter as to be virtually useless in \kbd{libpari}. Some
may be generated by \kbd{gp2c}. We document them here for completeness.

\subsec{Conversions}

\fun{GEN}{toser_i}{GEN x} internal shallow function, used to implement
automatic conversions to power series in GP (as in \kbd{cos(x)}).
Converts a \typ{POL} or a \typ{RFRAC} to a \typ{SER} in the same variable and
precision \kbd{precdl} (the global variable corresponding to
\kbd{seriesprecision}). Returns $x$ itself for a \typ{SER}, and \kbd{NULL}
for other argument types. The fact that it uses a global variable makes it
awkward whenever you're not implementing a new transcendental function in GP.
Use \tet{RgX_to_ser} or \tet{rfrac_to_ser} for a fast clean alternative to
\kbd{gtoser}.

\subsec{Output}

\fun{void}{print0}{GEN g, long flag} internal function underlying the
\kbd{print} GP function. Prints the entries of the \typ{VEC} $g$, one by one,
without any separator; entries of type \typ{STR} are printed without enclosing
quotes. \fl is one of \tet{f_RAW}, \tet{f_PRETTYMAT} or \tet{f_TEX}, using the
current default output context.

\fun{void}{out_print0}{PariOUT *out, const char *sep, GEN g, long flag} as
\tet{print0}, using output context \kbd{out} and separator \kbd{sep} between
successive entries (no separator if \kbd{NULL}).

\fun{void}{printsep}{const char *s, GEN g, long flag} \tet{out_print0} on
\tet{pariOut} followed by a newline.

\fun{void}{printsep1}{const char *s, GEN g, long flag} \tet{out_print0} on
\tet{pariOut}.

\fun{char*}{pari_sprint0}{const char *s, GEN g, long flag} displays $s$,
then \kbd{print0(g, flag)}.

\fun{void}{print}{GEN g} equivalent to \kbd{print0(g, f\_RAW)}, followed
by a \kbd{\bs n} then an \kbd{fflush}.

\fun{void}{print1}{GEN g} as above, without the \kbd{\bs n}. Use
\tet{pari_printf} or \tet{output} instead.

\fun{void}{printtex}{GEN g} equivalent to \kbd{print0(g, t\_TEX)}, followed
by a \kbd{\bs n} then an \kbd{fflush}. Use \tet{GENtoTeXstr} and
\tet{pari_printf} instead.

\fun{void}{write0}{const char *s, GEN g}

\fun{void}{write1}{const char *s, GEN g} use \kbd{fprintf}

\fun{void}{writetex}{const char *s, GEN g} use \tet{GENtoTeXstr} and
\kbd{fprintf}.

\fun{void}{printf0}{GEN fmt, GEN args} use \tet{pari_printf}.

\fun{GEN}{Strprintf}{GEN fmt, GEN args} use \tet{pari_sprintf}.

\subsec{Input}

\kbd{gp}'s input is read from the stream \tet{pari_infile}, which is changed
using

\fun{FILE*}{switchin}{const char *name}

Note that this function is quite complicated, maintaining stacks of files
to allow smooth error recovery and \kbd{gp} interaction. You will be better
off using \tet{gp_read_file}.

\subsec{Control flow statements}

\fun{GEN}{break0}{long n}. Use the C control statement \kbd{break}. Since
\kbd{break(2)} is invalid in C, either rework your code or use \kbd{goto}.

\fun{GEN}{next0}{long n}. Use the C control statement \kbd{continue}. Since
\kbd{continue(2)} is invalid in C, either rework your code or use \kbd{goto}.

\fun{GEN}{return0}{GEN x}. Use \kbd{return}!

\fun{void}{error0}{GEN g}. Use \kbd{pari\_err(e\_USER,)}

\fun{void}{warning0}{GEN g}. Use \kbd{pari\_warn(e\_USER,)}

\subsec{Accessors}

\fun{GEN}{vecslice0}{GEN A, long y1, long y2} used to implement $A[y_1..y_2]$.

\fun{GEN}{matslice0}{GEN A, long x1, long x2, long y1, long y2}
used to implement $A[x_1..x_2,y_1..y_2]$.

\subsec{Iterators}

\fun{GEN}{apply0}{GEN f, GEN A} gp wrapper calling \tet{genapply}, where $f$
is a \typ{CLOSURE}, applied to $A$. Use \kbd{genapply} or a standard C loop.

\fun{GEN}{select0}{GEN f, GEN A} gp wrapper calling \tet{genselect}, where $f$
is a \typ{CLOSURE} selecting from $A$. Use \kbd{genselect} or a standard C loop.

\fun{GEN}{vecapply}{void *E, GEN (*f)(void* E, GEN x), GEN x} used to implement
\kbd{[a(x)|x<-b]}.

\fun{GEN}{vecselect}{void *E, long (*f)(void* E, GEN x), GEN A}
used to implement \kbd{[x<-b,c(x)]}.

\fun{GEN}{vecselapply}{void *Epred, long (*pred)(void* E, GEN x), void *Efun, GEN (*fun)(void* E, GEN x), GEN A}
used to implement \kbd{[a(x)|x<-b,c(x)]}.

\subsec{Function related to the GP parser}

The prototype code \kbd{C} instructs the GP compiler to save the current
lexical context (pairs made of a lexical variable name and its value)
in a \kbd{GEN}, called \kbd{pack} in the sequel. This \kbd{pack} can be used
to evaluate expressions in the corresponding lexical context, providing it is
current.

\fun{GEN}{localvars_read_str}{const char *s, GEN pack} evaluate the string $s$
in the lexical context given by \kbd{pack}.  Used by \tet{geval_gp} in GP
to implement the behaviour below:
\bprog
? my(z=3);eval("z=z^2");z
%1 = 9
@eprog

\fun{long}{localvars_find}{GEN pack, entree *ep} does \kbd{pack} contain
a pair whose variable corresponds to \kbd{ep}? If so, where is the
corresponding value? (returns an offset on the value stack).

\subsec{Miscellaneous}

\fun{char*}{os_getenv}{const char *s} either calls \kbd{getenv}, or directly
return \kbd{NULL} if the \kbd{libc} does not provide it. Use \tet{getenv}.

\fun{sighandler_t}{os_signal}{int sig, pari_sighandler_t fun} after a
\bprog
  typedef void (*pari_sighandler_t)(int);
@eprog\noindent
(private type, not exported). Installs signal handler \kbd{fun} for
signal \kbd{sig}, using \tet{sigaction} with flag \tet{SA_NODEFER}. If
\kbd{sigaction} is not available use \tet{signal}. If even the latter is not
available, just return \tet{SIG_IGN}. Use \tet{sigaction}.

\chapter{Regression tests, benches}

This chapter documents how to write an automated test module, say \kbd{fun},
so that \kbd{make test-fun} executes the statements in the \kbd{fun} module
and times them, compares the output to a template, and prints an error
message if they do not match.

\item Pick a \emph{new} name for your test, say \kbd{fun}, and write down a
GP script named \kbd{fun}. Make sure it produces some useful output and tests
adequately a set of routines.

\item The script should not be too long: one minute runs should be enough.
Try to break your script into independent easily reproducible tests, this way
regressions are easier to debug; e.g. include \kbd{setrand(1)} statement before
a randomized computation. The expected output may be different on 32-bit and
64-bit machines but should otherwise be platform-independent. If possible, the
output shouldn't even depend on \kbd{sizeof(long)}; using a \kbd{realprecision}
that exists on both 32-bit and 64-bit architectures, e.g. \kbd{\bs p 38} is a
good first step.

\item Dump your script into \kbd{src/test/in/} and run \kbd{Configure}.

\item \kbd{make test-fun} now runs the new test, producing a \kbd{[BUG]} error
message and a \kbd{.dif} file in the relevant object directory \kbd{Oxxx}.
In fact, we compared the output to a non-existing template, so this must fail.

\item Now
\bprog
  patch -p1 < Oxxx/fun.dif
@eprog\noindent
generates a template output in the right place \kbd{src/test/32/fun}, for
instance on a 32-bit machine.

\item If different output is expected on 32-bit and 64-bit machines, run the
test on a 64-bit machine and patch again, thereby
producing \kbd{src/test/64/fun}. If, on the contrary, the output must be the
same, make sure the output template land in the \kbd{src/test/32/} directory
(which provides a default template when the 64-bit output file is missing);
in particular move the file from \kbd{src/test/64/} to \kbd{src/test/32/}
if the test was run on a 64-bit machine.

\item You can now re-run the test to check for regressions: no \kbd{[BUG]}
is expected this time! Of course you can at any time add some checks, and
iterate the test / patch phases. In particular, each time a bug in the
\kbd{fun} module is fixed, it is a good idea to add a minimal test case to
the test suite.

\item By default, your new test is now included in \kbd{make test-all}. If
it is particularly annoying, e.g. opens tons of graphical windows as
\kbd{make test-ploth} or just much longer than the recommended minute, you
may edit \kbd{config/get\_tests} and add the \kbd{fun} test to the list of
excluded tests, in the \kbd{test\_extra\_out} variable.

\item The \kbd{get\_tests} script also defines the recipe for
\kbd{make bench} timings, via the variable \kbd{test\_basic}. A test is
included as \kbd{fun} or \kbd{fun\_$n$}, where $n$ is an integer $\leq 1000$;
the latter means that the timing is weighted by a factor $n/1000$. (This was
introduced a long time ago, when the \kbd{nfields} bench was so much slower
than the others that it hid slowdowns elsewhere.)

\section{Functions for GP2C}

\subsec{Functions for safe access to components}

Theses function returns the adress of the requested component after checking
it is actually valid. This is used by GP2C -C.

\fun{GEN*}{safegel}{GEN x, long l}, safe version of \kbd{gel(x,l)} for \typ{VEC},
\typ{COL} and \typ{MAT}.

\fun{long*}{safeel}{GEN x, long l}, safe version of \kbd{x[l]} for \typ{VECSMALL}.

\fun{GEN*}{safelistel}{GEN x, long l} safe access to \typ{LIST} component.

\fun{GEN*}{safegcoeff}{GEN x, long a, long b} safe version of
\kbd{gcoeff(x,a, b)} for \typ{MAT}.

\chapter{Parallelism}

\section{The PARI MT interface}

PARI provides an abstraction for doing parallel computations.

\fun{void}{mt_queue_start}{struct pari\_mt *pt, GEN worker} Let \kbd{worker}
be a \typ{CLOSURE} object of arity $1$.  Initialize the structure \kbd{pt}
to evaluate \kbd{worker} in parallel.

\fun{void}{mt_queue_submit}{struct pari\_mt *pt, long taskid, GEN task} Submit
\kbd{task} to be evaluated by \kbd{worker}, or \kbd{NULL} if no further task
is left to be submitted. The value \kbd{taskid} is user-specified and allows
to later match up results and submitted tasks.

\fun{GEN}{mt_queue_get}{struct pari\_mt *pt, long *taskid, long *pending}
Return the result of the evaluation by \kbd{worker} of one of the previously
submitted tasks. Set \kbd{pending} to the number of remaining pending tasks.
Set \kbd{taskid} to the value associate to this task by
\kbd{mt\_queue\_submit}.  Returns \kbd{NULL} if more tasks need to be
submitted.

\fun{void}{mt_queue_end}{struct pari\_mt *pt} End the parallel execution.

Calls to \tet{mt_queue_submit} and \tet{mt_queue_get} must alternate: each
call to \tet{mt_queue_submit} must be followed by a call to
\tet{mt_queue_get} before any other call to \tet{mt_queue_submit},
and conversely.

The first call to \tet{mt_queue_get} will return \kbd{NULL} until a
sufficient number of tasks have been submitted. If no more tasks are left
to be submitted, use
\bprog
  mt_queue_submit(handle, id, NULL)
@eprog\noindent
to allow further calls to \tet{mt_queue_get}.  If \tet{mt_queue_get} sets
\kbd{pending} to $0$, then no more tasks are pending and it is safe to call
\tet{mt_queue_end}.

The parameter \kbd{taskid} can be chosen arbitrarily. It is associated to a
task but is not available to \kbd{worker}.  It provides an efficient way to
match a tasks and results. It is ignored when the parameter \kbd{task} is
\kbd{NULL}.

\subsec{Miscellaneous}

\fun{void}{mt_broadcast}{GEN code}: do nothing unless the MPI threading engine
is in use. In that case, it evaluates the closure  \kbd{code} on all secondary
nodes. This can be sued to change the states of the MPI child nodes.
This is used by \tet{install}.

\section{Initialization}

This section is technical.

\fun{void}{pari_mt_init}{void} \label{pari_mt_init}
When using MPI, it is sometimes necessary to run initialization code on the
child nodes after PARI is initialized. This can be done as follow:

\item call \tet{pari_init_opts} with the flag \tet{INIT_noIMTm}.
This initializes PARI, but not the MT engine.

\item call the required initialization code.

\item call \tet{pari_mt_init} to initialize the MT engine.
Note that under MPI, this function only returns on the master node. On the
child nodes, it enters slave mode. Thus it is no longer possible to run
initialization code on the child nodes.

See the file \kbd{examples/pari-mt.c} for an example.

\fun{void}{pari_mt_close}{void} \label{pari_mt_close}
When using MPI, calling \tet{pari_close} will terminate the MPI execution
environment. If this is undesirable, you should call \tet{pari_close_opts} with
the flag \tet{INIT_noIMTm}.  This closes PARI without terminating the MPI
execution environment It is allowed to call \kbd{pari\_mt\_close} later to
terminate it.  Note that the once MPI is terminated it cannot be restarted, and
that it is considered an error for a program to end without having terminated
the MPI execution environment.

\vfill\eject
\input index\end