path: root/content/Informatique/2017-01-01-gadt.rst

.. -*- 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.