📗 Cours 2 — Du tableau à la
machine virtuelle

Au cours précédent, on a écrit factorielle.c — un programme C qui calcule n! et l'affiche. C'était concret, ça marchait, et on pouvait le tester.

Maintenant, on va se poser une question étrange : comment ça marche, un processeur ? Pas le processeur physique, avec ses transistors et ses nanomètres — ça, c'est pour les électroniciens. Mais le modèle d'exécution : comment une machine fait-elle pour exécuter des instructions les unes après les autres ?

La réponse, c'est la Machine Virtuelle (VM) : un mini-processeur logiciel, avec sa propre mémoire, sa propre pile, et son propre jeu d'instructions. On va le programmer en C, en utilisant les concepts du cours 1 (variables, boucles, tableaux, fonctions) pour construire quelque chose de plus gros.

Dans le cours 1, on a vu les variables simples (int, long long, etc.) et les boucles. Mais pour une VM, il nous faut plus : des séquences de valeurs (la mémoire, la pile, le programme) et des noms symboliques pour les instructions.

2.1 Les tableaux — des variables qui se suivent

Un tableau, c'est une suite contiguë de variables du même type. On y accède par un indice (ou index).

int mem[256];      // un tableau de 256 entiers
mem[0]  = 42;      // écrire dans la case 0
int x = mem[0];   // lire la case 0

for (int i = 0; i < 256; i++)
    mem[i] = 0;    // initialiser tout le tableau

2.2 Les énumérations — des mots pour les chiffres

Une énumération (enum) permet de donner des noms à des entiers. C'est plus lisible que de se rappeler que l'instruction 0 c'est PUSH, 1 c'est DUP…

enum {
    PUSH,   // = 0
    DUP,    // = 1
    DROP,   // = 2
    ADD,    // = 3
    HALT    // = 4
};

int programme[] = { PUSH, 42, PRINT, HALT };

L'architecture de notre VM est une machine à pile, aussi appelée architecture postfixée ou Forth-like. C'est l'une des plus simples à implémenter : les opérations prennent leurs arguments sur une pile et y déposent leur résultat.

3.1 Qu'est-ce qu'une pile ?

Une pile (anglais : stack) fonctionne comme une pile d'assiettes : on ne peut empiler ou dépiler que par le dessus. C'est le principe LIFO (Last In, First Out).

Pile = [3, 7, 5] — le sommet est 5, la base est 3.

Dans notre VM, la pile est implémentée par un tableau et un indice de sommet (sp) :

int stack[STACK_SIZE];   // le tableau
int sp;                    // stack pointer : indice du prochain libre

void pousser(int v) {
    if (sp >= STACK_SIZE) {
        fprintf(stderr, "DEBORDEMENT DE PILE\n");
        exit(1);
    }
    stack[sp++] = v;  // sp pointe toujours sur la case libre
}

int depiler(void) {
    if (sp <= 0) {
        fprintf(stderr, "PILE VIDE\n");
        exit(1);
    }
    return stack[--sp];  // décrémenter puis lire
}

3.2 Notation postfixée (RPN)

Dans la vie de tous les jours, on écrit les opérations en notation infixée : 2 + 3. La VM utilise la notation postfixée (RPN = Reverse Polish Notation) : 2 3 +.

Maintenant qu'on a les briques (tableaux, enum, pile), on peut assembler la machine. Voici les composants :

4.1 Les registres

int ip;
int sp;

4.2 La mémoire

int mem[MEM_SIZE];     // mémoire de données (256 mots)
int stack[STACK_SIZE];  // pile de travail (128 mots)

• mem[] sert à stocker des variables et des chaînes
• stack[] sert aux calculs
• Les instructions (le programme) sont dans un tableau code[] séparé

4.3 Le cycle d'exécution

La VM fonctionne en boucle :

while (ip < taille) {
    int instr = code[ip++];    // 1. FETCH : lire l'instruction

    switch (instr) {               // 2. DECODE : identifier l'opcode
        case PUSH:                  // 3. EXECUTE : exécuter
            pousser(code[ip++]);
            break;
        case ADD: {
            int a = depiler();
            int b = depiler();
            pousser(b + a);
            break;
        }
        // ... autres opcodes ...
    }
}

C'est le fameux cycle FETCH → DECODE → EXECUTE (cherchez « architecture de Von Neumann »). La seule différence avec un vrai processeur, c'est la taille. Et la vitesse. Et le fait que ça tienne dans 300 lignes de C.

Le jeu d'instructions de notre VM comporte 23 opcodes, répartis en catégories. Chaque opcode est un entier (grâce à notre enum).

Les opcodes avec un argument (comme PUSH, JMP, LOAD) consomment un mot supplémentaire dans le programme après l'opcode. Les autres (comme ADD, DUP) n'ont pas d'argument.

Maintenant qu'on a la machine, écrivons un programme. On va implémenter la factorielle (déjà vue au cours 1), mais cette fois en bytecode VM plutôt qu'en C.

6.1 Algorithme en assembleur VM

L'algorithme classique, traduit en instructions VM :

; Algorithme factorielle en pseudo-assembleur VM
; Entrée : n est sur la pile
; Sortie : n! affiché

STORE N         ; mémoriser n dans mem[N]
PUSH 1          ; res = 1
PUSH 2          ; i = 2

LOOP:
    DUP         ; i i
    LOAD N      ; i i n
    GT          ; i (i > n)
    JNZ END     ; si i > n, fin
    SWAP        ; i res
    OVER        ; i res i
    MUL         ; i res*i
    SWAP        ; res*i i
    INC         ; res*i i+1
    JMP LOOP    ; retourner en début de boucle

END:
    DROP        ; res
    PRTS MSG    ; afficher " = "
    PRINT       ; afficher res
    HALT        ; fin du programme

6.2 Encodage en tableau d'entiers

Le même programme, encodé en C :

enum { N = 0, MSG = 200 };
enum { LOOP = 6, END = 19 };

int programme[] = {
    /*  0 */  STORE, N,
    /*  2 */  PUSH, 1,
    /*  4 */  PUSH, 2,
    /*  6 */  DUP,
    /*  7 */  LOAD, N,
    /*  9 */  GT,
    /* 10 */  JNZ, END,
    /* 12 */  SWAP,
    /* 13 */  OVER,
    /* 14 */  MUL,
    /* 15 */  SWAP,
    /* 16 */  INC,
    /* 17 */  JMP, LOOP,
    /* 19 */  DROP,
    /* 20 */  PRTS, MSG,
    /* 22 */  PRINT,
    /* 23 */  HALT,
};

Pour déverminer (debugger) notre VM, on a deux outils : le désassembleur et le mode pas-à-pas.

7.1 Désassembleur

Il transforme le tableau d'entiers en texte lisible :

void desassembler(int code[], int taille) {
    int i = 0;
    while (i < taille) {
        printf("%4d:  ", i);
        int op = code[i];
        if (op == PUSH || op == JMP || /* … */) {
            printf("%-5s %d\n", nom_opcode(op), code[i + 1]);
            i += 2;
        } else {
            printf("%s\n", nom_opcode(op));
            i++;
        }
    }
}

Résultat :

   0:  STORE 0
   2:  PUSH  1
   4:  PUSH  2
   6:  DUP
   7:  LOAD  0
   9:  GT
  10:  JNZ   19
  12:  SWAP
  …
  23:  HALT

7.2 Mode pas-à-pas

Avec l'option --pas-a-pas, la VM s'arrête après chaque instruction et affiche l'état de la pile :

if (pas_a_pas) {
    afficher_instr(code, ip);
    afficher_pile();
    getchar();   // attendre une touche
}

Quelques détails importants sur le code de la VM.

8.1 Gestion de la pile

La pile est initialisée vide (sp = 0) avant chaque exécution. La valeur à calculer (l'entrée du programme) est poussée sur la pile avant de lancer la VM.

pousser(n);                  // déposer l'entrée
executer(programme, taille);  // lancer
int res = stack[0];           // récupérer le résultat

8.2 Initialisation de la mémoire

La mémoire est remise à zéro avant chaque programme, et on y place les chaînes de caractères :

void initialiser_memoire(void) {
    for (int i = 0; i < MEM_SIZE; i++)
        mem[i] = 0;
    mem[MSG]     = ' ';      // " = \0"
    mem[MSG+1] = '=';
    mem[MSG+2] = ' ';
    mem[MSG+3] = 0;       // terminateur nul
}

8.3 Programme complet

Tout le code tient dans vm.c (~326 lignes) :

• Définition des opcodes (enum) — 12 lignes
• Pile et mémoire — 5 lignes
• Primitives de pile (pousser, depiler, sommet) — 25 lignes
• Afficheur de pile — 6 lignes
• Afficheur d'instruction — 17 lignes
• Exécuteur (switch sur 23 opcodes) — ~60 lignes
• Désassembleur — 15 lignes
• Programme factorielle (tableau) — 20 lignes
• Tests — ~30 lignes
• Le reste : main, initialisation, etc.

Notre VM s'inspire directement du langage Forth (créé par Chuck Moore dans les années 70). Forth, c'est : une pile, des mots (opcodes), et une philosophie minimaliste.

Pour compiler et tester la VM :

make vm         # compiler vm.c
make vm-run     # exécuter les tests (0! à 12!)
./vm             # exécution directe
./vm --pas-a-pas # mode déverminage

Les tests calculent n! pour n = 0 à 12 et comparent avec les valeurs attendues. Si tout est OK, le programme affiche 13 passes, 0 echoues et retourne 0.

=== Désassemblage du programme ===
   0:  STORE 0
   2:  PUSH  1
  …
  23:  HALT

=== Factorielle 0 à 12 ===
  0 = 1      OK
  1 = 1      OK
  2 = 2      OK
  3 = 6      OK
  4 = 24     OK
  5 = 120    OK
  6 = 720    OK
  7 = 5040   OK
  8 = 40320  OK
  9 = 362880 OK
  10 = 3628800  OK
  11 = 39916800 OK
  12 = 479001600 OK

  13 passes, 0 echoues

Pour aller plus loin, voici quelques pistes. La difficulté est indiquée par ★ (facile) à ★★★ (costaud).

Ce qu'on a vu dans ce cours :

Pistes pour la suite :

• Cours 3 : Parseur de s-expressions → on apprend à lire du LISP et à compiler des expressions arithmétiques en bytecode VM. Fini le codage à la main !
• Calculateur RPN interactif : Écrire un REPL qui lit des expressions RPN au clavier et les exécute sur la VM en temps réel. Comme une calculatrice HP, mais en moins cher.
• Assembleur VM : Écrire un programme qui lit du texte (PUSH 1, ADD, etc.) et le compile en bytecode. On pourrait même inventer une syntaxe avec des labels !
• Extensions : opcodes flottants (FADD, FMUL), chaînes, tableaux, etc.