Sadraskol

Les types algébriques pour les langages orientés objet

On pourrait renommer les languages fonctionnels (à l'exception d'Erlang, mais c'est une autre histoire) des languages algébriques à tel point que les structures algébriques sont leur outil de base. Nous allons essayer de montrer les analogies que ces structures ont avec les outils qui nous sont offerts dans les languages orientés objets et comment la réflexion en types algébriques permet de simplifier la modélisation de nos problèmes.

Les types sommes

Vous connaissez certainement déjà les types sommes : c'est le nom savant des énumerations. Vous savez ce qu'on utilise en Java pour désigner les méthodes Http ?

public enum HttpMethod {
	DELETE, GET, HEAD, OPTIONS, PATCH, POST, PUT, TRACE
}

Cette structure est assez simple, alors pourquoi la nommer avec une opération algébrique comme la somme ? Qu'est-ce qu'on somme ici ? On parle de somme car on ajoute les possibilités. Ici le type HttpMethod est la somme de ses valeurs possibles (DELETE, HEAD, etc.) : 8. On parle de Cardinalité pour exprimer ce nombre. On dit que le Cardinal de l'ensemble HttpMethod est 8. On reviendra sur ce concept plus tard.

Les énumérations ne sont pourtant pas beaucoup utilisées en Java et malgré leurs propriétés intéressantes (pas de garbage collection, pas de problème d'instantiation ou utilisation dans les switch, etc.) elles ne sont pas importantes dans les patrons de conceptions. Alors comment ce type pourrait-il être central dans un autre language ? Voyons ce qu'est un type produit avant de répondre à cette question.

Les types produits

Un type produit est aussi très familier. Il correspond à la réunion de deux types. Si une personne est défini par son nom et son âge, on dira qu'il est le produit de ces deux types :

public class Person {
  private final String name;
  private final int age;
}

On parle de produit dans ce cas, car on peut avoir autant d'instance de Person qu'il y a de noms multiplié par le nombre d'ages possibles. Dans ce cas, il s'agit d'une multiplication d'infini. Vu ce cardinal, il est impossible de prévoir tous les cas. C'est pourtant le type que le language nous engage le plus à utiliser. C'est que ce type permet d'englober toutes les possibilités dans une seule structure.

Est-il possible de restreindre le nombre de valeurs possibles tout en profitant de la modélisation de domaine complexe que permet les types produits ?

Les types algébriques

Les beaucoup de languages permettent d'utiliser une composition des types sommes et produits pour combiner les avantages des deux. Construisons un type qui modélise un cas concret, 

data Maybe a = Nothing | Just a

getHttpHeader = Just Get -- Maybe HttpMethod
noHttpHeader = Nothing -- Not available

Si l'on tente de calculer le cardinal de ce type algébrique, on voit que les valeurs possibles pour ce type sont : 1 + 1 * C(a), C(a) étant le cardinal du type a. La notion de somme et de produit transparait directement dans le calcul du cardinal. Dans le cas où a est un HttpMethod, C(Maybe HttpMethod) == 8. Ce qui est intéressant dans cette approche, c'est l'exhaustivité des types représentés. Par exemple, il est possible de représenter le score d'un point au tennis avec le type suivant :

data Point = Zero | Fifteen | Thirty

data Player = Player1 | Player2

data GameScore
  = Score Point Point
  | GamePoint Player Point
  | Deuce
  | Advantage Player
  | Game Player

On pourrai montrer que le type GameScore implémente l'ensemble des scores possible pour un point de tennis. On peut même trivialement calculer l'ensemble des valeurs possibles :

C(GameScore) == C(Point) * C(Point) + C(Player) * C(Point) + 1 + C(Player) + C(Player)
C(GameScore) == 3 * 3 + 2 * 3 + 1 + 2 + 2
C(GameScore) == 20

Il y a exactement 20 valeurs possibles (le code qui implémente le comportement est à la charge du lecteur 💪). Être capable de modéliser nos problèmes avec des types algébriques a l'énorme avantage de demander à ne résoudre que des valeurs possibles. Pas besoin de soucier des cas où il y aurait un score de 34 - 70 ou un score négatif. Si Haskell, et d'autres languages, permettent de simplement d'exprimer ces cas, comment utiliser ces outils dans un language comme Java ? Voyons cela ensemble.

Les types algébriques en Java

Il y a plusieurs alternatives pour implémenter correctement des types algébriques. Java n'offre pas d'outils de base pour les représenter, mais on peut utiliser un type purement produits avec une seule classe comme ceci :

class GameScore {
  private final int scorePlayer1;
  private final int scorePlayer2;
  private final GameStage stage;

  enum GameStage {
    Score, GamePoint, Deuce, Advantage, Game
  }
}

Le gros désavantage de ce genre d'approche (j'ai un peu exaggéré l'exemple, on aurait pu utiliser des classes plus fines) est facilement repérable à partir d'un calcul de cardinal : C(GameScore) = C(int) * C(int) * 5. Dans ce cas, C(GameScore) est largement supérieur au cas nominatif. De plus, il est de la responsabilité des méthodes manipulant ce type de ne pas se retrouver avec une valeur (Score, 40, 40) alors que c'est une valeur Deuce qui est attendue. Et puis que faire si on se retrouver dans la valeur (Advantage, 15, 15), bref la complexité de cette implémentation est, à minima, dangereuse.

Restreindre les valeurs possibles

Pour résoudre cela, nous allons limiter les valeurs possibles. Dans un premier temps, on peut implémenter les énumérations simples que l'on a présentées en Haskell :

enum Player { PLAYER_1, PLAYER_2 }
enum Score { Zero, Fifteen, Thirty }

Il nous reste quand même le cas de l'implémentation du score à résoudre. Pour cela, on va utiliser l'outil de base des languages orientés objets : le polymorphisme ! Une implémentation d'interface pour chaque constructeur de valeur :

public class Score implements GameScore {
  private final Score scorePlayer1;
  private final Score scorePlayer2;
}
public class GamePoint implements GameScore {
  private final Player gamePointPlayer;
  private final Score otherPlayerScore;
}
public class Deuce implements GameScore {}
public class Advantage implements GameScore {
  public final Player forPlayer;
}
public class Game implements GameScore {
  public final Player forPlayer;
}

Cette implémentation se rapproche très proche de l'implémentation en Haskell. On pourrait penser que son cardinal est la même. On a utilisé les mêmes constructeur avec les mêmes valeurs ! Or ce n'est pas le cas, car Java a une valeur qui est difficile à éviter lors de l'implémentation d'une classe : la valeur null. Si l'on explicite cette implémentation en Haskell, elle ressemblerait plutôt à ça :

data Player = Player1 | Player2 | NullPlayer
data GameScore
  = Score Point Point
  | GamePoint Player Point
  | Deuce
  | Advantage Player
  | Game Player
  | NullGameScore
-- etc.

Au lieu d'un cardinal du type algébrique GameScore : C(GameScore) = 20, on se retrouve avec C(GameScore | Java) = 36. Il y a 16 valeurs limites pour lesquels il va falloir se prémunir. Il existe des stratégies pour mitiger ce problème : on peut ignorer ces cas et risquer des NullPointerException, les prévenir avec des checkNotNull, etc. Aucune solution n'est meilleure qu'une autre et il faut faire avec, car c'est le language lui-même (et pas notre implémentation) qui produit des valeurs limites de nos types algébriques.

Conclusion

Les types algébriques sont un outil très efficace pour limiter les valeurs pour un type et donc alléger la charge mentale lors du développement d'une fonctionnalité. Les languages sont un auxiliaire à l'habilité du développeur et c'est de notre devoir de leur demander de coller au plus proche de ce que l'on souhaite exprimer.