Chapitre 7 Modularité
Jusqu'à présent, nous n'avons vu que l'écriture de petits programmes
ou de procédures suffisant pour apprendre les structures de données et
les algorithmes correspondants. La partie la plus importante de
l'écriture des vrais programmes consiste à les structurer pour les
présenter comme un assemblage de briques qui s'emboitent
naturellement. Ce problème, qui peut apparaître comme purement
esthétique, se révèle fondamental dès que la taille des programmes
devient conséquente. En effet, si on ne prend pas garde au bon
découpage des programmes en modules indépendants, on se retrouve
rapidement débordé par un grand nombre de variables ou de fonctions,
et il devient quasiment impossible de réaliser un programme correct.
Dans ce chapitre, il sera question de modules, d'interfaces, de
compilation séparée et de reconstruction incrémentale de programmes.
Figure 7.1 : File de caractères
7.1 Un exemple: les files de caractères
Pour illustrer notre chapitre, nous utilisons un exemple réel tiré du
noyau du système Unix. Les files ont été décrites dans le chapitre 3
sur les structures de données élémentaires. Nous avons vu deux
manières de les implémenter: par un tableau circulaire ou par une
liste. Les files de caractères sont très couramment utilisées, par
exemple pour gérer les entrées/sorties d'un terminal (tty
driver) ou du réseau Ethernet.
La représentation des files de caractères par des listes chaînées est
coûteuse en espace mémoire. En effet, si un pointeur est représenté
par une mémoire de 4 ou 8 octets (adresse mémoire sur 32 ou 64 bits),
il faut 5 ou 9 octets par élément de la file, et donc 5N ou 9N
octets pour une file de N caractères! C'est beaucoup. La
représentation par tableau circulaire semble donc meilleure du point
de vue de l'occupation mémoire. Toutefois, elle est plus statique
puisque, pour chaque file, il faut réserver à l'avance la place
nécessaire pour le tableau circulaire.
Introduisons une troisième réalisation possible de ces files. Au lieu
de représenter la file par une liste de tous les caractères la
constituant, nous allons regrouper les caractères par blocs contigus
de t caractères. Les premier et dernier éléments de la liste
pourront être incomplets (comme indiqué dans la figure
7.1). Ainsi, si t=12, une file de N caractères
utilise environ (4+t) × N/t octets pour des adresses sur 32
bits, ce qui fait un incrément tout à fait acceptable de 1/3 d'octet
par caractère. (En Java, on peut être amené à doubler la taille de
chaque bloc, puisque les caractères prennent deux octets).
Une file de caractères sera alors décrite par un objet donnant le
nombre d'éléments de la file, les bases et déplacements des premiers
et derniers caractères de la file dans les premiers et derniers blocs
les contenant. Par base et déplacement d'un caractère, nous entendons
une référence vers un bloc de la liste contenant le caractère et son
adresse relative dans ce bloc comme indiqué sur la figure
7.2. La déclaration de la classe FC
d'une
file de caractères s'effectue comme suit:
class FC {
int cc;
Bloc debut_b, fin_b;
int debut_d, fin_d;
FC () {
cc = 0;
}
static class Bloc {
final static int TAILLE = 12;
Bloc suivant;
char [] contenu;
Bloc () {
suivant = null;
contenu = new char[TAILLE];
}
}
}
La file vide est représentée par un compte de caractères
nul.
Figure 7.2 : Adresse d'un caractère par base et déplacement
static FC vide () {
return new FC();
}
L'ajout et la suppression d'un caractère dans une file
s'effectuent comme au chapitre 3. Pour respecter la structure des
blocs, il faut tester si le caractère suivant est dans le même bloc ou
s'il est nécessaire d'aller chercher le bloc suivant dans la liste des
blocs. Lors de l'ajout, il faut allouer un nouveau bloc dans le cas de
la file vide ou du franchissement d'un bloc.
static FC ajouter (char c, FC x) {
Bloc b;
if (x.cc == 0) {
b = new Bloc();
x.debut_b = b; x.debut_d = 0;
x.fin_b = b; x.fin_d = -1;
} else if (x.fin_d == Bloc.TAILLE - 1) {
b = new Bloc();
x.fin_b.suivant = b;
x.fin_b = b; x.fin_d = -1;
}
x.fin_b.contenu[++x.fin_d] = c;
++x.cc;
return x;
}
La suppression s'effectue au début de file. Pour la
suppression, il faut au contraire rendre un bloc si le caractère
supprimé (rendu en résultat) libère un bloc. Par convention, nous
retournons le caractère nul quand on demande de supprimer un caractère
dans une file vide. Une meilleure solution aurait été de retourner une
exception.
static char supprimer (FC x) {
char res;
if (x.cc == 0)
return -1;
else {
res = x.debut_b.contenu[x.debut_d];
--x.cc;
++x.debut_d;
if (x.debut_d >= Bloc.TAILLE) {
x.debut_b = x.debut_b.suivant;
x.debut_d = 0;
}
return res;
}
}
7.2 Interfaces et modules
Reprenons l'exemple précédent. Supposons qu'un programme, comme un
gestionnaire de terminaux, utilise des files de caractères, une pour
chaque terminal. On ne doit pas mélanger la gestion des files de
caractères avec le reste de la logique du programme. Il faut donc
regrouper les procédures traitant des files de caractères. Le
programme utilisant les files de caractères n'a pas besoin de
connaître tous les détails de l'implémentation de ces files. Il ne
doit connaître que la déclaration des types utiles dans la classe
FC
: le nom de la classe et les trois procédures pour
initialiser une file vide, ajouter un élément au bout de la file et
retirer le premier élément. Précisément, on peut se contenter de
l'interface suivante:
class FC {
static FC vide () {...}
/* Retourne une file vide */
static FC ajouter (char c, FC x) {...}
/* Ajoute c
au bout de la file x
*/
static int supprimer (FC x) {...}
/* Supprime le premier caractère c de x
et rend c comme résultat */
/* Si x
est vide, le résultat est -1 */
On ne manipulera les files de caractères qu'à travers cette
interface. Pas question de connaître la structure interne de ces
files. Ni de savoir si elles sont organisées par de simples listes,
des tableaux circulaires ou des blocs enchaînés. On dira que le
programme utilisant des files de caractères à travers l'interface
précédente importe cette interface. Le corps des procédures sur
les files seront dans la partie implémentation du module
des files de caractères. Dans l'interface d'un module, on a donc des
types, des procédures ou des fonctions que l'on veut exporter ou
rendre publiques, et il est bon d'y commenter la fonctionnalité de
chaque élément pour comprendre sa signification, puisqu'un utilisateur
n'aura besoin que de consulter l'interface. Dans un module, il y a
donc toute une partie cachée comprenant les types et les corps
des procédures ou des fonctions que l'on veut rendre privées. C'est
ce qu'on appelle le principe d'encapsulation.
Comment y arriver en Java? Le plus simple est de se servir des
modificateurs d'accès dans la déclaration des variables ou des
méthodes de la classe FC
. Le qualificatif private
signifie que seuls les instructions à l'intérieur de la classe où il
est définie pourront accéder à ce champ ou méthode. Au contraire
public
dit qu'un champ est accessible par toutes les
classes. Jusqu'à présent, nous n'avons pas mis (sauf pour la procédure
main
) de qualificatifs. L'option par défaut est de rendre
public les champs (en fait à l'intérieur du package où il est
défini, mais nous verrons plus loin la notion de package).
Redéfinissons donc notre classe FC
.
class FC {
private int cc;
private Bloc debut_b, fin_b;
private int debut_d, fin_d;
public FC () {
cc = 0;
}
private static class Bloc {
final static int TAILLE = 12;
Bloc suivant;
char [] contenu;
Bloc () {
suivant = null;
contenu = new char[TAILLE];
}
}
public static FC vide () {
return new FC();
}
public static FC ajouter (char c, FC x) {
Bloc b;
if (x.cc == 0) {
b = new Bloc();
x.debut_b = b; x.debut_d = 0;
x.fin_b = b; x.fin_d = -1;
} else if (x.fin_d == Bloc.TAILLE - 1) {
b = new Bloc();
x.fin_b.suivant = b;
x.fin_b = b; x.fin_d = -1;
}
x.fin_b.contenu[++x.fin_d] = c;
++x.cc;
return x;
}
public static char supprimer (FC x) {
char res;
if (x.cc == 0)
return -1;
else {
res = x.debut_b.contenu[x.debut_d];
--x.cc;
++x.debut_d;
if (x.debut_d >= Bloc.TAILLE) {
x.debut_b = x.debut_b.suivant;
x.debut_d = 0;
}
return res;
}
}
}
On peut avoir à cacher non seulement le code des procédures réalisant
l'interface, mais aussi des variables et des fonctions qui ne seront
pas accessibles de l'extérieur. Supposons dans notre exemple, que,
pour être hyper efficace (ce qui peut être le cas dans un driver
de périphérique), nous voulions avoir notre propre stratégie
d'allocation pour les blocs. On construira une liste des blocs libres
listeLibre
à l'initialisation du chargement de la classe
FC
et on utilisera les procédures nouveauBloc
et
libererBloc
comme suit:
class FC {
private int cc;
private Bloc debut_b, fin_b;
private int debut_d, fin_d;
public FC () {
cc = 0;
}
private static class Bloc {
final static int TAILLE = 12;
Bloc suivant;
char [] contenu;
Bloc () {
suivant = null;
contenu = new char[TAILLE];
}
}
public static FC vide () {
return new FC();
}
public static FC ajouter (char c, FC x) {
Bloc b;
if (x.cc == 0) {
b = nouveauBloc();
x.debut_b = b; x.debut_d = 0;
x.fin_b = b; x.fin_d = -1;
} else if (x.fin_d == Bloc.TAILLE - 1) {
b = nouveauBloc();
x.fin_b.suivant = b;
x.fin_b = b; x.fin_d = -1;
}
x.fin_b.contenu[++x.fin_d] = c;
++x.cc;
return x;
}
public static int supprimer (FC x) {
if (x.cc == 0)
return -1;
else {
char res = x.debut_b.contenu[x.debut_d];
--x.cc;
++x.debut_d;
if (x.cc <= 0)
libererBloc (x.debut_b);
else if (x.debut_d >= Bloc.TAILLE) {
Bloc b = x.debut_b;
x.debut_b = x.debut_b.suivant;
x.debut_d = 0;
libererBloc (b);
}
return res;
}
}
private final static int NB_BLOCS = 1000;
private static Bloc listeLibre;
static {
listeLibre = null;
for (int i=0; i < NB_BLOCS; ++i) {
Bloc b = new Bloc();
b.suivant = listeLibre;
listeLibre = b;
}
}
private static Bloc nouveauBloc () {
Bloc b = listeLibre;
listeLibre = listeLibre.suivant;
b.suivant = null;
return b;
}
private static void libererBloc (Bloc b) {
b.suivant = listeLibre;
listeLibre = b;
}
}
On veut que la variable listeLibre
reste cachée,
puisque cette variable n'a aucun sens dans l'interface des files de
caractères. Il en est de même pour les procédures d'allocation ou de
libération des blocs. Faisons trois remarques. Premièrement, il est
fréquent qu'un module nécessite une procédure d'initialisation. En
Java, on le fait en mettant quelques instructions dans la déclaration
de la classe (qui ne sont exécutées qu'une seule fois, au chargement
de la classe si le mot-clé static
figure devant).
Deuxièmement, pour ne pas compliquer le programme, nous ne testons pas
le cas où la liste des blocs libres devient vide et, donc,
l'allocation d'un nouveau bloc libre impossible. Troisièmement, on un
créerait un nouveau module séparé pour l'allocation des blocs, si les
procédures d'allocation et de libération de blocs étaient très
complexes. Alors le module des files de caractères serait lui aussi
constitué par plusieurs modules. Essayer de le faire en exercice.
Pour résumer, un module contient deux parties: une interface exportée
qui contient les constantes, les types, les variables et la signature
des fonctions ou procédures que l'on veut rendre publiques, une partie
implémentation qui contient la réalisation des objets de l'interface.
L'interface est la seule porte ouverte vers l'extérieur. Dans la
partie implémentation, on peut utiliser tout l'arsenal possible de la
programmation. On ne veut pas que cette partie soit connue de son
utilisateur pour éviter une programmation trop alambiquée. Si on
arrive à ne laisser public que le strict nécessaire pour utiliser un
module, on aura grandement simplifié la structure d'un programme. Il
faut donc bien faire attention aux interfaces, car une bonne partie de
la difficulté d'écrire un programme réside dans le bon choix des
interfaces.
Découper un programme en modules permet aussi la réutilisation des
modules, la construction hiérarchique des programmes puisqu'un module
peut lui-même être aussi composé de plusieurs modules, le
développement indépendant de programmes par plusieurs personnes dans
un même projet de programmation. Il facilite les modifications, si les
interfaces restent inchangées. Ici, nous insistons sur la
structuration des programmes, car tout le reste n'est que corollaire.
Tout le problème de la modularité se résume à isoler des parties de
programme comme des boîtes noires, dont les seules parties visibles à
l'extérieur sont les interfaces. Bien définir un module assure la
sécurité dans l'accès aux variables ou aux procédures, et est un bon
moyen de structurer la logique d'un programme. Une deuxième partie de
la programmation consiste à assembler les modules de façon claire.
7.3 Interfaces et modules en Java
Beaucoup de langages de programmation ont une notion explicite de
modules et d'interfaces, par exemple Clu, Mesa, Ada, Modula-2, Oberon,
Modula-3, et ML. En C ou C++, on utilise les fichiers include
pour simuler les interfaces des modules, en faisant coïncider les
notions de module et de compilation séparée.
En Java, la notion de modularité est plus dynamique et reportée dans
le langage de programmation avec les modificateurs d'accès. Il n'y a
pas de phase d'éditions de liens permettant de faire coincider
interfaces et implémentations. Seul le chargeur dynamique
ClassLoader
ou l'interpréteur (la machine virtuelle Java) font
quelques vérifications. Il existe une notion d'interfaces avec le
mot-clé Interface
et de classes implémentant ces interfaces,
mais ces notions sont plutôt réservés pour la construction de classes
paramétrées ou pour la gestion dynamique simultanée de plusieurs
implémentations pour un même interface.
Mais il existe une autre notion pour assurer la modularité en se
servant de la restriction dans l'espace des noms. Nous avons vu que
pour accéder à des variables ou à des fonctions, on pouvait avoir à
qualifier les noms par le nom de la classe (ou d'un objet pour les
méthodes dynamiques). Ainsi on écrit Liste.ajouter
,
FC.TAILLE
, args.length()
, System.out.print
dans
les exemples précédents. Parmi ces préfixes, System
est un nom
de package. Un package permet de regrouper un ensemble de
classes qui ont des fonctionalités proches, par exemple les appels
système, les entrées/sorties, etc. Un package correspond à un
répertoire du système de fichiers, dont les classes sont des
fichiers. Par défaut, une classe fait toujours partie d'un package, par défaut le répertoire dont le fichier contenant la classe
fait partie. On peut spécifier le package où se trouve une classe en
la précédent par l'instruction
package Nom_de_package;
Pour accéder à une classe, on doit la précéder par le nom du package dont elle fait partie. Mais, on peut éviter de mettre le nom
complet en donnant la liste des noms de packages importés.
import java.io.*;
import java.lang.*;
import java.util.*;
7.4 Compilation séparée et librairies
La compilation d'un programme consiste à fabriquer le binaire
exécutable par le processeur de la machine. Pour des programmes de
plusieurs milliers de lignes, il est bon de les découper en des
fichiers compilés séparément. En Java, le code généré est indépendant
de la machine qui l'exécute, ce qui permet de l'exécuter sur toutes
les architectures à travers le réseau. Il s'agit donc d'un code
interprété (byte-code) par un interpréteur dépendant lui de
l'architecture sous-jacente, la machine virtuelle Java (encore appelée
JVM pour en anglais Java Virtual Machine). Les fichiers de byte-code ont le suffixe .class
, les fichiers sources ayant
eux d'habitude le suffixe .java
. Pour compiler un fichier
source sous un système Unix, la commande:
% javac FC.java
permet d'obtenir le fichier byte-code FC.class
qui peut être utilisé par d'autres modules compilés
indépendamment. Supposons qu'un fichier TTY.java
contenant un
gestionnaire de terminaux utilise les fonctions sur les files de
caractères. Ce programme contiendra des lignes du genre:
class TTY {
FC in, out;
TTY () {
in = new FC();
out = new FC();
}
static int Lire (FC in) { ··· }
static void Imprimer (FC out) { ··· }
}
Figure 7.3 : Compilation séparée
En Unix, on devra compiler séparément TTY.java
et on lancera la
machine Java sur TTY.class
par les commandes:
% javac TTY.java
% java TTY
Remarquons que le suffixe .class
n'est pas nécessaire
dans la deuxième commande. La dernière commande cherche la fonction
publique main
dans la classe TTY.class
et démarre la
machine virtuelle Java sur cette fonction. Les diverses classes
utilisées sont chargées au fur et à mesure de leur
utilisation. Contrairement à beaucoup de langages de programmation, il
n'y a pas (pour le meilleur et pour le pire) de phase d'édition de
liens en Java. Tout se fait dynamiquement. Graphiquement, les phases
de compilation sont représentées par la figure
7.3.
Quand il y a un grand nombre de fichiers de code objet, on peut les
regrouper dans un fichier d'archive .jar
(java archive)
pour en faire une librairie, par exemple libX11.a
pour
X-window. Les diverses classes ou librairies sont retrouvées à des
endroits standards, que l'on peut changer en se servant de la variable
d'environnement CLASSPATH
.
Avec CodeWarrior, la notion de projet permet de combiner un
certain nombre de fichiers Java comme FC.java
et
TTY.java
, ainsi qu'un certain nombre de librairies. La commande
Run
exécute des commandes de compilation séparée et d'édition
de lien analogues à celles d'Unix.
7.5 Dépendances entre modules
Figure 7.4 : Dépendances dans une compilation séparée
Lors de l'écriture d'un programme composé de plusieurs modules, il est
commode de décrire les dépendances entre modules et la manière de
reconstruire les binaires exécutables. Ainsi on pourra recompiler le
strict nécessaire en cas de modification d'un des modules. Dans
l'exemple de notre gestionnaire de terminaux, nous voulons indiquer
que les dépendances induites par la figure
7.5 pour reconstruire le code objet
TTY.class
. La description des dépendances varie selon le
système. La commande javac
fait l'analyse de dépendances et
compile ce qui est nécessaire. De même, la commande Run ou Compile en CodeWarrior sur Mac. De manière plus générale sous le
système Unix, on utilise des Makefile et la commande make.
Supposons pour un moment notre programme écrit en C, avec un fichier
d'interface fc.h
. Le fichier de dépendances serait ainsi écrit:
tty: tty.o fc.o
cc -o tty tty.o fc.o
tty.o: tty.c fc.h
cc -c tty.c
fc.o: fc.c fc.h
cc -c fc.c
Figure 7.5 : Dépendances dans un
Makefile
Après ``:'', il y a la liste des fichiers dont dépend
le but mentionné au début de la ligne. Dans les lignes suivantes, il y
a la suite de commandes à effectuer pour obtenir le fichier but. La
commande Unix make considère le graphe des dépendances et
calcule les commandes nécessaires pour reconstituer le fichier but. Si
les interdépendances entre fichiers sont représentés par les arcs d'un
graphe dont les sommets sont les noms de fichier, cette opération
d'ordonnancement d'un graphe sans cycle s'appelle le tri
topologique.
7.6 Tri topologique
Au début de certains livres, les auteurs indiquent les dépendances
chronologiques entre les chapitres en les représentant par un
diagramme. Celui qui figure au début du livre de Barendregt sur
lambda-calcul [4] est sans doute l'un des plus
compliqués. Par exemple, on voit sur ce diagramme que pour lire le
chapitre 16, il faut avoir lu les chapitres 4, 8 et 15. Un lecteur
courageux veut lire le strict minimum pour appréhender le chapitre 21.
Il faut donc qu'il transforme l'ordre partiel indiqué par les
dépendances du diagramme en un ordre total déterminant la liste des
chapitres nécessaires au chapitre 21. Bien sûr, ceci n'est pas
possible si le graphe de dépendance contient un cycle. L'opération qui
consiste à mettre ainsi en ordre les noeuds d'un graphe dirigé sans
circuit (souvent appelés sous leur dénomination anglaise dags
pour directed acyclic graphs) est appelée le tri topologique.
Comme nous l'avons vu plus haut, elle est aussi bien utile dans la
compilation et l'édition de liens des modules
Figure 7.6 : Un exemple de graphe acyclique
Le tri topologique consiste donc à ordonner les sommets d'un dag en
une suite dans laquelle l'origine de chaque arc apparait avant son
extrémité. La construction faite ici est une version particulière du
tri topologique, il s'agit pour un sommet s donné de construire une
liste formée de tous les sommets origines d'un chemin d'extrémité s.
Cette liste doit en plus satisfaire la condition énoncée plus haut.
Pour résoudre ce problème, on applique l'algorithme de descente en
profondeur d'abord (Trémaux) sur le graphe opposé. (Au lieu de
considérer les successeurs succ[u,k]
du sommet u, on
parcourt ses prédécesseurs.) Au cours de cette recherche, quand on a
fini de visiter un sommet, on le met en tête de liste. En fin de
l'algorithme, on calcule l'image mirroir de la liste. Pour tester
l'existence de cycles, on doit vérifier lorsqu'on rencontre un noeud
déjà visité que celui-ci figure dans la liste résultat. Pour ce faire,
il faut utiliser un tableau annexe etat
sur les noeuds qui
indique si le noeud est visité, en cours de visite, ou non visité.
final static pasVu = 0, enCours = 1, dejaVu = 2;
static Liste triTopologique (int u) {
for (int i = 0; i < nbSommets; ++i)
etat[i] = pasVu;
Liste resultat = Liste.reverse (DFS (u, null));
}
static Liste DFS (int u, Liste a_faire) {
for (int k = 0; pred[u][k] != Omega; ++k) {
int v = pred[u][k];
if (etat[v] == enCours)
Erreur ("Le graphe a un cycle");
if (etat[v] == pasVu) {
etat[v] = enCours;
a_faire = DFS (v, a_faire);
}
}
etat[u] = dejaVu;
return Liste.ajouter (u, a_faire);
}
Nous avons omis les déclarations des variables i
et
etat
et du type énuméré des éléments de ce tableau. Nous avons
repris les structures développées dans les chapitres sur les graphes
et les fonctions sur les listes. Nous supposons aussi que le tableau
succ
est remplacé par pred
des prédécesseurs de chaque
noeud.
7.7 Un exemple de module en C
C est proche de Java par sa non-existence d'un système de modules.
Nous reprenons l'exemple des files de caractères (en fait telles
qu'elles se trouvaient en Unix version 7 pour les gestionaires de
terminaux). C'est aussi l'occasion de constater comment la
programmation en C permet certaines acrobaties, peu recommandables car
on aurait pu suivre la technique d'adressage des caractères dans les
blocs comme en Java. La structure des files est légèrement différente
car on adresse directement les caractères dans un bloc au lieu du
système base et déplacement de Pascal. Le débordement de bloc est
testé en regardant si on est sur un multiple de la taille d'un bloc,
car on suppose le tableau des blocs aligné sur un multiple de cette
taille. Le fichier interface fc.h
est
#define NCLIST 80 /* max total clist size */
#define CBSIZE 12 /* number of chars in a clist block */
#define CROUND 0xf /* clist rounding: sizeof(int *) + CBSIZE - 1
*/
/*
* A clist structure is the head
* of a linked list queue of characters.
* The characters are stored in 4-word
* blocks containing a link and several characters.
* The routines fc\_get
and fc\_put
* manipulate these structures.
*/
struct clist
{
int c_cc; /* character count */
char *c_cf; /* pointer to first char */
char *c_cl; /* pointer to last char */
};
struct cblock {
struct cblock *c_next;
char c_info[CBSIZE];
};
typedef struct clist *fc_type;
int fc_put(char c, fc_type p);
int fc_get(fc_type p);
void fc_init(void);
Dans la partie implémentation qui suit, on remarque l'emploi
de la directive static
(celle de C, et non de Java!) qui permet
de cacher à l'édition de liens des variables, procédures ou fonctions
privées qui ne seront pas considérées comme externes. Contrairement à
Pascal, il est possible en C de cacher la représentation des files, en
ne déclarant le type fc_type
que comme un pointeur vers une
structure clist
non définie. Les fonctions retournent un
résultat entier qui permet de retourner des valeurs erronées comme
-1. Le fichier fc.c
est
#include <stdlib.h>
#include <fc.h>
static struct cblock cfree[NCLIST];
static struct cblock *cfreelist;
int fc_put(char c, fc_type p)
{
struct cblock *bp;
char *cp;
register s;
if ((cp = p->c_cl) == NULL || p->c_cc < 0 ) {
if ((bp = cfreelist) == NULL)
return(-1);
cfreelist = bp->c_next;
bp->c_next = NULL;
p->c_cf = cp = bp->c_info;
} else if (((int)cp & CROUND) == 0) {
bp = (struct cblock *)cp - 1;
if ((bp->c_next = cfreelist) == NULL)
return(-1);
bp = bp->c_next;
cfreelist = bp->c_next;
bp->c_next = NULL;
cp = bp->c_info;
}
*cp++ = c;
p->c_cc++;
p->c_cl = cp;
return(0);
}
int fc_get(fc_type p)
{
struct cblock *bp;
int c, s;
if (p->c_cc <= 0) {
c = -1;
p->c_cc = 0;
p->c_cf = p->c_cl = NULL;
} else {
c = *p->c_cf++ & 0xff;
if (--p->c_cc<=0) {
bp = (struct cblock *)(p->c_cf-1);
bp = (struct cblock *) ((int)bp & ~CROUND);
p->c_cf = p->c_cl = NULL;
bp->c_next = cfreelist;
cfreelist = bp;
} else if (((int)p->c_cf & CROUND) == 0){
bp = (struct cblock *)(p->c_cf-1);
p->c_cf = bp->c_next->c_info;
bp->c_next = cfreelist;
cfreelist = bp;
}
}
return(c);
}
void fc_init()
{
int ccp;
struct cblock *cp;
ccp = (int)cfree;
ccp = (ccp+CROUND) & ~CROUND;
for(cp=(struct cblock *)ccp; cp <= &cfree[NCLIST-1]; cp++) {
cp->c_next = cfreelist;
cfreelist = cp;
}
}
7.8 Modules en Caml
On construit pour tout module deux fichiers fc.mli
(pour ML
interface) et fc.ml
(le module d'implémentation). Le premier est un
fichier d'interface dans lequel on donne la signature de tous les types,
variables ou fonctions exportées. Par exemple:
(* Files de caractères *)
type fc;;
(* Le type des files de caractères *)
exception FileVide;;
(* Levée quand [supprimer] est appliquée à une file vide. *)
value vide: unit -> fc
(* Retourne une nouvelle file, initialement vide. *)
and ajouter: char -> fc -> fc
(* [ajouter c x] ajoute le caractère [c] à la fin de la file [x]. *)
and supprimer: fc -> char
(* [supprimer x] enlève et retourne le premier élément de la file [x]
ou lève l'exception [FileVide] si la queue est vide. *)
Le deuxième contient l'implémentation des files de
caractères, où on fournit les structures de données ou le code
correspondant à chaque déclaration précédente:
type fc = {mutable cc: int;
mutable debut_b: liste_de_blocs; mutable debut_d: int;
mutable fin_b: liste_de_blocs; mutable fin_d: int} and
liste_de_blocs = Nil | Cons of bloc and
bloc = {contenu: string; mutable suivant: liste_de_blocs};;
exception FileVide;;
let taille_bloc = 12;;
let vide() = {cc = 0; debut_b = Nil; debut_d = 0; fin_b = Nil; fin_d = 0};;
let ajouter c x =
let nouveau_bloc() =
Cons {contenu = make_string taille_bloc ` `; suivant = Nil} in
if x.cc = 0 then begin
let b = nouveau_bloc() in
x.debut_b <- b; x.debut_d <- 0;
x.fin_b <- b; x.fin_d <- -1;
end else if x.fin_d = taille_bloc - 1 then begin
let b = nouveau_bloc() in
(match x.fin_b with
Cons r -> r.suivant <- b
| Nil -> ()
);
x.fin_b <- b; x.fin_d <- -1;
end;
x.fin_d <- x.fin_d + 1;
(match x.fin_b with
Cons r -> r.contenu.[x.fin_d] <- c
| Nil -> ()
);
x.cc <- x.cc + 1;
x;;
let supprimer x =
if x.cc = 0 then
raise FileVide
else match x.debut_b with
Nil -> failwith "Cas impossible"
| Cons r -> let res = r.contenu.[x.debut_d] in
x.cc <- x.cc - 1;
x.debut_d <- x.debut_d + 1;
if x.debut_d >= taille_bloc then begin
x.debut_b <- r.suivant;
x.debut_d <- 0;
end;
res;;
Dans un deuxième module, par exemple un gestionnaire de
terminaux dont le code se trouve dans un fichier tty.ml
, on
peut utiliser les noms du module fc.mli
en les qualifiant par
le nom du module suivi symbole __
1
let nouveau_tty =
let x = fc__vide() in
...
let y = fc__ajouter c x ....
Si on n'a pas envie d'utiliser cette notation longue, on supprime
le préfixe avec la directive suivante en tête de tty.ml
.
#open "fc";;
Les dépendances entre modules se font comme dans le cas de C. On se sert de
la commande make
de Unix et du makefile suivant. Remarquons
que les fichiers .ml
se compilent en fichiers .zo
, les
fichiers .mli
en .zi
, et que l'on finit avec un fichier
tty
directement exécutable.
tty: tty.zo fc.zo
camlc -o tty tty.zo fc.zo
tty.zo: tty.ml fc.zi
camlc -c tty.ml
fc.zo: fc.ml
camlc -c fc.ml
fc.zi: fc.mli
camlc -c fc.mli
Figure 7.7 : Dépendances entre modules Caml
Enfin, en Caml, on n'est pas forcé de définir un fichier d'interface,
auquel cas le compilateur générera automatiquement un fichier
.zi
en supposant toutes les variables et fonctions publiques
dans le module d'implémentation. Toutefois, c'est plus sûr de définir
soi-même les fichiers d'interface.
- 1
- En OCaml, on est
revenu à une notation plus classique avec un point au lieu des deux
caractères souligné!