Aller au contenu principal

Vaλisp 3 : Environnement & GC

Progression

#Vaλisp 3 : Environnement lexical et ramasse-miettes

Vaλisp sait désormais représenter ses valeurs. Pour évaluer un programme Lisp, il faut aussi mémoriser les variables et pouvoir recycler la mémoire. Ce chapitre introduit la chaîne des environnements et implémente un garbage collector mark‑sweep.

#1. Chaîne d’environnements

Un environnement est une liste de cadres. Chaque cadre associe des symboles à des valeurs et pointe vers son parent. Manipuler cette structure réintroduit un modèle que vous connaissez déjà : une liste chaînée.

cc
1typedef struct Binding {2    TaggedValue symbol;3    TaggedValue value;4    struct Binding *next;5} Binding;6 7typedef struct Env {8    Binding *bindings;9    struct Env *parent;10} Env;

env_lookup parcourt la chaîne ; env_define insère un nouveau binding en tête du cadre courant ; env_set remonte la chaîne jusqu’à trouver le symbole. Nous écrivons aussi env_push/env_pop pour préserver l’environnement courant pendant l’évaluation.

#2. Garbarge collector mark-sweep

L’arène que nous utilisions jusqu’ici ne recyclait pas la mémoire. Nous ajoutons un bit mark à chaque cellule et implémentons un GC en deux phases :

  1. Marquage : partir des racines (environnement global, pile d’évaluation) et marquer récursivement toutes les valeurs atteignables.
  2. Balayage : parcourir l’arène et remettre en liste libre les cellules non marquées.
cc
1void gc_mark_value(TaggedValue v) {2    if ((v & TAG_MASK) != TAG_PTR) return;3    Value *cell = (Value *)(v & ~TAG_MASK);4    if (cell->mark) return;5    cell->mark = 1;6    switch (cell->kind) {7        case VAL_CONS:8            gc_mark_value(cell->as.cons.car);9            gc_mark_value(cell->as.cons.cdr);10            break;11        case VAL_SYMBOL:12        case VAL_NUMBER:13        case VAL_NIL:14            break;

Pendant le balayage, les cellules non marquées sont remises dans une liste libre que l’allocateur réutilise. Nous déclenchons le GC lorsque l’arène est remplie à 80 % ou après un certain nombre d’allocations.

#3. Atelier

  1. Ajoutez un compteur de pression mémoire et déclenchez un GC dès que l’arène dépasse un seuil configurable.
  2. Étendez l’ensemble des racines pour intégrer la pile d’évaluation et les registres temporaires utilisés par l’interpréteur.
  3. Ajoutez un mode trace qui affiche les statistiques du GC (cells markées, temps de marquage, temps de balayage) lorsque l’option --gc-stats est fournie.

À l’issue de ce chapitre, Vaλisp peut tourner indéfiniment sans fuiter de mémoire et chaque variable trouve naturellement sa valeur via la chaîne des environnements. La prochaine étape consistera à lire une expression Lisp et à construire nos structures directement depuis le texte d’entrée.