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 :

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 :

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

   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.

(*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 :

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.

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 :

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 :

let t_bool = Bool
and t_int = Int

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 :

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 :

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

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

TODO

type result =
  | Result : 'a value -> result

(** 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)

(* Décompose le retour d'un appel *)
let Result r = … in
let type_of = type_of_value r in
…

(** Get the value out of the box *)
let get_value_content: type a. a value -> a = function
  | Bool b -> b
  | Int n -> n

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 :

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 :

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

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

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

begin match eq_sig_typ signature fn_sig with Eq ->

Terminons

Tout est en place, il ne reste plus qu’à enregistrer les fonctions dans notre catalogue :

(*        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 :

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

$ 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 :

$ ocaml wrong_catalog.ml
There is no function '=' with signature (Int, Bool)

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.