Approche objet et types abstraits de données

(loi d'action = loi externe de composition)

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 -> C ou C x I -> I

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)

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 forme de dualité entre les frameworks et les bibliothèques.

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.

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

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.

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.

// 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 recourt alors à un type existentiel : on affirme 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 quantifié existentiellement) : ouvrir le module m permet de récupérer le type abstrait par la quantification existentielle.

<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

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.
      sum :: (rep, rep) -> rep
      zero :: rep
      opposite :: rep -> rep -- additive inverse
      mult :: (rep, rep) -> rep
      unit :: rep
      inverse :: rep -> rep -- multiplicative inverse
      numerator :: rep -> Int
      denominator :: rep -> Int
      quotient :: rep -> Double
      fraction :: (Int, Int) -> rep
      fromDouble :: 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 fonctions :

• ouverture via la capture ("unpack" en anglais),
• abstraction ("pack" en anglais).

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.

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 de cette existence, par construction.

exists rep.
    sum :: (rep, Q) -> Q
    opposite :: rep -> Q
    mult :: (rep, Q) -> Q
    inverse :: rep -> Q 
    numerator :: rep -> Int
    denominator :: 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,
fromFraction :: (Int,Int) -> Q,
fromDouble :: 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

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.

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.

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.