Les modules d'O'Caml

Objectifs :Présentation du langage O'CAML, comparaison avec le langage caml-light. Principes de programmation modulaire. Description du système de modules de O'CAML

Le langage Caml

Le langage Caml (Categorical Abstract Machine Language) est un langage de la famille ML, i.e. un langage fonctionnel typé muni de traits impératifs. Ses caractéristiques principales sont les suivantes.

Le langage Caml est :

• un langage fonctionnel :

  où les fonctions sont des valeurs du langage et peuvent donc être passées comme arguments ou retournées comme résultat de calculs;

• typé statiquement :

  le type des expressions est vérifié à la compilation, une incohérence de types rejette le programme;

• inférant le type des expressions :

  le programmeur n'a pas besoin d'indiquer le type des expressions y compris les paramètres de fonctions, le système déduira automatiquement leur type le plus général;

• polymorphe paramétrique :

  les types peuvent être paramétrés par des variables de types permettant ainsi la définition d'un traitement générique des structures de données analogues;

• acceptant la définition par cas :

  où la définition d'une fonction s'effectue par filtrage de motif sur les arguments passés;

• muni d'un mécanisme d'exceptions :

  permettant de déclencher une exception à tout moment de l'exécution, celle-ci sera alors traitée par le dernier récupérateur d'exceptions rencontré;

• de traits impératifs :

  comprenant les entrées/sorties, l'affectation et les structures de contrôle séquentielle et itérative;

• et d'un système de modules :

  permettant la réutilisation de composants logiciels;

• comprenant de nombreuses bibliothèques :

  en particulier les bibliothèques graphiques et d'analyses lexicale et syntaxique;

• et acceptant deux modes de compilation :

  l'un sous forme de boucle d'interaction permettant le développent incrémental d'applications, et l'autre en mode ligne de commande produisant des programmes exécutables autonomes et s'intégrant dans les outils de développement classiques de dépendance de fichiers et de gestion de versions.

Le langage Caml est développé à l'Inria depuis 1984 . Il est principalement utilisé dans l'enseignement, y compris comme premier langage , et la recherche. L'intérêt de son apprentissage provient principalement de son système de typage et de sa sémantique bien définie. Il existe trois dialectes du langage Caml :

• Caml (V3.1) : l'ancêtre dont l'implantation utilisait la bibliothèque d'exécution du langage Le_Lisp; on lui doit le nom actuel car son implantation était basée sur la machine CAM.
• Caml-Light :
• Objective Caml (O'Caml) :

Caml-Light a été étudiée dans le cours de Programmation et utilisé dans le cours de Compilation de la licence d'informatique de Paris 6. Pour les étudiants ne l'ayant jamais étudié, il est fortement conseillé de lire la première partie du livre de Guy Cousineau et Michel mauny : Approche Fonctionnelle de la Programmation .

O'Caml reprend le noyau fonctionnel et impératif de Caml-Light. Il lui ajoute un système de modules paramétrés, une extension objet (classes, instances, héritage, classes abstraites, classes paramétrées, héritage multiple) qui s'intègre à son système de typage. De plus un compilateur optimisant, produisant du code natif pour les principales architectures machine, permet d'obtenir de bonnes performances à l'exécution. Enfin de nouvelles bibliothèques, principalement la bibliothèque de tt threads (processus légers), permet de l'utiliser comme support d'un cours sur la concurrence.

Nous étudierons dans ce cours son système de modules.

La programmation modulaire et les modules d"O'CAML

La programmation modulaire permet le découpage d'un programme en unités logiques plus petites. Le but étant de pouvoir traiter (réaliser) un module séparément des autres modules, y compris de ceux dont il dépend. Pour cela un module possède une interface qui décrit les communications avec les objets (valeurs, types, exceptions, ...) du module. Enfin au moment de l'assemblage des différents modules les hypothèses des interfaces doivent être vérifiées. L'intérêt est donc :

• découpage logique;
• abstraction des données (spécification et réalisation);
• indépendance de l'implantation;
• réutilisation.

Il y a souvent une confusion entre programmation modulaire et compilation séparée. La compilation séparée décompose un programme en unités de compilation, compilables séparément. Les deux approches sont nécessaires pour la réalisation d'applications de grande taille. Pour ce faire, il est nécessaire que la spécification d'un module (au sens "types abstraits de données) soit vérifiable par un compilateur. Pour cela on se limitera à la vérification de types sans chercher à vérifier d'autres propriétés du module. Pour que les deux approches se rejoignent une interface sera à la fois la spécification d'un module et contiendra l'information de typage et de compilation pour les autres modules.

Le langage de modules d'O'Caml

On parlera de structure pour pour la partie réalisation/implantation et de signature pour la partie spécification/interface. Le langage de modules est indépendant du langage de base (O'Caml), bien qu'il y ait un parallèle entre (valeur : type) et structure : signature. On peut voir la signature d'un module comme son type.

modules simples

La partie implantation d'un module est une suite de définitions : de valeurs y compris fonctionnelles, de types, d'exceptions et de sous-modules.

module Liste = 
  struct 
    type 'a liste = Vide | Elt of 'a * 'a liste
    exception Liste_vide
    let nil = Vide
    let ajoute x l = Elt (x,l)
    let tete l = match l with Vide -> raise Liste_vide | Elt(t,q) -> t
    let queue l = match l with  Vide -> raise Liste_vide | Elt(t,q) -> q
    let rec longueur l = match l with Vide -> 0 | Elt(_,q) -> 1 + longueur q
  end;;

qui donne la signature suivante :

module Liste :
  sig
    type 'a liste = Vide | Elt of 'a * 'a liste
    exception Liste_vide
    val nil : 'a liste
    val ajoute : 'a -> 'a liste -> 'a liste
    val tete : 'a liste -> 'a
    val queue : 'a liste -> 'a liste
    val longueur : 'a liste -> int
  end

L'accès à un élément d'un module se fait par la notation "point".

# Liste.nil;;
- : 'a Liste.liste = Liste.Vide

qui peut être simplifié par l'ouverture du module :

# open Liste;;
# ajoute "hello" nil;;
- : string Liste.liste = Elt ("hello", Vide)

La partie interface d'un module est une suite de déclarations et de spécification de types. On utilisera la convention suivante pour nommer les structures et les signatures : une signature sera écrite en MAJUSCULE, et une structure en Minuscule dont l'initiale en majuscule.

module type LISTE = 
  sig
    type 'a liste = Vide | Elt of 'a * 'a liste
    exception Liste_vide
    val nil : 'a liste
    val ajoute : 'a -> 'a liste -> 'a liste
    val tete : 'a liste -> 'a
    val queue : 'a liste -> 'a liste
  end

Quand une signature est associée à une structure il y a vérification de la cohérence :

• les déclaration de la signature existent dans la structure
• et satisfont les spécifications de la signature.

communications entre modules

Les modules utilisent des déclarations d'autres modules, c'est ce que l'on appelle la communication entre modules. Elles peuvent être implicites, en utilisant la notation "point" et en tenant compte de l'environnement global ou explicite en utilisant des foncteurs.

de manière implicite

module Element = 
  struct 
    type t = int
  end;;

module ListeV2 = 
  struct 
    type liste = Vide | Elt of Element.t * liste 
                     (* on suppose Element connu dans l'environnement global *)
    exception Liste_vide
    let nil = Vide
    let ajoute x l = Elt (x,l)
    let tete l = match l with Vide -> raise Liste_vide | Elt(t,q) -> t
    let queue l = match l with  Vide -> raise Liste_vide | Elt(t,q) -> q
    let rec longueur l = match l with Vide -> 0 | Elt(_,q) -> 1 + longueur q
  end;;

de manière explicite : module paramétré (foncteur)

module type ELEMENT = 
  sig 
    type t 
  end;;

module ListeV3 = functor (Element : ELEMENT) -> 
  struct 
    type liste = Vide | Elt of Element.t * liste 
    exception Liste_vide
    let nil = Vide
    let ajoute x l = Elt (x,l)
    let tete l = match l with Vide -> raise Liste_vide | Elt(t,q) -> t
    let queue l = match l with  Vide -> raise Liste_vide | Elt(t,q) -> q
    let rec longueur l = match l with Vide -> 0 | Elt(_,q) -> 1 + longueur q
  end;;

et de son application :

module ListeV4 = ListeV3(Element);;

module NouvelElement = 
  struct 
    type t = float
  end;;

module ListeV5 = ListeV3(NouvelElement);;

syntaxe des modules

La déclaration d'une structure est "typecheckée", ces informations de typage produisent une signature. La coercion d'une structure par une signature utilise la syntaxe de la coercion des types. En cela le langage de module est un langage fonctionnel typé.

• valeur :

  module Nom [ : SIGNATURE ] = 
    struct 
        val ...
        type ...
        exception ...
        module ...
    end
  

• type

  module type Nom = 
    sig 
      ...
    end
  

• abstraction (valeur fonctionnelle)

  module Nom = functor ( Module : SIGNATURE) -> 
    struct 
    end
  

• application

  module Nom = Module(Structure)
  

Abstraction

Les déclarations de type dans les signatures peuvent être concrètes (la définition du type est alors visible) ou abstraite (la représentation du type n'est pas visible). Ce dernier cas permet de faire de construire des types abstraits de données (ADT).

abstraction de types

module type ELEMENT_ORD = 
  sig
    type t
    val compare : t -> t -> bool
  end
;;

module type ARBRE_BIN  = functor (Element : ELEMENT_ORD) ->  
  sig 
     type element = Element.t 
     type arbre_bin
     val arbre_vide : arbre_bin
     val ajoute : element -> arbre_bin -> arbre_bin
     val appartient : element -> arbre_bin -> bool
  end;; 

module ArbreBin = functor (Element : ELEMENT_ORD) ->  
  struct
    type element = Element.t
    type arbre_bin = Vide | Noeud of element * arbre_bin * arbre_bin
    let arbre_vide = Vide
    let rec ajoute x a = 
      match  a with 
        Vide -> Noeud (x,Vide,Vide)
      | Noeud(l,g,d) -> 
          if Element.compare x l 
          then Noeud(l,ajoute x g,d) 
          else Noeud(l,g,ajoute x d)
    let rec appartient x a = 
      match a with 
        Vide -> false
      | Noeud(l,g,d) -> 
          if x = l then true 
          else 
            if Element.compare x l 
            then appartient x g 
            else appartient x d
  end;;    

module ArbreBinAbstrait = (ArbreBin : ARBRE_BIN);;

module EntierInf  = 
  struct
    type t = int
    let compare x y = x < y
  end;;


module ArbreBinInf  = ArbreBinAbstrait(EntierInf);;

L'utilisation du module ArbreBinInf est la suivante :

#   open ArbreBinInf;;
# let a = arbre_vide;;
val a : ArbreBinInf.arbre_bin = <abstr>
# ajoute 3 a;;
- : ArbreBinInf.arbre_bin = <abstr>
# ajoute "hello" a;;
This expression has type string but is here used with type
  ArbreBinInf.element = int

L'intérêt de l'abstraction dans les modules par rapport au polymorphisme paramétrique de ML, est d'effectuer une limitation du polymorphisme (dans un but de vérification). En effet si l'on définit un nouveau module ArbreBinSup représentant les arbres de recherche sur les entiers ordonnées par supérieur, dont la représentation interne des arbres est identique, il ne sera en aucun possible d'appliquer ArbreBinInf.ajoute sur un arbre d'ArbreBinSup. Dans le cas d'une fonction polymorphe d'ajout, prenant comme premier élément l'ordre, il est possible de casser la structure d'un arbre de recherche si on l'applique avec un autre ordre.

contraintes de partage

Si pour s'abstraire, encore un peu plus, on désire déclarer abstraitement le type element, il sera alors nécessaire d'indiquer un partage de types.

module EntierInfAbstrait = (EntierInf : ELEMENT_ORD);;

module NouvelArbreBinInf =
  ArbreBinAbstrait(EntierInfAbstrait);;

la même séquence d'utilisation que précédemment provoquera une erreur de typage :

# open NouvelArbreBinInf;;
# let a = arbre_vide;;
val a : NouvelArbreBinInf.arbre_bin = <abstr>
# ajoute 3 a;;
This expression has type int but is here used with type
  NouvelArbreBinInf.element = EntierInfAbstrait.t

L'égalité des types NouvelArbreBinInf.element et ElementInfAbstrait.t est perdue. Pour la rétablir il est nécessaire de l'indiquer explicitement.

En fait il est même nécessaire d'ouvrir la signature ARBRE_BIN pour pouvoir effectuer cette contrainte de types. Comme ARBRE_BIN est un foncteur, il n'est pas possible de l'appliquer dans le but d'obtenir la signature résultat. On définit alors une nouvelle signature X_ARBRE_BIN de la manière suivante :

module type X_ARBRE_BIN = 
  sig
    type element
    type arbre_bin
    val arbre_vide : arbre_bin
    val ajoute : element -> arbre_bin -> arbre_bin
    val appartient : element -> arbre_bin -> bool
  end;;

où le type element est abstrait. Le foncteur suivant rétablit la correspondance des types.

module XArbreBinAbstrait  = 
 (ArbreBinAbstrait :   
   functor (E : ELEMENT_ORD) -> (X_ARBRE_BIN with type element = E.t));;

On retrouve dans la signature du foncteur XArbreBinABstrait l'information suivante :
type element = E.t.

module XArbreBinInf = XArbreBinAbstrait(EntierInf);;

Et l'on se retrouve dans le cas où le type element est lié au type t, tout en l'ayant déclaré abstrait dans la signature X_ARBRE_BIN.

# open XArbreBinInf;;
# let a = arbre_vide;;
val a : XArbreBinInf.arbre_bin = <abstr>
# ajoute 3 a;;
- : XArbreBinInf.arbre_bin = <abstr>

Compilation séparée

L'unité de compilation en O'Caml reste le fichier, à la manière de Caml-Light, où une unité de compilation est découpée en deux fichiers: un fichier d'interface d'extension .mli pour la signature et un fichier d'implantation d'extension .ml pour la structure. Si l'on ne précise rien, le module correspondant à l'unité de compilation est :

module Nom = (
   struct 
     contenu du fichier nom.ml
   end :
   sig
     contenu du fichier nom.mli
   end
)

Attention le nom du module qui commence par une majuscule correspond aux fichiers nom.ml et nom.mli qui commencent par une minuscule.

L'environnement de typage est celui des répertoires d'accès aux fichiers, c'est à dire le répertoire courant, la bibliothèque standard, ...

De Caml-Light à O'Caml

Pour porter un programme Caml-Light en O'Caml, il est nécessaire de :

• réécrire les ouvertures de fichier : on remplacera alors le #open "fichier";; par un open Fichier;;;
• de renommer certaines fonctions des bibliothèques standards.

Dans le cas de la boucle d'interaction, le #use "fichier.ml";; remplacera le load "fichier";;.

Autres lectures

Ce cours s'inspire des lectures suivantes :

• La documentation d'O'Caml sur les modules ;
• le cours de Xavier Leroy au DEA SPP, en PostScript ;
• le rapport Inria 2721 sur la version intermédiaire de Caml, nommée Caml Special Light, en PostScript gzippé ;
• la présentation de Maria-Virginia Aponte (courrier) à l'école de jeunes chercheurs du GDR de Programmation de 1995.

elles ne sont pas obligatoire mais permettent d'avoir une vision plus complète de la programmation modulaire et des modules d'O'Caml.