TD 2

Du parseur aux

environnements & fermetures lexicales

9 exercices pour ajouter variables, fonctions et listes à votre langage

Laurent Thiry — Programmation en C

« Une variable sans environnement, c'est comme un poisson sans vélo.
Ça peut exister mais c'est pas très utile. »

1 / 12

🗺️ Plan de la séance

  1. Évaluateur récursif — rappel du TD1 et généralisation
  2. Environnement — stocker des paires (nom, valeur)
  3. let — lier des variables
  4. set! — muter l'environnement
  5. lambda — créer des fermetures lexicales
  6. Listes — car, cdr, cons, null?
  7. Bonus — map, filter, fold maison
  8. Aller plus loin — Défis supplémentaires
  9. Sans filet — À vous de jouer
Aujourd'hui, on donne une mémoire à votre évaluateur. Ensuite, il va se souvenir de tout. Même de cette blague nulle. Surtout de cette blague nulle.
2 / 12

1. Évaluateur récursif généralisé ★☆☆

Reprenez l'évaluateur du TD1 et étendez-le pour gérer les sous-expressions arbitrairement imbriquées.

a) Nested eval

  1. Repartez de parseur.c (TD1 ex5–6)
  2. Faites en sorte que eval traite récursivement chaque argument
  3. Gérez +, -, *, / avec strcmp
  4. Vérifiez (* (+ 2 3) (- 10 4)) → 30

b) Détection d'erreurs

  1. Que se passe-t-il si on passe (+ 1 "hello") ?
  2. Ajoutez une vérification de type avant d'appliquer l'opérateur
  3. Affichez "Erreur de type" si un argument n'est pas un nombre

c) Opérateur unaire

  1. Ajoutez les opérateurs unaires neg (négation) et abs (valeur absolue)
  2. (neg 5) → -5, (abs -3) → 3
🐍 Voir la solution 
long long eval(Sexp *e) {
    if (e->type == SEXPR_INT) return e->entier;
    if (e->type != SEXPR_CONS || e->car->type != SEXPR_SYM) {
        fprintf(stderr, "Erreur de syntaxe\n");
        return 0;
    }
    char *op = e->car->symbole;
    Sexp *args = e->cdr;

    /* c) unaires */
    if (!strcmp(op, "neg")) return -eval(args->car);
    if (!strcmp(op, "abs")) {
        long long v = eval(args->car);
        return v < 0 ? -v : v;
    }

    long long val = eval(args->car);
    /* b) vérification de type */
    if (args->car->type != SEXPR_INT && args->car->type != SEXPR_CONS) {
        fprintf(stderr, "Erreur de type\n"); return 0;
    }
    for (args = args->cdr; args; args = args->cdr) {
        long long v = eval(args->car);
        if (!strcmp(op, "+")) val += v;
        else if (!strcmp(op, "-")) val -= v;
        else if (!strcmp(op, "*")) val *= v;
        else if (!strcmp(op, "/")) {
            if (v == 0) { fprintf(stderr, "/0 !\n"); return 0; }
            val /= v;
        }
    }
    return val;
}
💡 strcmp : retourne 0 quand les chaînes sont égales. C'est contre-intuitif — comme les panneaux « sens interdit » qui sont ronds.
3 / 12

2. Environnement ★★☆

Créez une structure pour stocker des associations nom → valeur.

a) Structure de base

  1. Définissez un struct Env avec une liste d'association et un parent
  2. Écrivez cherche_value qui parcourt les bindings
  3. Écrivez env_lookup qui cherche dans l'env (puis le parent, etc.)
  4. Testez avec quelques paires (x → 42)

b) Environnement chaîné

  1. Créez un environnement parent avec (x → 10, y → 20)
  2. Créez un environnement enfant vide
  3. Vérifiez que l'enfant voit les variables du parent

c) env_bind

  1. Écrivez void env_bind(Env *env, Sexp *sym, Sexp *val)
  2. Ajoute le binding dans l'environnement courant en tête de liste
  3. Testez : un binding dans l'enfant masque celui du parent
🐍 Voir la solution 
typedef struct Env {
    Sexp *bindings;
    struct Env *parent;
} Env;

Env *env_new(Env *parent) {
    Env *e = malloc(sizeof(Env));
    e->bindings = NULL;
    e->parent = parent;
    return e;
}

/* c) ajouter un binding */
void env_bind(Env *env, Sexp *sym, Sexp *val) {
    env->bindings = sexp_cons(
        sexp_cons(sym, val), env->bindings);
}

/* a) + b) lookup avec chaîne */
long long env_lookup(Sexp *sym, Env *env) {
    while (env) {
        Sexp *pair = cherche(sym, env->bindings);
        if (pair) return pair->cdr->entier;
        env = env->parent;
    }
    fprintf(stderr, "Variable %s inconnue\n", sym->symbole);
    return 0;
}
Un environnement sans parent, c'est comme un étudiant sans café : ça existe, mais c'est lent et ça manque d'énergie.
4 / 12

3. let — lier des variables ★★☆

Ajoutez la forme spéciale (let nom valeur) à votre évaluateur.

a) let simple

  1. Dans eval, si l'opérateur est "let", traitez-le spécialement
  2. Ajoutez le binding dans l'environnement courant
  3. Exemple : (let x 42) (+ x 1) → 43

b) let avec expression

  1. Étendez : (let x (+ 2 3)) — il faut évaluer la valeur avant de lier
  2. Testez : (let x (+ 2 3)) (* x 2) → 10

c) let séquentiel (let*)

  1. Implémentez (let* (x 1) (y (+ x 1)) (z (+ y 1)))
  2. Chaque binding voit les précédents : z → 3
🐍 Voir la solution 
if (!strcmp(op, "let")) {
    /* a) let simple */
    Sexp *sym = args->car;
    Sexp *val_expr = args->cdr->car;
    long long v = eval(val_expr, env);  /* b) évalue d'abord */
    env_bind(env, sym, sexp_int(v));
    return v;
}
if (!strcmp(op, "let*")) {
    /* c) let* : chaque binding voit les précédents */
    Sexp *bindings = args;
    long long last = 0;
    while (bindings) {
        Sexp *sym = bindings->car->car;
        Sexp *val_expr = bindings->car->cdr->car;
        last = eval(val_expr, env);
        env_bind(env, sym, sexp_int(last));
        bindings = bindings->cdr;
    }
    return last;
}
💡 L'ordre compte : évaluez d'abord l'expression, puis ajoutez le binding. Si vous faites l'inverse, vous risquez de voir la variable dans la définition… comme en Python ! (Noooon, pas Python !)
5 / 12

4. set! — mutation ★★☆

Ajoutez (set! nom nouvelle_valeur) pour modifier un binding existant.

a) set! simple

  1. Parcourez l'environnement pour trouver le symbole
  2. Remplacez sa valeur (ou créez-le s'il n'existe pas)
  3. Testez : (let x 10) (set! x 42) x → 42

b) set! dans le parent

  1. Créez un environnement parent avec let et un enfant
  2. Vérifiez que set! dans l'enfant modifie la variable du parent
  3. Testez : (let x 10) (let f (lambda () (set! x 20))) (f) x → 20

c) set! avec cellules

  1. Utilisez cell et cell-ref (voir TD3) pour simuler une mutation
  2. (let c (cell 5)) (cell-ref c) → 5
🐍 Voir la solution 
if (!strcmp(op, "set!")) {
    Sexp *sym = args->car;
    Sexp *val_expr = args->cdr->car;
    long long v = eval(val_expr, env);

    Env *e = env;
    while (e) {                           /* b) remonte la chaîne */
        Sexp *pair = cherche(sym, e->bindings);
        if (pair) {
            sexp_free(pair->cdr);
            pair->cdr = sexp_int(v);
            return v;
        }
        e = e->parent;
    }
    fprintf(stderr, "set! : %s non trouvé\n", sym->symbole);
    return 0;
}
⚠️ set! vs let : let crée un nouveau binding, set! modifie un existant. C'est la différence entre écrire dans un cahier neuf et corriger une faute dans un cahier déjà rempli.
6 / 12

5. lambda — fermetures lexicales ★★★

Créez des fonctions anonymes qui capturent l'environnement courant.

a) Fermeture simple

  1. Représentez une fermeture par une liste dans une S-expression : (fun (x) (* x x) . env_snapshot)
  2. Écrivez make_closure qui gèle l'environnement
  3. apply_closure : crée un nouvel env, lie params→args, évalue le corps

b) Fonction d'ordre supérieur

  1. Testez : (let carre (lambda (x) (* x x))) (carre 5) → 25
  2. Créez (map (lambda (x) (* x 2)) '(1 2 3))

c) Compteur lexical

  1. Créez une fonction make-compteur qui renvoie une closure avec une variable interne
  2. Chaque appel incrémente et retourne le compteur
🐍 Voir la solution 
static Sexp *make_closure(Sexp *params, Sexp *body, Env *env) {
    Sexp *snap = NULL;
    for (Env *e = env; e; e = e->parent)
        snap = sexp_cons(e->bindings ? sexp_copie(e->bindings) : NULL, snap);
    return sexp_cons(sexp_sym("fun"),
                sexp_cons(params,
                    sexp_cons(body, snap)));
}

if (!strcmp(op, "lambda")) {
    return make_closure(args->car, args->cdr->car, env);
}

if (fn->type == SEXPR_CONS && fn->car->type == SEXPR_SYM
    && !strcmp(fn->car->symbole, "fun")) {
    return apply_closure(fn, args, env);
}

/* c) make-compteur en LISP */
;; (let make-compteur
;;   (lambda ()
;;     (let compteur 0)
;;     (lambda () (set! compteur (+ compteur 1)) compteur)))
Les fermetures, c'est comme un tupperware : ça garde votre environnement au frais jusqu'à ce que vous en ayez besoin. Et ça ne fuit pas (en principe).
7 / 12

6. Listes — car, cdr, cons ★★☆

Ajoutez les primitives de manipulation de listes.

a) Primitives de base

  1. (car '(1 2 3)) → retourne le premier élément
  2. (cdr '(1 2 3)) → retourne le reste
  3. (cons 1 '(2 3)) → construit une nouvelle paire
  4. (null? '(1 2)) → faux, (null? '()) → vrai

b) Longueur et append

  1. Implémentez length : (length '(1 2 3)) → 3
  2. Implémentez append : (append '(1 2) '(3 4)) → (1 2 3 4)

c) Reverse et nth

  1. Implémentez reverse : (reverse '(1 2 3)) → (3 2 1)
  2. Implémentez nth : (nth 1 '(a b c)) → b (indexation 0-based)
🐍 Voir la solution 
/* a) primitives */
if (!strcmp(op, "car")) {
    Sexp *lst = eval(args->car, env);
    return lst ?& lst->car : NULL;
}
if (!strcmp(op, "cdr")) {
    Sexp *lst = eval(args->car, env);
    return lst ?& lst->cdr : NULL;
}
if (!strcmp(op, "cons")) {
    return sexp_cons(eval(args->car, env),
                      eval(args->cdr->car, env));
}
if (!strcmp(op, "null?")) {
    Sexp *v = eval(args->car, env);
    return sexp_int(v == NULL || (v->type == SEXPR_CONS && v->car == NULL));
}

/* b) length, append en C (ou en LISP, au choix) */
if (!strcmp(op, "length")) {
    Sexp *lst = eval(args->car, env);
    int n = 0;
    while (lst && lst->type == SEXPR_CONS) { n++; lst = lst->cdr; }
    return sexp_int(n);
}

/* c) reverse : itératif */
if (!strcmp(op, "reverse")) {
    Sexp *lst = eval(args->car, env);
    Sexp *res = NULL;
    while (lst && lst->type == SEXPR_CONS) {
        res = sexp_cons(lst->car, res);
        lst = lst->cdr;
    }
    return res;
}
💡 Quote : '(1 2 3) est du sucre syntaxique pour (quote (1 2 3)). sexp_parse le gère déjà. Si car est "quote", retournez args->car sans l'évaluer.
8 / 12

7. Bonus — map, filter, fold ★★★

Écrivez des fonctions LISP qui manipulent des listes.

a) map

  1. Implémentez (map f '(1 2 3)) en LISP
  2. Testez : (map (lambda (x) (* x x)) '(1 2 3 4)) → (1 4 9 16)

b) filter

  1. Implémentez filter : garde les éléments qui satisfont un prédicat
  2. (filter (lambda (x) (> x 2)) '(1 2 3 4)) → (3 4)

c) foldl

  1. Implémentez foldl : (foldl + 0 '(1 2 3)) → 6
  2. Utilisez-le pour implémenter sum et product
🐍 Voir la solution 
;; a) map
(let map
  (lambda (f lst)
    (if (null? lst) '()
      (cons (f (car lst)) (map f (cdr lst))))))

;; b) filter
(let filter
  (lambda (pred lst)
    (if (null? lst) '()
      (if (pred (car lst))
        (cons (car lst) (filter pred (cdr lst)))
        (filter pred (cdr lst))))))

;; c) foldl
(let foldl
  (lambda (f acc lst)
    (if (null? lst) acc
      (foldl f (f acc (car lst)) (cdr lst)))))

(let sum (lambda (lst) (foldl + 0 lst)))
(let product (lambda (lst) (foldl * 1 lst)))
Vous venez de réinventer une partie de la bibliothèque standard de presque tous les langages fonctionnels. Prenez un moment pour vous sentir supérieur aux développeurs Java.
9 / 12

8. Aller plus loin ★★★

Défis supplémentaires pour enrichir votre langage. Solutions fournies.

🔧 function récursive

Ajoutez (function nom (params) corps) qui crée une fonction récursive en liant nom dans l'environnement de la fermeture.

(function fact (n) (if (= n 1) 1 (* n (fact (- n 1)))))

🔧 begin et if

(begin expr1 expr2 ...) évalue chaque expression et retourne la dernière.

(if cond then else) — n'évaluer que la branche choisie.

Testez : (if (> 3 2) 42 0) → 42

🔧 eq?

Comparaison de symboles ou d'entiers.

(eq? 'a 'a) → vrai, (eq? 42 42) → vrai

🔧 and / or / not

Opérateurs logiques, avec court-circuit.

(and (> 3 2) (< 5 10)) → 1 (vrai)

🐍 Voir la solution 
;; function récursive
(let fact
  (function fact (n)
    (if (eq? n 1) 1
      (* n (fact (- n 1))))))

;; if dans eval :
if (!strcmp(op, "if")) {
    long long cond = eval(args->car, env);
    Sexp *branch = cond ? args->cdr->car : args->cdr->cdr->car;
    return eval(branch, env);
}

;; begin
if (!strcmp(op, "begin")) {
    Sexp *cur = args;
    long long last = 0;
    while (cur) { last = eval(cur->car, env); cur = cur->cdr; }
    return last;
}
Le if paresseux, c'est comme un étudiant le lundi matin : il n'évalue que ce qui est vraiment nécessaire et ignore le reste.
10 / 12

9. Sans filet ★★★

⚠️ Pas de solution fournie. Ces exercices sont pour ceux qui veulent vraiment maîtriser le sujet. Inspirez-vous de let.c si vous êtes bloqué.

🧮 Quicksort en LISP

Implémentez quicksort dans ./let en utilisant uniquement des fonctions récursives (pas de boucle).

Algorithme :

  1. Choisir un pivot (le premier élément)
  2. Filtrer les éléments ≤ pivot à gauche
  3. Filtrer les éléments > pivot à droite
  4. Trier récursivement les deux parties et concaténer

Indice

🏗️ letrec

Implémentez (letrec bindings corps) qui permet des définitions récursives et mutuellement récursives.

Contrairement à let, letrec évalue les bindings dans un environnement où tous les noms sont déjà visibles.

(letrec ((pair (cons 1 2))) pair)

✏️ Défi bonus : Écrivez un interpréteur Brainfuck en C de moins de 200 lignes qui utilise un tableau de 30000 octets comme mémoire. Entrée/sortie via getchar/putchar.
11 / 12

TD 2 — Terminé !

Votre évaluateur sait maintenant : lier des variables (let),
les modifier (set!), créer des fonctions (lambda),
et manipuler des listes (car, cdr, cons).

📄 Fichier clé
evalenv.c — votre évaluateur enrichi
📚 Prochaine séance
TD 3 — Cellules, objets, natives & sauvegarde
🔑 Mots-clés
environnement, fermeture, lambda, liste, récursion
Les fermetures, c'est comme les valises : plus vous en avez, plus vous pouvez emporter de trucs. Mais à un moment, faut les ouvrir.
« Un environnement, c'est juste une mémoire qui n'oublie pas. Enfin, sauf si vous faites un free(). »
12 / 12
© 2026 laurent.thiry@uha.fr
1 2 3 4 5 6 7 8 9 10 11 12