Au lieu de parcourir l'arbre à chaque fois, on le traduit une fois en instructions simples exécutées par une petite machine.
⏱️ Durée : environ 100 minutes · 🎓 Niveau : intermédiaire · 🏅 Badge : Pilote de VM
🎬 L'histoire
La boucle de HashScript qui additionne 1 à 100 000 prend plusieurs secondes. Sam profile : le parcours de l'arbre, avec ses isinstance en cascade, est le goulot.
« Python, Java et Lua ne parcourent pas l'arbre, dit-il. Ils le traduisent d'abord en bytecode, une suite d'instructions très simples, qu'une machine virtuelle exécute en boucle. C'est plus rapide, plus compact, et ça ouvre la porte aux optimisations. »
Tu compiles HashScript vers un bytecode à pile et tu écris sa machine virtuelle.
🎯 Ta mission
À la fin, je serai capable de :
- expliquer ce qu'est un bytecode et une machine virtuelle à pile
- compiler expressions et instructions vers du bytecode
- gérer les sauts conditionnels et les boucles (étiquettes, remplissage a posteriori)
- écrire une VM et un désassembleur
- mesurer le gain par rapport à l'interpréteur d'arbre
🧩 Défi d'échauffement (5 XP)
Tu veux calculer (2 + 3) * 4 avec une calculatrice à pile (notation polonaise inverse) : tu tapes 2, 3, +, 4, ×. Écris la suite de touches. Ensuite : comment traduirais-tu si a < b alors ... sinon ... avec seulement des instructions simples du type « va à la ligne N » et « va à la ligne N si le dernier résultat est faux » ?
💡 Le concept
Du parcours d'arbre au bytecode
Un interpréteur d'arbre repasse sur la même structure à chaque exécution. Un compilateur vers bytecode la parcourt une seule fois et produit une liste plate d'instructions simples, qu'une machine virtuelle (VM) exécute dans une boucle serrée.
flowchart LR
A["AST"] --> B["Compilateur"]
B --> C["Bytecode<br/>(liste d'instructions)"]
C --> D["VM<br/>(boucle fetch-decode-execute)"]
Description du schéma : l'AST est traduit par le compilateur en bytecode, qui est exécuté par la VM. C'est la même boucle fetch-decode-execute que celle d'un processeur (HEF-040), en logiciel.
La machine à pile
La VM dispose d'une pile d'opérandes et d'un compteur de programme (PC). Les instructions travaillent sur la pile :
| Instruction | Effet |
|---|---|
PUSH v | empile la valeur v |
LOAD x | empile la valeur de la variable x |
STORE x | dépile et range dans la variable x |
ADD, SUB, MUL, DIV | dépile deux valeurs, empile le résultat |
LT, GT, LE, GE, EQ, NE | comparaisons (empile un booléen) |
2 + 3 * 4 se compile en : PUSH 2, PUSH 3, PUSH 4, MUL, ADD. L'ordre post-fixé vient directement du parcours de l'arbre « fils gauche, fils droit, puis le nœud ».
Compiler les instructions de contrôle
si c { A } sinon { B } tantque c { C }
<c> début : <c>
JZ vers_sinon JZ vers_fin
<A> <C>
JMP vers_fin JMP début
vers_sinon: <B> vers_fin: ...
vers_fin: ...
Problème : on ne connaît pas l'adresse de vers_fin quand on émet le saut. Solution : remplissage a posteriori (backpatching) : on émet JZ ?, on garde son indice, et on le complète une fois la cible connue.
La VM
def executer_vm(code):
pile, variables, sortie, pc = [], {}, [], 0
while True:
op, *arg = code[pc]
pc += 1
if op == "PUSH": pile.append(arg[0])
elif op == "LOAD": pile.append(variables[arg[0]])
elif op == "STORE": variables[arg[0]] = pile.pop()
elif op in OPS_BIN:
b = pile.pop(); a = pile.pop()
pile.append(OPS_BIN[op](a, b))
elif op == "JMP": pc = arg[0]
elif op == "JZ":
if not pile.pop(): pc = arg[0]
elif op == "PRINT": sortie.append(formater(pile.pop()))
elif op == "HALT": return sortie
Pourquoi c'est plus rapide ?
- plus de
isinstanceen cascade : un simple dispatch sur un code d'opération ; - structures plates, bonne localité de cache (HEF-040) ;
- le bytecode peut être optimisé (pliage, suppression des instructions inutiles) et sérialisé (fichiers
.pyc) ; - on peut aller plus loin : compilation JIT vers du code machine.
Voir le bytecode de Python
import dis
def somme(n):
s = 0
i = 1
while i <= n:
s = s + i
i = i + 1
return s
dis.dis(somme)
On y retrouve LOAD_FAST, STORE_FAST, BINARY_OP, COMPARE_OP, POP_JUMP_IF_FALSE, JUMP_BACKWARD: la même famille d'instructions que notre mini VM.
Limites de notre version
Variables globales dans un seul dictionnaire (pas de portées de blocs), pas de fonctions. Les VM réelles ajoutent des cadres d'appel (une pile d'appels), des variables locales indexées, des objets et un ramasse-miettes.
🔍 Exemple pas à pas
Problème : compiler HashScript vers du bytecode, l'exécuter, le désassembler et mesurer le gain.
import operator, time
from hashscript import parser, executer, Let, Assign, Print, Si, TantQue, Num, Bool, Var, Bin, Neg
NOMS_BIN = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV", "<": "LT", ">": "GT", "<=": "LE", ">=": "GE", "==": "EQ", "!=": "NE"}
OPS_BIN = {"ADD": operator.add, "SUB": operator.sub, "MUL": operator.mul, "DIV": operator.truediv,
"LT": operator.lt, "GT": operator.gt, "LE": operator.le, "GE": operator.ge, "EQ": operator.eq, "NE": operator.ne}
class Compilateur:
def __init__(self):
self.code = []
def emettre(self, *instruction):
self.code.append(tuple(instruction))
return len(self.code) - 1
def ():
(n, (Num, Bool)): .emettre(, n.valeur)
(n, Var): .emettre(, n.nom)
(n, Neg): .expr(n.expr); .emettre()
(n, Bin):
.expr(n.gauche); .expr(n.droite); .emettre(NOMS_BIN[n.op])
: NotImplementedError((n).__name__)
():
(n, (Let, Assign)):
.expr(n.expr); .emettre(, n.nom)
(n, Print):
.expr(n.expr); .emettre()
(n, Si):
.expr(n.cond)
saut_faux = .emettre(, )
i n.alors: .instr(i)
n.sinon:
saut_fin = .emettre(, )
.code[saut_faux] = (, (.code))
i n.sinon: .instr(i)
.code[saut_fin] = (, (.code))
:
.code[saut_faux] = (, (.code))
(n, TantQue):
debut = (.code)
.expr(n.cond)
sortie = .emettre(, )
i n.corps: .instr(i)
.emettre(, debut)
.code[sortie] = (, (.code))
:
.expr(n); .emettre()
():
i programme: .instr(i)
.emettre()
.code
():
v :
v :
(v, ) v == (v): ((v))
(v)
():
pile, variables, sortie, pc = [], {}, [],
:
op, *arg = code[pc]
pc +=
op == : pile.append(arg[])
op == : pile.append(variables[arg[]])
op == : variables[arg[]] = pile.pop()
op OPS_BIN:
b = pile.pop(); a = pile.pop()
pile.append(OPS_BIN[op](a, b))
op == : pile.append(-pile.pop())
op == : pc = arg[]
op == :
pile.pop(): pc = arg[]
op == : sortie.append(formater(pile.pop()))
op == : pile.pop()
op == : sortie
():
.join( i, instr (code))
():
Compilateur().compiler(parser(source))
source =
code = compiler_source(source)
(desassembler(code))
executer_vm(code) == executer(source) == []
long =
code_long = compiler_source(long)
t = time.perf_counter(); r1 = executer(long); t_arbre = time.perf_counter() - t
t = time.perf_counter(); r2 = executer_vm(code_long); t_vm = time.perf_counter() - t
r1 == r2
()
Extrait du désassemblage :
0 PUSH 1
1 STORE i
2 PUSH 0
3 STORE s
4 LOAD i ← début de la boucle
5 PUSH 5
6 LE
7 JZ 17 ← sortie de la boucle
...
16 JMP 4 ← retour au test
17 LOAD s
18 PRINT
19 HALT
Lecture : la boucle devient un JMP en arrière et un JZ en avant ; le résultat est identique à celui de l'interpréteur d'arbre, mais la VM évite le parcours récursif et les isinstance à chaque nœud.
✍️ À toi, avec aide (10 XP)
Compile à la main (puis vérifie avec le compilateur) :
let x = 3;
if x > 2 { print 1; } else { print 2; }
- Écris le bytecode attendu avec les numéros d'instruction et les cibles de saut.
- Exécute-le sur la VM et trace l'état de la pile à chaque instruction pour le début du programme.
💡 Indice 1
let x = 3; → PUSH 3, STORE x.
💡 Indice 2
La condition x > 2 → LOAD x, PUSH 2, GT, puis JZ vers_sinon.
💡 Indice 3
Le bloc alors se termine par JMP vers_fin pour ne pas exécuter le sinon.
✅ Réponse
0 PUSH 3
1 STORE x
2 LOAD x
3 PUSH 2
4 GT
5 JZ 9 # si faux : aller au bloc sinon
6 PUSH 1
7 PRINT
8 JMP 11 # fin du alors : sauter le sinon
9 PUSH 2
10 PRINT
11 HALT
# (Compilateur et VM de l'exemple)
code = compiler_source("let x = 3; if x > 2 { print 1; } else { print 2; }")
print(desassembler(code))
assert executer_vm(code) == ["1"]
Pile pendant les premières instructions : [] → [3] (PUSH 3) → [] (STORE x) → [3] (LOAD x) → [3, 2] (PUSH 2) → [True] (GT) → [] (JZ : la condition est vraie, pas de saut).
🚀 À toi, en solo (20 XP)
Optimiseur de bytecode (peephole). Écris optimiser(code) qui supprime les calculs constants sur du code sans saut :
PUSH a; PUSH b; ADD→PUSH (a+b)(idem SUB, MUL, et DIV sib ≠ 0, comparaisons) ;PUSH a; NEG→PUSH -a;- répète jusqu'à ce que plus rien ne change.
Pour un programme qui contient des sauts, ne touche à rien (les adresses cibles seraient décalées). Vérifie sur 200 programmes d'expressions aléatoires (print d'une expression avec nombres seulement) que la sortie est identique et que le code est plus court.
✅ Pistes de correction
# (Compilateur, VM et OPS_BIN de l'exemple)
import random
def optimiser(code):
if any(instr[0] in ("JMP", "JZ") for instr in code):
return list(code) # on ne modifie pas un code avec sauts
code = list(code)
changement = True
while changement:
changement, i, nouveau = False, 0, []
while i < len(code):
if i + 2 < len(code) and code[i][0] == "PUSH" and code[i + 1][0] == "PUSH" and code[i + 2][0] in OPS_BIN:
a, b, op = code[i][1], code[i + 1][1], code[i + 2][0]
if not (op == "DIV" and b == 0):
nouveau.append((, OPS_BIN[op](a, b)))
i +=
changement =
i + < (code) code[i][] == code[i + ][] == :
nouveau.append((, -code[i][]))
i +=
changement =
nouveau.append(code[i])
i +=
code = nouveau
code
():
profondeur == rng.random() < :
(rng.randint(, ))
op = rng.choice([, , ])
rng = random.Random()
gagne =
_ ():
source =
code = compiler_source(source)
opt = optimiser(code)
executer_vm(opt) == executer_vm(code), source
gagne += (code) - (opt)
(, gagne)
code = compiler_source()
optimiser(code) == code
(desassembler(optimiser(compiler_source())))
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Oublier le remplissage des sauts | Les JZ pointent sur None | Mémoriser l'indice du saut puis le compléter |
| Pile déséquilibrée | Résidus sur la pile ou dépilage d'une pile vide | Chaque expression pousse exactement une valeur ; une instruction expression la dépile (POP) |
| Optimiser du code avec des sauts | Les adresses de saut deviennent fausses | Recalculer les cibles ou limiter l'optimisation aux blocs sans saut |
| Comparer des vitesses sans vérifier l'égalité des résultats | Un VM rapide mais faux ne vaut rien | assert d'équivalence avant de mesurer |
🐉 Mini-boss (40 XP)
Transpileur HashScript → Python. Au lieu d'un bytecode, génère du code source Python à partir de l'AST (pour le sous-ensemble sans fonctions), puis exécute-le avec exec.
- Écris
vers_python(programme): variables → variables Python,print→ ajout à une liste de sortie (en respectant le format de HashScript),si/tantque→if/whileavec indentation correcte. - Les erreurs de division par zéro doivent être converties en
ErreurLangage(indice : une fonction auxiliairediv(a, b)générée dans le code). - Vérifie sur 20 programmes que l'interpréteur d'arbre, la VM et le transpileur donnent les mêmes sorties.
- Mesure les trois sur une boucle de 100 000 itérations et classe-les.
- Explique en 5 lignes quand préférer chaque approche (arbre, VM, transpilation).
✅ Pistes de correction
Un bon travail : une fonction récursive qui génère des lignes avec un niveau d'indentation (" " * niveau), let/Assign → nom = expression, Si → if cond: + bloc (avec pass si vide) + else:, TantQue → while cond:, expressions entièrement parenthésées pour garder les priorités; div définie en tête du code généré et levant ErreurLangage; le code est exécuté avec exec(code, {"sortie": [], "div": div}). Résultats typiques : la transpilation (qui profite de la VM de Python) est la plus rapide, la VM maison est ensuite, l'interpréteur d'arbre le plus lent. Explication : arbre = simplicité et débogage ; VM = portabilité et contrôle (sécurité, limites) ; transpilation = performance maximale, mais dépend d'un langage cible et pose des questions de sécurité (code généré exécuté).
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Un bytecode est :
- A. du texte lisible par l'utilisateur
- B. un arbre de syntaxe
- C. une liste plate d'instructions simples exécutée par une VM
2. PUSH 2; PUSH 3; ADD laisse sur la pile :
- A. 5
- B. 2 et 3
- C. rien
3. Le remplissage a posteriori (backpatching) sert à :
- A. optimiser les boucles
- B. compléter les cibles de saut une fois connues
- C. annuler une instruction
4. 🔁 Révision mission 07 : En portée lexicale, une variable libre d'une fonction est cherchée dans :
- A. l'environnement de l'appelant
- B. la mémoire globale uniquement
- C. l'environnement où la fonction a été définie
5. 🔁 Révision mission 07 : Une fermeture est :
- A. une fonction accompagnée de son environnement de définition
- B. une fonction sans paramètre
- C. un type de boucle
✅ Réponses
- C.
- A.
- B.
- C.
- A.
🪞 Je réfléchis (10 XP)
- Quelle tâche de ta vie préfères-tu « traduire une fois en liste d'étapes simples » plutôt que de réfléchir à chaque fois ?
- Quels compromis vois-tu entre un interpréteur d'arbre, une VM et un transpileur ?
🎒 À retenir
- Bytecode = liste plate d'instructions ; VM = boucle fetch-decode-execute.
- Machine à pile : opérandes empilés, opérations sur le sommet.
- Contrôle de flot : JMP, JZ, backpatching.
- Désassembleur et tests d'équivalence.
- Optimisation peephole sur du code sans saut.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Pilote de VM
← Mission 07 — Environnement, portée et fermetures · Mission 09 — Erreurs et diagnostics →
HEF-090 — Compilateurs et langages

