De zéro à λ en C — Examen

Durée : 1h30	Documents : aucun
Total : 20 points	Calculateur : interdit

Consignes : Lisez attentivement chaque question avant d'y répondre. Répondez sur des copies séparées (pas sur le sujet). Soyez précis et concis. Le barème est donné à titre indicatif.

Partie 1 — Questions de cours (4 points, ~15 min)

Q1. (1 pt) Expliquez la différence entre les types int et long long en C en termes de taille, de plage de valeurs et de format printf. Quel problème peut survenir lorsqu'on calcule la factorielle de 20 avec un int ? Le C vous avertit-il ?

Q2 — Structures chaînées et capture d'état. (1 pt) Qu'est-ce qu'une fermeture lexicale (closure) dans le contexte de let.c ? Comment est-elle représentée en mémoire (structure de donnée utilisée) ? Que signifie « geler l'environnement » ?

Q3 — Insertion vs modification dans une liste chaînée. (1 pt) Quelle est la différence entre let et set! dans l'interpréteur LISP ? Donnez un exemple de code LISP où les deux produisent des résultats différents.

Q4. (1 pt) Expliquez le principe de la notation polonaise inversée (RPN / postfixée). Donnez la séquence RPN de l'expression : (3 + 4) × (5 − 2).

Partie 2 — Analyse de code C (5 points, ~20 min)

On considère le programme C suivant :

#include <stdio.h>

int mystere(int n, int *p) {
    if (n <= 1) {
        *p = 1;
        return 0;
    }
    int temp;
    int res = mystere(n - 1, &temp);
    *p = n + temp;
    return res + temp;
}

int main() {
    int x;
    int r = mystere(5, &x);
    printf("r = %d, x = %d\n", r, x);
    return 0;
}

Q5. (2 pts) Que calcule la fonction mystere ? En déduire l'affichage du programme sans l'exécuter. Expliquez brièvement votre raisonnement.

Q6. (1.5 pts) Dessinez l'évolution de la pile d'appels (avec les valeurs de n, p, temp, res) pour mystere(3, &x).

Q7. (1.5 pts) Réécrivez la fonction mystere sous forme itérative (avec une boucle, sans récursion). La fonction itérative doit produire les mêmes résultats.

Partie 3 — S-expressions et parcours d'arbre (4 points, ~20 min)

Dans tout ce qui suit, Sexp est une structure C avec union et champ type.

On utilise la bibliothèque sexpression.h vue en cours. On considère la S-expression suivante :

(+ (* 2 3) (- 10 (/ 8 4)))

Q8. (1 pt) Dessinez l'arbre correspondant à cette S-expression : chaque nœud CONS a un car (à gauche) et un cdr (à droite). On attend un schéma avec la structure en paires chaînées.

Q9. (2 pts) Écrivez une fonction C récursive :

int profondeur(Sexp *e);

qui calcule la profondeur maximale d'une S-expression. La profondeur est définie comme le nombre maximal de niveaux d'imbrication de nœuds CONS entre la racine et une feuille (un atome entier ou symbole). Un atome a une profondeur de 0.

Exemple : '(+ 2 (* 3 4)) a une profondeur de 2.

Q10. (1 pt) Quelle est la profondeur de l'expression donnée plus haut (+ (* 2 3) (- 10 (/ 8 4))) ?

Partie 4 — VM et bytecode (4 points, ~20 min)

La VM du cours 2 utilise les opcodes suivants :

Opcode	Effet
`PUSH v`	Empile la valeur `v`
`ADD`	Dépile a, dépile b, empile b + a
`SUB`	Dépile a, dépile b, empile b − a
`MUL`	Dépile a, dépile b, empile b × a
`DIV`	Dépile a, dépile b, empile b ÷ a
`PRINT`	Dépile et affiche la valeur
`HALT`	Arrête l'exécution

Q11. (2 pts) Traduisez l'expression arithmétique suivante en bytecode pour cette VM :

(8 − 2 × 3) × 4

Donnez la séquence d'instructions et l'état de la pile après chaque instruction (sous forme d'un tableau).

Q12. (2 pts) Écrivez une fonction C :

int eval_bytecode(int code[], int taille);

qui exécute ce bytecode avec une pile (tableau d'entiers, taille maximale 256) et retourne la valeur au sommet de la pile à la fin de l'exécution. Si une division par zéro est détectée, affichez "Erreur: /0" et retournez 0.

Rappel : utilisez un tableau int pile[256] et un indice sp (stack pointer). Pour l'encodage, les opcodes sont des entiers : 0=PUSH, 1=ADD, 2=SUB, 3=MUL, 4=DIV, 5=PRINT, 6=HALT. PUSH est suivi de l'argument dans le tableau code[].

Partie 5 — Architecture de l'interpréteur (3 points, ~15 min)

Q13. (1.5 pts) Décrivez le fonctionnement de la fonction apply_closure dans let.c. Quelles sont les étapes pour appliquer une fermeture (closure) à ses arguments ? En particulier : comment les paramètres sont-ils liés aux arguments ? dans quel environnement le corps est-il évalué ?

Q14. (1.5 pts) Expliquez le mécanisme de comptage de références (champ refs) utilisé dans les cellules mutables (SEXPR_CELL de sexpression.c). Pourquoi est-il nécessaire ? Que se passerait-il si on le supprimait et qu'on copiait les cellules naïvement avec memcpy ou une affectation ?

— Fin du sujet —