Construire une machine virtuelle à pile en Rust

La VM est l'endroit où le code FLIN prend vie. Une pile, un compteur de programme et plus d'une centaine d'opcodes -- c'est toute la machine.

Le 2 janvier 2026, dans la Session 010, nous nous sommes assis pour construire la machine virtuelle qui exécuterait chaque programme FLIN jamais écrit. Pas un interpréteur qui parcourt un AST. Pas un transpileur qui génère du JavaScript. Une vraie machine virtuelle de bytecode, écrite en Rust, avec une pile d'opérandes dédiée, une pile d'appels, un tas et un ramasse-miettes. Le genre de chose sur laquelle des langages comme Lua, Python et Ruby sont construits -- sauf que la nôtre devait gérer les vues, les entités et la réactivité comme des préoccupations de première classe.

C'est l'histoire de comment nous avons conçu et implémenté cette VM en une seule session, produisant 2 850 lignes de code Rust et 32 nouveaux tests. C'est la fondation sur laquelle tout le reste de FLIN repose.

Pourquoi une machine à pile

Il existe deux architectures dominantes pour les machines virtuelles : basée sur les registres et basée sur la pile. La JVM et CPython utilisent une pile. La VM Lua (depuis la version 5.0) et Dalvik utilisent des registres. Chacune a ses compromis.

Nous avons choisi une machine à pile pour trois raisons.

Premièrement, la simplicité de la génération de code. Le compilateur de FLIN émet du bytecode à partir d'un AST. Avec une machine à pile, chaque expression devient une séquence postfixe : pousser les opérandes, appliquer l'opérateur. Il n'y a pas de passe d'allocation de registres, pas de coloration de graphe, pas de logique de débordement. Le générateur de code parcourt l'AST récursivement et émet les instructions en un seul passage. Cette simplicité était critique quand nous construisions l'ensemble de la chaîne d'outils -- lexer, parser, vérificateur de types, générateur de code et VM -- en quelques jours.

Deuxièmement, un bytecode compact. Les instructions de pile font typiquement un octet pour l'opcode plus zéro à deux octets pour les opérandes. Les instructions de registres doivent encoder les registres source et destination, rendant chaque instruction plus large. Pour FLIN, où le bytecode voyagerait éventuellement sur le réseau pour le rechargement à chaud de modules, plus petit est mieux.

Troisièmement, le précédent de CPython et de la JVM. Les deux sont des machines à pile. Les deux ont des décennies de preuves que les machines à pile peuvent être assez rapides pour les charges de travail du monde réel. Nous n'essayions pas de concurrencer le compilateur JIT de V8. Nous essayions de construire une VM correcte et maintenable dans le moins de lignes de code possible.

La représentation des valeurs

Avant que la VM puisse exécuter quoi que ce soit, elle doit savoir à quoi les valeurs ressemblent à l'exécution. C'est l'enum Value -- l'atome de l'ensemble du système :

rustpub enum Value {
    None,
    Bool(bool),
    Int(i64),
    Float(f64),
    Object(ObjectId),
}

Cinq variantes. C'est l'ensemble du système de types à l'exécution au niveau le plus bas. None est l'absence de valeur. Bool, Int et Float sont des valeurs immédiates -- elles vivent directement sur la pile sans allocation sur le tas. Object(ObjectId) est un handle vers quelque chose sur le tas : une chaîne, une liste, une map, une instance d'entité, une fonction, une fermeture ou un itérateur.

La décision de garder Int et Float comme variantes séparées (plutôt qu'un type Number unifié) était délibérée. FLIN a des types Int et Float distincts dans son système de types, et nous voulions que la VM préserve cette distinction. L'arithmétique entière est exacte. L'arithmétique flottante est IEEE 754. Les confondre signifierait que chaque opération entière paie le prix de la sémantique en virgule flottante.

Chaque objet alloué sur le tas porte un en-tête :

rustpub struct HeapObject {
    header: ObjectHeader,
    data: ObjectData,
}

pub struct ObjectHeader {
    type_tag: TypeTag,
    marked: bool,
    size: u32,
}

pub enum ObjectData {
    String(String),
    List(Vec<Value>),
    Map(HashMap<String, Value>),
    Entity(EntityInstance),
    Function(FunctionData),
    Closure(ClosureData),
    NativeFunction(NativeFunctionData),
    Iterator(IteratorData),
}

Le TypeTag discrimine les types d'objets. Le bit marked est pour le ramasse-miettes. Le champ size suit le nombre d'octets que cet objet occupe sur le tas, que le GC utilise pour décider quand déclencher une collecte.

Cette conception signifie que les opérations de pile sur les primitives (Int, Float, Bool, None) sont sans allocation. Ce n'est que quand le programme crée une chaîne, une liste, une map ou une entité que la VM touche le tas. Pour un programme compteur -- count = 0; count++ -- le tas n'est jamais touché.

La struct VM

Avec les valeurs définies, la VM elle-même est étonnamment petite :

rustpub struct VM {
    stack: Vec<Value>,              // Pile d'opérandes
    frames: Vec<CallFrame>,         // Pile d'appels
    ip: usize,                      // Pointeur d'instruction
    globals: HashMap<String, Value>,
    heap: Vec<HeapObject>,          // Stockage d'objets
    free_list: Vec<usize>,          // Recyclage GC
    bytes_allocated: usize,
    gc_threshold: usize,
    output: Vec<String>,            // Sortie d'impression
    debug: bool,
}

La pile d'opérandes contient les valeurs sur lesquelles les instructions opèrent. La pile d'appels contient des objets CallFrame qui suivent les appels de fonctions. Le pointeur d'instruction (ip) indexe dans le tableau de bytecode. Les globales sont stockées dans une table de hachage par nom. Le tas est un vecteur plat d'objets, avec une liste libre pour recycler les emplacements après le ramasse-miettes.

Le CallFrame est tout aussi compact :

rustpub struct CallFrame {
    return_ip: usize,
    base_pointer: usize,
    locals: Vec<Value>,
    function_name: String,
}

Quand la VM appelle une fonction, elle pousse un nouveau CallFrame avec l'adresse de retour (pour savoir où continuer après le retour de la fonction), un pointeur de base (pour le déroulement de la pile), un vecteur de variables locales et le nom de la fonction (pour les messages d'erreur et la sortie de débogage).

Deux limites strictes protègent le système : une profondeur de pile maximale de 65 536 valeurs et une profondeur d'appel maximale de 1 024 cadres. La limite de pile empêche les boucles infinies accidentelles de consommer toute la mémoire. La limite de profondeur d'appel empêche la récursion non bornée de faire exploser la pile d'appels. Les deux sont assez généreuses pour tout programme raisonnable et assez restrictives pour attraper les bogues tôt.

La boucle d'exécution

Le coeur de la VM est une boucle qui récupère, décode et exécute les instructions :

rustimpl VM {
    pub fn execute(&mut self, chunk: &Chunk) -> Result<Value, RuntimeError> {
        loop {
            let instruction = chunk.code[self.ip];

            match instruction {
                OpCode::Halt => {
                    return Ok(self.pop_or_none());
                }

                OpCode::LoadConst(idx) => {
                    let value = chunk.constants[idx as usize].to_value();
                    self.push(value);
                }

                OpCode::Add => {
                    let b = self.pop();
                    let a = self.pop();
                    self.push(a.add(&b)?);
                }

                OpCode::Jump(offset) => {
                    self.ip = offset as usize;
                    continue; // Sauter l'incrément de ip
                }

                OpCode::JumpIfFalse(offset) => {
                    let condition = self.pop();
                    if !condition.is_truthy() {
                        self.ip = offset as usize;
                        continue;
                    }
                }

                // ... 100+ opcodes supplémentaires
            }

            self.ip += 1;
        }
    }
}

Le pattern est le même pour chaque instruction : récupérer l'opcode au pointeur d'instruction courant, faire un match dessus, effectuer l'opération (impliquant généralement la pile), et avancer le pointeur d'instruction. Les instructions de saut définissent ip directement et font continue pour sauter l'incrément automatique.

C'est une boucle de distribution à threads directs. Dans les VM de production comme CPython, ce pattern est parfois remplacé par des tables de goto calculé pour une meilleure prédiction de branchement. Nous sommes restés avec match parce que le compilateur Rust l'optimise en une table de sauts quand le nombre de variantes est assez grand, et parce que la clarté comptait plus que d'extraire la dernière nanoseconde.

Un détail subtil : l'instruction continue après les instructions de saut. Sans elle, la VM incrémenterait ip après l'avoir défini à la cible du saut, atterrissant une instruction après où elle devrait être. C'est un bogue classique de VM, et le corriger produit des symptômes qui ne ressemblent en rien à la cause réelle -- des valeurs apparaissent sur la pile dans le mauvais ordre, des fonctions retournent à la mauvaise adresse, des conditionnels prennent la mauvaise branche. Nous l'avons attrapé en testant, mais cela nous a coûté trente minutes de débogage avant de le tracer à un continue manquant.

Opérations de pile en détail

La pile est le système nerveux de la VM. Chaque valeur produite par une expression y passe. Chaque argument de fonction, chaque valeur de retour, chaque résultat intermédiaire vit sur la pile exactement aussi longtemps qu'il le faut.

Les opérations de base sont trompeusement simples :

rustfn push(&mut self, value: Value) {
    if self.stack.len() >= MAX_STACK_SIZE {
        panic!("Stack overflow: exceeded {} values", MAX_STACK_SIZE);
    }
    self.stack.push(value);
}

fn pop(&mut self) -> Value {
    self.stack.pop().expect("Stack underflow")
}

fn peek(&self) -> &Value {
    self.stack.last().expect("Stack underflow")
}

Mais le bytecode nécessite plus que juste push et pop. Considérez l'instruction Dup, qui duplique le sommet de la pile. Elle existe parce que de nombreuses opérations ont besoin d'utiliser une valeur deux fois -- une fois pour une comparaison et une fois pour une affectation, par exemple. Sans Dup, le compilateur devrait émettre une instruction de chargement pour la même variable deux fois, ce qui est à la fois plus gros et plus lent.

Swap échange les deux valeurs du sommet. Over copie la deuxième valeur depuis le sommet vers le sommet. Dup2 duplique les deux valeurs du sommet. Ces instructions existent parce qu'elles éliminent les chargements redondants dans les patterns courants. Un simple a = a + 1 bénéficie de Dup pour éviter de recharger a après l'incrément.

La VM fournit aussi des instructions de chargement spécialisées pour les constantes courantes : LoadInt0, LoadInt1, LoadIntN1 et LoadSmallInt. Charger l'entier zéro est si courant (initialiser des compteurs, réinitialiser l'état, vérifier les collections vides) qu'il mérite une instruction d'un seul octet au lieu du LoadConst de trois octets suivi d'une recherche d'index.

Variables : locales et globales

FLIN a deux portées pour les variables : locale (dans une fonction) et globale (au niveau du module). La VM les gère différemment.

Les variables globales vivent dans une HashMap<String, Value>. Charger une globale signifie hacher le nom de la variable et le chercher. Stocker une globale signifie insérer dans la map. C'est O(1) amorti mais implique une allocation sur le tas pour la chaîne clé.

Les variables locales vivent dans le vecteur locals du CallFrame courant. Charger une locale signifie indexer dans ce vecteur par numéro d'emplacement. Stocker une locale signifie écrire dans cet emplacement. C'est O(1) sans allocation -- juste un index de tableau.

Le compilateur assigne à chaque variable locale un numéro d'emplacement au moment de la compilation. La première locale dans une fonction obtient l'emplacement 0, la deuxième l'emplacement 1, et ainsi de suite. Le numéro d'emplacement est encodé directement dans l'instruction :

LoadLocal 0    ; Charger la première variable locale
LoadLocal 1    ; Charger la deuxième variable locale
StoreLocal 2   ; Stocker dans la troisième variable locale

Pour les fonctions avec plus de 255 locales (rare, mais possible dans du code généré), la VM fournit LoadLocal16 et StoreLocal16 avec des indices d'emplacement de 16 bits.

Deux instructions spécialisées, IncrLocal et DecrLocal, incrémentent ou décrémentent une variable locale en place sans toucher la pile. Le pattern i = i + 1 est si courant dans les boucles qu'une instruction dédiée économise trois opérations de pile par itération.

Flux de contrôle

L'exécution conditionnelle et les boucles se réduisent à trois instructions de saut : Jump, JumpIfTrue et JumpIfFalse. Chacune prend une adresse cible comme opérande.

Jump est inconditionnel -- il définit le pointeur d'instruction et continue. JumpIfTrue et JumpIfFalse dépilent le sommet de la pile, testent sa véracité et sautent (ou non) selon le résultat.

La véracité dans FLIN suit des règles simples : false et None sont faux. Tout le reste -- y compris l'entier zéro, la chaîne vide et la liste vide -- est vrai. Cela diverge de Python (où zéro est faux) et de JavaScript (où la chaîne vide est fausse), mais s'aligne avec la philosophie de FLIN qu'une valeur existe ou n'existe pas. Zéro est un comptage valide. Une chaîne vide est une chaîne valide. Seule l'absence explicite de valeur (None) et le booléen explicite false sont faux.

Les appels de fonctions utilisent l'instruction Call, qui dépile l'appelé et pousse un nouveau CallFrame :

LoadGlobal "add"   ; Pousser la fonction sur la pile
LoadInt 3          ; Pousser le premier argument
LoadInt 5          ; Pousser le deuxième argument
Call 2             ; Appeler avec 2 arguments
; Le résultat est maintenant sur la pile

L'instruction Return dépile la valeur de retour, restaure le pointeur d'instruction depuis le CallFrame, tronque la pile au pointeur de base du cadre et pousse la valeur de retour. Le cadre de pile entier de la fonction disparaît en une opération.

Pour les sauts lointains (cibles au-delà de 65 535), l'instruction JumpFar utilise une adresse de 32 bits. En pratique, les programmes dépassent rarement 65K instructions, mais la VM y est préparée.

L'exemple du compteur : du source à l'exécution

Pour voir tout cela fonctionner ensemble, considérez le programme FLIN le plus simple :

flincount = 0
count++

Le compilateur émet ce bytecode :

LoadInt0           ; Pousser 0 sur la pile
StoreGlobal $count ; Dépiler 0, stocker comme globale "count"
LoadGlobal $count  ; Pousser la valeur courante de count (0)
Dup                ; Dupliquer : pile est [0, 0]
Incr               ; Incrémenter le sommet : pile est [0, 1]
StoreGlobal $count ; Dépiler 1, stocker comme globale "count"
LoadGlobal $count  ; Pousser la valeur courante de count (1)
Halt               ; Arrêter, retourner le sommet de pile (1)

Huit instructions. La VM les exécute en quelques microsecondes. À la fin, la variable globale count contient la valeur 1, et la VM retourne Value::Int(1).

Ce petit exemple exerce cinq des sous-systèmes de la VM : le pool de constantes (le nom $count), le stockage de variables globales, les opérations de pile (Dup), l'arithmétique (Incr) et la boucle d'exécution elle-même. Si l'un d'entre eux est cassé, l'exemple du compteur échoue. C'est pourquoi c'était le premier test d'intégration que nous avons écrit.

Implémentations stub : planifier pour l'avenir

La Session 010 a implémenté tous les opcodes de pile, arithmétique, comparaison, logique, variables, listes, maps, propriétés et flux de contrôle. Mais le jeu d'instructions de FLIN inclut aussi des opcodes pour les opérations d'entités, les opérations de vues, les opérations d'intent, les opérations temporelles et les fonctions intégrées.

Nous les avons tous stubés. Chaque opcode non implémenté retournait un RuntimeError::NotImplemented avec le nom de l'opcode. Cela signifiait que la VM pouvait charger et commencer à exécuter n'importe quel bytecode FLIN valide sans paniquer -- elle rapportait simplement quelle opération n'était pas encore disponible.

Ce n'était pas du code provisoire. C'était un contrat. Chaque stub déclarait l'effet de pile exact de son opcode (combien de valeurs il dépile, combien il pousse) même avant que l'implémentation n'existe. Quand nous sommes revenus pour implémenter les opérations d'entités dans la Session 011 et les opérations de vues dans les sessions suivantes, les signatures étaient déjà définies. Le compilateur avait émis ces opcodes depuis le début. Tout ce que nous avions à faire était de remplir les implémentations.

Ce que 2 850 lignes de Rust nous ont apporté

À la fin de la Session 010, la VM était complète à 56 %. La représentation des valeurs était faite. La boucle d'exécution de base était faite. Tous les opcodes de pile, arithmétique, comparaison, logique, variables, listes, maps et flux de contrôle étaient implémentés. Trente-deux nouveaux tests réussissaient, portant le total à 251.

Plus important encore, l'architecture était verrouillée. L'enum Value ne changerait pas. La struct VM grandirait (en ajoutant un magasin d'entités, une pile HOF, un tampon de vue), mais sa forme fondamentale -- une pile d'opérandes, une pile d'appels, un tas et un pointeur d'instruction -- était définie.

Quand vous construisez une machine virtuelle, vous construisez le rez-de-chaussée d'un gratte-ciel. Chaque autre fonctionnalité -- ramasse-miettes, fermetures, vues, réactivité, rechargement à chaud de modules -- repose sur cette fondation. Si la fondation est mauvaise, tout ce qui est au-dessus est mauvais. Si la fondation est solide, tout ce qui est au-dessus a une chance d'être correct.

La fondation était solide. Trente-deux tests le disaient. Et le compilateur Rust, qui avait vérifié chaque type, chaque emprunt et chaque durée de vie dans ces 2 850 lignes, était le trente-troisième.

Ceci est la partie 21 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 : [22] Gestion de la mémoire et ramasse-miettes -- comment nous avons construit un ramasse-miettes mark-and-sweep qui garde le tas de FLIN propre sans arrêter le monde.