Ours & Hippy — le blog [extensibilité]

J’aime bien l’expression problem, mais il n’est pas particulièrement utile dans la pratique logicielle de tous les jours : les langages utilisés aujourd’hui ne permettent pas en général de le résoudre de façon complètement satisfaisante, soit parce que leurs concepteurs ne se sont même pas posés la question, soit parce qu’ils ont estimé que quelque chose de plus statique mais de plus simple était préférable. Car l’extensibilité à un prix, et les solutions sont souvent compliquées ; certains langages en contiennent en fait d’assez satisfaisante, mais elles ne sont pas au cœur du langage (car on préfère se baser sur des choses sûres et éprouvées), et donc relativement de seconde zone dans la pratique des programmeurs : il faut privilégier la simplicité, donc sauf dans les cas où en a vraiment besoin, on évite d’utiliser ces constructions plus délicates.

Ce qui est intéressant, c’est que ce probème est un très bon moyen de voir les liens entre les langages fonctionnels et les langages orientés objet. Il n’est pas spécifique à un seul paradigme, et les différentes solutions révèlent des caractéristiques, à mon avis assez profondes, des différents paradigmes. En deux mots, généralement les langages fonctionnels facilitent l’ajout d’opérations au détriment de l’extensibilité des données, et les langages à objets favorisent les données plutôt que les opérations.

Produits d’opérations

On pourrait ne pas être tout à fait satisfait de la solution des types sommes extensibles : il y a pas mal de code chiant et qui a l’air inutile (on parle de code boilerplate). En effet :

• tout ce qui concerne les expressions sans multiplication est coiffé d’un constructeur supplémentaire. Ça passe mais si on fait trois extensions de suite, trois couches de constructeurs, ça commence à faire lourd ;

• pour la même raison, on ne peut pas réutiliser directement les fonctions des types étendus pour manipuler des éléments de type simple : si on a une fonction qui sait manipuler des nombres, des sommes et des produits, on ne peut pas lui donner directement un élément de expr, alors qu’elle saurait pourtant manipuler les nombres et les sommes. C’est encore plus compliqué si on voulait n’avoir que des nombres et des produits (pas de somme) sur une partie du programme, puisqu’ils ne sont pas dans un type commun ; il faudrait travailler sur expr2 en lançant une erreur si on tombe sur une somme, ce qui n’est pas très propre.

Je vous ai parlé de langages dans lesquels il était plus facile d’étendre les données que les opérations, sans modifier le code existant. Comment faire, et peut-on le faire en OCaml ? La réponse est oui, mais cela demande un changement (assez radical) de point de vue.

Actuellement, les programmes sont centrés autour des données : on définit leur type, et on exprime ensuite, a posteriori, des opérations comme des fonctions qui opèrent sur ce type : c’est aux opérations de faire le travail de tripoter les données pour en extraire un résultat.

On peut voir la situation complètement différemment en se plaçant du point de vue des opérations : on commence par définir les opérations qui nous intéressent, on en fait un type. Ensuite on exprimera des données qui feront le travail d’exploiter les opérations de leurs composants pour produire leurs opérations.

type ops =
  { eval : int;
    print : string }

Voici nos opérations : l’évaluation, dont le résultat est un entier, et l’affichage.

let int n =
  { eval = n;
    print = string_of_int n }

Voici une donnée. Citoyen de seconde zone ! C’est une fonction qui construit les opérations quivontbien.

let add a b =
  { eval = a.eval + b.eval;
    print = sprintf "(%s + %s)" a.print b.print }

Voici une autre donnée. C’est à elle de faire tout le travail, elle utilise les opérations de ses composants pour construire ses opérations à elle. Parce que sans opérations, une donnée n’est rien. Vous remarquez que je l’ai ajoutée comme ça, sans rien modifier d’existant.

let eval_test = (add (int 1) (int 2)).eval

Ça marche. Mais comme on est coquet :

let eval ops = ops.eval
let print ops = ops.print

let eval_test = eval (add (int 1) (int 2))
let print_test = print (add (int 1) (int 2))

Ça marche et, du point de vue de l’utilisateur, rien n’a changé.

Maintenant, on essaie d’étendre nos opérations. On va rajouter l’opération rpn (notation polonaise inversée) que je vous ai brièvement présentée avec les types sommes simples.

type ops2 =
  { rpn : Buffer.t -> unit;
    ops : ops }

On a une surcouche avec une opération de plus. Celle-ci a de particulier qu’elle demande, pour produire son résultat, un paramètre : un buffer dans lequel est insèrera son contenu. Le sucre syntaxique (qui transforme l’accès à une donnée en fonction) nous rend ici service puisqu’il cache ce détail :

let rpn ops2 =
  let buf = Buffer.create 47 in
  ops2.rpn buf;
  Buffer.contents buf

Par contre, maintenant qu’on a changé le type des opérations, il faut redéfinir les anciennes données pour supporter cette nouvelle opération, et le sucre syntaxique correspondant aux opérations de l’ancien type.

let int n =
  { rpn = (fun buf -> bprintf buf "%d " n);
    ops = int n }

let add a b =
  let rpn buf =
    a.rpn buf; b.rpn buf;
    bprintf buf "+ " in
  { rpn = rpn;
    ops = add a.ops b.ops }

let eval ops2 = ops2.ops.eval
let print ops2 = ops2.ops.print

On peut encore étendre nos données et nos opérations, en rajoutant une donnée mul pour la multiplication.

let mul a b =
  let rpn buf =
    a.rpn buf; b.rpn buf;
    bprintf buf "*" in
  { rpn = rpn;
    ops = { eval = a.ops.eval * b.ops.eval;
            print = sprintf "(%s * %s)" a.ops.print b.ops.print } }

let rpn_test =
  rpn (add (int 1) (mul (int 2) (int 3)))

Caractéristiques de l’approche produit

On a donc l’extensibilité dans les deux dimensions, comme avec les sommes ouvertes. Mais cette fois-ci, on n’a eu besoin que d’une seule itération pour trouver quelque chose de satisfaisant, et c’est relativement simple puisque ça ne demande pas de types paramétrés ni même de traitement de la récursion : la définition des données de ce problème est récursive, mais pas celle des opérations ! En changeant de point de vue on l’attaque donc selon un angle plus simple. Cette méthode a cependant deux défauts assez importants.

D’abord, La définition des données est éparpillée un peu partout, et chacune contient un peu d’information sur les opérations, ce qui rend le code moins facile à suivre (surtout pour des opérations plus complexes) : pour voir la définition d’une opération, il faut trouver ses petits morceaux dans chaque définition de donnée, il n’y a pas de vue d’ensemble.

En réalité il y a un problème symétrique dans le cas des sommes : si l’on considère l’ensemble des effets des opérations sur un cas spécifique de notre structure comme un tout, on se retrouve à devoir lire le code de chaque opérations pour y voir à chaque fois le traitement du cas qui nous intéresse : « Je m’intéresse seulement aux multiplications et pas aux additions : comment sont-elles évaluées ? Comment sont-elles affichées ? » Et les opérations sont définies en plusieurs endroits pour une même donnée, donc ça rend plus difficile la vision d’ensemble sur un cas spécifique. On observe donc vraiment les deux facettes d’une même pièce : il faut pouvoir prendre un point de vue ou l’autre, car l’un pourra être plus adapté que l’autre dans certaines situations.

D’autre part, cette écriture des opérations en fonction des opérations des composants ne marche bien que pour une certaine classe d’opérateurs, les catamorphismes (c’est en gros leur definition : opérateurs que l’on peut définir avec uniquement le résultat d’opérations sur les composants directs de notre donnée). C’est une classe plutôt générale mais certaines opérations n’en font pas partie.

Typiquement, dans le cas d’arbres comme celui qui nous intéresse (les expressions mathématiques forment un arbre dont les nombres sont les feuilles, et les opérations les noeuds), le catamorphisme va favoriser un mode de parcours de l’arbre en particulier (tu parcours chaque fils de ton noeud séparément puis tu réunis les résultats) alors que certains problèmes demandent des modes de parcours différents (par exemple une fonction dont le résultat dépend à chaque fois du père et du fils gauche, au lieu du fils gauche et du fils droit). On peut toujours tout faire rentrer à la hache dans la pensée unique du catamorphisme (qui est assez naturel donc très courant), mais dans certains cas ça donne des codes illisibles.

Dans ce cas, la meilleure solution, au lieu de chercher à accéder intelligemment aux résultats des fils dans le bon ordre, et de mettre une machinerie complexe pour faire passer les résultats dans tous les sens, est souvent de :

• reconstruire l’« arbre » correspondant à la donnée, qui est l’information la plus générale que l’on puisse obtenir, et dont la construction s’exprime comme un catamorphisme ;
• implémenter l’opération à partir de l’arbre, dans un style plus direct.

Le problème est alors : quel type donner à l’arbre ? On se retrouve en fait à définir un type somme, et c’est donc le retour à la case départ : si notre type somme n’est pas extensible, les opérations qui l’utilisent ne le seront pas non plus. Si on veut garder l’extensibilité par les produits d’opérations, il faut donc sacrifier de la facilité à programmer.

POO et motifs de conception

Vous l’aurez peut-être remarqué en lisant ma dernière partie, mais elle est en fait très proche de certaines idées de la POO. L’insistance en particulier sur le fait que les opérations (« méthodes ») font parties du type que l’on définit, au point d’en faire l’élément le plus important du programme. Comme on l’a vu, cela a selon les besoins des avantages, mais aussi des inconvénients.

Dans un langage plus POO, la structure que j’ai mise en place dans la dernière partie correspond au motif Composite. Dans ce motif, on définit une interface qui décrit les opérations, puis une classe pour chaque donnée :

class type expr = object
  method eval : int
  method print : string
end

class int n : expr = object
  method eval = n
  method print = string_of_int n
end

class add a b : expr = object
  method eval = a#eval + b#eval
  method print = sprintf "(%s + %s)" a#print b#print
end

let test = (new add (new int 1) (new int 2))#eval

On peut remarquer que les langages OO aussi auront bien besoin de sucre syntaxique pour alléger un peu tout ça. Par contre, là où une solution objet est intéressante par rapport à notre solution à base d’enregistrements, c’est qu’on peut étendre les opérations avec le mécanisme d’héritage :

class type expr2 = object
  inherit expr
  method rpn : Buffer.t -> string
end

On peut alors appeler directement les méthodes eval et print sur des objets vérifiant l’interface expr2, sans devoir passer par une couche d’indirection (le .ops de la solution produit). De notre point de vue c’est presque un détail syntaxique, et la première méthode a aussi ses mérites puisqu’elle correspond à la relation de composition qui est souvent considérée par les programmeurs POO comme plus adaptée que l’héritage dans un grand nombre de cas.

Approche somme en POO

J’ai présenté cette vision POO du problème, qui correspond au motif Composite. C’est la méthode la plus naturelle pour un programmeur OO (qui est donc sans le savoir un descendant de la solution produit), mais il est aussi possible d’effectuer un changement radical de point de vue, dans le but de retrouver une approche avec des sommes. Ça correspond au motif Visiteur : au lieu de mettre les opérations dans les méthodes, on met les données.

L’idée est la suivante : on imagine chaque donnée comme un lieu que l’on peut visiter ; chaque donnée est chargée de coder une fonction accept qui appelle une méthode adaptée du visiteur :

let int n = object
  method accept visitor = visitor#int n
end

let add a b = object
  method accept visitor = visitor#add a b
end

Ces fonctions accept prennent des visiteurs en argument, et leurs donnent leurs composants. Chaque opérateur est un visiteur :

let eval = object (self)
  method int n = n
  method add a b = a#accept self + b#accept self
end

let test_eval =
  let expr = add (int 1) (int 2) in
  expr#accept eval

Cette solution est donc l’analogue OO des types sommes; on peut de plus profiter de la "récursion ouverte" des objets pour obtenir l’analogue de la "somme ouverte" : pas besoin de paramétrer les objets de départ pour les enrichir ensuite, le mécanisme d’héritage suffit. Elle est cependant beaucoup plus difficile à typer (c’est pourquoi elle est plus souvent utilisée dans des langages à typage dynamique qui ne se posent pas la question).

À chaque fois que je veux rédiger une réaction, c’est la même chose : je vais voir dans ma liste de publications pour voir ce que je pourrais traiter. Il y en a qui m’ennuient, qui sont trop techniques pour être agréables, ou encore d’autres qui sont très tentants, mais dont je sais qu’ils demanderont beaucoup de travail, par exemple parce qu’ils sont suivis de quelques annotations « commencer par relire ceci et cela, ne pas oublier de mentionner aussi ceci et cela », etc.

Et là, je tombe sur la publication qui me tente : pas trop difficile, je sens que j’ai envie des choses à dire mais pas trop. Je vais le relire et ça commence typiquement par un « haha, il est super clair, je vais mettre deux lignes d’introduction, un résumé, et hop je les envoie le lire ». Mais le malheur arrive vite : les remarques indispensables s’accumulent, je me pose de nouvelles questions, je commence à expérimenter de mon côté, et quatre heures après j’ai un tas de code bizarre dans un fichier, et rien d’écrit.

Cette fois-ci, ça a tellement bien marché que je ne vais vous citer aucune publication dans ce billet : les développements préliminaires méritent un billet à eux tout seul, et sont assez lourds pour qu’une publication en plus frôle l’indigestion. Je ferai donc un billet suivant, et pour me racheter j’y citerai non pas une publication, ni deux, mais trois. Beware!

Édit : je vous écris depuis le futur pour vous signaler qu’un développement inattendu a nécessité la création d’un deuxième billet préliminaire. Les liens seront donc pour le troisième billet.

Pour profiter de ce billet, vous devez savoir lire du code en Objective Caml.

Types, opérations et extensibilité

Qu’est-ce qu’une structure de données en informatique ? C’est une question essentielle quand on veut programmer, et la réponse, en gros, on l’a, ma bonne dame, ce sont les types algébriques :

• une structure de donnée peut se présenter sous plusieurs formes différentes ;

• sous chaque forme, elle est composée d’un certains nombres de composants, qui sont aussi des données, mais pas forcément de la même sorte.

Par exemple, quelqu’un dans une école est soit un élève, soit un professeur. Si c’est un élève, il est caractérisé par son nom, son âge, et la marque de ses chaussures. Si c’est un professeur c’est la matière, la note moyenne, et le nom de ses antidépresseurs. Bien sûr, ce n’est qu’un modèle donné pour un problème donné, un modèle étant par définition réducteur : si on s’intéresse à d’autres aspects de la même chose (les personnes présentes dans une école) on pourra être amené à faire d’autres distinctions, ajouter des informations dans chaque cas, ou au contraire approximer en enlevant des informations (les profs, tous des salauds !). Ne vous laissez pas influencer par les gens qui prétendent que leur modèle décrit vraiment la nature profonde du monde matériel : en particulier, si vous croyez qu’en envoyant à un élève au hasard un message pour lui demander son nom, il va répondre (et, le cas échéant, que la réponse sera bien typée)…

Bref, les types algébriques des langages fonctionnels typés, c’est bon, mangez-en. Ce n’est pas la solution ultime (ça n’existe pas) et ça ne suffit pas toujours, mais c’est une solution générale et commode dans la plupart des cas. Qu’on se mette d’accord tout de suite : quand un type a plusieurs composants accessible simultanément (il a un champ foo et un champ bar), je parle de type produit, comme le produit cartésien en mathématiques (un couple avec un élément de chaque), et quand on a un choix (c’est soit un foo, soit un bar) je parle de type somme, comme la somme disjointe de deux ensemble en mathématiques. On peut évidemment faire des combinaisons, par exemple des sommes de produits (c’est soit un nom et une adresse, soit un identifiant et une adresse web), ou des produits de sommes (c’est, d’une part, un numéro de téléphone ou une adresse mail, et d’autre part un site web ou rien du tout).

Les types algébriques c’est le bien, mais comment fait-on si on a besoin de changer un peu les informations sur notre type (par exemple on veut rajouter un cas « personnel de la cantine ») ? Facile : On change notre type algébrique. Et comme on est dans un langage fortement typé, le compilateur va repérer^α tous les endroits de notre code où on utilise ce type, puisque leur typage sera devenu incorrect, et nous donner leur position pour qu’on les modifie pour prendre en compte le changement de type, un par un, il nous prend par la main et ça simplifie énormément la maintenance^β du programme.

Ça ne marchera pas si les modifications n’impliquent pas de changement incompatible du type (par exemple on remplace un composant de type entier par un composant de type entier, qui n’a pas la même signification), mais là c’est que vous le faites exprès : vous avez un langage au typage expressif, profitez-en pour que vos types soient un peu précis !

Expression problem

Maintenant, comment faire si on envie de rajouter des informations, mais sans modifier le code existant ? Ça arrive quand vous avez le malheur d’utiliser une bibliothèque propriétaire (mais alors c’est de votre faute), ou même que ça demanderait de modifier une bibliothèque et que vous n’avez pas envie de maintenir un fork, ni de justifier vos changements upstream (ou qu’ils les refuseraient de toute façon car ils cassent la compatibilité avec l’existant), bref que le type existant n’est pas de vous. Ou tout simplement que vous n’avez pas envie de devoir recompiler le code existant, car votre compilateur est terriblement lent.

Pour ajouter des cas à un type somme (par exemple ancien_type), sans le modifier, on définit un nouveau type somme :

type nouveau_type =
  | Ancien_cas of ancien_type
  | Nouveau_cas of nouvelles_informations

On peut ensuite définir de nouvelles opérations, et il est utile de faire du filtrage de motif sur les objets^γ de type nouveau_type :

match ma_donnee with
  | Ancien_cas ancienne_donnee -> ...
  | Nouveau_cas nouvelle_donnee -> ...

Dans les premiers ... on met le traitement à effectuer sur les anciennes valeurs (on réutilise souvent directement les fonctions de traitement définies sur l’ancien type), et dans les deuxièmes on gère le nouveau cas. C’est clair (quand on l’habitude), commode, expressif^δ, bon pour la peau, etc.

Cette méthode a quand même ses limites. Déjà elle est un peu lourde (à l’écriture, et à l’exécution) parce qu’on rajoute une nouvelle couche de distinction de cas à chaque fois (là ça va mais après trois ajouts vous devrez faire trois distinctions successives…), mais aussi des problèmes plus profonds que vous verrez en partie dans le reste de ce billet. Ça a poussé les chercheurs en langages de programmation à expérimenter de nouvelles façon d’exprimer la chose, et c’est ce qu’on appelle l’expression problem :

Comment définir des données et les opérations sur ces données, tout en pouvant ensuite ajouter des données et des opérations, sans modifier le code existant ?

Chacun a apporté sa petite solution, et la compare à celle des autres. Elles sont plus ou moins compliquées, et plus ou moins solutionnesques (certaines gèrent des choses que les autres ne gèrent pas, et chacun prétend que son petit plus est déterminant). Je ne compte pas apporter une solution dans ce billet, mais plutôt développer la question par des essais successifs, pour vous faire sentir son intérêt et une partie des difficultés.

Fil conducteur

On s’intéressera dans ces billets au problème de l’extensibilité dans le cas particuliers d’expressions arithmétiques simples. Je présenterai différentes façon de représenter des nombres, des sommes, de calculer leur valeur ou de les afficher non calculées, éventuellement des produits (extensibilité des données) ou d’autres opérations.

Avec des types somme

On commence par des expressions qui sont soit des nombres, soit des sommes d’expressions :

type expr =
  | Int of int
  | Add of expr * expr

On peut facilement définir une fonction d’évaluation et d’affichage :

let rec eval = function
  | Int n -> n
  | Add (a, b) -> eval a + eval b

let eval_test = assert (eval (Add (Int 1, Int 2)) = 3)

let rec print = function
  | Int n -> string_of_int n
  | Add (a, b) -> sprintf "(%s + %s)" (print a) (print b)

let print_test = assert (eval (Add (Int 1, Int 2)) = "(1 + 2)")

Pour la deuxième fonction il faut ouvrir le module Printf. Je donne le code en OCaml pour montrer que ce n’est pas que du vent, mais ne vous focalisez pas sur de petits détails (pourquoi renvoyer une chaîne ? et la concaténation ça coûte cher ? blablabla).

Comme vous pouvez le voir, rajouter une fonction, c’est très facile, tellement qu’on n’y pense même pas (tous les langages n’ont pas la même chance). Par contre, si on veut étendre les données, pour ajouter le produit d’expressions, ça coince :

type expr2 =
  | Expr of expr
  | Mul of expr2 * expr2 

Epic fail! En effet, ce type ne correspond pas à ce qu’on veut : on peut rajouter des multiplications par dessus des valeurs existantes, mais pas l’inverse : on ne peut pas dire Add (Mul (..), ..), car Add prend des paramètres de type expr, et Mul n’en fait pas partie, il n’est que dans le type expr2. Dans certains cas spécifiques ce comportement est utile, mais ici on veut pouvoir mélanger les multiplications et les additions, donc ça ne va pas. On est arrivé à une limite de la méthode d’extensibilité par types somme : utilisée naïvement, elle supporte très très mal les données récursives (ici le problème c’est que le type expr fait référence à lui-même, et pas à expr2).

Frustré, vous décidez de rajouter une opération, nah.

(* notation polonaise inversée *)
let rpn expr = 
  let buf = Buffer.create 37 in
  let print fmt = bprintf buf (format_of_string fmt) in
  let rec rpn = function
  | Int n -> print "%d " n
  | Add (a, b) -> 
      rpn a; rpn b;
      print "+ " in
  rpn expr;
  Buffer.contents buf

let test_rpn = rpn (Add (Int 1, Int 2))

Types somme ouverts

Examinons le code suivant.

type expr =
  | Int of int
  | Add of expr * expr

type expr2 =
  | Expr of expr
  | Mul of expr2 * expr2 

Le deuxième type ne fait pas ce qu’on voudrait, parce que le type expr est fermé : on a fixé le type de ses composants et il refuse d’en accepter de nouveaux. On peut essayer de s’en sortir en le forçant à s’ouvrir, c’est à dire en rajoutant un paramètre de type :

type 'a _expr =
  | Int of int
  | Add of 'a * 'a

Je mets le mignon petit _ devant pour montrer que c’est un type ouvert, tolérant, hippie quoi. On pourrait maintenant avoir un type expr2 convenable :

type expr2 =
  | Expr of expr2 _expr
  | Mul of expr2 * expr2

La partie « ancienne » de expr2 accepte maintenant des composants de type expr2 : on peut mettre des multiplications dans les additions, mission accomplie. Mais il ne faut pas brusquer les choses, on va commencer avec juste _expr, et s’intéresser à l’ajout d’opérations.

let _eval eval = function
  | Int n -> n
  | Add (a, b) -> eval a + eval b

Vous remarquez sans doute un paramètre supplémentaire, eval : en effet les sommes contiennent un composant 'a à priori inconnu, et on ne sait pas comment l’évaluer : on prend donc en paramètre une fonction auxiliaire eval qui sait évaluer le type 'a. C’est charmant mais ça ne nous dit pas comment évaluer les expressions avec juste des additions et des nombres qu’on essaie de manipuler : il faut une version fermée du type _expr :

type expr = Fix of expr _expr

Toute ressemblance avec un point fixe de récursion serait purement fortuite. Ça revient à définir un type d’expressions qui se contient lui-même : on est en fait revenu au type récursif fermé expr de départ, mais avec un constructeur explicite pour la récursion car sinon le compilateur râle (ou alors il faut ajouter l’option -rectypes).

Dans le même genre tying the knot, on a l’évaluateur d’expressions fermées :

let rec eval (Fix expr) = _eval eval expr

let eval_test = eval (Fix (Add (Fix (Int 1), Fix (Int 2))))

C’est quand même un peu lourd à écrire, donc on définit du sucre syntaxique sous forme de smart constructors :

let _int n = Int n
let _add a b = Add (a, b)
  
let int n = Fix (_int n)
let add a b = Fix (_add a b)

let eval_test = eval (add (int 1) (int 2))

On a bien l’extensibilité des opérations, maintenant on récolte les bénéfices de toutes ces complications avec l’extensibilité des données :

type 'a _mul_expr =
  | Expr of 'a _expr
  | Mul of 'a * 'a

let _mul_eval (!) = function
  | Expr e -> _eval (!) e
  | Mul (a, b) -> !a * !b

Deux remarques. J’ai choisi une forme ouverte pour mul_expr, puisque cela permettra de l’étendre elle aussi si le besoin s’en fait sentir (heureusement pour la longueur de ce billet, il ne se fera pas sentir, mais imaginez ! :pirate:). J’ai choisi le rigolo nom (!) pour la fonction d’évaluation prise en paramètre parce qu’on peut l’utiliser comme opérateur infixe, c’est amusant.

Smart constructors, on ferme la récursion, et on profite :

let _int n = Expr (_int n)
let _add a b = Expr (_add a b)
let _mul a b = Mul (a, b)

type mul_expr = Fix2 of mul_expr _mul_expr
let rec eval (Fix2 expr) = _mul_eval eval expr

let int n = Fix2 (_int n)
let add a b = Fix2 (_add a b)
let mul a b = Fix2 (_mul a b)

let eval2_test = eval (add (int 1) (mul (int 2) (int 3)))

Vous notez que je ne vous ai pas arnaqués, en faisant sans le dire à nouveau le travail effectué pour le premier type (si on doit introduire des redondances, ce n’est plus de la vraie extensibilité) : j’ai défini les nouveaux constructeurs _int et _add en fonction des anciens, de façon mécanique et indolore : on n’a pas à connaître leur signification (juste leur arité) ou, pire, leur implémentation.

Pour enfoncer le clou sur l’extensibilité, on se reconvainc de l’extensibilité des opérations avec une fonction print sur le tard :

let _print print = function
  | Expr (Int n) -> string_of_int n
  | Expr (Add (a, b)) -> sprintf "(%s + %s)" (print a) (print b)
  | Mul (a, b) -> sprintf "(%s * %s)" (print a) (print b)

let rec print (Fix2 expr) = _print print expr
let print_test = print (add (int 1) (mul (int 2) (int 3)))