Cours 5 — S-expressions

Environnements, fermetures lexicales, cellules mutables, objets par passage de messages, listes, et transpilation LISP → Python.

1. Rappel : les S-expressions et leurs limites

Depuis le cours 3, la bibliothèque sexpression.h/.c permet de parser et évaluer des S-expressions. La fonction evaluer gère les opérateurs arithmétiques, les listes, et les formes spéciales de base.

/* Ce qui fonctionne avec evaluer() de la bibliothèque */
(+ 1 2)               → 3
(car (quote (a b)))   → a
(if 1 2 3)            → 2

/* Ce qui ne fonctionne PAS : */
(let x 42)            ; pas de variable
(+ x 1)               ; x n'existe pas
(function f (n) ...)  ; pas de fonction

Problème : evaluer ne garde aucune trace des évaluations précédentes. Chaque appel repart de zéro. Pour aller plus loin, il faut un environnement : une structure qui retient les associations nom → valeur.

1.1 Architecture du programme let.c

Le fichier let.c (environ 580 lignes) étend la bibliothèque Sexp avec des environnements chaînés, des closures, des cellules mutables, et des opérations sur listes. Contrairement à calc.c qui compile vers la VM, let.c est un interprète complet : il évalue les expressions directement dans une boucle REPL ou en ligne de commande.

2. Environnements chaînés

Un environnement est une table d'association (symbole . valeur) organisée en chaîne. Chaque nouveau let empile une nouvelle portée. La recherche remonte la chaîne jusqu'à trouver le symbole.

2.1 Structure Env

typedef struct Env Env;
struct Env {
    Sexp *bindings;  /* alist : ((sym val) …) */
    Env  *parent;    /* portée englobante */
};

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

/* Exemple de chaîne : */
[2] ((x 10) (y 20))
       ↑ parent
[1] ((z 100))
       ↑ parent
[0] ()    ← globale

2.2 Recherche : env_lookup

Parcourt la chaîne d'environnements en remontant les parents. Retourne la première liaison trouvée (résolution lexicale).

static Sexp *env_lookup(Env *env, Sexp *key) {
    while (env) {
        Sexp *v = cherche(key, env->bindings);
        if (v) return v;    /* trouvé dans cette portée */
        env = env->parent;  /* remonte d'un niveau */
    }
    return NULL;          /* pas trouvé → erreur */
}

La fonction cherche de la bibliothèque parcourt une liste d'association :

Sexp *cherche(Sexp *key, Sexp *alist) {
    while (alist) {
        if (key->entier == alist->car->car->entier)
            return alist->car->cdr->car;
        alist = alist->cdr;
    }
    return NULL;
}

3. let — lier une variable

(let x 42) crée une nouvelle portée avec la liaison x = 42 et retourne la valeur. Le nouvel environnement devient l'environnement courant pour les expressions suivantes.

3.1 Code

if (strcmp(name, "let") == 0) {
    Sexp *sym = args->car;
    Sexp *val = evaluer_env(
        args->cdr->car, env);
    Env *local = env_new(*env);
    local->bindings = sexp_cons(
        sexp_cons(
            sexp_copie(sym),
            sexp_cons(stored, NULL)),
        local->bindings);
    *env = local;
    return sexp_copie(stored);
}

3.2 Exemple pas à pas

$ ./let '(let x 42)' '(+ x 1)' '(let y (* x 2))'
; État initial       : env: [0] ()
; (let x 42)          → 42  | env: [0] (x 42) parent: [1] ()
; (+ x 1)             → 43  | env inchangé
; (let y (* x 2))     → 84  | env: [0] (y 84) parent: [1] (x 42) parent: [2] ()

Chaque let empile une portée. L'environnement est une pile de dictionnaires. La recherche commence toujours par la portée la plus récente.

4. set! — muter une liaison

(set! x 43) modifie la valeur de la liaison existante la plus proche dans la chaîne d'environnements.

4.1 Deux cas de mutation

set! a deux comportements selon le type de la valeur stockée :

;; mutation d'une liaison simple
(let x 42)    ; x → 42
(set! x 100)  ; x → 100 (remplace dans l'alist)

;; mutation d'une cellule
(let c (cell 10))  ; c → #<cell:10>
(set! c 42)        ; cell:10 → cell:42
(cell-ref c)       ; → 42

4.2 Détection dans le code

for (Env *e = *env; e; e = e->parent) {
    Sexp *v = cherche(sym, e->bindings);
    if (v) {
        if (v->type == SEXPR_CELL) {
            v->cell->value = new_val->entier;
            sexp_free(new_val);
        } else {
            /* remplace dans l'alist */
        }
        return ...;
    }
}
/* si on arrive ici : x n'existe dans aucun env */
fprintf(stderr, "ERREUR: set! symbole inconnu\n");

5. Fermetures lexicales (closures)

Une closure est une fonction accompagnée de l'environnement dans lequel elle a été créée. C'est le mécanisme qui permet de « capturer » des variables.

5.1 Représentation

Dans let.c, une closure est représentée par une liste S-expression :

(fun (params) corps snapshot_env)

Avec les accesseurs suivants :

static int is_closure(Sexp *v) {
    return v && v->type == SEXPR_CONS
        && v->car->type == SEXPR_SYM
        && strcmp(v->car->symbole, "fun") == 0;
}

static Sexp *closure_params(Sexp *c) { return c->cdr->car; }
static Sexp *closure_body(Sexp *c)   { return c->cdr->cdr->car; }
static Sexp *closure_env(Sexp *c)   { return c->cdr->cdr->cdr->car; }

5.2 Snapshot d'environnement

Quand on crée une closure, on fige la chaîne d'environnements. Le snapshot est une copie profonde des bindings, stockée dans la closure.

static Sexp *env_snapshot(Env *env) {
    if (!env) return NULL;
    return sexp_cons(
        sexp_copie(env->bindings),
        env_snapshot(env->parent));
}

static Env *env_from_snapshot(Sexp *s) {
    if (!s) return NULL;
    Env *e = env_new(env_from_snapshot(s->cdr));
    e->bindings = sexp_copie(s->car);
    return e;
}

5.3 Application d'une closure

L'application d'une closure se fait en trois étapes :

1. Reconstruire la chaîne d'env depuis le snapshot
2. Lier les paramètres aux arguments via zip
3. Évaluer le corps dans le nouvel env

/* extrait de evaluer_env — application de closure */
if (is_closure(op)) {
    Sexp *params = closure_params(op);
    Sexp *body   = closure_body(op);
    Env *saved   = env_from_snapshot(closure_env(op));
    Env *local   = env_new(saved);  /* nouvelle portée */
    local->bindings = zip(params, args);
    return evaluer_env(body, &local);
}

6. lambda & function

6.1 lambda — fonction anonyme

(lambda (x) (+ x 1)) crée une closure anonyme et la retourne. Elle peut être appelée immédiatement ou stockée dans une variable.

;; appel immédiat d'une lambda
$ ./let '((lambda (x) (* x 2)) 21)'
→ 42

;; stocker une lambda dans une variable
$ ./let '(let double (lambda (x) (* x 2)))' '(double 21)'
→ 42

6.2 function — fonction nommée

(function f (x) (+ x 1)) crée une closure et l'enregistre dans l'environnement courant sous le nom f. Le corps peut faire référence à f pour la récursion.

if (strcmp(name, "function") == 0) {
    Sexp *sym   = args->car;
    Sexp *params = args->cdr->car;
    Sexp *body  = args->cdr->cdr->car;
    Sexp *clos = make_closure(params, body, *env);
    /* enregistre dans l'env courant */
    (*env)->bindings = sexp_cons(
        sexp_cons(sym, sexp_cons(clos, NULL)),
        (*env)->bindings);
    return sexp_copie(clos);
}

Exemple : factorielle récursive

$ ./let '(function fact (n)
    (if (eq? n 1) 1
      (* n (fact (- n 1)))))'
  '(print (fact 5))'
120

La récursion fonctionne car fact est dans l'environnement quand le corps de la fonction s'exécute. Au moment de l'appel, on a reconstruit l'environnement depuis le snapshot, qui contient déjà la liaison fact.

7. Cellules mutables

Une cellule est une boîte mutable sur le tas. Elle permet de partager une valeur modifiable entre plusieurs environnements (ou plusieurs closures).

7.1 Nouveau type : SEXPR_CELL

typedef struct Cell {
    int value;  /* valeur stockée */
    int refs;   /* compteur de références */
} Cell;

Cell *cell_new(int v) {
    Cell *c = malloc(sizeof(Cell));
    c->value = v;
    c->refs = 1;
    return c;
}

/* sexp_copie pour SEXPR_CELL :
   partage la même Cell, incrémente refs */
if (s->type == SEXPR_CELL && s->cell) {
    s->cell->refs++;
    return sexp_cell(s->cell);
}

/* sexp_free pour SEXPR_CELL :
   décrémente refs, libère si 0 */
if (s->type == SEXPR_CELL && s->cell
    && --s->cell->refs == 0)
    free(s->cell);

7.2 Utilisation

;; créer une cellule
(cell 42)       → #<cell:42>

;; lire la valeur
(cell-ref c)    → 42

;; muter avec set!
(set! c 100)    ; la cellule contient maintenant 100

8. Objets par passage de messages

Une closure + une cellule mutable = un objet. Le message est passé comme argument (un symbole) que la closure interprète avec eq?.

8.1 Compteur

(function make-compteur (init)
  (let c (cell init))
  (lambda (msg)
    (if (eq? msg 'inc)
        (begin (set! c (+ (cell-ref c) 1)) (cell-ref c))
      (if (eq? msg 'value) (cell-ref c)
        (if (eq? msg 'reset)
            (begin (set! c 0) (cell-ref c))
          0)))))

$ ./let '(let c (make-compteur 100))'
  '(c 'inc)'  '(c 'inc)'  '(c 'value)'
101
102
102

$ ./let '(let a (make-compteur 0))'
  '(let b (make-compteur 50))'
  '(a 'inc)'  '(b 'inc)'  '(a 'inc)'  '(b 'inc)'
1
51
2
52

8.2 Analyse

• make-compteur est une fonction qui crée une cellule c et retourne une closure qui « voit » c
• La closure reçoit un message ('inc, 'value, 'reset) et agit en conséquence
• Chaque appel à make-compteur crée une nouvelle cellule → chaque compteur a son état propre
• Pas de this, pas de classe, pas d'héritage — juste une fermeture lexicale et une cellule mutable

8.3 Banque — un objet avec état et paramètres

(function make-bank (initial)
  (let solde (cell initial))
  (let historique (cell (list)))
  (lambda (msg mt)
    (if (eq? msg 'deposit)
        (begin
          (set! solde (+ (cell-ref solde) mt))
          (cell-ref solde))
      (if (eq? msg 'withdraw)
          (if (>= (cell-ref solde) mt)
              (begin
                (set! solde (- (cell-ref solde) mt))
                (cell-ref solde))
            0)  ; refusé
        (if (eq? msg 'balance) (cell-ref solde)
          0)))))

Ici, le message peut porter un paramètre (mt pour le montant). La condition (>= (cell-ref solde) mt) implémente la vérification de solde suffisant.

9. Listes : list car cdr cons null?

Les listes sont déjà représentées en interne par les SEXPR_CONS de la bibliothèque. On ajoute simplement des mots-clés au langage pour les construire et les décomposer.

9.1 Nouvelles formes spéciales

9.2 Implémentation de car (extrait)

if (strcmp(name, "car") == 0) {
    Sexp *v = evaluer_env(args->car, env);
    if (!v || v->type != SEXPR_CONS) {
        fprintf(stderr,
            "ERREUR: car attend une paire\n");
        exit(1);
    }
    Sexp *r = sexp_copie(v->car);
    sexp_free(v);
    return r;
}

9.3 Combiner listes et fonctions

Avec la récursion, on peut implémenter des algorithmes classiques :

;; longueur d'une liste
(function len (lst)
  (if (null? lst) 0
    (+ 1 (len (cdr lst)))))

;; map : appliquer f à chaque élément
(function map (f lst)
  (if (null? lst) (list)
    (cons (f (car lst)) (map f (cdr lst)))))

;; filter : garder les éléments satisfaisant pred
(function filter (pred lst)
  (if (null? lst) (list)
    (if (pred (car lst))
        (cons (car lst) (filter pred (cdr lst)))
      (filter pred (cdr lst)))))

10. Transpiler LISP → Python

Le langage est suffisamment complet pour être traduit vers Python. Le fichier transpile.c (environ 360 lignes) implémente un transpileur qui parcourt l'AST et émet du code Python 3.

10.1 Principe

int main(int argc, char *argv[]) {
    for (int i = 1; i < argc; i++) {
        Sexp *s = sexp_parse(argv[i]);
        transpile(s, 0);  /* 0 = context statement */
        printf("\n");
        sexp_free(s);
    }
}

La fonction récursive transpile(s, in_expr) examine le type de s :

• Entier → imprime le nombre
• Symbole → imprime le nom (avec sanitization des - et ? remplacés par _)
• Cons → inspecte l'opérateur et émet le code Python correspondant (infix, fonction, forme spéciale…)

10.2 Correspondances

10.3 Gestion du begin dans les fonctions

Le begin pose un problème : en Python, un lambda ne peut contenir qu'une expression, pas une séquence d'instructions. Le transpileur utilise deux stratégies :

;; LISP
(function f (x)
  (begin
    (display x)
    (* x 2)))

;; Python
def f(x):
    print(x, end='')
    return x * 2

;; LISP
(lambda (x)
  (begin
    (display x)
    (* x 2)))

;; Python (tuple trick)
lambda x: (print(x, end=''),
           x * 2)[-1]

10.4 Exemples d'utilisation

# Factorielle récursive
$ ./transpile '(function fact (n) (if (eq? n 1) 1
    (* n (fact (- n 1)))))' '(print (fact 5))' | python3
120

# Map et filter
$ ./transpile '(function map (f lst) …)' \
    '(function even (x) (eq? 0 (% x 2)))' \
    '(print (filter even (list 1 2 3 4 5 6)))' | python3
[2, 4, 6]

# Générer du Python et l'enregistrer
$ ./transpile '(let x 42)' '(+ x 1)' > script.py
$ python3 script.py

11. Exercices

Niveau ★☆☆

Niveau ★★☆

Niveau ★★★

Allez plus loin

Le fichier let.c est le programme le plus complexe du cours — environ 580 lignes de C qui implémentent un langage de programmation complet. Prenez le temps de le lire et de le comprendre. Voici quelques pistes pour aller plus loin :

• Ajoutez map, filter, fold comme primitives du langage (pas juste des fonctions utilisateur) pour les rendre plus efficaces
• Ajoutez un ramasse-miettes ou améliorez le refcounting des cellules
• Étendez le transpileur pour gérer les cellules et les closures avec mutation
• Implémentez un compilateur LISP → bytecode VM (comme calc.c le fait) pour votre nouveau langage
• Ajoutez une forme define qui permet de définir des variables globales sans imbrication
• Expérimentez avec le REPL : tapez ./let et interagissez en mode interactif