Types de sortes supérieures en JAVA

Publié le May 15, 2020
Tags: informatique, langage de programmation, JAVA, hkt, higher kinded type

Retour sur le polymorphisme paramétrique

Java et les types génériques

Depuis JAVA 5, JAVA supporte le polymorphisme paramétrique grâce aux types génériques. Ces type permettent de définir des structures dont la forme ne dépendant pas de son contenu. Par exemple, un couple, et toutes les opérations attenantes (récupération de l’élément à gauche, à droite, …) ne dépendent pas du type du contenu que contient le couple. En JAVA on peut exprimer cela de la manière suivante.

class Couple<A, B>{
    A gauche;
    B droit;
    Couple(A a, B b){
        this.a = a;
        this.b = b;
    }
    A getGauche(){
        return this.gauche;
    }
    B getDroit() {
        return this.droit;
    }
    public static void main(String[] args){
        Couple<Integer, String> couple = new Couple<>(2, "bonjour");
        String message = couple.getDroit();
        System.out.println(message.length());
    }
}

Sorte : le type des types

Dans tout le corps de la classe Couple<A, B>, les paramètres A et B sont utilisés comme n’importe quel type ou classe habituelle (comme le type int, la classe String, …). De même, Couple<A, B> s’utilise lui aussi comme n’importe quel type.

Si Couple<A, B> est un type, qu’en est t’il de Couple ? En JAVA, on appelle cela un raw type, qui sont né afin de préserver la compatibilité avec les versions de JAVA précédent la version 5. Pour les versions ultérieures, Couple est un raccourci pour Couple<Object, Object>.

Pour d’autres langages de programmation, comme Haskell, Couple serait vu comme un constructeur de type. Par exemple, il prend le type Integer, le type String et construit le type Couple<Integer, String>.

Attention, on parle bien ici du Couple dans class Couple<A, B> et pas dans Couple(A a, B b) ! Le premier vit dans le “monde” des types, le second vit dans celui des objets. Dans le monde des objets, chaque objet à un type, et dans le monde des types, chaque type a une sorte (ou kind en anglais).

Si on essaye de spécifier ce qu’est Couple en lui associant une sorte, on peut dire que Couple est une fonction prenant en paramètre deux types et retournant un type. Si on note ** la sorte des types non paramétré comme int ou String, on peut écrire la sorte de Couple comme étant (*,*)*(*, *) \to *, ou, avec un peu de curryfication, **** \to * \to *.

Type de sorte supérieure

Exemples en JAVA

Certains types génériques sont employés pour définir des classes “entourant” un ou plusieurs objets du même type. Par exemple, les listes (List<T>), les ensembles (Set<T>) ou les éléments “nommables”, que l’on peut encoder dans le type Couple<String, T>. Sur ces types de classes il est naturelle de définir une fonction de conversion sur la collection tout entière à partir d’une fonction de conversion sur le type à l’intérieur.

Par exemple, si on dispose d’une liste l1 de type List<String> et que l’on dispose d’une fonction intOfString de pseudo-type String \to Integer calculant par exemple un entier à partir de sa description en texte, On pourrait souhaiter construire la liste l2 de type List<Integer> à partir de l1 et de intOfString.

public List<Integer> map(Function<String, Integer> intOfString, List<String> l1){
    List<Integer> res = new ArrayList<>();
    for(String s : l1){
        res.add(intOfString.apply(s));
    }
    return res;
}

Dans un premier temps il apparaît que cette fonction map est indépendante des types String et Integer. On peut donc l’écrire de manière plus générale, en utilisant les types génériques

public <A, B> List<B> map(Function<A, B> convert, List<A> l1){
    List<B> res = new ArrayList<>();
    for(A s : l1){
        res.add(convert.apply(s));
    }
    return res;
}

De même que pour les listes, la fonction map est facilement définissable pour les ensembles ou les éléments nommables. Par exemple, dans le deuxième cas :

public <A, B> Couple<String, B> map(Function<A, B> convert, Couple<String, A> couple){
    return new Couple(couple.getGauche(), convert.apply(couple.getDroit()));
}

Est-il possible de caractériser l’ensemble des “types” sur lesquelles peut se définir la fonction map ?

Ici, on notera que “type” n’est pas vraiment le bon terme, car la fonction map ne se définit pas sur un type au sens propre (comme List<Integer> ou Couple<String, Integer>) mais sur un constructeur de type (comme List ou Couple<String, ...>).

Tentons une spécification générale de la fonction map. Pour cela, on cherche à écrire une interface Mappable<T>T désignerait un constructeur de type comme List ou Set.

interface Mappable<T> {
    <A, B> T<B> map(Function<A, B> convert, T<A> ta);
}

Ici, T est de sorte *** \to *, ce qui fait de Mappable un constructeur de types de sorte (**)*(* \to *) \to *. En JAVA, un problème apparaît dans les formes T<A> et T<B> car il est impossible de définir des sortes d’ordre supérieur.

Encodage des types de sortes supérieures

La difficulté est de définir un “élément commun” aux types obtenus à partir d’un même constructeur. L’idée est d’utiliser un témoin propre à chaque constructeur de type, afin de spécifié la conservation du constructeur de type par la conservation de ce témoin.

On définit alors une interface HKT que surchargeront toutes les classes se déclarant comme “d’ordre supérieur”.

interface HKT<W, T> {}

Cet interface fait apparaitre le témoin W propre à chaque constructeur. Par exemple

class List<T> implements HKT<List.W, T> {
    public static class W{}
}

Grâce à la présence du témoin, on sait que tout type HKT<List.W, T> représente le type List<T>.

Vraiment tout ? Par vraiment, car comme on peut le voir, la classe List.W est public : en effet, tout programme utilisant l’interface HKT avec des listes vas devoir faire référence à ce témoin.