Les types génériques dans FLIN

La Session 101 a achevé la Phase 2 du système de types de FLIN. La dernière fonctionnalité : les types génériques.

Les génériques sont la fonctionnalité qui sépare un système de types capable de décrire des données concrètes d'un système capable de décrire des motifs de données. Sans génériques, on peut écrire une fonction qui trie une liste d'entiers. Avec les génériques, on peut écrire une fonction qui trie une liste de n'importe quoi -- et le compilateur vérifie toujours que « n'importe quoi » est utilisé de manière cohérente.

Pour FLIN, les génériques n'étaient pas un luxe. C'était une nécessité. Le langage a Option<T> pour les valeurs optionnelles, Result<T, E> pour la gestion des erreurs, et des opérations sur les collections comme map et where qui transforment un type en un autre. Tout cela nécessite des types génériques pour être type-safe.

Mais FLIN est aussi un langage avec une syntaxe de vue similaire au HTML. Et les chevrons -- la syntaxe universelle des génériques -- sont aussi la syntaxe universelle des balises HTML. Cette collision a créé le défi d'implémentation le plus intéressant de tout le système de types.

La syntaxe

La syntaxe générique de FLIN suit la convention établie par Java, C#, TypeScript et Rust :

flin// Alias de type générique
type Option<T> = T?
type Result<T, E> = T | E

// Fonction générique
fn identity<T>(value: T) -> T {
    return value
}

// Fonction générique avec plusieurs paramètres de type
fn map<T, U>(list: [T], f: (T) -> U) -> [U] {
    // ...
}

// Instanciation de type générique
value: Option<int> = 42
result: Result<int, text> = "error"

// Génériques imbriqués
data: Option<[int]> = [1, 2, 3]

La syntaxe avec chevrons était la seule option sérieuse. Les alternatives comme Option[T] (Scala) ou Option(T) auraient créé des conflits avec l'indexation de liste et les appels de fonction respectivement. Les crochets dans FLIN signifient déjà les listes. Les parenthèses signifient déjà l'application de fonction. Les chevrons étaient la paire de délimiteurs restante.

Ce qui nous a amenés au problème.

Le problème du lexer : <T> versus <div>

FLIN utilise une syntaxe similaire au HTML pour les vues. Un composant ressemble à ceci :

flincount = 0
<button click={count++}>{count}</button>

Et un type générique ressemble à ceci :

flintype Option<T> = T?

Le lexer voit < et doit décider : est-ce le début d'une liste d'arguments de type générique, ou le début d'une balise HTML ? Dans la plupart des langages, cette ambiguïté n'existe pas car il n'y a pas de syntaxe HTML. Dans FLIN, c'est le défi d'analyse central.

La solution était l'adjacence des positions. Quand le lexer rencontre <, il vérifie si le token précédent (un identifiant) est immédiatement adjacent -- pas d'espace entre l'identifiant et le < :

rust// In the scanner
fn scan_less_than(&mut self) -> Token {
    let start_pos = self.current_position();

    // Check if previous token is an identifier immediately adjacent
    if let Some(prev) = &self.previous_token {
        if prev.kind.is_identifier()
            && prev.span.end.offset == start_pos.offset
        {
            // No whitespace: this is a generic bracket
            return Token::GenericOpen;
        }
    }

    // Whitespace present: this is a less-than or HTML tag
    Token::LessThan
}

L'idée clé : dans Option<T>, il n'y a pas d'espace entre Option et <. Dans <div>, le < commence soit une ligne, soit est précédé d'un espace. Le lexer vérifie si le < est immédiatement adjacent à l'identifiant précédent. Si oui, c'est un chevron générique. Sinon, c'est du HTML ou une comparaison.

Cette heuristique fonctionne car la convention de style de FLIN -- et en fait la convention de chaque langage avec des génériques -- est d'écrire Option<T> sans espaces. Personne n'écrit Option <T>. La vérification d'adjacence est effectivement une exigence de formatage, et c'est une exigence que chaque développeur respecte déjà.

L'approche par adjacence des positions a été la percée de la Session 101. Avant cette solution, nous avons envisagé plusieurs alternatives :

1. Désambiguïsation par mot-clé. Exiger le mot-clé generic avant les paramètres de type. Rejeté car cela ajoute de la verbosité à chaque utilisation de générique.
2. Analyse lexicale dépendante du contexte. Suivre l'état du parser dans le lexer. Rejeté car cela couple les deux phases et rend le lexer non trivial.
3. Délimiteurs différents. Utiliser [T] ou ::<T>. Rejeté car ils entrent en conflit avec la syntaxe existante ou semblent étrangers.

L'adjacence des positions était élégante car elle nécessitait des modifications de code minimales et s'alignait avec les conventions de formatage existantes.

Représentation dans l'AST

Les types génériques ont nécessité deux nouvelles variantes dans l'AST :

rustpub enum Type {
    // ... existing variants ...
    TypeParam(String),                          // T, U, etc.
    Generic { name: String, type_args: Vec<Type> },  // Option<int>, Result<T, E>
}

Et deux modifications aux instructions existantes :

rustpub enum Stmt {
    TypeDecl {
        name: String,
        type_params: Vec<String>,   // NEW: <T, U, ...>
        value: Type,
        // ...
    },
    FnDecl {
        name: String,
        type_params: Vec<String>,   // NEW: <T, U, ...>
        params: Vec<Param>,
        return_type: Option<Type>,
        body: Block,
        // ...
    },
    // ...
}

Le champ type_params sur TypeDecl et FnDecl porte les paramètres de type déclarés. Ces paramètres sont ensuite dans la portée lors de l'analyse du corps de la déclaration.

Analyse des déclarations génériques

L'analyse des déclarations de type générique a nécessité une nouvelle fonction, parse_type_params :

rustfn parse_type_params(&mut self) -> Result<Vec<String>, ParseError> {
    if !self.match_token(&Token::GenericOpen) {
        return Ok(vec![]);
    }

    let mut params = vec![];
    loop {
        let name = self.expect_identifier()?;
        params.push(name);
        if !self.match_token(&Token::Comma) {
            break;
        }
    }
    self.expect(&Token::GreaterThan)?;
    Ok(params)
}

Cette fonction est appelée après l'analyse du nom d'un alias de type ou d'une fonction. Si un token GenericOpen suit, elle collecte tous les noms de paramètres de type. Sinon, elle retourne un vecteur vide -- la déclaration n'est pas générique.

L'analyse des instanciations de type générique -- Option<int> -- a nécessité l'extension du parser de type de base :

rustfn parse_base_type(&mut self) -> Result<Type, ParseError> {
    let name = self.expect_identifier()?;

    // Check for type arguments
    if self.check(&Token::GenericOpen) {
        let type_args = self.parse_type_arguments()?;
        Ok(Type::Generic { name, type_args })
    } else if self.type_params_in_scope.contains(&name) {
        // This is a type parameter reference
        Ok(Type::TypeParam(name))
    } else {
        Ok(Type::Named(name))
    }
}

La vérification type_params_in_scope est cruciale. Lors de l'analyse à l'intérieur d'une fonction ou d'un type générique, le parser sait quels noms sont des paramètres de type. T à l'intérieur de fn identity<T>(value: T) est un TypeParam, pas une référence à un type appelé T.

Support du vérificateur de types

Le vérificateur de types a gagné deux nouvelles variantes dans FlinType :

rustpub enum FlinType {
    // ... existing variants ...
    TypeParam(String),
    Generic { name: String, type_args: Vec<FlinType> },
}

Quand le vérificateur de types rencontre un appel de fonction générique, il effectue une substitution des paramètres de type. Si identity<T> est appelé avec un argument int, le vérificateur substitue T = int dans toute la signature de la fonction et vérifie que le type de retour est aussi int.

La logique de substitution :

rustfn substitute_type_params(
    &self,
    flin_type: &FlinType,
    substitutions: &HashMap<String, FlinType>,
) -> FlinType {
    match flin_type {
        FlinType::TypeParam(name) => {
            substitutions.get(name).cloned().unwrap_or(FlinType::Any)
        }
        FlinType::List(inner) => {
            FlinType::List(Box::new(self.substitute_type_params(inner, substitutions)))
        }
        FlinType::Optional(inner) => {
            FlinType::Optional(Box::new(self.substitute_type_params(inner, substitutions)))
        }
        FlinType::Generic { name, type_args } => {
            let resolved_args: Vec<FlinType> = type_args
                .iter()
                .map(|arg| self.substitute_type_params(arg, substitutions))
                .collect();
            FlinType::Generic { name: name.clone(), type_args: resolved_args }
        }
        other => other.clone(),
    }
}

Cette fonction parcourt la structure de type récursivement, remplaçant chaque TypeParam par sa substitution concrète. Option<T> avec T = int devient Option<int>. [T] devient [int]. Les génériques imbriqués comme Result<Option<T>, E> avec T = int, E = text deviennent Result<Option<int>, text>.

Génériques imbriqués

Les génériques imbriqués fonctionnent naturellement car le parser d'arguments de type est récursif :

flindata: Option<[int]> = [1, 2, 3]
nested: Result<Option<int>, text> = "error"

Le parser voit Option, puis <, puis analyse [int] comme un type (une liste d'int), puis voit >. Le résultat est Generic { name: "Option", type_args: [List(Int)] }. L'imbrication à profondeur arbitraire est supportée car parse_type_arguments appelle parse_type, qui peut lui-même rencontrer et analyser des types génériques.

Champs d'entité avec génériques

Les types génériques peuvent apparaître comme types de champs d'entité :

flinentity Container {
    value: Option<int>
    items: Result<[text], text>
}

Le vérificateur de types résout les types génériques lors de la vérification des déclarations de champs d'entité. Option<int> est résolu en un type entier optionnel concret. Cela garantit que la construction d'entité est type-safe :

flinContainer { value: 42, items: ["a", "b"] }  // OK
Container { value: "not an int" }             // ERROR

Affichage et messages d'erreur

Les types génériques ont nécessité un formatage d'affichage approprié pour les messages d'erreur :

rustimpl fmt::Display for Type {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Type::TypeParam(name) => write!(f, "{}", name),
            Type::Generic { name, type_args } => {
                write!(f, "{}<", name)?;
                for (i, arg) in type_args.iter().enumerate() {
                    if i > 0 { write!(f, ", ")?; }
                    write!(f, "{}", arg)?;
                }
                write!(f, ">")
            }
            // ...
        }
    }
}

Quand le compilateur signale une erreur impliquant des types génériques, il les affiche dans la même syntaxe que le développeur a écrite : Option<int>, Result<text, text>, [T]. Cette cohérence entre le code source et les messages d'erreur réduit la charge cognitive du débogage des erreurs de type.

La suite de tests

La Session 101 a ajouté 12 nouveaux tests de parser spécifiquement pour les types génériques :

• test_parse_generic_type_alias_single -- type Option<T> = T?
• test_parse_generic_type_alias_multiple -- type Result<T, E> = T | E
• test_parse_generic_function_single -- fn identity<T>(value: T) -> T
• test_parse_generic_function_multiple -- fn map<T, U>(list: [T], f: (T) -> U) -> [U]
• test_parse_generic_type_instantiation -- value: Option<int>
• test_parse_generic_type_instantiation_multiple -- result: Result<int, text>
• test_parse_generic_type_nested -- data: Option<[int]>
• test_parse_generic_type_display -- vérification du formatage
• test_parse_generic_in_entity_field -- champ d'entité avec type générique
• test_parse_non_generic_type_alias -- s'assurer que les alias non génériques fonctionnent toujours
• test_parse_non_generic_function -- s'assurer que les fonctions non génériques fonctionnent toujours

Les deux derniers tests sont aussi importants que les neuf premiers. Les tests de régression garantissent que l'ajout des génériques ne casse pas l'analyse du code non générique. Avec 1 059 tests de bibliothèque et 93 tests d'intégration tous passants, nous avions confiance que la fonctionnalité était additive -- elle étendait le langage sans rien casser.

Phase 2 terminée

Avec les types génériques, la Phase 2 du système de types de FLIN était complète :

Quatre fonctionnalités à travers trois sessions. Chacune s'appuyait sur l'infrastructure de la précédente : les types union utilisaient le vérificateur de compatibilité de types, les génériques utilisaient l'infrastructure des types union pour Result<T, E> = T | E, et tous utilisaient le moteur d'inférence de types bidirectionnel.

Cette construction en couches n'est pas accidentelle. C'est le produit de la conception du système de types comme un tout cohérent avant d'implémenter une fonctionnalité individuelle. Nous savions dès le départ que les types union auraient besoin de paramètres de type génériques, que les types génériques auraient besoin de membres de type union, et que les deux auraient besoin du rétrécissement de type. Les construire en séquence -- types union d'abord, puis génériques -- signifiait que chaque fonctionnalité pouvait présupposer l'existence de la précédente.

L'impact plus large

Les types génériques ont déclenché une cascade de fonctionnalités en aval. Les bornes de trait (where T: Comparable) nécessitaient des paramètres de type génériques comme cible des contraintes. Le pattern matching sur des enums génériques nécessitait l'instanciation de type générique. Les opérations de collection de la bibliothèque standard (map, where, reduce) avaient toutes besoin de signatures de fonctions génériques.

Sans la Session 101, aucune de ces fonctionnalités n'aurait été possible de manière type-safe. Les génériques sont la fondation sur laquelle repose l'ensemble du système de types avancé.

Le prochain article couvre les traits et interfaces -- le mécanisme par lequel FLIN contraint ce qu'un paramètre de type générique peut faire.

Ceci est la partie 33 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 : - [31] Le système de types de FLIN : inféré, expressif, sûr - [32] Types union et rétrécissement de type - [33] Les types génériques dans FLIN (vous êtes ici) - [34] Traits et interfaces - [35] Pattern matching : de switch à match