#Vaλisp 1 : valeurs et allocateurCopier le lien

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. Le projet est cumulatif : chaque étape s’appuie sur la précédente et se termine par un jalon vérifiable. Cette première étape installe la représentation en mémoire des s-expressions et l’allocateur le plus simple possible : une arène. Tout ce que vous écrivez ici sera conservé jusqu’au dernier chapitre.

#1. Choisir une représentation pour les valeursCopier le lien

Les valeurs de Vaλisp sont, pour l’instant, des nombres, des symboles et des paires (cons). Un type variant en C, c’est une énumération pour distinguer les formes et une union pour mutualiser l’espace : un seul champ est valide à la fois, celui que désigne kind.

1/* value.h */2typedef enum {3    VAL_NIL,       /* liste vide */4    VAL_NUMBER,5    VAL_SYMBOL,6    VAL_CONS7} ValueKind;8 9typedef struct Value Value;10 11struct Value {12    ValueKind kind;13    union {14        double number;                    /* VAL_NUMBER */

La discipline de propriété, dès maintenant :

• VAL_NUMBER : la valeur est dans la cellule, aucune ressource externe.
• VAL_SYMBOL : la cellule possède name (copie allouée par le constructeur). Libérer une valeur de symbole, c’est libérer name.
• VAL_CONS : les pointeurs car/cdr désignent des cellules de la même arène ; on ne les libère jamais individuellement, l’arène est libérée en bloc.
• VAL_NIL : aucune ressource.

Lire as.number sur une cellule VAL_SYMBOL est un comportement indéfini : le kind est la seule clé d’accès à l’union. Toute fonction qui reçoit un Value * commence donc par examiner kind.

#2. Construire une arène linéaireCopier le lien

Pour commencer, l’allocateur le plus simple : un bloc contigu dans lequel on sert les cellules une à une, sans jamais les reprendre. La durée de vie de toute valeur est celle de l’arène entière ; le ramasse-miettes viendra à l’étape 3.

1/* arena.c */2#include <stdlib.h>3#include <stdio.h>4#include "value.h"5 6typedef struct {7    size_t capacity;   /* cellules totales */8    size_t count;      /* cellules déjà servies */9    Value *cells;10} Arena;11 12int arena_init(Arena *a, size_t capacity) {13    a->capacity = capacity;14    a->count = 0;

Deux choix à noter. calloc plutôt que malloc : les cellules sont mises à zéro, donc une cellule servie puis jamais initialisée reste VAL_NIL plutôt qu’un kind aléatoire (lire un ValueKind non initialisé serait un comportement indéfini). Et arena_alloc renvoie NULL au lieu d’appeler abort() : un allocateur qui plante le programme empêche tout test propre ; la politique d’erreur appartient à l’appelant.

Les symboles posent la seule vraie question de propriété de cette étape : leurs noms sont alloués hors arène. L’interface la plus simple à cet stade est de les recenser et de les libérer à la destruction, ou de leur consacrer une seconde arène d’octets ; l’étape suivante (internage) remplacera ce dispositif par une table qui vit le temps du programme.

#3. Les constructeursCopier le lien

Chaque constructeur prend l’arène, y prend une cellule, et initialise tous les champs du cas concerné :

1Value *make_number(Arena *a, double x) {2    Value *v = arena_alloc(a);3    if (!v) return NULL;4    v->kind = VAL_NUMBER;5    v->as.number = x;6    return v;7}8 9Value *cons(Arena *a, Value *car, Value *cdr) {10    Value *v = arena_alloc(a);11    if (!v) return NULL;12    v->kind = VAL_CONS;13    v->as.cons.car = car;14    v->as.cons.cdr = cdr;

make_symbol suit le même motif avec, en plus, la copie possédée du nom : strlen + malloc + memcpy (ou strdup, POSIX). Contrat : le pointeur passé par l’appelant reste à l’appelant ; la cellule possède sa copie.

#Atelier : jalon 1Copier le lien

1. Écrivez value.c et arena.c avec make_number, make_symbol, cons, puis une fonction print_value qui affiche une valeur en notation Lisp : les nombres en %g, les symboles par leur nom, les paires sous forme de liste chaînée (a b c) avec VAL_NIL en terminateur.
2. Écrivez main.c qui construit (1 2 3) : trois nombres et trois paires, chaînées depuis la tête, la dernière paire pointant vers une valeur VAL_NIL.
3. Ajoutez dump_value qui affiche le graphe mémoire : pour chaque cellule, son index dans l’arène, son kind, et les index de car/cdr.

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

Sortie attendue, à l’espacement près :

1(1 2 3)2cell 0: NUMBER 13cell 1: NUMBER 24cell 2: NUMBER 35cell 3: CONS car=0 cdr=46cell 4: CONS car=1 cdr=57cell 5: CONS car=2 cdr=NIL

Puis vérifiez l’absence de fuite :

1valgrind -q --leak-check=full ./valisp2# attendu : aucune sortie