Les modules en Ocaml.
Postscript, PDF Didier Rémy Polytechnique, INRIA
Cours (super, frames) [man]
[doc] [type-index] Exercices
  1. Modules de base
  2. Signatures
  3. Restriction de signature
  4. Compilation séparée
  5. Foncteurs
  6. Exemple avancé
  1. Abstraction tardive... (**)
  2. Utilisation des librairies (*)
  3. Création d'une librairie (*)
  4. Polynômes (***)

En quelques mots

    ·Un petit langage fonctionnel typé.
    ·Manipule des collections de définitions (de valeurs, de types) du langage de base.
    ·Leurs types: des collections de déclarations/spécifications (types des valeurs, déclarations des types).
    ·Modules emboîtés.
    ·Fonctions (foncteurs) et application de fonctions.
Largement indépendant du langage de base.

Modules de base

Les structures sont des collections de définitions.

    struct p1 ...pn end

Les définitions correspondent aux phrases du langage de base:
définitions de valeurs et de fonctions     let x = ...
définitions de types     type t = ...
définitions d'exceptions     exception E [of ...]
définitions de classes     class C = ... end
Plus:
définition de sous-modules     module X = ...
définition de type de module     module type S = ...


Le nommage d'un module se fait à l'aide de la liaison module.
module S = struct type t = int let x = 0 let f x = x+1 end;;

Utilisation d'un module

On fait référence aux composantes d'un module avec la notation pointée module.composante
        ... (Z.f Z.x : Z.t) ...
Autre possibilité: la directive open module permet d'omettre le préfixe et le point:
        open Z
        ... (f x : t) ...

Modules emboîtés

Un module peut être composante d'un autre module:
module T =
  struct
    module R = struct let x = 0 end
    let y = R.x + 1
  end;;
La notation pointée et la construction open s'étendent naturellement aux sous-modules:
module Q =
  struct
    let z = T.R.x
    open T.R
      ...
  end
  NB: La notation open T.R rend les composantes de T.R visibles dans la suite du corps de Q mais n'ajoute pas ces composantes à Q.
Les types des modules de base

Les signatures: collections de spécifications (de types).
sig s1 s2 ... end
spécification de valeurs val x : s
spécification de types abstraits type t
spécification de types manifestes type t = t
spécification d'exceptions exception E
spécification de sous-modules module X : M
spécification de type de module module type S  [ = M]

Nommage d'un type de module: par la liaison module type
    module type MA_SIGNATURE = sig ... end

structures v.s. des signatures

Structures (implémentations)     Signatures (interfaces)
Séquence de définitions      Séquence de spécifications de types
Valeurs
let x = [1]     val x : int list
let rec f x = ...     val f : int -> int
Exceptions
exception E of string     exception E of string
Types concrets
type t = int     type t = int
type 'a u = A | B of 'a     type 'a u = A | B of 'a
Types abstraits
type v = string     type v

Synthèse de signature

Le système infère les signatures des modules (comme il infère les types des valeurs).
Module
module Exemple =
  struct
    type t = int
    module R =
      struct
        let x = 0
      end
    let y = R.x + 1
  end;;
 
Signature inférée
module Exemple :
  sig
    type t = int
    module R :
      sig
        val x : int
      end
    val y : int
  end

Restriction par une signature

La construction (structure : signature)
    ·vérifie que la structure satisfait la signature
(toutes les composantes spécifiées dans la signature doivent être définies dans la structure, avec des types au moins aussi généraux);
    ·rend inaccessibles les parties de la structure qui ne sont pas spécifiées dans la signature;
    ·produit un résultat qui peut être lié par module M = ...
Sucre syntaxique:
    module X : S = M
est équivalent à
    module X = (M : S)
Restriction (Écritures équivalentes)

module M =
  (struct
      type t = int
      let x = 1
      let f y = x + y
   end :
   sig
      type t
      val f : int -> t
   end)
;;
 
module type S = 
   sig
      type t
      val f : int -> t
   end
module M : S =
  struct
      type t = int
      let x = 1
      let f y = y + x
   end;;
M.x;;           (* Unbound value M.x *)
M.f 1 + 1;;     (* S.f 1 of type M.t is used with type int *)
Vues isomorphes incompatibles

Il est parfois important de distinguer des types isomorphes. Par exemples Euros et Dollars sont tous deux représentés par des flottants. Pourtant, il ne faut pas les confondre.

Ce sont deux espaces vectoriels, isomorphes mais disjoints, avec pour unités respectives l'euro et le dollar.
module Float =
  struct
    type t = float
    let un = 1.0
    let plus = (+.)
    let prod = ( *. )
  end;;
 
module type MONNAIE =
  sig
    type t
    val un  : t
    val plus : t -> t -> t
    val prod : float -> t -> t
  end;;
La multiplication devient une opération externe sur les flottants.

Monnaies incompatibles

Dans Float le type t est concret donc il peut être confondu avec "float". Par contre, il est abstrait dans les modules Euro et Dollar ci-dessous:
module Euro = (Float : MONNAIE);;
module Dollar = (Float : MONNAIE);;
Les types Euro.t et Dollar.t sont isomorphes mais incompatibles.
let euro x = Euro.prod x Euro.un;;
Euro.plus (euro 10.0) (euro 20.0);;
Euro.plus (euro 50.0) Dollar.un;; 
Pas de duplication de code entre Euro et Dollar.

Exercice

Exercise 1   On voudrait implémenter une bureau de change. Pour simplifier, nous considérons seulement deux monnaies Euro et Dollar. Quel est le problème? Avez-vous une idée de la solution?
Answer
Donner la signature BUREAU_DE_CHANGE des valeurs exportées par le module Bureau_de_change.
Answer
Donner l'implémentation du module Bureau_de_change.
Answer
Tester votre implémentation.
Answer

Vues multiples d'un même module

On peut donner une interface restreinte pour, dans un certain contexte, ne permettre que certaines opérations (typiquement, interdire la création de valeurs):

module type PLUS = 
  sig
    type t
    val plus : t -> t -> t
  end;;
module Plus = (Euro : PLUS)
 
module type PLUS_Euro = 
  sig
    type t = Euro.t
    val plus : t -> t -> t
  end;;
module Plus = (Euro : PLUS_Euro)
À gauche, le type Plus.t est incompatible avec Euro.t.

À droite, le type t est partiellement abstrait et compatible avec "Euro.t", et la vue Plus permet de manipuler les valeurs construites avec la vue Euro.

La notation with

La notation with permet d'ajouter des égalités de types dans une signature existante.

L'expression PLUS with type t = Euro.t est une abréviation pour la signature
  sig
    type t = Euro.t
    val plus: t -> t -> t
  end
On peut alors écrire
module Plus = (Euro : PLUS with type t = Euro.t);;
Plus.plus Euro.un Euro.un;;
Elle permet de créer facilement des signatures partiellement abstraites.

Modules et compilation séparée

Une unité de compilation A se compose de deux fichiers:
    ·Le fichier d'implémentation a.ml:
une suite de phrases
semblable à l'intérieur de struct ... end
    ·Le fichier d'interface a.mli (optionnel):
une suite de spécifications
semblable à l'intérieur de sig ... end
Une autre unité de compilation B peut faire référence à A comme si c'était une structure, en utilisant la notation pointée A.x ou bien en faisant open A.

Une fois les interfaces écrites et vérifiées (par le typeur) les composantes peuvent être développées et testées indépendamment.

La modularité du développement coïncide avec la modularité dans le langage.

Compilation séparée d'un programme

Fichiers sources: a.ml, a.mli, b.ml

Étapes de compilation:
ocamlc -c a.mli compile l'interface de A crée a.cmi
ocamlc -c a.ml compile l'implémentation de A crée a.cmo
ocamlc -c b.ml compile l'implémentation de B crée b.cmo
ocamlc -o monprog a.cmo b.cmo   édition de liens finale

Les lignes 2 et 3 peuvent être échangées.

Le programme se comporte comme le code monolithique:
module A sig (* contenu de a.mli *) end =
   struct (* contenu de a.ml *) end
module B =
   struct (* contenu de b.ml *) end
L'ordre des définitions de modules correspond à l'ordre des fichiers objets .cmo sur la ligne de commande de l'éditeur de liens.

Utilisation de la commande make

Modules paramétrés

Un foncteur est une fonction des modules dans les modules:

    functor (Z : T) -> M

Le module (corps du foncteur) est explicitement paramétré par le paramètre de module S. Il fait référence aux composantes de son paramètre avec la notation pointée.
module F = functor(Z : S) ->
  struct
    type u = Z.t * Z.t
    let y = Z.f 0
  end;;

Application de foncteur

On ne peut pas directement accéder dans T. Il faut au préalable l'appliquer explicitement à une implémentation de la signature SIG (tout comme on applique une fonction ordinaire).
    module P1 = F(M1)
    module P2 = F(M2)
P1, P2 s'utilisent alors comme des structures ordinaires:
    (P1.y : P2.u)
P1 et P2 partagent entièrement leur code.

Exemple (long) d'un compte bancaire

module type BANQUE =            (* vue du banquier *)
  sig
    type t
    type monnaie
    val créer : unit -> t
    val dépôt : t -> monnaie -> monnaie
    val retrait : t -> monnaie -> monnaie
  end

module type CLIENT =            (* vue donnée au client *)
  sig
    type t
    type monnaie
    val dépôt : t -> monnaie -> monnaie
    val retrait : t -> monnaie -> monnaie
  end;;    

Une modélisation simple de la banque

Sur le modèle des actions, le compte est donné au client... de façon abstraite bien sûr (sa représentation est cachée) afin que seule la banque puisse modifier le compte du client.
module Banque_au_porteur (M : MONNAIE) :
    BANQUE with type monnaie = M.t =
  struct
    type monnaie = M.t and t = { mutable solde : monnaie }
    let zéro = M.prod 0.0 M.un and neg = M.prod (-1.0)
    let créer() =  { solde = zéro }
    let dépôt c x =
      if x > zéro then c.solde <- M.plus c.solde x; c.solde
    let retrait c x =
      if c.solde > x then (c.solde <- M.plus c.solde (neg x); x) else zéro 
  end;;
module Poste = Banque_au_porteur (Euro);;

La modularité dans l'exemple

-- Les clients et le banquier ont des vues différents, mais compatibles, de la banque.
module Client : CLIENT
     with type monnaie = Poste.monnaie
     with type t = Poste.t 
   =  Poste;;
let mon_ccp = Poste.créer ();;
Poste.dépôt mon_ccp (euro 100.0);;
Client.dépôt mon_ccp (euro 100.0);;

-- On peut créer des comptes dans différentes devises sans risque de confusion (elles seront détectées par le typage).
module Citybank = Banque_au_porteur (Dollar);;
let mon_compte_aux_US = Citybank.créer();;
Citybank.dépôt mon_ccp;;                          
Citybank.dépôt mon_compte_aux_US (euro 100.0);;   

Modularité (suite)

-- On peut changer l'implémentation de la banque tout en en préservant l'interface.

Pour éviter la fraude, une banque donne seulement au client un numéro de compte et conserve l'état de son compte en interne.

La représentation d'un compte devient un simple numéro.

-- Plusieurs banques européennes ont alors des banques de données indépendantes (protégées).
module Banque_centrale = Banque_au_porteur (Euro);;
module Poste = Banque_au_porteur (Euro);;


module Banque (M : MONNAIE) : BANQUE with type monnaie = M.t =
  struct
    let zéro = M.prod 0.0 M.un and neg = M.prod (-1.0)
    type t = int
    type monnaie = M.t

    type compte = { numéro : int; mutable solde : monnaie }
    let comptes = Hashtbl.create 10 and last = ref 0  
    let compte n = Hashtbl.find comptes n

    let créer() = let n = incr last; !last in 
      Hashtbl.add comptes n {numéro = n; solde = zéro}; n

    let dépôt n x = let c = compte n in
      if x > zéro then c.solde <- M.plus c.solde x; c.solde
    let retrait n x = let c = compte n in
      if c.solde > x then (c.solde <- M.plus c.solde x; x) else zéro
  end;;
Indépendance vis-à-vis de la représentation


Banque_au_porteur et "Banque" implémentent la même interface et sont interchangeables
        module Poste = Banque_au_porteur(Euro);;
        module La_Poste = Banque(Euro);;
        module Citybank = Banque(Dollar);;

Il se trouve qu'on ne peut pas non plus observer la différence de comportement au niveau du langage, mais cela n'est pas garanti par le typage...

Utilisation des librairies

Exercise 2  [(*) Utilisation des librairies]   Les amis des amis sont nos amis revient à dire que la relation d'amitié est la fermeture transitive de la relation de grande amitié (amitié directe).

Pour l'exercice on impose de représenter les personnes par leur nom (chaîne de caractères), les amis par des ensembles de personnes (librairie Set), et la relation de grande amitié par une table d'association (librairie Hashtbl).

On considère donné une certain nombre de personnes, et pour chaque personne l'ensemble de ses grands amis. Écrire une fonction qui calcule l'ensemble de tous les amis d'une personne et tester sur un petit exemple.
Answer

Fabrication d'un librairie

Exercise 3  [(*) Les piles]   Définir la structure 'a pile des piles d'élément de type 'a, modifiables en place . Définir une fonction de créer: unit -> 'a pile qui retourne une pile vide. Écrire les fonctions ajouter : 'a -> 'a pile -> unit et retirer : 'a pile -> 'a d'ajout en pile et de retrait du dernier élément. On lancera une exception lorsque l'on essaye de retirer un élément d'une pile vide.
Answer
En faire un module Pile permettant de rendre la représentation des piles abstraite.
Answer
Utiliser la commande make pour compiler le programme.

On voudrait maintenant écrire une version plus riche de cpile, avec une fonction consulter qui retourne le sommet de la pile sans le retirer, mais on ne dispose que du code compiler et de son interface.
Answer
Que manque-t-il pour fournir une implémentation plus efficace de la méthode sommet?

Modifier la librairie pile pour en avoir deux vues différentes: (1) une vue concrète, extensibles, pour l'expert; (2) une vue abstraite pour l'utilisateur ordinaire.

Ici, on pourra écrire tous les modules et leur types dans un seul fichier piles.ml sans se soucier de la compilation séparée.
Answer
Polynômes
Exercise 4  [Polynômes à une variable (***)]  
    ·Réaliser une bibliothèque fournissant les opérations sur les polynômes à une variable. Les coefficients forment un anneau passé en argument à la bibliothèque.
    ·Vérifier l'égalité (X + Y) (X -Y) = (X2 - Y2) en considérant les polynômes à deux variables comme polynôme en X à coefficients les polynôme en Y.
    ·Vérifiez les mêmes égalités dans l'anneau Z/2Z. Z/2Z.
    ·Écrire un programme qui prend un polynôme sur la ligne de commande et l'évalue en chacun des points lus dans stdin (un entier par ligne). Le résultat est imprimé dans stdout.
    ·Utiliser la commande make pour compiler le programme.
    ·Écrire une autre implémentation des polynômes, par exemple par des polynomes creux.
    ·Écrire une version spécialisée des polynômes dans Z/2Z utilisation une représentation pleine et des opérations logiques sur des vecteurs de bits (on pourra se limiter à des polynômes de faible degré à condition de tester le débordemnent).

This document was translated from LATEX by HEVEA and HACHA.