Des listes aux tables, des tables aux templates, des templates au chatbot. Parce que la factorielle, c'est bien, mais publipostage et IA low-cost, c'est mieux.
Au cours précédent, on a construit un parseur de s-expressions (merci LISP) et un évaluateur arithmétique. On avait une calculette en ligne de commande, c'était déjà pas mal.
Maintenant, on veut aller plus loin. On veut manipuler des tables de données — comme dans un tableur ou une base de données — mais en ligne de commande, en C, avec des parenthèses. Parce que pourquoi faire simple ?
Le fil rouge : on commence par des trucs simples (multiplier tous les éléments d'une liste par k, filtrer les valeurs < k), on passe aux tables (filtre sur une colonne, projection), on invente les templates (des motifs nommés avec évaluation d'expressions), et on finit par imaginer un mini chatbot dont le moteur est… un template.
Tout notre travail repose sur une bibliothèque maison,
sexpression.h / sexpression.c.
Elle définit le type Sexp (pour
S-expression) et les opérations de base.
Un Sexp peut être :
SEXPR_INT) — avec une valeur entierSEXPR_SYM) — avec une chaîne symboleSEXPR_CONS) — avec car et cdr, qui sont eux-mêmes des Sexptypedef struct Sexp { int type; int entier; char *symbole; struct Sexp *car; struct Sexp *cdr; } Sexp;
Les constructeurs sont simples :
sexp_int(v) — crée un entiersexp_sym("truc") — crée un symbole (avec copie de la chaîne)sexp_cons(a, b) — crée une paire de deux Sexp
La liste (1 2 3) est représentée par
cons(1, cons(2, cons(3, NULL))).
La liste vide, c'est NULL.
Tout est dans la convention.
La fonction sexp_parse prend une chaîne comme
"(+ 2 (* 3 4))" et construit l'arbre Sexp correspondant.
C'est un parseur récursif descendant — il lit les parenthèses
et construit des cons cells au fur et à mesure.
Le cœur du parseur :
static Sexp *parse_depuis(Parseur *p) { if (strcmp(p->token, "(") == 0) { prochain_token(p); Sexp *tete = NULL, *cur = NULL; while (strcmp(p->token, ")") != 0) { Sexp *item = parse_depuis(p); Sexp *cell = sexp_cons(item, NULL); if (!tete) { tete = cell; cur = cell; } else { cur->cdr = cell; cur = cell; } } prochain_token(p); return tete; } // atome → entier ou symbole return est_nombre(tok) ? sexp_int(atoi(tok)) : sexp_sym(tok); }
À l'époque, on l'avait écrit pour la calculette. Maintenant, il nous sert à lire des données, des templates, des requêtes… C'est ça, la réutilisabilité.
zip prend deux listes de même longueur et les
fusionne en une liste d'association :
zip((x y z), (1 2 3)) → ((x 1) (y 2) (z 3))
Sexp *zip(Sexp *a, Sexp *b) { if (!a || !b) return NULL; Sexp *ca = a->car, *cb = b->car; Sexp *ac = (ca->type == SEXPR_INT) ? sexp_int(ca->entier) : sexp_sym(ca->symbole); Sexp *bc = (cb->type == SEXPR_INT) ? sexp_int(cb->entier) : sexp_sym(cb->symbole); return sexp_cons(sexp_cons(ac, sexp_cons(bc, NULL)), zip(a->cdr, b->cdr)); }
cherche parcourt une liste d'association pour trouver
la valeur d'un symbole. evaluer utilisecherche
pour évaluer une expression dans un environnement.
// chercher la valeur de 'x' dans ((x 1) (y 2)) → 1 Sexp *cherche(Sexp *key, Sexp *alist) { while (alist && alist->type == SEXPR_CONS) { Sexp *entree = alist->car; if (entree && entree->car->type == SEXPR_SYM && key->type == SEXPR_SYM && strcmp(entree->car->symbole, key->symbole) == 0) return entree->cdr->car; alist = alist->cdr; } return NULL; }
evaluer prend une expression et un environnement.
Si l'expression est un entier, on le renvoie.
Si c'est un symbole, on cherche sa valeur dans l'environnement.
Si c'est une liste, le premier élément est l'opérateur :
if (strcmp(op->symbole, "+") == 0) return sexp_int(vg + vd); if (strcmp(op->symbole, "*") == 0) return sexp_int(vg * vd); // ... et <, >, =, and, or, not ...
cherche est une fonction de 15 lignes qui fait
le même boulot qu'une base de données relationnelle.
La différence, c'est que la base a 40 ans de développement
et 1500 pages de documentation. Nous, on a 15 lignes et
on est fiers. Mais les deux font la même chose : trouver
une valeur à partir d'une clé. C'est beau, l'abstraction.
L'étape suivante, c'est de passer des listes simples (comme
(1 2 3 4 5)) à des tables (comme
((x y) (1 1) (2 1) (3 2))).
Une table est une liste dont le premier élément est la ligne
d'en-tête, et les suivants sont les lignes de données.
On commence par deux petits programmes qui manipulent des listes simples (pas de tables encore) :
// ./mapk 3 → (3 6 9 12 15 18 21 24 27 30) Sexp *liste = sexp_parse("(1 2 3 4 5 6 7 8 9 10)"); while (cur) { Sexp *nv = sexp_int(cur->car->entier * k); sexp_cons(nv, ...) cur = cur->cdr; }
// ./filterk 5 → (1 2 3 4) Sexp *liste = sexp_parse("(1 2 3 4 5 6 7 8 9 10)"); while (cur) { if (cur->car->entier < k) { // garder } cur = cur->cdr; }
Ces deux programmes sont intentionnellement simples. Leur but n'est pas d'impressionner, mais de montrer comment on parcourt une liste Sexp et comment on en construit une nouvelle.
Une liste d'association (alist) est
une liste de paires clé-valeur. En LISP, c'est la structure
de données la plus naturelle pour représenter un dictionnaire.
alist.c combine zip et cherche :
zip((x y z), (10 20 30)) → ((x 10) (y 20) (z 30)) cherche(y, ((x 10) (y 20) (z 30))) → 20
C'est avec zip qu'on crée un
environnement à partir des en-têtes
de colonnes et des valeurs d'une ligne. Et c'est avec
cherche qu'on retrouve la valeur d'une variable
dans cet environnement. Deux fonctions. Toute la suite.
zip
pour qu'il partage les atomes au lieu de les copier. On économiserait
de la mémoire et du temps, mais on devrait faire attention à ne
pas libérer l'environnement avant d'avoir fini d'utiliser les valeurs.
C'est un compromis classique en C : sécurité vs performance.
evalenv.c met tout ensemble. On crée un environnement
fixe avec zip, on évalue une expression avec
evaluer :
// ./evalenv '(+ x y)' Sexp *cles = sexp_parse("(x y)"); Sexp *vleurs = sexp_parse("(10 20)"); Sexp *env = zip(cles, vleurs); Sexp *expr = sexp_parse(argv[1]); Sexp *res = evaluer(expr, env); sexp_print(res); // → 30
C'est simple. C'est court. C'est le moteur de tout ce qui va suivre. Un environnement, c'est juste une alist. Une alist, c'est juste une liste de paires. Et évaluer, c'est juste chercher et calculer. Les gros mots (moteur de base de données, interpréteur, IA) cachent souvent des mécanismes très simples.
Une table, dans notre format, c'est simplement :
((col1 col2) (val11 val12) (val21 val22) …)
La première liste est l'en-tête. Les suivantes sont les lignes.
Pas de SQL, pas de CSV, pas de JSON. Des parenthèses. Point.
filter_table prend une table, un nom de colonne,
un opérateur et une valeur, et retourne les lignes qui satisfont
la condition. C'est un SELECT … WHERE … en 40 lignes :
Sexp *filter_table(Sexp *table, Sexp *col, Sexp *op, Sexp *val) { Sexp *headers = table->car; Sexp *rows = table->cdr; Sexp *result = NULL, *last = NULL; while (rows) { Sexp *env = zip(headers, rows->car); Sexp *cond = sexp_parse( "(" op_str " (?" col_str ") " val_str ")"); ... } }
L'astuce, c'est qu'on construit une expression Sexp à partir du nom de colonne et de la valeur, et on l'évalue dans l'environnement de la ligne. Si le résultat est vrai (≠ 0), on garde la ligne.
| Appel | Résultat |
|---|---|
filter_table(t, "y", "=", 1) | ((x y) (1 1) (2 1)) |
filter_table(t, "x", ">", 2) | ((x y) (3 2) (4 3) (5 5)) |
SELECT * FROM t WHERE y = 1, on écrit
filter_table(t, "y", "=", 1).
C'est moins joli, mais ça compile avec gcc -std=c99,
pas besoin d'installer PostgreSQL. Et on peut le mettre dans
un pipeline shell. Prends ça, SQLite.
La projection (ou SELECT colonnes
en SQL) consiste à évaluer une liste d'expressions pour chaque
ligne et à produire une nouvelle table avec les colonnes calculées.
Sexp *project_table(Sexp *table, Sexp *exprs) { // exprs = ((+ x y) (- x y) ...) // Pour chaque ligne, évalue chaque expression dans l'environnement // Retourne une nouvelle table sans noms de colonnes }
L'avantage par rapport à filter_table : on peut
calculer des nouvelles colonnes à partir des existantes.
(+ x y), (* x 2), etc.
C'est la première brique d'un vrai langage de requêtes.
((nom expr) …)
au lieu d'une liste d'expressions. C'est exactement ce qu'on
va faire avec les templates. La project_table, c'est le template
sans les noms. Le template, c'est la project_table avec des noms.
Tout s'emboîte.
On arrive au plat de résistance. Un template est un motif qui mêle du texte fixe et des expressions à évaluer. Pour chaque ligne d'une table, on crée une version remplie du motif.
Concrètement, (x vaut (x) et xy vaut (+ x y)) veut dire :
« pour chaque ligne, affiche 'x vaut', puis la valeur de la colonne x,
puis 'et xy vaut', puis la valeur de (x + y) ».
Le template a une structure plate :
(nom1 vaut expr1 et nom2 vaut expr2 …)
Les vaut et et sont des mots-clés
(littéraux), les nom sont des symboles qui
deviendront les noms des colonnes de sortie, les
expr sont des expressions évaluées
dans l'environnement de la ligne courante.
Quand une expression est une liste d'un seul symbole comme
(x), on la déplie en x pour que
l'évaluateur la traite comme une variable.
paires_template prend le template brut (une liste
plate) et en extrait les paires ((nom1 expr1) (nom2 expr2) …)
en ignorant les mots-clés vaut et et :
while (tmpl) { Sexp *nom = tmpl->car; // x tmpl = tmpl->cdr; // → (vaut (x) et ...) tmpl = tmpl->cdr; // saute 'vaut' → ((x) et ...) Sexp *expr = tmpl->car; // (x) ou (+ x y) // (x) → x pour les références à une variable if (expr->type == SEXPR_CONS && !expr->cdr && expr->car->type == SEXPR_SYM) expr = expr->car; sexp_cons(sexp_copie(nom), sexp_cons(sexp_copie(expr), NULL)); // saute 'et' entre deux clauses if (tmpl && tmpl->cdr && … strcmp(…, "et") == 0) tmpl = tmpl->cdr; }
On copie les noms et les expressions avec
sexp_copie pour que les paires soient
indépendantes du template original. Sinon, libérer
l'un libérerait l'autre — double free assuré.
eval_template prend une table et un template,
et pour chaque ligne :
zipevaluer(nom vaut val et nom vaut val …)Sexp *env = zip(headers, rows->car); Sexp *row = NULL, *rcur = NULL; Sexp *p = paires; while (p) { Sexp *nom = p->car->car; Sexp *expr = p->car->cdr->car; Sexp *val = evaluer(expr, env); // on ajoute (nom vaut val) à la liste de sortie sexp_cons(sexp_copie(nom), …) sexp_cons(sexp_sym("vaut"), …) sexp_cons(val, …) // insère 'et' entre les clauses if (p) sexp_cons(sexp_sym("et"), …) p = p->cdr; }
Résultat pour notre table de test :
table : ((x y) (1 1) (2 1) (3 2) (1 3) (4 3) (5 5) (0 4))
tmpl : (x vaut (x) et xy vaut (+ x y))
res : ((x vaut 1 et xy vaut 2) (x vaut 2 et xy vaut 3)
(x vaut 3 et xy vaut 5) (x vaut 1 et xy vaut 4)
(x vaut 4 et xy vaut 7) (x vaut 5 et xy vaut 10)
(x vaut 0 et xy vaut 4))
gcc, make, et une
fierté démesurée. Et ça marche dans un terminal.
Une fois qu'on a appliqué un template, on peut vouloir extraire les valeurs à partir du résultat et d'un nouveau template qui sert de « masque d'extraction ». C'est l'opération inverse.
L'idée : si on a (x vaut (v1) et xy vaut (v2))
comme masque, et qu'on reçoit (x vaut 1 et xy vaut 2),
on peut en extraire v1 = 1 et v2 = 2.
En répétant sur toutes les lignes, on reconstruit une table.
On parcourt le masque pour trouver les (sym) —
des listes d'un seul symbole qui indiquent où se trouvent
les valeurs et comment les nommer :
while (tmpl) { if (tmpl->car->type == SEXPR_CONS // c'est une liste && !tmpl->car->cdr // d'un seul élément && tmpl->car->car->type == SEXPR_SYM) { // qui est un symbole // → on a trouvé un placeholder! sexp_copie(tmpl->car->car) // nom du placeholder } tmpl = tmpl->cdr; }
Ensuite, on parcourt les lignes et le masque en parallèle.
Quand le masque a une sous-liste (v1), la
ligne a une valeur à la même position. On collecte ces
valeurs pour former une nouvelle table :
Sexp *inverse_template(Sexp *res_liste, Sexp *tmpl) { Sexp *noms = noms_placeholders(tmpl, &nph); // noms = (v1 v2) for (chaque ligne dans res_liste) { // parcours masque et ligne en parallèle while (t && row_in) { if (t->car est un placeholder) { // extraire la valeur à la même position dans row_in sexp_int(row_in->car->entier) } t = t->cdr; row_in = row_in->cdr; } } return sexp_cons(noms, rows_out); // ((v1 v2) (1 2) …) }
Résultat :
res : ((x vaut 1 et xy vaut 2) (x vaut 2 et xy vaut 3) …) tmpl_inv: (x vaut (v1) et xy vaut (v2)) table : ((v1 v2) (1 2) (2 3) (3 5) (1 4) (4 7) (5 10) (0 4))
On a bien retrouvé une table structurée à partir d'une liste de templates évalués. Template + inverse template = identité (modulo le renommage des colonnes).
vaut et et).
À la fin, on a les cadeaux rangés dans un tableau Excel.
Enfin, dans une liste de listes de Sexp.
C'est pareil.
On a maintenant tous les ingrédients pour construire un mini moteur de chatbot. Le principe est simple : au lieu d'avoir une table de nombres, on a une table de chaînes. Au lieu d'évaluer des expressions arithmétiques, on évalue des substitutions de variables.
On définit une « base de connaissances » sous forme de table associative :
((pattern) (reponse))
(("(bonjour je m appelle (nom))") ("(bonjour (nom) !)"))
(("(quel age as tu)") ("(je suis ne en 2026)"))
(("(au revoir)") ("(a bientot (nom) !)"))
Quand on reçoit une entrée, on cherche un pattern qui
correspond. Le pattern (bonjour je m appelle (nom))
contient le placeholder (nom). L'entrée
(bonjour je m appelle Alice) matche, et on
extrait nom = Alice.
Ensuite, on applique le template de réponse
(bonjour (nom) !) avec nom = Alice
→ (bonjour Alice !).
inverse_template avec le pattern pour extraire
les valeurs.eval_template avec la réponse comme template,
en utilisant les valeurs extraites comme environnement.
Voici à quoi pourrait ressembler le moteur :
// 1. Base de connaissances : une table de paires (pattern . reponse) Sexp *base = sexp_parse("((pattern reponse) (((bonjour je m appelle (nom))) ((bonjour (nom) !))) (((quel age as tu)) ((je suis ne en 2026))) (((au revoir)) ((a bientot (nom) !))))"); // 2. Entrée utilisateur Sexp *entree = sexp_parse("(bonjour je m appelle Bob)"); // 3. Pour chaque règle : inverser, puis appliquer for (chaque règle) { // 3a. Pattern → extraction de variables Sexp *vars = inverse_template(entree, pattern); // vars = ((nom) (Bob)) ? Ou mieux : ((nom Bob)) // 3b. Si vars non NULL : pattern matché ! // 3c. Réponse → template avec les variables extraites Sexp *reponse = eval_template(vars, template_reponse); // reponse = (bonjour Bob !) }
Évidemment, c'est une version simplifiée. Il faudrait :
_ (underscore) qui matche
n'importe quelle valeur sans l'extraire. Utile pour des
patterns du genre (je veux _ s il vous plait) →
on se fiche de ce qu'il veut, on répond juste
(voila).
(vous avez dit (x) ? repondez : (x)) →
on répète ce que l'utilisateur a dit, façon perroquet.
sexp_parse
peut lire depuis une chaîne, il suffit de charger
le fichier en mémoire avec fread ou
fgets. Faire évoluer les réponses sans
recompiler le programme — c'est ça, la flexibilité.
Ce qu'on a vu dans ce cours :
| Fichier | Concept |
|---|---|
mapk.c | Parcourir une liste, en créer une nouvelle |
filterk.c | Filtrer une liste selon une condition |
alist.c | Liste d'association, zip, cherche |
evalenv.c | Évaluation dans un environnement |
table.c | filter_table — WHERE en s-expressions |
project.c | project_table — expressions calculées |
template.c | Template nommé → publipostage |
untemplate.c | Inverse → extraction de valeurs |
sexpression.h/c | Bibliothèque commune : types, parse, zip, cherche, evaluer, copie |
| Terme | Définition |
|---|---|
| S-expression | Notation parenthésée (LISP) pour représenter données et code |
| Cons cell | Paire (car . cdr) — brique de base des listes chaînées |
| Liste d'association | Liste de paires clé-valeur, utilisée comme dictionnaire |
| Environnement | Mapping variable → valeur (implémenté comme une alist) |
| Template | Motif avec espaces réservés, évalué dans un environnement |
| Placeholder | Variable dans un template, notée (sym) dans notre format |
| Zip | Fusion point par point de deux listes en une alist |
| Copie défensive | Copier les données pour éviter les doubles free |
| Double free | Libérer deux fois la même mémoire → crash |
La progression est claire : on est partis de listes d'entiers
(mapk, filterk), on a ajouté des clés (alist), on a enrobé
le tout en tables (filter_table, project_table), on a nommé
les colonnes (template), et on a rendu l'opération réversible
(untemplate). Chaque étape ajoute une couche d'abstraction
sans changer le moteur fondamental : zip +
cherche + evaluer.
Pistes pour la suite :
JOIN SQL en s-expressions)factorielle(5) = 120 il y a
trois cours. On termine avec une architecture de chatbot,
un moteur de publipostage, et des bases de données en
s-expressions. Si vous aviez dit ça à votre prof de maths
préféré, il vous aurait ri au nez. Mais le C, c'est comme
les Legos : avec 3 types de briques, on construit une fusée.
Ou un chatbot qui répond « (bonjour Bob !) ».
C'est déjà pas mal pour un mardi soir.