De zéro à λ en C — Correction — Sujet B

Réponse

• int : signé, plage ≈ [−2,1·10⁹ , 2,1·10⁹], format %d.
• unsigned int : non signé, plage [0 , 4,2·10⁹], format %u.
• -1 affiché avec %u donne 4294967295 (wrap-around : tous les bits sont à 1 = UINT_MAX).
• En C, le dépassement d'un unsigned int est défini (wrap-around modulo 2³²) — pas d'erreur, pas d'UB contrairement au signé.

Barème : 0,3 pt plages/formats, 0,3 pt -1 en %u, 0,4 pt wrap-around défini.

Réponse

• Les quatre types : SEXPR_INT (entier), SEXPR_SYM (symbole), SEXPR_CONS (paire), SEXPR_CELL (cellule mutable).
• Une liste (+ 1 2) est une chaîne de nœuds CONS : chaque car pointe vers un élément, chaque cdr pointe vers le reste de la liste. Le dernier cdr est NULL.

  (+ 1 2)  →  CONS → CONS → CONS → NULL
              car=+  car=1  car=2

Barème : 0,4 pt les quatre types, 0,6 pt représentation des listes.

Réponse

• quote empêche l'évaluation de son argument : il retourne l'argument tel quel (sous forme de S-expression).
• L'évaluation normale interprète le premier élément comme une fonction et les suivants comme ses arguments évalués.
• Exemple : (quote (+ 1 2)) → (+ 1 2) (la liste non évaluée). Sans quote, (+ 1 2) → 3.
• Nécessaire pour manipuler des listes comme données, ex : (car (quote (a b c))) → a.

Barème : 0,3 pt quote, 0,3 pt évaluation normale, 0,4 pt exemple.

Réponse

• Fetch : lire l'instruction à l'adresse IP dans le tableau code[].
• Decode : déterminer l'opcode (PUSH, ADD, etc.).
• Execute : effectuer l'opération (empiler/dépiler/calculer).
• IP (instruction pointer) : index dans le tableau code[], avance après chaque instruction (sauf HALT).
• SP (stack pointer) : index du sommet de la pile, varie selon les instructions.

Barème : 0,4 pt cycle FDE, 0,3 pt IP, 0,3 pt SP.

Réponse

Ce que calcule fibo : le n-ième nombre de Fibonacci (F₀=0, F₁=1, Fₙ = Fₙ₋₁ + Fₙ₋₂). *compteur compte le nombre total d'appels à fibo.

Affichage : r = 5, c = 15

Explication : F₅ = 5. Le nombre d'appels pour Fₙ suit la récurrence C(0)=C(1)=1, C(n)=1+C(n-1)+C(n-2). Pour n=5 : C(5)=15.

Comptage pour n=5 :

fibo(5)
├─ fibo(4)
│  ├─ fibo(3)
│  │  ├─ fibo(2)
│  │  │  ├─ fibo(1) → 1
│  │  │  └─ fibo(0) → 0
│  │  └─ fibo(1) → 1
│  └─ fibo(2)
│     ├─ fibo(1) → 1
│     └─ fibo(0) → 0
└─ fibo(3)
   ├─ fibo(2)
   │  ├─ fibo(1) → 1
   │  └─ fibo(0) → 0
   └─ fibo(1) → 1
Total : 15 appels (1 + 9 sous-appels + 5 feuilles)

Barème : 0,5 pt identification de Fibonacci, 0,5 pt affichage, 1 pt comptage des appels.

Réponse

Arbre d'appels pour fibo(4, &c) :

fibo(4, &c)     c=1
├─ fibo(3, &c)  c=2
│  ├─ fibo(2, &c)  c=3
│  │  ├─ fibo(1, &c)  c=4 → 1
│  │  └─ fibo(0, &c)  c=5 → 0
│  └─ fibo(1, &c)  c=6 → 1
└─ fibo(2, &c)  c=7
   ├─ fibo(1, &c)  c=8 → 1
   └─ fibo(0, &c)  c=9 → 0

Total : 9 appels pour F₄. Résultat : F₄ = 3 (0+1+1+2+...).

Barème : 0,5 pt structure arborescente, 0,5 pt valeurs n, 0,5 pt compteur.

Réponse

int fibo_iter(int n, int *compteur) {
    if (n <= 1) {
        (*compteur)++;
        return n;
    }
    int a = 0, b = 1;  /* F₀, F₁ */
    *compteur = 2;     /* appels pour a et b déjà comptés */
    for (int i = 2; i <= n; i++) {
        int tmp = a + b;
        a = b;
        b = tmp;
        (*compteur)++;
    }
    return b;
}

Vérification pour n=5 : F₅ = 5, compteur = 6 (2 + 4 itérations). ✓

Barème : 0,5 pt boucle correcte, 0,5 pt calcul de Fibonacci, 0,5 pt compteur.

Réponse

Arbre de (list 1 (list 2 3) 4) :

       CONS
       ╱    ╲
     SYM     CONS
    "list"  ╱    ╲
           INT    CONS
            1    ╱    ╲
               CONS    CONS
               ╱    ╲  ╱    ╲
             SYM   CONS INT  NULL
            "list" ╱    ╲  4
                  INT   CONS
                   2   ╱    ╲
                      INT   NULL
                       3

Barème : structure correcte. Barème souple — un schéma lisible suffit.

Réponse

int compte_atomes(Sexp *e) {
    if (e == NULL) return 0;
    if (e->type != SEXPR_CONS) return 1;  /* atome (INT ou SYM) */

    int total = 0;
    Sexp *cur = e;
    while (cur != NULL && cur->type == SEXPR_CONS) {
        total += compte_atomes(cur->car);
        cur = cur->cdr;
    }
    return total;
}

Explication : On parcourt la liste chaînée ; pour chaque élément (car), on compte récursivement ses atomes. Les atomes (INT, SYM) renvoient 1, NULL renvoie 0.

Test : '(1 2 (3 4)) → atomes : 1, 2, 3, 4 = 4. ✓

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

4 atomes.

• Atomes au niveau 1 : list (1), 1 (1), 4 (1)
• Atome dans la sous-liste (list 2 3) : list (1), 2 (1), 3 (1) — mais ce sont 3 atomes supplémentaires

Total : list + 1 + list + 2 + 3 + 4 = 6 atomes

Barème : réponse correcte = 1 pt. (Piège : le list est aussi un atome.)

Réponse

Bytecode pour ((10 + 2) × 3) − (8 ÷ 2) :

PUSH 10
PUSH 2
ADD        ; 10 + 2 = 12
PUSH 3
MUL        ; 12 × 3 = 36
PUSH 8
PUSH 2
DIV        ; 8 ÷ 2 = 4
SUB        ; 36 − 4 = 32
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_v2(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: /* DUP */
            pile[sp] = pile[sp-1];
            sp++;
            break;
        case 2: /* ADD */
            sp--;
            pile[sp-1] += pile[sp];
            break;
        case 3: /* SUB */
            sp--;
            pile[sp-1] -= pile[sp];
            break;
        case 4: /* MUL */
            sp--;
            pile[sp-1] *= pile[sp];
            break;
        case 5: /* DIV */
            sp--;
            if (pile[sp] == 0) {
                printf("Erreur: /0\n");
                return 0;
            }
            pile[sp-1] /= pile[sp];
            break;
        case 6: /* PRINT */
            printf("%d\n", pile[--sp]);
            break;
        case 7: /* 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/DUP, 0,5 pt ADD/SUB/MUL/DIV avec /0, 0,5 pt PRINT/HALT/retour.

Réponse

eval détermine le type d'expression en regardant le champ type de la S-expression :

1. Entier (SEXPR_INT) → retourne l'entier (valeur immédiate).
2. Symbole (SEXPR_SYM) → cherche la valeur du symbole dans l'environnement via env_lookup.
3. Liste vide (NULL) → retourne NULL (ou provoque une erreur selon l'implémentation).
4. Liste (SEXPR_CONS) → examine le car :
   • Si c'est une forme spéciale (let, set!, lambda, if, quote, begin, define, and/or) → traitement spécifique sans évaluer tous les arguments.
   • Sinon → appel de fonction : évaluer le car (qui doit produire une closure), évaluer les arguments (cdr), puis appeler apply_closure.

Barème : 0,3 pt dispatch par type, 0,4 pt entiers/symboles/NULL, 0,4 pt formes spéciales, 0,4 pt appel de fonction.

Réponse

• L'environnement est une liste chaînée de struct Env, chaque maillon contenant un nom de variable et sa valeur, plus un pointeur parent vers l'environnement englobant.
• env_lookup(symbol, env) parcourt la chaîne :
  1. Cherche symbol dans le maillon courant.
  2. Si trouvé → retourne sa valeur.
  3. Sinon → remonte au parent et recommence.
  4. Si parent == NULL et pas trouvé → erreur (symbole non défini).
• Shadowing : si un même nom existe à plusieurs niveaux, env_lookup retourne la première occurrence rencontrée (la plus proche, dans l'environnement le plus interne). Les occurrences plus loin dans la chaîne sont masquées.

Barème : 0,5 pt structure chaînée, 0,5 pt env_lookup, 0,5 pt shadowing.