Machine Virtuelle

Catnip utilise une VM stack-based implémentée en Rust pour exécution bytecode sans limites de profondeur.

Pourquoi une VM

La VM résout trois limitations de l'interprétation directe d'AST :

Stack overflow : Élimine les limites 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.md)

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 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

┌─────────────────────────────────────────────────┐
│ Float (normal)    │ s │  exp   │   mantissa     │
│ NaN (quiet)       │ 0 │ 11111  │ 1xxxxxxxxxxxxxx │
│ Pointer           │ 0 │ 11111  │ 10pppppppppppp  │ ← PyObject*
│ Int (small)       │ 0 │ 11111  │ 110iiiiiiiiiiii │ ← i32
│ Bool/None         │ 0 │ 11111  │ 111tttttttttttt │ ← type tag
└─────────────────────────────────────────────────┘

Avantages :

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

Trade-off : Int limité à i32 (-2^31 à 2^31-1), grands ints → PyObject

Références :

• NaN-boxing (blog post)
• LuaJIT's value representation
• JavaScriptCore NaN-boxing

NaN-boxing exploite le fait que les floats IEEE-754 ont 2^52 patterns NaN possibles mais en utilisent qu'un seul. On squatte les 2^52-1 autres pour stocker des ints, des pointeurs, des bools. C'est du parasitage de bits autorisé par la spec.

Pipeline d'Exécution

Op nodes (AST)
    ↓
VM Compiler (Rust)
    ↓
Bytecode (CodeObject)
    ↓
VM Executor (Rust)
    ↓
Result

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 instructions (opcode + arg)
• Construit tables (constants, names, varnames)

Optimisations :

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

Output : CodeObject avec bytecode linéaire

Exécution : Bytecode → Result

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

Dispatch loop :

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

Frame : Structure d'exécution

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

Frame pooling : Réutilisation des frames pour éviter 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

Utilité AST mode :

• Debugging (pas de compilation bytecode)
• Tests de régression
• Validation du pipeline

Performances Typiques

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

Voir JIT.md pour détails sur compilation native.