Représentation des objets
(dans le modèle à enregistrement). |
|
Les objets sont des valeurs sophistiquées. Ils ne sont pas représentables
directement (en machine).
Comment faut-il les représenter en machine pour permettre une exécution
efficace?
Nous nous limitons au modèle à enregistrements.
Nous considérons le cas général, et quelques cas particuliers intéressants.
Représentation des objets |
|
Un objet est créé par instantiation d'une classe ou par clonage.
En théorie, il est
représenté par une copie de l'environnement (enregistrement) représentant
sa classe: l'affectation d'un champ d'un objet n'affectera pas les
autres objets de sa classe.
En pratique, on partage la partie commune à chaque objet d'une même classe,
i.e. l'ensemble des méthodes: un objet est alors un vecteur (C, v1, ...,
vk) où
· | C est la représentation de la classe (ie. un enregistrement
anonyme) mais où les variables xi ont été remplacées par leur position
di dans le tuple, et
|
· | vdi est la valeur de la variable xi.
|
L'envoi de messages et l'accès aux variables d'instance doivent être
modifiés de façon cohérente.
Appel de méthodes et accès aux variables |
|
Les méthodes sont des fonctions anonymes placées dans les champs d'un
enregistrement. 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 sélectionnée
dynamiquement1 dans l'enregistrement des méthodes porté par
l'objet qui reçoit le message.
L'envoi d'un message p # m x1 ... xn revient à
appliquer la fonction représentant la méthode m dans p à l'objet
p et aux arguments, soit p.(0).m p x1 ... xn.
L'accès à une variable xi est p.(di), soit p.(p.(0).xi).
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.
Code source
class point x =
object (self)
val mutable abscisse = x
method getx = abscisse
method bump = abscisse <- self#getx +1
end |
|
Traduction (non typée)
let getx_point self = self.(self.(0).x)
let bump_point self = self.(0).x <- self.(0).getx self + 1
let partagé =
{ abscisse = 1; point = getx_point; bump = bump_point }
let new_point x : obj = [| partagé; x |] |
|
Envoi de message
let p = new point 17 in p#bump |
|
Traduction
let p = new_point 17 in p.(0).bump p |
|
Se réduit en
let p = [| meth; 17 |] in bump_point p |
|
puis
Les enregistrements utilisés ici sont anonymes, ie. non déclarés. Comment
les représenter? Dans le cas général, on ne connaît pas la position
associée à un champ de l'enregistrement, car on ne connaît que son type (qui
est une information incomplète en présence de sous-typage).
L'utilisation des enregistrements anonymes est nécessaire pour
que l'envoi de message soit polymorphe.
Dans le cas général, un enregistrement anonyme est une table
l Î etiquettes |® v Î valeurs
La représentation d'une telle table peut être coûteuse.
La représentation des enregistrements et des objets se ramène à
· | choisir une représentation générale relativement efficace,
|
· | optimiser les cas particuliers fréquents.
|
En fait, 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, cela se ramène à la représentation d'une fonction
partielle:
c Î [1,p] × l Î [1, q] d Î I N
Cette table peut se décomposer dans l'une ou l'autre direction:
c |® (l d),
4em
ou
4em
l |® (c d).
La partie gauche peut toujours s'implanter par un vecteur.
Comment représenter la partie droite?
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
- des arbres balancés.
- 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 l |® (c d).
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
- Deux étiquettes qui ne sont jamais dans un même enregistrement.
- 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 print
sont dans presque tous les enregistrements)
Compaction au prix d'une indirection |
|
On peut rendre la compaction 2 très efficace au prix d'une indirection
supplémentaire en coupant l Î [1,q] d en
lfort Î [1,q1]
(lfaible Î [1,q2] d)
4em
où
q1, q2 » q
Beaucoup plus d'opportunités de compaction. Jamais de gros trous.
C'est la solution utilisée dans Ocaml.
Message d'une classe connue |
|
Lorsque qu'on envoie le message à un objet d'une classe connue, on
peut calculer statiquement l'emplacement de la méthode.
Ce cas est assez fréquent, surtout si on fait au préalable une analyse de
flux.
Cas particulier de l'héritage simple |
|
Une classe n'a qu'un seul parent. Cela permet de placer les
champs à des positions réservées dans toutes les sous-classes.
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).
Dans l'exemple ci-dessus, un accès à la variable a dans un objet d'une
sous-classe de B est uniformément p.(1).
Cette optimisation s'étant aux méthodes (avec une indirection).
Un appel de méthode p#g v1 v2 dans un objet p dont on sait qu'il
est une sous-classe de B est p.(0).(1) p v1 v2.
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é.
|
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 C0 de p est une sous-classe de C, ou de façon abstraite, à
savoir si le noeud C0 domine le noeud C dans l'arbre d'héritage.
Test d'appartenance (héritage simple) |
|
Il suffit de rechercher si C est une des classes parentes de C0. On
peut effectuer ce test en temps constant en représentant les classes
parentes de C0 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, C0 est sous-classe de C si et seulement si
V.(d) = C.
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.
La création d'un nouveau type d'objet revient à la création d'une nouvelle
classe.
This document was translated from LATEX by
HEVEA and HACHA.