UP | HOME

Approche objet et types abstraits de données

Table of Contents

Cf. le paquet session5.intraInterOp pour les exemples de code.

1 Type abstrait

Un type abstrait de données se définit par un ensemble (ou plusieurs ensembles, un par sorte de données) muni d'opérations. Les opérations vérifient certaines propriétés, très souvent exprimées par des équations.

Exemple 1: les entiers naturels

  • Deux opérations (dont une constante) : zero et successeur
  • Aucune équation

Exemple 2 : un monoïde (comme l'ensemble des mots)

  • Deux opérations (dont une constante) : zero et somme
  • Equations
    • Neutralité : zero.somme(x) = x.somme(zero) = x
    • Associativité : x.somme(y.somme(z)) = (x.somme(y)).somme(z)

Exemple 3 : une pile

  • Cinq opérations : push, vide, estVide, pop, top
  • Equations
    • (p.push(e)).pop = p et (p.push(e)).top = e.
    • si p.estVide, p = vide.
    • Etc.

Une interface permet de représenter un type abstrait de données. Cependant, la relation entre les implémentations et l'interface n'est pas unique mais peut varier entre deux cas limites, caractéristiques de l'approche objet et de l'approche fonctionnelle respectivement.

2 Lois de composition et lois d'action

2.1 Approche objet : utilisation de lois d'action

somme : I x I -> I
  • en Maths : loi interne de composition sur I

Traduction classique en Java

interface I {
  I somme(I x);
}
class C implements I {
  public I somme(I x) {...}
}

Symétrie perdue dans C :

somme : C x I -> I // ou C x I -> C

Ce n'est plus une loi interne de composition mais une loi externe de composition, autrement dit une loi d'action. Elle peut s'appliquer à des I qui ne sont pas des C : c'est le polymorphisme. Le polymorphisme permet l'interopérabilité.

Usage important : les frameworks (cadriciels)

2.2 Digression (et rappel) : frameworks et bibliothèques

Une bibliothèque présente un ensemble d'interfaces et une ou plusieurs implémentations pour chaque interface. Le programmeur définit le programme principal en important les bibliothèques utiles et en les appelant.

  • Exemple : API standard

Un framework définit un programme principal (ou un sous-programme) paramétré réalisant une fonctionnalité utile. Pour utiliser le framework, le programmeur instancie les paramètres. Lors de l'exécution, le framework appelle les paramètres instanciés par l'utilisateur : c'est une inversion du contrôle relativement au cas des bibliothèques. Dans un langage à objets, la paramétrisation se fait typiquement via des interfaces : l'utilisateur implémente alors ces interfaces. L'interopérabilité entre le framework et les implémentations de la paramétrisation est donc nécessaire.

  • Exemples : framework Swing pour les interfaces graphiques, framework Java pour les servlets

On observe donc une dualité entre les frameworks et les bibliothèques.

2.3 Application : un carré est-il un rectangle ?

Voici un problème classique concernant la modélisation objet.

interface Rectangle {
  double longueurX();
  double longueurY();
  void dilatationX(double rapport); // dilatation ou contraction 
                                    //   suivant l'axe des x
}
interface Carre extends Rectangle {
  double longueur();
}

Supposons qu'on ait implémenté l'interface Rectangle. Comment implémenter l'interface Carre ?

Par héritage, on doit rajouter un invariant, à savoir que les côtés d'un carré ont la même longueur. Si on ne modifie pas l'implémentation de dilatationX, l'invariant n'est plus préservé : un carré devient un rectangle, tout en étant de type Carre. Si on la modifie de manière à préserver le caractère carré, on peut obtenir des comportements inattendus lorsqu'un objet de type Carre est converti en un objet de type Rectangle et dilaté : la spécification de Rectangle doit donc être affaiblie.

Pour résoudre ce problème, prenons le point de vue algébrique et pensons en termes de loi. Typons la transformation géométrique :

dilatationX : Rectangle x double -> Rectangle
dilatationX : Carre x double -> Rectangle

Les interfaces doivent donc se récrire ainsi (en ajoutant les fabriques utiles) :

interface Rectangle {
  double longueurX();
  double longueurY();
  Rectangle creer(double lx, double ly);
  Rectangle dilatationX(double rapport); // dilatation ou contraction 
                                    //   suivant l'axe des x
}

interface Carre extends Rectangle {
  double longueur();
}

Voici une esquisse d'une implémentation immutable de Rectangle.

class RectangleImmut implements Rectangle {
  ... // Etat 
  public RectangleImmut(double lx, double ly) {...}
  public Rectangle creer(double lx, double ly) {
    return new RectangleImmut(lx, ly);
  }
  public Rectangle dilatationX(double rapport) {
    return this.creer(rapport * lx, ly);
  }
}

L'implémentation immutable de Carre peut s'obtenir par héritage.

interface Carre extends Rectangle {
  double longueur();
  Carre creer(double l);
}
class CarreImmut extends RectangleImmut implements Carre {
  public CarreImmut(double l) {
    super(l, l);
  }
  public double longueur(){
    return this.longueurX(); // ou return this.longueurY();
  }
  public Carre(double l){
    return new CarreImmut(l);
  }
}

Passons aux versions mutables.

class RectangleMut implements Rectangle {
  ... // Etat 
  public RectangleMut(double lx, double ly) {...}
  public Rectangle creer(double lx, double ly) {
    return new RectangleMut(...);
  }
  public Rectangle dilatationX(double rapport) {
    ... // Modification de l'état
    return this;
  }
}

L'implémentation mutable de Carre peut s'obtenir par héritage. Elle nécessite cependant la récriture de dilatationX, suivant la version immutable.

class CarreMut extends RectangleMut implements Carre {
  public CarreMut(double l) {
    super(l, l);
  }
  public Rectangle dilatationX(double rapport) {
    return this.creer(...);
  }
  ...
}

Si la spécification de Rectangle énonce qu'un rectangle est toujours modifié en place, alors cette implémentation de Carre ne peut convenir : il n'y a pas de solution dans ce cas.

Exercice : dans session5.intraInterOp.CarreRectangle, étudier les définitions plus complètes et implémenter les interfaces déclarées.

2.4 Approche fonctionnelle : utilisation de lois de composition

L'approche fonctionnelle part de la définition d'un module abstrait, déclarant les fabriques et les opérations du type abstrait avec leur signature. Une implémentation fournit alors une représentation concrète pour l'état.

Exemple : ensemble muni d'une opération somme

// Déclaration du module abstrait
interface Module<Rep extends Etat> {
  Rep somme(Rep x, Rep y);
}

// Une implémentation concrète 
// Choix de l'implémentation pour Rep : ImplemEtat
class ImplemModule implements Module<ImplemEtat> {
  public ImplemEtat somme(ImplemEtat x, ImplemEtat y) {...}
}

La symétrie est conservée : somme définit bien une loi interne de composition sur le type ImplemEtat (une implémentation de l'interface Etat).

Lors d'une utilisation du module concret, on cherche à abstraire le choix de l'implémentation pour éviter que l'utilisateur ne viole la barrière d'abstraction, c'est-à-dire ne découvre le type concret implémentant le type abstrait Etat. On plonge alors le module dans l'union de tous les modules, Module<? extends Etat>, en recourant au joker : on affirme ainsi qu'il existe un type de représentation Rep (ici de valeur ImplemEtat) tel que le module a pour type Module<Rep>.

private static Module<? extends Etat> m = new ImplemModule();
// Fonction permettant l'accès à l'unique instance après abstraction du type
// -> Usage d'un type existentiel
public static Module<? extends Etat> abstraction() {
  return m;
}

Pour utiliser le module ainsi abstrait, on utilise une fonction d'ouverture réalisant la capture du joker (représentant le type paramétrant l'union infinie) : ouvrir le module m permet de récupérer le type abstrait par le plongement dans l'union infinie.

<Rep extends Etat> void ouvrir(Module<Rep> m) {
  ... Rep ...
}

C'est le phénomène de capture : on peut utiliser Rep dans le corps de la fonction, avec pour information que Rep est un sous-type de Etat.

Avantage : intra-opérabilité permettant une meilleure efficacité ou précision lors de l'implémentation (du fait que le type d'implémentation est fixé)

Désavantage : interopérabilité impossible

Bonne solution pour les bibliothèques

3 Comparaison : interopérabilité versus intra-opérabilité

L'approche objet et l'approche fonctionnelle correspondent à deux cas limites : interopérabilité maximale pour l'approche objet, intra-opérabilité maximale pour l'approche fonctionnelle.

Premier exemple : voir l'unité de compilation session5.intraInterOp.TAD.

Second exemple : les rationnels

  • Si le premier exemple montre qu'un langage à objets comme Java permet les deux approches, le second exemple indique qu'un langage fonctionnel comme Haskell permet aussi ces deux approches.

Définition du type abstrait de données (avec une syntaxe à la Haskell)

somme :: (Q, Q) -> Q
zero :: Q
oppose :: Q -> Q 
produit :: (Q, Q) -> Q
unite :: Q
inverse :: Q -> Q 
numerateur :: Q -> Int
denominateur :: Q -> Int
quotient :: Q -> Double
fraction :: (Int, Int) -> Q
doubleRationnel :: Double -> Q

On cherche à implémenter ce type abstrait.

3.1 Lois de composition

Première possibilité : approche fonctionnelle.

On affirme l'existence d'un type concret Rep implémentant le type abstrait Q. L'implémentation correspond à la preuve de cette existence, par construction.

exists Rep.
  somme :: (Rep, Rep) -> Rep
  zero :: Rep
  oppose :: Rep -> Rep 
  produit :: (Rep, Rep) -> Rep
  unite :: Rep
  inverse :: Rep -> Rep 
  numerateur :: Rep -> Int
  denominateur :: Rep -> Int
  quotient :: Rep -> Double
  fraction :: (Int, Int) -> Rep
  doubleRationnel :: Double -> Rep

Lire : "il existe un type concret d'implémentation Rep tel que les opérations du type abstrait ont pour type …"

A cette définition, on associe deux opérations :

  • l'une d'ouverture, correspondant à la capture ("unpack" en anglais),
  • l'autre d'abstraction, correspondant au plongement dans l'union dépendante ("pack" en anglais).

Dans un langage fonctionnel comme Haskell, ces opérations sont primitives.

Le type abstrait Q a partout été remplacé par le type concret : c'est l'intra-opérabilité qui est recherchée, les opérations devenant des lois internes de composition.

3.2 Lois d'action

Seconde possibilité : approche objet

Comme dans le cas précédent, on affirme l'existence d'un type concret Rep implémentant le type abstrait Q. L'implémentation correspond à la preuve constructive de cette existence.

exists rep.
  somme :: (Rep, Q) -> Q
  oppose :: Rep -> Q 
  produit :: (Rep, Q) -> Q
  inverse :: Rep -> Q
  numerateur :: Rep -> Int
  denominateur :: Rep -> Int
  quotient :: Rep -> Double

Lire : "il existe un type concret d'implémentation Rep tel que les opérations du type abstrait ont pour type …".

On ajoute les fabriques, qui n'utilisent pas le type concret rep :

zero :: Q,
unit :: Q,
fraction :: (Int,Int) -> Q,
doubleRationnel :: Double -> Q

A cette définition, on associe une fonction implémentée par la machine virtuelle Java :

  • la liaison dynamique.

Elle permet de réaliser la liaison au code d'une implémentation à partir d'une interface.

Q y = ...;
Q x = new Rep(...);
x.sum(y) // Code de Rep

En Haskell, la liaison dynamique se programme, en déléguant à l'implémentation le calcul.

En résumé, le type abstrait Q a été remplacé par le type concret le moins possible : c'est l'inter-opérabilité qui est recherchée, les opérations devenant des lois d'action.

4 Bibliographie

4.1 On understanding data abstraction, revisited

In 1985 Luca Cardelli and Peter Wegner, my advisor, published an ACM Computing Surveys paper called "On understanding types, data abstraction, and polymorphism". Their work kicked off a flood of research on semantics and type theory for object-oriented programming, which continues to this day. Despite 25 years of research, there is still widespread confusion about the two forms of data abstraction, abstract data types and objects. This essay attempts to explain the differences and also why the differences matter.

Conférence OOPSLA de 2009

Cf. l'article en ligne.

4.2 The power of interoperability: why objects are inevitable

Three years ago in this venue, Cook argued that in their essence, objects are what Reynolds called procedural data structures. His observation raises a natural question: if procedural data structures are the essence of objects, has this contributed to the empirical success of objects, and if so, how?

This essay attempts to answer that question. After reviewing Cook's definition, I propose the term service abstractions to capture the essential nature of objects. This terminology emphasizes, following Kay, that objects are not primarily about representing and manipulating data, but are more about providing services in support of higher-level goals. Using examples taken from object-oriented frameworks, I illustrate the unique design leverage that service abstractions provide: the ability to define abstractions that can be extended, and whose extensions are interoperable in a first-class way. The essay argues that the form of interoperable extension supported by service abstractions is essential to modern software: many modern frameworks and ecosystems could not have been built without service abstractions. In this sense, the success of objects was not a coincidence: it was an inevitable consequence of their service abstraction nature.

Conférence OOPSLA de 2013

Cf. l'article en ligne.

Author: Hervé Grall
Version history: v1: 2015-11-02; v2 :2016-11-02[update]; v3: 2017-10-19[update]; v4: 2017-10-25[update]; v5: 2018-11-27[update].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.