Écrire un catalogue dynamique de fonctions en OCaml

Publié le dans « Informatique ». Mots-clefs : OCaml

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.

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:

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

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:

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:

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 :

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

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:

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:

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

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

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

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

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

Remplissons notre catalogue

Avec ces nouveaux types, nous pouvons construire notre dictionnaire de données, et y insérer nos fonctions à appeler:

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:

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:

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:

(*        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)
get the file

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.

À lire aussi :

Commentaires :

Aucun commentaire pour l'instant.