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

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 unsigned int en C en termes de plage de valeurs et de format printf. Que se passe-t-il si on affiche -1 avec %u ? Le C vous signale-t-il une erreur lors d'un dépassement d'un unsigned int ?

Q2 — S-expressions : types et représentation. (1 pt) Quels sont les quatre types de nœuds d'une S-expression dans la bibliothèque sexpression.h ? Comment une liste (ex : (+ 1 2)) est-elle représentée en mémoire à l'aide de ces nœuds ?

Q3 — Évaluation différée. (1 pt) Quelle est la différence entre quote et l'évaluation normale dans l'interpréteur LISP ? Donnez un exemple où quote est nécessaire pour éviter une évaluation.

Q4. (1 pt) Expliquez le cycle de fonctionnement de la VM du cours 2 (fetch-decode-execute). Quel est le rôle du pointeur d'instruction (IP) et du pointeur de pile (SP) ?

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

On considère le programme C suivant :

#include <stdio.h>

int fibo(int n, int *compteur) {
    (*compteur)++;
    if (n <= 1) return n;
    return fibo(n - 1, compteur) + fibo(n - 2, compteur);
}

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

Q5. (2 pts) Que calcule la fonction fibo ? En déduire l'affichage du programme sans l'exécuter. Combien de fois fibo est-elle appelée au total pour n = 5 ? Expliquez brièvement.

Q6. (1.5 pts) Dessinez l'arbre d'appels de fibo(4, &c) en montrant les valeurs de n et la valeur de *compteur après chaque appel. On attend un schéma arborescent.

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

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 :

(list 1 (list 2 3) 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 compte_atomes(Sexp *e);

qui compte le nombre d'atomes (entiers ou symboles) dans une S-expression. Les listes vides (NULL) ne comptent pas. Les atomes imbriqués dans des sous-listes sont comptés.

Exemple : '(1 2 (3 4)) contient 4 atomes.

Q10. (1 pt) Combien d'atomes contient l'expression donnée plus haut (list 1 (list 2 3) 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`
`DUP`	Duplique le sommet de la pile
`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 :

((10 + 2) × 3) − (8 ÷ 2)

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_v2(int code[], int taille);

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

Rappel : int pile[256] et un indice sp. Encodage : 0=PUSH, 1=DUP, 2=ADD, 3=SUB, 4=MUL, 5=DIV, 6=PRINT, 7=HALT. PUSH est suivi de l'argument.

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

Q13. (1.5 pts) Décrivez le fonctionnement de la fonction eval dans let.c. Comment détermine-t-elle quel type d'expression elle doit évaluer ? Donnez les principaux cas de dispatch (entier, symbole, liste vide, appel de fonction, forme spéciale).

Q14. (1.5 pts) Expliquez le principe de l'environnement chaîné (chaîne de struct Env) dans let.c. Comment la fonction env_lookup parcourt-elle la chaîne pour trouver la valeur d'un symbole ? Que se passe-t-il en cas de shadowing (deux fois le même nom dans des niveaux différents) ?

— Fin du sujet B —