Article complet: Le type somme fermée de produits ouverts

Le billet d'aujourd'hui a pour but de désamorcer une difficulté courante et propre à entraver l'usage des classes en Objective-Caml.

Le style de programmation encouragé par Objective-Caml tend à marginaliser le recours à une POO d'encapsulation où les classes auraient pour objectif essentiel de limiter la propagation des effets hors d'une certaine portée. En présence de valeurs immutables cet usage des classes comme un moyen de componentisation, si essentiel en POO impérative, perd tout ou partie de son attrait. Il devient alors tentant d'utiliser les classes, non pas comme une enveloppe pour camoufler son contenu, mais comme un type produit particulier, un type produit ouvert.

[Suite:]

Dans un programme suffisamment expressif un tel type produit n'est pas isolé, il va de pair avec un type somme.
Le but étant souvent de construire un type algébrique où la somme est fermée mais où les produits restent ouverts.

Remarque hors sujet:
Vu d'une certaine façon, le catalogue des design patterns n'est qu'une longue énumération des inconvénients à penser dans le cadre d'un paradigme plutôt qu'à utiliser le type qui convient pour l'usage qui convient. Les gourous de la POO ont remarqué depuis longtemps l'inadéquation des types produits ouverts à implanter ce qui par nature est essentiellement un type somme. Plutôt que de nous infliger avec fatalisme leur catalogue de solutions imparfaites, ils devraient en tirer la conclusion qui s'impose d'elle-même. Que leur langage favori n'est pas assez riche en types. Que la POO n'est pas une meilleure implantation du vieux type union (même s'il était typé avec les pieds) mais un type de nature différente qui n'élimine pas le besoin d'un véritable type somme dans les langages impératifs.

Revenons à notre type somme fermée de produits ouverts.
Pour l'illustrer nous allons prendre l'exemple du type des arbres rouge-noir.
Chaque noeud d'un arbre rouge-noir est :

• soit vide (Empty)
• soit rouge (Red)
• soit noir (Black)

Evidemment il faudra distinguer le cas d'un noeud vide comme un cas à part (un noeud vide n'a pas de fils), ce qu'un type produit ne peut pas faire. De plus il n'y a aucune raison d'ajouter des cas supplémentaires. C'est pourquoi le type node_color doit être un type somme fermée.

Il en va différemment des données attachées aux noeuds, on peut vouloir ne stocker qu'une clé (conteneur ensembliste) ou bien on peut vouloir stocker un article attaché à une clé (conteneur associatif). On peut aussi vouloir stocker des renseignements structurels complémentaires, par exemple son nombre de noeuds (en vue d'accéder rapidement à l'élément de rang n). Un paramètre de type nous permet d'abstraire toutes ces possibilités :

type 'a node_color =
  | Empty
  | Red   of 'a node_data 
  | Black of 'a node_data
and 'a node_data =
  {left: 'a node_color; right: 'a node_color; data: 'a}

Un paramètre de type est raisonnable ici parce que nous n'avons qu'un seul type produit. Si nous avions un type algébrique plus expressif et que nous souhaitions l'ouvrir en extension pour chacune de ses alternatives il serait déraisonnable d'ajouter un paramètre de type pour chacun des cas. On ne pourrait plus simuler en paramétrant le type somme, il nous faudrait un véritable type produit ouvert.

Le code d'une première tentative d'utiliser une classe ressemblerait alors à ceci :

type node_color =
  | Empty
  | Red   of node_data
  | Black of node_data

class node_data l r =
  object
    method left:  node_color = l
    method right: node_color = r
  end 

Cependant ce code ne compile pas parce que le type node_data n'est pas défini dans node_color.
Bien sûr, si on interverti l'ordre des déclarations, c'est à son tour le type node_color qui n'est pas défini dans node_data.

Curieusement, il n'existe pas de syntaxe pour rendre mutuellement récursifs le type node_color et la classe node_data. En voici l'explication rationnelle: une classe n'est pas vraiment un type, c'est surtout une valeur fonctionnelle (celle du constructeur new). Une classe est avant tout une fonction constructeur pour un type produit. Par conséquent une classe n'a rien à faire dans une déclaration de type.

Pour spécifier un type produit comme extensible il suffit en fait de spécifier ce type comme on le ferait pour un type enregistrement puis de remplacer la paire encadrante {...} par une paire <...>. Par la suite une classe servira de constructeur pour ce type.

type node_color =
  | Empty
  | Red   of node_data
  | Black of node_data
and node_data =
  <left: color_node; right: color_node>

class node_data l r =
  object
    method left:  node_color = l
    method right: node_color = r
  end 

Voilà, j'espère que ce billet vous aura aidé à faire le point sur les différentes sortes de types à votre disposition, ainsi qu'à les faire cohabiter dans un cadre fonctionnel, hors des domaines à quoi leurs origines les prédestinait.