Ours & Hippy — le blog [macaque]

En ces périodes d’activité intense, il est de plus en plus difficile de prendre le temps d’écrire un bon gros billet comme on les aime. Je me permets de vous servir ici un billet un peu réchauffé : j’ai écrit un article sur Macaque, et j’en profite pour en parler ici.

Macaque a déjà été mentionné sur ce blog, mais sans vraiment d’introduction concrète. J’espère ici présenter Macaque de façon plus introductive, et surtout vous donner le lien vers l'article (18 pages) et vous inciter à le lire.

Macaque

Qu’est-ce que c’est que Macaque ? Puisque la paresse préside ce billet, je me permets de citer, verbatim, le résumé et une partie de l’introduction de l’article.

Macaque est une bibliothèque OCaml permettant d’interagir avec un serveur SQL. Elle permet de construire des requêtes vérifiées statiquement, de façon modulaire. Une extension Camlp4 apporte une syntaxe concrète inspirée des compréhensions. Des types > fantômes sont utilisés pour encoder, en utilisant les types objets d’OCaml, certaines propriétés fines des valeurs SQL, comme la nullabilité.

Les bases de données sont des méthodes solides et reconnues de stockage d’information pour les besoins d’une application. Un programmeur qui voudrait s’en servir est cependant confronté à une situation désagréable : il doit communiquer avec un programme externe (le serveur de base de données) en lui envoyant des requêtes en format texte, c’est-à-dire oublier, dans cette partie de son programme, tout le confort des données structurées et des moyens d’expression de son langage.

La méthode la plus flexible pour construire des requêtes SQL est la production d’une chaîne de caractères correspondant à la requête :

let interroge table predicat =
  "SELECT * FROM " ^ table ^ " WHERE " ^ predicat

Son inconvénient majeur et qu’elle transporte toutes les données sous forme de chaînes de caractères, qui n’apportent aucune information de typage, donc aucune vérification de correction (même syntaxique) à la compilation. En particulier, il y a facilement des problèmes de sécurité si des portions de la requête peuvent provenir d’un utilisateur malicieux du programme.

La méthode la plus sûre pour écrire des requêtes est de vérifier leur validité, au moment de la compilation, en interrogeant directement le serveur SQL, comme le fait le projet PG'OCaml :

let interroge predicat =
  PGSQL(dbh) "select * from ma_table where $predicat"

Pour que cette vérification statique soit possible, la requête doit contenir assez d’information : le serveur PostgreSQL sait vérifier le type des données mais ne dispose ni d’un moteur d’inférence sophistiqué, ni d’une forme de polymorphisme. En particulier, on a dû préciser ici la table étudiée, ma_table. On ne peut pas écrire de fonction générique interroge, qui fonctionne sur n’importe quelle table. On a donc perdu en flexibilité.

Quels sont les compromis acceptables ? Macaque est un langage de requête, embarqué dans OCaml, qui se veut à la fois sûr et flexible. C’est une extension syntaxique couplée à une bibliothèque logicielle à l’interface fortement typée, qui permettent d’écrire des requêtes modulaires en conservant la sûreté à laquelle sont habitués les programmeurs OCaml.

Macaque est un logiciel libre, disponible sur le site OCamlForge.

L’article présente Macaque à des utilisateurs potentiels (Oui, vous !), mais discute aussi de son implémentation. En particulier, la section dédiée au traitement de l’opération GROUP BY décrit les méthodes de métaprogrammation utilisées pour renforcer la sûreté statique permise par le typage.

La petite histoire

J’ai écrit Macaque au cours d’un stage de deux mois dans le laboratoire PPS. Cela ne vous dit sans doute rien, mais beaucoup les connaissent indirectement, car ce sont eux qui hébergent la principale version en ligne du livre « Développement d’applications avec Objective Caml », DA-OCAML pour les intimes, un cours OCaml pas forcément très accessible pour les débutants, mais très complet et qui met les pieds dans le plat de la programmation fonctionnelle.

Une partie des gens de ce laboratoire travaillent sur un ensemble d’outils pour le développement Web dans le langage OCaml. C’est le projet Ocsigen, dont le but est grosso-modo d’apporter la beauté de la programmation fonctionnelle aux sauvages qui codent des sites Web. Comme vous pouvez vous en douter, la diffusion de leur travail est restée plutôt restreinte, mais il y a des choses intéressantes dedans et je vous invite à jeter un coup d’oeil ; personnellement, j’ai abandonné ce terrain depuis longtemps et je ne suis pas impatient d’y remettre les pieds.

Toujours est-il que le sujet qu’ils m’ont proposé était intéressant, puisqu’il combinait beaucoup d’OCaml, du typage, de la métaprogrammation, et plus globalement le travail sur la conception d’une partie d’un langage de programmation, ce qui reste un des points qui me plaisent le plus en informatique.

J’y étais encadré par Jérôme Vouillon, un type très sympathique qui a su m’aider, malgré sa terrible timidité. Sa connaissance du langage OCaml m’a parfois impressionné ; il m’a permis en particulier de résoudre un problème de typage assez velu :

module M : sig
  type 'a t
  val of_option : 'a option -> 'a t
  val to_option : 'a t -> 'a option
end = struct
  type 'a t = 'a option
  let id x = x
  let of_option, to_option = id, id
end

Ce module a l’air tout à fait inoffensif, mais il ne permet pas de conserver le polymorphisme de la valeur None, naturellement de type 'a option :

# let pas_assez_polymorphe = M.of_option None;;
val pas_assez_polymorphe : '_a M.t = <abstr>

Une toute petite modification suffit. Voyez-vous laquelle ?

C’est d’ailleurs un problème que j’aurais dû reconnaître, puisqu’il est mentionné dans un article que j’ai déjà survolé plusieurs fois, Relaxing the value restriction (12 pages).

La rédaction de l’article a eu lieu après le stage proprement dit, et, malheureusement pour moi, sur mon temps libre. Je dirais que cela représente environ 40 heures de travail. Il n’est pas du tout exhaustif, et même pas aussi complet que je l’aurais souhaité : après la première phase de rédaction, une grande partie de l’effort de relecture/retravail avait pour but de le raccourcir pour respecter les contraintes de taille. En pratique, cela constitue à enlever les explications, certains exemples de code, une partie du contenu, et surtout à rogner le plus possible sur les espaces verticaux du document.

Chaque paragraphe a donc été soigneusement retravaillé pour être le moins compréhensible possible, tout en contenant toute l’information nécessaire pour que l’on puisse expliquer à un éventuel critique que s’il n’a pas compris quelque chose, c’est qu’il n’a pas lu assez attentivement. L’étape suivante, utilisée par les copistes avant le septième siècle, est de supprimer la ponctuation et les espaces entre les mots.

Quel futur pour Macaque ?

Je continue à maintenir Macaque sur mon temps libre. La force de développement est donc plutôt réduite, puisque le temps que je lui accorde est faible, mais elle est pour l’instant largement supérieure à la demande : à part le projet Ocsigen, personne ne semble pour l’instant envisager d’utiliser Macaque, et je n’ai donc pas de demandes d’utilisateurs. Pas de retours, pas de développement.

J’ai encore quelques idées de choses à ajouter à Macaque. J’en ai un peu parlé sur le canal IRC #ocaml, et flux m’a fait des remarques qui ont conduit à l’ajout, par exemple, des valeurs par défaut à l’insertion.

Je pense que Macaque est une bonne solution pour le problème qu’il essaie de résoudre : générer des requêtes vers une base de données depuis le langage OCaml. Pour cette raison (et aussi peut-être un peu d’ego), je serais heureux de voir plus de gens s’en servir, profiter de ses qualités, et se plaindre de ses défauts. Je n’ai pas non plus fait beaucoup d’efforts pour populariser Macaque et pousser des gens à s’en servir : j’envisage mollement d’écrire un message consistant à la mailing list OCaml, et ce billet fait lui aussi partie d’une timide campagne de propagande.

Pour ma part, je suis content du travail que j’ai effectué pendant mon stage, et de l’expérience que j’en ai retirée, et je ne m’inquiète pas trop pour le sort des utilisateurs de SQL et OCaml. En plus du projet PG’OCaml déjà cité, d’autres personnes essaient de combiner les deux, dont par exemple quelques divagations sur eigenclass.org, ou le projet Ocaml-orm-sqlite, qui a commencé exactement en même temps que mon stage, mais prend une approche très différente.

En bref, ce n’est pas moi, de mon point de vue, qui décidera du futur (ou pas) de Macaque. Si des gens s’en servent, tant mieux, et je le ferai évoluer vers quelque chose de plus complet, sinon ce n’est pas grave, de toute façon j’ai déjà beaucoup trop de choses à faire.

Comme vous le savez peut-être, mon temps de développement cet été est principalement accaparé par Macaque, un sous-langage spécialisé dans les bases de données (DSL SQL) pour OCaml.

Le sujet n’est pas trivial : il s’agit de permettre d’écrire des requêtes SQL de façon à la fois expressive, composable et typée. Cela recèle tout un tas de problèmes qui me font m’arracher les cheveux, et surtout ça me pousse à sortir des sentiers battus où j’ai mon petit confort, et mettre en place des techniques de programmation un peu plus osées que d’habitude.

Dans ce billet je compte vous présenter une technique parmi celle que j’ai eu l’occasion de mettre en place dans Macaque : le polymorphisme d’ordre supérieur. L’idée est de profiter d’un exemple pratique pour la décrire de façon un peu moins théorique que d’habitude.

Pour profiter du contenu technique de ce billet, vous devez connaître un langage fonctionnel typé. Sinon, vous n’en retiendrez sans doute qu’un discours un peu longuet sur les types abstraits et le choix d’une interface pour des fonctions qui ne sont pas complètement innocentes, mais c’est déjà ça de pris.

Trois remarques avant de commencer. D’une part, évidemment, je ne prétends pas avoir inventé quoi que ce soit : ce sont des techniques^α bien connues des spécialistes en programmation fonctionnelle depuis un certain temps, et je n’y aurai sans doute pas pensé si je ne les avait pas déjà vues en application dans d’autres cas. Mais justement, en voir des applications peut être intéressant pour savoir éventuellement l’utiliser soi-même ensuite, donc je veux partager mon expérience.

D’autre part, ce billet n’est pas un billet de présentation de Macaque (mais je pourrais envisager d’en écrire un; est-ce que ça vous intéresserait ?) : je ne donnerai pas beaucoup de détails d’ensemble, mais juste les informations contextuelle qui permettent de comprendre chaque exemple.

Enfin, vous l’avez sans doute constaté dans ma réaction précédente, j’aime bien développer des points précis dans un second temps, en annexe. Développer… en longueur, et c’est bien le problème : on m’a fait remarquer, et à raison, que mes billets étaient trop longs. J’ai donc choisi de couper celui-ci : je me tiendrai au fil principal dans un premier temps, et je posterai plus tard un second billet pour approfondir des points secondaires. Cela me permettra aussi d’y traiter des questions qui seraient éventuellement apparues en commentaire.^β

Décrire les tables d’une base de données

Ce point ne concerne pas une question d’implémentation directement, mais plutôt une question d’interface. Je m’intéresse à une des fonctions de l’interface publique de Macaque (sql.mli), la fonction table. Cette fonction est utilisée dans la partie de Macaque qui permet de décrire des tables d’une base de données; l’utilisateur doit lui donner des informations sur les champs de la table, qui permettront derrière à Macaque d’en construire une représentation adaptée à ses besoins. Elle renvoie une valeur abstraite (l’utilisateur ne voit pas son contenu) qui représente la table, et quand l’utilisateur voudra utiliser cette table ensuite (pour effectuer des requêtes dessus par exemple), il devra donner cette valeur aux fonctions qui la demandent. De son point de vue, cette valeur de retour de la fonction table joue donc le rôle de certificat, ou témoin : « oui, j’ai bien déclaré la table machin, cette valeur en témoigne ».

Les informations que Macaque demande pour construire la table sont variées, mais celle qui nous intéresse ici est le parser : l’utilisateur doit fournir la fonction qui servira à lire les chaînes de caractères vomies par le serveur SQL quand on lui demande des lignes de cette table, pour en construire de jolies valeurs typées que Macaque pourra ensuite donner à l’utilisateur avec le sourire.

Si Macaque demande à l’utilisateur de lui fournir le parseur, c’est parce qu’il serait difficile de le construire automatiquement : ça voudrait dire utiliser les valeurs caml passées en paramètre à la fonction pour construire un parser; mais alors le type du résultat du parseur dépendrait de ces valeurs, et avoir une fonction qui renvoie un type différent selon les valeurs qu’on lui donne n’est pas possible dans le système de typage Caml, il faudrait des outils théoriques plus puissants. Il y a toujours moyen de s’arranger, mais demander à l’utilisateur de faire le travail reste la solution la plus simple.

Un parser qui renvoie un élément de type 'a est de type 'a parser, qui est un type de macaque ressemblant à string -> 'a, avec un peu plus d’informations. L’utilisateur doit donc écrire une fonction du genre :

let parse_user input =
  object
    method id = parse_id input
    method nom = parse_nom input
  end

En réalité, ce n’est pas lui qui l’écrit, mais une macro qui fait le travail à sa place, mais du point de vue de l’interface de Macaque c’est la même chose. Le problème c’est qu’il ne sait pas comment parser id et nom : les valeurs qu’il faut renvoyer ne sont pas de simples entiers et chaines de caractères, mais des valeurs d’un type interne à Macaque qui contiennent toutes les informations dont il a besoin (type, nullabilité (est-ce que la valeur peut valoir NULL), etc.). Bien sûr, la définition de ce type n’est pas accessible à l’utilisateur : sinon, il pourrait faire n’importe quoi avec, construire de fausses valeurs (qui ne respectent pas les invariants implicites de la structure) et détruire l’univers.

Ce que l’utilisateur a à sa disposition, ce sont des valeurs abstraites qui décrivent le type de ses champs. Il a une valeur de type int sql_type et une valeur de type string sql_type (abstraits, bien sûr), qui contiennent les informations de typage utiles à Macaque, et en particulier la méthode nécessaire pour parser ces valeurs.

Décrire le parser de sa table

Macaque, en interne, sait produire un parser à partir d’un élément de type 'a sql_type; la fonction qui construit ce parser spécialisé à partir de la description du type est ce que j’appelle un parser universel. Mais voilà le problème : je n’ai pas envie d’exposer ce parser universel à l’utilisateur, parce qu’il n’en a normalement pas besoin. Je pourrais la mettre dans l’interface en précisant que l’utilisateur n’a normalement pas besoin de s’en servir (seule ma macro de description de tables l’utilise), mais tant qu’à faire je préfère éviter : un peu de prudence ne peut pas faire de mal. Il ne s’agit pas de l’en empêcher à tout prix : de toute façon au final l’utilisateur peut toujours bidouiller pour faire ce qu’il veut, mais de ne pas l’y encourager.

L’idée, c’est de demander à l’utilisateur : « Bon, d’accord, tu n’as pas accès aux fonctions de parsing des composants de ta table, mais si c’était le cas, comment ferais-tu pour construire le parser de la table entière ? ». On lui demande de construire une fonction témoin avec un type du genre :

universal_parser -> table_parser

S’il produit une fonction de ce type là, on sait qu’il peut parser la table, et on peut prendre la fonction, et ensuite en interne (derrière les coulisses) lui donner un parser universel, pour récupérer le parser de table qui nous intéresse.

Le typage du parser universel coince

C’est là qu’on arrive enfin au sujet promis : le polymorphisme d’ordre supérieur. Quel est le type de la fonction témoin ? On est d’abord tenté de lui donner le type ('a sql_type -> 'a parser) -> 't parser (où 't est le type objet représentant une ligne de la table).

On aurait donc un type pour table (en oubliant les autres paramètres) :

val table : (('a sql_type -> 'a parser) -> 't parser) -> 't table

Mais ça coince vite quand on essaie d’écrire :

let parse_user univ_parser input =
  object
    method id = univ_parser int_type input
    method nom = univ_parser string_type input
  end

On suppose que l’utilisateur a déjà reçu d’autres fonctions les valeurs int_type : int sql_type et string_type : string sql_type. Quand on essaie de compiler notre code, catastrophe : il souligne la valeur string_type et nous répond : Error: This expression has type string T.sql_type but an expression was expected of type int T.sql_type.

Soucis : let-polymorphism et value restriction

Le problème vient du fait que le 'a dans le type de notre fonction doit être "le même" à chaque fois qu’on l’utilise. Si on l’utilise à chaque fois comme une fonction polymorphe, elle reste polymorphe, mais dès qu’on l’utilise sur un type particulier, OCaml infère qu’elle est de ce type là, et nous empêche de l’utiliser sur un autre.

Une autre manière de voir le problème est de considérer la variable de type 'a comme une façon de dire « le type a, quel qu’il soit » : on peut introduire explicitement des quantificateurs (comme en logique), et lire le type

(('a sql_type -> 'a parser) -> 't parser) -> 't table

Comme la formule :

∀ a, ∀ t, ((a sql_type -> a parser) -> t parser) -> t table

Comme le type dont on est parti ne contient aucune information sur la position des quantificateurs, on l’a mis à l’endroit le plus naturel : au début de la fonction. Le problème vient justement de cette position : cela correspond à dire que pour chaque application de la fonction, on fixe 'a et 't au départ : on peut en choisir un différent à chaque mais à l’intérieur du type ils sont fixés, et en particulier la fonction ('a sql_type -> 'a parser) ne peut être appelée plusieurs fois avec un 'a différent.

Polymorphisme d’ordre supérieur en OCaml

On voudrait en fait le type suivant :

∀ t, ((∀ a, (a sql_type -> a parser)) -> t parser) -> t table

J’ai déplacé le quantificateur à l’intérieur de la fonction : à chaque application de la sous-fonction, on peut avoir un nouveau type 'a.

Comment faire comprendre ça à OCaml ? Il faut un moyen de rajouter des informations sur la position des quantificateurs. C’est possible en OCaml, mais seulement^γ pour déclarer deux types de valeurs : les enregistrements et les objets.

On déclare donc le type de notre parser universel, dans un enregistrement :

type univ_parser = { of_type : 'a . 'a sql_type -> 'a parser }

Notez la différence de taille par rapport au type classique

type 'a univ_parser = { of_type : 'a sql_type -> 'a parser }

Le type ne prend pas de paramètre. En effet j’ai placé le quantificateur à l’intérieur (la syntaxe 'a . avant le type), donc le type ne "dépend plus" de 'a, il n’est pas fixé au niveau du type mais à l’intérieur, dans le champ of_type.

Je peux ensuite coder ma fonction, heureux :

let parse_user (parser : univ_parser) input =
  object
    method id = parser.of_type int_type input
    method nom = parser.of_type string_type input
  end

Le type est maintenant :

val table : .. -> (univ_parser -> 't parser) -> 't table

Le quantificateur sur 'a est placé à l’intérieur du type univ_parser, et plus au début de la fonction. Happy end !