Aller au contenu principal

Vaλisp 1 : Allocateur

Progression

#Vaλisp 1 : Présenter les valeurs et poser l’allocateur

Vaλisp est notre fil rouge : un interpréteur Lisp compact qui servira de terrain d’entraînement pour les pointeurs, la gestion mémoire et l’architecture logicielle. Cette première étape installe la représentation en mémoire des s‑expressions et le gestionnaire de tas le plus simple possible.

#1. Choisir une représentation pour les valeurs

Les valeurs de Vaλisp sont des nombres, des symboles et des paires (cons). Nous définissons une énumération pour distinguer ces formes et un union pour mutualiser l’espace mémoire. Le union correspond parfaitement aux types variant : un seul champ est valide à la fois, et le code choisit le bon en fonction du kind.

cc
1typedef enum {2    VAL_NIL,3    VAL_NUMBER,4    VAL_SYMBOL,5    VAL_CONS6} ValueKind;7 8typedef struct Value Value;9 10struct Value {11    ValueKind kind;12    union {13        double number;14        struct { char *name; } symbol;

VAL_NIL matérialise la liste vide ; les nombres sont stockés sous forme de double pour simplifier les opérations ; les symboles contiennent un pointeur vers une chaîne allouée ailleurs ; les paires (cons) réutilisent deux pointeurs vers d’autres valeurs.

#2. Construire une arène linéaire

Pour commencer, nous utilisons un allocateur très simple : un bloc contigu (arena) dans lequel on emprunte les cellules une à une. Cette approche est suffisante tant que nous ne récupérons pas la mémoire ; le ramasse-miettes viendra plus tard.

cc
1typedef struct {2    size_t capacity;3    size_t count;4    Value *cells;5} Arena;6 7void arena_init(Arena *arena, size_t capacity) {8    arena->capacity = capacity;9    arena->count = 0;10    arena->cells = calloc(capacity, sizeof(Value));11}12 13Value *arena_alloc(Arena *arena) {14    if (arena->count >= arena->capacity) {

Chaque constructeur (make_number, make_symbol, cons) prend un pointeur vers l’arène et récupère une cellule libre. Nous insistons sur le fait que cette approche n’autorise pas free : le tas est libéré en une fois à la fin du programme.

#3. Atelier

  1. Implémentez make_number, make_symbol et cons. Pour make_symbol, dupliquez la chaîne passée en argument via strdup ou une implémentation maison.
  2. Écrivez un REPL linéaire : lisez la ligne (+ 1 2) depuis l’entrée standard, convertissez-la dans la représentation cons et affichez le graphe mémoire pour vérifier votre compréhension.

Nous disposons maintenant d’une fondation solide : une représentation uniforme des valeurs et un allocateur simple. Les prochains chapitres ajouteront l’internage des symboles, un encodage plus compact et, bientôt, le ramasse-miettes.