Types union étiquetés et types de données algébriques

La Session 145 a apporté un concept du monde académique de la théorie des langages de programmation dans FLIN, un langage conçu pour le développement pragmatique d'applications : les types de données algébriques.

Le nom semble intimidant. Le concept est simple. Un type de données algébrique est un type qui peut être l'une de plusieurs variantes, où chaque variante peut porter des données différentes. Le résultat d'une requête réseau est soit un succès avec un corps de réponse, soit un échec avec un message d'erreur. Un élément de liste est soit une valeur suivie de plus de liste, soit la fin de la liste. Une valeur JSON est soit une chaîne, un nombre, un booléen, null, un tableau, ou un objet.

Dans FLIN, ceux-ci s'appellent des unions étiquetées, et ils sont déclarés avec le mot-clé enum.

Des enums simples aux unions étiquetées

FLIN avait déjà des enums simples avant la Session 145 :

flinenum Status {
    Pending,
    Active,
    Completed
}

Un enum simple est un type avec des variantes nommées et pas de données associées. Status.Pending est une valeur. Status.Active est une valeur différente. On peut filtrer dessus, les comparer, les stocker. Mais ce ne sont que des étiquettes.

Les unions étiquetées étendent les enums avec des données associées :

flinenum Message {
    Quit,
    Move(int),
    Write(text)
}

Maintenant Quit ne porte pas de données, Move porte un int (une distance, peut-être), et Write porte un text (un corps de message). Chaque variante est une forme différente. L'étiquette -- Quit, Move, Write -- indique quelle forme on a, et le pattern matching permet d'accéder aux données à l'intérieur.

Unions étiquetées génériques

La vraie puissance vient de la combinaison des unions étiquetées avec les génériques :

flinenum Option<T> {
    Some(T),
    None
}

enum Result<T, E> {
    Ok(T),
    Err(E)
}

Option<int> est un type qui est soit Some(42) soit None. Result<int, text> est un type qui est soit Ok(42) soit Err("something went wrong"). Ces deux types seuls gèrent la grande majorité des valeurs nullables et de la gestion d'erreurs dans n'importe quelle application.

Le paramètre générique T dans Option<T> n'est pas un type concret -- c'est un espace réservé. Quand on écrit Option<int>, le compilateur substitue T = int dans toute la définition de l'enum. Some(T) devient Some(int). Quand on écrit Option<text>, Some(T) devient Some(text).

Enums génériques contraints

La Session 145 a aussi ajouté le support des paramètres de type contraints par des traits sur les enums :

flinenum Container<T: Comparable> {
    Empty,
    Single(T),
    Multiple([T])
}

La contrainte T: Comparable signifie que Container ne peut être instancié qu'avec des types qui implémentent le trait Comparable. Container<int> est valide (int est comparable). Container<User> n'est valide que s'il y a un impl Comparable for User.

L'implémentation dans l'AST

La Session 145 a modifié l'AST à trois endroits clés.

Premièrement, Stmt::EnumDecl a gagné un champ type_params :

rustStmt::EnumDecl {
    name: String,
    type_params: Vec<TypeParam>,  // NEW: <T, E>, <T: Comparable>
    variants: Vec<EnumVariant>,
    visibility: Visibility,
    span: Span,
}

La structure TypeParam porte à la fois le nom du paramètre et les contraintes optionnelles :

rustpub struct TypeParam {
    pub name: String,
    pub constraints: Vec<String>,  // trait names
}

Deuxièmement, EnumVariant avait déjà un Option<Type> pour les données associées, mais la Session 145 a fait interagir correctement ce champ avec les paramètres de type :

rustpub struct EnumVariant {
    pub name: String,
    pub data_type: Option<Type>,  // None for Quit, Some(Type::Int) for Move(int)
}

Lors de l'analyse d'une variante comme Ok(T), le parser reconnaît T comme un paramètre de type (pas un type concret) car il est dans la portée de type_params.

Troisièmement, une nouvelle variante de motif a été ajoutée pour filtrer les variantes d'enum :

rustPattern::EnumVariant {
    enum_name: String,
    variant: String,
    inner: Option<Box<Pattern>>,
    span: Span,
}

Modifications du parser

Le parser a nécessité deux modifications. Premièrement, parse_enum_decl a été étendu pour analyser les paramètres de type après le nom de l'enum :

rustfn parse_enum_decl(&mut self) -> Result<Stmt, ParseError> {
    self.expect_keyword("enum")?;
    let name = self.expect_identifier()?;
    let type_params = self.parse_type_params()?; // NEW

    self.expect(&Token::LeftBrace)?;
    let mut variants = vec![];
    while !self.check(&Token::RightBrace) {
        variants.push(self.parse_enum_variant_with_params(&type_params)?);
        self.optional_comma();
    }
    self.expect(&Token::RightBrace)?;

    Ok(Stmt::EnumDecl { name, type_params, variants, visibility, span })
}

Deuxièmement, une nouvelle fonction parse_enum_variant_with_params a été ajoutée pour gérer les types de données de variante qui référencent des paramètres de type :

rustfn parse_enum_variant_with_params(
    &mut self,
    type_params: &[TypeParam],
) -> Result<EnumVariant, ParseError> {
    let name = self.expect_identifier()?;
    let data_type = if self.match_token(&Token::LeftParen) {
        let param_names: Vec<&str> = type_params.iter().map(|p| p.name.as_str()).collect();
        let data = self.parse_type_with_params(&param_names)?;
        self.expect(&Token::RightParen)?;
        Some(data)
    } else {
        None
    };
    Ok(EnumVariant { name, data_type })
}

La fonction parse_type_with_params sait quels identifiants sont des paramètres de type, donc T dans Ok(T) est analysé comme Type::TypeParam("T") plutôt que Type::Named("T").

Extension du système de types

La variante FlinType::Enum a été étendue pour porter les paramètres de type et les données de variante typées :

rustFlinType::Enum {
    name: String,
    type_params: Vec<String>,
    variants: Vec<(String, Option<Box<FlinType>>)>,
}

Avant la Session 145, les variantes étaient juste Vec<String> -- des noms sans types de données. Après la Session 145, chaque variante porte un FlinType optionnel pour ses données associées.

Quand le vérificateur de types enregistre une déclaration d'enum, il convertit la représentation AST en FlinType :

rustfn register_enum(&mut self, decl: &Stmt) {
    let Stmt::EnumDecl { name, type_params, variants, .. } = decl else { return };

    let flin_variants: Vec<(String, Option<Box<FlinType>>)> = variants
        .iter()
        .map(|v| {
            let data = v.data_type.as_ref().map(|t| {
                Box::new(FlinType::from(t))
            });
            (v.name.clone(), data)
        })
        .collect();

    let param_names: Vec<String> = type_params.iter().map(|p| p.name.clone()).collect();

    self.type_env.insert(
        name.clone(),
        FlinType::Enum {
            name: name.clone(),
            type_params: param_names,
            variants: flin_variants,
        },
    );
}

Construction de variantes

La création d'une valeur de variante utilise une syntaxe similaire aux appels de fonction :

flinresult = Ok(42)
option = Some("hello")
message = Move(10)
status = Completed

Les variantes avec données ressemblent à des appels de fonction. Les variantes sans données sont des identifiants nus. Le parser les distingue en vérifiant si des parenthèses suivent le nom de la variante.

Dans le vérificateur de types, la construction de variante est validée contre la définition de l'enum :

rustfn check_variant_construction(
    &mut self,
    enum_name: &str,
    variant_name: &str,
    args: &[Expr],
) -> FlinType {
    let enum_def = self.resolve_enum(enum_name);

    let variant = enum_def.variants.iter()
        .find(|(name, _)| name == variant_name);

    match variant {
        Some((_, Some(expected_data))) => {
            if args.len() != 1 {
                self.report_error("variant expects exactly one argument");
            } else {
                let arg_type = self.infer_type(&args[0]);
                if !self.types_compatible(expected_data, &arg_type) {
                    self.report_error("variant data type mismatch");
                }
            }
        }
        Some((_, None)) => {
            if !args.is_empty() {
                self.report_error("variant takes no arguments");
            }
        }
        None => {
            self.report_error(&format!("unknown variant: {}", variant_name));
        }
    }

    FlinType::Enum { name: enum_name.to_string(), /* ... */ }
}

Pattern matching sur les unions étiquetées

La manière principale de travailler avec les unions étiquetées est le pattern matching :

flinfn handle_result(result: Result<int, text>) -> text {
    match result {
        Ok(value) -> "Success: " + text(value)
        Err(msg) -> "Error: " + msg
    }
}

Le motif Ok(value) fait trois choses :

1. Vérification de l'étiquette : Vérifie que l'étiquette à l'exécution est Ok
2. Extraction des données : Extrait les données associées
3. Liaison : Lie les données au nom value

À l'intérieur du corps du bras, value a le type int -- dérivé de Ok(T) de Result<int, text> où T = int.

Le vérificateur de types gère les motifs de variante d'enum :

rustfn check_enum_variant_pattern(
    &mut self,
    pattern: &Pattern,
    enum_type: &FlinType,
) {
    let Pattern::EnumVariant { variant, inner, .. } = pattern else { return };
    let FlinType::Enum { variants, type_params, .. } = enum_type else { return };

    let variant_def = variants.iter().find(|(name, _)| name == variant);

    match (variant_def, inner) {
        (Some((_, Some(data_type))), Some(inner_pattern)) => {
            // Bind inner pattern with the data type
            self.check_pattern(inner_pattern, data_type);
        }
        (Some((_, None)), None) => {
            // No data variant, no inner pattern -- OK
        }
        (Some((_, Some(_))), None) => {
            self.report_error("variant has data but pattern does not destructure it");
        }
        (Some((_, None)), Some(_)) => {
            self.report_error("variant has no data but pattern tries to destructure");
        }
        (None, _) => {
            self.report_error(&format!("unknown variant: {}", variant));
        }
    }
}

Motifs d'utilisation réels

Les unions étiquetées ne sont pas une curiosité académique. Elles modélisent des motifs d'application réels.

Gestion des erreurs

flinenum ApiResult<T> {
    Success(T),
    NotFound,
    Unauthorized,
    ServerError(text)
}

fn fetch_user(id: int) -> ApiResult<User> {
    // ... API call ...
}

match fetch_user(42) {
    Success(user) -> render_profile(user)
    NotFound -> show_404()
    Unauthorized -> redirect_to_login()
    ServerError(msg) -> show_error(msg)
}

Chaque résultat possible est une variante. Le compilateur garantit que chaque site d'appel gère chaque résultat.

Machines à états

flinenum ConnectionState {
    Disconnected,
    Connecting(text),
    Connected(Socket),
    Error(text)
}

fn render_status(state: ConnectionState) -> text {
    match state {
        Disconnected -> "Not connected"
        Connecting(host) -> "Connecting to " + host + "..."
        Connected(socket) -> "Connected to " + socket.host
        Error(msg) -> "Error: " + msg
    }
}

La machine à états est le type. Les transitions entre états sont des affectations de différentes variantes. Le compilateur garantit que chaque état est géré.

Structures de données récursives

flinenum JsonValue {
    Null,
    Bool(bool),
    Number(number),
    Text(text),
    Array([JsonValue]),
    Object([text: JsonValue])
}

Une valeur JSON est soit null, un booléen, un nombre, une chaîne, un tableau de valeurs JSON, ou un objet mappant des chaînes vers des valeurs JSON. Cette définition récursive capture la spécification JSON complète en six lignes.

Résultats des tests

La Session 145 a ajouté six nouveaux tests d'intégration :

1. test_e2e_tagged_union_simple_enum -- enum basique sans données
2. test_e2e_tagged_union_with_data -- Message avec données de variante
3. test_e2e_tagged_union_generic_enum -- Option<T> avec paramètre générique
4. test_e2e_tagged_union_generic_result -- Result<T, E> avec deux paramètres
5. test_e2e_tagged_union_constrained_generic -- Container<T: Comparable>
6. test_e2e_tagged_union_pub_enum -- enum avec visibilité publique

Le nombre total de tests est passé de 1 782 à 1 788. Tous les tests existants ont continué à passer.

Fichiers modifiés

La Session 145 a touché sept fichiers :

Les modifications étaient chirurgicales. La plupart des fichiers n'avaient besoin que de quelques lignes ajoutées ou modifiées. C'est parce que l'infrastructure -- paramètres de type génériques, pattern matching, le cadre du vérificateur de types -- existait déjà. Les unions étiquetées étaient la fonctionnalité qui a connecté ces pièces.

Décisions de conception

Parenthèses pour les données de variante, pas des accolades. Nous avons choisi Ok(42) plutôt que Ok { value: 42 }. Les parenthèses sont plus courtes et plus familières (Rust utilise la même syntaxe). Les accolades suggèrent une structure, qui est un concept différent. Les parenthèses suggèrent un constructeur, ce qui est plus proche de ce qu'est réellement la création de variante.

Une seule valeur de données par variante. Chaque variante porte au plus une valeur. Pour plusieurs valeurs, utiliser un tuple ou une entité. Cela garde la syntaxe simple : Move(int) plutôt que Move(int, int). Si on a besoin de deux valeurs, utiliser Move((int, int)) avec un tuple.

Paramètres de type sur l'enum, pas sur les variantes. Les paramètres de type appartiennent à la déclaration de l'enum : enum Result<T, E>, pas enum Result { Ok<T>(T), Err<E>(E) }. Cela suit la convention de Rust et garde la syntaxe des variantes propre.

L'exhaustivité est obligatoire. Chaque match sur une union étiquetée doit couvrir chaque variante. Il n'y a pas de default comme échappatoire pour les enums. Si on ajoute une variante, chaque match doit être mis à jour. C'est un choix délibéré pour la sécurité plutôt que la commodité.

La théorie des types algébriques

Le nom « type de données algébrique » vient d'une analogie mathématique. Une union étiquetée est un type somme -- le nombre total de valeurs possibles est la somme des valeurs possibles de chaque variante. Option<bool> a trois valeurs : Some(true), Some(false), et None. C'est 2 + 1 = 3.

Une entité (ou struct) est un type produit -- le nombre total de valeurs possibles est le produit. Une entité avec un champ bool et un champ int a 2 * 2^64 valeurs possibles.

Ensemble, les types somme et les types produit donnent l'« algèbre » des types de données algébriques. On peut les composer pour décrire n'importe quelle forme de données : sommes de produits, produits de sommes, types récursifs, types génériques.

FLIN n'exige pas que les développeurs connaissent cette théorie. Mais la théorie explique pourquoi les unions étiquetées sont si puissantes -- elles sont la moitié manquante de l'algèbre des types. Sans elles, on peut décrire des enregistrements (produits) mais pas des alternatives (sommes). Avec elles, on peut tout décrire.

La Session 145 a donné à FLIN l'algèbre complète. Le système de types du langage était maintenant complet au sens théorique : il pouvait décrire n'importe quelle forme de données dont un développeur pourrait avoir besoin. Les sessions restantes -- déstructuration, opérateur pipeline, boucles while-let -- étaient des fonctionnalités ergonomiques construites sur cette fondation complète.

Ceci est la partie 36 de la série « Comment nous avons construit FLIN », documentant comment un CEO à Abidjan et un CTO IA ont conçu et implémenté un langage de programmation à partir de zéro.

Navigation de la série : - [34] Traits et interfaces - [35] Pattern matching : de switch à match - [36] Types union étiquetés et types de données algébriques (vous êtes ici) - [37] La déstructuration partout - [38] L'opérateur pipeline : composition fonctionnelle dans FLIN