Séance 11
Programmation orientée objets

Dans cette séance, nous allons définir des objets à partir de classes, et mettre en évidence le concept de polymorphisme. L'exemple ci-dessous rappelle la syntaxe d'une classe, la création d'un objet et son utilisation.

   declare
   class Counter
      attr value
      meth init   % (re)initialise le compteur
         value:=0
      end
      meth inc   % incremente le compteur
         value:=@value+1
      end
      meth get(X)   % renvoie la valeur courante du compteur dans X
         X=@value
      end
   end

   MonCompteur={New Counter init}
   for X in [65 81 92 34 70] do {MonCompteur inc} end

   {Browse {MonCompteur get($)}}   % affiche 5

   local X in {MonCompteur get(X)} X end

Enoncés des exercices

1. Collections. Une collection regroupe des valeurs. Voici une classe qui implémente des collections. Trois méthodes sont définies: put(X), get(X) et isEmpty(B).

      class Collection
         attr elements
         meth init   % initialise la collection
            elements:=nil
         end
         meth put(X)   % insere X
            elements:=X|@elements
         end
         meth get($)   % extrait un element et le renvoie
            case @elements of X|Xr then elements:=Xr X end
         end
         meth isEmpty($)   % renvoie true ssi la collection est vide
            @elements==nil
         end
      end
   

   Notez que par défaut, le corps d'une méthode est une instruction. Mais la notation $ permet de définir des méthodes comme des fonctions. Leur contenu doit être une expression qui décrit la valeur renvoyée. Dans l'exemple, la méthode put(X) est définie par une instruction, tandis que la méthode isEmpty($) l'est par une expression.

   • Ajoutez une méthode union(C) à cette classe. L'appel {C1 union(C2)} fait l'union des collections C1 et C2. Après l'appel, C1 contient cette union et C2 est vide. Votre méthode doit être polymorphe, c'est-à-dire qu'elle ne doit pas dépendre des implémentations des objets concernés.

   • Définissez maintenant une classe SortedCollection pour des collections triées. L'interface d'une collection triée est la même qu'une collection, à la différence près que la méthode get(X) renvoie les éléments dans l'ordre du tri. En d'autres mots, la méthode renvoie toujours l'élément le plus petit de la collection. Votre classe doit hériter de la classe Collection.

   • Considérez l'appel {C1 union(C2)}. Quelle est sa complexité temporelle si C1 et C2 sont de la classe Collection? Que devient cette complexité si C1 et C2 sont de votre classe SortedCollection?

   • Utilisez votre classe SortedCollection pour trier une liste. Votre implémentation correspond-elle à un des algorithmes de tri vus dans la séance 5? Quelle est sa complexité temporelle?

   • Pouvez-vous facilement convertir une collection quelconque en une collection triée?

2. Des objets pour représenter des expressions. Cet exercice est similaire au projet que vous avez fait. L'idée est ici de représenter des expressions par des objets et non plus par des enregistrements. Chaque sous-expression d'une expression est représentée par un objet, y compris les symboles de variables. On définit pour cela différents types d'expressions, et chaque type est implémenté par une classe propre. Par exemple, on peut représenter la formule 3x² - xy + y³ par

      declare
      VarX={New Variable init(0)}
      VarY={New Variable init(0)}
      local
         ExprX2={New Puissance init(VarX 2)}
         Expr3={New Constante init(3)}
         Expr3X2={New Produit init(Expr3 ExprX2)}
         ExprXY={New Produit init(VarX VarY)}
         Expr3X2mXY={New Difference init(Expr3X2 ExprXY)}
         ExprY3={New Puissance init(VarY 3)}
      in
         Formule={New Somme init(Expr3X2mXY ExprY3)}
      end
   

   Notez qu'on utilise le même objet VarX pour toutes les occurrences de x dans la formule.

   Ces objets vont vous permettre de réaliser deux choses : (1) évaluer une expression pour une valeur donnée des variables, et (2) produire la dérivée d'une expression par rapport à une variable donnée. Cette dérivée est elle-même une expression.

   Pour évaluer la formule de l'exemple, on affecte des valeurs aux variables x et y en utilisant la méthode set(N) des objets VarX et VarY. Ensuite, on appelle la méthode evalue(X) de l'objet Formule. On doit pouvoir réévaluer la formule avec d'autres valeurs pour les variables. L'exemple suivant évalue la formule avec x=7 et y=23, puis avec x=5 et y=8.

      {VarX set(7)}
      {VarY set(23)}
      {Browse {Formule evalue($)}}   % affiche 12153
   
      {VarX set(5)}
      {VarY set(8)}
      {Browse {Formule evalue($)}}   % affiche 547
   

   Pour dériver la formule, on appelle la méthode derive(V E) sur l'objet Formule. Le paramètre V est l'objet représentant la variable par rapport à laquelle on fait la dérivée. Par exemple, pour dériver par rapport à x, on utilise V=VarX. La méthode affecte alors à E un objet représentant l'expression résultat. L'exemple ci-dessous dérive la formule par rapport à x et l'évalue avec x=7 et y=23.

      declare
      Derivee={Formule derive(VarX $)}   % represente 6x - y
   
      {VarX set(7)}
      {VarY set(23)}
      {Browse {Derivee evalue($)}}   % affiche 19
   

   Implémentez les classes Variable, Constante, Somme, Difference, Produit et Puissance pour qu'elles représentent des formules.

   • Ces classes doivent toutes implémenter les méthodes evalue(X) et derive(V E). Ces méthodes sont polymorphes, car on peut les appeler quelle que soit la classe de l'objet formule. Par exemple, l'objet ExprXY évalue son résultat en appelant les objets VarX et VarY avec la méthode evalue.

   • Les classes ont également des méthodes propres. Par exemple, leur méthode d'initialisation, pour laquelle les arguments ont des significations différentes suivant les classes. Un autre exemple est la méthode set(N) de la classe Variable, qui permet d'affecter les variables avant d'évaluer la formule. Cette méthode est absente des autres classes.

   Quels sont les avantages et inconvénients d'utiliser des objets et des méthodes plutôt que des enregistrements et des fonctions? Est-il difficile d'ajouter un nouveau type d'expression? Pouvez-vous facilement implémenter une méthode de simplification d'expression?

3. Elu par cette crapule. Un palindrome est un texte qui est indépendant du sens de la lecture. "Radar", "ici" et "elu par cette crapule" (sans les espaces) en sont des exemples. Le but de l'exercice est d'écrire un programme qui détermine si une chaîne de caractères est un palindrome.

   L'algorithme devra utiliser une classe Sequence. Un objet de cette classe représente une liste modifiable d'éléments. Nous utilisons le mot séquence pour éviter toute confusion avec les listes. L'objet permet d'accéder aux premier et derniers éléments de la séquence, ainsi que d'ajouter et retirer des éléments. Les méthodes de la classe Sequence sont

   • isEmpty($) renvoie true si la séquence est vide, false sinon.
   • first($) renvoie le premier élément.
   • last($) renvoie le dernier élément.
   • insertFirst(X) ajoute l'élément X au début de la séquence.
   • insertLast(X) ajoute l'élément X à la fin de la séquence.
   • removeFirst retire le premier élément.
   • removeLast retire le dernier élément.

   Voici l'algorithme, décrit dans les commentaires de la fonction Palindrome.

      fun {Palindrome Xs}
         S={New Sequence init}
         fun {Check}
            %% si S est vide, alors Xs est un palindrome
            %% sinon, on compare les premier et dernier elements de S:
            %%  - s'ils sont egaux, on les retire de S et on continue
            %%  - sinon, Xs n'est pas un palindrome
         end
      in
         %% mettre tous les elements de Xs dans S (dans l'ordre)
         {Check}
      end
   

   Implémentez la classe Sequence et complétez la fonction Palindrome.