Le problème de l'expression

• Durée de l'évaluation : 1h15'
• Créer un nouveau projet Java ArchiLog17_eval, puis un paquet eval. Développer ensuite votre code dans ce paquet. Finalement, exporter votre projet (Export > General > Archive File) puis déposer sur Campus.
• Remarques
  • On utilise la terminologie suivante.
    • Un attribut est dit déclaré lorsqu'il est nommé et typé mais pas initialisé.
    • Une méthode est dite déclarée lorsqu'elle est nommée et typée mais pas implémentée.
    • Une méthode est dite définie lorsqu'elle est nommée, typée et implémentée.

    • Etant donné une interface générique P<T>, une interface I a la propriété P si elle est déclarée ainsi.

      interface I extends P<I> { ... }
      

      De même, une classe C a la propriété P si elle est déclarée ainsi.

      class C implements P<C> { ... }
      

      Si la classe C implémente l'interface I et l'interface P<I>, on dit aussi que C a la propriété P.

      class C implements I, P<I> { ... }
      

      Cette définition se généralise au cas de plusieurs propriétés.

  • Le langage de programmation utilisé est Java, version 8.
  • On utilise particulièrement des interfaces concrètes, au sens où elles contiennent des méthodes définies. Dans ce cas, ces méthodes sont précédées du mot-clé default.
  • Lorsqu'une interface I est concrète, au sens où toutes ses méthodes sont définies, il est possible de construire un objet de type I par l'appel new I(){}.

Le problème de l'expression est le suivant.

• Définir un type inductif de données et des fonctions de domaine ce type, de manière à ce qu'il soit possible d'ajouter de nouveaux cas à la définition et de nouvelles fonctions de domaine ce type, en respectant les principes suivants de modularité :
  • ouverture aux extensions dans les deux dimensions (nouveau cas de définition, nouvelle fonction),
  • fermeture aux modifications (pas de modification du code existant avant l'extension),
  • absence de redondance,
  • exhaustivité combinatoire (possibilité de toute combinaison entre un sous-ensemble de cas et un sous-ensemble de fonctions).

Le terme "expression" fait référence non seulement au type inductif de données, supposé définir des expressions d'un langage particulier, mais aussi aux capacités expressives du langage de programmation. Le problème de l'expression devient alors un outil pour comparer les capacités expressives des langages de programmation, suivant la qualité des solutions proposées à ce problème.

On montre ici qu'il est possible de résoudre le problème de l'expression en Java de manière optimale, en utilisant les techniques modulaires vues en cours :

• définition de propriétés par des interfaces,
• factorisation des architectures en couches, en utilisant l'héritage multiple.

La solution proposée est une généralisation d'une solution proposée récemment lors de la conférence Modularity.

Le problème des expressions présente deux couches :

• une couche basse, formée des expressions,
• une couche haute, formée des fonctions, qui sont implémentées en utilisant les expressions, typiquement de manière récursive.

Une solution doit permettre de définir

• une couche basse, donnant la définition de chaque cas,
• une couche haute, donnant la définition de chaque fonction pour chaque cas.

Les solutions traditionnelles correspondent à deux constructions orthogonales, à partir des définitions des cas de la couche basse :

• par cas : chaque définition d'un cas de la couche basse est complété par les définitions des fonctions pour ce cas ;
• par fonction : une fonction regroupe les définitions pour chaque cas.

La première solution permet d'ajouter facilement un cas, mais pas une fonction, la seconde solution permet d'ajouter facilement une fonction, mais pas un cas.

Nous proposons une solution permettant de définir séparément non seulement les cas dans la couche basse, mais aussi les fonctions déclinées par cas, puis de les combiner. La solution repose sur la généricité.

On utilise des expressions arithmétiques définies ainsi.

Une expression arithmétique est

• soit un littéral formé à partir d'un entier relatif (représenté par un int),
• soit une addition formée à partir de deux expressions arithmétiques.

Voici la grammaire correspondante.

exp1 ::= Lit(n) | Add(exp1, exp1)
   n ::= ... // Un entier relatif (représenté par un int)

On considère initialement les deux fonctions suivantes.

• eval : exp1 -> int : fonction d'évaluation d'une expression arithmétique produisant un int.
• equiv : exp1 x exp1 -> boolean : fonction testant l'équivalence entre deux expressions, deux expressions étant équivalentes si elles s'évaluent en la même valeur.

Ensuite on envisage deux extensions, dans les deux dimensions, celle des expressions avec un nouveau cas, la multiplication, et celle des fonctions, avec une notation suffixe ou polonaise inversée des expressions.

Une expression arithmétique étendue est

• soit un littéral formé à partir d'un entier relatif (représenté par un int),
• soit une addition formée à partir de deux expressions arithmétiques,
• soit une multiplication formée à partir de deux expressions arithmétiques.

Voici la grammaire correspondante.

exp2 ::= Lit(n) | Add(exp2, exp2) | Mult(exp2, exp2)
   n ::= ... // Un entier relatif (représenté par un int)

On considère la fonction supplémentaire suivante.

• notation : exp2 -> String : fonction de notation d'une expression arithmétique produisant une chaîne de caractères, la notation suffixe de l'expression.

La fonction notation est spécifiée ainsi.

- notation(Lit(n)) = n
- notation(Add(a, b)) = notation(a) notation(b) +
- notation(Mult(a, b) = notation(a) notation(b) *

On définit des interfaces pour décrire les états et les fabriques correspondant à la couche basse. Ce sont des interfaces exprimant des propriétés, génériques lorsqu'elles dépendent du type des expressions (représenté par le paramètre de type T).

Littéraux

• Définir l'interface EtatLitteral avec deux méthodes.
  • Définir le sélecteur boolean estLitteral() : il renvoie false par défaut.
  • Définir l'accesseur int val() : il renvoie une exception de type UnsupportedOperationException par défaut.
• Définir une interface générique FabriqueLitteral<T> avec une méthode.
  • Déclarer la fabrique T litteral(int val) : elle renverra une expression littérale de valeur val.

Additions

• Définir l'interface générique EtatAddition<T> avec trois méthodes.
  • Définir le sélecteur boolean estAddition() : il renvoie false par défaut.
  • Définir les deux accesseurs aux deux membres de l'addition, T gaucheAddition() et T droitAddition() : ils renvoient une exception de type UnsupportedOperationException par défaut.
• Définir une interface générique FabriqueAddition<T> avec une méthode.
  • Déclarer la fabrique abstraite T addition(T g, T d) : elle renverra une expression représentant une addition à partir de deux expressions.

On définit des classes implémentant les interfaces décrivant les états.

Littéraux

• Définir la classe d'implémentation CasLitteral implémentant l'interface EtatLitteral.
  • Déclarer un attribut de type int et définir le constructeur associé.
  • Définir les deux méthodes à implémenter.

Additions

• Définir la classe d'implémentation CasAddition<T> implémentant l'interface EtatAddition<T>.
  • Déclarer deux attributs de type T et définir le constructeur associé.
  • Définir les trois méthodes à implémenter.

On définit des interfaces pour décrire les fonctions de la couche haute. Ce sont des interfaces exprimant des propriétés, génériques lorsqu'elles dépendent du type des expressions (représenté par le paramètre de type T).

Evaluation

• Définir l'interface ServiceEvaluation déclarant la méthode d'évaluation.
  • Déclarer la méthode int eval().

Equivalence

• Définir l'interface générique ServiceEquivalence<T> déclarant la méthode testant l'équivalence.
  • Déclarer la méthode estEquivalent, à typer correctement.

Pour chaque cas possible pour les expressions, on définit des interfaces concrètes implémentant les interfaces décrivant les services.

Evaluation - Littéraux

• Définir l'interface EvaluationCasLitteral étendant EtatLitteral et ServiceEvaluation.
  • Définir la méthode eval : elle renvoie le int associé au littéral cible.

Evaluation - Additions

• Définir l'interface générique EvaluationCasAddition<T> étendant EtatAddition<T> et ServiceEvaluation.
  • Majorer le paramètre de type T.
  • Définir la méthode eval : elle renvoie la somme des évaluations des deux membres de l'addition.

Equivalence - Littéraux et additions

• Définir l'interface générique EquivalenceCasUniversel<T> étendant ServiceEvaluation et ServiceEquivalence<T>.
  • Majorer le paramètre de type T.
  • Définir la méthode estEquivalent : deux expressions sont équivalentes si elles s'évaluent en le même int.

Une fois que les couches hautes et basses sont implémentées, il est possible de les combiner pour obtenir une première implémentation d'expressions formées de littéraux et d'additions.

Fabrique générique

• Définir une interface générique FabriqueLitteralAddition<T> par héritage de FabriqueLitteral<T> et de FabriqueAddition<T>.

Expressions et fabriques d'expressions

• Définir pour les expressions une interface ExpressionLA, ayant les propriétés définies par les interfaces EtatLitteral, EtatAddition, FabriqueLitteralAddition, ServiceEvaluation et ServiceEquivalence. Le paramètre de type T utilisé dans les définitions génériques est instancié par ExpressionLA, ici comme dans les définitions suivantes.
• Définir pour les fabriques une interface FabriqueExpressionLA ayant la propriété FabriqueLitteralAddition<ExpressionLA>.
  • Définir les deux fabriques par appel des constructeurs des classes LitteralLA et AdditionLA, spécifiées ci-dessous.

Implémentation des expressions

• Définir la classe LitteralLA implémentant ExpressionLA et représentant les littéraux, par héritage de la classe CasLitteral et ayant les propriétés EvaluationCasLitteral, EquivalenceCasUniversel et FabriqueExpressionLA.
• Définir la classe AdditionLA implémentant ExpressionLA et représentant les additions de manière analogue.

Test

• Définir une fonction principale de test en appelant la fonction versionInitiale définie ci-dessous. Exécuter pour tester.

private static <T extends ServiceEvaluation & ServiceEquivalence<T>> 
  void versionInitiale(FabriqueLitteralAddition<T> fab) {             
  T cinq = fab.litteral(5);
  T sept = fab.litteral(7);
  T add_5_7 = fab.addition(cinq, sept);
  System.out.println("12 : " + add_5_7.eval());
  System.out.println("true : " + add_5_7.estEquivalent(fab.litteral(12)));
  System.out.println("false : " + add_5_7.estEquivalent(fab.litteral(13)));
}

On étend la couche basse en rajoutant un cas analogue à l'addition, la multiplication. On commence par définir deux interfaces pour décrire les états et les fabriques correspondant aux multiplications.

Multiplications

• Définir l'interface générique EtatMultiplication<T> avec trois méthodes.
  • Définir le sélecteur boolean estMultiplication() : il renvoie false par défaut.
  • Définir les deux accesseurs aux deux membres de la multiplication, T gaucheMultiplication() et T droitMultiplication() : ils renvoient une exception de type UnsupportedOperationException par défaut.
• Définir une interface générique FabriqueMultiplication<T> avec une méthode.
  • Déclarer la fabrique abstraite T multiplication(T g, T d) : elle renverra une expression représentant une multiplication à partir de deux expressions.

On définit une classe implémentant l'interface décrivant les états des multiplications.

Multiplications

• Définir la classe d'implémentation CasMultiplication<T> implémentant l'interface EtatMultiplication<T>.
  • Déclarer deux attributs de type T et définir le constructeur associé.
  • Définir les trois méthodes à implémenter.

Pour le nouveau cas possible pour les expressions, on définit des interfaces concrètes implémentant les interfaces décrivant les services. Une seule interface est à définir puisque l'équivalence entre expressions a été définie pour tous les cas possibles.

Evaluation - Multiplications

• Définir l'interface générique EvaluationCasMultiplication<T> étendant EtatMultiplication<T> et ServiceEvaluation.
  • Majorer le paramètre de type T.
  • Définir la méthode eval : elle renvoie le produit des évaluations des deux membres de la multiplication.

Une fois que les couches hautes et basses ont été étendues, il est possible de les combiner pour obtenir une seconde implémentation d'expressions formées de littéraux, d'additions et de multiplications.

Fabrique générique

• Définir une interface générique FabriqueLitteralAdditionMultiplication<T> par héritage de FabriqueLitteralAddition<T> et de FabriqueMultiplication<T>.

Expressions et fabriques d'expressions

• Définir pour les expressions une interface ExpressionLAM, ayant les propriétés définies par les interfaces EtatLitteral, EtatAddition, EtatMultiplication, FabriqueLitteralAdditionMultiplication, ServiceEvaluation et ServiceEquivalence. Le paramètre de type T utilisé dans les définitions génériques est instancié par ExpressionLAM, ici comme dans les définitions suivantes.
• Définir pour les fabriques une interface FabriqueExpressionLAM ayant la propriété FabriqueLitteralAdditionMultiplication<ExpressionLAM>.
  • Définir les trois fabriques par appel des constructeurs des classes LitteralLAM, AdditionLAM et MultiplicationLAM, spécifiées ci-dessous.

Implémentation des expressions

• Définir la classe LitteralLAM implémentant ExpressionLAM et représentant les littéraux, par héritage de la classe CasLitteral et ayant les propriétés EvaluationCasLitteral, EquivalenceCasUniversel et FabriqueExpressionLAM.
• Définir la classe AdditionLAM implémentant ExpressionLAM et représentant les additions de manière analogue.
• Définir la classe MultiplicationLAM implémentant ExpressionLAM et représentant les multiplications de manière analogue.

Test

• Définir deux tests supplémentaires dans la fonction principale de test :
  • le premier appelle la fonction versionInitiale avec pour argument une fabrique d'expressions de type ExpressionLAM ;
  • le second appelle la fonction versionEtendueParUnCas définie ci-dessous, partiellement et qu'on complétera.
• Exécuter pour tester.

private static <T ...> // TODO Quantification à relativiser
  void versionEtendueParUnCas(FabriqueLitteralAdditionMultiplication<T> fab) {                
  T cinq = fab.litteral(5);
  T sept = fab.litteral(7);
  T mult_5_7 = fab.multiplication(cinq, sept);
  System.out.println("35 : " + mult_5_7.eval());
  System.out.println("true : " + mult_5_7.estEquivalent(fab.litteral(35)));
  System.out.println("false : " + mult_5_7.estEquivalent(fab.litteral(36)));
}

On étend la couche haute par la fonction notation, donnant la notation suffixe ou polonaise inversée d'une expression.

Notation

• Définir l'interface ServiceNotation déclarant la méthode de notation.
  • Déclarer la méthode String representer().

Pour chaque cas possible pour les expressions, on définit des interfaces concrètes implémentant l'interface ServiceNotation.

Notation - Littéraux

• Définir l'interface NotationCasLitteral étendant EtatLitteral et ServiceNotation.
  • Définir la méthode representer : elle renvoie le int associé au littéral cible sous forme d'une String.

Notation - Additions

• Définir l'interface générique NotationCasAddition<T> étendant EtatAddition<T> et ServiceNotation.
  • Majorer le paramètre de type T.
  • Définir la méthode representer : elle renvoie la concaténation des notations des deux membres de l'addition, séparées par un espace, suivie d'un espace et de \(+\).

Notation - Multiplications

• Définir l'interface générique NotationCasMultiplication<T> étendant EtatMultiplication<T> et ServiceNotation.
  • Majorer le paramètre de type T.
  • Définir la méthode representer : elle renvoie la concaténation des notations des deux membres de la multiplication, séparées par un espace, suivie d'un espace et de \(\ast\).

Une fois que la couche haute a été étendue, il est possible de la combiner à l'existant pour obtenir une troisième implémentation d'expressions formées de littéraux, d'additions et de multiplications et munies de trois fonctions au lieu de deux : évaluation, équivalence et notation.

Expressions et fabriques d'expressions

• Définir pour les expressions une interface ExpressionLAME, ayant les propriétés définies par les interfaces EtatLitteral, EtatAddition, EtatMultiplication, FabriqueLitteralAdditionMultiplication, ServiceEvaluation, ServiceEquivalence et ServiceNotation. Le paramètre de type T utilisé dans les définitions génériques est instancié par ExpressionLAME, ici comme dans les définitions suivantes.
• Définir pour les fabriques une interface FabriqueExpressionLAME ayant la propriété FabriqueLitteralAdditionMultiplication<ExpressionLAME>.
  • Définir les trois fabriques par appel des constructeurs des classes LitteralLAME, AdditionLAME et MultiplicationLAME, spécifiées ci-dessous.

Implémentation des expressions

• Définir la classe LitteralLAME implémentant ExpressionLAME et représentant les littéraux, par héritage de la classe CasLitteral et ayant les propriétés EvaluationCasLitteral, EquivalenceCasUniversel, NotationCasLitteral et FabriqueExpressionLAME.
• Définir la classe AdditionLAME implémentant ExpressionLAME et représentant les additions de manière analogue.
• Définir la classe MultiplicationLAME implémentant ExpressionLAME et représentant les multiplications de manière analogue.

Test

• Définir trois tests supplémentaires dans la fonction principale de test :
  • le premier appelle la fonction versionInitiale avec pour argument une fabrique d'expressions de type ExpressionLAME ;
  • le second appelle la fonction versionEtendueParUnCas avec pour argument une fabrique d'expressions de type ExpressionLAME ;
  • le troisième appelle la fonction versionEtendueParUnCasEtUneFonction définie ci-dessous, partiellement et qu'on complétera, avec pour argument une fabrique d'expressions de type ExpressionLAME.
• Exécuter pour tester.

private static <T ...> // TODO Quantification à relativiser
  void versionEtendueParUnCasEtUneFonction(FabriqueLitteralAdditionMultiplication<T> fab) {
  T cinq = fab.litteral(5);
  T sept = fab.litteral(7);
  T neuf = fab.litteral(9);
  T add_5_7 = fab.addition(cinq, sept);
  T mult_9_add_5_7 = fab.multiplication(neuf, add_5_7);
  System.out.println("9 5 7 + * : " + mult_9_add_5_7.representer());
}