\documentclass[a4paper]{article}
\usepackage[latin1]{inputenc}

%I want this document to compile if latex2html is not installed
\usepackage{ifthen}
\ifthenelse{\boolean{true}}{%
%Currently this is always true, but see below.
\newcommand{\link}[2]{#1}
\newcommand{\gpcc}{{\tt gp2c}}
%HEVEA \renewcommand{\link}[2]{\ahref{#2}{#1}}
}{%
%If we use latex2html, we must set the boolean to false so that this branch is
%used. However current latex2html version does not know about ifthen and so
%just read *both* branch so it is *not* necessary.
\usepackage{html}
\newcommand{\link}[2]{\htmladdnormallink{#1}{#2}}
\newcommand{\gpcc}{gp2c}
}
%Use \gpcc only for large fonts.(titles,sections)
\newcommand{\pathlink}[1]{\link{\path{#1}}{#1}}
\newcommand{\path}[1]{\texttt{#1}}
\newcommand{\gp}[1]{\textit{#1}}
\newcommand{\pari}[1]{\textsf{#1}}
\newcommand{\cmd}[1]{{\noindent\bf #1}}
\newcommand{\typ}[1]{\texttt{t\_#1}}
\title{\gpcc\ types and the description system}
\author{By Bill Allombert}

\begin{document}
\maketitle
\tableofcontents
\section{\gpcc\ types}
\subsection{Introduction}

The main feature GP2C adds above GP is the use of types. Types give a
semantic to PARI objects, so that GP2C can generate code that use
specialized (hence faster) PARI functions instead of generic ones. Please
read the section 'Advanced use of GP2C' in the GP2C manual for how to use
the GP2C types and examples.

Such types are used in conjunctions with so-called \emph{descriptions} which
are stored in the field 'Description:' of the file \path{pari.desc} and provide
the actual C code to use depending of the types of the arguments. They are
described in Section~\ref{description}.

Abstractly, a GP2C type is a set of pairs $(A,B)$ where $A$ is a mathematical
object and $B$ its computer representation. Two different types can contain
the same mathematical object, with a different computer representation.
For example the type \gp{bool} is the set \{(true,1L), (false,0L)\},
\emph{i.e.}~true and false with true coded by the C-long integer \(1\) and
false coded by the C-long integer \(0\); the type \gp{negbool} is
the set \{(true,0L), (false,1L)\} which is the same set of mathematical objects,
but now true is coded by the C-long integer \(0\) and false by the C-long
integer \(1\).

For each GP2C type, there exists a C type $Ct$ such that for all pairs $(A,B)$
belonging to the type, the C type of $B$ is $Ct$. This C type is specified by
the description \pari{\_typedef}.

The GP2C types are preordered. Abstractly, we say that $t_1\prec
t_2$ if and only if there is a map $f$ such that $(A,B)\mapsto (A,f(B))$
defines a one-to-one mapping from $t_1$ to $t_2$.
Practically we restrict the relation $\prec$ to make it a partial order
such that any two types have an upper bound.
This partial order is defined by the chains in the description
\pari{\_type\_preorder}.  It can be printed by running \verb!gp2c -t!.

\begin{figure}[htbp]
  \begin{center}
    \[
%HEVEA \begin{toimage}
\unitlength=1.mm
\begin{picture}(12,50)(-6,0)
\put(6,50){\makebox[0mm]{gen}}
\put(6,44){\line(0,1){5}}
\put(6,40){\makebox[0mm]{mp}}
\put(-2,44){\line(1,1){5}}
\put(-3,40){\makebox[0mm]{vec}}
\put(-9,44){\line(2,1){12}}
\put(-9,40){\makebox[0mm]{pol}}
\put(-9,34){\line(0,1){5}}
\put(-9,30){\makebox[0mm]{var}}
\put(12,30){\makebox[-1.5mm]{real}}
\put(12,34){\line(-1,1){5}}
\put(0,30){\makebox[-1.5mm]{int}}
\put(0,34){\line(1,1){5}}
\put(0,20){\makebox[1mm]{small}}
\put(0,24){\line(0,1){5}}
\put(0,10){\makebox[1mm]{bool}}
\put(-8,17){\line(1,1){4}}
\put(-15,15){\makebox[1mm]{negbool}}
\put(-4,11){\line(-1,1){4}}
\put(0,14){\line(0,1){5}}
\put(0,00){\makebox[1mm]{void}}
\put(5,01){\line(1,4){7}}
\put(0,04){\line(0,1){5}}
\end{picture}
%HEVEA \end{toimage}
%HEVEA \imageflush
\]
    \caption{Example of type preorder}
    \label{fig:type}
  \end{center}
\end{figure}

The process of converting a mathematical object from one type to
another is called casting. The casting methods known to GP2C are
given by the \pari{\_cast} description.

\subsection{List of types}

In this section, we list the types known to PARI/GP.
The current list is available in the description \pari{\_typedef}.

\subsubsection{Basic types}
\begin{description}
\item[small] Small integers represented by C \pari{long} integers.
\item[int] Multi-precision integers represented by \typ{INT} GENs.
\item[real] Multi-precision floating point real numbers represented by \typ{REAL} GENs.
\item[mp] Multi-precision numbers. Union of the types \gp{int} and \gp{real}.
\item[vecsmall] Vectors of small integers represented by \typ{VECSMALL} GENs.
\item[vec] Vectors and matrices of PARI objects, represented by \typ{VEC},
\typ{COL} or \typ{MAT} GENs.
\item[var] Polynomial variables represented by their variable number which is
a C \pari{long} integer. This is associated to the prototype code 'n'.
\item[pol] Polynomials represented by \typ{POL} GENs.
\item[genstr] Strings represented by \typ{STR} GENs.
\item[list] GP lists represented by \typ{LIST} GENs.
\item[gen] Generic PARI objects represented by GENs.
\end{description}
\subsubsection{Special types}
\begin{description}
\item[void] This type is a set with only one element called \gp{void}. This is
the return type of functions not returning anything. GP allows to cast it to
\(0\).
\item[bool] Boolean values represented as C \pari{long} integers, where 1 is
true and 0 is false.
\item[negbool] Negated boolean values represented as C \pari{long} integers,
where 0 is true and 1 is false.

\item[lg] Vector lengths represented by the \pari{lg} macro output, i.e.
a C \pari{long} integer equal to the actual length plus one.

\item[str] C strings represented by C \pari{const char *} strings.
\item[typ] GEN types represented by C \pari{long} integers, as returned by the
\pari{typ()} macro.
\end{description}

\subsubsection{Internal types}
The following types are mainly for internal use inside GP2C.
\begin{description}
\item[empty] This type is the empty set. No individual object can be of this
type but a set of objects can. In fact this is a default type for an
unspecified set of objects.
\item[small\_int] Small integers represented by C \pari{int} integers.
This is only available for compatibility with PARI function returning
\pari{int} (instead of \pari{long}).
\item[bptr] Byte pointer. This is used for the \pari{primepointer} global
variable.
\item[func\_GG] function with protype \pari{GEN f(GEN,GEN)}. Used by
\gp{forvec}.
\item[pari\_sp] This is the stack pointer type \pari{pari\_sp}.
\end{description}

\subsubsection{Types for data structure.}
These types are mainly defined to allow the use of inline member functions.

\begin{description}
\item[nf] Number field as returned by \gp{nfinit}.
\item[bnf] Big number field as returned by \gp{bnfinit}.
\item[bnr] Ray class field as returned by \gp{bnrinit}.
\item[ell] Elliptic curve as returned by \gp{ellinit}.
\item[bell] Big elliptic curve as returned by \gp{ellinit}.
\item[clgp] Class group as returned by the 'clgp' member function.
\item[prid] Prime ideal as returned by \gp{idealprimedec}.
\item[gal] Galois group as returned by \gp{galoisinit}.
\end{description}

\subsection{C-Type}
A \textit{C-Type} is just a level of indirection toward real C types.
C-types are defined by the descriptions \pari{\_decl\_base} and
\pari{\_decl\_ext}.  Each type belongs to a C-type as specified by the
description \pari{\_typedef}.

\section{The description system}\label{description}

\subsection{Introduction}

The description system is a way to describe the PARI application programming
interface in a way understandable by both the GP2C compiler and human
beings. The present document is mostly addressed to this second category.
We start by a simple example:

The description of the GP function \gp{sqr} is
\begin{verbatim}
 (int):int      sqri($1)
 (mp):mp        gsqr($1)
 (gen):gen      gsqr($1)
\end{verbatim}

Each line is called a \textit{rule}, which in this case consists of three
parts. Let us consider the first one: the parts \verb!(int)!, \verb!:int! and
\verb!sqri($1)!  are respectively called the \textit{pattern}, \textit{type},
and \textit{action} part.

When GP2C compiles \gp{sqr(1)}, it computes the types of the arguments
(here~\gp{1} is of type \gp{small}) and matches them against the patterns
from top to bottom. The ``best'' rule is used; in case of a tie, the topmost
rule wins. Here, all three rules apply, and the first rule wins. Since the type
of this rule is \gp{int}, GP2C sets the type of the expression
\gp{sqr(1)} to \gp{int}. The action part is \verb!sqri($1)!, so GP2C
generates the C code \pari{sqri(\$1)} where \pari{\$1} is replaced by the
code of the argument \gp{1} cast to the pattern type (\gp{int}). The result
is the C code \pari{sqri(gen\_1)}.

Now a more complex example: the description of the GP function \gp{exp} is
\begin{verbatim}
 (real):real    mpexp($1)
 (mp):mp:prec   gexp($1, prec)
 (gen):gen:prec gexp($1, prec)
\end{verbatim}
When GP2C compiles \gp{exp(1)}, it looks for the "best" rules.
The first rule cannot be used, because there is no way to cast a
\gp{small} to a \gp{real}, so it uses the second rule.
This time the result will be
of type \gp{mp}. The extra part \verb!:prec! is called a mode. The
mode `prec' states that the action part will use the special `prec'
variable that holds the current real precision. This is obvious from
the action part code, but GP2C do not parse the action part so it
needs this mode. Note that the last rule is also valid and has the
same action part so would generate the exact same code. However, the
type of the expression would be less precise.

The description of the GP function \gp{matdet} is
\begin{verbatim}
 (gen, ?0):gen      det($1)
 (gen, 1):gen       det2($1)
 (gen, #small):gen  $"incorrect flag in matdet"
 (gen, small):gen   det0($1, $2)
\end{verbatim}
We see several new pattern atoms:
\begin{itemize}
\item \gp{1} matches a literal $1$, e.g. \gp{matdet(M,1)} would match the
second rule.
\item \gp{?0} matches an optional literal $0$: \gp{matdet(M)},
\gp{matdet(M,0)} and \gp{matdet(M,)} all match the first rule.
\item \gp{\#small} matches an unspecified literal \gp{small}.
\end{itemize}
Finally, we also see a new action \gp{\$"\dots"}, which causes GP2C
to display the error message and abort.

\subsection{Definitions}
We now give a formal definition of descriptions.
\subsubsection{Description}
A description is a line-separated list of \textit{rules}.
\subsubsection{Rule}
A rule is a line of the form
\begin{quote}
(\textit{pattern})\textit{:type}\textit{:modelist}  \textit{action}
\end{quote}
Only the pattern part is mandatory, though most rules also include
an action and a type.

\subsubsection{Pattern}
A pattern is a comma-separated list of \textit{pattern atoms}.

\subsubsection{Type}
The type of a rule is a standard GP2C type.

\subsubsection{Modelist}
A modelist is a colon-separated list of \textit{modes}.

\subsubsection{Action}

An action is a string (normally a piece of C code) that can
include \textit{replacement strings}. Replacement strings start by
a \$ and are substituted according to the replacement rules.

\subsection{Pattern atom}

A pattern atom is one of the following, where \gp{type} is any GP2C type,
\gp{n} any small integer, \gp{"str"} any character string and \gp{ctype}
any C-type. A pattern atom can match an object.

\begin{itemize}
\item \gp{type}. This matches any object of type comparable to \gp{type}.
\item \gp{n}. This matches a constant small integer value equal to \gp{n}.
\item \gp{?n}. This matches an optional \gp{small} value which defaults to
 \gp{n}.
\item \gp{?type}. This matches an optional \gp{type} value with standard default value.
\item \gp{"str"}. This matches a constant character string equal to \gp{str}.
\item \gp{\&type}. This matches a reference (the GP \gp{\&x} construction) to
an object of type equal or less than \gp{type} referencing the same data type.
\item \textit{nothing}. This matches a missing argument.
\item \gp{\#type}. This matches a constant value of type \gp{type}.
\item \gp{...} This matches any number of arguments matching the previous atom.
This must be the last atom of the pattern. This allows to implement functions
taking an unlimited number of arguments.
\item \gp{C!ctype}. This matches any object of C-type \gp{ctype}.
\item \gp{@type}. This matches a variable of type \gp{type}. This is mainly used
for expressions that evaluate their arguments several times.
\item \gp{*type}. This matches an lvalue of type \gp{type}. This is used in
constructions that modify their arguments.
\end{itemize}

\subsection{Matching}

The best rule is determined as follows:
\begin{enumerate}
\item The result of matching a pattern atom against some GP code is
either 'reject' or 'match'.
\item There are three matching levels: 'partial', 'normal' and 'perfect'.
\item A pattern matches if all the atoms match.
\item A rule matches if its pattern matches.
\item The best rule is the matching rule with the higher number of normal
and perfect matches. In case of a tie, the highest number of perfect matches
wins. If there is still a tie, the topmost rule wins.
\end{enumerate}

When matching the pattern atoms \gp{type} and \gp{?type}, the matching
level is determined as follows:
\begin{itemize}
\item a perfect match occurs when the type of the object is exactly \gp{type},
\item a normal match when the type is less than \gp{type},
\item a partial match when the type is bigger than \gp{type}.
\item Rejection happens when the types are uncomparable.
\end{itemize}
Other pattern atoms always result in a reject or a perfect match.

\subsection{Mode}
Modes are used in descriptions to give more information to GP2C about the
action part.  They are usually useless to human beings that are smart
enough to understand the action part. The current list of modes is:
\begin{description}
\item[prec] The action uses the \pari{prec} variable.
\item[parens] The action does not have top precedence. GP2C will put it between
parentheses when needed (see \$())
\item[copy] The action returns data that access memory belonging to other
objects. GP2C will generate calls to \pari{gcopy()} when needed.
\end{description}

%\begin{description}
%\item[long] The action returns a \pari{GEN} casted to \pari{long}. GP2C will
%generate type casting if needed. This is not supported anymore.
%\item[semicolon] The action is a full block and does not need a trailing
%semicolon.
%\item[brace] The action does not need to be put inside brace.
%\item[else] This is an if-else block. This is used by GP2C in conjunction
%with brace to add braces around if-else blocks.
%\end{description}

%The following modes are defined but currently ignored.
%\begin{description}
%\item[var] (ignored)  value cannot be determined at compile time
%\item[sidef] (ignored) The statement has a side-effect.
%\item[term] (ignored) The statement terminate the function.
%\end{description}

\subsection{Lists of replacement strings}

The following special sequences can occur in the action part:
\begin{itemize}

\item \pari{\$n}. This is replaced by the \(n\)-th argument of the function.

\item \pari{\$(n)}. This is replaced by the \(n\)-th argument of the function
between parenthesis if it has the parens mode.

\item \pari{\$type:n}. This is replaced by the \(n\)-th argument of the
function cast to type \gp{type}.

\item \pari{\$(type:n)}. Combination of \$(n) and \$type:n.

\item \pari{\$\%n}. This is replaced by the \(n\)-th argument of the function,
which must be a constant string, with all \% characters doubled and no quotes.
This is for use inside format specification.

\item \pari{\$prec}: short cut for \pari{\${prec}}.
\item \pari{\$bitprec}: short cut for \pari{\${bitprec}}.
\item \pari{\$"message"}. Signals an invalid condition. GP2C will abort by
printing the error message \pari{message}.

\item \pari{\$\{RPN sequence\}}
The RPN sequence is a space separated list of RPN commands that will be
evaluated by the GP2C internal RPN evaluator.
If the stack is empty at the end of the evaluation, this is replaced by
the empty string, else this is replaced by the integer at the top of the
stack. Some RPN commands generate text, in that case it is pasted just before
the \$ sign.
\end{itemize}

\subsection{Lists of RPN commands}
The commands are evaluated with respect to a stack of integer values,
initially empty.
The exact list of command supported by a particular GP2C version is the
\pari{\%accepted\_command} hash in the script \path{scripts/822\_desc.pl.in}.

\begin{description}
\item[\gp{literal integer}] push the integer at the top of the stack.
\item[:\gp{type}] push the type \gp{type} at the top of the stack.
\item[add, sub, mul, div, mod] 2-ary arithmetic operators
\item[neg] 1-ary arithmetic operator
\item[and, or, xor] 2-ary logical operators
\item[not] 1-ary logical operator
\item[type] pop an integer $n$ and push the type of the $n$-th argument.
\item[value] pop an integer $n$ and push the value of the $n$-th argument,
provided it is a constant integer.
\item[code] pop an integer $n$ and generate the C code for the $n$-th argument.
\item[cast] pop an integer $n$ and a type $t$ and generate the C code for the
$n$-th argument cast to type $t$.
\item[parens] this is a flag requesting \cmd{code} and \cmd{cast} to enclose
the C code between parenthesis if the argument has the \gp{parens} mode.
\item[str\_format, str\_raw] pop an integer $n$ such that the $n$-th argument
is a constant string and display the string without leading and ending ".
Furthermore \cmd{str\_format} will display the string in a way suitable for
inclusion in a format string by quoting meta-characters.
\item[prec] display the local precision (in prec format).
\item[bitprec] display the local precision in bit.
\end{description}

The following RPN commands are useful with the \gp{...} pattern atom to
implement functions that take an unlimited number of arguments.
\begin{description}
\item[nbarg] push the actual number of arguments of the function.
\item[format\_string, format\_args] pop an integer $n$ such that the $n$-th
argument corresponds to a \gp{...} pattern atom and generate a format string
and a list of arguments, see the description of the GP function \gp{print}.
\item[code, cast] If the integer $n$ corresponds to a \gp{...} pattern atom,
generate a comma-separated list of C code for the arguments $n-1$, $n$, $n+1$,
\ldots, \cmd{nbarg}, by matching each argument against the $n-1$ pattern atom.
\item[stdref] this is a flag requesting \cmd{code} and \cmd{type} to
prepend a '\&' before each arguments.
\end{description}
The following RPN commands are useful to implement functions that take closures
as arguments.
\begin{description}
\item[wrapper, cookie] pop an integer $n$ and generate a call to the wrapper
(resp. the cookie associated to the wrapper) for the $n$-th argument. The
wrapper generated depends on the wrapper prototype in the Wrapper field.
The cookie is the list of local variables seen by the closure.
\end{description}

\end{document}