#Vaλisp 3 : environnement lexical et ramasse-miettesCopier le lien

Vaλisp sait représenter ses valeurs et comparer ses symboles par adresse. Pour évaluer un programme, il faut encore mémoriser les variables et recycler la mémoire : ce chapitre introduit la chaîne des environnements puis un ramasse-miettes mark-sweep. C’est l’étape où le modèle de propriété change : plus personne ne libère cellule par cellule, le GC décide de ce qui survit à partir de racines.

#1. La chaîne des environnementsCopier le lien

Un environnement associe des symboles à des valeurs. Pour implémenter la portée lexicale (une fonction voit les variables de son lieu de définition), chaque cadre pointe vers son parent :

1typedef struct Binding {2    TaggedValue symbol;              /* symbole interné */3    TaggedValue value;4    struct Binding *next;            /* chaîne du cadre courant */5} Binding;6 7typedef struct Env {8    Binding *bindings;               /* liaisons de CE cadre */9    struct Env *parent;              /* cadre englobant, NULL pour le global */10} Env;

Trois opérations suffisent à l’évaluation :

• env_lookup(env, sym) : remonte la chaîne cadre par cadre, compare les symboles par adresse (l’internage du jalon 2 paie ici : un simple == sur les mots), renvoie la valeur ou signale l’absence.
• env_define(env, sym, val) : ajoute une liaison en tête du cadre courant (c’est le define de Lisp : définit dans le cadre courant, ne remonte jamais).
• env_set(env, sym, val) : remonte jusqu’à trouver le symbole et modifie sa valeur ; erreur si absent (c’est le set! : on ne crée pas de variable implicite).

La durée de vie des Env et des Binding suit la même règle que les cellules : alloués dans le tas de l’interpréteur, jamais libérés à la main, rendus au GC. env_push/env_pop, qui sauvegardent et restaurent l’environnement courant pendant l’évaluation, deviennent donc de simples manipulations de pointeurs, sans allocation ni libération.

#2. Un ramasse-miettes mark-sweepCopier le lien

L’arène du jalon 1 ne récupère rien : tout programme non trivial la sature. Nous ajoutons un bit mark par cellule et un GC en deux phases.

Phase 1, le marquage. On part des racines (tout ce que le programme peut encore atteindre : l’environnement global, la pile d’évaluation, les temporaires en cours) et on marque récursivement tout ce qui est atteignable :

1void gc_mark_value(TaggedValue v) {2    if ((v & TAG_MASK) != TAG_PTR) return;   /* immédiats : rien à suivre */3    Value *cell = (Value *)(v & ~(uintptr_t)TAG_MASK);4    if (cell->mark) return;                  /* déjà visité : stoppe les cycles */5    cell->mark = 1;6    if (cell_is_cons(cell)) {7        gc_mark_value(cell->as.cons.car);8        gc_mark_value(cell->as.cons.cdr);9    }10    /* symboles internés : la table est racine à part entière */11}

Le test cell->mark avant la récursion fait deux choses : il évite le repassage, et il casse les cycles. Des listes circulaires existent en Lisp (un cdr qui reboucle) ; sans ce test, le marquage bouclerait à l’infini.

Phase 2, le balayage. On parcourt l’arène ; chaque cellule non marquée rejoint une liste libre que arena_alloc servira en priorité ; les marquées sont remises à zéro pour la prochaine collecte :

1void gc_sweep(Arena *a) {2    a->free_count = 0;3    for (size_t i = 0; i < a->capacity; ++i) {4        Value *c = &a->cells[i];5        if (c->mark) {6            c->mark = 0;7        } else if (cell_is_in_use(c)) {      /* servie mais inaccessible */8            a->free_list[a->free_count++] = c;9        }10    }11}

Quand collecter ? Le déclencheur simple : quand arena_alloc échoue (arène pleine), lancer gc_mark_roots(); gc_sweep(a); puis réessayer l’allocation ; ne déclarer l’échec que si l’arène est encore pleine après la collecte. La pression mémoire devient ainsi l’événement déclencheur, sans seuil arbitraire à régler.

#3. Atelier : jalon 3Copier le lien

1. Ajoutez le champ mark aux cellules, free_list/free_count à l’arène, et modifiez arena_alloc pour servir d’abord la liste libre, puis les cellules neuves, et déclencher un GC avant d’échouer.
2. Écrivez gc_mark_env (chaîne des environnements) et gc_mark_value (récursion ci-dessus), puis gc_sweep.
3. Programme de test : dans une boucle de 10 000 itérations, construisez (i i+1 i+2), affichez-la, jetez-la. L’arène est dimensionnée à 100 cellules : sans GC elle sature immédiatement, avec lui elle boucle indéfiniment.
4. Comptez les collectes et affichez-les : l’option --gc-stats imprime le total en fin d’exécution.

1cc -std=c17 -Wall -Wextra -Wpedantic -g -fsanitize=address,undefined value.c arena.c symtab.c env.c gc.c main.c -o valisp2./valisp --gc-stats

1(0 1 2)2(1 2 3)3...4(9999 10000 10001)5gc: 336 collectes, arène 100 cellules, saturation: 0

Le nombre exact de collectes dépend de votre liste libre ; le jalon est : les 10 000 lignes s’affichent, la saturation reste à zéro, et la sortie ASan/Valgrind reste propre.