OCaml est un langage de programmation fortement typé, c’est-à-dire qu’il impose une certaine restriction sur les types des valeurs et interdit toutes conversions implicites. De plus, le système de types d’OCaml met en jeu l’inférence de types : quand nous ne précisons pas nous-mêmes le type de nos expressions, le compilateur le détermine tout seul. Ainsi quand nous définissons une fonction, comme celle-ci :
# let f (x : int) : int = x + 1;; val f : int -> int = <fun>
Nous précisons par des annotations de types que le type de notre fonction f est int -> int. Mais c’est presque inutile ici, car le compilateur sait l’inférer tout seul :
# let f x = x + 1;; val f : int -> int = <fun>
En effet, comme il y a une vraie rigueur au niveau du typage en OCaml, tout ce que l’on peut ajouter à un entier est un entier et tout ce que peut retourner une addition d’entiers est un entier. Cependant, il existe des fonctions où un type ne peut pas être inféré. Prenons juste l’exemple simple de la fonction identité.
# let id x = x;; val f : 'a -> 'a = <fun>
La fonction peut donc accepter tout élément en entrée, quelque soit son type (‘a), mais doit retourner un élément du même type (‘a). C’est ce qu’on appelle le polymorphisme. Étudions maintenant un cas très particulier.
Pourquoi le faible polymorphisme
OCaml est un langage qui se veut multi-paradigme, il comprend aussi bien des traits impératifs que fonctionnels (et aussi des traits orientés objets que personne n’utilise !). Parmi ces traits impératifs, il y a la possibilité de définir des objets mutables. Déclarer des variables dont on peut modifier la valeur (qui admet donc plusieurs états au cours du temps), ce qui ne serait normalement pas possible dans un langage qui se voudrait «fonctionnellement pur» (quel joli mot !). Ainsi, si on définit une référence comme ceci :
# let a = ref 0;;
val a : int ref = {contents = 0}
On peut ensuite modifier sa valeur à notre aise :
# a := !a + 1;;
- : unit = ()
# a;;
- : int ref = {contents = 1}
# incr a;;
- : unit = ()
# !a;;
- : int = 2
Maintenant, remarquons que ces objets mutables sont dangereux pour notre typage. En effet, imaginons qu’on arrive à déclarer un objet mutable dont le contenu soit du type ‘a ; mais comme l’objet est mutable, on pourrait vouloir lui donner pour contenu d’abord une chaine de caractère, puis ensuite, en fait, changer d’avis et lui donner un flottant. Cela deviendrait catastrophique pour la sécurité de notre programme. Heureusement, ce scénario catastrophe n’arrivera pas. En effet, essayons de déclarer une telle référence :
# let a = ref [];;
val a : '_a list ref = {contents = []}
Ici, le type est donc ‘_a list ref, et non pas, comme on s’y serait attendu, ‘a list ref. En effet, le type de cette variable est forcé d’être généralisé, car le compilateur ne peut pas deviner de ce qui adviendra de cette liste vide [] plus tard : évoluera-t-elle : est-ce en listes d’entiers ? Ou bien en liste de flottants ? Le tiret-bas _ marque ici la faiblesse du polymorphisme. C’est-à-dire que pour l’instant, on va « accorder « à cette variable le type ‘_a list ref, mais aussitôt qu’on changera son contenu, son type évoluera, et le polymorphisme sera « cassé ».
# a := 1 :: !a;;
- : unit = ()
# a;;
- : int list ref = {contents = [1]}
Le type de a est maintenant int list ref. C’est dans des cas comme celui-ci que l’on se rend compte que OCaml est un langage bien fait et c’est plutôt rassurant.
Plus vicieux
Maintenant, observons la fonction suivante :
# let f =
let r = ref 0 in
let aux x =
r := !r + x;
!r
in aux;;
val f : int -> int = <fun>
Le comportement (relativement) inattendu est le suivant :
# f 1;; - : int = 1 # f 2;; - : int = 3 (* aie *) # f 37;; - : int = 40
Ici le code après « let f = » est évalué tout de suite, de sorte que la référence r est créée une fois pour toute. En fait, je n’ai pas totalement élucidé les dessous de cette affaire, mais ce comportement est équivalent à ce qu’on aurait pu écrire ainsi (on ne tient pas compte des portées de r et aux bien sûr) :
# let r = ref 0;;
val r : int ref = {contents = 0}
# let aux x =
r := !r + x;
!r;;
val aux : int -> int = <fun>
# aux 1;;
- : int = 1
# aux 2;;
- : int = 3
# aux 37;;
- : int = 40
Ici, le vilain responsable est bien l’application partielle, comme on s’en serait douté :
# let f x =
let r = ref 0 in
let aux x =
r := !r + x;
!r
in aux x;;
val f : int -> int = <fun>
# f 1;;
- : int = 1
# f 2;;
- : int = 2;;
# f 37;;
- : int = 37
Dans ce cas là, le code après « let f x = » ne sera évalué que lors de l’appel, et donc une nouvelle référence r est recréée avec la valeur 0 à chaque appel de f. Dès lors, on ne peut plus vraiment faire confiance aux applications partielles. La fonction suivante deviendrait en effet très dangereuse :
# let map f =
let r = ref [] in
let rec aux = function
| [] -> !r
| x::xs -> r := f x :: !r ; aux xs
in aux;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
# let vilaine = map (fun x -> x);;
val vilaine : '_a list -> '_b list = <fun>
# vilaine [1;2;3];;
- : int list = [3;2;1]
# vilaine [4;5];;
- : int list = [5;4;3;2;1]
Si la fonction vilaine était polymorphe, on pourrait l’appeler avec autre chose qu’une liste d’entiers, et ce serait tout bonnement une catastrophe. Du coup, tout les applications partielles sont rendues faiblement polymorphes, et ce, même dans des cas, où ce n’est pas forcément dangereux, notamment :
# let map_id = List.map (fun x -> x) val map_id : '_a list -> '_a list = <fun> # let id = (fun x -> x) (fun x -> x) val id : '_a -> '_a = <fun>
C’est ce que l’on appelle la value restriction.
Value restriction
La value restriction est la règle qui régit le système de type quand celui-ci est amené à généraliser le type d’une expression. La généralisation polymorphique est appliquée uniquement quand le membre de droite d’une expression let est une valeur. Selon ces slides, ce qui est considéré comme une « valeur » est :
- Les constantes
- Les variables
- Les fonctions
- Les constructeurs appliqués à des valeurs (pas ref)
- Une valeur et une contrainte de type
- Un n-uplets, un enregistrement ou une liste de valeurs
Les fonctions appliquées partiellement ne constituent donc pas une simple valeur et la value restriction s’applique. Cependant, nous avons vu qu’il y a parfois des cas où il est regrettable de ne pas avoir de polymorphisme sur des fonctions « innocentes ». Ce problème est réglé par l’« eta-expansion », mot compliqué pour vraiment pas grand chose : on ajoute le paramètre manquant.
The scholar penguin 