2 Interface utilisateur
2.1 Choix d'implémentation
SPPoC est une bibliothèque pour le langage Objective Caml [20].
Celle-ci est en fait constituée d'un module qui regroupe plusieurs
sous-modules donnant accès à ses différentes fonctionnalités.
Nous avons choisi le langage Objective Caml pour ses capacités de traitement
de structures de données complexes et symboliques, son expressivité et
sa possibilité d'interfaçage direct avec le langage C, utilisé pour
l'implémentation de PIP et de la PolyLib , l'Omega Library étant écrite
en C++. Le code représente au final environ 9000 lignes de code Objective Caml et 6000 lignes de code C.
Pour une utilisation facile, il faut un moyen de décrire les données
manipulées avec une syntaxe humainement lisible. Nous avons utilisé le
préprocesseur camlp4 [9] pour construire des <<
quotations >>. Il s'agit de chaînes de caractères entre <:s<
et >> où s est un sélecteur qui indique le type de la
quotation. D'autre part, un ensemble d'imprimeurs a été défini qui
permet un affichage automatique << en clair >> des structures de
données symboliques.
Bien que SPPoC ait été conçu comme une bibliothèque destinée à être
intégrée à des outils tels que des compilateurs, il peut aussi être
utilisé comme une calculatrice. En effet, grâce à l'utilisation
d'Objective Caml comme langage de programmation, la construction d'un
système interactif pour SPPoC a été quasi immédiate : Objective Caml dispose
d'une boucle interactive de compilation, évaluation, impression du
résultat. Chaque commande tapée au clavier est typée, compilée puis
exécutée. Il suffit de lier la bibliothèque contenant le module
SPPoC avec ce système interactif et toutes les fonctions de
la bibliothèque deviennent accessibles.
Nous présentons ci-dessous dans un premier temps la structure des
modules composant la bibliothèque puis comment utiliser SPPoC de
façon interactive en ligne de commande.
2.2 Interface de programmation
Le module SPPoC propose un ensemble de types abstraits
(chacun représenté par un module distinct) qui permettent les
manipulations de calcul symbolique. Les principaux types abstraits
sont :
-
les formes affines (module Form) ;
- les expressions arithmétiques générales (module Expr) ;
- les (in)équations affines (module Ineq) ;
- les QUAST (QUasi Affine Selection Tree) (module
Quast) ;
- les QUAST étendus (module Equast), qui sont des QUAST
dans lesquels on peut avoir des variables qui représentent des
restes de divisions euclidiennes d'une forme linéaire par un entier.
On définit ensuite le module PIP qui permet la résolution de
problèmes de programmation linéaire paramétrée (par l'appel à PIP ).
Ces problèmes sont caractérisés par un système d'inéquations affines
et par une question (module Question). La solution d'un tel
problème est donnée sous la forme d'un QUAST étendu.
Le module Polyhedron implante toutes les fonctions de la
PolyLib et le module Presburger implante certaines fonctions
de l'Omega Library .
Tous les modules définis ici, sauf le module PIP représentent
des types abstraits et sont construits selon le même schéma : un type
abstrait t, des constructeurs, des destructeurs, éventuellement
des opérateurs sur ce type, et des fonctions d'entrée-sortie : un
constructeur à partir d'une chaîne de caractères, read, à base
d'une grammaire gérée par camlp4 et un imprimeur, print.
2.3 Utilisation interactive
Les apports particuliers pour une utilisation interactive de SPPoC sont d'une part les mécanismes d'entrées-sorties (quotations et
imprimeurs) et la présence d'une fonction help documentant
chaque module. Les différentes quotations définies sont décrites dans
la table 1.
| donnée |
type |
exemples |
| liste de variables |
string list |
<:v<a,a',a''>> <:v<{i;j;k;l}>> |
| forme affine |
Form.t |
<:f<7+4*i-j+3*(i+j-k)>> |
| expression |
Expr.t |
<:e<(3i-k^x+n) div (2p) |
| |
|
- (3j-k-m) % q>> |
| (in)équation |
Ineq.t |
<:i<2*i-(j div 3)<n*m>> |
| |
|
<:i<i=j>> <:i<0<=2*k>> |
| système |
System.t |
<:s<2i+j=n, 0<=i<=n, j<=n, j<i>> |
| |
|
<:s<{1<=i1<=n, 1<=j1<=n, |
| |
|
i1=j1, j1%8=k1%8}>> |
| |
|
<:s<[a+b<c<=2*a; a>=0]>> |
| fonction |
Function.t |
<:fct<x;y <- 2*i % p, i^(p%2)>> |
| |
|
<:fct<[p;q] <- {i+j, n-i-j}>> |
| rayons |
Rays.t |
<:r<{line(3*i-2*j), ray(-j), |
| |
|
vertex((35*j+12*k)/21)}>> |
Table 1: Quotations disponibles dans SPPoC
Leur syntaxe est très permissive. En effet, l'utilisateur peut séparer
une liste d'objets en utilisant une virgule ou un point-virgule, il
peut les encadrer par des délimiteurs optionnels (accolades ou
crochets), ce qui permet des notation ensemblistes (accolades et
points-virgules), de style listes Caml (crochets et points-virgules)
ou libre (pas de délimiteurs et virgules). Certains opérateurs
arithmétiques ont plusieurs notations, par exemple le modulo
(mod ou %) ou l'élévation à une puissance**). Le but de cette permissivité est la facilité
d'utilisation. L'utilisateur doit se concentrer sur son problème et
non sur la syntaxe à employer.
Dans toute la suite de l'article, nous illustrons les fonctionnalités
de SPPoC par des exemples. Ceux-ci sont des extraits de sessions
d'utilisation de l'outil interactif, ils sont présentés comme
ci-dessous :
# let d = <:s< 1<=i<=n, 1<=j<=i >>;;
val d : SPPoC.System.t = i >= 1, i <= n, j >= 1, i >= j
# Polyhedron.of_system d;;
- : SPPoC.Polyhedron.t =
{({i >= j, j >= 1, i <= n},
{vertex(i+j+n), ray(n), ray(i+n), ray(i+j+n)})}
Le caractère # est le message d'invite du système interactif,
chaque phrase tapée par l'utilisateur est imprimée en italique et
terminée par ;;. La réponse du système se décompose en 3 parties
:
-
avant les :, le mot clé val suivit du nom de la
valeur définie par une construction du style << let nom
= valeur >> ou - s'il s'agit d'une simple évaluation
sans nommage ;
- entre les : et le signe =, le type de l'expression
résultant de l'évaluation de la phrase de l'utilisateur (inféré par
le système de typage d'Objective Caml ) ;
- après le signe =, la valeur telle qu'affichée par
l'imprimeur associé à son type.