Participer à Batteries, un projet de bibliothèque standard étendue

(contribution à un projet déjà actif, généraliste)

Batteries est uny projet communautaire visant à étendre la "bibliothèque standard" OCaml fournie avec le compilation, qui est minimaliste -- les auteurs du compilateur souhaiteraient qu'elle ne soit plus considérée comme "bibliothèque standard" mais comme "bibliothèque du compilateur", et que la communauté se charge de fournir les outils de base qui vont autour, y compris la bibliothèques standard.

Il y a nombreuses choses à faire dans Batteries et il est très facile de participer. Cela va de choses très ponctuelles, comme d'écrire des tests unitaires pour quelques fonctions -- une activité plus intéressante qu'elle ne le semble de loin, un peu comme les probabilités -- à des tâches plus ambitieuses comme le développement d'une signature unifiée pour décrire les structures de données linéaires (ou les structures associatives), en passant par l'écriture de documentation (une bonne façon de découvrir un projet, mais qui demande des qualités différentes de la programmation pure).

Les développeurs actuels (dont je fais partie, donc je m'envoie des fleurs) sont très ouverts aux contributions extérieures, même venant de gens ayant peu d'expérience de OCaml. Il est facile par exemple de faire accepter un patch qui corrige un bug (il suffit de le soumettre), de proposer un exemple de code pour une fonction (à inclure dans la documentation), etc. Comme le projet évolue en même temps, il faut aussi éventuellement coordonner son développement avec les autres, ce qui est une expérience intéressante.

Contribuer à ocamlbuild: règles de haut niveau et visualisation de traces

(build manager, bibliothèques haut niveau, visualisation)

OCamlbuild est un "build manager", qui permet de compiler très facilement un petit projet OCaml: on lui indique le "ficher principal" pour créer l'exécutable concerné, et il calcule tout seul les dépendances par rapport aux autres fichiers du projet, sait chercher un .mly pour le mouliner avec ocamlyacc/menhir auparavant, etc. Il permet d'obtenir des choses utiles (documentation de l'API, compilation en mode debug, bibliothèques en forme .cma) sans avoir à manipuler directement les outils sous-jacents, et peut être étendu pour gérer des projets plus compliqués (génération dynamique de code, etc.).

Le cœur de l'outil est un système de build générique, pas intrinsèquement restreint à OCaml, qui permet de spécifier des règles pour déduire des dépendances à partir d'un fichier, et comment compiler ces dépendances.

C'est un projet assez jeune, présent dans OCaml seulement depuis la dernière version (3.12), et qui peut encore évoluer. Il y a plusieurs choses sur lequel il est possible de travailler pour l'améliorer, entre autres (mais n'hésitez pas à demander d'autres choses si travailler sur l'outil vous intéresse):

• ajouter des règles haut niveau qui correspondent à ce qu'on peut vouloir faire dans certains cas courants
• une façon commode de visualiser les "traces", l'ensemble des les règles déduites et appliquées dans une compilation donnée, pour l'utilisateur qui parfois se demande pourquoi l'outil n'a pas fait ce à quoi il s'attendait

Tests aléatoire à la QuickCheck : travailler sur Kaputt

(test aléatoire, bibliothèque de combinateurs, monades)

QuickCheck est une bibliothèque qui vient du monde Haskell et qui permet de faire de la génération aléatoire de tests -- elle a depuis été portée, sous une forme ou une autre, dans la plupart des langages de programmation. Imaginez que vous avez codé une fonction de concaténation de liste "concat".

L'idée est qu'au lieu de vérifier par exemple, sous forme de tests unitaires: concat [1; 2] [] = [1; 2] concat [1; 2] (concat [3] [4]) = [1; 2; 3; 4]

Vous pouvez formuler les propriétés à tester comme des propriétés logiques ("théorèmes à vérifier"): ∀a, concat a [] = a ∀a b c, concat a (concat b c) = concat (concat a b) c

Dans un monde idéal on pourrait prouver formellement ces propriétés en raisonnant sur les programmes. En attendant, on fait des tests aléatoires: on vérifie la propriété ∀a.P(a) en générant mettons 1000 listes au hasard, et en testant le prédicat P sur chacune d'entre elles.

Cette approche de test est meilleure que les tests unitaires dans certains cas car elle peut tomber par hasard sur des cas qu'on n'aurait pas pensé à vérifier directement. Elle est aussi plus coûteuse en temps, et en pratique il faut pas mal jouer sur les distributions de probabilités des objets générés pour que ce soit intéressant (par exemple, il faut que la liste vide revienne souvent, car c'est souvent un cas limite qui fait foirer les programmes; si on générait une liste aléatoire en tirant un nombre uniformément entre 0 et 2^30 ça n'arriverait pas).

Kaputt est une bibliothèque existante en OCaml qui permet de faire ça, développée par Xavier Clerc, et sur laquelle il y a des choses à faire. C'est une bibliothèque de combinateurs, et il y a moyen de faire des choses jolies et intéressantes:

• Il y a un lien concret avec l'écriture de formules logiques de premier ordre, qui peut guider la conception vers des choses élégantes, mais avec des subtilités parce que le résultat d'un essai aléatoire n'est pas une simple valeur booléenne: on veut dire "le test a réussi" ou "le test a raté", mais aussi "ce tirage aléatoire n'est pas un cas intéressant, retourne en arrière pour choisir une autre entrée, mais ne compte pas ce test comme une réussite parce qu'il n'est pas représentatif".

• Si vous connaissez ce concept, la génération aléatoire de valeurs forme une monade, et cette structure algébrique peut influencer la conception d'une interface (par exemple en utilisant naturellement les fonctions monadiques habituelles sur les structures de donnée).

• Il y a tout de même des contraintes de "performance", il faut explorer le plus grand espace de recherche possible en le moins d'essais possibles. Ça veut dire que toutes les façons d'exprimer un test ne se valent pas (il vaut mieux savoir qu'il faut essayer autre chose le plus tôt possible) et que, par exemple, l'interface monadique n'est peut-être pas une bonne approche si elle encourage des utilisations moins efficaces.

Le test aléatoire est pour l'instant relativement peu utilisé dans la communauté OCaml; si vous arrivez à produire quelque chose d'intéressant et solide, même assez simple, et qu'on fait de la pub dessus, il y a moyen de faire entrer cette technique dans les méthodologies de développement habituelles, et donc d'avoir un impact important.

Une bibliothèque de parallélisme à "packager"

(packaging, programmation système, concurrence à mémoire partagée)

Jérôme Vouillon, l'auteur d'un des solveurs SAT, de jsofocaml, d'une bibliothèque de regexp qui va nettement plus vite que PCRE, etc., a aussi dans ses cartons (je cite) "une petite bibliothèque de parallélisme" qui pourrait intéresser d'autres gens, mais qu'il n'a jamais eu le temps de dégager/isoler/packager pour la présenter.

Si ça intéresse des gens, c'est un projet sans doute de plus courte durée que d'autres (il n'y a pas forcément d'effort de développement nécessaire, même si Jérôme a certainement des idées d'extensions possibles etc. si ça vous tente), mais qui peut permettre de se familiariser avec le domaine.

Je ne connais pas cette bibliothèque moi-même donc j'ai assez peu de détails. Je sais que c'est une bibliothèque faisant de la concurrence à mémoire partagée (donc sur du multi-core mais pas de calcul distribué sur un cluster par exemple) qui permet à un processus de surveiller et réordonner les répartitions des tâches de travail.

(Par contre, pour cette bibliothèque je ne sais pas très bien qui seraient les utilisateurs potentiels.)

Contributions à Cryptokit, par exemple un algorithme de padding pour RSA

(cryptographie, bas niveau, programmation C)

Cryptokit est une bibliothèque de cryptographie, écrite par Xavier Leroy, qui permet d'utiliser les algos de crypto classique (AES, DES, RSA, hashs etc.) depuis OCaml avec un style relativement haut niveau de "composition de transformations". C'est une bibliothèque d'excellente qualité, écrite dans un mélange de C et de OCaml (personne n'est parfait, mais pour la crypto on y échappe difficilement), et qui est efficace – pour une implémentation logicielle portable.

Xavier a des idées de choses qui pourraient être ajoutées; par exemples des algos de "padding" pour RSA ont été demandés par un utilisateur, et qui répondent aux doux noms de "PKCS 1.5" et "OAEP". C'est un projet assez spécialisé, mais qui peut être très enrichissant si voulez vous intéresser à la crypto par la suite.

Compilation séparée pour jsofocaml

(compilation, linking, javascript)

js_of_ocaml est un compilateur qui prend en entrée du bytecode OCaml et qui produit du Javascript. Ça a l'air absurde de loin, mais ça permet de faire tourner du code OCaml dans un navigateur web, une technique de déploiement des applications de plus en plus à la mode. Si on combine en plus les astuces magiques de son auteur, Jérôme Vouillon, et les centaines d'années-efforts investis par Microsoft, Apple, Mozilla et Google dans la course au moteur Javascript le plus rapide, on obtient une technique de compilation de programmes OCaml qui donne des performances pas du tout ridicules: plus rapide que l'interpréteur bytecode, moins rapide que le compilateur natif.

js_of_ocaml travaille actuellement comme un "whole-program optimizer": il prend l'ensemble des modules bytecode à combiner pour avoir le programme complet, les passe à la moulinette et produit un gros blob de JS. Ça permet de faire tourner des optimisations intéressantes (élimination de code mort en particulier), mais ça a l'inconvénient qu'à chaque fois qu'on change un fichier .ml, c'est tout le code du programme qu'il faut recompiler.

Il serait intéressant de voir comment permettre la "compilation séparée" pour jsofocaml. Pour chaque module (compilé en bytecode), on produirait un fichier .js séparé, et on inclurait à la fin un bout de code qui branche ces .js les uns avec les autres – jouant le rôle du "linker" pour les programmes compilés vers l'assembleur.

C'est un excellent projet si vous voulez vous intéresser à la compilation: il faut comprendre les grandes lignes des techniques de compilation de js_of_ocaml (sans avoir besoin d'être un expert), et les problématiques de linking sont souvent plus intéressantes qu'il n'y paraît. Il faudra aussi peut-être se poser des questions sur l'interaction entre compilation séparée et certaines des passes d'optimisations (en particulier l'élimination de code mort), éventuellement les restreindre ou les désactiver.

js_of_ocaml est utilisé assez sérieusement par les gens de la communauté (il y a par exemple une startup qui écrit en OCaml des outils de manipulations de WebGL), et la question de la compilation séparée reviendrait souvent et aurait un impact positif sur tous les utilisateurs.

Une bibliothèque d'entrée/sortie haut niveau pour Bigarray

(bibliothèque, bas niveau)

En raison de choix d'implémentation sur la représentation en mémoire des chaînes de caractères OCaml (le type string), celles-ci sont limitées, sur les architectures 32 bits, à une taille de 16Mio maximum: leur "header" qui contient des informations pour le GC, etc., en plus de leur taille, tient sur un mot machine.

Les gens qui manipulent de grosses quantités de données (par exemple Unison, un programme de synchronisation de fichiers, ou les gens qui font de la bio-info et manipulent des données ADN) doivent parfois contourner cette limitation en utilisant d'autres types. Un choix classique est d'utiliser les "bigarray", des tableaux d'entiers qui sont gérés de manière spécifique pour avoir la même représentation que les tableaux C ou Fortran – ce qui est utile pour les bindings inter-langages. Il est possible par exemple d'utiliser l'appel système mmap pour efficacement récupérer des données dans un bigarray.

Ce choix peut se révéler gênant en raison du manque de fonctions de haut niveau sur Bigarray: il y a des fonctions bas-niveau (suffisant pour les cas d'utilisations courants de Bigarray qui sont eux-mêmes bas-niveau), mais si on veut juste s'en servir pour remplacer les string on se rend compte que des choses bien pratiques comme print_endline par exemple manque à l'appel.

Une bibliothèque d'entrée sortie utilisant des bigarray comme type de données de base plutôt que string pourrait donc trouver des utilisateurs intéressés.

Dans le Garbage Collector (GC) OCaml, traiter par paquet les valeurs à vieillir (caml_oldify_one)

(très bas niveau, code entièrement en C)

Le GC de OCaml est dit "générationnel": il stocke la mémoire utilisée par le programme dans deux tas séparés, appelés "tas mineur" et "tas majeur", correspondant à une "jeune" et une "vieille" génération de valeurs. L'idée est que dans un programme fonctionnel, la plupart des valeurs ont une courte durée de vie, et on a intérêt à optimiser un GC pour être très rapide sur les valeurs libérées presque aussitôt après leur création. Avoir deux tas, avec un tas mineur assez petit, permet d'utiliser des algorithmes de récupération de mémoire différents des deux côtés, celui du tas mineur étant pensé pour maximiser la vitesse d'allocation, et celui du tas majeur pour permettre une collection incrémentale d'une potentiellement grande quantité de mémoire.

On observe expérimentalement que certains programme OCaml passent une partie importante de leur temps à déplacer des valeurs du tas mineur vers le tas majeur (quand elles ont survécu à un certain nombre de collections). La fonction caml_oldify_one (définie dans byterun/minor_gc.c) traite, comme son nom l'indique, les valeurs une par une (pour parcourir tout le sous-graphe accessible depuis une valeur à faire vieillir, les valeurs vers lesquelles elle point sont stockées dans une liste de valeurs à faire vieillir ensuite). La question se pose de savoir si une fonction caml_oldify_many, qui fait vieillir une séquence de valeurs "d'un seul coup", pourrait améliorer les performances en mettant en commun certains tests qui sont aujourd'hui faits pour chaque valeur.

Pour l'instant je n'ai aucune idée de si cela pourrait améliorer les performances, ou si ces parties que l'on pourrait mettre en commun prennent de toute façon un temps négligeable aujourd'hui par rapport au reste des tâches à effectuer dans cette fonction. Le premier travail serait d'utiliser des outils de profiling pour estimer les gains potentiels. Le code en question est très bas niveau et assez compliqué, donc il ne sert à rien de le modifier au risque d'ajouter des bugs très pénibles à débugguer si on n'est pas certain de gagner en performances de façon sensible...

Projets terminés ou en cours

Implémentation des "Hash Array Mapped Trie" de Clojure en OCaml

(algorithmique, structures de données)

Les HAMT sont une structure de table associative qui est à la base d'une grande partie de la bibliothèque standard du langage Clojure: un dialecte Lisp qui tourne sur la JVM, orienté vers la concurrence et qui privilégie donc les structures de données persistantes (~fonctionnelles pures). D'après les gens de Clojure, ça va plus vite dans leur cadre que les arbres balancés classiques (rouge/noir, AVL...).

(En très gros, il s'agit d'un arbre de recherche à gros branching factor (32 ou 64), qui ne contient pas de bookeeping pour assurer qu'il reste balancé mais hashe les clés avant de les comparer (et donc obtient un truc plutôt uniforme), et qui utilise une astuce pour que les nœuds allouent une mémoire proportionnelle au nombre d'enfants présents seulement, et pas le branching factor maximum, pour améliorer la localité.)

Récemment d'autres langages fonctionnels ont testé l'implémentation de cette structure et se sont montré satisfaits (performances comparables voire supérieures à celles des structures utilisées par la bibliothèque standard du langage): Scala, puis une expérimentation en Haskell. Est-ce que ça pourrait marcher en OCaml aussi ?

Il y a plusieurs facteurs qui peuvent jouer sur l'intérêt ou pas d'une structure de données (représentation des données dans le langage, compromis faits par l'algorithme de GC...), et il n'est pas clair du tout qu'elle soit intéressante en OCaml, c'est à voir. Mais si c'est le cas, pour la personne qui l'a implémentée, c'est la gloire.

État du projet :

"Faire sortir" Pprint, une bibliothèque de pretty-printing

(Pretty-printing, bibliothèque de combinateurs, évaluation stricte et paresseuse)

Pprint est une bibliothèque de pretty-printing, c'est-à-dire l'affichage "joli" de données structurées (typiquement du code source) avec sauts à la ligne, indentation qui va bien, etc.

C'est un domaine pas si simple car il faut à la fois permettre au programmeur un contrôle très fin sur la sortie ("oui, je veux des '|' devant chaque ligne, mais pas la première, qui doit du coup être indentée de 4 plutôt que 2 pour s'aligner avec le reste") tout en restant simple à utiliser.

Pprint est une bibliothèque de combinateurs: elle expose un petit nombre de fonctions "axiomatiques" qui ont un rôle simple mais puissant, que l'on peut composer les unes avec les autres pour obtenir ce qu'on veut. Elle part du principe qu'un document structuré peut se voir comme un ensemble de "boîtes" imbriquées. Les combinateurs d'affichage combinent ces boîtes, et peuvent se comporter de façon différente selon que la boîte dans laquelle ils se trouvent tient sur une ligne ou qu'elle doit être découpée, avec une sous-boîte par ligne. Cette idée simple permet d'obtenir de bons résultats avec une manière agréable à programmer.

La bibliothèque, écrite par François Pottier, a une histoire intéressante : cette idée de pretty-printing par boîtes vient du monde Haskell, où elle a été proposée sous forme d'une "functional pearl" qui utilise l'évaluation paresseuse de façon très astucieuse (ou "magique", ou même "assez incompréhensible") pour faire juste ce qu'il faut. Au lieu de garder la version paresseuse, François a essayé de comprendre à quel ordre d'évaluation strict cela correspondait, et est arrivé ainsi à un algorithme très différent, qui consiste essentiellement à interpréter les commandes d'une "machine virtuelle d'affichage". Bref, sous le capot, la bibliothèque est écrite de façon intéressante.

Il y a un ensemble de combinateurs bas niveau qui marche bien, mais on peut vouloir écrire par dessus des fonctions utilitaires qui font des choses courantes dans les cas simples; il y en a déjà certains (pour afficher par exemple des tuples, des listes) mais il serait intéressant d'en rajouter ou de les restructurer. François est à la recherche de quelqu'un que ça intéresse, et qui puisse éventuellement s'occuper de faire une sortie officielle du projet -- pour l'instant il est quelque part sur sa page web, pas très visible.

État du projet

Un ensemble de benchmarks représentatifs pour OCaml

(benchmarks, considérations de performances sur code compilé)

Un problème récurrent dans le développement du compilateur est le suivant: quelqu'un vient avec un patch un peu compliqué qui "produit du meilleur code assembleur dans tel et tel cas". Comment savoir s'il faut accepter ce changement, avec les coûts de maintenance et les risques de bugs qui vont avec ? Il est facile de produire du meilleur code sur un micro-benchmark, mais dans une situation qui ne se rencontre jamais en pratique dans les programmes réels, et dans ce cas le changement n'est pas intéressant -- voire contre-productif.

Pour l'instant, on répond à cette question de façon un peu ad-hoc: on teste d'abord sur le compilateur OCaml lui-même (est-ce qu'il va plus vite), puis sur un projet gros et connu (par exemple Coq, ou Frama-C); éventuellement la personne qui propose le patch présente un cas d'utilisation plausible, par exemple dans son code, où ça fait une grosse différence -- mais malheureusement c'est rarement le cas.

Un problème de cette approche est qu'elle a tendance à favoriser certains types de programmes, par exemple ceux qui font de la manipulation symbolique, au détriment d'autres programmes (calculs numériques...) ou styles de programmation qu'on n'a pas pensé à tester.

On manque d'un ensemble de benchmarks représentatifs des "programmes OCaml" en général, qui permette d'évaluer l'intérêt d'un changement du compilateur. Ça a l'air tout bête, mais en fait c'est quelque chose de délicat (trouver et isoler des bouts de code représentatifs dans des applications existantes, voire les écrire) et qui demande du travail pour être utilisable. C'est donc un projet qui n'est pas directement orienté "écriture de code" mais qui peut être intéressant, en particulier pour en apprendre plus sur la façon dont sont compilés les programmes OCaml.

État du projet