Tout développeur est amené, dans son activité (et parfois sans s'en rendre compte),
à manipuler des concepts mathématiques. Comprendre ces concepts et leurs propriétés ne peut qu'être un plus. Cependant, comme beaucoup de programmeurs sont autodidactes ou que la relation entre les domaines mathématiques et ceux liés à la programmation est souvent floue, ces concepts peuvent paraître étrangers. Durant ma scolarité, ce fut mon cas, et c'est pour cela que j'ai décidé d'écrire la première partie d'une série d'articles qui évoqueront les structures algébriques.
Cette première partie est destinée à introduire le concept de "structure algébrique".
Dans la vie de tous les jours, lorsque l'on pense à une structure, on pense (parfois)
à l'élément sous-jacent d'un objet concret. Par exemple, la structure d'une maison, d'un immeuble ou encore d'une voiture. Cependant, il est possible de considérer la structure à un niveau plus abstrait, par exemple la structure d'un récit ou d'une composition musicale. Toutes ces structures peuvent être composées elles-mêmes de plus petites structures.
En mathématiques, l'idée derrière la notion de structure n'est pas différente de celle que l'on se fait dans le monde réel. Une structure mathématique n'est rien de plus qu'une organisation (potentiellement complexe) de structures plus fondamentales. Formellement, les structures designent une extension à la théorie des ensembles.
Alors que cette dernière limite ses primitives à la notion d'ensemble (d'éléments) et d'appartenance, une structure propose plus de contraintes, par exemple, la présence d'axiomes, de signes et de règles. Ce sont ces contraintes complémentaires qui permettent de définir de nouvelles structures.
Les structures algébriques
Comme son nom l'indique, une structure algébrique est un type particulier de structure (e.g. un groupe, un anneau, ou encore un corps). Elle est caractérisée par :
- un ensemble (de valeurs) ;
- au moins une loi de composition interne ;
- elle satisfait une série d'axiomes.
Si comme moi, malheureusement, vous n'avez pas été très attentif durant vos cours de mathématiques à la fac, voici une petite explication des termes qui pourraient poser problèmes.
Un axiome
Le terme est assez populaire et assez simple à comprendre.
Un axiome est une propriété indémontrable et admise vraie
(e.g. Euclide qui déclara que par un point donné ne passait qu'une seule et unique droite parallèle à une droite donnée). De ce fait, les axiomes peuvent servir de base à un raisonnement. Dans le monde de l'informatique, on peut se servir de
tests unitaires, d'assertions ou encore de systèmes de types et d'analyses statiques pour vérifier des axiomes.
Une loi de composition interne
Ce terme-ci peut paraître plus abstrait, cependant, il est aussi très simple à comprendre. Une loi de composition interne pour un ensemble E est une opération qui donne un résultat appartenant dans l'ensemble E, pour tous les couples possibles d'éléments de E, soit une application du produit cartésien de E
dans lui-même (E x E -> E).
Par exemple, dans l'ensemble des entiers naturels (N),
l'addition est une loi de composition interne car peu importe la valeur de x et de y dans x + y = r, r sera toujours compris dans l'ensemble des entiers naturels.
La soustraction est une loi de composition interne dans l'ensemble des entiers relatifs (Z), par contre, elle ne l'est pas dans l'ensemble des naturels : 3 - 10 donne un nombre qui n'est pas inclus dans N.
Un ensemble, E (par exemple), doté d'un opérateur <+> (par exemple) est noté (E,<+>) et est appelé un magma (c'est un nom assez classe !).
Les structures algébriques en informatique
Même si les langages statiquement typés sont adéquats pour représenter des structures algébriques (car l'ensemble est caractérisé par un type), il est possible (mais douloureux) de représenter les contraintes d'appartenance à un ensemble au moyen de tests unitaires.
En OCaml, on peut se servir d'une signature du module pour contraindre une structure algébrique :
module type Magma =
sig
type t (* Type de l'ensemble, soit un alias sur int*)
val (<+>) : t -> t -> t (* Loi de composition interne, soit un opérateur*)
end
(* E(Z,<+>) *)
module MagmaRelatifsPlus : Magma =
struct
type t = int
let (<+>) x y = x + y
end
Une autre approche serait d'encapsuler les valeurs d'un ensemble dans des objets pour représenter
un magma sous forme de classe abstraite générique (en Java par exemple).
Intérêt de l'usage des structures algébriques
Premièrement, les structures algébriques peuvent être comparées (légèrement !) avec les motifs de conception. En général, elles proposent une manière uniforme de traiter des problèmes variés. De plus, avec l'explosion de l'informatique de ces dernières décennies, la complexité des programmes n'a cessé de croître, une foultitude de termes a fait son apparition :
Big Data, Programmation Fonctionnelle Réactive, Promesses/Futures. Beaucoup de techniques découlant de ces nouveaux termes reposent sur des structures algébriques :
- dans le domaine du Big Data, MapReduce repose sur l'idée du Monoïde ;
- on peut représenter la Programmation Fonctionnelle Réactive au moyen de Flèches ;
- les Promesses/Futures sont une spécialisation des monades.
Monoïdes, flèches, et monades sont des structures algébriques que nous tâcherons de développer dans des articles futurs.
Conclusion
L'objectif de cet article était de donner la base (de la base) du vocabulaire nécéssaire pour comprendre facilement les articles de cette série qui vont suivre. Au fur et à mesure que nous présenterons des structures algébriques, nous tâcherons d'évoquer (en expliquant... évidemment)
des propriétés liées à ces structures pour comprendre de quelles manières elles peuvent aider le développeur à être efficace en se reposant sur des propriétés et en dépassant la "simple" intuition.
N'oubliez pas, une structure algébrique c'est :
- un ensemble de valeurs ;
- au moins une loi de composition interne satisfaisant certains axiomes.