L'AST est une carte. Le générateur de code la transforme en directions que la VM peut suivre, une instruction à la fois.
Lorsque le code source atteint le générateur de code, il a déjà survécu à trois épreuves. Le lexer l'a découpé en tokens. Le parser a assemblé ces tokens en un arbre. Le vérificateur de types a confirmé que l'arbre a du sens. Ce qui reste est la traduction finale : convertir cette représentation abstraite et hiérarchique en un flux plat d'instructions bytecode que la machine virtuelle FLIN peut exécuter.
C'est l'histoire de la Session 009 -- la session où FLIN a acquis la capacité de compiler. En environ trente minutes d'implémentation, nous avons construit un générateur de code qui parcourt l'AST, émet des opcodes, gère un pool de constantes et produit du bytecode pour chaque construction supportée par FLIN : variables, arithmétique, flux de contrôle, opérations sur les entités, rendu de vues, accès temporel et requêtes alimentées par l'IA. 1 700 lignes de Rust. 26 nouveaux tests. Et à la fin, une application compteur qui se compilait en 26 octets de bytecode.
L'architecture du générateur de code
Le générateur de code comporte trois couches : le Chunk (le conteneur de bytecode), l'Emitter (le moteur de parcours d'arbre) et la façade CodeGenerator (l'API publique). Chaque couche a une seule responsabilité.
Le Chunk est le format de sortie brut -- un tableau d'octets pour les instructions, un pool de constantes pour les valeurs et une table de lignes pour le débogage :
rustpub struct Chunk {
pub constants: Vec<Constant>,
pub code: Vec<u8>,
pub lines: Vec<u32>,
}
impl Chunk {
pub fn add_constant(&mut self, constant: Constant) -> u16 {
// Déduplication : si cette constante existe déjà, retourner son index
for (i, existing) in self.constants.iter().enumerate() {
if existing == &constant {
return i as u16;
}
}
let index = self.constants.len() as u16;
self.constants.push(constant);
index
}
pub fn write_opcode(&mut self, op: OpCode, line: u32) {
self.code.push(op as u8);
self.lines.push(line);
}
pub fn write_u16(&mut self, value: u16) {
self.code.push((value & 0xFF) as u8);
self.code.push((value >> 8) as u8);
}
}Deux décisions de conception dans cette structure méritent attention. Premièrement, la déduplication des constantes. Quand le générateur de code rencontre la chaîne "count" trois fois dans un programme, le pool de constantes la stocke une seule fois et retourne le même index à chaque fois. Cela maintient le bytecode compact -- ce qui est critique quand l'index du pool de constantes est encodé comme un opérande de deux octets. Deuxièmement, l'encodage little-endian pour les valeurs multi-octets. Chaque opérande u16 est stocké octet faible en premier, correspondant au format spécifié dans la spécification du bytecode et à l'ordre natif des octets de la plupart du matériel moderne.
L'Emitter est là où le vrai travail se fait. Il porte l'état de compilation :
rustpub struct Emitter {
chunk: Chunk,
locals: Vec<Local>,
scope_depth: usize,
loop_starts: Vec<usize>,
loop_exits: Vec<Vec<usize>>,
entities: HashMap<String, EntitySchema>,
globals: HashMap<String, u16>,
}Chaque champ sert un objectif précis. locals suit les variables dans la portée courante, associant des noms à des emplacements de pile. scope_depth indique à l'émetteur si une déclaration de variable doit produire une instruction StoreLocal ou StoreGlobal. loop_starts et loop_exits gèrent les cibles de saut pour les boucles for -- l'adresse de début pour continue et les adresses de sortie pour break, qui doivent être patchées après l'émission du corps de la boucle. entities stocke les schémas des entités déclarées pour que save et la construction d'entités sachent quels champs attendre. globals associe les noms de variables globales à leurs indices dans le pool de constantes.
L'API publique est délibérément simple :
rustpub struct CodeGenerator {
emitter: Emitter,
}
impl CodeGenerator {
pub fn generate(self, program: &Program) -> Result<Chunk, CodeGenError>;
pub fn generate_with_debug(self, program: &Program, name: &str)
-> Result<(Chunk, String), CodeGenError>;
}Deux méthodes. L'une compile et retourne du bytecode. L'autre compile, retourne du bytecode et retourne également une chaîne de désassemblage lisible par l'humain pour le débogage. C'est toute la surface publique.
Parcours de l'AST
La génération de code est un parcours en profondeur de l'arbre. Pour chaque noeud de l'AST, l'émetteur appelle la méthode emit_* appropriée, qui émet des opcodes et traite récursivement les noeuds enfants. La distribution est directe :
Pour les instructions, emit_stmt() fait un pattern-matching sur le type d'instruction :
VarDecl-- émettre l'expression d'initialisation, puisStoreGlobalouStoreLocalEntityDecl-- enregistrer le schéma dans la table des entités (aucun code d'exécution émis)Save-- émettre l'expression d'entité, puis l'opcodeSaveDelete-- émettre l'expression d'entité, puis l'opcodeDeleteIf-- émettre la condition, émettreJumpIfFalsevers la branche else, émettre la branche then, émettreJumpau-delà de la branche else, patcher les cibles de sautFor-- émettre l'itérable, configurer l'itérateur, émettre le corps de la boucle avecNextFor/EndForView-- déléguer au sous-système d'émission de vues
Pour les expressions, emit_expr() fait de même :
Integer(0)-- émettreLoadInt0(une instruction d'un seul octet, aucun opérande nécessaire)Integer(1)-- émettreLoadInt1Integer(n)où -128 <= n <= 127 -- émettreLoadSmallIntavec un opérande d'un octetInteger(n)sinon -- ajouter au pool de constantes, émettreLoadConstBinary { left, op, right }-- émettre left, émettre right, émettre l'opcode de l'opérateurPostfix { operand, Increment }-- charger, dupliquer, incrémenter, stockerAsk(query)-- charger la chaîne de requête, émettreAskTemporal { expr, time }-- émettre l'expression, émettreAtVersionouAtTime
Cette structure récursive signifie que des expressions arbitrairement complexes se compilent naturellement. a + b * c devient : émettre a, émettre b, émettre c, émettre Mul, émettre Add. La structure arborescente encode déjà la précédence des opérateurs -- le générateur de code n'a pas besoin d'y penser.
Le pool de constantes
Chaque valeur qui ne peut pas être encodée directement dans un opérande d'instruction va dans le pool de constantes : chaînes de caractères, grands entiers, nombres à virgule flottante, identifiants (utilisés comme clés pour la recherche de variables globales), noms d'entités et références de fonctions.
Le pool de constantes utilise un format étiqueté :
rustpub enum Constant {
Null,
Bool(bool),
Int(i64),
Float(f64),
String(String),
Identifier(String),
EntityName(String),
Function { arity: u8, address: u16, name_idx: u16 },
Time(i64),
Money { amount: i64, currency: u8 },
}La distinction entre String et Identifier est importante. Une constante String est une valeur de chaîne à l'exécution -- le résultat de "hello" dans le code source. Un Identifier est un nom utilisé pour la recherche de variables -- le count dans count = 0 ou LoadGlobal $count. Ils occupent le même pool de constantes, mais leurs rôles sémantiques diffèrent. La VM utilise les identifiants pour chercher les globales par nom ; elle utilise les chaînes comme valeurs de données poussées sur la pile.
La déduplication maintient le pool compact. Considérez un programme FLIN qui référence count à cinq endroits différents : une fois dans la déclaration, deux fois dans les gestionnaires d'événements, une fois dans une liaison de texte, une fois dans un conditionnel. Sans déduplication, le pool de constantes contiendrait cinq copies de l'identifiant "count". Avec la déduplication, il en contient une seule, et les cinq instructions référencent le même index.
L'index du pool de constantes est encodé en u16, donnant un maximum de 65 536 constantes par unité de compilation. Pour la plupart des applications FLIN -- qui sont des programmes mono-fichier orientés interface utilisateur -- c'est plus que suffisant.
Patching des sauts
Le flux de contrôle est l'endroit où la nature plate du bytecode entre en collision avec la nature hiérarchique de l'AST. Une instruction if a une branche then et une branche else optionnelle. Dans l'AST, ce sont des enfants imbriqués. Dans le bytecode, ce sont des régions d'un flux plat d'instructions connectées par des instructions de saut.
Le défi : quand l'émetteur rencontre une instruction if, il doit émettre une instruction JumpIfFalse qui saute vers la branche else. Mais il ne connaît pas encore l'adresse de la branche else -- il n'a pas encore émis la branche then.
La solution est le patching des sauts. L'émetteur écrit une adresse de substitution, enregistre l'offset où la substitution se trouve, émet la branche then, puis revient en arrière et écrase la substitution avec l'adresse correcte :
rustfn emit_if(&mut self, condition: &Expr, then_branch: &[Stmt],
else_branch: &Option<Vec<Stmt>>) -> Result<(), CodeGenError> {
// Émettre la condition
self.emit_expr(condition)?;
// Émettre JumpIfFalse avec substitution
let else_jump = self.emit_jump(OpCode::JumpIfFalse);
// Émettre la branche then
for stmt in then_branch {
self.emit_stmt(stmt)?;
}
if let Some(else_stmts) = else_branch {
// Sauter au-delà du else (depuis la fin de la branche then)
let end_jump = self.emit_jump(OpCode::Jump);
// Patcher le else_jump pour pointer ici
self.patch_jump(else_jump);
// Émettre la branche else
for stmt in else_stmts {
self.emit_stmt(stmt)?;
}
// Patcher le end_jump pour pointer ici
self.patch_jump(end_jump);
} else {
self.patch_jump(else_jump);
}
Ok(())
}La méthode emit_jump écrit l'opcode et une substitution de deux octets (0x0000), puis retourne l'offset de la substitution. La méthode patch_jump calcule la distance de la substitution à la position courante du code et la réécrit en utilisant Chunk::patch_u16. Ce pattern est utilisé pour chaque conditionnel et boucle du langage.
Pour les boucles, le patching fonctionne dans les deux directions. Le début de la boucle enregistre une adresse loop_start pour les sauts arrière (l'itération de la boucle). Le vecteur loop_exits collecte tous les offsets de sauts avant qui doivent être patchés quand la boucle se termine -- les instructions break, la condition de terminaison de la boucle et l'instruction EndFor.
Génération de code pour les vues
Le système de vues de FLIN compile des modèles de type HTML en bytecode. C'est l'un des aspects les plus distinctifs du générateur de code -- la plupart des compilateurs de langage n'ont pas besoin de gérer la création d'éléments DOM comme une opération de première classe.
L'émission de vues suit la structure d'imbrication du modèle. Pour un simple compteur :
flincount = 0
<button click={count++}>{count}</button>Le générateur de code produit :
0000: LoadInt0 ; push 0
0001: StoreGlobal $count ; count = 0
0004: CreateElement $button ; <button>
0007: CreateHandler $click ; début du gestionnaire click
000A: LoadGlobal $count ; charger count
000D: Dup ; dupliquer pour postfixe
000E: Incr ; incrémenter
000F: StoreGlobal $count ; stocker
0012: TriggerUpdate ; notifier le système de réactivité
0013: EndHandler ; fin du gestionnaire click
0014: BindHandler ; attacher le gestionnaire à l'élément
0015: LoadGlobal $count ; charger count pour l'affichage
0018: BindText ; lier comme texte réactif
0019: CloseElement ; </button>
001A: Halt ; finPlusieurs détails méritent attention. CreateElement pousse un élément sur la pile d'éléments de la VM. CloseElement le dépile. Tout ce qui est émis entre les deux -- gestionnaires, liaisons de texte, attributs -- s'attache à l'élément courant. Cette approche basée sur la pile reflète l'imbrication du HTML sans nécessiter que le format de bytecode soit hiérarchique.
Les gestionnaires d'événements sont délimités par des paires CreateHandler/EndHandler. Les instructions entre eux ne sont pas exécutées immédiatement -- elles forment une fermeture que la VM stocke et invoque quand l'événement se déclenche. TriggerUpdate à l'intérieur du gestionnaire indique au système de réactivité que l'interface utilisateur doit se re-rendre après la fin du gestionnaire.
BindText crée une liaison réactive. Quand la VM rencontre BindText, elle ne se contente pas de définir le contenu textuel une fois -- elle enregistre la dépendance de sorte que quand count change (via TriggerUpdate), le texte est automatiquement mis à jour. C'est l'implémentation au niveau bytecode du modèle de réactivité de FLIN : le générateur de code émet le graphe de dépendances, et la VM le maintient à l'exécution.
Les conditionnels et boucles de vues utilisent des mécaniques de patching de sauts similaires aux instructions de flux de contrôle, mais avec des opcodes spécifiques aux vues : StartIf/EndIf pour le rendu conditionnel et StartFor/NextFor/EndFor pour le rendu de listes.
Émission optimisée des littéraux
Les petites optimisations dans la génération de code se composent à travers un programme entier. L'optimisation la plus impactante dans l'émetteur est les instructions spécialisées pour les littéraux.
Charger l'entier 0 pourrait se faire avec LoadConst -- ajouter 0 au pool de constantes et émettre une instruction de trois octets. Mais 0 est de loin le littéral entier le plus courant dans tout programme (initialisation, comparaisons, compteurs de boucle). Donc le jeu d'instructions fournit LoadInt0, une instruction d'un seul octet sans opérande. Idem pour LoadInt1 et LoadIntN1.
Pour les entiers dans la plage -128 à 127, LoadSmallInt utilise un opérande signé d'un octet au lieu d'une référence au pool de constantes. Cela couvre les bornes de boucle, les indices de tableau et la plupart des opérations de compteur.
L'émetteur applique ces optimisations de manière transparente :
rustfn emit_literal(&mut self, value: &Expr, line: u32) -> Result<(), CodeGenError> {
match value {
Expr::Integer(0) => {
self.chunk.write_opcode(OpCode::LoadInt0, line);
}
Expr::Integer(1) => {
self.chunk.write_opcode(OpCode::LoadInt1, line);
}
Expr::Integer(-1) => {
self.chunk.write_opcode(OpCode::LoadIntN1, line);
}
Expr::Integer(n) if *n >= -128 && *n <= 127 => {
self.chunk.write_opcode(OpCode::LoadSmallInt, line);
self.chunk.code.push(*n as u8);
}
Expr::Integer(n) => {
let idx = self.chunk.add_constant(Constant::Int(*n));
self.chunk.write_opcode(OpCode::LoadConst, line);
self.chunk.write_u16(idx);
}
Expr::Bool(true) => {
self.chunk.write_opcode(OpCode::LoadTrue, line);
}
Expr::Bool(false) => {
self.chunk.write_opcode(OpCode::LoadFalse, line);
}
Expr::None => {
self.chunk.write_opcode(OpCode::LoadNone, line);
}
// ...
}
Ok(())
}Les booléens et none reçoivent le même traitement. LoadTrue, LoadFalse et LoadNone sont des instructions d'un seul octet. Pas d'entrée dans le pool de constantes, pas de décodage d'opérande à l'exécution. Ces optimisations sont invisibles pour le programmeur mais réduisent la taille du bytecode de 20 à 30 % dans les programmes typiques.
Évaluation en court-circuit
Les opérateurs booléens nécessitent un traitement spécial. Dans la plupart des langages, a && b n'évalue pas b si a est faux. De même, a || b n'évalue pas b si a est vrai. Ce n'est pas juste une optimisation -- c'est une garantie sémantique. Du code comme user != none && user.name == "Juste" repose sur l'évaluation en court-circuit pour éviter une erreur de pointeur nul.
L'émetteur implémente l'évaluation en court-circuit en utilisant des sauts conditionnels :
Pour && : émettre a, émettre JumpIfFalse au-delà de l'évaluation de b, émettre b, émettre And. Si a est faux, le saut ignore b entièrement et la valeur fausse reste sur la pile.
Pour || : émettre a, émettre JumpIfTrue au-delà de l'évaluation de b, émettre b, émettre Or. Si a est vrai, le saut ignore b entièrement et la valeur vraie reste sur la pile.
C'est l'un des cas où le générateur de code doit raisonner sur la sémantique d'évaluation, pas juste sur la traduction mécanique. Une implémentation naïve qui émettrait toujours les deux opérandes produirait des programmes incorrects.
Détection des méthodes d'entité
Les entités FLIN ont des méthodes intégrées : .all, .find(id), .where(condition), .first, .count, .order(field). Celles-ci ressemblent à des appels de méthode ordinaires dans le code source, mais se compilent en opcodes spécialisés que la VM mappe directement aux opérations FlinDB.
L'émetteur détecte les appels de méthode d'entité en vérifiant si l'appelé est un nom d'entité connu avec une méthode reconnue :
Pour User.all, il émet QueryAll avec l'index du type d'entité. Pour User.find(id), il émet l'expression id suivie de QueryFind. Pour User.where(active == true), il émet le prédicat suivi de QueryWhere.
Cette détection se fait au moment de la génération de code, pas à l'exécution. La VM n'a pas besoin de distribuer les appels de méthode dynamiquement -- elle reçoit un opcode de requête spécifique et exécute l'opération FlinDB correspondante directement.
Le désassembleur
Le générateur de code inclut un désassembleur qui produit une sortie lisible par l'humain à partir du bytecode. Ce n'était pas une réflexion après coup -- il a été construit en parallèle avec l'émetteur et utilisé pour vérifier chaque test :
== counter ==
Constants:
[0000] 0
[0001] $count
[0002] $button
[0003] $click
Code:
0000 1 LoadInt0
0001 | StoreGlobal 0001 ; $count
0004 | CreateElement 0002 ; $button
0007 | CreateHandler 0003 ; $click
...Le désassembleur résout les références au pool de constantes en ligne (les commentaires ; $count), affiche les offsets de bytecode en hexadécimal et utilise | pour indiquer les instructions sur la même ligne source que l'instruction précédente. Ce format de sortie est devenu l'outil principal de débogage pour l'ensemble du compilateur -- quand un test échoue, le désassemblage montre immédiatement si le mauvais opcode a été émis, si la mauvaise constante a été référencée ou si la mauvaise cible de saut a été patchée.
26 tests, zéro surprise
La Session 009 a ajouté 26 nouveaux tests, portant le total à 219. Les tests couvraient trois couches :
Les tests de définition de bytecode vérifiaient que les opcodes font un aller-retour correct (écrire un octet, le relire, obtenir le même opcode), que les tailles d'opérande correspondent à la spécification, que les étiquettes de constantes sont uniques et que la structure de données Chunk gère correctement le patching.
Les tests d'émetteur vérifiaient les patterns de compilation individuels : littéraux entiers, déclarations de variables, addition binaire, littéraux de chaîne, littéraux booléens, listes, l'exemple du compteur, branchement if-else, instructions save/delete, construction d'entité, expressions ask, négation unaire et comparaisons.
Les tests d'intégration compilaient des programmes complets à travers la façade CodeGenerator et vérifiaient la sortie par rapport aux séquences de bytecode attendues.
Le test de l'exemple compteur était le couronnement -- un programme FLIN complet qui exerce la déclaration de variable, la création d'élément de vue, la gestion d'événement, l'incrément postfixe, la liaison de texte réactif et l'instruction Halt. Quand ce test a réussi, nous savions que le générateur de code pouvait gérer de vrais programmes.
Ce que cette phase a prouvé
Construire un générateur de code en une seule session -- environ 30 minutes de temps réel -- semble invraisemblable jusqu'à ce que l'on considère la préparation. L'AST était propre et bien typé. La spécification du bytecode (PRD 08) définissait chaque opcode, chaque format d'opérande et chaque comportement d'instruction avant qu'une seule ligne de codegen ne soit écrite. Le vérificateur de types avait déjà validé que chaque expression avait un type connu.
Le générateur de code n'avait pas besoin de prendre des décisions. Il traduisait. Chaque noeud de l'AST avait exactement une séquence de bytecode correcte. Chaque opcode avait exactement un encodage. La spécification a fait la réflexion ; l'implémentation a juste suivi la carte.
C'est le retour sur investissement du développement piloté par la spécification. Quand vous investissez du temps à écrire une spécification de bytecode précise et une définition d'AST précise, le générateur de code s'écrit tout seul. Les alternatives -- découvrir le format de bytecode pendant l'implémentation, ou concevoir l'AST et le codegen simultanément -- produisent du code fonctionnel à terme, mais au prix de faux départs, de reconceptions et de bogues subtils liés aux incompatibilités d'impédance entre l'arbre et les instructions.
Ceci est la partie 16 de la série « Comment nous avons construit FLIN », documentant comment un CEO à Abidjan et un CTO IA ont construit un compilateur de langage de programmation en sessions mesurées en minutes, pas en mois.
Prochain dans la série : Le format de bytecode lui-même -- le binaire .flinc, les octets magiques, l'encodage des instructions et les décisions de conception qui rendent le bytecode de FLIN à la fois compact et débogable.