#Vaλisp 2 : encodage compact et table de symbolesCopier le lien

Le jalon 1 fonctionne, mais chaque valeur consomme une structure complète (énumération, union, deux pointeurs) même pour un simple entier. Cette étape introduit un encodage plus compact inspiré des Lisp historiques : un mot machine contient à la fois la donnée et son type. Le mécanisme repose sur l’alignement des pointeurs, que le chapitre codage mémoire vous a appris à mesurer. Nous ajoutons l’internage des symboles, qui rend leur comparaison immédiate.

#1. Tagger les valeursCopier le lien

Sur une architecture 64 bits, malloc renvoie des pointeurs alignés : leurs bits de poids faible valent 0. Nous détournons les deux bits de poids faible pour y ranger une étiquette de type :

1#include <stdint.h>2 3typedef uintptr_t TaggedValue;4 5#define TAG_MASK 0x3u6#define TAG_INT  0x0u    /* entier : porté par le mot, bits 2..63 */7#define TAG_PTR  0x1u    /* pointeur vers une cellule de l'arène */8#define TAG_SYM  0x2u    /* pointeur vers un nom interné */9#define TAG_NIL  0x3u    /* immédiat : la liste vide n'occupe aucune cellule */10 11static inline TaggedValue wrap_int(long n) {12    return ((TaggedValue)(uint64_t)n << 2u) | TAG_INT;   /* décale puis étiquette */13}14 

Ce qui change par rapport au jalon 1 :

• Les entiers n’allouent plus. Un entier vit dans le mot ; une liste de 10 000 entiers ne consomme que ses 10 000 paires. En échange, l’entier est limité à 62 bits signés : le débordement à la construction doit être détecté (vérifier n >= -(1L<<61) et n < (1L<<61) avant le décalage), pas subi.
• VAL_NIL devient un immédiat : la constante TAG_NIL est une valeur comme une autre, aucune cellule.
• Les paires restent dans l’arène, mais on n’y accède plus que par unwrap_ptr :

1static inline TaggedValue wrap_ptr(Value *p) {2    uintptr_t raw = (uintptr_t)p;3    /* invariant de l'arène : calloc garantit l'alignement, donc bits 0-1 à zéro */4    return raw | TAG_PTR;5}6 7static inline Value *unwrap_ptr(TaggedValue v) {8    return (Value *)(v & ~(uintptr_t)TAG_MASK);9}

Enfin, la même clé de discipline qu’au jalon 1 : l’étiquette est l’unique clé d’accès. unwrap_int sur un mot TAG_PTR ne produit pas une erreur, il produit un entier absurde (indice de l’étiquette compris). Toute fonction commence par tester l’étiquette ; un switch sur v & TAG_MASK couvre les quatre cas.

#2. Interner les symbolesCopier le lien

Deux symboles de même nom doivent pouvoir être comparés par adresse. La table d’internage est un dictionnaire nom vers pointeur unique :

1typedef struct {2    size_t capacity;   /* puissance de deux */3    size_t count;4    char **slots;      /* NULL = libre */5} SymbolTable;6 7const char *intern(SymbolTable *t, const char *name);

Contrat de intern : renvoie un pointeur unique et permanent pour ce nom ; le premier appel copie la chaîne (à charge de la table, pour toujours), les suivants renvoient le même pointeur. L’identité devient un test d’égalité :

1TaggedValue a = wrap_symbol(intern(&symbols, "car"));2TaggedValue b = wrap_symbol(intern(&symbols, "car"));3/* a == b : comparaison de mots, aucun strcmp */

Propriété de la table : elle vit le temps du programme et n’est jamais vidée élément par élément ; sa destruction libère ensuite chaque nom puis le tableau de slots. Hachage simple pour commencer : FNV-1a sur les caractères, puis adressage ouvert linéaire (candidat suivant : (h + i) & (capacity - 1)), redimensionnement quand count * 4 >= capacity * 3.

#3. Atelier : jalon 2Copier le lien

1. Écrivez wrap_ptr/unwrap_ptr, wrap_symbol/unwrap_symbol, is_nil, is_symbol. Adaptez print_value : il teste d’abord is_int, is_nil, is_symbol, ne déréférence l’arène que pour les paires.
2. Implémentez la SymbolTable avec FNV-1a et adressage ouvert ; testez intern("abc") == intern("abc") (même adresse) et intern("abc") != intern("abd").
3. Reconstruisez (1 2 3) : trois wrap_int, trois cons. La sortie Lisp doit être identique au jalon 1.
4. Mesurez : construisez une liste de 10 000 entiers avec l’ancienne représentation (struct Value par entier) puis avec la nouvelle (paires seulement), affichez arena->count dans les deux cas.

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

1(1 2 3)2intern: identite OK, difference OK3liste de 10000 entiers : ancienne representation 20000 cellules, nouvelle 10000 cellules

Exactitude finale :

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