Un langage sans fermetures est un langage sans puissance. La Session 013 a donné à FLIN à la fois les fermetures et les fonctions d'ordre supérieur qui en dépendent -- map, filter et reduce -- en un seul sprint de soixante minutes qui a produit 16 nouveaux opcodes et 37 nouveaux tests.
Les fermetures sont l'une de ces fonctionnalités qui semblent simples du point de vue de l'utilisateur. Vous écrivez une fonction qui référence une variable de sa portée englobante, et ça marche tout simplement. Mais sous le capot, dans une VM basée sur la pile où les variables locales vivent sur des cadres d'appel qui disparaissent quand les fonctions retournent, « ça marche tout simplement » nécessite une ingénierie soigneuse.
C'est l'histoire de comment nous avons fait fonctionner les fermetures dans la VM de FLIN, comment nous avons construit l'infrastructure des fonctions d'ordre supérieur par-dessus, et comment nous avons combattu le borrow checker de Rust à chaque étape.
Ce que sont les fermetures et pourquoi elles comptent
Une fermeture est une fonction associée à un environnement -- un instantané des variables qu'elle référence depuis sa portée englobante. Considérez ce code FLIN :
flinmultiplier = 3
double = |x| x * multiplier
result = double(5) // 15Le lambda |x| x * multiplier capture la variable multiplier. Quand double(5) s'exécute, le lambda a besoin d'accéder à multiplier même si ce n'est pas un paramètre. La valeur 3 doit être transportée avec la fonction elle-même.
Dans un interpréteur qui parcourt un AST, c'est facile : les fermetures capturent une référence à l'environnement englobant. Dans une VM de bytecode, c'est plus difficile, parce que l'environnement englobant (le cadre d'appel) pourrait avoir été dépilé de la pile d'appels au moment où la fermeture s'exécute.
FLIN résout cela en stockant les valeurs capturées directement dans l'objet fermeture sur le tas :
rustpub struct ClosureData {
pub function: FunctionData,
pub captures: Vec<Value>,
}Quand le compilateur crée une fermeture, il émet des instructions pour copier les variables capturées depuis leurs emplacements courants (pile, locales ou globales) dans le vecteur captures de la fermeture. Quand la fermeture est appelée, la VM rend ces valeurs capturées disponibles comme si elles étaient des variables locales.
L'objet fermeture
Sur le tas, une fermeture ressemble à ceci :
rustObjectData::Closure(ClosureData {
function: FunctionData {
name: "double".to_string(),
arity: 1,
address: 42, // Adresse bytecode du corps de la fonction
local_count: 1,
},
captures: vec![Value::Int(3)], // multiplier = 3
})Le champ function contient tout ce dont la VM a besoin pour appeler la fermeture : son nom (pour les messages d'erreur), son arité (combien d'arguments elle attend), son adresse bytecode (où sauter) et combien de variables locales elle utilise. Le vecteur captures contient les valeurs qui ont été fermées au moment de la création.
C'est une conception de « fermeture plate » -- toutes les valeurs capturées sont copiées dans la fermeture au moment de la création. L'alternative est les « upvalues » (comme dans Lua), où la fermeture contient des références à des cellules mutables qui peuvent être partagées entre la portée englobante et la fermeture. Les fermetures plates sont plus simples et plus rapides pour le cas courant où les valeurs capturées sont en lecture seule. FLIN ne supporte pas actuellement la mutation des variables capturées depuis l'intérieur d'une fermeture, donc les fermetures plates sont suffisantes.
Infrastructure des fonctions d'ordre supérieur
Avec les fermetures fonctionnelles, nous avions besoin de map, filter et reduce -- les trois chevaux de trait de la programmation fonctionnelle. Mais implémenter des fonctions d'ordre supérieur dans une VM de bytecode est fondamentalement différent de les implémenter dans un interpréteur en langage hôte.
Dans un moteur JavaScript, array.map(fn) appelle fn en utilisant le mécanisme d'appel du langage hôte. Dans la VM de FLIN, le corps de la fermeture est du bytecode. L'appeler signifie configurer un cadre d'appel, sauter à l'adresse bytecode de la fermeture, exécuter les instructions et gérer le retour. Et map doit faire cela une fois pour chaque élément de la liste.
Nous ne pouvions pas simplement boucler en Rust et appeler la fermeture N fois, parce que la fermeture exécute du bytecode FLIN, pas du code Rust. La fermeture pourrait elle-même appeler d'autres fonctions, allouer des objets, ou même déclencher un autre map. La boucle d'exécution de la VM doit rester le seul point de contrôle.
La solution était une approche basée sur les continuations : l'infrastructure HOF gère l'état d'itération sur une pile séparée, et l'instruction Return normale est augmentée pour vérifier si elle retourne d'un callback HOF.
Le HofContext
rust#[derive(Debug, Clone, Copy, PartialEq)]
pub enum HofKind {
Map,
Filter,
Reduce,
}
#[derive(Debug, Clone)]
pub struct HofContext {
pub kind: HofKind,
pub source_list: ObjectId,
pub current_index: usize,
pub length: usize,
pub results: Vec<Value>,
pub accumulator: Option<Value>,
pub closure_id: ObjectId,
pub return_ip: usize,
}Quand la VM rencontre une instruction ListMap, ListFilter ou ListReduce, elle crée un HofContext et le pousse sur la hof_stack. Le contexte suit quelle liste est itérée, la position courante, les résultats accumulés, la fermeture à appeler et où reprendre quand l'ensemble du HOF est terminé.
La VM appelle ensuite la fermeture pour le premier élément en utilisant hof_call_next :
rustfn hof_call_next(&mut self, chunk: &Chunk) -> Result<(), RuntimeError> {
let (source_list, current_index, closure_id, kind, accumulator) = {
let ctx = self.hof_stack.last().ok_or(
RuntimeError::InternalError("No HOF context".into())
)?;
(ctx.source_list, ctx.current_index, ctx.closure_id,
ctx.kind, ctx.accumulator.clone())
};
// Obtenir l'élément courant de la liste source
let element = {
let list = self.get_list(source_list)?;
list[current_index].clone()
};
// Configurer l'appel de fermeture
let closure = self.get_closure(closure_id)?;
let frame = CallFrame {
return_ip: self.ip,
base_pointer: self.stack.len(),
locals: vec![element.clone()],
function_name: closure.function.name.clone(),
};
// Pour reduce, la fermeture prend deux arguments : accumulateur et élément
if kind == HofKind::Reduce {
if let Some(acc) = accumulator {
frame.locals.insert(0, acc);
}
}
self.frames.push(frame);
self.ip = closure.function.address;
Ok(())
}Remarquez la déstructuration en haut. Nous extrayons toutes les valeurs nécessaires du HofContext dans des variables locales avant de faire quoi que ce soit d'autre. C'est le pattern du borrow checker que nous avons décrit dans l'article précédent -- extraire les données avant de muter self.
Return modifié
L'idée clé est que l'opcode Return fait double emploi. Quand il retourne d'un appel de fonction normal, il restaure le cadre de l'appelant. Quand il retourne d'un callback HOF, il alimente le résultat dans la machinerie HOF :
rustOpCode::Return => {
let result = self.pop();
if !self.hof_stack.is_empty() {
// Continuation HOF : traiter la valeur de retour du callback
self.hof_handle_return(result)?;
// Si le HOF n'est pas terminé, appeler la fermeture pour l'élément suivant
if !self.hof_stack.is_empty() {
self.hof_call_next(chunk)?;
}
} else {
// Retour de fonction normal
let frame = self.frames.pop().unwrap();
self.ip = frame.return_ip;
self.stack.truncate(frame.base_pointer);
self.push(result);
}
}Gestion des retours
hof_handle_return traite la valeur de retour du callback différemment selon le type de HOF :
- Map : la valeur de retour est ajoutée au vecteur de résultats inconditionnellement.
- Filter : la valeur de retour est testée pour sa véracité. Si vraie, l'élément courant (pas la valeur de retour) est ajouté aux résultats.
- Reduce : la valeur de retour devient le nouvel accumulateur.
Quand l'index courant atteint la longueur de la liste, le HOF est complet. Le HofContext est dépilé de la hof_stack, le pointeur d'instruction est restauré à return_ip, et le résultat final (une nouvelle liste pour map/filter, l'accumulateur pour reduce) est poussé sur la pile d'opérandes.
16 nouveaux opcodes
La Session 013 a ajouté 16 nouveaux opcodes dans la plage 0xE0-0xEF :
rust// Fonctions intégrées étendues (0xE0-0xEF)
Replace = 0xE0, // Remplacement de chaîne
Abs = 0xE1, // Valeur absolue mathématique
Floor = 0xE2, // Plancher mathématique
Ceil = 0xE3, // Plafond mathématique
Round = 0xE4, // Arrondi mathématique
Min = 0xE5, // Minimum mathématique
Max = 0xE6, // Maximum mathématique
Sqrt = 0xE7, // Racine carrée mathématique
PowFn = 0xE8, // Puissance mathématique
ListFirst = 0xE9, // Premier élément
ListLast = 0xEA, // Dernier élément
ListReverse = 0xEB, // Inverser la liste
ListSort = 0xEC, // Trier la liste
ListMap = 0xED, // HOF map avec fermeture
ListFilter = 0xEE, // HOF filter avec fermeture
ListReduce = 0xEF, // HOF reduce avec fermetureLes 13 premiers sont des fonctions intégrées simples. ListMap, ListFilter et ListReduce sont les opcodes HOF qui déclenchent la machinerie de continuation décrite ci-dessus.
Chaque fonction mathématique intégrée gère les arguments Int et Float :
rustOpCode::Abs => {
let val = self.pop();
let result = match val {
Value::Int(n) => Value::Int(n.abs()),
Value::Float(n) => Value::Float(n.abs()),
_ => return Err(RuntimeError::TypeError(
"abs() requires a number".into()
)),
};
self.push(result);
}Les opérations de liste créent de nouvelles listes plutôt que de muter en place. reverse(list) retourne une nouvelle liste inversée. sort(list) retourne une nouvelle liste triée. La liste originale est intouchée. Cette approche immuable par défaut simplifie le raisonnement sur les opérations de liste et élimine toute une classe de bogues où une fonction mute inopinément son entrée.
Le borrow checker riposte
S'il y a une session où le borrow checker de Rust était notre adversaire principal, c'était celle-ci. L'infrastructure HOF nécessite de lire le tas (pour obtenir la liste source et la fermeture) tout en écrivant aussi sur le tas (pour allouer les résultats) et en mutant l'état de la VM (pousser des cadres, changer le pointeur d'instruction).
La solution était toujours la même : extraire ce dont vous avez besoin dans des variables locales d'abord, puis muter.
rust// Extraire les valeurs avant les opérations mutables
let (source_list, current_index, closure_id, kind, accumulator) = {
let ctx = self.hof_stack.last().ok_or(...)?;
(ctx.source_list, ctx.current_index, ctx.closure_id,
ctx.kind, ctx.accumulator.clone())
};
// Maintenant sûr d'appeler self.push(), self.get_list(), etc.Ce pattern apparaît au moins une douzaine de fois dans l'implémentation HOF. Chaque fois, nous cadrons l'emprunt immutable de self (pour lire le contexte HOF) dans un bloc, laissant l'emprunt se terminer avant le début des opérations mutables.
Trois sous-agents parallèles ont travaillé sur la Session 013 : un sur les fonctions mathématiques intégrées et les opcodes, un sur l'infrastructure HOF et un sur les tests. Les trois ont terminé, mais l'agent HOF a eu besoin de corrections manuelles pour les problèmes de borrow checker. Le borrow checker ne comprend pas l'intention -- il ne voit que les durées de vie. Et l'intention de « lire ceci, puis écrire cela » nécessite que le programmeur rende le séquençage explicite.
Test des fonctions d'ordre supérieur
La suite de tests pour les fonctions intégrées et les HOF couvrait 37 nouveaux cas :
Fonctions intégrées de chaîne (16 tests) : len, upper, lower, trim, split, join, contains, starts_with, ends_with, replace -- chacune testée avec des entrées typiques et des cas limites.
Fonctions intégrées mathématiques (14 tests) : abs, floor, ceil, round, sqrt, min, max, pow -- chacune testée avec des entrées Int et Float, y compris les nombres négatifs et les cas limites comme sqrt(0).
Fonctions intégrées de liste (7 tests) : first, last, reverse, sort, len -- incluant les listes vides et les listes à un élément.
Les tests HOF étaient des tests d'intégration qui compilaient du source FLIN en bytecode et l'exécutaient :
rustfn compile_and_run(source: &str) -> Result<(Value, VM), String> {
let tokens = tokenize(source)?;
let program = parse(tokens)?;
check(&program)?;
let chunk = CodeGenerator::new().generate(&program)?;
let mut vm = VM::new();
let result = vm.execute(&chunk)?;
Ok((result, vm))
}Ce helper était le cheval de trait de tous les tests de VM à partir de la Session 011. Il prend du code source FLIN comme chaîne, l'exécute à travers le pipeline complet (lexer, parser, vérificateur de types, générateur de code, VM) et retourne le résultat. Si une étape échoue, le message d'erreur vous dit exactement où.
Ce que cela a débloqué
Avec les fermetures et les HOF fonctionnels, FLIN a gagné des capacités de programmation fonctionnelle que la plupart des développeurs attendent d'un langage moderne. Un développeur pouvait écrire :
flinnumbers = [1, 2, 3, 4, 5]
doubled = numbers.map(|x| x * 2) // [2, 4, 6, 8, 10]
evens = numbers.filter(|x| x % 2 == 0) // [2, 4]
sum = numbers.reduce(|a, b| a + b, 0) // 15Chacune de ces expressions se compile en bytecode que la VM exécute en utilisant la machinerie de continuation HOF. La fermeture |x| x * 2 est une vraie fermeture -- elle est allouée sur le tas, porte son environnement capturé et est appelée une fois par élément par la boucle d'exécution de la VM.
Le total après la Session 013 : 338 tests réussis, la Phase 6 (Fonctions intégrées) à 64 %, et la VM capable d'exécuter de vrais programmes fonctionnels. Le langage n'était plus juste une calculatrice. C'était un langage.
Le pattern plus large
En rétrospective, la progression de la Session 010 à la 013 suit un pattern :
- Session 010 : Construire le moteur d'exécution (pile, flux de contrôle, arithmétique).
- Session 011 : Construire le système de mémoire (tas, GC, allocation).
- Session 013 : Construire la couche d'abstraction (fermetures, HOF, fonctions intégrées).
Chaque couche dépend de celle en dessous. Les fermetures ont besoin du tas (pour stocker les valeurs capturées). Le tas a besoin du GC (pour récupérer les fermetures mortes). Le GC a besoin du moteur d'exécution (pour trouver les racines sur la pile et dans les cadres d'appel).
Cette approche ascendante -- fondation d'abord, abstraction ensuite -- est la seule façon de construire une VM correctement. Si nous avions essayé d'implémenter les fermetures avant que le GC ne fonctionne, les valeurs capturées fuiraient. Si nous avions essayé d'implémenter le GC avant que le tas ne soit conçu, la phase de marquage ne saurait pas quoi traverser. Chaque session a construit exactement ce dont la session suivante avait besoin.
Le prochain article passe du runtime au frontend : comment la VM exécute les instructions de vues pour générer du HTML, lier les attributs de manière réactive et gérer les événements.
Ceci est la partie 23 de la série « Comment nous avons construit FLIN », documentant comment un CEO à Abidjan et un CTO IA ont construit un langage de programmation à partir de zéro.
Prochain : [24] Comment la VM exécute les vues -- le pont entre le bytecode et le DOM.