Prog comp— Cours 2 - Notes de cours et TD Summary & Study Notes

📚 Résumé du cours (objectifs)

Objectifs : comprendre les structures de données (listes, arbres, tables), la mutabilité vs immutabilité, les modèles d'exécution (interprétation, compilation, machine virtuelle) et la représentation des programmes (AST, IR, CFG). Ces notions servent à raisonner sur l'efficacité, la sûreté et le design d'API.

🧱 Données immuables et mutables

Les objets immuables ne changent jamais après construction (ex. records immuables). Les objets mutables possèdent des champs modifiables et peuvent être mis à jour en place. L'usage de l'un ou l'autre influe sur : l'aliasing, les effets de bord, la nécessité de copies profondes vs superficielles, et la facilité du raisonnement (les fonctions pures bénéficient de la transparence référentielle).

🔁 Passage des valeurs et retours de fonctions

Dans des langages comme Java, OCaml, Python : les structures non-primitives sont passées par référence (adresse). En C, les structs sont souvent passées par valeur (copie), sauf si on passe un pointeur. Les fonctions peuvent soit écrire le résultat dans un argument (style impératif) soit retourner une nouvelle valeur (style fonctionnel) — trade-off mémoire vs contrôle.

🧠 Fonctions pures, caches et effets

Une fonction pure renvoie toujours le même résultat pour les mêmes arguments et n'a pas d'effets de bord. Cela permet des optimisations (mémoïsation, substitution). Les fonctions avec un cache interne peuvent rester observablement pures pour le client tout en utilisant de la mutabilité interne pour optimiser.

🕰 Évaluation retardée (lazy)

Principe : encapsuler un calcul non effectué et l'évaluer à la première demande, en mémorisant le résultat. Exemple conceptuel : structure contenant soit Imm(v) soit Ret(f). La première évaluation appelle f(), stocke Imm(v) et retourne v. Utilité : éviter des calculs coûteux non utilisés, implémenter des structures potentiellement infinies (suites, streams).

🧩 Conteneurs impératifs vs fonctionnels

• Listes impératives (Java, Python) : mutables, insertion/accès selon l'implémentation (tableau vs liste chaînée). Danger : modifier une collection pendant son parcours.
• Listes fonctionnelles (OCaml) : immuables, partagent la queue, construction par ::, traitement par pattern matching.
• Tables d'association : implémentées par listes de paires, tables de hachage (requièrent hash/égalité) ou arbres équilibrés (requièrent ordre). Certaines APIs fournissent versions mutables et immuables (Map.Make en OCaml).

⚙ Modèles d'exécution : interprétation vs compilation

• Interprétation : exécution directe du source/IR, démarrage rapide, portable, plus lent.
• Compilation : génération de code natif, exécution rapide, nécessite étape de compilation et recompilation pour cibles différentes.
• Machines virtuelles (code-octet) : compromis portable + plus d'abstraction, possibilité de JIT pour améliorer la vitesse.

🌳 Représentations des programmes

• AST : structure récursive qui représente le programme sans détails superflus (espaces, commentaires). Utile pour analyses et interprétation.
• IR / code 3-adresses : bas niveau, pratique pour optimisation et génération de code.
• CFG (graphe de flot) : blocs + flots conditionnels, utile pour l'analyse de flux et transformations.

🧾 Sémantique et interprètes

La sémantique opérationnelle décrit l'évolution pas à pas d'un programme. Un interprète construit un AST, éventuellement un IR, puis exécute en faisant évoluer un environnement (table de hachage mutable pour les versions impératives ou en retournant de nouveaux environnements pour versions immuables).

🧭 Présentation des TD (organisation)

Le TD₂ propose des exercices couvrant : criblé d'Ératosthène, arbres binaires, évaluation retardée, comptage de points (Belote), mini-interprète, et Jeu de la Vie. L'objectif est d'appliquer les notions du cours aux implementations pratiques (OCaml/Python/Java ou autre).

🔢 Exercice 1 — Crible d'Ératosthène (algorithme & signatures)

• But : calculer la suite des nombres premiers entre $2$ et $n$.
• Fonctions demandées (exemples de signatures) :
  • interval : int * int -> int list — retourne la liste des entiers de a à b inclus.
  • is_multiple : int * int -> bool — vrai si x est multiple de m.
  • remove_multiple_of : int -> int list -> int list — retire tous les multiples d'un entier donné.
  • sieve : int -> int list — applique l'algorithme classique, en arrêtant quand le carré du plus petit élément restant dépasse $n$.
• Astuce : implémenter remove_multiple_of en filtrant la liste; pour de meilleures performances, utiliser tableaux/bitset si $n$ grand.

🌲 Exercice 2 — Arbre binaire (types et opérations)

• Type (exemple OCaml) : type int_tree = Nil | Node of int * int_tree * int_tree
• Fonctions :
  • size : int_tree -> int — nombre de nœuds.
  • depth : int_tree -> int — longueur de la plus longue branche.
  • sum : int_tree -> int — somme des étiquettes.
  • contains : int -> int_tree -> bool — test d'appartenance.
  • elements : int_tree -> int list — parcours gauche, racine, droite (infixe). Éviter la concaténation coûteuse en utilisant un accumulateur en queue pour construire la liste.
• Conseil : écriture récursive simple; pour elements, fournir une auxiliaire accum qui construit la liste efficacement.

🕰 Exercice 3 — Évaluation retardée (lazy)

• Implémentation donnée en OCaml : type 'a value = Imm of 'a | Ret of (unit -> 'a); type 'a lazyval = { mutable v : 'a value }
• Tâches :
  • écrire fib en style lazy (mêmes principes que fact).
  • traduire la structure en Python (objet avec attribut v contenant soit valeur ou callable, méthode force qui évalue et mémorise).
• Remarque : la mémoïsation empêche les recalculs et permet des dépendances circulaires contrôlées si bien gérées.

🃏 Exercice 4 — Comptage des points à la Belote

• Types à définir : couleur (trèfle, cœur, pique, carreau) et carte (As, Roi, Dame, Valet, 2..10, 7..10 selon jeu).
• Fonction valeur : prend la couleur de l'atout et une carte et renvoie sa valeur entière suivant les règles (As=11, Roi=4, Dame=3, Valet=20 si atout sinon 2, 10=10, 9=14 si atout sinon 0, autres=0).
• valeur_jeu : somme des valeurs d'une liste de cartes.
• Test : exemple donné doit produire 30 pour la main fournie.

🛠 Exercice 5 — Mini-interprète (AST et interprétation)

• Définir les types d'AST pour expr, cst, stmt (assign, skip, seq, if, while, opérations binaires/unaires).
• Fonctions :
  • affichage lisible d'un AST (pretty-print), utile pour déboguer.
  • interprète impératif : exécute un AST en utilisant une table de hachage mutable comme environnement (Hashtbl en OCaml, dict en Python, Map en Java).
  • interprète fonctionnel : version immuable qui prend un environnement et retourne un nouvel environnement sans mutation (utile pour raisonnement formel).
• Extension : ajouter opérations arithmétiques et comparaisons, tester sur programmes d'exemple.

🦠 Exercice 6 — Jeu de la Vie

• Représenter la grille (ex. ensemble de coordonnées vivantes ou matrice booléenne). Fournir une configuration initiale init_gen.
• neighbours : calcule le nombre de voisins vivants d'une cellule (8 voisins possibles).
• next_gen : applique règles : survie si 2 ou 3 voisins, mort par isolement (<2) ou étouffement (>3), naissance si exactement 3.
• Conseil : représenter les cellules vivantes comme un set de paires (i,j) pour simuler un grand espace sparse efficacement.

✅ Conseils pratiques pour le rendu

• Commencer par écrire les types et signatures avant d'implémenter.
• Tester chaque fonction unitairement sur petits cas.
• Choisir version mutable ou immuable selon l'exercice et documenter les choix.

ℹ️ Note sur la provenance (texte utilisateur)

Les fichiers fournis se complètent : le document cours-2_ok.pdf contient la partie cours (concepts et exemples) et TD2-etu.pdf contient les exercices pratiques associés. Utiliser le cours pour comprendre les principes avant d'attaquer les TD.

🗺 Plan d'étude recommandé

1. Lire le cours pour maîtriser mutabilité/immutabilité, évaluation retardée, modèles d'exécution et représentations (AST/IR/CFG).
2. Implémenter les exercices du TD dans un langage familier (OCaml/Python/Java), en commençant par le crible et les arbres.
3. Vérifier les propriétés : complexité de l'algorithme, absence d'effets de bord indésirables, et tests unitaires pour valider le comportement.

🔎 Astuce rapide

Documenter les choix (mutable vs immuable) et préférer des petites fonctions testables. Pour la mémoïsation et la lazy evaluation, vérifier toujours la gestion des effets de bord lors de l'évaluation différée.