Sous-typage et polymorphisme d'inclusion

Sous-typage et polymorphisme d'inclusion

Le sous-typage est la possibilité pour un objet d'un certain type d'être considéré et utilisé comme un objet d'un autre type. Un type d'objet ot2 pourra être un sous-type de ot1 si

il possède au moins toutes les méthodes de ot1,
le type de chaque méthode de ot2 présente dans ot1 est sous-type de celle de ot1.

La relation de sous-typage n'a de sens qu'entre objets. Elle ne devra donc être exprimée qu'entre objets. De plus, la relation de sous-typage devra toujours être explicite. On peut indiquer soit qu'un type est sous-type d'un autre, soit qu'un objet doit être considéré comme objet d'un sur-type.

Syntaxe

(nom : sous_type :> sur_type)

(nom :> sur_type)

Exemple

Ainsi, on pourra indiquer qu'une instance de colored_point peut être utilisée comme une instance de point :


# let pc = new colored_point (4,5) "blanc";;
val pc : colored_point = <obj>
# let p1 = (pc : colored_point :> point);;
val p1 : point = <obj>
# let p2 = (pc :> point);;
val p2 : point = <obj>

Bien que connu comme un point, p1 n'en reste pas moins un point coloré et l'envoi de la méthode to_string déclenchera l'exécution de la méthode attachée aux points colorés :


# p1#to_string();;
- : string = "( 4, 5) de couleur blanc"

On peut ainsi construire des listes contenant à la fois des points et des points colorés :


# let l = [new point (1,2) ; p1] ;;
val l : point list = [<obj>; <obj>]
# List.iter (fun x -> x#print(); print_newline()) l;;
( 1, 2)
( 4, 5) de couleur blanc
- : unit = ()

Bien entendu, les manipulations que l'on peut faire sur les objets d'une telle liste sont restreintes à celles autorisées sur les points.


# p1#get_color () ;;
Characters 1-3:
This expression has type point
It has no method get_color

Cette combinaison de liaison tardive et sous-typage autorise une nouvelle forme de polymorphisme : le polymorphisme d'inclusion. C'est-à-dire la possibilité de manipuler des valeurs de n'importe quel type en relation de sous-typage avec le type attendu. Dès lors, l'information de typage statique garantit que l'envoi d'un message trouvera toujours la méthode correspondante, mais le comportement de cette méthode dépendra de l'objet receveur effectif.

Sous-typage n'est pas héritage

Le sous-typage est une notion différente de celle d'héritage. Il y a deux arguments principaux à cela.

Le premier est qu'une instance d'une classe c2 peut avoir comme type un sous-type du type objet c1 sans que c2 soit sous-classe de c1. En effet, on aurait pu définir la classe colored_point de manière indépendante de la classe point et contraindre le type de l'une de ses instances en type objet point.

Le second est qu'il est aussi possible d'avoir un héritage de classes sans pouvoir faire du sous-typage entre instances de ces classes. L'exemple ci-dessous illustre ce second point. Il utilise la possibilité de définir une méthode abstraite prenant en argument une instance (non encore déterminée) de la classe en cours de définition. Dans notre exemple, c'est la méthode eq de la classe equal.

# class virtual equal () =
  object(self:'a)
   method virtual eq : 'a -> bool
  end;;
class virtual equal : unit -> object ('a) method virtual eq : 'a -> bool end
# class c1 (x0:int) =
  object(self)
   inherit equal ()
   val x = x0
   method get_x = x
   method eq o = (self#get_x = o#get_x)
  end;;
class c1 :
  int ->
  object ('a) val x : int method eq : 'a -> bool method get_x : int end
# class c2 (x0:int) (y0:int) =
  object(self)
   inherit equal ()
   inherit c1 x0
   val y = y0
   method get_y = y
   method eq o = (self#get_x = o#get_x) && (self#get_y = o#get_y)
  end;;
class c2 :
  int ->
  int ->
  object ('a)
    val x : int
    val y : int
    method eq : 'a -> bool
    method get_x : int
    method get_y : int
  end

On ne peut pas forcer une instance de c2 à être du type des instances de c1 :


# let a = ((new c2 0 0) :> c1) ;;
Characters 11-21:
This expression cannot be coerced to type
  c1 = < eq : c1 -> bool; get_x : int >;
it has type c2 = < eq : c2 -> bool; get_x : int; get_y : int >
but is here used with type < eq : c1 -> bool; get_x : int; get_y : int >
Type c2 = < eq : c2 -> bool; get_x : int; get_y : int >
is not compatible with type c1 = < eq : c1 -> bool; get_x : int >
Only the first object type has a method get_y

L'incompatibilité entre les types c1 et c2 vient en fait de ce que le type de eq dans c2 n'est pas un sous-type du type de eq dans c1.

Pour montrer qu'il est bon qu'il en soit ainsi, comme dans nos bons vieux devoirs de mathématiques : << raisonnons par l'absurde >>. Soient o1 une instance de c1 et o21 une instance de c2 sous-typée en c1. Si nous supposons que le type de eq dans c2 est un sous-type du type de eq dans c1 alors l'expression o21#eq(o1) est correctement typée (o21 et o1 sont toutes deux de type c1). Cependant, à l'exécution, c'est la méthode eq de c2 qui est déclenchée (puisque o21 est une instance de c2). Cette méthode va donc tenter d'envoyer le message get_y à o1 qui ne possède pas une telle méthode !

On aurait donc un système de type qui ne remplirait plus son office. C'est pourquoi la relation de sous-typage entre types fonctionnels doit être définie moins naïvement. C'est ce que nous proposons au paragraphe suivant.

Formalisation

Sous-typage entre objets

Soient t=<m₁:t₁; ... m_n: t_n> et t'=<m₁:s₁ ; ... ; m_n:s_n; m_n+1:s_n+1; etc...> on dit que t' est un sous-type de t, noté t' £ t, si et seulement si s_i £ t_i pour i Î {1,...,n}.

Appel de fonction

Si f : t ® s, si a:t' et t' £ t alors (f a) est bien typé et a le type s.

Intuitivement, une fonction f qui attend un argument de type t peut recevoir sans danger un argument d'un sous-type t' de t.

Sous-typage des types fonctionnels

Le type t'® s' est un sous type de t® s, noté t'® s' £ t® s, si et seulement si

s'£ s et t £ t'

La relation s'£ s est appelée covariance et la relation t £ t' est appelée contravariance. Cette relation a priori surprenante entre les types fonctionnels peut facilement être justifiée dans le cadre des programmes objets avec liaison dynamique.

Supposons deux classes c1 et c2 possédant toutes deux une méthode m. La méthode m a le type t₁® s₁ dans c1 et le type t₂® s₂ dans c2. Pour plus de lisibilité, notons m₍₁₎ la méthode m de c1 et m₍₂₎ celle de c2. Supposons enfin c2£ c1, c'est à dire t₂® s₂ £ t₁® s₁, et voyons d'où viennent les relations de covariance et de contravariance sur un petit exemple.

Soit g : s₁ ® a, posons h (o:c1) (x:t₁) = g(o#m(x))

covariance: la fonction h attend comme premier argument un objet de type c1, comme c2£ c1 on peut lui passer un objet de type c2. La méthode invoquée par o#m(x) est alors m₍₂₎ qui retourne une valeur de type s₂. Comme cette valeur est passée à g qui attend un argument de type s₁, il faut bien que s₂£ s₁.
contravariance: la fonction h attend, comme second argument, une valeur de type t₁. Si, comme précédemment, nous passons à h un premier argument de type c2, la méthode m₍₂₎ est invoquée et elle attend un argument de type t₂. Il faut donc qu'impérativement t₁£ t₂.

Polymorphisme d'inclusion

On appelle << polymorphisme >> la possibilité d'appliquer une fonction à des arguments de n'importe quelle << forme >> (type) ou d'envoyer un message à des objets de formes différentes.

Dans le cadre du noyau fonctionnel/impératif du langage, nous avons déjà rencontré le polymorphisme paramétrique qui permet d'appliquer une fonction à des arguments de n'importe quel type. Le paramètre polymorphe de la fonction a un type contenant une variable de type. Une fonction polymorphe est une fonction qui exécutera le même code pour les différents types de paramètres. Pour cela elle n'explore pas la structure de l'argument.

La relation de sous-typage utilisée avec la liaison retardée introduit un nouveau genre de polymorphisme pour les méthodes : le polymorphisme d'inclusion. Celui-ci autorise l'envoi d'un même message, à des instances de types différents, si celles-ci ont été contraintes vers le même sur-type. On construit une liste de points, dont certaines valeurs sont en fait des points colorés (vus comme des points). Le même envoi de message entraîne l'exécution de méthodes différentes, sélectionnées par l'instance réceptrice. Ce polymorphisme est appelé d'inclusion car il accepte l'envoi d'un message, contenu dans la classe c, sur toute instance d'une classe sc, sous-type de c (sc :> c) qui est contrainte en c. On obtient alors un envoi de message polymorphe sur toutes les classes de l'arbre des sous-types de c. À la différence du polymorphisme paramétrique le code exécuté peut être différent pour ces instances.

Les deux formes de polymorphisme peuvent être utilisées conjointement grâce aux classes paramétrées.

Égalité entre objets

Nous pouvons maintenant expliquer le comportement surprenant de l'égalité structurelle entre objets présentée à la page ??. Un objet est égal structurellement à un autre uniquement s'il est physiquement égal à celui-ci.


# let p1 =  new point (1,2);;
val p1 : point = <obj>
# p1  = new point (1,2);;
- : bool = false
# p1 = p1;;
- : bool = true

Cela provient de la relation de sous-typage. En effet une instance o2 d'une classe sc, sous-type de c, contrainte en c peut être comparée à une instance o1 de la classe c. Si les champs communs à ces deux instances sont égaux alors les deux objets seraient considérés comme égaux, ce qui est faux du point de vue structurel car o2 peut avoir des champs supplémentaires. Pour cela Objective CAML considère que deux objets physiquement différents sont structurellement différents.

# let pc1 = new colored_point (1,2) "rouge";;
val pc1 : colored_point = <obj>
# let q = (pc1 :> point);;
val q : point = <obj>
# p1 = q;;
- : bool = false

C'est une vision restrictive de l'égalité qui garantit qu'une réponse true n'est pas erronée; la réponse false ne garantit rien.