Majeur 2
Langages et Compilation
Cours 8

Objets et classes et leur compilation

Didier Rémy

23 mars 1998

Les supports de cours:

    http://www.polytechnique.fr/poly/edu/informatique/
    http://www.polytechnique.fr/poly/~remy/majeur/pc8/

Livre

Appel, Modern Compiler Implementation in Java, Cambridge University Press, 1997

Langage Objective Caml (Ocaml)

    http://pauillac.inria.fr/ocaml/

Tutorial et manuel pour Ocaml

    http://pauillac.inria.fr/~remy/objectdemo.html
    http://pauillac.inria.fr/ocaml/htmlman/node3.html
    http://pauillac.inria.fr/ocaml/htmlman/node5.8.html
    http://pauillac.inria.fr/ocaml/htmlman/node5.10.html

Plan

Intérêts de la programmation avec objets,
Exemples en Ocaml.
Un mini-langage à objets et à classes (otigre).
Compilation, cas général (et héritage multiple)
Compilation, cas particulier (et l'héritage simple)
Typage: importance et difficultés

Intérêts de la programmation avec objets

Connus plus particulièrement pour des applications graphiques.

La machine Next, et l'environnement Next-Step est écrit entièrement en style objet (Objective C).
Presque tous les <<interface builders>> sont écrits avec des objets.

Avantages

Modularité, abstraction, réutilisation du code.
Forme de polymorphisme pour les langages qui n'en ont pas.
Facilité d'extension a posteriori (sans avoir été prévue à l'avance).

Programmation classique

On distingue les données, simples (entiers, chaînes) ou construites (listes, arbres, etc), des fonctions, primitives ou définies, qui opèrent sur ces données. Par exemple,

type pierre =  Opal | Perle | Diamant;;

let concasse =  function
    Opal    -> ['O'; 'p'; 'a'; 'l'; ' ']
  | Perle   -> ['P'; 'e'; 'r'; 'l'; 'e'; ' ' ]
  | Diamant -> [ 'D'; 'i'; 'a'; 'm'; 'a'; 'n'; 't'; ' '];;

Dans cette vue traditionnelle, le calcul est décrit par l'application d'une fonction à des données

let imprime_caillou x = List.iter print_char (concasse x);;
imprime_caillou Opal;;

Programmation avec objets

Dans le style à objets, une donnée est regroupée avec toutes les fonctions qui peuvent opérer sur celle-ci, dans une structure appelée objet.

Les objets sont construits à partir de classes.

Les classes décrivent au travers des méthodes le comportement d'un ensemble d'objets, mais elles abstraient les valeurs particulières qui différencient les objets de la même classe.

 
  class caillou c =
    val roche = c
    method concasse = concasse roche
    method imprime = imprime_caillou roche
  end;;

Un objet est créé comme instance d'une classe.

    let treize = new entier 13 and pierre = new caillou Diamant;;

Le calcul est décrit par envoi de message

Plusieurs messages du même nom ont un comportement différent.

    treize # imprime; pierre # imprime;;

Formellement, le comportement à exécuter à la réception du message est porté par l'objet qui reçoit le message.

Cela fournit une nouvelle forme de polymorphisme.

Par exemple, une fonction SPMquotécho" qui répète l'envoi du message SPMquotimprime" peut être appliquée à tout objet possédant une méthode SPMquotimprime".

    let écho x = x # imprime; x # imprime;;
    écho treize; écho pierre;;

L'envoi de messages polymorphes est une opération essentielle. Un langage avec cette possibilité peut déjà prétendre offrir le ``style'' de la programmation avec objets.

Il permet de construire de nouvelles classes à partir de classes existantes. La classe des cailloux peut être enrichie en une classe de bijoux, par ajout d'un champ SPMquotvaleur" et d'une méthode pour calculer le prix à partir de la valeur.

  class bijou c v =
    inherit caillou c as pierre
    val valeur = v
    method prix = 2 * valeur
    method imprime =
      pierre # imprime; print_int valeur; print_string " carats"
  end;;

Un bijou est imprimé en le considérant d'abord comme une pierre sans valeur (le mot clé SPMquotas" lie le bijou à la variable SPMquotpierre" avant que les nouvelles méthodes ne soient ajoutées), puis le prix est affiché suivi de l'unité.

Self et récursion

Les fonctions récursives jouent un rôle essentiel dans le style de programmation traditionnelle. Les méthodes peuvent aussi s'appeler récursivement. Pour cela, l'objet qui invoque une méthode est liée à une variable SPMquotself" (implicite ou explicite selon les langages).

Exemple du jeu de la roulette russe.

  class roulette () as jeu =
    val mutable position = 0
    method roulette = position <- Random.int 8; jeu
    method coup = position <- (position + 1) mod 8; position = 0
    method à_moi = if jeu # coup then "Je meurs" else jeu # à_toi
    method à_toi = if jeu # coup then "Tu meurs" else jeu # à_moi
  end;;

  (new roulette ()) # roulette # à_moi;;

Le mécanisme de liaison tardive

Il est réalisé par l'envoi de messages récursifs. En effet, les appels récursifs ne sont pas résolus au moment de leur introduction (comme dans le style traditionnel), mais leur résolution est retardée jusqu'au moment de la création de l'objet.

Nous spécialisons la classe de la roulette à un jeu à deux contre un. La classe SPMquotroulette_à_deux_contre_un" hérite de la classe ``roulette'' et redéfinit la méthode SPMquotà_moi" pour ajouter un coup supplémentaire.

class roulette_à_deux_contre_un () as jeu = 
  inherit roulette () as vieux_jeu
  method à_moi = if jeu#coup then "je meurs" else vieux_jeu # à_moi
end;;

Pour ne pas tricher, il est important que la méthode SPMquotà_toi" bien qu'inchangée appelle maintenant la nouvelle méthode SPMquotà_moi".

Une nouvelle forme de modularité

Les cellules

class ('a, 'b) cons (h:'a) (t:'b) =
  val head = h
  val tail = t
  method null = false
  method car = head
  method cdr = tail
end

exception Null
class ('a, 'b) nil () = 
  method null = true
  method car = (raise Null : 'a)
  method cdr = (raise Null : 'b)
end;;

Exercice sur les listes

Les listes sont un cas particulier (une spécialisation) des cellules.

Extension verticale Montrer comment ajouter une nouvelle fonctionnalité aux listes en utilisant l'héritage, par exemple une opération d'itération, et sans duplication de code.

Comment ferait-on dans le style classique?

Extension horizontale Montrer que l'on peut raffiner la structure de donnée sans duplication de code.

Par exemple, pour permettre de concaténer les listes avec une complexité en O(1), on peut ajouter un nouveau constructeur SPMquotAppend" (ici une nouvelle classe SPMquotappend") ayant la même interface que les classes SPMquotnil" et SPMquotcons".

Comparer avec le style traditionnel.

Solution SPMquothttp://pauillac.inria.fr/ remy/objectdemo.html"

Un mini-langage à objets

De nombreuses variations sont possibles. La difficulté de la compilation dépend des fonctionnalités implémentées. Au minimum, on aura:

l'envoi de message polymorphe, et l'envoi de message à self,
des classes à toplevel, héritage simple,
un typage statique fort.

Au mieux, et plus expressif:

l'héritage multiple,
la possibilité de retourner self,
la possibilité de cacher les variables d'instances,
la coercion vers des classes parentes, un test d'appartenance.

Au pire, pas de typage statique.

Ctigre avec objets et classes à <<toplevel>>

phrase ::= decl ";;"
decl   ::= "class" class_binding "in" decl
         | expr

class_binding ::= ident "=" [ "inherit" ident ] fields 

fields ::= "val" ident ":=" expr
         | "method" ident [ "(" arg_bindings ")" ] = expr

expr   ::= ...
         | ident "#" ident [ "(" args ")" ]
         | "self"

Si héritage multiple

class_binding ::=
        ident "=" [ "inherit" ident ( "," ident ) * ] fields

Sémantique opérationnelle, interprétation

En général, les objets ne sont pas créés directement mais par instantiation d'une classe. Toutefois, il faut comprendre leur représentation avant de comprendre les classes.

De façon abstraite, un objet est composé de champs qui sont

des méthodes, ou
des variables d'instances.

C'est donc une table (de domaine fini) associant des valeurs à certaines variables d'instances et des fonctions aux méthodes.

Pour préserver la distinction entre méthodes et variables d'instance, on peut représenter les méthodes

L'enregistrement des méthodes est partagé par tous les objets de la même classe. En fait, on le représente comme une composante supplémentaire de l'enregistrement des variables d'instances, qui n'est pas partagé.

Les méthodes elles-mêmes sont des fonctions abstraites par rapport à un objet (self). L'accès à une variable d'instance est remplacé par un accès au champ correspondant de l'enregistrement.

Compilation, approche générale

Une classe est un ensemble de liaisons des identificateurs vers

des variables d'instances, ou
des méthodes.

Les méthodes sont elles-mêmes des fonctions abstraites par rapport à un objet (SPMquotself"). On remplace dans les méthodes les accès aux variables d'instance par des accès explicites dans SPMquotself".

Cela ressemble à la construction SPMquotlet" ...SPMquotin". Toutefois, les fonctions compilées ne sont pas appelées directement mais mémorisées pour être sélectionnées ultérieurement et dynamiquement.

L'héritage revient à la concaténation des environnements associés, avec priorité à la dernière définition.

Compilation des classes

La classe point définie par

class point = 
  var abscisse := 0
  method getx = abscisse
  method setx y = abscisse <- x in

est interprétée (et compilée) comme la construction d'un environnement

let point = 
 let getx_point (self:point) = self.abscisse,
 and setx_point (self:point, y:int) = self.abscisse := y in
 {abscisse := 17, getx = getx_point, setx = setx_point}

Compilation de l'héritage

La classe rond définie par

class rond = inherit point
  method bump y = self#setx (self#getx + y) in

est interprétée comme la concaténation de l'environnement de la classe parente avec les nouvelles composantes.

 let bump_rond (self:point, y:int) = self#setx (self#getx + y) in
 point || {bump = bump_rond}

Elle s'évalue en l'environnement

 {abscisse := 17, getx = getx_point, setx = setx_point,
  bump = bump_point}

Les champs éventuellement redéfinis remplacent les anciens.

Les méthodes sont des valeurs fonctionnelles

Ce sont des fonctions, retournées comme des valeurs pour être sélectionnées et appelées dynamiquement.

On compile une fonction anonyme SPMquotlet f (args) = expr in f" comme une fonction statique en émettant le code associée à une nouvelle étiquette SPMquot@f", mais au lieu de lier statiquement cette étiquette dans l'environnement de compilation, on la retourne comme valeur.

let compile env = function ... | 
 (let f(args) = exp in f) -> 
  let (lab, code) = compile_fun env (f, args, exp) in
  émettre lab code;
  Name lab

Pour effectuer un appel de fonction anonyme, puisqu'on ne connaît pas statiquement l'étiquette de la fonction appelée, on la recherche dans l'environnement dynamique comme on le ferait pour une autre valeur.

Attention! aux valeurs fonctionnelles non closes...

La restriction à des classes donc des méthodes <<toplevel>> est importante.

let f = 
  let x = 19         - ajout le bloc: x |-> 19              
  in {foo() = x}     - f.foo fait un accès à x au niveau -1 
in                   - retire le bloc: x |-> 19             
f.foo ()             - *** plante en tentant d'accéder à x! ***

La compilation des valeurs fonctionnelles non closes, n'est pas traitée dans ce cours. C'est une construction fondamentale dans les langages dit fonctionnels comme Camllight, Ocaml.

Ici, une classe ne voit que les déclarations <<toplevel>> qui sont des variables globales (elles ne sont jamais déallouées).

Représentation des objets

Les objets sont créés par instantiation d'une classe. Abstraitement, on les représente par une copie de l'environnement (enregistrement) représentant leur classe. Ainsi l'affectation d'un champ d'un objet n'affectera pas les autres objets de la même classe.

En pratique, pour partager la partie commune à chaque objet d'une même classe, on représente un objet par un vecteur (C, v₁, ... v_k) où

C est la représentation de la classe où les variables x_i ont été remplacées par leur position d_i dans le tuple, et
v_{d_i} est la valeur de la variable x_i.

Par exemple l'objet SPMquotnew point" est

  ({abscisse = 1,  getx = getx_point, setx = setx_point,
    bump = bump_rond}, 17)

Appel de méthodes et accès aux variables

Dans les objets les méthodes sont des fonctions anonymes, c'est-à-dire des fonctions dont on connaît plus leur définition. C'est la base de la programmation par envoi de message. Le comportement à effectuer à la réception d'un message, donc la fonction à exécuter est déterminé dynamiquement en fonction de l'objet qui reçoit le message.

L'envoi d'un message $p \char93 m (x_1, ... x_n)$ revient à appliquer la fonction représentant la méthode m dans p à l'objet p, soit p[0].m (p, x₁, ... x_n).

L'accès à une variable p.x est un p[p [0].x].

Le coup de l'envoi de message ou de l'accès à une variable est une ou deux indirections plus un accès dans un enregistrement anonyme.

Compilation des enregistrements anonymes

Les enregistrements utilisés ici sont anonymes, car ils ne sont pas déclarés. Dans le cas général, on ne connaît pas la position associée à un champ de l'enregistrement.

L'utilisation des enregistrements anonymes est nécessaire pour la programmation par envoi de messages.

Dans le cas général, il faut voir (et représenter) un enregistrement anonyme comme une table $\ell \in etiquettes \mapsto v \in valeurs$ .

La représentation d'une telle table peut être coûteuse. La compilation des enregistrements et des objets se ramène à

choisir une représentation efficace en fonction des opérations utilisées,
optimiser les cas particuliers.

Cas général

Il s'agit de fournir une représentation et des opérations efficaces pour un ensemble de p enregistrements (classes) avec au plus q étiquettes.

De façon abstraite,on cherche à représenter une fonction partielle

$\begin{displaymath}c \in [1,p] \times \ell \in [1, q] \mapstochar \rightharpoonup d \in I\!\! N \end{displaymath}$

Bien sûr, on peut la décomposer en

$\begin{displaymath}c \mapsto (\ell \mapstochar \rightharpoonup d), \hskip 4em \... ...t} \hskip 4em \ell \mapsto (c \mapstochar \rightharpoonup d). \end{displaymath}$

La partie gauche peut facilement s'implanter par un vecteur.

Comment représenter la partie droite?

Solution incrémentale (asymétrique)

Elle permet d'ajouter de nouveaux enregistrements avec de nouvelles étiquettes. On n'ajoute jamais d'étiquette dans les vieux enregistrements.

Représentation par listes d'associations

C'est la solution la plus simple, incrémentale, efficace en espace, mais très coûteuse en temps de calcul surtout pour de gros enregistrements.

On peut l'améliorer en utilisant

1.: des arbres balancés.
2.: des caches (le dernier appel est remis en tête).

Avec utilisation de caches, la solution est relativement performante surtout en utilisant la décomposition inverse.

Représentation par des vecteurs

Chaque méthode est un vecteur de taille voisine de q. Solution efficace en temps, mais trop coûteuse en espace.

Pour gagner en place, on peut superposer (par coloriage de graphe)

1.: Deux étiquettes qui ne sont jamais dans un même enregistrement.
2.: Deux enregistrements qui ont des domaines disjoints.

La compaction 1 est efficace, mais pas incrémentale. La compaction 2 est incrémentale, mais peu efficace, car certaines méthodes comme SPMquotprint" sont dans presque tous les enregistrements)

On peut rendre la compaction 2 très efficace au prix d'une indirection supplémentaire en coupant $\ell \in [1,q] \mapstochar \rightharpoonup d$ en

$\begin{displaymath}\ell_{fort} \in [1,q_1] \mapstochar \rightharpoonup (\ell_{f... ...ghtharpoonup d) \hskip 4em \hbox{où } q_1, q_2 \approx \sqrt q \end{displaymath}$

Beaucoup plus d'opportunités de compaction. Jamais de gros trous.

C'est la solution utilisée dans Ocaml.

Optimisation des appels récursifs

L'envoi d'un message à self ou l'accès à une variable d'instance peuvent être optimisés en pré-calculant leur position à la construction de la classe.

On abstrait chaque méthode par rapport à un tuple des appels récursifs.

Une invocation interne ou un accès à une variable d'instance est réduit à deux indirections.

$\begin{displaymath}m'(self, u) = {\tt self}\char93 m(u + {\tt self}.x) \end{displaymath}$

devient

$\begin{displaymath}m'({\tt self}, (x_d, m_f, m_a), u) = m_f({\tt self}, m_a, u + {\tt self}[x_d]) \end{displaymath}$

Une invocation externe $p\char93 m (x_1, ... x_k)$ devient

$\begin{displaymath}{\tt let\@} w = p[0].m {\@\tt in\@} w[1] (p, w[2], x_1, ... x_k) \end{displaymath}$

Ce schéma est utilisé pour les variables d'instance et les méthodes privées en Ocaml.

Exemple

La classe SPMquotpoint" peut être compilée comme

 {abscisse := 17,
  getx (self, {abscisse}) = self [abscisse],
  setx ({self, {abscisse, y) = self [abscisse] := y,
  bump ({self, {abscisse, getx_f, getx_a, setx_f, setx_a}, y) =
            setx_f (self, setx_a,  y) + getx_f (self, getx_a)}

L'entête d'un objet de la classe

 ({abscisse = 1,  getx = (getx_f, getx_a), setx = (setx_f, setx_a),
   bump = (bump_f, bump_a)}, 17)

Les composantes SPMquot(xxx_f, xxx_a)" sont calculées au moment de la création de la classe.

Envoi d'un message à un objet d'une classe connue

Ce cas est assez fréquent, surtout si on fait au préalable une analyse de flux. On peut alors appeler la méthode directement.

Pour l'accès à une variable on connaît la position, et on se contente d'une indirection.

Cas particulier de l'héritage simple

Une classe n'a qu'un seul parent. Cela permet de placer les champs à des positions préservées dans toutes les sous-classes.

$\begin{displaymath}\expandafter\ifx\csname graph\endcsname\relax \csname newbox\... ...dth0pt height 0pt}% \kern 1.143in }% }% \hskip 4em \box\graph \end{displaymath}$

L'accès à une variable d'instance p.x peut être optimisé lorsque la position de x est connue statiquement, c'est-à-dire dès que l'on connaît une classe parente de l'objet qui possède ce champ (1).

Un accès à la variable a dans un objet d'une sous-classe de B est p[1]

Accès aux méthodes

Cette optimization s'étant aux méthodes (avec une indirection).

$\begin{displaymath}\expandafter\ifx\csname graph\endcsname\relax \csname newbox\... ...h1.086in width0pt height 0pt}% \kern 3.514in }% }% \box\graph \end{displaymath}$

Un appel de méthode $p\char93 g (v_1, v_2)$ dans un objet p dont on sait qu'il est une sous-classe de B est p[0][2] (p,v₁,v₂).

Avantages et limitations

Les avantages

+: L'héritage simple concerne de nombreux langages (Java compris).
+: L'optimisation est très efficace.

Les limitations: il faut que la condition (1) soit satisfaite:

-: En général, on utilise un système de typage qui restreint le sous-typage à du sous-classage. Ce qui n'est pas un très bon choix...
-: Cela est incompatible avec la possibilité de cacher des variables d'instances.
-: Cela ne fonctionne pas dans un langage non typé.

Compilation du test d'appartenance

Appartenance au sens strict Il s'agit de tester si un objet à été créé par la classe C. Pour cela, il suffit de mettre dans chaque objet une information indiquant sa classe. On peut utiliser le champ p[0] à cet effet.

Appartenance au sens large Il s'agit de tester si un objet p appartient au sens strict à une sous-classe de C.

Si on se restreint au cas de l'héritage simple, cela revient à tester si la classe C₀ de p est une sous-classe de C, ou de façon abstraite, à savoir si le n $\oe$ ud C₀ domine le n $\oe$ ud C dans l'arbre d'héritage.

Il suffit de rechercher si C est une des classes parentes de C₀. On peut effectuer ce test en temps constant en représentant les classes parentes de C₀ dans un vecteur V (une classe étant positionnée à sa profondeur dans la hiérarchie), et à condition de connaître la profondeur d de la classe C. Alors, C₀ est sous-classe de C si et seulement si V[d] = C.

Langages sans classe

Il existe des langages sans classes, mais mis à part les langages théoriques, ils sont plus rares. Les objets sont créés par extension ou duplication des modèles. Ils peuvent se compiler par la méthode générale.

Importance du typage

En général:

pour éviter les erreurs
pour mieux compiler

C'est encore plus vrai pour les objets.

Le typage des objets est un problème difficile qui reflète des difficultés réelles à les utiliser. Des erreurs sérieuses ont été commises (O₂, Eiffel, sont des langages industriels avec objets qui ont un système de typage <<troué>>).

Le système de typage de Java doit pallier ses faiblesses par des tests d'appartenance superflus (vérifications dynamiques des types).

Le typage des objets aujourd'hui bien compris a fait couler beaucoup d'encre pendant les dix dernières années.

Typer pour éviter les erreurs

Le sous-typage est souvent confondu avec le sous-classage avec l'idée que l'on peut utiliser un objet d'une classe avec l'interface d'un objet de sa classe parente. C'est faux en présence de méthodes binaires.

class point x as self = 
  val x = (x : int)  method getx = x
  method min p = if x < p#getx then self else p
end;;

class point_coloré(x,c) as self = inherit point x as super
  val c = (c : bool)  method getc = c
  method bump p = if c = p#getc then self#min p else p
end;;

Si SPMquotp" est un point et SPMquotq" est un point coloré, alors SPMquotq#min p" produit une erreur d'exécution à l'appel de la méthode SPMquotp#getx". On ne peut donc pas considérer SPMquotq" comme un SPMquotpoint".

Typer pour mieux compiler

En présence d'héritage simple, le typage permet en général de connaître la classe d'un objet.

Toutefois, ce n'est plus le cas si la relation de sous-typage s'appuie sur la compatibilité des inferfaces et non le sous-classage.

Par contre, des techniques d'analyse de flux, voisines du typage, permettent de résoudre statiquement de nombreux appels de méthodes.

Conclusion

La programmation avec objets n'est pas une réponse à tout
La sémantique est compliquée par l'abstraction des appels récursifs.
Le typage des opérations sur les objets est difficile.
Il y a d'autres solutions à la programmation modulaire: les modules

+
Concept plus classique, mieux formalisé.

-
Il faut en général prévoir le partage à l'avance (abstraire)
Les objets sont moins nécessaires dans un langage avec polymorphisme et modules.

Pratiquement, il faut utiliser les objets quand ils apportent quelque chose, mais ne pas ignorer les autres constructions (modules et polymorphisme) qui apportent aussi souplesse et expressivité.

Théoriquement, enrichir modules et objets pour unifier les deux concepts est un problème de recherche ouvert et important.