\documentclass{article}
\begin{document}
\title{Giac: une librairie de calcul formel en d\'eveloppement}
\author{Bernard Parisse}
\maketitle
\section{Pr\'esentation rapide de Giac/xcas}
Giac est un projet de librairie C++ de logiciel libre de calcul formel 
que j'ai d\'emarr\'e en 2000 \`a la suite du d\'eveloppement du logiciel de 
calcul formel
int\'egr\'e aux calculatrices graphiques HP49 et HP40\footnote{Pour
ceux qui souhaitent tester, il existe un
\'emulateur libre de ces calculatrices sous Unix/Linux
{\tt http://www.hpcalc.org/hp49g/pc/emulators/saturnv41.tgz}, et le 
t\'el\'echargement de la ROM est gratuit 
{\tt http://www.hpcalc.org/hp49/pc/rom/}} 
effectu\'e pendant
une d\'el\'egation au sein de Hewlett Packard en 1998/99, 
xcas est le nom du programme avec
interface graphique correspondant. J'ai \'ecrit l'essentiel du code,
Ren\'ee de Graeve ayant cod\'e le reste et document\'e l'essentiel de la
documentation en-ligne, R. Kreckel a \'ecrit la premi\`ere version
de l'autoconfiguration.

Giac a pour objectif de coordonner les efforts de d\'eveloppement
libres en vue de cr\'eer un logiciel de calcul formel et g\'eom\'etrie
dynamique utilisable aussi bien en recherche qu'en enseignement. 
Il existe un logiciel libre de calcul formel g\'en\'eraliste aujoud'hui:
c'est maxima (en fait pas tout-\`a-fait libre car maxima utilise gnuplot
pour la visualisation de fonctions et gnuplot contrairement \`a ce que
le gnu de son nom pourrait laisser croire n'est pas un logiciel libre). 
Mais mon opinion est que son avenir n'est pas clair:
il n'a malheureusement plus de maintainer officiel, mais ce qui est 
plus grave c'est qu'une grande partie de son code source est \'ecrit en 
lisp peu ou pas comment\'e (sans parler des probl\`emes de taille, j'y
reviendrai en parlant de financement plus loin).
Il existe aussi une offre commerciale importante. 
Mais il me semble qu'on ne peut pas raisonnablement baser
un r\'esultat math\'ematique sur un calcul utilisant un logiciel dont les sources
ne sont pas libres. D'autre part, les performances de certaines librairies
libres par rapport aux logiciels formels g\'en\'eralistes sont tr\`es souvent
bien meilleures dans leur domaine mais il manque \`a ces librairies
une interface graphique unifi\'ee et les assembler n\'ecessite des comp\'etences
d'administration syst\`eme pas forc\'ement accessible dans tous les laboratoires
de recherche et \`a fortiori pour un individu plus isol\'e.

De plus, la France dispose d'une importante communaut\'e
de recherche en calcul formel et est un des pays ou il est le plus
utilis\'e dans l'enseignement (en particulier dans les lyc\'ees grace
aux calculatrices graphiques symboliques). Pourtant nous n'avons
jamais d\'evelopp\'e de logiciel de calcul formel (mettons \`a part PARI
qui n'est pas g\'en\'eraliste). On a en effet l'habitude en France
de consid\'erer l'impl\'ementation d'un logiciel comme n'\'etant pas
de la recherche. Or les choix techniques sont aussi des choix
politiques. Il faut garantir notre ind\'ependance dans ce domaine
(\`a d\'efaut de pouvoir le faire aussi dans le domaine du mat\'eriel 
informatique mais cela s'\'ecarte des comp\'etences de math\'ematiciens...)

\section{L'\'etat actuel de giac}
Giac est disponible au t\'el\'echargement \`a partir de ma page web\\
\verb|http://www-fourier.ujf-grenoble.fr/~parisse|\\
sous forme de code source dans les m\^emes conditions que les logiciels
du projet GNU (ce qui permet en principe de le compiler sur n'importe
quel Unix, y compris Darwin en utilisant le trio \verb|configure|,
\verb|make|, \verb|make install|, mais aussi sous Windows avec cygwin),
ou sous forme de binaires compil\'es pour Linux PC 
(binaires statiques pour processeur
compatible ``Intel'' x86), Linux Familiar (distribution Linux
produite par Compaq pour processeur ARM tournant sur des Pocket PC) et
Windows (95, NT et au-del\`a). Il n'existe pas de portage sous Windows CE
pour l'instant mais le portage de PARI et maxima sur cet OS laisse
penser que cela est possible.

Le r\'epertoire \verb|check| du r\'epertoire source contient les tests
automatis\'es effectu\'es pour d\'etecter l'introduction accidentelle
de bugs, il donne une id\'ee des capacit\'es actuelles de Giac (pour
tester les performances de giac, on peut utiliser la commande
\verb|cas| en mode console apr\`es avoir d\'efini la variable
d'environnement \verb|SHOW_TIME|).

Actuellement, giac
est compos\'e des briques ext\'erieures logicielles suivants (sous licence
LGPL ou GPL):
\begin{itemize}
\item GMP (entier et flottants en pr\'ecision arbitraire) n\'ecessaire
\item FLTK/FLNX (librairie graphique permettant de faire
tourner xcas sur Windows, XWindows pour FLTK ou Microwindows/Nano-X pour 
FLNX) facultatif
\item import de fonctions de PARI (pour l'arithm\'etique, pour l'instant
factorisation d'entier et test de primalit\'e d\'eterministe) facultatif
\item import de fonction de GSL (Gnu Scientific Library pour le
num\'erique, pour l'instant fonctions sp\'eciales $\psi$ et airy et
int\'egration num\'erique d'ODE) facultatif
\end{itemize}

Les principales fonctionnalit\'e impl\'ement\'ees sont du point de vue
non math\'ematique: interface de type
``calculatrice graphique symbolique'' (style TI89/92 et HP49 mais sans 
\'editeur d'\'equation ni de matrice), langage de programmation (on peut
choisir une syntaxe de type C++ non typ\'e ou Maple ou Mupad ou HP49 en
mode polonaise invers\'e) avec
possibilit\'e de mise au point interactive (d\'ebuggeur, ne fonctionne
que sur plateforme Unix/Linux et en mode alg\'ebrique). L'interpr\'eteur du langage est \'ecrit
en lex/yacc et est donc facile \`a maitenir (flex et bison sont n\'ecessaires pour 
compiler Giac). Le reste des sources est \'ecrit en C++ (il s'agit
essentiellement de C utilisant les facilit\'es de C++ comme la gestion
de m\'emoire transparente pour le programmeur via new/delete et 
constructeurs/destructeurs, les conteneurs de la Standard
Template Library en particulier vector pour les listes et la progammation
g\'en\'erique). La gestion de la compilation est faite par automake/make.
La reconnaissance de la plateforme et l'utilisation optionnelle de briques 
logicielles ext\'erieures est g\'er\'ee par autoconf (\verb|AC_CHECK_LIB|). Tout
repose donc sur des programmes du projet GNU tr\`es r\'epandus et utilis\'es ce
qui devrait assurer la p\'erennit\'e.

Du point de vue math\'ematique: polyn\^omes (dense et creux \`a une variable,
creux \`a plusieurs variables), 
PGCD (heuristique, modulaire, sous-r\'esultant), B\'ezout (note pour 
Marie-Françoise: j'utilise bien les sous-r\'esultants dans le cas non
modulaire!), factorisation (sqff, ddf, Cantor-Zassenhauss,
Hensel, manque LLL+knapsack) y compris avec extensions alg\'ebriques, 
d\'erivation, int\'egration formelle (m\'ethodes
heuristiques), \'equations diff\'erentielles num\'erique (GSL), solveur
d'\'equations de type polynomiale \`a une variable, d\'eveloppement en
s\'erie et limit\'es (algorithme mrv), alg\`ebre
lin\'eaire (Gauss-Bareiss, valeurs propres, vecteurs propres et cycles
de Jordan, formes quadratiques), repr\'esentation graphique de
fonctions (fonction, param\'etrique, polaire) en interaction avec
la g\'eom\'etrie plane.

Les principaux manques actuels:
\begin{itemize}
\item la documentation
\item conformit\'e aux standards: Giac place toutes ses fonctions dans
l'espace de nom giac mais il faut que je renomme le type g\'en\'erique
de \verb|entier| en \verb|gen| et que je
rajoute le caract\`ere soulign\'e devant les noms de constantes
\verb|#define|
\item interface: \'editeur d'\'equation, \'editeur de matrice (si
possible avec un minimum de fonctionnalit\'es d'un tableur afin de r\'epondre
dans un m\^eme logiciel \`a tous les besoins rencontr\'es ). 
\item Impression: il faut pouvoir convertir les graphiques en Postscript
encapsul\'e et \'egalement pouvoir exporter au format PNG
\item graphique 3-d (voire g\'eom\'etrie dans l'espace): il faut probablement
utiliser Open-GL, donc la librairie Mesa. Je pourrais ensuite supprimer
toute r\'ef\'erence \`a gnuplot.
\item compl\'eter l'interface logicielle avec PARI et GSL. L'interface
avec GSL ne pose pas de probl\`emes, celle avec PARI s'annonce plus
d\'elicate (en particulier l'inclusion de macros, la gestion de
la m\'emoire et les noms de fonction C non conformes aux standards pour une
utilisation par d'autres). L'ensemble des fonctions PARI doit
donc \^etre regroup\'e dans un unique fichier \verb|.cc| qui sera
le seul \`a inclure \verb|#include <pari/pari.h>|.
\item fonctionnalit\'es en calcul formel: int\'egration (Risch au moins
dans le cas d'extensions transcendantes), limites
(algorithme mrv cas des fonctions ``non tractables'' et cas des fonctions 
sp\'eciales), sommes discr\`etes (Gosper et Zeilberger), factorisation 
(lll et knapsack), syst\`emes d'\'equations polynomiales (Grobner: F4), 
d'in\'equations (\`a commencer par le cas 1-dimensionnel).
\end{itemize}
Le dernier item requiert des comp\'etences \`a la fois en math\'ematique
et en programmation.

Les autres librairies math\'ematiques interfaçable avec Giac que j'ai examin\'ees:
\begin{itemize}
\item GiNaC: en fait j'ai travaill\'e avec GiNaC en 2000 mais j'ai
finalement d\'ecid\'e de cr\'eer mes propres types. GiNaC est \`a mon avis
trop rigide par une application trop stricte de l'encapsulation des
donn\'ees et trop orient\'e programmation objet. De plus il utilise
une classe interm\'ediaire (CLN) pour les scalaires num\'eriques ce
qui d'une part ajoute une couche de complexit\'e mais p\'enalise \'egalement
au niveau performance. A mon sens il faut \'ecrire des fonctions
de conversion \verb|GiNaC::ex <-> giac::gen| d\`es que la version
1 de GiNaC sera disponible pour permettre d'appeler les fonctions
utiles en physique th\'eorique depuis giac et inversement.
\item NTL: comme pr\'ec\'edemment j'ai commenc\'e \`a travailler avec NTL
pour la factorisation de polyn\^omes mais j'ai arr\^et\'e fin 2000,
une des raisons est que NTL est incompatible avec la Standard Template
Library (sauf \`a faire des contorsions tr\`es compliqu\'ees...)
\end{itemize}
Il en existe d'autres potentiellement int\'eressantes que je n'ai pas
encore examin\'ees en d\'etails (jacal, zen, ...)

En ce qui concerne les interfaces: il peut et devrait s'en d\'evelopper
plusieurs (on peut imaginer des interfaces de type langage de script 
comme xmaxima, de type navigateur, pour KDE/Qt, pour Gnome/GTK, \`a
l'int\'erieur d'un traitement de texte TeXmacs ou lyx ou ..., etc.).
Il faudra imaginer un abstraction des types graphiques manipul\'es
(point, courbes repr\'esentatives, etc.) qui puisse s'adapter \`a
diff\'erents toolkits graphiques. Il est pour l'instant essentiel
d'avoir une interface compatible avec les projets de PDA sous
Linux (qui utilisent en particulier la distribution Familiar avec
XWindows ou son remplacement Microwindows)

\section{Projet de d\'eveloppement collaboratif}
D'ici la fin de l'ann\'ee 2001, j'esp\`ere pouvoir ouvrir Giac au
d\'eveloppement collaboratif en compl\'etant la documentation et en
travaillant sur la conformit\'e du code aux standards. Il faudra
ensuite ouvrir une base CVS, je pense (bien que le projet soit
en C++ et pas en C) qu'on pourrait discuter avec
\verb|www.savannah.org| le site de d\'eveloppement de projets de la FSF.

Ensuite il faut s'interroger sur la suite du projet:
\begin{itemize}
\item financement. Le financement public peut se faire par d\'eplacement
de masses budg\'etaires (achat de licence) pour le support et la
formation, mais aussi par la reconnaissance scientifique des activit\'es 
de d'impl\'ementation de logiciels libres. Le financement priv\'e de
logiciels libres peut se faire par la vente de services aux
constructeurs de hardware ou aux \'editeurs de contenus p\'edagogiques 
utilisant le logiciel (correction de
bogues, support de 2\`eme niveau, d\'eveloppement \`a façon). Pour r\'eussir,
il faut avoir une strat\'egie ``commerciale'' sur l'utilisation du
logiciel dans l'enseignement math\'ematique (voir plus loin)
\item coordination: il suffit \`a mon avis de suivre l'exemple des
autres logiciels libres. En particulier il n'y a aucun inconv\'enient
\`a avoir un d\'eveloppement d\'ecentralis\'e pourvu que des rencontres
entre les d\'eveloppeurs (sous forme de journ\'ees par exemple) puissent
avoir lieu r\'eguli\`erement. Il me parait toutefois important que 
les personnes impl\'ementant des algorithmes math\'ematiques soient
\`a proximit\'e d'une \'equipe de recherche en calcul formel. Un
(enseignant-)chercheur dirige le projet.
\item Interface. Le d\'eveloppement d'interfaces intuitives requiert
\`a mon avis soit des contractants ext\'erieurs soit un poste de
d\'eveloppeur. Vu la rigidit\'e des grilles salariales de la fonction publique,
il est probablement pr\'ef\'erable d'utiliser des contractants
ext\'erieurs pour \^etre au niveau.
\item support technique: une fois la version 1 du logiciel publique,
il faut une personne pour cela. Son travail consiste \`a g\'erer l'archive
CVS, la liste de bugs par version, les
listes de discussions (giac-devel, giac-bugs, giac-general,...). Elle g\`ere
la r\'eception des bugs, les v\'erifie, indique \`a l'envoyeur ceux qui 
ont \'et\'e
corrig\'es et effectue une premi\`ere r\'epartition des bugs par d\'eveloppeur.
Si on envisage un financement priv\'e, il faut assurer le support technique
de 2\`eme niveau et les relations vis-\`a-vis des entreprises utilisant 
le logiciel ce qui
peut n\'ecessiter en fonction du succ\`es un 2\`eme poste.
\item formation. Il faut pr\'evoir la r\'edaction de documents mais
aussi de formation ``en pr\'esentiel'' (IUFM, profs de CGPE).
\end{itemize}

Je termine par mon opinion sur la strat\'egie \`a d\'evelopper pour obtenir
des financements priv\'es sans d\'eroger au principe du logiciel libre.
Actuellement le march\'e \'educatif math\'ematique est domin\'e par quelques 
acteurs: 
les calculatrices graphiques (avec la consitution \`a br\`eve \'ech\'eance 
d'un monopole de Texas Instruments comme c'est le cas aux \'Etats-Unis), les
logiciels Maple, Cabri G\'eom\`etre et Sketchpad et les \'editeurs de 
manuels (qui de plus en plus lient leur manuels à ces logiciels).
Si l'on veut r\'eussir un projet de logiciel libre de calcul formel
il doit \^etre utilis\'e d\`es le lyc\'ee sinon il sera cantonn\'e \`a
la recherche et son financement serait fragilis\'e. 
Il faut donc \^etre pr\'esent sur les 3 segments \`a la fois. L'avenir
de la calculatrice graphique est je pense un engin hybride
entre le t\'el\'ephone portable et l'assisant num\'erique type Pocket PC
(PDA avec stylet). Il faut donc avoir un logiciel tournant sur
ce type de plateforme (il y a donc contraintes de taille du programme et
de vitesse d'ex\'ecution au moins comparable \`a Maple dans les situations
rencontr\'ees en enseignement) 
et proposant du calcul formel et de la g\'eom\'etrie
dynamique (j'ai appris hier que Cabri-G\'eom\`etre se lancerait dans
un projet d'int\'egration de calcul formel). Il faut essayer rapidement
de convaincre des constructeurs concurrents de TI (Casio, Sharp,
HP/Compaq) qu'il y a un march\'e qu'ils peuvent conqu\'erir. Il faut
faire vite, la pr\'evalence des calculatrices de type actuel ne va
probablement pas durer plus de 2-3 ans, le temps pour les
PDA d'atteindre un prix inf\'erieur \`a 1000F. Faute de quoi, le
logiciel de calcul formel utilis\'e dans l'enseignement sera un logiciel 
propri\'etaire pour encore pas mal d'ann\'ees.

\end{document}