UP | HOME

Le problème de l'expression en Typescript et Java
Solution par agrégation avec délégation

Table of Contents

1 Consignes - Remarques préalables

  • Durée de l'évaluation : 2h30'
  • Langage : Java 8 ou Typescript 3

Organisation du travail et rendu

  • Typescript : Créer un nouveau répertoire Nom_eval (où Nom est votre nom) sous le répertoire typescript. Développer ensuite votre code dans ce répertoire. Finalement, archiver au format zip ce répertoire puis déposer l'archive sur Campus.
  • Java : Créer un nouveau projet Java Nom_eval (où Nom est votre nom), 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.
  • Par la suite, on entend par "unité" (de compilation)
    • en Typescript : un fichier, contenant des définitions d'interfaces et de classes, à exporter, si elles doivent être accessibles d'autres unités, qui les importent,
    • en Java : un paquet ("package"), contenant les définitions d'interfaces et de classes publiques dans des fichiers.
  • Quatre unités sont utilisées pour les développements : etat, service, synthese et test. En typescript, elles correspondent à quatre fichiers, en Java, à quatre paquets.

Remarques

  • Par la suite, on désigne
    • par Flottant
      • le type float (ou Float, le type enveloppe associé) en Java, ou
      • le type number en Typescript,
    • par Booleen
      • le type boolean (ou Boolean, le type enveloppe associé) en Java, ou
      • le type boolean en Typescript,
    • et par Mot
      • le type String en Java, ou
      • le type string en Typescript.
  • Une fonction de paramètre un A et renvoyant un B a pour type
    • en Typescript : (x : A) => B,
    • en Java : Function<A, B> (du paquet javal.util.function).
  • Une fonction de paramètres un A et un B, et renvoyant un C, a pour type
    • en Typescript : (x : A, y : B) => C,
    • en Java : BiFunction<A, B, C> (du paquet javal.util.function).
  • Des diagrammes de types (interfaces et classes) sont donnés à la fin du sujet. Ils sont identiques en Java et en Typescript.
  • De nombreuses définitions de types sont paramétrées par un type noté T. Ce paramètre de type sera instancié par les différents types représentant les expressions.

2 Le problème de l'expression

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 et en Typescript 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'agrégation avec délégation.

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

3 Une architecture en deux couches

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ée par les définitions des fonctions pour ce cas ;
  • par fonction : chaque fonction regroupe les définitions pour tous les 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é et l'agrégation avec délégation.

Couche haute
Fonction F1
F1 / C1
F1 / C2
Fonction F2
F2 / C1
F2 / C2
Cas C1
Cas C2
Couche basse

4 Des expressions numériques, des fonctions et deux extensions

On utilise des expressions numériques définies ainsi.

Une expression numérique est

  • soit un littéral formé à partir d'un nombre (représenté par un Flottant),
  • soit une addition formée à partir de deux expressions numériques.

Voici la grammaire correspondante.

Exp1 ::= Lit(n) | Add(exp1, exp1)
   n ::= ... // Un nombre (représenté par un Flottant)

On considère initialement les deux fonctions suivantes.

  • eval : Exp1 -> Flottant : fonction d'évaluation d'une expression numérique produisant un Flottant.
  • equiv : Exp1 x Exp1 -> Booleen : fonction testant l'équivalence entre deux expressions, deux expressions étant équivalentes si elles s'évaluent en la même valeur.

Précisément, la fonction eval est spécifiée ainsi.

- eval(Lit(n)) = n
- eval(Add(a, b)) = eval(a) + eval(b)

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 numérique étendue est

  • soit un littéral formé à partir d'un nombre (représenté par un Flottant),
  • soit une addition formée à partir de deux expressions numériques,
  • soit une multiplication formée à partir de deux expressions numériques.

Voici la grammaire correspondante.

Exp2 ::= Lit(n) | Add(Exp2, Exp2) | Mult(Exp2, Exp2)
   n ::= ... // Un nombre (représenté par un Flottant)

La fonction eval est spécifiée ainsi pour une multiplication.

- eval(Mult(a, b)) = eval(a) * eval(b)

On considère la fonction supplémentaire suivante.

  • notation : Exp2 -> Mot : fonction de notation d'une expression numérique produisant un mot (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) *

5 Couche basse - Version initiale - Unité etat

On définit des types (interfaces et classes d'implémentations) pour décrire les expressions correspondant à la couche basse. Ce sont des types génériques lorsqu'ils dépendent du type réel des expressions (représenté par le paramètre de type T). Deux cas sont présentés : un cas de base, pour les littéraux, et un cas construit pour les opérations binaires, comme les additions ou les multiplications.

Littéraux

  • Définir l'interface FiltrageLitteral avec une méthode générique filtrageCas. Cette méthode, paramétrée par le type R, prend en paramètre une fonction de Flottant dans R et renvoie un R.
  • Définir la classe Litteral implémentant FiltrageLitteral. Cette classe possède un attribut de type Flottant, initialisé par le paramètre du constructeur.

Opérations binaires

  • Définir l'interface générique FiltrageOperationBinaire<T> avec une méthode générique filtrageCas. Cette méthode, paramétrée par le type R, prend en paramètre une fonction prenant deux T et renvoyant un R et renvoie un R.
  • Définir la classe générique OperationBinaire<T> implémentant FiltrageOperationBinaire<T>. Cette classe possède deux attributs de type T, initialisés par les paramètres du constructeur.

On définit les interfaces des fabriques associées aux différentes expressions.

Fabriques

  • Définir une fabrique générique FabriqueLitteral<T>. Elle possède une méthode litteral prenant un Flottant et renvoyant un T.
  • Définir une fabrique générique FabriqueAddition<T>. Elle possède une méthode addition prenant deux T et renvoyant un T.
  • Définir l'interface FabriqueLitteralAddition<T> héritant de FabriqueLitteral<T> et de FabriqueAddition<T>.

6 Couche haute - Version initiale - Unité service

Tout d'abord, 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). Ensuite, on définit les implémentations de ces interfaces, en utilisant l'agrégation avec délégation.

Cette couche peut se décomposer en deux sous-couches.

  • L'équivalence universelle se calcule à partir d'une évaluation.
  • Une évaluation se calcule à partir d'une expression, un littéral ou une expression binaire.

Evaluation

  • Définir l'interface Evaluation déclarant la méthode d'évaluation eval, sans paramètre et renvoyant un Flottant.

Equivalence

  • Définir l'interface générique Equivalence<T> déclarant la méthode testant l'équivalence, equivalentA prenant un T et renvoyant un Booleen.

Implémentations de l'interface Evaluation

  • Définir deux classes EvaluationLitteral et EvaluationAddition<T> implémentant Evaluation.
    • Ces deux classes possèdent une expression comme unique attribut, de type FiltrageLitteral et FiltrageOperationBinaire<T> respectivement. Chaque attribut est initialisé par le paramètre du constructeur.
    • L'implémentation de la méthode eval utilise la méthode filtrageCas.
    • Le paramètre de type T doit être majoré.

Implémentation de l'interface Equivalence<T>

  • Définir une classe EquivalenceUniverselle<T> implémentant Equivalence<T>.
    • Cette classe possède un attribut de type Evaluation, initialisé par le paramètre du constructeur.
    • Le paramètre de type T doit être majoré.

7 Synthèse des expressions - Version initiale - Unité synthese

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 générique d'expressions formées de littéraux et d'opérations binaires, munies de deux fonctions, l'évaluation et l'équivalence.

Littéraux génériques

  • Définir la classe Litteral_EE<T> implémentant FiltrageLitteral, Evaluation et Equivalence<T>.
    • Cette classe possède trois attributs, de type FiltrageLitteral, Evaluation et Equivalence<T>, initialisés à partir du paramètre du constructeur de type Flottant.
    • Les trois méthodes sont implémentées par délégation aux attributs.
    • Le paramètre de type T doit être majoré.

Opérations binaires génériques

  • Définir la classe Operation_EE<T> implémentant FiltrageOperationBinaire, Evaluation et Equivalence<T>.
    • Cette classe possède trois attributs, de type FiltrageOperationBinaire<T>, Evaluation et Equivalence<T>, initialisés à partir des paramètres du constructeur de type FiltrageOperationBinaire<T> et Evaluation respectivement.
    • Les trois méthodes sont implémentées par délégation aux attributs.
    • Le paramètre de type T doit être majoré.

Il devient possible de définir l'ensemble des expressions muni de deux fonctions, l'évaluation et l'équivalence, en héritant des définitions génériques précédentes.

Interface des expressions

  • Définir l'interface Expression_LA_EE par héritage de Evaluation et de Equivalence, correctement instancié.
    • Déclarer une méthode générique filtrage, paramétrée par R, prenant comme paramètres deux fonctions pour traiter le cas des littéraux et des additions respectivement, et renvoyant un R.

Implémentation des littéraux

  • Définir la classe Litteral_LA_EE implémentant Expression_LA_EE par héritage de Litteral_EE, correctement instancié.
    • Définir un constructeur avec un Flottant pour paramètre.

Implémentation des additions

  • Définir la classe Addition_LA_EE implémentant Expression_LA_EE par héritage de Operation_EE, correctement instancié.
    • Définir un constructeur avec deux expressions de type Expression_LA_EE pour paramètres.

Fabrique d'expressions

  • Définir une classe FabriqueExpression_LA_EE implémentant FabriqueLitteralAddition<Expression_LA_EE>.

8 Test 1 - Unité test

Test générique des expressions

  • Définir un test en appelant la fonction versionInitiale définie ci-dessous.
  • Majorer le paramètre de type T de manière à rendre la fonction la plus générale possible.
  • Exécuter pour tester.

Java

static <T extends ...> 
  void versionInitiale(FabriqueLitteralAddition<T> fab) { 
    System.out.println("***** test add *****");
    T cinq = fab.litteral(5);
    System.out.println("5 : " + cinq.eval());
    T sept = fab.litteral(7);
    System.out.println("false : " + cinq.equivalentA(sept));
    T add_5_7 = fab.addition(cinq, sept);
    System.out.println("12 : " + add_5_7.eval());
    System.out.println("true : " + add_5_7.equivalentA(fab.litteral(12)));
    System.out.println("false : " + add_5_7.equivalentA(fab.litteral(13)));             
}

Typescript

function versionInitiale<T extends ...>(
  fab: FabriqueLitteralAddition<T>) {
  console.log("***** test add *****");
  let cinq = fab.litteral(5);
  console.log("5 : " + cinq.eval());
  let sept = fab.litteral(7);
  console.log("false : " + cinq.equivalentA(sept));
  let add_5_7 = fab.addition(cinq, sept);
  console.log("12 : " + add_5_7.eval());
  console.log("true : " + add_5_7.equivalentA(fab.litteral(12)));
  console.log("false : " + add_5_7.equivalentA(fab.litteral(13)));
}

9 Couche basse - Une extension par un nouveau cas - Unité etat

On étend la couche basse en rajoutant un cas analogue à l'addition, la multiplication. Comme la multiplication est une opération binaire comme l'addition, il suffit d'ajouter des fabriques comprenant la multiplication.

Fabriques pour la multiplication

  • Définir une fabrique générique FabriqueMultiplication<T>. Elle possède une méthode multiplication prenant deux T et renvoyant un T.
  • Définir l'interface FabriqueLitteralAdditionMultiplication<T> héritant de FabriqueLitteralAddition<T> et de FabriqueMultiplication<T>.

10 Couche haute - Extension des fonctions pour le nouveau cas - Unité service

Comme l'équivalence est définie universellement (pour tous les cas), seule l'évaluation est à définir pour la multiplication.

Implémentations de l'interface Evaluation pour la multiplication

  • Définir une classe EvaluationMultiplication<T> implémentant Evaluation.
    • Cette classe possède une expression comme unique attribut, de type FiltrageOperationBinaire<T>. L'attribut est initialisé par le paramètre du constructeur.
    • L'implémentation de la méthode eval utilise la méthode filtrageCas.
    • Le paramètre de type T doit être majoré.

11 Synthèse - Version étendue par un cas - Unité synthese

Comme précédemment, il devient possible de définir l'ensemble des expressions étendues muni de deux fonctions, l'évaluation et l'équivalence, en héritant des définitions génériques précédentes.

Interface des expressions étendues

  • Définir l'interface Expression_LAM_EE par héritage de Evaluation et de Equivalence, correctement instancié.
    • Déclarer une méthode générique filtrage, paramétrée par R, prenant comme paramètres trois fonctions pour traiter le cas des littéraux, des additions et des multiplications respectivement, et renvoyant un R.

Implémentation des littéraux

  • Définir la classe Litteral_LAM_EE implémentant Expression_LAM_EE par héritage de Litteral_EE, correctement instancié.
    • Définir un constructeur avec un Flottant pour paramètre.

Implémentation des additions

  • Définir la classe Addition_LAM_EE implémentant Expression_LAM_EE par héritage de Operation_EE, correctement instancié.
    • Définir un constructeur avec deux expressions de type Expression_LAM_EE pour paramètres.

Implémentation des multiplications

  • Définir la classe Multiplication_LAM_EE implémentant Expression_LAM_EE par héritage de Operation_EE, correctement instancié.
    • Définir un constructeur avec deux expressions de type Expression_LAM_EE pour paramètres.

Fabrique d'expressions étendues

  • Définir une classe FabriqueExpression_LAM_EE implémentant FabriqueLitteralAdditionMultiplication<Expression_LAM_EE>.

12 Test 2 - Unité test

Test générique des expressions étendues

  • Définir un test en appliquant à la même fabrique la fonction versionInitiale et la fonction versionEtendueParUnCas définie ci-dessous.
  • Majorer le paramètre de type T de manière à rendre la fonction la plus générale possible.
  • Exécuter pour tester.

Java

static <T extends ...> 
  void versionEtendueParUnCas(
    FabriqueLitteralAdditionMultiplication<T> fab) {
      System.out.println("***** test multi *****");
      T cinq = fab.litteral(5);
      System.out.println("5 : " + cinq.eval());
      T sept = fab.litteral(7);
      System.out.println("false : " + cinq.equivalentA(sept));
      T mult_5_7 = fab.multiplication(cinq, sept);
      System.out.println("35 : " + mult_5_7.eval());
      System.out.println("true : " + mult_5_7.equivalentA(fab.litteral(35)));
      System.out.println("false : " + mult_5_7.equivalentA(fab.litteral(36)));
    }

Typescript

function versionEtendueParUnCas<T extends ...>(
  fab: FabriqueLitteralAdditionMultiplication<T>) {
  console.log("***** test multi *****");
  let cinq = fab.litteral(5);
  console.log("5 : " + cinq.eval());
  let sept = fab.litteral(7);
  console.log("false : " + cinq.equivalentA(sept));
  let mult_5_7 = fab.multiplication(cinq, sept);
  console.log("35 : " + mult_5_7.eval());
  console.log("true : " + mult_5_7.equivalentA(fab.litteral(35)));
  console.log("false : " + mult_5_7.equivalentA(fab.litteral(36)));
}

13 Couche haute - Une extension par une nouvelle fonction - Unité service

On définit une interface pour décrire la fonction de notation permettant d'obtenir une représentation en notation polonaise inversée. Ensuite, on définit les implémentations de cette interface, en utilisant l'agrégation avec délégation.

Notation

  • Définir l'interface Notation déclarant la méthode representation, sans paramètre et renvoyant un Mot (string ou String).

Implémentations de l'interface Notation

  • Définir trois classes NotationPolonaiseInverseeLitteral, NotationPolonaiseInverseeAddition<T> et NotationPolonaiseInverseeMultiplication<T> implémentant Notation.
    • Ces trois classes possèdent une expression comme unique attribut, de type FiltrageLitteral pour la première et FiltrageOperationBinaire<T> pour les deux autres. Chaque attribut est initialisé par le paramètre du constructeur.
    • L'implémentation de la méthode representation utilise la méthode filtrageCas.
    • Le paramètre de type T doit être majoré.

14 Synthèse - Version étendue par un cas et une fonction - Unité synthese

Comme précédemment, une fois que les couches hautes et basses sont implémentées, il est possible de les combiner pour obtenir une seconde implémentation générique d'expressions formées de littéraux et d'opérations binaires, munies de trois fonctions, l'évaluation, l'équivalence et la notation polonaise inversée.

Littéraux génériques

  • Définir la classe Litteral_EEN<T> implémentant FiltrageLitteral, Evaluation, Equivalence<T> et Notation.
    • Procéder par héritage de Litteral_EE<T>.
    • La méthode representation est implémentée par délégation à un nouvel attribut.
    • Le paramètre de type T doit être majoré.

Opérations binaires génériques

  • Définir la classe Operation_EEN<T> implémentant FiltrageOperationBinaire, Evaluation, Equivalence<T> et Notation.
    • Procéder par héritage de Operation_EE<T>.
    • La méthode representation est implémentée par délégation à un nouvel attribut.
    • Le paramètre de type T doit être majoré.

Il devient maintenant possible de définir l'ensemble des expressions étendues muni de trois fonctions, l'évaluation, l'équivalence et la notation polonaise inversée, en héritant des définitions précédentes.

Interface des expressions étendues munies de trois fonctions

  • Définir l'interface Expression_LAM_EEN par héritage de Evaluation, de Equivalence, correctement instancié, et de Notation.
    • Déclarer une méthode générique filtrage, paramétrée par R, prenant comme paramètres trois fonctions pour traiter le cas des littéraux, des additions et des multiplications respectivement, et renvoyant un R.

Implémentation des littéraux

  • Définir la classe Litteral_LAM_EEN implémentant Expression_LAM_EEN par héritage de Litteral_EEN, correctement instancié.
    • Définir un constructeur avec un Flottant pour paramètre.

Implémentation des additions

  • Définir la classe Addition_LAM_EEN implémentant Expression_LAM_EEN par héritage de Operation_EEN, correctement instancié.
    • Définir un constructeur avec deux expressions de type Expression_LAM_EEN pour paramètres.

Implémentation des multiplications

  • Définir la classe Multiplication_LAM_EEN implémentant Expression_LAM_EEN par héritage de Operation_EEN, correctement instancié.
    • Définir un constructeur avec deux expressions de type Expression_LAM_EEN pour paramètres.

Fabrique d'expressions étendues munies de trois fonctions

  • Définir une classe FabriqueExpression_LAM_EEN implémentant FabriqueLitteralAdditionMultiplication<Expression_LAM_EEN>.

15 Test 3 - Unité test

Test générique des expressions étendues

  • Définir un test en appliquant à la même fabrique les fonctions versionInitiale et versionEtendueParUnCas et la fonction versionEtendueParUnCasEtUneFonction définie ci-dessous.
  • Majorer le paramètre de type T de manière à rendre cette dernière fonction la plus générale possible.
  • Exécuter pour tester.

Java

static <T extends ...> 
  void versionEtendueParUnCasEtUneFonction(
    FabriqueLitteralAdditionMultiplication<T> fab) {
    System.out.println("***** test notation *****");
    T cinq = fab.litteral(5);
    System.out.println("5 : " + cinq.representation());
    T sept = fab.litteral(7);
    System.out.println("7 : " + sept.representation());
    T add_5_7 = fab.addition(cinq, sept);
    System.out.println("5  7 + : " + add_5_7.representation());
    T mult_5_7 = fab.multiplication(cinq, sept);
    System.out.println("5  7 * : " + mult_5_7.representation());
  }

Typescript

function versionEtendueParUnCasEtUneFonction<T extends ...>(
  fab: FabriqueLitteralAdditionMultiplication<T>) {
  console.log("***** test notation *****");
  let cinq = fab.litteral(5);
  console.log("5 : " + cinq.representation());
  let sept = fab.litteral(7);
  console.log("7 : " + sept.representation());
  let add_5_7 = fab.addition(cinq, sept);
  console.log("5 7 + : " + add_5_7.representation());
  let mult_5_7 = fab.multiplication(cinq, sept);
  console.log("5 7 * : " + mult_5_7.representation());
}

16 En résumé - Les diagrammes de types

16.1 Unité etat

Eval_etat.png

Figure 1: Couche basse

16.2 Unité service

Eval_service.png

Figure 2: Couche haute

16.3 Unité synthese

Eval_synthese1et2.png

Figure 3: Synthèse - Premier et second cas

Eval_synthese3.png

Figure 4: Synthèse - Troisième cas

Eval_fabriques.png

Figure 5: Synthèse - Les fabriques

Author: Hervé Grall
Version history: v1: 2018-12-04.
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.