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 __ ¹

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é!