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

📄 Cours principal — Polymorphisme, ordres supérieurs et inférence (cours-4_ok.pdf)

But et contexte Courte vue d'ensemble : le document explique le polymorphisme paramétrique (OCaml, Java génériques), les ordres supérieurs (fonctions comme valeurs) et l'inférence de types (Damas–Hindley–Milner) avec ses algorithmes d'unification et de généralisation.

📚 Polymorphisme : notions clés

Polymorphisme paramétrique : permet d'écrire un seul code réutilisable pour plusieurs types (ex. type 'a list en OCaml, List en Java). Ici 'a ou T est un paramètre de type. Avantages : sécurité statique, réduction des casts, réutilisabilité.

Polymorphisme d'inclusion : héritage/implémentation d'interfaces en PO (Java). Diffère du polymorphisme paramétrique.

Compilation et modularité : certains langages compilent une seule instance générique (OCaml/Java), d'autres génèrent du code pour chaque instanciation (templates C++ / macros C).

🔁 Ordres supérieurs et fonctions comme valeurs

Les fonctions peuvent être passées en argument, retournées, stockées. Exemples pratiques : map, reduce, iter. En OCaml, ces fonctions sont naturellement polymorphes : map : (’a -> ’b) -> ’a list -> ’b list.

Captures et fermetures : une fonction garde accès à l'environnement lexical où elle a été définie ; la représentation d'une fonction à l'exécution est une fermeture (pointeur code + valeurs capturées). En Java/Python, on simule souvent une fermeture via un objet avec état.

🧠 Inférence de types (Damas–Hindley–Milner)

Objectif : inférer automatiquement les types sans annotations explicites. On distingue deux phases :

• génération de contraintes (variables de type TVar pour inconnues),
• résolution par unification (mise à jour d'une solution mutable sol : TVar -> type).

Types de base dans l'algorithme : int, t1 -> t2, variables de type TVar; plus tard on introduit paramètres de type (TParam, notés 'a) pour le polymorphisme.

Algorithme de typage (règles importantes) :

• n (entier) -> type int
• var -> env(var)
• fun v -> e : créer t1 = fresh(); typer e avec env[v -> t1] et résultat t1 -> t2
• (e1 e2) : t1 = type(e1), t2 = type(e2), t3 = fresh(); ajouter contrainte t1 = t2 -> t3, retourner t3
• let v = e1 in e2 : typer e1, généraliser si nécessaire, ajouter au env pour e2
• if e1 = 0 then e2 else e3 : contraindre e1 : int et t2 = t3

⚙️ Unification et utilitaires

Fonctions-clés : apply(t, sol) (applique les substitutions connues dans sol), subst(t, v, u) (remplace occurrences de v par u), occurs(v, t) (évite les cycles), add(sol, t1, t2) (ajoute contrainte et met à jour sol). L'algorithme garantit que sol n'a pas de variables résolues contenant d'autres variables résolues (après apply/subst).

🔁 Polymorphisme let (gen/inst)

Pour autoriser le polymorphisme, distinguer variables de type résolues (TVar) et paramètres de type (TParam, ex. 'a). Deux opérations :

• gen(t) : généralise un type en remplaçant les TVar non résolues par des TParam ('a, 'b...).
• inst(t) : instancie un type polymorphe en remplaçant ses TParam par TVar fraîches.

Règle importante : ne généraliser que les types complètement résolus (après apply(sol, t)) pour éviter de généraliser des variables qui auront ultérieurement une solution.

🧩 Extensions et précautions

• Paires polymorphes : ajouter type t × t et gérer inst/gen pour pair, fst, snd.
• Références/mutabilité : la généralisation auto pour des références est dangereuse (exposé via 'weak' en OCaml). Certaines limitations existent en pratique (références, recursivité, modules).

✅ Exemples pratiques et comparaisons

Comparaison OCaml vs Java vs Python pour fonctions/ordres supérieurs :

• OCaml : récursion et listes immuables, inférence riche.
• Java : interfaces fonctionnelles, lambdas et génériques, effacement des types à la compilation.
• Python : valeurs polymorphes sans vérification statique, style plus impératif et compréhensions.

Conseil d'étude : jouer les exemples (map, reduce, iter), suivre l'algorithme d'inférence sur des petits programmes et vérifier l'évolution de sol lors de l'unification.

📝 Travaux dirigés — Exercices et tâches (TD4-etu.pdf)

Objectifs du TD Pratiquer les fonctions d'ordre supérieur, le polymorphisme, et implémenter l'inférence de types (monomorphe puis polymorphe) selon les étapes vues en cours.

🔧 Exercice 1 — Listes et ordres supérieurs

Tâches principales :

• Implémenter en OCaml une fonction sum pour sommer une liste d'entiers (type attendu : int list -> int).
• Implémenter reduce (fold_left) terminal, puis montrer comment sum est une application partielle de reduce.
• Implémenter map_reduce (appliquer f à chaque élément puis réduire). Définir compose et dériver map_reduce à l'aide de compose, map et reduce.
• Donner les types de map, reduce, compose, map_reduce.
• Implémentations équivalentes en Java (List, Function<T,U>, BiFunction) et versions optionnelles en Java/Python (lambda, functools.reduce) et une version sans liste intermédiaire.

Indices techniques : utiliser l'application partielle en OCaml, boucles for-each en Java, lambda et functools.reduce en Python. Pour la version sans liste intermédiaire, faire une réduction accumulant la transformation.

🔐 Exercice 2 — Représentation des fermetures

Analyse du code OCaml : définir le type de app_ml = app ml, montrer le comportement de app_ml 5 ;; app_ml 10 ;;. Représenter graphiquement les fermetures pour des fonctions qui capturent un état mutable (ex. compteur c = {contents = 0}), préciser l'environnement capturé par next et reset (références vers c.contents partagées ou distinctes selon mk_counter).

🔁 Exercice 3 — Continutations

Programme mystere utilisant continuation explicite : comprendre la trace d'exécution de mystere [2;3;4], expliquer le rôle de k (accumulateur de continuation), puis réécrire l'algorithme en style direct (sans continuation explicite). Ce TD illustre comment les continuations transforment la structure du calcul (accumulation de fonctions de suite).

🧩 Exercice 4 — Inférence de types (gros projet)

Étapes demandées :

1. Définir structures de données pour type et expr, et un env mutable Var -> type.
2. Implémenter fresh(): unit -> string (compteur global de TVar fraîches) et fonctions d'affichage.
3. Implémenter occurs(v, t), subst(t, v, u) et apply(t, sol).
4. Implémenter add(sol, t, u) : algorithme d'unification qui met à jour sol en place, signale une erreur si impossible.
5. Cas de test pour unification (construites et non satisfaisables). Réinitialiser sol avant chaque test.
6. Implémenter la fonction type (typprog) : parcours récursif des expressions, génération des contraintes, utilisation d'add et apply. Gérer environment des variables d'expression et la table de solutions.
7. Étendre au polymorphisme : ajouter TParam, implémenter gen (généralisation) et inst (instanciation), mettre à jour typprog pour généraliser sur let et instancier lors d'accès aux variables.
8. Tests : programmes corrects, erreurs de type, fonctions récursives et d'ordre supérieur.
9. Extension optionnelle : support des paires polymorphes ou autre constructeur choisi.

Conseils pratiques : commencer par l'inférence monomorphe, bien tester apply/subst/occurs/add séparément avant d'attaquer typprog. Lors de la généralisation, appeler apply(sol, t) pour s'assurer que seules les TVar non résolues deviennent des paramètres.

📂 Déploiement et rendu

Indication : l'exercice 4 doit être rendu sur le GitLab dédié (faire un fork du projet TME4 et pousser les contributions).

🗒️ Note utilisateur — Contexte et conseils d'utilisation (text:user-input)

Contexte fourni : le document principal est le cours (cours-4_ok.pdf) et les exercices associés sont dans TD4-etu.pdf. Cette note récapitule l'ordre recommandé d'étude et les points d'attention.

🧭 Ordre recommandé d'étude

1. Lire rapidement le cours pour comprendre les concepts : polymorphisme, ordres supérieurs, fermetures et l'algorithme Damas–Hindley–Milner.
2. Travailler les exercices pratiques du TD dans l'ordre (listes & reduce → fermetures → continuations → inférence). Cela aide à consolider les aspects théoriques.
3. Pour l'inférence : implémenter d'abord les utilitaires (fresh, occurs, subst, apply), tester-les isolément, puis implémenter add (unification) et enfin la fonction de typage récursive.

✅ Points d'attention

• Toujours appliquer apply(sol, t) avant de généraliser pour éviter de généraliser des variables déjà résolues.
• Vérifier occurs pour éviter lier une TVar à un type qui la contient (cycle).
• Tester des cas d'erreur (contradiction d'unification) pour s'assurer que add signale correctement l'échec.
• Pour les fermetures, bien distinguer valeurs copiées (immuables) et références partagées (mutables) lors de la représentation graphique.

💡 Astuces pratiques

• En OCaml, exploiter le pattern matching pour implémenter proprement le typage récursif et la traversée d'expressions.
• En Java, utiliser java.util.function et List pour les versions génériques des exercices fonctionnels.
• En Python, functools.reduce et lambdas pour des prototypes rapides.

Bonne étude : lisez le cours, codez les petits exemples, puis attaquez l'inférence étape par étape.