Contexte et objectifs

L’auteur a reçu un exercice de structures de données consistant à transformer une expression arithmétique en arbre binaire et à en calculer le résultat. Plutôt que de se limiter à l’évaluation, il a choisi de créer un petit langage fonctionnel, incluant variables, fonctions, un REPL et un FFI, le tout écrit en C.

Architecture du langage

Le cœur du système repose sur une représentation d’expression sous forme d’arbre abstrait (AST). Le type Node est une union discriminée :

typedef enum { LITERAL, VAR, FUNC } NodeType;
struct Node {
    struct Node *left;
    struct Node *right;
    union {
        int literal;
        char *var;
        char *func;
    } data;
    NodeType type;
};

Chaque nœud occupe 32 octets sur une architecture 64 bits (8 B pour chaque pointeur, 8 B pour l’union, 4 B pour l’enum, 4 B de remplissage). L’auteur montre que l’évaluation de 1+1 nécessite trois nœuds, soit 96 B d’espace brut. Cependant, chaque appel à malloc ajoute 16 B d’en‑tête, portant le coût réel à 48 B par nœud et 144 B pour l’expression complète.

Gestion de la mémoire

Face à la fragmentation induite par de nombreuses petites allocations, l’auteur implémente un allocateur de type arena. Le principe consiste à réserver un bloc contigu de taille fixe (exemple : #define SIZE 1024 Node arena[SIZE]) et à distribuer les nœuds en incrémentant un indice top. La fonction d’allocation devient alors :

Node *allocNode() {
    return &arena[top++];
}

Cette approche élimine l’en‑tête de malloc, réduit le coût mémoire et accélère les allocations, au prix d’une libération globale à la fin de l’exécution.

Fermetures et table d’environnement

Les fonctions sont traitées comme des valeurs de première classe. Au lieu d’utiliser des pointeurs de fonctions C, chaque fonction est stockée sous forme de nœud contenant le paramètre et le corps de l’AST, ce qui permet de les passer, de les retourner et de les évaluer ultérieurement. L’environnement associe des noms à des nœuds via une table de hachage implémentée manuellement, car le C ne fournit pas de structure native. Cette table gère à la fois les variables et les fonctions, rendant possible la création de fermetures qui capturent leur environnement lexical.

Analyse des limites et perspectives

Le modèle présenté fonctionne pour des programmes très simples, mais plusieurs contraintes apparaissent. L’arène a une taille fixe ; dépasser SIZE provoquerait un débordement sans mécanisme de reallocation. L’absence de ramasse‑miettes signifie que les nœuds alloués restent en mémoire jusqu’à la libération de l’arène, ce qui peut entraîner une utilisation excessive pour des programmes longs. Le code ne gère pas encore les variables locales ni les captures d’environnement dans les fermetures, ce qui limite la portée des fonctions définies par l’utilisateur. Enfin, le REPL et le FFI restent à implémenter, ce qui serait nécessaire pour interagir avec du code C existant.