Types abstraits – Notation

Ils est souvent utile d'exprimer une idée de manière indépendante du langage de programmation; le pseudocode par exemple est notation bien connue pour exprimer de manière les idées de la programmation structurée.

Ceci permet de distinguer l'idée générale exprimée de sa réification dans un langage de programmation donné, tout en évitant de devoir s'attarder aux multiples détails de ce dernier. En échange, bien sûr, on perd un peu en précision... C'est normal : l'abstraction, selon Andrew Koenig, c'est une forme d'ignorance sélective, et faire le choix d'exprimer des idées de manière abstraite, c'est aussi faire le choix de laisser certains détails à préciser ultérieurement.

Dans le cours Structures de données, nous adopterons une notation pour exprimer des types de manière abstraite. Cette notation est inspirée de celle que l'on trouve dans plusieurs langages de programmation, principalement ceux mettant l'accent sur la programmation fonctionnelle comme Haskell ou Erlang, mais aussi les versions plus contemporaines de C#, Java ou C++.

Nous illustrerons cette notation avec un exemple comparatif simple, soit celui d'une classe modélisant un point sur le plan cartésien. Supposant pour les besoins de l'exemple que la gamme d'opérations à supporter soit :

• Un constructeur par défaut, modélisant un point à l'origine $(0,0)$
• Un constructeur paramétrique acceptant en paramètre les valeurs initiales des attributs $x$ et $y$ et construisant un point représentant la coordonnée $(x,y)$
• Un opérateur $+$ binaire tel que $(x_0,y_0)+(x_1,y_1)=(x_0+x_1,y_0+y_1)$
• Un opérateur $-$ unaire tel que $-(x,y)=(-x,-y)$
• Des opérateurs binaires $==$ et $!=$ permettant de tester l'équivalence entre deux points
• Des accesseurs X et Y exposant les valeurs des attributs $x$ et $y$ sans permettre de les modifier

Si cette classe devrait être exprimée en C#, supposant des coordonnées exprimées par des entiers signés, un synopsis correct serait (approximation, car ce langage ne permet pas de véritablement séparer l'interface de l'implémentation) :

class Point
{
   public Point();
   public Point(int x, int y);
   public int X { get; private init; }
   public int Y { get; private init; }
   public static Point operator+(Point p0, Point p1);
   public static Point operator-(Point p);
   public static bool operator==(Point p0, Point p1);
   public static bool operator!=(Point p0, Point p1);
   // pour compiler sans avertissement, ajouter Equals(object) et GetHashCode, et
   // probablement implémenter IEquatable<Point> parce que rendu là...
}

Si cette classe devrait être exprimée en C++, une déclaration correcte serait :

class point {
   int x_, y_;
public:
   point();
   point(int x, int y);
   int x() const;
   int y() const;
   point operator+(const point &) const;
   point operator-() const;
   bool operator==(const point&) const;
   bool operator!=(const point&) const;
};

... ou encore, du fait que les opérateurs peuvent être exprimés en termes de l'interface publique de point, comme suit (ce qui réduirait le couplage) :

class point {
   int x_, y_;
public:
   point();
   point(int x, int y);
   int x() const;
   int y() const;
};
point operator+(const point &, const point&);
point operator-(const point&);
bool operator==(const point&, const point&);
bool operator!=(const point&, const point&);

La notation équivalente à titre de type abstrait serait :

type Point
Opérations:
   construction()
   construction(x : entier signé, y : entier signé)
   X() -> entier signé
   Y() -> entier signé
   opérateur+(Point, Point) -> Point
   opérateur-(Point) -> Point
   opérateur==(Point, Point) -> booléen
   opérateur!=(Point, Point) -> booléen

Si la classe était générique sur la base de type des coordonnées, alors le synopsis approximatif en C# serait :

class Point<T> where T : IEquatable<T>
{
   public Point();
   public Point(T x, T y);
   public T X { get; private init; }
   public T Y { get; private init; }
   // malheureusement, impossibles à exprimer de manière générique avec C#10
   // public static Point operator+(Point p0, Point p1);
   // public static Point operator-(Point p);
   public static bool operator==(Point p0, Point p1);
   public static bool operator!=(Point p0, Point p1);
   // pour compiler sans avertissement, ajouter Equals(object) et GetHashCode, et
   // probablement implémenter IEquatable<Point> parce que rendu là...
}

La déclaration en C++ serait :

template <class T>
class point {
   T x_, y_;
public:
   point();
   point(const T &x, const T &y);
   T x() const;
   T y() const;
   point operator+(const point &) const;
   point operator-() const;
   bool operator==(const point&) const;
   bool operator!=(const point&) const;
};

... ou encore :

template <class T>
class point {
   T x_, y_;
public:
   point();
   point(const T &x, const T &y);
   T x() const;
   T y() const;
};
template <class T> point<T> operator+(const point<T>&, const point<T>&);
template <class T> point<T> operator-(const point<T>&);
template <class T> bool operator==(const point<T>&, const point<T>&);
template <class T> bool operator!=(const point<T>&, const point<T>&);

La notation équivalente à titre de type abstrait serait :

type Point<T>
Opérations:
   construction()
   construction(x : T, y : T)
   X() -> T
   Y() -> T
   opérateur+(Point, Point) -> Point
   opérateur-(Point) -> Point
   opérateur==(Point, Point) -> booléen
   opérateur!=(Point, Point) -> booléen

Comme on peut le voir dans ces exemples, les détails des langages de programmation pris individuellement sont mis de côté, et la notation abstraite vise à concenter les efforts notationnels vers ce qui va à l'essence du type.

Parenthèse

En classe, mon collègue de Sherbrooke a examiné le problème de représenter des unités de mesure (p. ex. : des minutes, des secondes, des mètres carrés, etc.). Il a pour ce faire exploré différentes approches, par exemple faire un type par unité :

class metre { /* ... */ };
class seconde { /* ... */ };
class metre_carre { /* ... */ };

...pour se rendre compte qu'au final, si on les implémente, les unités sont pas mal semblables. La seule différence entre un mètre et une seconde, c'est le type exact de l'unité, autrement ce sont les mêmes opérations.

On se rend aussi compte que la seule différence entre des mètres et des centimètres, c'est un facteur d'échelle sur la valeur, mais qu'au final, c'est la même « base » d'unité.

On en arrive donc à définir le type abstrait ScaledUnit. La notation que Vincent utilise est semblable à celle d'un template en C++, mais c'est pour se faciliter la vie.

Mon collègue de Sherbrooke en arrive donc à un ScaledUnit générique, classe permettant de représenter des unités de mesure à partir de trois paramètres du template. Avec ce type (qu'il ne fait qu'esquisser, du moins à ma connaissance), il montre qu'un même type peut en quelque sorte représenter, dans l'abstrait, une multitude d'unités de mesure distinctes (p.ex.: des minutes, des secondes, des mètres carrés, etc.)

Son ScaledUnit est donc défini comme suit :

• ScaledUnit<U, N, D>, avec
  • U : Unité
  • N et D respectivement : le numérateur et dénominateur de la fraction pour la mise à l'échelle à partir d'une mise à l'échelle $\frac{1}{1}$.

Il examine regarde ensuite quelles sont les opérations mathématiques possibles (addition, soustraction, multiplication par une valeur sans unité (réel), division par une valeur sans unité, une valeur sans unité divisée par une mise à l'échelle, etc.

Suit une écriture des opérations de façon plus formelle :

type ScaledUnit<U,N,D>
Opérations:
   // ...
   ScaledUnit<U, N, D> + ScaledUnit<U, N1, D1> -> ScaledUnit<U, N, D>
   ScaledUnit<U, N, D> - ScaledUnit<U, N1, D1> -> ScaledUnit>U, N, D>
   ScaledUnit<U, N, D> * réel -> ScaledUnit<U, N, D>
   // ...

...etc. (notez que "réel" signifie ici "nombre à virgule flottante", du moins si le nombre doit etre écrit). Ceci montre qu'il est possible de raisonner sur le plan opératoire à partir des types abstraits sans "descendre" jusqu'à la mécanique d'un langage de programmation spécifique.