Blog personnel d'Arthur Milchior

Plus précisément, j'ai voulu créer des pages sur les structures de données purement fonctionnelles. C'est un sujet que je trouve très joli, et j'ai justement profité des vacances pour lire Purely functional data structures de Chris Okasaki. Ce livre à 17 ans et mériterait bien une deuxième édition afin d'être mis à jour^[1] puisque j'ai appris via Wikipédia que de nouvelles structures purement fonctionnelles plus efficaces ont été découvertes^[2] depuis.

Le premier problème^[3], c'est que la page purely functional existe. Sauf que, elle ne devrait pas. D'ailleurs, c'est ce qui est dit dans les discussions^[4], cette page n'a pas de sens. On pourrait parler de langages purement fonctionnels. De structures de données purement fonctionnelles. De programmation purement fonctionnelle. Mais «purement fonctionnel» tout seul, ça ne veut rien dire. Et même si en 2009 et 2013 des gens ont dit que la page devrait être supprimé, personne n'a fait la demande formelle, ce qui dans leur jargon se nomme un AfD, Article for Deletion. Je m'en suis donc chargé. Les avis semblent être «on ne supprime pas, on va juste en faire autre chose», sans consensus sur ce qu'est cet autre chose. L'un propose de merger avec «transparence référentielle», un autre avec «programmation fonctionnelle». Et encore un propose de couper l'article en deux entre langage purement fonctionnel et structure de données purement fonctionnelle. Je trouve cette dernière proposition assez marrante. L'article «purely functional» est petit. Un tiers de l'article est un exemple, hors-sujet, et que des gens avaient déjà dit être mal choisi. Et un autre tiers contient juste des liens, qui sont d'ailleurs pas toujours pertinent.

Ce qui amène à un autre problème, la page programmation fonctionnel est déjà très longue, très documenté, et contient tout ce qu'il faut sur la programmation purement fonctionnelle. On dirait même que l'introduction parle plus de purement fonctionnel que de fonctionnel. Et j'ai AUCUNE envie de toucher à cette page, qui a déjà une longue page de discussion, avec quelques controverses, dont une assez fort pour qu'un éditeur dise qu'une phrase de l'article le fasse vomir (ce qui, sur un tel sujet, me semble très surprenant.) Bref, je ne vois pas ce qu'on pourrait prendre de «purement fonctionnel» pour mettre dans cette page.

Structures de données purement fonctionnelles

Je commence donc à prendre l'article «purement fonctionnel», et m'en inspirer pour en faire un article «structure de données purement fonctionnel». Sauf que je trouve triste qu'il y ait peu de telles structures à mettre en exemples. Pour l'instant, il n'y a presque des structures qui sont naturellement purement fonctionnelle, comme les piles ou les arbres binaires de recherches. C'est pas super intéressant d'avoir des exemples qui sont purement fonctionnel par hasard, le vrai intérêt de cette page, et du livre mentionné plus haut, c'est que parfois, choisir purement fonctionnel a des avantages ET des inconvénients. Bref, que ça demande au programmeur de vraiment faire un choix. Or, la seule structure listée sur la page actuellement est la VList.

VList

Une petite note sur la VList. D'abord, elle a l'avantage de n'être effectivement pas une structure utilisé hors du monde purement fonctionnel, donc d'être un exemple potentiellement pertinent. Elle a par contre le désavantage de n'être pas non plus utilisé dans le monde purement fonctionnel. Et pour une raison toute simple, il n'est pas possible de créer cette structure dans le monde purement fonctionnel. Ce qui amené son découvreur, Phil Bagwell, à demander - arguments à l'appui - à ce qu'on rajoute ça comme brique de base des langages purement fonctionnels. Pour l'instant, ce n'est pas fait. À part dans le langage créé par M. Bagwell afin d'illustrer l'efficacité de cette structure.

Cette structure de donnée prétend être une liste, persistante, avec un accès en lecture en temps constant en moyenne à n'importe quel élément. Si vous comprenez pas, dites vous juste que c'est un truc souvent utilisé, avec des propriété sympathiques et qu'on sait pas avoir en général^[5]. Je me demande donc pourquoi je n'en avais jamais entendu parler. Je vais alors lire l'article originale. Et là je réalise - si j'ai bien compris - que ce qui est passé sous silence, c'est que le temps constant en moyenne ne tient QUE SI la persistance n'est PAS utilisée. Autrement dit, il y a deux propriétés sympathiques, mais il faut choisir l'une ou l'autre. En tout cas, c'est ce que je crois comprendre, ce que les discussions de l'article Wikipédia semblent dire.

Notons en passant, à la décharge des VList, que ça ne serait pas la première structure de donnée persistante OU efficace. Les queue amorties, par exemple, en sont un exemple simple. Il se trouve que les queues temps-réel corrigent ce problème, mais, pour autant que je sache, il n'est pas corrigé pour les random-access list^[6]. Bref, en soit, c'est un défaut qui n'est pas rédhibitoire, mais encore faut il le mentionner explicitement. Ici, l'article Wikipédia, et l'introduction de l'article original, ne mentionnent que les cotés positifs.

De toute façon, l'article original, de recherche, ne contient aucune preuve. Il contient des résultats d'expérience, mais sans expliquer quels expériences exactes sont faites, donc ce n'est pas très utile. Ce qui n'est pas grave d'un point de vue de recherche, puisque c'est un papier de conférence, et que c'est donc sensé être un travail en cours, pas un papier définitif. Bref, aucun article, ni Wikipédia, ni l'original, ne sont clair. Et il y a dans les discussions sur Wikipédia des questions à son sujets, posées en 2006, auxquels personne n'a répondu.

Les humains derrières tout ça.

Ça va être encore plus dur d'avoir des réponses que Phil Bagwell, le découvreur des VList, puisqu'il est mort il y a 4 ans. Non pas que s'il était mort plus récemment ça serait mieux. Et de toute façon, il est mort 12 après son article parlant des VList, donc je suppose que s'il n'a jamais publié à leurs sujets depuis, il y a d'autres raisons. Et pourtant, j'hésite à faire une demande de suppression de l'article VList, car j'ai quelque part l'impression bête que ça serait manqué de respect à un mort.

Une petite note en passant. Pour ceux qui seraient gêné(triggeré) par des histoires de chantages/de rumeur de sexe/et de mineur.... je ne mettrai pas sur ce blog le mot qui désigne l'union de ces deux derniers sujets ..., merci de passer au paragraphe suivant. J'ai voulu regarder le profil de l'auteur original de l'article et voir s'il pouvait améliorer l'article. Il a été banni de manière définitive de tout le projet commons (Wikipédia et tout ce qu'il y a autour), et il était admis de Wikipédia. Ma curiosité a voulu savoir pourquoi il était banni... Je sais que certains n'aiment pas Wikipédia, que Wikipédia a bien des défauts. Mais je n'imaginais pas que des sites entiers (au moins deux) étaient dévolu à dénoncer les abus et «crimes» de la direction de Wikipédia. Et ces sites sont totalement capable, et c'est leur but, de faire que quand on recherche un nom d'administrateur, on trouve d'immondes rumeurs. Je n'ai pas vu de preuve pour étayer ces accusation - ils disent que les admins les ont supprimés - et je n'ai rien lu qui me suggère que ceux qui écrivent ces rumeurs aient fait part de leurs soupçons/certitudes aux autorité judiciaires. J'ai trouvé ça effrayant parce que, même si je savais théoriquement que la réputation en ligne - c'est à dire la réputation aujourd'hui - était quelque chose de fragile, je n'avais jamais vu moi même ça en fonctionnement. Et je ne m'avais jamais vu moi même être convaincu par ces sites, au point qu'il me faille attendre au moins une heure pour qu'un déclic se fasse et que je me dise que je n'ai rien qui m'indique que ces accusations ont quoi que ce soit de véridiques. Me dire que, pour ce que je sais, il est plus probable qu'ils ont inventer les copies de logs IRC qu'ils nous montrent. Et qu'il restait, même avec ses logs, peu probable que les programmes créé pour aider les jeunes à éditer Wikipédia servent aux admins à rentrer en contact avec ses jeunes dans des buts non précisés.

Et c'est horrible, parce que ces accusations sont à coté de trucs crédible, et probablement vrai. Sur plus d'un millier d'admin, par exemple, ça serait mémé étonnant qu'il n'y en ai aucun qui ait cherché ce poste avant tout pour avoir un truc impressionnant à mettre sur un CV, et pas pour améliorer Wikipédia. (Et encore, vu le processus qu'il faut passer pour être et pour rester admin, ça ne me parait pas évident que ça soit une idée courante).

Des vrais structures de données purement fonctionnelles

Histoire qu'il y ait des structures de données purement fonctionnelles, qui soient reconnus par la communauté, et qui ne soient pas triviales, j'ai décidé de rajouter une description des queues temps-réel, des queues à deux bouts temps-réel. J'ai aussi voulu faire les listes à accès aléatoire. Sauf que les implémentation purement fonctionnelles efficaces de ces listes sont basée sur les représentations skew binaire des nombres. J'ignore comment cette représentation se nomme en français. Alors, pour une fois, l'article était déjà là, il a juste fallu l'améliorer, et rajouter des choses qui étaient absentes. En particulier, plutôt que de dire qu'il n'y a qu'un nombre a changer, il est plus pertinent de dire que le changement se fait en temps constant sur les représentations sparses^[7]. Ce qui nécessite de créer un article sur les représentation sparse des nœuds.

Les représentations sparses des nombres.

Et là, encore un problème. Il est dur de trouver des sources sur les représentations sparses. D'abord, parce que google renvoie beaucoup plus de liens vers les matrices sparses, qui sont pour le coup un sujet très important du calcul numérique. Et que même quand j'obtiens des nombres au lieu d'obtenir des matrices, et bien j'obtiens des nombres sparses, alors que je veux des représentation sparses de nombres. Les nombres sparses, ceux dont la représentation binaire n'ont pas deux bits consécutifs à 1, n'ont d'ailleurs pas de page Wikipédia. Mais là, j'ai pas envie d'en faire, car je ne sais pas à quoi ça sert, à part à faire des jeux mathématiques. Et même si je soupçonne que c'est très pratique en théorie de l'information/théorie des codes, par exemple car représenter deux 1 d'affiler pourrait causer un bug, je n'en sais pas assez, je ne veux pas inventer, ni même passer du temps à chercher.

En même temps, c'est assez normal que je ne trouve pas grand chose sur les représentations sparses. Parce que même si la fonction successeur s'y fait en temps constant, cela n'est pas très utile en pratique, vu que la fonction successeur se fait aussi en temps constant en pratique sur les processeurs actuels. Je n'ai pas fait de test, mais je doute que la représentation sparse fasse vraiment gagner du temps, à moins de travailler sur des nombres qui font, au moins, des milliers de chiffre. Ce qui est assez rare il me semble. Et même si ça arrivait souvent, ça règle uniquement la question du successeur, l'addition se fait toujours en temps linéaire en la longueur des nombres, et quant à la multiplication, je n'ai rien trouvé, et pas osé y réfléchir.

Bref, tout ça pour dire, c'est un peu dur de justifier sur Wikipédia l'article des représentations de nombres sparses. Et si j'ai bien trouvé une source différente de Okasaki, j'ai un peu triché, puisque cette source citait Okasaki. Parce qu'il utilisait aussi les représentations des nombres comme guide pour implémenter une structure de donnée efficace. Notons en passant qu'une partie de mon ancien laboratoire s'occupe de représentation des nombres, il y a donc une solution simple: me renseigner la prochaine fois que j'y retourne.

Les articles généraux.

Puisqu'il y avait une majorité de gens proposant une page de redirection plutôt qu'un article «purement fonctionnelle», encore fallait-il avoir des choses vers quoi rediriger. Il est théoriquement possible, mais pas recommandé, de rediriger vers des articles qui n'existent pas. J'ai donc pris mon courage à deux main, suivi les recommandations Wikipédia de créer de manière audacieuse, et, malgré mon anglais, j'ai créé une page sur la programmation purement fonctionnelle, et un article sur les structures de données purement fonctionnelles. Dans ce dernier article, je pouvais d'ailleurs enfin y lier des exemples naturels et intéressants que j'avais créé plus tôt.

J'ai donc remplacé la page «purement fonctionnelle» par une page de désambiguiation. Et ça a été mon premier revert, la première fois que quelqu'un annule une modification que j'ai fait. Parce que, d'abord, la discussion n'était pas fini. Et de toute façon, il y a près d'une cinquantaine de page qui renvoyaient vers «purely functional», or les liens ne doivent pas renvoyer vers de la désambiguation, sauf exception^[8]. Il fallait donc rediriger tout ces liens vers la bonne page, en fonction de si purement fonctionnel fait référence à un langage, une structure de donnée, un paradigme ou une fonction.

Et c'est pas si simple que ça, car parfois, je ne trouvai pas le lien vers l'article «purement fonctionnel». Parfois, c'était parce que le lien pointait vers une page qui, elle-même, redirige ait vers purely-functional. Ce problème disparaissant quand la redirection est corrigé, mais ce n'était pas évident. Parfois, le lien était dans un template, il fallait alors comprendre qu'il fallait aller regarder le code du-dit template au lieu de regarder le code de la page qui appelle le template. Et enfin, parfois, le lien était totalement introuvable. Et j'ai laissé tombé. J'ai finit par comprendre quand j'ai eu un conflit d'édition; c'est à dire quand, en validant, Wikipédia me dit qu'entre temps, quelqu'un avait modifié la page. Parce que nous étions en fait, au moins deux, et je soupçonne trois, à faire ça en parallèle.

Conclusion

Bon, ça n'a pas totalement arrêté le débat de la page de suppression. Parce que quelqu'un prétendait que, il y a quand même un lien entre programmation, langage, fonction et structure de donnée purement fonctionnelle, donc que si une page existe, il faut qu'elle résume ce qui lie tout ces sujets. Sauf que vu que, pour l'instant, aucun article/texte n'explique clairement ce qui relie tout ça, un tel résumé serait du travail original, ce qui est interdit dans Wikipédia ! Et puis, aucun des informaticiens de la discussion ne se sentait capable de faire un tel article, et le seul à défendre l'article général était le seul à dire ne pas connaître le sujet dont on parle.

Il n'est pas permis d'avoir une page de désambiguation pour un terme T si elle se contente de renvoyer vers toutes les expression qui contiennent T. La règle est qu'il faille que quelqu'un, sans contexte particulier, puisse appeler chacun des objets «T». C'est ce qui justifie sa place sur la page de désambiguation. Il y a donc eu un «débat», où certains tentaient de justifier que dans la phrase «Haskell est purement fonctionnel»/«les piles sont purement fonctionnelles», il n'y avait pas besoin de contexte, tandis que d'autres disaient que le contexte indiquait clairement qu'il s'agit d'un langage/d'une structure de donnée purement fonctionnel, donc qu'on est dans le cas du sous-terme.

Deux solutions magnifiques se sont offertes à ces deux problèmes. En loi des marques américaines «purely functional» fait référence à functionality doctrine, qui n'a rien à voir avec le schmilblick. Cela justifie donc la désambiguation et rend impossible la page générale.

Et une deuxième solution, encore plus jolie, s'est offerte. La discussion avait lieu sur la demande de suppression de la page. Or, presque tout le monde était d'accord sur le fait que la page ne doit pas être supprimée. La discussion pouvait donc être close, savoir si on faisait une page de désambiguation ou un résumé global était hors-sujet. Celui qui a fermé la discussion a quand même dit que si on voulait en parler on pouvait, dans la page de discussion de l'article «purement fonctionnel». Mais, personne l'a fait, et plus personne n'a contesté quand il a remplacé la page «purement fonctionnel» par une page de désambiguation !

P.S.

On me demande parfois pourquoi je ne créé des pages que en anglais. Vous avez vu le boulot que ça m'a pris, pour faire les choses biens. J'ai vraiment pas le courage de faire ça deux fois. Et puis je me dis que quelqu'un qui s'intéresse à un sujet aussi technique n'a de toute façon pas le choix de parler anglais dans le monde académico-industriel actuel. Donc je doute que créer les même articles en français ne servirait à rien.