Ours & Hippy — le blog

De l'art de coder un blog (1/2)

2010-02-28T22:22:14+01:00

Après deux semaines de développement (et une semaine de déploiement qu’il serait dommage d’oublier…), le nouveau blog est là. Pour les pauvres âmes égarées par erreur en ces lieux, permettez-moi de rappeler que ce blog, sur lequel vous êtes, est un produit entièrement artisanal, issu de nos belles campagnes, ahem, je me dissipe.

Mais si je vous écris aujourd’hui, ce n’est pas pour vous parler des nouvelles fonctionnalités trop cools du blog (vous pouvez bien voir par vous-mêmes, vous êtes assez grands), mais pour vous faire part de cette petite expérience, la mienne, dans le monde du développement Web. Au programme donc, aujourd’hui : comment écrire un blog, ou plutôt, comment j’ai écrit le mien. Original, n’est-t-il-pas ?^α :]

Avant de poursuivre, il faut replacer la démarche dans son contexte (wow, je croirais entendre mes profs). Mon blog est un petit blog, hébergé en grande partie sur mon PC de bureau reconverti en serveur malgré lui, tout ça derrière une Freebox. Il est clair, à partir de là, que les enjeux ne sont pas du tout comparables à un site moyen ou gros comptant les visiteurs par milliers.

α : Ça me fait penser à ce petit billet gentillet sur lequel j’étais tombé par hasard, un jour, alors que je dérivais de recherches en recherches puis de liens en liens, sur l’Internet : Blogging apps are the new Hello World.

Le fond

Dans le fond, un blog, c’est quoi ? C’est un tas d’articles, de commentaires (si le blog n’est pas trop perdu), et toute une taxinomie de ce vaste petit monde en tags, catégories, séries, ou tout autre mode de classification que l’on pourra imaginer.

Besoins très classiques et à la fois pas si évidents à modéliser correctement.

Bien sûr, le but, du moins le mien, n’est pas d’implémenter tous les outils de filtrage et de tri possibles et imaginables. J’ai toujours pensé, par exemple, que les tags et les catégories étaient redondants. Je ne doute pas que certains y trouvent leur compte, à séparer en tags et en catégories ; moi, honnêtement, avec mon modeste blog, je n’en vois pas l’intérêt. Il n’y a tout simplement pas suffisamment de contenu pour nécessiter autant de sophistication.^β

J’ai donc retenu les éléments suivants :

des articles ;
des commentaires ;
des séries (collections d’articles, avec possibilité de lier deux articles d’une même série par des liens précédent / suivant) ;^γ
et des tags (mots-clés décrivant un article).

β : Du temps des RZ-pages, mon ancien site, le système de catégorie était autrement plus complexe, conceptuellement, que l’actuel classification par tags : il était hiérarchique, et les articles pouvaient en même temps être des catégories (duh!). L’expérience a montré que pour le contenu que j’avais à proposer, c’était plus confus qu’autre chose.

γ : Du point de vue de l’implémentation, séries et catégories sont proches, si l’on exclut la possibilité de joindre des articles consécutifs d’une série.

Séries, articles, commentaires, et hiérarchie

Durant les dernières vacances (ou était-ce avant ?), j’ai eu une discussion intéressante sur #sdz, sur l’organisation des commentaires. Certains argumentaient que les commentaires hiérarchiques étaient plus clairs, tandis que je restais sceptique.

Mais si je vous parle de cela, c’est qu’un tel choix n’est pas sans conséquences sur l’implémentation. Si l’on opte pour une vue généralisée en arbres des commentaires, il vient naturellement que l’on pourrait faire de même pour les articles, et quitte à faire, ne maintenir qu’un seul arbre gigantesque comprenant toutes les séries, les articles, et les commentaires. Une telle stratégie suggère une représentation spécialisée des données, adaptée à la consultation d’arborescences, telle que la représentation intervallaire.

Pour mon blog, j’ai décidé de rester sur un modèle plus simple, avec une hiérarchie figée, à trois niveaux : séries, articles, commentaires. Se pose tout de même la question de faire une seule ou plusieurs tables ; j’ai décidé de n’en faire qu’une. Un article, une série, ou un commentaire est, dans ma base de données, un enregistrement dans la table entry. Il y a à cela plusieurs raisons, qui peuvent finalement toutes se résumer à un mot : homogénéité. J’aime pouvoir traiter les articles et les commentaires de manière similaire… car ils sont similaires ! L’interface est différente (voy. ci-dessous : Rédaction, mises à jour, et Atom), mais les données sont analogues : des auteurs, un contenu, une date, et quelques autres broutilles.

Mais la conception ne s’arrête pas là : on ne va guère loin avec juste des articles, des commentaires, et des séries… reste à les lier entre eux ! Et c’est là où les choses se gâtent quelque peu. Résumons les différents types de liens qui peuvent lier deux objets :

un article peut appartenir à au plus une série ;
un article peut avoir un prédécesseur et un successeur ;
un commentaire appartient à un et un seul article.

En SQL, cela donne ceci :

CREATE TABLE entry (
        -- Un identifiant :
        e_eid INTEGER PRIMARY KEY,

        -- Des métadonnées :
        e_atomid TEXT UNIQUE NOT NULL,
        e_title TEXT NOT NULL,
        e_ctime INTEGER NOT NULL,
        e_mtime INTEGER NOT NULL,
        e_lang TEXT,

        -- Quelques liens :
        e_parent INTEGER,
        e_prev INTEGER,
        e_next INTEGER,

        -- Le contenu :
        e_content TEXT,

        -- D'autres métadonnées (relatives au site) :
        e_url TEXT UNIQUE,
        e_type CHAR(1) NOT NULL, -- Series | Article | Topic | Comment.
        e_from CHAR(1) NOT NULL, -- Primary | Secondary | Foreign.
        e_banned CHAR(1) NOT NULL, -- Auto-banned | Banned | -.
        e_level INTEGER NOT NULL,

        -- D'autres champs...
);

De plus, il est fréquent, quand on récupère les données d’un objet, d’avoir besoin de certaines informations connexes, telles que le nombre de commentaires d’un article, ou le titre de la série apparentée. Avec une base de données relationnelle, on a des jointures. C’est un joli concept, dirait bluestorm, mais une jointure pour la série parente, une pour l’article précédent, une autre pour l’article suivant, et encore une pour les commentaires associés, cela fait… beaucoup.

C’est là qu’intervient le cache. Enfin, un cache ; car il y a toute une flopée de façons de faire. On peut mettre en cache le résultat de certaines requêtes, ou carrément la sortie HTML produite par notre script. On peut stocker ça en mémoire (p.ex. en utilisant memcached), ou dans la base de données. Sans compter les mille et une manières de maintenir ce cache à jour.

Dans mon cas, il s’agit tout simplement d’une petite table,^δ dont les données sont extraites à partir d’une vue associée. C’est la méthode du pauvre pour matérialiser une vue, disons.

δ : Il y a également un cache au niveau de la sortie HTML (ou XML pour Atom et les sitemaps).

Et pour ceux qui aiment le code, voici :

-- La vue :
CREATE VIEW entry_cache_1 AS
SELECT
    self.e_eid AS ec_eid,
    parent.e_url AS ec_parent_url,
    parent.e_title AS ec_parent_title,
    parent.e_atomid AS ec_parent_atomid,
    parent.e_authors AS ec_parent_authors,
    parent.e_tags AS ec_parent_tags,
    thread.et_utime AS ec_parent_utime,
    prev.e_url AS ec_prev_url,
    prev.e_title AS ec_prev_title,
    prev.e_atomid AS ec_prev_atomid,
    next.e_url AS ec_next_url,
    next.e_title AS ec_next_title,
    next.e_atomid AS ec_next_atomid
FROM
    entry self LEFT JOIN
    entry parent ON self.e_parent = parent.e_eid LEFT JOIN
    entry_thread thread ON self.e_parent = thread.et_eid LEFT JOIN
    entry prev ON self.e_prev = prev.e_eid LEFT JOIN
    entry next ON self.e_next = next.e_eid;

-- La table :
CREATE TABLE entry_cache (
        ec_eid INTEGER PRIMARY KEY,
        ec_parent_url TEXT,
        ec_parent_title TEXT,
        ec_parent_atomid TEXT,
        ec_parent_authors TEXT,
        ec_parent_tags TEXT,
        ec_parent_utime INTEGER,
        ec_prev_url TEXT,
        ec_prev_title TEXT,
        ec_prev_atomid TEXT,
        ec_next_url TEXT,
        ec_next_title TEXT,
        ec_next_atomid TEXT
);

-- Et la requête pour remplir la seconde depuis la première :
REPLACE INTO entry_cache SELECT * FROM entry_cache_1
WHERE ec_eid = ?

En vérité, il manque sur cette démonstration certaines données capitales telles que le nombre de commentaires d’un article. Celles-ci sont en fait maintenues à part, dans une table entry_thread. Cette dernière est mise à jour par incréments, à chaque ajout d’un nouveau commentaire. Elle peut également être rafraîchie à partir d’une requête, à la manière d’entry_cache.^ε

Des approches plus complexes (principalement du fait de leurs possibilités de passage à l’échelle) peuvent se justifier pour des gros sites, mais compte tenu de mon hébergement quelque peu technologiquement précaire, pour parler comme Poulet, la ressource limitante est clairement la bande passante, et s’il est rigolo de jouer au petit jeu de l’optimisation un moment, on peut dire que j’aurais déjà perdu assez de temps comme cela. :)

ε : C’est utile, par exemple, pour l’importation de commentaires sous forme d’un flux Atom archivé, comme cela a été le cas lors de la migration vers la nouvelle version du blog.

Et les tags, dans tout ça ?

La question du stockage et de l’indexation des tags est l’autre gros problème d’implémentation. Le sujet est plutôt bien présenté, benchmarks à l’appui, dans cet article sur la représentation des tags dans une base de données ; je ne vais pas épiloguer sur les différentes manières de faire. Pour résumer, on a le choix entre stocker les tags d’un article de manière dénormalisée avec l’objet lui-même, ou utiliser des tables d’associations entre des objets articles et des objets tags, avec toutes les variantes possibles et imaginables.

L’ancienne version du blog utilisait la forme dénormalisée… essentiellement par flemme. Le problème qui s’est posé fut celui de faire des statistiques (p.ex. des nuages de tags) sur les tags. Cette approche est fondamentalement asymétrique et privilégie l’accès par articles au détriment de l’accès par tags.

On pourrait imaginer maintenir un index orthogonal, qui recense tous les articles associés à chaque tag. Avec des structures de données appropriées, l’intuition me dit que l’on devrait arriver à queque chose de pas mal. Je n’ai pas tellement étudié la question, mais il me semble logique que les mecs qui se branlent sur les bases de données non relationnelles, dans lesquelles la redondance est reine, soient enclins à opter pour ce genre de solutions. Quelqu’un au courant pour m’expliquer à quel point j’ai tort ?

Bref, pour revenir à des choses plus modestes, l’architecture actuelle du blog utilise également un modèle redondant : les tags sont stockés à la fois dans la table des articles, sous forme dénormalisée, et dans une table tag, à part, associée à entry par la table d’association tagmap :

CREATE TABLE entry (
        -- Champs précédemment décrits...

        -- Listes d'auteurs et de tags dénormalisées :
        e_authors TEXT,
        e_tags TEXT,

        -- D'autres champs...
);

CREATE TABLE tag (
        t_tid INTEGER PRIMARY KEY,
        t_name VARCHAR(255) UNIQUE NOT NULL
);

CREATE TABLE tagmap (
        tm_eid INTEGER NOT NULL,
        tm_tid INTEGER NOT NULL,
        PRIMARY KEY (tm_eid, tm_tid)
);

Rédaction, mises à jour, et Atom

Le dernier point que j’aimerais aborder est une des particularités de mon blog. En effet, on n’écrit pas ses articles directement sur le site Web ! Mais ce n’est pas un blog entièrement statique non plus…

Mon blog est une espèce hybride qui se nourrit de fichiers Atom. En fait, quand bluestorm ou moi poste un billet, il l’ajoute à un fil Atom interne (grâce à un jeu d’outils en ligne de commandes développés en parallèle), et ping le blog pour lui demander de rafraîchir sa mémoire.

Cela peut paraître un peu compliqué pour pas grand chose, au premier abord, mais l’intérêt de cette méthode est qu’elle découple la rédaction et la présentation du contenu… Pas convaincus ? :p Accessoirement, la généralisation de cette approche permet d’importer du contenu d’autres blogs, le but étant au final d’obtenir une espèce de gros annuaire de billets intéressants affiliés à la micro-communauté #sdz.^ζ

ζ : Le concept est différent d’un Planet, qui agrège du contenu trié par date ; ici, le but serait de hiérarchiser, classer les choses intéressantes dans un index global.

Je rappelle au passage aux intéressés, qui se reconnaîtront, que la spéc du format Atom augmenté utilisé pour cette opération de référencement se trouve ici : atom.text

Conclusion

Voilà qui conclut la première partie de cet article. Il me reste pas mal de choses à raconter ; des anecdotes plus légères, plus digestes sans doute pour certains, plus ennuyeuses pour d’autres. J’ai fini de parler de la machinerie derrière le blog. La prochaine fois, je parlerai de la partie directement visible : les questions d’interface, de présentation, de déploiement, tous ces petits ingrédients qui contribuent à créer des petites pages mignonnes et, je l’espère, agréables à lire, pour les visiteurs… sans oublier les robots, moteurs de recherches, et autres joyeusetés qui accompagnent immanquablement tout site Web dans sa vie, ou sa non-vie ! :]

Expression problem (2/3) : dualités somme/produit et fonctionnel/OO

2009-10-11T12:17:16+02:00

Après deux semaines d’absence, le blog reprend vie ! Mais ce n’est, comme trop souvent, pas grâce à moi… mais ça devrait changer bientôt… bref, acclamez le, il est de retour, pour tous les enfants de la terre… chui fatigué moi… comment ça, ça se voit ? :]

—minh

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

Attention, on définit ici une nouvelle donnée int (pour le type ops2) en utilisant l’ancienne donnée int (pour le type ops) : ce n’est pas une définition récursive (absence du mot clé rec).

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).

Expression problem (1/3) : sommes fermées, sommes ouvertes

2009-09-27T15:53:12+02:00

Dans cette période sombre où le blog se meurt,^† un homme est là pour inverser la tendance et remplir nos cœurs de joie et de bonheur (et nos têtes de mots compliqués). Il est là, Alba^Wbluestorm !

† : En fait, j’ai menti, le flux de visiteurs est relativement constant depuis le début du mois.

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

α : Ça ne marche sans doute pas par défaut en Haskell, parce que c’est un langage prévu pour être utilisé par des surhommes.

β : Οn dirait un argument de vendeur de dentifrice comme ça, mais je suis sérieux, j’en fais l’expérience régulièrement dans Macaque : on rajoute un cas au type somme et pouf pouf pouf (ou tak tak), il nous conduit à travers tout le code pour rajouter le bon traitement partout où il y en a besoin.

Par contre, pour que cela marche vraiment bien, il faut parfois adapter un chouilla son style de programmation, par exemple éviter les patterns universels là où ils empêcheraient le compilateur de foirer à l’apparition d’un nouveau cas ; parce que typiquement ce nouveau cas n’entrera pas dans le traitement par défaut, on l’oublie et ça fait un bug.

C’est le même genre de bonnes pratiques qui pousse les gens à écrire explicitement tous les champs d’une table SQL quand ils font une requête INSERT.

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.

γ : Quand je parle d’objet c’est au sens intuitif, un truc, ça n’a pas de rapport avec la POO. Ne laissez pas dévaliser votre vocabulaire !

δ : On peut combiner les filtrages pour exprimer joliment des conditions sophistiquées ; insérer un élément dans un arbre bicolore, c’est tout simplement horrible, sauf si on connaît l’implémentation fonctionnelle avec filtrage.

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)))