UP | HOME

Codage de types existentiels en Typescript

Table of Contents

1 Objectifs du TP

Le but du TP est de coder en Typescript des types existentiels, qui n'existent pas en Typescript. En chemin, on aborde les différences entre Java et Typescript concernant les règles de variance.

2 Variance

Les types génériques en Java ne vérifient aucune propriété de variance, ni de covariance, ni de contravariance. Cette limitation est sûre mais parfois trop restrictive.

En Typescript, la situation est moins restrictive, mais aussi moins sûre. Considérons un type générique A en Typescript, et son interprétation en une structure d'enregistrement. Considérons deux types, S et T, avec S sous-type de T. Pour comparer A<S> et A<T>, les attributs (ou propriétés dans la terminologie Javascript), éventuellement fonctionnels, sont passés successivement en revue : la variance de leur type est évaluée, en appliquant les règles correctes de variance, excepté pour le type des arguments, pour lesquels la bivariance est autorisée (au lieu de la contravariance, seule correcte). Le type A est

  • covariant si le type de tout attribut est covariant,
  • contravariant si le type de tout attribut est contravariant.

Il est possible d'interdire la bivariance pour le type des arguments, et de n'autoriser que la contravariance, en utilisant une option de compilation : "strictFunctionTypes": true. Mais cette correction n'est applicable qu'aux fonctions, et non aux méthodes.

Pour les types suivants, dire si les règles de covariance ou de contravariance s'appliquent. Préciser si elles sont correctes. Répondre en commentaire dans le fichier contenant le code.

// Variance ?
 interface Liste1<T> {
     tete(): T;
     reste(): Liste1<T>;
 }
 // Variance ?
 interface Liste2<T> {
     tete(): T;
     reste(): Liste2<T>;
     cons(t: T): Liste2<T>; // fabrique
 }
 // Variance ?
 interface Liste3<T> {
     setTete(t: T): void
     reste(): Liste3<T>;
 }
 // Variance ?
 interface Liste4<T> {
     tete(): T;
     setTete(t: T): void
     reste(): Liste4<T>;
     cons(t: T): Liste4<T>;
 }

On pourra justifier ses réponses en utilisant des fonctions de conversions comme celles suivant.

class A { }
class B extends A {
    f(): void { }
}

function covariance1(l: Liste1<B>): Liste1<A> {
    return l;
}
function contravariance1(l: Liste1<A>): Liste1<B> {
    return l;
}

3 L'absence de sûreté

Le type générique Array (représentant les tableaux) est covariant en Typescript. Montrer par un exemple produisant une erreur de type que cette règle n'est pas sûre. De même, montrer que la contravariance ne serait pas sûre. Pour simuler la contravariance, utiliser une conversion explicite. Ces exemples sont-ils possibles avec le type ReadonlyArray ?

namespace variance {
    class A { }

    class B extends A {
        f(): void { }
    }

    function produireErreurParCovariance(): void {
      // A compléter.
    }

    function produireErreurParContravariance(): void {
      // A compléter.
      // Utiliser la conversion explicite "<Array<B>>t" pour convertir "t: Array<A>". 
    }

    try {
        produireErreurParContravariance();
    } catch (e) {
        console.log(e);
    }
    console.log("********************************************************");
    try {
        produireErreurParCovariance();
    } catch (e) {
        console.log(e);
    }

}

4 Type existentiel

En Java, il existe une forme faible de type existentiel, grâce au joker ?. Précisément, cette forme correspond à une disjonction paramétrée par un type, dans l'interprétation ensembliste :

A<? extends M> = Union T tel que T sous-type de M. A<T>.

En Typescript, il n'existe pas de telle construction. Cependant, comme tout type générique est covariant, il est possible de représenter le type A<? extends M> par A<M>. Si la conversion implicite est bien vérifiée, en revanche le type A<M> permet des usages que le type A<? extends M> ne permet pas. Cette représentation n'est pas sûre. Voyons comment représenter un type existentiel en Typescript, dans l'interprétation logique.

Considérons un type générique A. On souhaite représenter A<? extends M> par un type existentiel existe T tel que T sous-type de M. A<T>.

Pour construire un élément de ce type, il suffit de disposer d'un élément de type A<T>, pour un type T sous-type de M.

Pour utiliser un tableau de ce type, voyons la règle de logique associée à l'utilisation d'une proposition existentielle.

  Gamma ⊢ ∃T.A     Gamma ⊢ ∀T.(A => R)
----------------------------------------  (R indépendant de T)
	      Gamma ⊢ R

Cette règle dite d'élimination permet de produire un résultat de type R si on dispose élément du type existentiel et d'une fonction générique qui à tout type T et à tout élément de A<T> associe un résultat de type R.

Voyons l'exemple des tableaux de type Array. Le type TableauExistentiel<M> permet de représenter Array<? extends M>.

class TableauExistentiel<M> {
    constructor(private tab: Array<M>) {
    }
    elimination<R>(k: <T extends M>(t: Array<T>) => R): R {
        return k(this.tab);
    }
}

4.1 L'usage des tableaux

Définir une fonction qui prend en argument un tableau de type TableauExistentiel<any> et retourne une chaîne de caractères représentant tous les éléments du tableau, séparés par un point-virgule.

4.2 L'exemple des files

Définissons un module pour représenter des files immutables. Il prend pour paramètres de types le type F des files et le type E des éléments de la file.

interface ModuleFile<F, E> {
    vide(): F;
    ajout(e: E, f: F): F;
    retrait(f: F): [E, F];
    estVide(f: F): boolean;
}

Nous allons développer deux implémentations de ce module, l'une fondée sur une liste fonctionnelle, l'autre fondée sur deux listes, la première représentant la queue de la file et la seconde représentant la tête de la file.

Voici l'interface et l'implémentation des listes.

interface Liste<E> {
    filtrage<R>(casVide: () => R, casCons: (t: E, r: Liste<E>) => R): R;
}

class ListeVide<E> implements Liste<E> {
    filtrage<R>(casVide: () => R, casCons: (t: E, r: Liste<E>) => R) {
        return casVide();
    }
}

class ListeCons<E> implements Liste<E> {
    constructor(private tete: E, private reste: Liste<E>) {
    }
    filtrage<R>(casVide: () => R, casCons: (t: E, r: Liste<E>) => R) {
        return casCons(this.tete, this.reste);
    }
}

function vide<E>(): Liste<E> {
    return new ListeVide();
}

function cons<E>(tete: E, reste: Liste<E>): Liste<E> {
    return new ListeCons(tete, reste);
}

Définir une fonction miroir, inversant une liste. Utiliser une fonction auxiliaire, définie récursivement.

On utilisera aussi des couples. Un constructeur de couples se révèle utile.

interface Liste<E> {
    filtrage<R>(casVide: () => R, casCons: (t: E, r: Liste<E>) => R): R;
}

class ListeVide<E> implements Liste<E> {
    filtrage<R>(casVide: () => R, casCons: (t: E, r: Liste<E>) => R) {
        return casVide();
    }
}

class ListeCons<E> implements Liste<E> {
    constructor(private tete: E, private reste: Liste<E>) {
    }
    filtrage<R>(casVide: () => R, casCons: (t: E, r: Liste<E>) => R) {
        return casCons(this.tete, this.reste);
    }
}

function vide<E>(): Liste<E> {
    return new ListeVide();
}

function cons<E>(tete: E, reste: Liste<E>): Liste<E> {
    return new ListeCons(tete, reste);
}

Définir une fonction miroir, inversant une liste. Utiliser une fonction auxiliaire, définie récursivement.

On utilisera aussi des couples. Un constructeur de couples se révélera utile.

function couple<A, B>(x: A, y: B): [A, B] {
    return [x, y];
}

Définir la classe d'implémentation ModuleFileParListe<E> de l'interface ModuleFile<Liste<E>, E>, puis la classe d'implémentation ModuleFileParDeuxListes<E> de l'interface ModuleFile<[Liste<E>, Liste<E>], E>.

Pour la première implémentation, l'ajout se fait en fin de liste alors que le retrait se fait en tête si la file n'est pas vide. Pour la seconde implémentation, l'ajout se fait en tête de la première liste, et le retrait en tête de la seconde liste si la file n'est pas vide. Lors du retrait, si la seconde liste est vide, la première remplace la seconde, après inversion.

Définir le type existentiel ModuleFileAbstrait<E>, correspondant à ModuleFile<?, E>. Définir la fabrique associée.

// Fabrique
function abstraction<F, E>(m: ModuleFile<F, E>): ModuleFileAbstrait<E> {
    // à compléter
}

Compléter la fonction permettant la représentation d'une file, étant donné un module.

function representation<M, E>(m: ModuleFile<M, E>, f: M): string {
    // à compléter
}

Définissions un module abstrait.

let module = abstraction(new ModuleFileParListe<number>());

Réaliser le scénario suivant avec ce module.

  • Créer une file vide.
  • Ajouter successivement 3, 4 et 5.
  • Afficher la représentation de la file ainsi obtenue.
  • Retirer un élément : afficher cet élément et la file obtenue.

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