Types algébriques en JAVA

Publié le April 12, 2020
Tags: informatique, langage de programmation, JAVA, adt

Types algébriques

Un type algébrique permet de combiner plusieurs types entre eux, en pouvant encoder à la fois les types produit (disposer d’un objet de type produit A×BA\times B donne accès à un objet de type AA et un objet de type BB) et les types somme (disposer d’un objet de type somme A+BA+B donne accès soit à un objet de type AA soit un objet de type BB).

Les types produits sont usuels dans la plupart des langages de programmation, à partir du moment où ils disposent de structure d’enregistrement (les différents champs d’une classe JAVA, les struct en C, etc.)

Par contre, les types sommes, en tant que disjonction entre différents sous-types, sont plus difficiles à voir dans ces langages. Il existe bien des opérateurs de disjonctions, comme le switch en JAVA, mais il n’opère pas une disjonction entre les types, mais entre les valeurs

Cas pratique

Supposons par exemple que l’on souhaite écrire une fonction qui retourne une valeur d’un certain type dans un cas, et une valeur d’un autre type dans un autre.

Dans la suite on va donner plusieurs encodages possibles en JAVA répondant à ce problème, et on verra quelles sont leurs limitations.

Enumérations

Une première possibilité peut être d’utiliser les énumérations. Par exemple, on peut définir une classe Resultat utilisant un champ définissant le cas dans lequel on se trouve.

enum Cas {
    Gauche,
    Droit
}
class Resultat<A, B>{
    Cas cas;
    A a;
    B b;
    Resultat(Cas cas, A a, B b){
        this.cas = cas;
        this.a = a;
        this.b = b;
    }
}
Resultat<Float, String> div(Float a, Float b){
    if(b == 0.){
        return new Resultat<>(Cas.Droit, null, "Impossible de diviser par zero");
    } else {
        return new Resultat<>(Cas.Gauche, a/b, null);
    }
}
public static void main(String[] args){
    Resultat<Float,String> resultat = div(Float.parseFloat(args[0]), Float.parseFloat(args[1]));
    switch (resultat.cas){
        case Gauche:
            System.out.println("resultat : " + resultat.a);
            break;
        case Droit:
            System.out.println(resultat.b);
            break;
        default:
            assert false;
    }
}

Le programme div renvoie la division de a par b, et si b est nul, il renvoie chaîne expliquant l’erreur.

Le problème de cette implémentation est qu’elle ne fait aucune vérification statique de cohérence de la structure, c’est-à-dire que sans exécuter le programme, je ne sais pas (ou plutôt, le compilateur ne me le dit pas) si le programme va s’exécuter sans erreur.

Deux types d’incohérences sont possibles

  1. Lors de la création d’un résultat, le cas Droit ou Gauche n’est pas directement corrélé avec le contenu des autres paramètres. Il est par exemple possible de construire Resultat(Gauche, null, "message").

  2. Lors de la consultation du résultat, la disjonction des cas n’est pas corrélée avec les données auxquelles on a accès. Ainsi il est possible d’écrire le programme suivant sans erreur du compilateur.

public static void main(String[] args){
    Resultat<Float,String> resultat = div(Float.parseFloat(args[0]), Float.parseFloat(args[1]));
    switch (resultat.cas){
        case Droit:
            System.out.println("resultat : " + resultat.a); // c'est pas corrélé au cas Droit
            break;
        case Gauche:
            System.out.println(resultat.b); // n'est pas corrélé au cas Gauche
            break;
        default:
            assert false; // On aimerait ici ne pas avoir à écrire ce cas
    }
}

Sous-classes

Afin de toujours corréler les cas avec les données, on peut utiliser le sous-classage.

abstract class Resultat<A, B>{
    private Resultat(){}
    static final class Gauche<A, B> extends Resultat<A, B>{
        A a;
        Gauche(A a){
            super();
            this.a = a;
        }
    }
    static final class Droit<A, B> extends Resultat<A, B>{
        B b;
        Droit(B b){
            super();
            this.b = b;
        }
    }
}
Resultat<Float, String> div(Float a, Float b){
    if(b == 0.){
        return new Resultat.Droit<>("Impossible de diviser par zero");
    } else {
        return new Resultat.Gauche<>(a/b);
    }
}
public static void main(String[] args){
    Resultat<Float,String> resultat = div(Float.parseFloat(args[0]), Float.parseFloat(args[1]));
    if (resultat instanceof Gauche){
        Gauche<Float,String> gauche = (Gauche<Float, String>) resultat;
        System.out.println("resultat : " + gauche.a);
    } else {
        Droit<Float,String> droit = (Droit<Float, String>) resultat;
        System.out.println(droit.b);
    }
}

On notera l’usage du constructeur privé afin d’emplêcher le sous-classage excepté des classes Gauche et Droit, ainsi que les modificateurs final devant ces deux classes, afin là aussi d’empécher le sous-classage. L’important de cette interdiction apparaît dans la fonction principale, où l’on teste l’appartenance du résultat à une classe ou l’autre.

Ici, le premier problème de cohérence de structure a été résolu, car on ne peut plus faire de résultat incohérent. Par contre, il reste toujours le problème de cohérence à l’utilisation, car chaque branche du test instanceof peut ne pas être cohérent avec le résultat du test.

Utilisation cohérente

Tout en gardant l’idée de la sous-classe pour garder la cohérence à la construction, on propose cette modification pour permettre de conserver le test de cohérence lors de l’utilisation.

abstract class Resultat<A, B>{
    private Resultat(){}
    public interface Cases<R, A, B>{
        R casGauche(A gauche);
        R casDroit(B droit);
    }
    abstract <R> R match(Cases<R, A, B> cases);
    static final class Gauche<A, B> extends Resultat<A, B>{
        A a;
        Gauche(A a){
            super();
            this.a = a;
        }
        <R> R match(Cases<R, A, B> cases) {
            return cases.casGauche(a);
        }
    }
    static final class Droit<A, B> extends Resultat<A, B>{
        B b;
        Droit(B b){
            super();
            this.b = b;
        }
        <R> R match(Cases<R, A, B> cases) {
            return cases.casDroit(b);
        }
    }
    static Resultat<Float, String> div(Float a, Float b){
        if (b == 0.){
            return new Droit<>("Impossible de diviser par zero");
        } else {
            return new Gauche<>(a/b);
        }
    }
    public static void main(String[] args) {
        Resultat<Float, String> res = div(Float.parseFloat(args[0], args[1]));
        res.match(new Cases<Void, Float, String>() {
            public Void casGauche(Float gauche) {
                System.out.println("res : " + gauche);
                return null;
            }
            public Void casDroit(String droit) {
                System.out.println(droit);
                return null;
            }
        });
    }
}

Ici, à la fois la cohérence à l’écriture et à la consultation sont testés lors de la compilation.