Les types génériques ont donné à FLIN la capacité d'écrire des fonctions qui fonctionnent avec n'importe quel type. Mais « n'importe quel type » est trop large. Une fonction de tri ne fonctionne pas avec n'importe quel type -- elle fonctionne avec les types qui peuvent être comparés. Une fonction de sérialisation ne fonctionne pas avec n'importe quel type -- elle fonctionne avec les types qui peuvent être convertis en texte. Une fonction de hachage ne fonctionne pas avec n'importe quel type -- elle fonctionne avec les types qui ont une implémentation de hachage.
Les traits sont le mécanisme qui contraint les types génériques au sous-ensemble de types qui supportent réellement les opérations dont une fonction a besoin.
Les Sessions 133 à 136 ont construit le système de traits de FLIN de A à Z : les déclarations de traits, les blocs impl, les bornes de traits sur les paramètres de type génériques, et l'infrastructure du vérificateur de types qui valide les contraintes à la compilation.
La conception
Le système de traits de FLIN s'inspire du système de traits de Rust et du système d'interfaces de TypeScript, mais simplifie les deux pour le public de FLIN.
Un trait déclare un ensemble de signatures de méthodes qu'un type doit implémenter :
flintrait Printable {
fn to_text() -> text
}
trait Comparable {
fn compare(other: Self) -> int
}
trait Serializable {
fn serialize() -> text
fn deserialize(data: text) -> Self
}Un bloc impl fournit l'implémentation pour un type spécifique :
flinentity User {
name: text
email: text
}
impl Printable for User {
fn to_text() -> text {
return name + " <" + email + ">"
}
}
impl Comparable for User {
fn compare(other: User) -> int {
return name.compare(other.name)
}
}Cette séparation -- déclaration à un endroit, implémentation à un autre -- est la décision de conception clé. Cela signifie que les traits peuvent être définis dans un module et implémentés dans un autre. Une bibliothèque peut définir un trait, et le code utilisateur peut l'implémenter pour ses propres types.
Pourquoi les traits, pas les interfaces
TypeScript utilise les interfaces. Java utilise les interfaces. Pourquoi FLIN a-t-il choisi les traits ?
La distinction est importante. Une interface en TypeScript est structurelle : tout objet avec la bonne forme satisfait l'interface, qu'il le déclare ou non. Un trait dans FLIN est nominal : un type satisfait un trait uniquement s'il y a un bloc impl explicite déclarant l'implémentation.
Nous avons choisi les traits nominaux pour deux raisons.
Premièrement, l'explicité. Quand on voit impl Comparable for User, on sait exactement quels types implémentent quels traits. Dans un système structurel, il faut examiner la forme de chaque type pour déterminer la compatibilité. Pour le public cible de FLIN -- des développeurs qui valorisent la clarté plutôt que l'ingéniosité -- l'implémentation explicite est plus facile à comprendre.
Deuxièmement, les messages d'erreur. Quand une borne de trait échoue, le compilateur peut dire « User n'implémente pas Comparable -- ajoutez un bloc impl Comparable for User ». Avec le typage structurel, l'erreur serait « User n'a pas la méthode compare(other: Self) -> int » -- ce qui est techniquement correct mais ne dit pas au développeur quelle abstraction il n'a pas satisfaite.
Déclaration de trait dans l'AST
La déclaration de trait est une nouvelle variante d'instruction :
rustpub enum Stmt {
TraitDecl {
name: String,
type_params: Vec<TypeParam>,
methods: Vec<TraitMethod>,
span: Span,
},
ImplBlock {
trait_name: String,
target_type: Type,
type_args: Vec<Type>,
methods: Vec<Stmt>,
span: Span,
},
// ...
}
pub struct TraitMethod {
pub name: String,
pub params: Vec<Param>,
pub return_type: Option<Type>,
pub default_body: Option<Block>,
pub span: Span,
}Un TraitMethod inclut un default_body optionnel. Les implémentations par défaut sont des méthodes qu'un trait fournit prêtes à l'emploi, que les implémenteurs peuvent redéfinir si nécessaire :
flintrait Printable {
fn to_text() -> text // requis
fn debug_text() -> text { // implémentation par défaut
return "[" + to_text() + "]"
}
}Avec un corps par défaut, implémenter Printable ne nécessite que to_text(). La méthode debug_text() est fournie gratuitement, utilisant l'implémentation par défaut.
Analyse des traits et des blocs impl
Le parser reconnaît trait et impl comme mots-clés et les envoie vers des fonctions d'analyse dédiées :
rustfn parse_trait_decl(&mut self) -> Result<Stmt, ParseError> {
self.expect_keyword("trait")?;
let name = self.expect_identifier()?;
let type_params = self.parse_type_params()?;
self.expect(&Token::LeftBrace)?;
let mut methods = vec![];
while !self.check(&Token::RightBrace) {
methods.push(self.parse_trait_method()?);
}
self.expect(&Token::RightBrace)?;
Ok(Stmt::TraitDecl { name, type_params, methods, span: self.current_span() })
}
fn parse_impl_block(&mut self) -> Result<Stmt, ParseError> {
self.expect_keyword("impl")?;
let trait_name = self.expect_identifier()?;
self.expect_keyword("for")?;
let target_type = self.parse_type()?;
self.expect(&Token::LeftBrace)?;
let mut methods = vec![];
while !self.check(&Token::RightBrace) {
methods.push(self.parse_fn_decl()?);
}
self.expect(&Token::RightBrace)?;
Ok(Stmt::ImplBlock { trait_name, target_type, type_args: vec![], methods, span: self.current_span() })
}L'analyse est directe car la syntaxe est régulière. trait Name { methods } et impl Trait for Type { methods } suivent le même modèle de bloc délimité par des accolades que les entités et les fonctions.
Vérificateur de types : enregistrement des traits
Quand le vérificateur de types rencontre une déclaration de trait, il enregistre le trait dans un registre de traits :
ruststruct TraitRegistry {
traits: HashMap<String, TraitDef>,
impls: HashMap<(String, String), ImplDef>, // (trait_name, type_name) -> impl
}
struct TraitDef {
name: String,
type_params: Vec<String>,
methods: Vec<TraitMethodDef>,
}
struct TraitMethodDef {
name: String,
params: Vec<(String, FlinType)>,
return_type: FlinType,
has_default: bool,
}Quand le vérificateur de types rencontre un bloc impl, il valide trois choses :
- Le trait existe.
- Le type cible existe.
- Chaque méthode requise est implémentée avec la bonne signature.
rustfn check_impl_block(&mut self, impl_block: &Stmt) {
let Stmt::ImplBlock { trait_name, target_type, methods, .. } = impl_block else {
return;
};
let trait_def = match self.trait_registry.get(trait_name) {
Some(def) => def,
None => {
self.report_error(&format!("unknown trait: {}", trait_name));
return;
}
};
// Check all required methods are implemented
for required in &trait_def.methods {
if required.has_default {
continue; // default methods are optional
}
let found = methods.iter().find(|m| m.name() == required.name);
if found.is_none() {
self.report_error(&format!(
"impl {} for {} is missing method '{}'",
trait_name, target_type, required.name
));
}
}
// Check method signatures match
for method in methods {
if let Some(required) = trait_def.methods.iter().find(|m| m.name == method.name()) {
self.check_method_signature(method, required);
}
}
}Cette validation est la valeur fondamentale des traits. Si un type prétend implémenter un trait, le compilateur vérifie cette prétention. Pas d'implémentations partielles. Pas de méthodes manquantes. Pas d'incompatibilités de signatures.
Bornes de traits sur les génériques
L'utilisation principale des traits est de contraindre les paramètres de type génériques. Une fonction générique qui trie une liste a besoin de savoir que les éléments peuvent être comparés :
flinfn sort<T: Comparable>(items: [T]) -> [T] {
// ... logique de tri qui utilise T.compare() ...
}La syntaxe T: Comparable est une borne de trait. Elle signifie « T peut être n'importe quel type, tant que ce type implémente le trait Comparable ». Le compilateur l'applique à chaque site d'appel :
flinsort([3, 1, 2]) // OK -- int implémente Comparable
sort(["c", "a", "b"]) // OK -- text implémente Comparable
sort([User{...}]) // ERROR -- User n'implémente pas Comparable
// (sauf s'il y a un impl Comparable for User)Dans le vérificateur de types, les bornes de traits sont validées lorsque des fonctions génériques sont appelées :
rustfn check_generic_call(
&mut self,
func: &FnDef,
type_args: &[FlinType],
call_span: Span,
) {
for (i, param) in func.type_params.iter().enumerate() {
let concrete_type = &type_args[i];
for bound in ¶m.constraints {
if !self.type_implements_trait(concrete_type, bound) {
self.report_error(&format!(
"type {} does not implement trait {}",
concrete_type, bound
));
}
}
}
}
fn type_implements_trait(&self, flin_type: &FlinType, trait_name: &str) -> bool {
let type_name = flin_type.display_name();
self.trait_registry.impls.contains_key(&(
trait_name.to_string(),
type_name,
))
}La recherche d'implémentation est une simple vérification dans une table de hachage. Une paire (trait_name, type_name) existe-t-elle dans le registre d'impl ? Si oui, le type implémente le trait. Sinon, la borne est violée.
Implémentations de traits intégrées
Les types primitifs de FLIN sont livrés avec des implémentations de traits intégrées. Celles-ci sont enregistrées dans le registre de traits lors de l'initialisation du compilateur :
flin// Built-in implementations (implicit, not written by users)
impl Comparable for int { ... }
impl Comparable for number { ... }
impl Comparable for text { ... }
impl Printable for int { ... }
impl Printable for number { ... }
impl Printable for text { ... }
impl Printable for bool { ... }Cela signifie que les fonctions génériques avec des bornes Comparable fonctionnent directement avec les types primitifs. Les utilisateurs n'ont besoin d'écrire des blocs impl que pour leurs propres types d'entité.
Le type Self
Les traits utilisent Self pour référencer le type qui les implémente :
flintrait Cloneable {
fn clone() -> Self
}
impl Cloneable for User {
fn clone() -> User { // Self devient User
return User {
name: name,
email: email
}
}
}Dans le vérificateur de types, Self est résolu vers le type concret lors de la vérification des blocs impl :
rustfn resolve_self_type(&self, flin_type: &FlinType, self_type: &FlinType) -> FlinType {
match flin_type {
FlinType::SelfType => self_type.clone(),
FlinType::List(inner) => {
FlinType::List(Box::new(self.resolve_self_type(inner, self_type)))
}
FlinType::Optional(inner) => {
FlinType::Optional(Box::new(self.resolve_self_type(inner, self_type)))
}
other => other.clone(),
}
}Bornes de traits multiples
Un paramètre de type peut avoir plusieurs bornes de traits :
flinfn sort_and_print<T: Comparable + Printable>(items: [T]) {
sorted = sort(items)
for item in sorted {
print(item.to_text())
}
}La syntaxe + combine les traits. Le type doit implémenter tous les traits listés. Le vérificateur de types valide chaque borne indépendamment :
rustfor bound in ¶m.constraints {
if !self.type_implements_trait(concrete_type, bound) {
self.report_error(/* ... */);
}
}Les bornes multiples sont stockées comme un vecteur de noms de contraintes sur chaque paramètre de type. La boucle vérifie chacune.
Messages d'erreur pour les violations de traits
Quand une borne de trait échoue, le message d'erreur est spécifique et actionnable :
error[E0010]: trait bound not satisfied
--> app.flin:15:5
|
15 | sort([User{name: "Juste"}])
| ^^^^ User does not implement Comparable
|
= note: required by bound T: Comparable in fn sort<T: Comparable>
= hint: add an implementation: impl Comparable for User { fn compare(other: User) -> int { ... } }L'erreur dit au développeur quel trait est manquant, où il est requis, et comment le corriger. L'indice inclut la signature de méthode qui doit être implémentée. Ce niveau de détail est possible car les traits sont nominaux -- le compilateur sait exactement quel trait est manquant et quelles sont ses méthodes.
Décisions de conception
Plusieurs décisions de conception ont façonné le système de traits de FLIN.
Pas d'héritage de traits. Les traits ne peuvent pas étendre d'autres traits. Cela garde le système simple -- il n'y a pas de problème du diamant, pas d'ordre de résolution de méthode, pas d'exigences de super-trait. Si une fonction a besoin à la fois de Comparable et Printable, elle utilise T: Comparable + Printable.
Pas de types associés (initialement). Les types associés -- des types définis comme partie d'un trait -- ont été reportés à une session ultérieure. Le système de traits initial se concentrait sur les méthodes.
Pas de règle orpheline. En Rust, on ne peut implémenter un trait pour un type que si on possède soit le trait, soit le type. FLIN n'applique pas cette règle, car les programmes FLIN sont typiquement des applications mono-auteur, pas des écosystèmes multi-crates.
Les blocs impl sont des instructions. Les blocs impl peuvent apparaître partout où les instructions peuvent apparaître -- au niveau supérieur d'un fichier, à l'intérieur d'un bloc, même conditionnellement. C'est plus flexible que l'approche de Rust (où les blocs impl doivent être au niveau du module) et s'aligne avec la philosophie de FLIN que le fichier est le composant.
L'arc des sessions
Le système de traits a été construit à travers quatre sessions :
- Session 133 : Syntaxe de déclaration de trait, analyse et représentation AST
- Session 134 : Blocs impl, analyse et validation des méthodes de trait
- Session 135 : Bornes de traits sur les paramètres de type génériques
- Session 136 : Implémentations de traits intégrées, messages d'erreur et interaction avec le type Never
Chaque session s'appuyait sur la précédente et maintenait la suite de tests complète tout au long. À la Session 136, FLIN avait un système de traits complet -- pas aussi puissant que celui de Rust, mais suffisamment puissant pour les motifs que les programmes FLIN utilisent réellement.
Ce que les traits permettent
Avec les traits en place, la bibliothèque standard de FLIN pouvait exprimer des motifs qui étaient auparavant impossibles à vérifier au niveau des types :
flinfn max<T: Comparable>(a: T, b: T) -> T {
if a.compare(b) > 0 { return a }
return b
}
fn to_text_list<T: Printable>(items: [T]) -> [text] {
return items.map(x => x.to_text())
}
fn find_min<T: Comparable>(items: [T]) -> T? {
if items.len == 0 { return none }
result = items[0]
for item in items[1:] {
if item.compare(result) < 0 {
result = item
}
}
return result
}Chacune de ces fonctions est générique, type-safe, et fonctionne avec n'importe quel type qui satisfait la borne de trait. Le compilateur vérifie à chaque site d'appel que le type concret a l'implémentation requise. Pas de dispatch à l'exécution. Pas d'erreurs de type à l'exécution.
Les traits ont complété le troisième pilier du système de types de FLIN. Les primitifs et l'inférence fournissent la fondation. Les types union et les génériques fournissent l'expressivité. Les traits fournissent les contraintes qui rendent les génériques sûrs. Ensemble, ils forment un système de types suffisamment simple pour les débutants et suffisamment puissant pour les applications réelles.
Le prochain article couvre le pattern matching -- la syntaxe qui lie toutes ces fonctionnalités du système de types en un code ergonomique.
Ceci est la partie 34 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 : - [32] Types union et rétrécissement de type - [33] Les types génériques dans FLIN - [34] Traits et interfaces (vous êtes ici) - [35] Pattern matching : de switch à match - [36] Types union étiquetés et types de données algébriques