Jean-Christophe Filliâtre : Programmation

Programmation OCaml

À mes heures perdues, je développe quelques bricoles, principalement en OCaml, un langage fonctionnel disposant d'une excellente bibliothèque standard et d'un compilateur (bytecode et natif) qui peut rivaliser avec gcc. Le code OCaml étant entièrrement portable, vous pouvez recompiler le code ci-dessous sur toutes les plate-formes supportées par OCaml : Linux, un grand nombre d'UNIX commerciaux, mais aussi MacOS, Windows, etc. (sauf lorsque l'on utilise une spécificité d'un système, comme la bibliothèque SVGAlib de Linux).

Sauf mention explicite du contraire, tout le code disponible sur cette page est distribué selon les termes de la GNU Library General Public License version 2, avec une exception concernant l'édition de lien, décrite dans le fichier LICENSE.

À propos des liens ci-dessous :

Les .ps sont des fichiers PostScript produits à partir du source OCaml grâce à ocamlweb.
Les .ml et .mli ont été produits avec l'outil caml2html de Sébastien Ailleret (maintenant Martin Jambon).
Cliquer sur le nom de la bibliothèque / de l'application pour télécharger.
Lorsqu'un dépôt github ou un paquet opam existe, il est indiqué entre parenthèses.

Structures de données

Vector : Tableaux redimensionnables (.mli / .ml)
Parray : Tableaux peristants (.mli / .ml) ; voir cet article
Puf : Union-Find persistant (.mli / .ml) ; voir cet article
Creal : arithmétique réelle exacte
Bitv : une bibliothèque de vecteurs de bits (.pdf | .mli | github | opam)
Bitset : petits ensembles d'entiers codés par des vecteurs de bits (.mli | .ml)
Arbres de Patricia : Ensembles et dictionnaires efficaces sur les entiers (.pdf | ptset.mli | ptmap.mli), à partir d'un papier de Chris Okasaki
Voir aussi les modules Hashcons, Hset et Hmap ci-dessous (pour utiliser les arbres de Patricia lorsque l'on fait du hash-consing)
Trie : Dictionnaires sur des listes (.ps | .mli | .ml)
Heaps : (tas = files de priorité)
- structure impérative classique utilisant un tableau (.mli | (.ml)
- arbres de Braun (.mli | (.ml)
- tas gauches (leftist heaps) (.mli | (.ml)
Rbset : arbres rouges et noirs (.ps | .mli)
Ce code a été certifié avec Coq; voir cette page>
Hashset : Ensembles codés par des tables de hachage (plus simple à utiliser et légèrement plus compact que l'utilisation du module Hashtbl) (.ps | .mli)
Suffix_tree : Algorithme d'Ukkonen (.mli | .ml)
Ropes : structure de corde (.mli | .ml)
Un éditeur de texte vite-fait, mal-fait et incomplet utilisant les cordes : editor.ml (nécessite ocamlsdl, voir ci-dessous)
Rbuffer : (.mli | .ml) Implantation du module Buffer à l'aide de cordes ; pour des cordes d'usage général, voir ci-dessus.
Poly : Polynômes à coefficients dans un anneau quelconque (.mli | .ml)
Bdd : Diagrammes de décision binaires (.mli | README)

Bibliothèques

Combine, une bibliothèque de cominatoire (avec Remy El Sibaïe) (opam)
Functory, une bibliothèque de calcul distribué, inspirée par MapReduce (avec Kalyan Krishnamani)
OCamlgraph, une bibliothèque de graphes pour OCaml (github | opam)
Mlpost, une bibliothèque OCaml pour dessiner des figures (github | opam)
cgi : une bibliothèque pour écrire des scripts CGI (.mli)
ocamlsvga : interface pour de la bibliothèque Linux SVGAlib
ocamlsdl : interface pour de la bibliothèque graphique SDL; inclus le support OpenGL, pour être utilisé par exemple avec lablGL

Note : il existe un projet similaire plus avancé, OcamlSDL.sourceforge.net
display : visualisation de la représentation interne des valeurs Caml (.ps | .mli)
hashcons : tables de hash pour le hash consing (.ps | .mli | github). Cette technique est décrite dans ce papier.
Hset / Hmap: Modules Ptset et Ptmap (voir ci-dessus) spécialisés sur les valeurs hash-consées (hset.mli | hmap.mli).
prtree : pour imprimer des arbres à la manière de pstree (.ps | .mli)
search : codes fonctorisés pour les recherches en profondeur, en largeur, et en approfondissement itératif (.ps | .mli)

Applications

bibtex2html : convertisseur de BibTeX vers HTML
ocamlweb : un outil de programmation litéraire pour OCaml (opam)
ocamlwc : un programme pour compter les lignes de code et de documentation dans du source OCaml (.ps)
yamlpp : un pré-processeur HTML très simple, inspiré par l'htmlpp de Nicolas Thiéry

Algorithmique

Algorithme de Garsia-Wachs : suit la description faite dans The Art of Computer Prorgamming ; code OCaml décrit en détail dans cet article (.mli / .ml)
Triangulation de Delaunay : implantation de l'algorithme de D. Knuth présenté dans Axioms and Hulls. Complexité : O(N log N) en temps (en moyenne) ; toujours O(N) en espace. S'applique à n'importe quel système CCC (voir Axioms and Hulls). Note : ce module fait partie d'OCamlgraph mais peut être utilisé indépendamment. (.mli)
DLX: Implantation de l'algorithme de D. Knuth Dancing Links (.mli / .ml / .ps)
Voir aussi la bibliothèque Combine.
Knuth-Morris-Pratt : recherche d'une chaîne dans une autre (.mli / .ml / .ps)
Pentaminos : calcul du nombre de solutions
Solitaire : recherche de la solution (solitaire français) (.ps), en collaboration avec Xavier Urbain.
anagram.ml : Anagrammes (.ps). Pour le tester, voici un dictionnaire anglais
koda-ruskey.ml : Implantation de l'algorithme de Koda-Ruskey (.ps), inspiré d'une implantation par D. E. Knuth
Ce code est détaillé dans cet article (en Français) et cet autre article (en Anglais, co-écrit avec François Pottier)

Jeux

Un démineur à vocation pédagogique écrit en moins d'une heure : demineur.ml / download

Publications

Certaines de mes publications, ou matériel pédagogique, en rapport avec la programmation OCaml. (Ma liste complète de publications se trouve ici.)

Type-Safe Modular Hash-Consing (avec Sylvain Conchon, ML workshop, 2006)
A Persistent Union-Find Data Structure (avec Sylvain Conchon, ML workshop, 2007)
Designing a Generic Graph Library using ML Functors (avec Sylvain Conchon, J. Signoles, Trends in Functional Programming, 2007)
A Functional Implementation of the Garsia-Wachs Algorithm (ML workshop, 2008)

Le petit guide du bouturage, ou comment réaliser des arbres mutables en OCaml (2013)
Faire bonne figure avec Mlpost (avec R. Bardou, J. Kanig, S. Lescuyer, JFLA 2009)
Polycopié de cours de Master Informatique (M1) : Initiation à la programmation fonctionnelle. Transparents : DVI (pour Active DVI) / PostScript

Divers

Compilation : configure.in : un script de configuration autoconf pour les programmes OCaml, et une suggestion de Makefile.in
Mon entrée au concours de programmation ICFP Programming Contest 2001 (en anglais)
D'autres participations avec The Caml Riders

J'aime cette définition du mot hacker tirée du Jargon File:

Hacker: One who programs enthusiastically (even obsessively) or who enjoys programming rather than just theorizing about programming.

Quelques pointeurs

OCaml home page
OCaml Package Manager (OPAM)
Le site de Daniel de Rauglaudre contient quelques beaux programmes OCaml, en particulier GeneWeb.

Détente

The evolution of a Programmer

Jean-Christophe Filliâtre (formatté avec yamlpp).