Organisation mémoire

Le code intermédiaire manipule des variables et des appels comme des abstractions. Pour produire du code qui s'exécute, il faut répondre à une question restée en suspens : où vivent ces variables en mémoire, et comment un appel de fonction s'y organise ? C'est l'environnement d'exécution — la convention, fixée par le compilateur, qui régit l'usage de la mémoire pendant que le programme tourne.

Ce chapitre relie enfin deux fils : l'« emplacement mémoire » que la table des symboles (chapitre 6) promettait, et les param, appels et locales du code intermédiaire (chapitre 9). Il explique aussi, au passage, pourquoi la récursivité fonctionne — et pourquoi elle peut faire déborder la pile.

Les segments de mémoire

À l'exécution, la mémoire d'un programme se divise en régions aux rôles distincts :

Deux régions croissent en sens opposés pendant l'exécution, ce qui optimise l'espace : le tas grandit vers le haut au fil des allocations, la pile grandit vers le bas au fil des appels. Les variables globales vivent dans les données statiques (adresse fixe, connue dès la compilation) ; les variables locales vivent sur la pile, et n'existent que le temps de leur fonction. C'est cette dernière région qui fait tout l'intérêt du chapitre.

L'enregistrement d'activation

Chaque appel de fonction reçoit un enregistrement d'activation (ou frame) : un bloc de mémoire, empilé sur la pile, qui contient tout ce dont cet appel a besoin. Un enregistrement typique rassemble :

• les paramètres de la fonction ;
• l'adresse de retour — où reprendre l'exécution une fois la fonction terminée ;
• les variables locales ;
• de quoi retrouver l'enregistrement de l'appelant (le chaînage, plus bas).

Le point essentiel pour le compilateur : à l'intérieur d'une frame, chaque variable occupe une place à un décalage fixe depuis le début de la frame. Une variable locale n'a pas d'adresse absolue — elle a un décalage relatif à sa frame. acc est « à +4 du début de la frame de factoriel ». Ce décalage est calculé à la compilation (en disposant paramètres puis locales à la suite, en cumulant leurs tailles) ; l'adresse réelle ne se connaît qu'à l'exécution : adresse de la frame + décalage.

C'est exactement l'« emplacement mémoire » que la table des symboles (chapitre 6) réservait dans ses entrées : le chapitre 6 promettait un emplacement, le voici — un décalage dans un enregistrement d'activation.

La pile d'appels

Pourquoi une pile ? Parce que les appels suivent une discipline dernier entré, premier sorti : la fonction appelée en dernier est celle qui rend la main en premier. Quand A appelle B qui appelle C, on empile la frame de A, puis de B, puis de C ; C retourne (on dépile), puis B, puis A. La pile grandit à chaque appel, rétrécit à chaque retour, au rythme exact du programme.

Cette organisation offre gratuitement la propriété la plus importante : la récursivité. Comme chaque appel a sa propre frame, un appel récursif de factoriel a son propre k, son propre acc, indépendants de l'appel qui l'a déclenché. Trois appels imbriqués, ce sont trois frames superposées, chacune avec ses variables — les appels ne se marchent pas dessus. La récursion n'a besoin d'aucun mécanisme spécial : elle découle de la pile.

La contrepartie est le débordement de pile (stack overflow) : une récursion trop profonde (ou infinie) empile plus de frames que la mémoire n'en peut contenir. C'est la traduction concrète, à l'exécution, d'une récursion sans cas de base — le pendant du « la pile déborde » qu'évoquait déjà l'analyse descendante (chapitre 4). L'exercice fait dérouler cette pile pas à pas.

Passage de paramètres et valeur de retour

Reste à convenir comment l'appelant et l'appelé s'échangent les données — la convention d'appel, contrat que les deux côtés respectent.

Les paramètres se transmettent en les plaçant à un endroit convenu : dans la frame de l'appelé (sur la pile), ou dans des registres pour les premiers arguments (plus rapide, c'est l'usage moderne). La valeur de retour repart de même, typiquement par un registre dédié. Le passage peut se faire par valeur (on copie l'argument — le cas par défaut) ou par référence (on transmet l'adresse, ce qui permet à l'appelé de modifier la variable de l'appelant).

Un détail que la convention doit trancher : qui nettoie la frame au retour, l'appelant ou l'appelé ? Il n'y a pas de bonne réponse universelle, seulement un contrat à respecter des deux côtés — c'est précisément ce qu'est une convention d'appel.

Variables locales et chaînage

Deux liens relient les frames entre elles, et il ne faut pas les confondre.

Le chaînage dynamique (ou lien de contrôle) pointe vers la frame de l'appelant — celui qui a déclenché l'appel. Il sert à restaurer la pile au retour : on sait où reprendre. C'est le lien qui suit la chaîne des appels.

Le chaînage statique (ou lien d'accès) pointe vers la frame de la fonction englobante lexicalement, dans les langages qui autorisent des fonctions imbriquées. Il permet à une fonction interne d'accéder aux variables locales de la fonction qui la contient — la portée statique du chapitre 6, réalisée à l'exécution. Beaucoup de langages (dont C) n'ont pas de fonctions imbriquées et se passent de ce second lien.

La distinction est celle-là même du chapitre 6 : le chaînage dynamique suit les appels, le chaînage statique suit la structure du texte. Les deux coexistent parce qu'ils répondent à deux questions différentes : « d'où viens-je ? » et « qui m'entoure dans le code ? ».

À vous

L'exercice relie les deux moments de la vie d'une variable locale. À la compilation, vous calculez les décalages des paramètres et locales dans l'enregistrement d'activation — l'emplacement que la table des symboles promettait. À l'exécution, vous simulez la pile d'appels pendant une récursion, en empilant une frame par appel.

Vous verrez pourquoi chaque appel a ses propres variables — d'où la récursivité — et ce qu'est concrètement un débordement de pile.

// À l'exécution, chaque APPEL de fonction reçoit un ENREGISTREMENT
// D'ACTIVATION (une « frame ») empilé sur la PILE D'APPELS. Il contient les
// paramètres, l'adresse de retour, et les variables locales — chacune à un
// DÉCALAGE fixe depuis le début de la frame.

// Description d'une fonction : ses paramètres et ses locales, chacun avec sa
// taille en octets.
const FONCTIONS = {
  main:      { params: [], locales: [ ["n", 4] ] },
  factoriel: { params: [ ["k", 4] ], locales: [ ["acc", 4], ["i", 4] ] },
};

// ── À VOUS (1) : calculer les décalages (à la COMPILATION) ───────────────────
// Poser les paramètres puis les locales à la suite, en cumulant les tailles.
// Renvoyer un objet nom -> décalage, et la taille totale de la frame.
function disposition(fn) {
  const f = FONCTIONS[fn];
  const dec = {};
  let offset = 0;
  // à compléter : pour chaque [nom, taille] de f.params PUIS f.locales :
  //   dec[nom] = offset ; offset += taille;
  return { dec, taille: offset };
}

console.log("Disposition des frames (calculée à la compilation) :");
for (const fn of Object.keys(FONCTIONS)) {
  const d = disposition(fn);
  console.log("  " + fn + " : " + JSON.stringify(d.dec) + "  (taille " + d.taille + " o)");
}

// ── À VOUS (2) : simuler la pile d'appels (à l'EXÉCUTION) ────────────────────
const pile = [];
function entrer(fn) {
  // à compléter : empiler une frame { fn, taille } ; afficher la profondeur
  const d = disposition(fn);
  pile.push({ fn, taille: d.taille });
  console.log("  ".repeat(pile.length) + "-> appel " + fn + " (frame " + d.taille + " o), profondeur " + pile.length);
}
function sortir() {
  const f = pile.pop();
  console.log("  ".repeat(pile.length + 1) + "<- retour " + f.fn + ", frame libérée");
}

// main appelle factoriel, qui s'appelle 2 fois récursivement :
console.log("\nDéroulé de la pile :");
entrer("main");
entrer("factoriel");   // factoriel(3)
entrer("factoriel");   // factoriel(2)
entrer("factoriel");   // factoriel(1)
sortir(); sortir(); sortir(); sortir();
console.log("pile vide ? " + (pile.length === 0));

function disposition(fn) {
  const f = FONCTIONS[fn];
  const dec = {};
  let offset = 0;
  for (const [nom, taille] of [...f.params, ...f.locales]) {
    dec[nom] = offset;       // le décalage de la variable dans la frame
    offset += taille;        // on avance de sa taille pour la suivante
  }
  return { dec, taille: offset };
}
// main      : { n: 0 }                 (taille 4)
// factoriel : { k: 0, acc: 4, i: 8 }   (taille 12)
//
// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Deux moments à ne pas confondre :
//    - À LA COMPILATION, on calcule les DÉCALAGES : « acc est à +4 du début de
//      la frame de factoriel ». C'est l'« emplacement mémoire » que la table
//      des symboles (chapitre 6) promettait — une variable locale n'a pas
//      d'adresse absolue, seulement un décalage relatif à SA frame.
//    - À L'EXÉCUTION, chaque appel EMPILE une frame ; l'adresse réelle d'une
//      variable est « adresse de la frame + décalage ».
//
// 2. La RÉCURSIVITÉ tombe gratuitement : chaque appel de factoriel a SA
//    PROPRE frame sur la pile, donc son propre « k », « acc », « i ». Trois
//    appels imbriqués = trois frames superposées, chacune avec ses variables.
//    C'est pourquoi la récursion fonctionne sans que les appels se marchent
//    dessus — et pourquoi une récursion trop profonde provoque un débordement
//    de pile (stack overflow).
//
// 3. La frame contient aussi l'ADRESSE DE RETOUR (où reprendre après l'appel)
//    et de quoi retrouver la frame appelante (le chaînage). Le passage de
//    PARAMÈTRES place les arguments dans la frame de l'appelé (ici k), la
//    VALEUR DE RETOUR repart par un registre ou un emplacement convenu.
//
// 4. La pile grandit et rétrécit en LIFO, au rythme exact des appels et
//    retours : entrer = empiler, sortir = dépiler. Tout ce qui était local
//    disparaît d'un coup au retour — comme la portée du chapitre 6, mais à
//    l'exécution.

Ce que la suite en fait

L'organisation mémoire est en place : on sait où vivent les variables et comment les appels s'empilent. Il ne reste qu'une étape — produire le code cible réel, celui de la machine, et le rendre efficace.

Le chapitre 11, dernier du cours, traite la génération de code proprement dite — choisir les instructions, placer les valeurs dans les registres — et l'optimisation — rendre le code plus rapide sans changer ce qu'il calcule. C'est le back-end qui referme la chaîne ouverte au chapitre 1.

À retenir