De zéro à λ en C — Correction

Réponse

• int : 32 bits (souvent), plage ≈ [−2,1·10⁹ , 2,1·10⁹], format printf : %d.
• long long : 64 bits, plage ≈ [−9,2·10¹⁸ , 9,2·10¹⁸], format printf : %lld.
• 20! = 2 432 902 008 176 640 000 > 2,1·10⁹ → débordement (overflow) si stocké dans un int.
• Le C n'avertit pas : le dépassement d'un entier signé est un comportement indéfini (silencieux).

Barème : 0,5 pt pour taille/format/plage, 0,5 pt pour l'overflow silencieux.

Réponse

• Une fermeture lexicale (closure) est un couple (fonction, environnement) : la fonction « gèle » l'environnement dans lequel elle a été créée.
• Dans let.c, elle est représentée par une liste (fun (params) corps env_snapshot…) — un SEXPR_CONS dont le car est le symbole fun, suivi des paramètres, du corps, puis de la copie de la chaîne d'environnements.
• « Geler l'environnement » = copier récursivement les bindings de la chaîne d'Env au moment de la création de la closure, pour que les variables capturées survivent même si l'environnement original est modifié ou détruit.

Barème : 0,3 pt définition, 0,4 pt représentation, 0,3 pt gel.

Réponse

• let crée un nouveau binding dans l'environnement courant. Si le symbole existe déjà, il est masqué (shadowing).
• set! modifie un binding existant en remontant la chaîne d'environnements. Si le symbole n'existe pas, c'est une erreur.

Exemple :

(let x 10)
(let f (lambda () (let x 20)))  (f) x   → 10  (nouveau binding local)
(let g (lambda () (set! x 20))) (g) x   → 20  (mutation du x original)

Barème : 0,3 pt let, 0,3 pt set!, 0,4 pt exemple correct.

Réponse

• En RPN (notation polonaise inversée), les opérandes précèdent l'opérateur. Pas de parenthèses ni de priorité : l'ordre des opérations est entièrement déterminé par la position des opérateurs.
• Évaluation avec une pile : on empile les opérandes, l'opérateur dépile ses arguments et empile le résultat.

RPN de (3 + 4) × (5 − 2) :

Barème : 0,4 pt explication, 0,6 pt RPN correcte.

Réponse

Ce que calcule mystere :

• *p reçoit la valeur du n-ième nombre triangulaire : T(n) = 1 + 2 + … + n = n(n+1)/2.
• La valeur de retour est la somme des nombres triangulaires de T(1) à T(n−1).

Trace pour n=5 :

Affichage : r = 20, x = 15

Barème : 0,5 pt explication, 1 pt tracé correct, 0,5 pt affichage.

Réponse

Trace détaillée de la pile d'appels pour mystere(3, &x) :

┌─ mystere(3, &x)─────────────────────────────┐
│ n=3  p→x  temp=⊘  res=⊘                     │
│   ┌─ mystere(2, &temp)───────────────────┐  │
│   │ n=2  p→temp  tmp=⊘  res=⊘            │  │
│   │   ┌─ mystere(1, &tmp) ────────────┐  │  │
│   │   │ n=1  p→tmp                     │  │  │
│   │   │ *p = 1  ← tmp = 1             │  │  │
│   │   │ return 0                       │  │  │
│   │   └────────────────────────────────┘  │  │
│   │ tmp=1, res=0                          │  │
│   │ *p = 2 + 1 = 3  ← temp = 3           │  │
│   │ return 0 + 1 = 1                      │  │
│   └───────────────────────────────────────┘  │
│ temp=3, res=1                                │
│ *p = 3 + 3 = 6  ← x = 6                     │
│ return 1 + 3 = 4                             │
└──────────────────────────────────────────────┘
⇒ r = 4, x = 6

Barème : 0,5 pt par niveau correct de la pile.

Réponse

int mystere_iter(int n, int *p) {
    int ret = 0;
    *p = 0;
    for (int i = 1; i <= n; i++) {
        *p = *p + i;          /* T(i) = T(i-1) + i */
        if (i < n)
            ret += *p;        /* somme des T(1)…T(n-1) */
    }
    return ret;
}

Vérification pour n=5 :

Résultat : r=20, x=15. ✓

Barème : 0,5 pt boucle correcte, 0,5 pt mise à jour de *p, 0,5 pt accumulation de ret.

Réponse

Arbre de (+ (* 2 3) (- 10 (/ 8 4))) en paires CONS :

         CONS
        ╱    ╲
      SYM     CONS
      "+"    ╱    ╲
           CONS    CONS
          ╱    ╲  ╱    ╲
        SYM   CONS SYM  CONS
        "*"  ╱    ╲ "-" ╱    ╲
            INT  CONS  INT  CONS
             2  ╱    ╲  10  ╱    ╲
              INT  NULL   CONS  NULL
               3         ╱    ╲
                       SYM    CONS
                       "/"   ╱    ╲
                           INT   CONS
                            8   ╱    ╲
                              INT   NULL
                               4

Barème : structure correcte (symboles, entiers, listes imbriquées). Barème souple — un schéma lisible suffit.

Réponse

int profondeur(Sexp *e) {
    if (e == NULL) return 0;
    if (e->type != SEXPR_CONS) return 0;  /* atome → 0 */

    int max_elem = 0;
    Sexp *cur = e;
    while (cur != NULL && cur->type == SEXPR_CONS) {
        int d = profondeur(cur->car);
        if (d > max_elem) max_elem = d;
        cur = cur->cdr;
    }
    return 1 + max_elem;
}

Explication : On parcourt la liste (la « colonne vertébrale » de CONS), on calcule récursivement la profondeur de chaque élément (car), et on prend le max. Un niveau de liste ajoute 1.

Test avec (+ 2 (* 3 4)) : les éléments sont + (0), 2 (0), (* 3 4) (1). Max = 1, donc profondeur = 2. ✓

Barème : 0,5 pt cas de base, 0,5 pt boucle de parcours, 0,5 pt appel récursif, 0,5 pt retour.

Réponse

Profondeur = 3

Analyse :

• Niveau 1 (liste racine) : +, (* 2 3), (- 10 (/ 8 4))
• Niveau 2 : *, 2, 3 (profondeur 1) et -, 10, (/ 8 4) (profondeur 1)
• Niveau 3 : /, 8, 4

Barème : réponse correcte = 1 pt.

Réponse

Bytecode pour (8 − 2 × 3) × 4 :

PUSH 8
PUSH 2
PUSH 3
MUL        ; 2 × 3 = 6
SUB        ; 8 − 6 = 2
PUSH 4
MUL        ; 2 × 4 = 8
PRINT
HALT

État de la pile après chaque instruction :

Barème : 1 pt séquence correcte, 1 pt tableau pile.

Réponse

int eval_bytecode(int code[], int taille) {
    int pile[256], sp = 0;

    for (int ip = 0; ip < taille; ) {
        int op = code[ip++];
        switch (op) {
        case 0: /* PUSH v */
            pile[sp++] = code[ip++];
            break;
        case 1: /* ADD */
            sp--;
            pile[sp-1] += pile[sp];
            break;
        case 2: /* SUB */
            sp--;
            pile[sp-1] -= pile[sp];
            break;
        case 3: /* MUL */
            sp--;
            pile[sp-1] *= pile[sp];
            break;
        case 4: /* DIV */
            sp--;
            if (pile[sp] == 0) {
                printf("Erreur: /0\n");
                return 0;
            }
            pile[sp-1] /= pile[sp];
            break;
        case 5: /* PRINT */
            printf("%d\n", pile[--sp]);
            break;
        case 6: /* HALT */
            return sp > 0 ? pile[sp-1] : 0;
        }
    }
    return sp > 0 ? pile[sp-1] : 0;
}

Barème : 0,5 pt structure (pile, sp, boucle), 0,5 pt PUSH/ADD/SUB/MUL, 0,5 pt DIV avec /0, 0,5 pt PRINT/HALT/retour.

Réponse

apply_closure applique une fermeture à des arguments :

1. Extraire la fermeture : vérifier que c'est une liste (fun (params) body env_snapshot).
2. Reconstruire la chaîne d'environnements à partir du env_snapshot via env_from_snapshot (parcours et recréation des Env).
3. Lier les paramètres aux arguments : pour chaque paramètre (dans l'ordre), évaluer l'argument correspondant et l'ajouter au nouvel environnement avec env_bind.
4. Évaluer le corps dans le nouvel environnement (qui a pour parent la chaîne issue du snapshot).
5. Retourner le résultat.

Point clé : le corps est évalué dans l'environnement gelé (celui de la création), pas dans l'environnement d'appel → portée lexicale.

Barème : 0,3 pt extraction, 0,3 pt snapshot, 0,5 pt liaison params→args, 0,4 pt évaluation du corps.

Réponse

Principe du comptage de références :

• Chaque Cell possède un champ refs qui compte le nombre de Sexp pointant vers cette cellule.
• sexp_cell(v) : crée une cellule, refs = 1.
• sexp_copie(e) : si SEXPR_CELL, on incrémente refs (copie superficielle, pas de nouveau malloc).
• sexp_free(e) : si SEXPR_CELL, on décrémente refs ; on ne libère la mémoire que quand refs == 0.

Pourquoi est-ce nécessaire ?

• Les cellules permettent la mutation partagée : deux fermetures peuvent référencer la même cellule (ex : un compteur partagé).
• Si on copiait naïvement (affectation ou memcpy) :
  • Soit on duplique la cellule → les deux copies sont indépendantes → perdre le partage (muter l'une n'affecte pas l'autre).
  • Soit on copie le pointeur sans compter → dangling pointer : la première free libère la cellule que l'autre pointeur référence encore.

Sans refcounting : crash (double free ou use-after-free) dès qu'une cellule est partagée entre plusieurs environnements.

Barème : 0,5 pt mécanisme, 0,5 pt nécessité (partage, mutation), 0,5 pt conséquences sans refcounting.