Machine virtuelle

Catnip exécute par défaut un bytecode dans une machine à pile Rust. Ce chemin évite que la profondeur des appels Catnip dépende de la pile Python, réduit le coût du dispatch et fournit les compteurs utilisés par le JIT et le debugger.

Pourquoi une machine à pile

Une instruction consomme ses opérandes au sommet de la pile et y dépose son résultat :

LOAD_CONST 10
LOAD_CONST 20
ADD

Cette représentation garde le bytecode compact et permet au compilateur de l'émettre directement depuis l'IR. Elle demande plus de mouvements de pile qu'une machine à registres ; Catnip accepte ce coût pour réduire le nombre de cas dans le compilateur et conserver une boucle de dispatch unique.

Le bytecode est compilé lors de la première exécution d'une IR préparée, puis réutilisé. Une exécution transporte :

• une pile d'opérandes ;
• des slots de variables locales ;
• un compteur d'instruction ;
• une pile de frames ;
• les gestionnaires d'exception et les positions source.

Références :

• Stack machine ;
• Virtual machine comparison (USEN 2005).

Représentation des valeurs

Les deux VM Rust transportent leurs valeurs dans un mot de 64 bits. Les flottants IEEE-754 ordinaires restent directement encodés ; les motifs NaN inutilisés servent à distinguer les entiers courts, booléens, nil, symboles, handles et valeurs allouées. Les entiers qui sortent de la plage inline sont promus en BigInt, puis redescendent quand le résultat tient de nouveau dans la plage courte.

La promotion se décide sur le calcul, jamais sur l'allure du résultat. Un décalage à gauche l'illustre : a << b sur l'entier machine tronque les bits sortis, et la valeur tronquée peut très bien retomber dans la plage courte — la retenir reviendrait à confondre « ça tient » et « rien n'a été perdu ». Le décalage n'est donc gardé sous forme courte que s'il est réversible ((a << b) >> b == a), sinon il passe par l'entier long. Le décalage à droite, lui, n'alloue rien : il sature au-delà de la largeur (0, ou -1 pour un négatif). Un compte négatif est un ValueError, pour l'entier court comme pour l'entier long.

catnip_rs, qui dialogue avec Python, et catnip_vm, qui reste en Rust pur, n'ont pas exactement la même table de tags. Le premier utilise notamment des handles vers une table d'objets Python ; le second représente ses collections, structures et closures par des valeurs natives. Une valeur brute ne doit donc jamais être interprétée avec le schéma de l'autre runtime.

Trois classes de tags

La frontière de valeur distingue trois classes :

from_raw_scalar(bits) n'accepte que les scalaires. Les retours de plugins non marqués et la restauration de bits externes passent par cette fonction : un mot fabriqué ne peut pas devenir un pointeur puis être déréférencé. La partition et cette frontière sont modélisées dans CatnipValueClassProof.v, CatnipBoundaryProof.v et CatnipPluginBoundaryProof.v ; voir Preuves Coq.

Un tag pointeur, c'est un pari sur l'allocateur d'en face. La frontière scalaire refuse de parier.

Le NaN-boxing masque les pointeurs au système de types Rust : un wrapper transparent autour de u64 peut être considéré Send + Sync alors que certains motifs désignent un objet qui ne l'est pas. Les chemins parallèles ne s'appuient donc pas sur cet auto-trait ; ils valident les classes admises, gèlent ou sérialisent les valeurs, et réinstallent les registres nécessaires dans le worker.

Identité des NaN Python

Un NaN n'est égal à rien, pas même à lui-même. Les collections Python compensent souvent par un test d'identité avant ==. Recréer un PyFloat à chaque traversée ferait donc perdre le comportement de in, index, count, des dictionnaires et des ensembles.

Un NaN reçu de Python conserve son objet dans l'ObjectTable. Les opérations génériques le voient comme un flottant, mais le JIT et les chemins spécialisés n'acceptent que les flottants inline. Un NaN produit par un calcul reste une valeur inline ; l'identité Python ne traverse pas une sérialisation ou une frontière de processus.

Le critère reste l'identité : deux objets float('nan') distincts restent distincts, deux références vers le même objet restent identiques.

Le seul flottant qui refuse de s'égaler à lui-même exige, en compensation, qu'on se souvienne de qui il est.

Propriété et durée de vie

Une valeur présente dans une pile, un slot, une constante, une closure, une collection ou une map globale possède sa référence. Copier une valeur allouée prend une nouvelle référence ; l'écraser, la dépiler sans transfert ou détruire son conteneur la rend. Les appels transfèrent leurs arguments vers la frame Catnip appelée ou les libèrent après conversion vers Python.

Ce contrat couvre aussi les sorties d'erreur. Une opérande déjà retirée de la pile doit être soit transférée, soit libérée avant de propager l'erreur. Les frames libèrent leur pile, leurs locals, leurs snapshots de blocs et leurs bindings de pattern, quel que soit le chemin de sortie.

Deux corollaires que la forme du code ne rappelle pas d'elle-même, et qui ont chacun produit des défauts :

• Lire une opérande ne la dé-possède pas. Un opcode qui ne fait que consulter sa valeur — tester sa vérité, la formater, comparer un slot à « non lié » — l'a quand même retirée de la pile, donc il la rend. Ces sites n'ont pas de variable de résultat à laquelle rattacher la libération, ce qui les fait ressembler à des lecteurs purs.
• Une fonction interne déclare si elle emprunte ou si elle consomme, et tous ses appelants suivent la même règle. Quand deux helpers voisins diffèrent sur ce point, l'écart ne se voit pas au type — les deux prennent une Value par copie — et un appelant qui libère ce que l'appelé a déjà consommé produit une double libération, pas une fuite.

Le test qui ferme ces deux cas ne mesure pas une absence de croissance mais un retour à la valeur de base : on garde un témoin Arc sur la valeur et on vérifie son compteur après exécution.

Les deux runtimes appliquent ce contrat par des mécanismes différents :

• catnip_vm emploie des Arc pour les collections, les structures et les closures runtime. Leur compteur fort porte la durée de vie ;
• catnip_rs combine des Arc, une ObjectTable pour Python et un registre d'instances de structures. Les proxies Python conservent l'identifiant du registre qui les a créés afin de rendre la référence au bon propriétaire.

Les types et constantes d'un CodeObject possèdent aussi leurs valeurs. Le clonage d'un code object prend les références correspondantes ; sa destruction les rend. Cette symétrie évite de faire dépendre la sûreté d'un ordre de teardown particulier.

Les classes PyO3 qui peuvent fermer un cycle avec le contexte participent au GC cyclique via __traverse__ et __clear__. Une traversée déduplique les objets Python partagés, tandis que la libération rend chaque handle possédé.

Compter une référence partagée deux fois revient à inventer un propriétaire qui n'existe pas ; le ramasse-miettes attend poliment ce fantôme.

Les compteurs de debug _rs._debug_live_counts() complètent les tests de croissance mémoire. Ils mesurent les allocations encore vivantes et servent à détecter une pente après warmup. Une RSS stable ne prouve pas l'absence de fuite, et un compteur d'allocations ne détecte pas à lui seul un refcount qui gonfle sur un slot unique : les tests emploient donc aussi des témoins de slots et des campagnes différentielles VM/AST.

Structures, fonctions et frontières

Les fonctions templates restent indexées dans une table, car leurs indices sont présents dans le bytecode. Les closures créées à l'exécution portent leur propre durée de vie et leurs captures. Une auto-référence est faible ; la frame active garde la référence forte nécessaire pendant l'appel. Les groupes de récursion mutuelle sont drainés au teardown afin de casser leurs cycles.

Les instances de structures ont leur propre drain. Un cycle entre elles (p.next = p, ou deux instances qui se pointent) est sûr mais qu'un compteur de références ne peut pas casser : le champ tient la référence qui garde le slot, et le slot tient le champ. Écrire une instance dans un champ est la seule mutation qui ferme un tel cycle, donc c'est là que le receveur est enregistré ; passé un seuil de participants, une suppression d'essai réclame les composants que plus rien n'atteint depuis l'extérieur, puis se réarme sur ce qui a survécu. La rétention est bornée, pas nulle : le dernier lot reste enregistré à la fin d'une exécution.

Seules les arêtes champ → instance sont parcourues. Un cycle refermé à travers une liste, un dictionnaire ou une capture de closure n'est pas réclamé — sous-approximation délibérée : une arête manquée gonfle le compteur, donc le composant paraît atteignable et est gardé.

Le registre porte aussi les liaisons de type en attente. Un callback déclare un type, le rapatriement le fond chez l'appelant — mais le NOM, lui, est lié dans les variables, et celles d'un worker meurent avec sa tâche : la même déclaration était donc joignable en mode séquentiel et introuvable en mode thread. Le rapatriement ne peut pas la lier lui-même, puisqu'il s'exécute sur le worker pendant que la VM appelante est suspendue, ses variables hors d'atteinte. Il note donc ce qu'il a fondu, et la VM lie les noms à son retour. Le mode d'exécution choisit où un callback tourne, jamais ce que le programme répond.

L'enregistrement des cycles appartient au registre, pas à la VM qui écrit. Un child VM de broadcast meurt à la fin de son callback, et une liste tenue là mourait avec lui : le composant n'était jamais proposé au drain, et la rétention croissait linéairement avec le nombre d'éléments. Le rapatriement des instances vers le parent transporte donc aussi les racines, et le drain n'est déclenché qu'une fois les comptes du child soldés — un composant réclamé plus tôt serait relâché deux fois.

Une structure native convertie vers Python devient un proxy. Le proxy possède une référence vers l'instance et peut être réimporté comme valeur native si son registre est encore accessible. Entre deux runtimes ou processus, l'identité du type est vérifiée par sa forme, pas par un index local ni par son seul nom.

Tant que son registre vit, le proxy est une vue sur son slot : lire ou écrire un champ à travers lui atteint l'instance. Il porte aussi une copie des valeurs de champs, mais celle-ci ne répond qu'une fois le registre disparu — c'est ce qui permet à une closure de survivre à sa session. Répondre depuis la copie pendant que le slot vit donnait deux vérités pour une instance : une fonction Python qui mutait l'argument reçu écrivait à côté, et une structure capturée par une closure devenait privée à cette closure, puisque la capture est convertie en proxy pour être portable.

Un proxy qui nomme un slot vivant de la lignée du registre courant est ramené à sa valeur native avant tout accès de champ ou dispatch de méthode. Ce qui entre depuis Python l'était déjà par la conversion ordinaire ; une capture, elle, ne traverse jamais cette frontière, et manquait donc le chemin natif — l'appel retombait sur un getattr Python, donc sur un child VM, là où un receveur natif s'exécute dans la VM courante. Un proxy que le registre courant ne peut pas résoudre est laissé intact : c'est une normalisation, jamais une matérialisation.

Chaque frontière a donc son mécanisme, et un seul. Côté VM, la normalisation : ce qui entre dans un opcode est ramené à sa forme native, donc les gardes (gel, capture ND en lecture seule) et les chemins rapides s'appliquent uniformément. Côté Python, la vue : __getattr__ et __setattr__ atteignent le slot, parce qu'aucune normalisation n'est possible quand c'est l'appelant qui est Python. La vue reste aussi le repli de la VM quand la normalisation échoue — registre disparu, ou proxy d'une autre lignée.

Les structures utilisées comme clés sont gelées au premier hash. Toute mutation ultérieure lève une erreur, ce qui préserve le contrat a == b ⇒ hash(a) == hash(b). Le runtime pur conserve un snapshot de forme et de champs dans ses clés ; le runtime PyO3 propage le drapeau de gel à travers le proxy.

Le broadcast exécute les callbacks sur des copies privées des structures. Une mutation dans le callback ne modifie pas l'élément source ; le résultat transporte la copie mutée quand l'opération le demande. Le chemin rapide map/filter exécute directement les fonctions Catnip dans la VM courante tout en gardant cette isolation. La copie d'élément est profonde (champs struct imbriqués compris) sur tous les chemins, child VM de repli inclus. Les structures capturées suivent la règle inverse : dans un broadcast régulier l'écriture traverse — le child de repli réinstalle ses slots mutés dans le parent au retour — et dans un callback ND elle est refusée. La sémantique complète est décrite dans Broadcasting.

Références sur la représentation :

• LuaJIT value representation ;
• JavaScriptCore NaN-boxing.

Pipeline d'exécution

Le compilateur unifié choisit le chemin Rust pur quand l'IR et ses constantes peuvent être représentées sans Python. Les constantes qui nécessitent Python, comme certaines formes décimales ou imaginaires, passent par le pont PyO3. Les deux chemins partagent l'émission, les pools, les règles de sauts et le peephole dans catnip_core.

Le produit de compilation contient :

• les instructions et leurs arguments ;
• les constantes et noms ;
• la carte des slots locaux ;
• les sous-fonctions ;
• une position source par instruction ;
• les descriptions de vérifications de types.

Le peephole peut supprimer du code mort et compacter les instructions. Il doit alors réadresser toutes les cibles, y compris celles encodées dans un argument composite. Les gestionnaires except et finally font partie du graphe de contrôle : une sortie break, continue ou return dépile exactement les handlers quittés.

Dispatch et hôte

La boucle de dispatch Rust lit une instruction, exécute son bras et avance ou modifie le compteur d'instruction. Les opérations qui dépendent de l'environnement sont abstraites par un hôte : résolution globale, interopération Python, itération, attributs, items et calcul ND. La VM principale utilise un contexte Python ; la PureVM fournit les mêmes services sans PyO3.

Cette séparation permet au compilateur, à l'arithmétique et à une large part du dispatch de rester dans catnip_core/catnip_vm, tout en conservant l'intégration Python dans catnip_rs.

Frames et appels

Les frames sont recyclées dans un pool borné. Un appel Catnip lie les paramètres dans les slots de la nouvelle frame ; les petits appels suivent un chemin sans allocation intermédiaire. Les appels terminaux remplacent la frame courante au lieu d'en empiler une nouvelle. Ce sont des proper tail calls : la cible peut être la fonction courante, une sœur mutuellement récursive ou une autre closure.

Le mode AST applique le même contrat par trampoline. La règle observable est donc commune aux deux exécuteurs : une chaîne d'appels terminaux Catnip utilise un espace de pile borné.

Scopes et closures

La résolution respecte les liaisons englobantes avant les variables de module, puis consulte l'hôte. Une closure capture les liaisons de fonction par valeur ; les variables de module restent résolues dans la map vivante. Les règles utilisateur sont détaillées dans Scopes et variables.

La VM garde des slots locaux rapides et une map de globals partagée avec l'hôte. Après un appel susceptible de réentrer dans le runtime, elle resynchronise les slots de module si la génération des globals a changé. Les noms introduits dans un bloc sont retirés à sa fermeture dans les deux vues ; une closure créée dans ce bloc conserve sa capture. Le critère utilisateur est précisé dans Portée des blocs.

Le scope englobant passe avant le module : un nom répond à la fonction qui l'a lié, pas à celle qui l'a nommé en premier.

Cette map possède ses valeurs, et une valeur du moteur pur n'a pas de destructeur propre : la laisser mourir avec la map ne libère rien. L'hôte la vide donc quand il disparaît, et pas seulement lorsqu'un pipeline est réinitialisé — sans quoi une ressource liée à un nom global, un fichier ouvert par exemple, survivait au programme qui l'avait ouverte. Seul le dernier porteur vide : le namespace d'un module partage la même map et libère ses entrées lui-même.

Récursion et durée de vie des closures

Une fonction ne capture pas le nom sous lequel elle se lie elle-même : elle l'atteint par une référence faible, résolue avant la capture. Capturer le slot en plus reviendrait à figer la valeur précédente de ce nom — une entrée que la résolution ne lit jamais, mais dont la référence forte maintiendrait en vie la déclaration précédente, puis celle d'avant, dès qu'une boucle redéclare deux fonctions sœurs.

Un groupe mutuellement récursif se lie en revanche par des références fortes : une référence faible ne survivrait pas à un appel terminal, qui réutilise la frame propriétaire des autres membres. Le groupe forme donc un cycle que le comptage de références ne peut pas défaire. La VM enregistre ses participants et les balaie périodiquement : elle découvre la composante joignable par captures, en soustrait les références internes, et ne coupe que si rien d'extérieur ne pointe dedans — une fabrique qui ne renvoie qu'un membre du groupe reste appelable, ses sœurs comprises. Un comptage incomplet ne peut que conserver un groupe de trop, jamais en libérer un qui vit encore ; ce que le balayage conserve est libéré à la fin de vie de la VM.

Le procédé est une suppression d'essai (trial deletion) : Bacon et Rajan, « Concurrent Cycle Collection in Reference Counted Systems », ECOOP 2001.

Le même balayage s'applique aux instances de structure, qui forment un cycle dès qu'un champ pointe vers son propre porteur (p.nxt = p) ou vers une instance qui le référence en retour. La VM enregistre l'instance recevant un champ de type instance — la seule écriture capable de refermer un cycle — et libère les composantes que rien n'atteint.

Ce balayage-là ne suit que les arêtes champ → instance. Une instance en atteint aussi une autre à travers une liste, un dictionnaire, une capture de closure ou l'espace de noms d'un module, et ces chemins ne sont pas parcourus : une arête non vue gonfle le compte de références, donc la composante paraît joignable et reste retenue. Un cycle refermé par un conteneur survit ainsi jusqu'à la fin de vie de la machine, comme avant.

Un cycle ne se dénonce pas lui-même : on le reconnaît à ce que personne d'autre ne le réclame.

Types aux frontières de fonctions

Une annotation de paramètre devient une vérification runtime au prologue de la fonction, dans les deux VM et dans l'exécuteur AST.

Un nom de type inconnu laisse l'annotation inerte. Un échec vérifiable lève toujours TypeError, y compris quand un BigInt ne peut pas être converti en flottant fini. Le retour d'un callback typé est vérifié par l'appelant.

Après le prologue, l'analyse peut donc exploiter le type garanti. Elle remplace certaines opérations polymorphes par des variantes entières ou flottantes ; le runtime garde un repli défensif vers l'opération générique. Les détails des réécritures sont dans Optimisations.

Paramètres par défaut

Un défaut constant est stocké dans le CodeObject. Un défaut qui dépend d'un paramètre précédent, d'une capture, d'un global ou d'un appel est compilé dans le prologue et réévalué à chaque appel :

next = (a, b = a + 1) => { b }

L'expression appartient à la surface de capture de la fonction, comme son corps. Une sentinelle interne distingue l'argument absent de nil, qui reste une valeur légitime.

Un paramètre par défaut ne connaît sa valeur qu'au moment où on ne la lui donne pas.

Exceptions et positions source

Les exceptions, return, break et continue empruntent le même mécanisme d'unwind. Une frame porte une pile de handlers, l'exception active et, pendant un finally, le signal qui reprendra ensuite. Les types d'exception gardent leur hiérarchie à travers les frontières Python afin qu'un except continue de matcher le type ou l'un de ses parents. Un raise nu conserve type, message et identité de l'exception active.

SystemExit devient un arrêt avec code ; l'interruption coopérative produit un signal non attrapable par le code Catnip. Les convertisseurs PyErr ↔ VMError sont centralisés pour ne pas aplatir un type ou ajouter plusieurs fois son préfixe au message.

Chaque instruction conserve un offset source. En cas d'échec, la VM capture cet offset et la pile d'appels, puis le frontend construit ligne, colonne et extrait. Le chemin normal ne construit pas de traceback.

Error: TypeError: 'int' object is not callable
  1 | x = 1; x()
    |        ^

Cette table parallèle suit le même principe que CPython co_linetable.

La VM conserve la position de chaque instruction. Tant que tout marche, cette comptabilité reste silencieuse.

Vérifications périodiques

La VM consulte périodiquement :

• un drapeau atomique d'interruption, utilisé notamment par le REPL ;
• une limite de mémoire basée sur la RSS sous Linux.

La limite mémoire vaut 2048 MiB par défaut. -o memory:SIZE la modifie et -o memory:0 la désactive. Sur les plateformes sans lecture de RSS compatible, ce garde est inactif.

Fonctions d'ordre supérieur dans la PureVM

map, filter, fold et reduce peuvent rappeler une closure utilisateur depuis le dispatch PureVM. Le dispatch réentrant garde une profondeur de base afin qu'un appel interne ne dépile jamais les frames de son appelant.

Une différence observable subsiste : dans le pipeline Python, map et filter suivent les builtins Python et rendent des itérateurs paresseux ; la PureVM, qui n'a pas de valeur d'itérateur suspendu, rend des listes. fold et reduce rendent un scalaire dans les deux pipelines.

F-strings et intrinsics

Les f-strings sont abaissées en une opération de formatage par interpolation puis une concaténation unique. Le formatage appelle le protocole __format__, y compris pour les conversions et les spécifications de format. Ce choix suit les opérations FORMAT_VALUE et BUILD_STRING de CPython.

typeof(expr) est reconnu par l'analyseur et devient une instruction dédiée. Les valeurs natives sont classées par leur tag ; les objets Python suivent la classification de l'hôte.

Modes d'exécution

Le mode VM est le défaut :

catnip script.cat
catnip -x vm script.cat

Le mode AST est un outil contributeur :

catnip -x ast script.cat

Il exécute directement les nœuds via le registre d'opérations, sans bytecode ni JIT. La suite tourne dans les deux modes ; une divergence localise un défaut de compilation ou de dispatch VM.

Les gains dépendent du programme et de la frontière mesurée. La page Benchmarking décrit le protocole de mesure ; JIT couvre la compilation native des chemins chauds.