Aller au contenu principal

Vaλisp 2 : Types & encodage

Progression

#Vaλisp 2 : Encodage compact et table de symboles

L’arène linéaire fonctionne, mais chaque valeur occupe une structure complète même lorsqu’il s’agit d’un entier. Nous allons introduire un encodage plus compact inspiré des implémentations historiques de Lisp : un mot machine contient à la fois la donnée et le type. Ce mécanisme s’appuie sur l’alignement naturel des pointeurs.

#1. Tagger les valeurs

Sur une architecture 64 bits, les pointeurs sont alignés sur quatre ou huit octets. Les deux bits de poids faible valent donc toujours 00. Nous pouvons les détourner pour y écrire un identifiant de type.

cc
1typedef uintptr_t TaggedValue;2 3#define TAG_MASK 0x3u4#define TAG_INT  0x0u5#define TAG_PTR  0x1u6#define TAG_SYM  0x2u7 8static inline TaggedValue wrap_int(long n) {9    return ((TaggedValue)n << 2u) | TAG_INT;10}11 12static inline int is_int(TaggedValue v) {13    return (v & TAG_MASK) == TAG_INT;14}

Les entiers tiennent directement dans le mot. Les paires restent stockées dans l’arène ; on leur applique simplement le tag TAG_PTR en assurant que les deux bits de poids faible restent à zéro ((TaggedValue)ptr | TAG_PTR). Les symboles utilisent TAG_SYM et pointent vers une zone de mémoire distincte contenant le nom.

#2. Internage des symboles

Pour qu’un symbole puisse être comparé rapidement, nous l’introduisons dans une table d’internage. Une table de hachage à adressage ouvert suffit :

cc
1typedef struct {2    size_t capacity;3    size_t count;4    char **slots;5} SymbolTable;

Lorsque intern("car") est appelé, la fonction cherche s’il existe déjà un slot avec ce nom. Si oui, elle renvoie le pointeur existant; sinon elle duplique la chaîne avec strdup et l’insère. Deux symboles identiques partagent donc la même adresse, ce qui permet de comparer les symboles par simple comparaison de pointeurs.

#3. Atelier

  1. Ajoutez des fonctions wrap_ptr, unwrap_ptr, wrap_symbol, unwrap_symbol qui masquent la gestion des tags.
  2. Étendez l’encodage pour représenter deux booléens #t et #f. Vous pouvez réserver deux constantes (TAG_BOOL_TRUE, TAG_BOOL_FALSE) ou utiliser des pointeurs vers des sentinelles.
  3. Mesurez l’impact mémoire en évaluant un programme Lisp qui construit une liste de 10 000 entiers avec l’ancien et le nouvel encodage.

Grâce à ce travail d’encodage, Vaλisp gagne en compacité et en vitesse : les entiers n’allouent plus de cellule, les symboles se comparent en O(1). Nous sommes maintenant prêts à manipuler un environnement lexical et à préparer le terrain pour un ramasse-miettes.