diff options
Diffstat (limited to 'content/Informatique')
| -rw-r--r-- | content/Informatique/2017-01-01-gadt.rst | 594 |
1 files changed, 594 insertions, 0 deletions
diff --git a/content/Informatique/2017-01-01-gadt.rst b/content/Informatique/2017-01-01-gadt.rst new file mode 100644 index 0000000..ce34ad5 --- /dev/null +++ b/content/Informatique/2017-01-01-gadt.rst @@ -0,0 +1,594 @@ +.. -*- mode: rst -*- +.. -*- coding: utf-8 -*- + +=================================================== +Écrire un catalogue dynamique de fonctions en OCaml +=================================================== + +:date: 2017-01-01 +:tags: OCaml +:logo: /images/catalog/catalog_75.jpg +:summary: |summary| + +.. default-role:: literal + +.. figure:: {filename}/images/catalog/catalog.jpg + :figwidth: 250 + :figclass: floatright + :alt: Furniture + + Image : `Adam mayer`_ (creativecommons_) + +.. _Adam mayer: https://www.flickr.com/photos/phooky/12687690/in/photostream/ +.. _creativecommons: https://creativecommons.org/licenses/by-sa/2.0/ + +|summary| + +.. |summary| replace:: + + J'ai commencé à écrire un tableur. Je présenterai le résultat une autre fois, + quand le sujet aura plus avancé, et je vais ici me focaliser sur une partie du + code de ce tableur : le catalogue de fonction, en expliquant comment stocker + ensemble des fonctions prenant des paramètres différents, et comment mettre en + place l'appel à ces fonctions. + +Le code est téléchargeable à la fin de l'article. + +.. contents:: \ + :depth: 1 + :backlinks: top + +Présentation +============ + +Un tableur donc, comprend un mini langage. Quand on écrit dans une cellule +`= 2 + 2` ou `sum(A1:C2)` on exécute une instruction et pour obtenir un +résultat. Ce langage contient : + +:des valeurs: + `2` + +:des fonctions: + `+` ou `sum` + +:des références: + `A1` (qui contient à son tour le résultat d'un autre calcul) + + +Tout cela peut être combiné, il est ainsi possible d'écrire `A2 + 1` ou +`sum(C3:E4) + A2`, et le nombre de fonctions disponibles s'approche de la +centaine. Dans le tableur, je souhaitai pouvoir enrichir les fonctions +disponibles en en ajoutant sans avoir à recompiler l'application (par exemple +avec un système de *plugin*). + +En quelque sorte, mon but est de pouvoir enregistrer la fonction dans un +catalogue, et que celle-ci soit appelée automatiquement. Par exemple on peut +imaginer quelque chose comme : + +.. code-block:: ocaml + + (* Enregistrer la fonction + dans le catalogue : + la fonction prend deux paramètres, tous les deux de type int + elle renvoie une valeur également de type int + *) + Catalog.register2 "+" (t_int, t_int) t_int (fun x y -> x + y); + + (* Enregistrer la fonction sum dans le catalogue + la fonction prend un paramètre, qui est une liste une int + elle renvoie une valeur, qui est de type int + *) + register1 "sum" (t_list t_int) t_int (fun x -> List.fold_left (+) 0 x); + + (* Appeler la fonction "+" avec deux paramètres *) + let arg1 = … + and arg2 = … in + eval2 "+" arg1 arg2; + +Je vais montrer comment y parvenir à travers une méthode qui *garantie* à la +compilation que les fonctions font bien ce que l'on attend d'elles. + +Les garanties d'un compilateur +============================== + +Du point de vue d'un programmeur, on s'attend à avoir certaines garanties de la +part du compilateur du programme : + +1. La cohérence des types. + + .. code-block:: ocaml + + let ajoute_2 (x:int) = x + 2 + + Dans la ligne écrite ci-dessus, nous avons déclaré que la variable `x` était + de type `int`. Il est donc inutile de tester si c'est bien le cas (en OCaml + du moins, mais certains langages ne permettent pas d'ajouter cette + information). + + Si le programme a été compilé, alors on peut avoir l'assurance que la + fonction sera appelée uniquement avec des variables de type `int`. + + Cette contrainte peut être vérifiée au moment de la compilation du programme. + +2. La cohérence durant l'exécution. + + Si le langage permet d'avoir plusieurs fonctions avec le même + nom, (par exemple une fonction `+` qui ajoute deux nombres, et une fonction + `+` qui ajoute un nombre à une date, alors je dois être sûr qu'au moment où + j'appelle `date_du jour + 2`, je n'appelle pas la même fonction qu'au moment + où j'appelle `2 + 2`. + + Puisque l'on ne sait pas à l'avance quelle fonction sera appelée (puisque + cela est réalisé de manière dynamique), il est nécessaire de mettre en place + un contrôle à chaque appel de fonction. + +Et maintenant, quelle fonction vais-je devoir appeler quand j'écris `A2 + 2`. +On ne sait pas quelle est la valeur de `A2`, et l'on ne peut donc pas savoir +quelle est la fonction à appeler. Il nous faut donc avoir une information pour +être sûr de pouvoir garantir ces deux contraintes à tout moment dans le +programme : le type. + +Typons nos données +================== + +Dans un langage de programmation typé, la nature de chaque variable est +connue (liste, booléen, nombre entier…), le compilateur est donc capable de +savoir quelle est la fonction à appeler à partir de cette information. Eh bien +pour s'en sortir, nous allons devoir faire pareil, et, à tout moment, conserver +cette information. + +Par exemple dans `A2 + 2`, on ne sait pas quelle est la fonction `+` à +appeler, mais on connait le contenu de la variable `A2`. En suivant le fil des +valeurs, on est ainsi capable de trouver les bonnes informations (et lever une +erreur en disant qu'il n'est pas possible d'appeler la fonction `+` en lui +donnant des arguments de types `bool` et `int`). + +Quels sont les types dont nous avons besoin ? Je propose que nous fassions +notre exemple avec deux seulement pour commencer : les `int` et les `bool`. + +.. code-block:: ocaml + + (*On définit un type générique, qui peut être paramétré*) + type 'a typ + + (*Et deux variantes*) + val t_bool: bool typ + val t_int: int typ + + +Ici, nous venons de déclarer un type nommé `typ` (quelle originalité !) qui +peut être d'un type quelconque. Cette information est destinée au compilateur +(elle ne sera plus disponible après), et lui permet de mettre en place des +contraintes dans les signatures (par exemple une fonction qui prend en +paramètre un `bool typ` ne pourra pas être appelée avec un argument de type +`int typ`). + +Ce type est proposé sous forme de deux déclinaisons, qui correspondent aux deux +variantes que nous souhaitons prendre en charge dans notre application. + +En utilisant cette définition, il devient facile de donner la signature de la +fonction `register2` que nous avons cité au début de l'article : + +.. code-block:: ocaml + + val register2: + string -> (* Le nom de la fonction à enregistrer *) + ('a typ * 'b typ) ->(* Sa signature *) + 'c typ -> (* Le type de retour *) + ( 'a -> 'b -> 'c) (* La fonction en elle-même*) + -> unit + +Il faut ici prêter attentions aux `a` `b` `c` qui apparaissent. Le `a` et le +`b` qui apparaissent dans la signature signifient que la fonction prend en +paramètre un type `a` et `b`. Si ces valeurs ne correspondent pas, le +compilateur OCaml va rejeter le programme en indiquant que les valeurs sont +différentes. + +Cette solution permet de répondre au problème de la *cohérence des types* que +nous avons expliqué plus haut : les contrôles sont désormais à la charge du +compilateur. + +Et concrètement ? +================= + +En présentant notre type de données `'a typ`, j'ai précisé que le `'a` était +destiné au compilateur et n'était plus disponible après. Si l'on souhaite juste +s'en servir pour mettre en place des contrôles à la compilation, alors il est +possible de l'implémenter sous la forme d'un `type fantôme (en)`_. Mais dans +notre utilisation, cela n'est pas suffisant : il faut conserver cette +information pour contrôler au moment d'un appel que les paramètres donnés +correspondent à ceux attendus. + +.. _type fantôme (en): https://wiki.haskell.org/Phantom_type + +C'est là qu'interviennent les GADTs. Cette syntaxe nous permet d'écrire un type +somme, et d'associer à chaque élément un type différent : + +.. code-block:: ocaml + + type _ typ = + | Bool: bool typ + | Int: int typ + +Nous venons ici de créer un constructeur `Bool` (sans paramètres), ayant pour +type `bool typ` et un second constructeur `Int` ayant pour type `int typ`. Armé +de ces deux constructeurs, il est facile d'écrire les types `t_bool` et `t_int` +que nous avons défini dans notre signature : + +.. code-block:: ocaml + + let t_bool = Bool + and t_int = Int + +Pourquoi mettre en place un type somme ? +---------------------------------------- + +Cela permet de fermer la liste des types possibles : dans notre interface, nous +avons déclaré un type abstrait `'a typ` ouvert, mais en interne, nous aurons +juste à faire du *pattern matching* sur les constructeurs `Bool` et `Int`. On +peut ainsi tester l'exhaustivité des cas à chaque fois que l'on souhaite faire +une opération sur les types disponibles. + +Comment on l'utilise ? +---------------------- + +Alors, là il va falloir compliquer un peu l'écriture de notre code. En effet, +la fonction qui reçoit en paramètre notre GADT doit être capable de traiter des +paramètres de types différents, ce que le compilateur OCaml ne tolère pas par +défaut. Il faut explicitement déclarer nos paramètres (ce qui rend l'écriture +un peu plus verbeuse). + +Si l'on souhaite écrire une fonction qui retourne le nom de chaque type il va +falloir écrire notre fonction comme cela : + +.. code-block:: ocaml + + let print_typ: type a. a typ -> string = begin function + | Bool -> "Bool" + | Int -> "Int" + end + + +Revenons en à nos données +========================= + +Maintenant que nos types sont posés, nous allons pouvoir traiter nos données de +la même manière. Pour commencer, nous allons créer un type de données qui sera +le *miroir* de celui utilisé pour déclarer nos types : + +.. code-block:: ocaml + + type _ value = + | Bool: bool -> bool value + | Int: int -> int value + +La déclaration est similaire à celle du type `'a typ`, mais cette fois, les +constructeurs prennent chacun un paramètre (qui est en accord avec le type de +chaque valeur). + +Avec nos deux types `value` et `typ`, nous allons pouvoir faire des choses +intéressantes : + +Déduire le type à partir d'une valeur +------------------------------------- + +La fonction est assez simple (elle tient en quelques lignes), mais elle montre +comment il est possible de transposer l'information contenue dans la structure de +données : en effet, comme nos deux types peuvent être mis en correspondance — +l'information qu'ils portent est la même. Il est donc possible pour tout `a +value` de fournir un `a typ`, tout en conservant la cohérence de l'information +: + +.. code-block:: ocaml + + (* Extract the type from a boxed value *) + let type_of_value: type a. a value -> a typ = begin function + | Bool b -> Bool + | Int n -> Int + end + +Dans le cadre de notre catalogue, cette fonction va permettre de transformer +les arguments donnés à l'appel de la fonction, pour les comparer avec la +signature de la fonction enregistrée. + +Construire une valeur à partir d'un type +---------------------------------------- + +Cette fois, il s'agit de l'opération inverse, mais nous avons besoin d'une +information supplémentaire (puisque le type `'a typ` est un type somme sans +paramètre). Par contre, nous pouvons demander au compilateur de s'assurer que +les valeurs données en paramètre de la fonction sont les bons : + +.. code-block:: ocaml + + let build_value: type a. a typ -> a -> a value = fun typ content -> + begin match typ, content with + | Bool, x -> Bool x + | Int, x -> Int x + end + +La signature de la fonction oblige à donner en paramètre un `a typ`, un `a` et +donne en retour un `a value`, et ce *quel que soit* le type de `a`. + +Dans notre catalogue de fonction, cette fonction nous permet de reconstruire +notre données, une fois que l'on a appelé la fonction enregistrée, en effet, on +connait le type de retour de la fonction, et la valeur est en accord avec ce +type. Avec ces deux informations, il est facile de reconstruire notre résultat. + +Construire un type existentiel +------------------------------ + +Jusqu'à présent, nous avons toujours créé des fonctions qui prenaient +l'information du type à traiter en paramètre. Si nous souhaitons créer une +fonction qui puisse retourner un résultat *de n'importe quel type* nous ne +pouvons procéder ainsi. + +Notre fonction `eval` doit être en mesure de retourner une donnée inconnue +(puisque cela dépend de la fonction appelée), et OCaml n'autorise pas une +fonction à retourner un type inconnu : + +.. code-block:: ocaml + + TODO + +Pour pouvoir faire ce que l'on souhaite, il faut encapsuler notre retour dans +un type existentiel. Il s'agit d'un type qui ne porte pas l'information de la +donnée qu'il contient : + +.. code-block:: ocaml + + type result = + | Result : 'a value -> result + + +Avec ce type, il devient possible de coder le retour de nos fonctions +d'évaluations, (qui retourneront une valeur de type `result`) : + +.. code-block:: ocaml + + (** Create a result from a known type and a value *) + let inject: type a. a typ -> a -> result = fun typ res -> + Result (build_value typ res) + +Cet type ne contient pas d'information sur son contenu, mais puisqu'il a été +créé à partir d'une valeur valide, il est possible de décomposer cette valeur. +Par exemple : + +.. code-block:: ocaml + + (* Décompose le retour d'un appel *) + let Result r = … in + let type_of = type_of_value r in + … + +Récupérer la valeur +------------------- + +La dernière chose dont nous avons besoin est de pouvoir extraire la valeur qui +est contenu dans notre type. Là encore le code est vraiment simple puisqu'il +s'agit de faire du *pattern matching* : + +.. code-block:: ocaml + + (** Get the value out of the box *) + let get_value_content: type a. a value -> a = function + | Bool b -> b + | Int n -> n + +On constate en lisant la signature que là encore, aucune information de type +n'est inventée, tout est déjà déduit à partir des données déjà existantes. + +Et notre dictionnaire ? +======================= + +Maintenant que les concepts sont posés, il ne reste qu'à les mettre en œuvre. +Nous allons représenter notre dictionnaire sous la forme d'une table +associative, dont la clef sera un couple `nom de la fonction * signature`, et +la valeur associée sera un triplet `signature * type de retour * fonction à +appeler`. + +Nous avons besoin de stocker la signature de la fonction pour la comparer avec +les paramètres donnés en arguments. Par contre, il sera là encore nécessaire de +l'encapsuler dans un type existentiel pour pouvoir l'utiliser de manière +générique : + + +.. code-block:: ocaml + + type _ sig_typ = + | T1: 'a typ -> 'a sig_typ + | T2: 'a typ * 'b typ -> ('a * 'b) sig_typ + + type t_signature = + | Sig : 'a sig_typ -> t_signature + +`T1` est la signature d'une fonction n'ayant qu'un argument, `T2` est une +signature à deux paramètres. + +En présente de la même manière nos fonctions : + +.. code-block:: ocaml + + type t_function = + | Fn1: 'a typ * 'b typ * ('a -> 'b) -> t_function + | Fn2: ('a * 'b) sig_typ * 'c typ * ('a -> 'b -> 'c) -> t_function + + +Une fonction peut se présenter comme ayant 1 ou 2 paramètres, et est dans tous +les cas, enregistrée avec : + +- Le type des arguments qu'elle reçoit +- Le type de retour +- La fonction à exécuter + +Remplissons notre catalogue +--------------------------- + +Avec ces nouveaux types, nous pouvons construire notre dictionnaire de données, +et y insérer nos fonctions à appeler : + +.. code-block:: ocaml + + let (catalog:t_function Catalog.t ref) = ref Catalog.empty + + let register name signature f = begin + let name' = String.uppercase_ascii name in + catalog := Catalog.add (name', signature) f !catalog + end + + let register2: type a b c. string -> (a typ * b typ) -> c typ -> ( a -> b -> c) -> unit = begin + fun name (typ1, typ2) result f -> + let signature = T2(typ1, typ2) in + register name (Sig signature) (Fn2 (signature, result, f)) + end + +La fonction `register2` correspond exactement à l'implémentation de celle +donnée dans l'introduction. Le catalogue est conservé comme une référence +mutable et mis à jour à à chaque appel de la fonction `register`. + +Appelons les fonctions +---------------------- + +L'appel d'une fonction va se décomposer en deux étapes : + +1. La recherche dans le catalogue d'une fonction ayant le même nom et la même + signature que les arguments d'appels +2. Le contrôle que la fonction que l'on a pu obtenir présente bien la même + signature que les arguments d'appels. + +Pourquoi ces deux étapes ? Car même si notre fonction `register2` empêche que +l'on écrive n'importe quoi dans notre catalogue, la structure du catalogue +autorise d'y insérer des données incohérentes. Le compilateur OCaml nous oblige +à faire le contrôle pour que l'on puisse appeler la fonction. + +Et comment fait-on ce contrôle ? Me direz-vous ? En contrôlant `l'égalité des +types`_ : le type `eq` présenté dans les exemples avancés est exactement ce +dont nous avons besoin, il suffit juste d'adapter la fonction `eq_type` donné +dans l'exemple pour tester un type de signature et le résultat est présenté +ci-dessous : + +.. _l'égalité des types: https://caml.inria.fr/pub/docs/manual-ocaml/extn.html#sec238 + +.. code-block:: ocaml + + let find_function name signature = begin + Catalog.find (String.uppercase_ascii name, (Sig signature)) !catalog + end + + let eval2 name (Result p1) (Result p2) = begin + (* Construit la signature à partir des paramètres *) + let signature = T2 ((type_of_value p1), (type_of_value p2)) in + try + (* Recherche dans le catalogue *) + begin match find_function name signature with + | Fn2 (fn_sig, returnType, f) -> + (* Réalise le contrôle de type sur la signature de la fonction *) + begin match eq_sig_typ signature fn_sig with Eq -> + (* Appelle la fonction *) + let result = f (get_value_content p1) (get_value_content p2) in + (* Injecte le résultat de notre appel. *) + inject returnType result + end + | _ -> raise Not_found + end + with Not_found -> + print_error name signature; + raise Not_found + end + +La ligne la plus importante est celle-ci : + +.. code-block:: ocaml + + begin match eq_sig_typ signature fn_sig with Eq -> + +La fonction `eq_sig_typ` prend en paramètres deux signatures, et renvoie `Eq` si +et seulement si les deux signatures sont identiques. Cette information est +déduite par le compilateur OCaml, et c'est seulement grâce à la présence de ce +contrôle qu'il autorise l'appel à une fonction inconnue à la compilation, avec +des paramètres également inconnus au moment de la compilation. + +.. note:: + + Il est possible de se passer de ce double contrôle en réécrivant nous-même + notre type `Map` pour garantir que les valeurs portent les même informations + de type que les clefs, mais cela sort du cadre de cet article. + +Terminons +========= + +Tout est en place, il ne reste plus qu'à enregistrer les fonctions dans notre +catalogue : + +.. code-block:: ocaml + + (* nom signature retour fonction *) + register2 "=" (t_int, t_int) t_bool (=); + register2 "<>" (t_int, t_int) t_bool (<>); + + register2 "+" (t_int, t_int) t_int (+); + register2 "*" (t_int, t_int) t_int ( * ); + register2 "/" (t_int, t_int) t_int (/); + register2 "-" (t_int, t_int) t_int (-); + + (* nom signature retour fonction *) + register2 "=" (t_bool, t_bool) t_bool (=); + register2 "<>" (t_bool, t_bool) t_bool (<>); + + register1 "not" t_bool t_bool not; + register2 "and"(t_bool, t_bool) t_bool (&&); + register2 "or" (t_bool, t_bool) t_bool (||); + + +Et enfin testons : + + +.. code-block:: ocaml + + let i2 = inject t_int 2 + and i3 = inject t_int 3 + and b1 = inject t_bool true in + let r1 = eval2 "=" i2 i3 in (* r1 vaut Bool false *) + let r2 = eval1 "not" r1 in (* r2 vaut Bool true *) + let r3 = C.eval2 "=" b1 r2 in (* r3 vaut Bool true *) + let Result value = r3 in (* Extrait la valeur *) + match value with (* Teste le résultat *) + | Int n -> Printf.printf "%d\n" n + | Bool b -> Printf.printf "%b\n" b (* Doit afficher true *) + +.. code-block:: console + + $ ocaml catalog.ml + true + +Nous avons appelé ici la fonction `=` une fois sur des entiers, une fois sur +des booléens, et à chaque fois, la fonction à appeler a été déduite des +arguments passés en paramètres. En cas d'appel avec de mauvais types, l'erreur +n'est pas détectée à la compilation, mais à l'exécution : + +.. code-block:: console + + $ ocaml wrong_catalog.ml + There is no function '=' with signature (Int, Bool) + + +.. figure:: {filename}/images/package-x-generic.png + :figclass: floatleft + :alt: get the file + :target: {filename}/resources/catalog.ml + + Télécharger + +J'espère avoir été assez clair dans les explications. Le code à télécharger +reprend la totalité des exemples présentés ici. + +Pour aller plus loin, il reste à enrichir les différents types (en introduction +j'ai présenté le type `t_list` qui n'a pas été décrit, mais qui peut également +s'intégrer dans ce schéma), et gérer une plus grande arité dans les fonctions +(dans le tableur, il existe des fonctions qui ne prennent pas de paramètres, +telle `rand()` ou `true()` ou davantage que deux). + + +On pourrait également mettre en place une généricité des types (la fonction `=` +peut s'appliquer quel que soit le type de paramètres passés en arguments), mais +cela dépasse le simple catalogue que je présente ici. + |