📗 Cours 2 — Du tableau à la machine virtuelle

Au cours 1, on a vu les variables simples : int n = 5;. Une variable = une case mémoire. Mais si on veut plusieurs valeurs ? Par exemple, les 8 résultats de nos tests factorielle ? On pourrait écrire 8 variables, mais c'est fastidieux :

int test1_n = 0;   long long test1_res = 1;
int test2_n = 1;   long long test2_res = 1;
int test3_n = 2;   long long test3_res = 2;
/* … et on pleure à la 8e */

Heureusement, le C offre le tableau (array) : une collection d'éléments de même type, accessibles par un indice.

#include <stdio.h>

int main() {
    int mem[8];               // un tableau de 8 entiers

    mem[0] = 42;               // écrire dans la case 0
    mem[1] = mem[0] * 2;      // lire et calculer

    printf("mem[0] = %d\n", mem[0]);
    printf("mem[1] = %d\n", mem[1]);

    // parcourir tout le tableau avec une boucle
    for (int i = 0; i < 8; i++)
        printf("mem[%d] = %d\n", i, mem[i]);

    return 0;
}

Prenons un tableau un peu plus grand (256 cases) et appelons-le mem. Ce sera notre « mémoire » — on peut écrire dedans (STORE) et lire dedans (LOAD). C'est exactement comme ça que fonctionne la RAM d'un vrai ordinateur.

Ajoutons aussi un indice (ip) pour parcourir un « programme » qui serait une suite d'ordres stockée dans un autre tableau.

#include <stdio.h>

int mem[256];     // mémoire de données
int ip;          // instruction pointer

int programme[] = {
    10,          // instruction 10 = STORE à l'adresse suivante
    0,           // adresse 0
    20,          // instruction 20 = PRINT (affiche)
    99,          // instruction 99 = HALT (arrêt)
};

int main() {
    int taille = sizeof(programme) / sizeof(programme[0]);
    ip = 0;

    while (ip < taille) {
        int instr = programme[ip++];
        if (instr == 10) {       // STORE
            int addr = programme[ip++];
            mem[addr] = 42;    // on force 42 pour l'exemple
        }
        else if (instr == 20) { // PRINT
            printf("%d\n", mem[0]);
        }
        else if (instr == 99) { // HALT
            ip = taille;
        }
    }
    return 0;
}

C'est rudimentaire — une cascade de if qui teste des codes magiques (10, 20, 99). Mais le mécanisme est là : un tableau = le programme, un registre = l'indice, une boucle = le processeur. Félicitations, vous venez de réinventer le cycle de von Neumann.

Des codes numériques 10, 20, 99… c'est illisible. Si on se trompe de numéro, le programme fait n'importe quoi sans prévenir. Le C propose une solution élégante : l'énumération (enum).

// Avant — codes magiques
if (instr == 10) ...
else if (instr == 20) ...

int programme[] = {
    10, 0,    // STORE 0 ?
    20,        // PRINT ?
    99,        // HALT ?
};

enum { STORE = 10, PRINT = 20, HALT = 99 };

if (instr == STORE) ...
else if (instr == PRINT) ...

int programme[] = {
    STORE, 0,
    PRINT,
    HALT,
};

Quand on laisse le compilateur numéroter tout seul :

enum { PUSH, DUP, DROP, SWAP, OVER };  // PUSH=0, DUP=1, DROP=2…

Un if par instruction, ça devient vite long. Le C offre switch pour aiguiller selon la valeur d'une expression :

// Cascade if — long, lent
if (instr == PUSH) { … }
else if (instr == ADD) { … }
else if (instr == MUL) { … }
else { /* erreur */ }

// switch — clair, rapide
switch (instr) {
    case PUSH: … ; break;
    case ADD:  … ; break;
    case MUL:  … ; break;
    default:  /* erreur */;
}

Notre mémoire permet de stocker des valeurs, mais comment faire des calculs ? Ajoutons une pile (stack) — un tableau avec un sommet (sp).

Principe d'une pile :

• Pousser (push) : on écrit au sommet, on monte sp
• Dépiler (pop) : on descend sp, on lit la valeur
• Dernier entré, premier sorti (LIFO)

int stack[128];   // pile de travail
int sp;            // sommet de pile (stack pointer)

void pousser(int v) {
    stack[sp++] = v;
}

int depiler(void) {
    return stack[--sp];
}

// Et dans la boucle d'exécution :
switch (instr) {
    case PUSH:
        pousser(programme[ip++]);          // empiler la valeur
        break;
    case ADD: {
        int a = depiler();
        int b = depiler();
        pousser(b + a);                     // b + a (ordre postfixé)
        break;
    }
    case MUL: … // pareil avec *
}

Avec une pile, on peut enchaîner les opérations en postfixé : PUSH 3 PUSH 4 ADD calcule 3 + 4 = 7.

Que se passe-t-il si on dépile alors que la pile est vide ? Ou si on empile alors qu'elle est pleine ? Le programme plante (ou pire, il continue avec des données corrompues).

Ajoutons des gardes :

void pousser(int v) {
    if (sp >= 128) {
        fprintf(stderr, "DEBORDEMENT DE PILE\n");
        exit(1);           // on s'arrête proprement
    }
    stack[sp++] = v;
}

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

Sans sauts, un programme s'exécute linéairement du début à la fin. Pour faire une boucle (comme notre factorielle), il faut pouvoir sauter à une instruction précédente, et tester des conditions.

Trois instructions de saut suffisent :

• JMP addr — saut inconditionnel : ip = addr
• JZ addr — saut si zéro : dépiler, si = 0 alors ip = addr
• JNZ addr — saut si non-zéro : dépiler, si ≠ 0 alors ip = addr

case JMP:  ip = programme[ip]; break;          // saut pur
case JZ: {
    int addr = programme[ip++];
    if (depiler() == 0) ip = addr;
    break;
}
case JNZ: {
    int addr = programme[ip++];
    if (depiler() != 0) ip = addr;
    break;
}

Remarquez : JMP lit l'adresse dans le programme MAIS n'incrémente pas ip après — l'adresse remplace ip. C'est un saut. Les autres instructions lisent leur argument et incrémentent ip normalement.

Dans notre code, on a écrit int mem[256] et int stack[128]. Les nombres 256 et 128 apparaissent « en dur ». Si on veut les changer, il faut chercher partout. Le préprocesseur C offre #define pour nommer des constantes :

#define MEM_SIZE   256
#define STACK_SIZE 128

int mem[MEM_SIZE];
int stack[STACK_SIZE];

void pousser(int v) {
    if (sp >= STACK_SIZE) { … }
}

Un programme representé comme un tableau d'entiers, c'est pratique pour la machine, mais illisible pour l'humain. Un désassembleur fait la traduction inverse : il prend le tableau et affiche chaque instruction en texte.

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[op], code[i + 1]);
            i += 2;    // instruction à 2 mots
        } else {
            printf("%s\n", nom[op]);
            i++;        // instruction à 1 mot
        }
    }
}

On utilise un tableau nom[] qui associe à chaque opcode son nom textuel :

static const char *nom[] = {
    "PUSH", "DUP", "DROP", "SWAP", "OVER",
    "ADD", "SUB", "MUL", "NEG", "INC", "DEC",
    "EQ", "NE", "GT", "LT",
    "JMP", "JZ", "JNZ",
    "LOAD", "STORE",
    "PRINT", "PRTS", "HALT"
};

Maintenant qu'on a tous les ingrédients, écrivons un programme pour notre VM : la factorielle. On le définit comme un tableau d'entiers, avec des constantes pour les adresses :

enum { N = 0, MSG = 200 };    // adresses mémoire
enum { LOOP = 6, END = 19 };  // étiquettes de saut

int programme[] = {
    STORE, N,          // mem[N] = n
    PUSH, 1,          // res = 1
    PUSH, 2,          // i = 2
    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,         // retour boucle
    DROP,              // jeter i, garder res
    PRTS, MSG,         // afficher " = "
    PRINT,             // afficher res
    HALT,
};

Le programme se lit comme un algorithme : « STORE N, PUSH 1, PUSH 2, LOOP: DUP, LOAD N, GT, JNZ END… » — chaque mot a un sens précis. C'est ça, l'assembleur : une notation lisible pour du code machine.

Quand on ne comprend pas ce que fait un programme, on peut l'exécuter pas à pas : une instruction à la fois, en voyant l'état de la pile. La VM accepte l'option --pas-a-pas qui active ce mode :

if (pas_a_pas) {
    afficher_instr(code, ip);
    afficher_pile();
    getchar();       // attendre Entrée
}

À chaque instruction, la VM affiche l'instruction puis la pile, et attend qu'on appuie sur Entrée. On peut suivre le déroulement comme un film au ralenti.

Les nouveaux concepts et mots-clés C rencontrés :

Nouveaux concepts d'architecture :

• Machine à pile — les calculs passent par une pile, pas par des registres
• Instruction Pointer — l'indice qui parcourt le programme
• Cycle fetch-decode-execute — la boucle d'exécution
• Postfixé (RPN) — opérateurs après les opérandes (1 2 ADD)
• Désassembleur — traducteur code machine → texte

La VM complète (instructions, programme, tests) est documentée ici :

🖥️ Documentation complète de la VM → vm-doc.html