Machine Virtuelle

Catnip utilise une VM stack-based en Rust pour exécuter du bytecode sans buter sur la profondeur de pile Python.

Pourquoi une VM

La VM corrige trois limites de l'interprétation AST directe :

Stack overflow : supprime la limite de profondeur Python

• Récursion profonde possible (factorielle, fibonacci)
• Pas de RecursionError sur code tail-recursive

Performance : dispatch O(1) via pattern matching

• 2-15x plus rapide que l'interpréteur AST
• Bytecode compact et linéaire (cache-friendly)

Profilabilité : instrumentation et tracing intégrés

• Comptage d'opcodes pour hot detection
• Traces pour debugging
• Support JIT (voir JIT)

Architecture : Stack-based VM

Catnip utilise une stack machine plutôt qu'une register machine :

Stack-based :

LOAD_CONST 10    # Push 10
LOAD_CONST 20    # Push 20
ADD              # Pop 20, Pop 10, Push 30

Avantages :

• Bytecode compact (pas de registres à encoder)
• Simple à générer (compilation directe depuis AST)
• Simple à implémenter (une seule stack)

Trade-off : Plus d'instructions stack (push/pop) vs register-based, mais dispatch rapide compense

Références :

• Stack machine (Wikipedia)
• Virtual machine comparison (USENIX 2005)

NaN-boxing : Représentation Compacte

La VM utilise le NaN-boxing pour représenter toutes les valeurs sur 64 bits :

Principe : les floats IEEE-754 ont des patterns NaN inutilisés qu'on peut exploiter

[Sign:1][Exponent:11=0x7FF][Quiet:1][Tag:3][Payload:48]

Les floats sont stockés directement (pas dans un NaN pattern). Toutes les primitives tiennent dans 8 bytes sans allocation heap.

Avantages :

• Inline pour int/float/bool/None (pas d'allocation)
• Conversions zero-cost (reinterpret_cast)
• Cache-friendly (64 bits = 1 word)

Promotion automatique : quand un SmallInt overflow (48-bit), l'arithmétique promeut en BigInt (Arc<BigInt> via num-bigint). La demotion inverse se fait automatiquement si le résultat tient dans un SmallInt.

Struct round-trip : quand un TAG_STRUCT traverse la frontière Python (ex: stocké dans une list()), il est converti en CatnipStructProxy (PyObject) via to_pyobject(). Le proxy porte un native_instance_idx qui permet à from_pyobject() de restaurer le TAG_STRUCT natif si l'instance appartient au StructRegistry courant. Le pointeur thread-local du StructRegistry est sauvegardé/restauré dans PyRustVM::execute() pour gérer les appels VM réentrants (méthodes récursives sur structs dans des collections).

Références :

• LuaJIT's value representation
• JavaScriptCore NaN-boxing

Le NaN-boxing exploite le fait que les float s IEEE-754 ont 2^52 patterns NaN possibles mais n'en utilisent qu'un. On récupère les autres pour stocker des ints, des pointeurs, des bools. C'est du "parasitage" légal de bits.

Pipeline d'Exécution

Compilation : Op → Bytecode

Le compiler (catnip_rs/src/vm/compiler.rs) transforme les nœuds Op en instructions bytecode :

Génération :

• Traverse récursivement les Op nodes
• Génère les instructions (opcode + arg)
• Construit les tables (constants, names, varnames)

Optimisations :

• Slot allocation pour variables locales
• Constant pooling
• Jump optimization

Output : CodeObject avec bytecode linéaire

Struct optimizations :

• CallMethod (opcode 74) : fuse GetAttr + Call pour les appels de méthode sur structs. Encoding : (name_idx << 16) | nargs. Evite l'allocation de BoundCatnipMethod intermédiaire

Exécution : Bytecode → Result

L'executor (catnip_rs/src/vm/core.rs) exécute le bytecode via une boucle de dispatch :

Dispatch loop :

loop {
    let instr = frame.fetch_instruction();
    match instr.op {
        VMOpCode::LoadConst => { /* ... */ }
        VMOpCode::Add => { /* ... */ }
        // ...
    }
}

Frame : structure d'exécution

• Operand stack (valeurs NaN-boxed)
• Local variables (slots)
• Program counter (PC)

Frame pooling : réutilisation des frames pour éviter les allocations

Modes d'Exécution

VM mode (défaut) :

catnip script.cat              # Mode VM
catnip -x vm script.cat        # Explicite

AST mode (fallback) :

catnip -x ast script.cat       # Interprétation AST directe

Rôle du mode AST : implémentation de référence pour le développement de la VM. L'interpréteur AST existait avant la VM et exécute directement les nœuds Op via le Registry. Son intérêt est de fournir un oracle indépendant :

• Validation : tout test qui passe en AST et échoue en VM isole un bug de compilation ou de dispatch VM
• Debugging : pas de couche de compilation entre l'IR et l'exécution, le flux est plus lisible
• Régression : make test-all exécute la suite complète dans les deux modes, ce qui garantit l'équivalence sémantique

Le mode AST n'est pas destiné aux utilisateurs finaux. Il est plus lent (pas de NaN-boxing, dispatch indirect via Python) mais plus simple à raisonner.

Error Handling

La VM produit des messages d'erreur avec position source (fichier, ligne, colonne) et pile d'appels.

Principe : capture lazy - zéro overhead sur le chemin normal d'exécution.

Line table : le CodeObject contient une table parallèle aux instructions, chaque entrée mappe une instruction vers son start_byte. Le peephole optimizer maintient cette correspondance.

Call stack : la VM empile/dépile les frames d'appel avec nom de fonction et position source.

Capture : quand une erreur se produit, la VM consulte la line table et snapshote le call stack. Le bridge Python convertit le start_byte en ligne/colonne via SourceMap et enrichit l'exception avec un extrait.

Exemple de sortie :

File '<input>', line 2, column 14: division by zero
    2 | f = (x) => { x / 0 }
    |              ^
Traceback (most recent call last):
  File "<input>", in <lambda>
CatnipRuntimeError: division by zero

Références :

• CPython co_linetable -- même pattern de table parallèle aux instructions

La VM logge la position source de chaque instruction. En exécution normale: rien à signaler. En erreur: ciblage chirurgical.

Memory Guard

La VM vérifie périodiquement le RSS du processus pour empêcher un script de consommer toute la RAM.

Mécanisme : toutes les 65536 instructions (bitwise AND, coût négligeable), lecture de /proc/self/statm sur Linux (~5 µs par check). Sur les autres plateformes, le guard est inactif (no-op).

Limite par défaut : 2048 MB. Configurable via -o memory:SIZE (en MB), config TOML (memory_limit), ou variable d'environnement (CATNIP_OPTIMIZE=memory:SIZE). memory:0 désactive le guard.

Erreur : MemoryError avec message indiquant le RSS courant, la limite, et comment augmenter ou désactiver.

MemoryError: memory limit exceeded (2100 MB / 2048 MB)
Increase: catnip -o memory:4096
Disable:  catnip -o memory:0

Implémentation : catnip_rs/src/vm/memory.rs (lecture RSS), champs memory_limit_bytes et instruction_count dans la struct VM, variante MemoryLimitExceeded dans VMError (convertie en PyMemoryError).

Performances Typiques

Avec JIT : 50-200x vs AST pour boucles numériques intensives

Voir JIT pour détails sur compilation native.