# Mini-typeur · Carnet 3 — Inférer des fonctions ## Notre question Le solveur sait rendre compatibles des types contenant des inconnues. Relions-le maintenant à un parcours de l'AST. Nous voulons retrouver le type d'une fonction à partir de la façon dont elle utilise ses paramètres. > **Repères.** [Slides 22 à 29](https://ap-2026.noce.fr/slides/AP9-typeur.html#22) : inconnue fraîche par paramètre, type d'un appel. Elixir : un état en map `%{next: …, sub: …}`, `Enum.map_reduce/3`. Poly, chap. 5. Vous partez d'arbres d'AP2 écrits à la main ; le squelette du projet fournit le lexer et le parser pour tester ensuite depuis le texte. À partir du carnet 2, copiez vos propres modules précédents aux emplacements indiqués, car chaque Livebook a sa propre session. Réévaluez la cellule entière après avoir modifié un module ; les vérifications signalent une erreur tant que les fonctions demandées ne sont pas écrites. Prédisez d'abord leurs résultats. Vous pouvez ajouter des fonctions auxiliaires. > 💡 Nous choisirons en cours le point de passage selon votre avancement. ```elixir defmodule Check do def equal(actual, expected) do if actual != expected do raise "Attendu #{inspect(expected)}, obtenu #{inspect(actual)}" end :ok end def error({:error, _}), do: :ok def error(value), do: raise("Une erreur était attendue : #{inspect(value)}") end ``` ## Trois informations à faire circuler Le typeur transporte un environnement de noms, un compteur d'inconnues et une substitution. Il faut les distinguer : `%{"x" => {[], {:var, 0}}}` associe un nom au type de son paramètre ; `%{0 => :float}` contraint cette inconnue. Le compteur `next` fabrique des inconnues différentes, même quand deux fonctions utilisent le même nom de paramètre. Nous réservons dès maintenant la représentation `{quantifiées, type}` dans l'environnement. Pour cet atelier, `quantifiées` vaut toujours `[]` : chaque nom désigne un seul type partagé entre toutes ses occurrences. Il n'y a donc pas encore de polymorphisme de `let`. ### Suivre fn(x) { x + 1.0 } 1. Le paramètre reçoit une inconnue neuve `t0`. L'environnement local associe `x` à `{[], t0}`. 2. Le corps contient une addition ; elle exige `t0 = Float` et `Float = Float`. 3. Le solveur enregistre la première contrainte. Le corps a le type `Float`. 4. Le type initial `fn(t0) -> Float`, une fois résolu, devient `fn(Float) -> Float`. Prédisez à présent les types de `fn(x) { x }`, `fn(x) { True }` et `fn(f) { f(1.0) }`. Dans le dernier exemple, le type de retour de `f` n'est pas encore connu. Quel type peut-on néanmoins imposer à `f` ? ## À l'appel, une fonction doit avoir la bonne forme Pour typer `f(a)`, inférez le type de `f` et celui de `a`, puis créez une inconnue neuve pour le résultat. Unifiez le type de `f` avec `fn(type_de_a) -> résultat`. Cette seule contrainte vérifie qu'il s'agit d'une fonction et que l'arité convient. Une fonction à deux paramètres a une liste de deux types, et non deux appels successifs implicites. ## Faire évoluer votre typeur Copiez **votre module `MiniTypes` du carnet 2**. Gardez le solveur ; remplacez le parcours direct `infer/1` par une entrée publique qui lance `visit(tree, %{}, %{next: 0, sub: %{}})` puis résout le type final. `visit/3` rend `{:ok, type, état}` ou une erreur. Les règles de nombres, booléens, opérations et `case` restent les mêmes, mais leurs contraintes passent maintenant par `unify/3`. Propagez l'état rendu par chaque sous-arbre. Un exemple représentatif de fabrication d'inconnue : `fresh(state)` peut rendre `{{:var, state.next}, %{state | next: state.next + 1}}`. Écrivez les clauses suivantes : - Un nom lit `{[], type}` dans `env`, ou rend une erreur de nom absent. - Une fonction `{:fn, paramètres, corps}` donne une inconnue neuve à chaque paramètre, étend l'environnement pour son seul corps et rend un type fonction. - Un appel `{:call, fonction, arguments}` génère la contrainte décrite plus haut. - Un `{:let, nom, valeur, suite}` infère la valeur, puis associe son unique type à ce nom pour typer la suite. La valeur ne voit pas le nom en cours de définition. Commencez par une fonction à un paramètre et un appel à un argument ; étendez ensuite aux listes de paramètres. Les fonctions Elixir auxiliaires vous permettent de séparer fabrication d'inconnues, contraintes et parcours d'une liste. ```elixir # Copiez ici votre module MiniTypes du carnet 2. # Gardez resolve/2, free/1, unify/3 et leurs auxiliaires. # Remplacez infer/1 par l'entrée décrite ; ajoutez visit/3 et les auxiliaires. # L'environnement associe chaque nom à {[], type} à cette étape. ``` ## Vérifier le type obtenu, pas une numérotation arbitraire La première vérification de `id` observe une propriété : son argument et son résultat portent la même inconnue. Les numéros exacts dépendent de votre parcours. Pour les fonctions plus complexes, comparez les types après résolution. ```elixir identity = {:fn, ["x"], {:name, "x"}} {:ok, {:fun, [argument], result}} = MiniTypes.infer(identity) Check.equal(argument, result) Check.equal(MiniTypes.infer({:fn, ["x"], {:binary, :plus, {:name, "x"}, {:number, 1.0}}}), {:ok, {:fun, [:float], :float}}) Check.equal(MiniTypes.infer({:call, identity, [{:bool, true}]}), {:ok, :bool}) Check.equal(MiniTypes.infer({:call, {:fn, [], {:bool, true}}, []}), {:ok, :bool}) Check.error(MiniTypes.infer({:call, identity, []})) Check.error(MiniTypes.infer({:call, {:number, 1.0}, [{:number, 2.0}]})) Check.error(MiniTypes.infer({:fn, ["x"], {:call, {:name, "x"}, [{:name, "x"}]}})) Check.error(MiniTypes.infer({:name, "absent"})) # Une inconnue partagée ne peut pas être tantôt Float, tantôt Bool. mono = {:let, "id", identity, {:let, "n", {:call, {:name, "id"}, [{:number, 1.0}]}, {:call, {:name, "id"}, [{:bool, true}]}}} Check.error(MiniTypes.infer(mono)) ``` ## Indices **Premier indice.** À l'entrée d'une fonction, les paramètres masquent des noms de l'environnement extérieur, mais les autres noms restent visibles. C'est la portée lexicale rencontrée avec les fermetures d'AP2. **Deuxième indice.** Créer une inconnue change `next`, unifier change `sub`. Ne repartez jamais d'un ancien état après avoir parcouru un sous-arbre. **Troisième indice.** À l'appel, le type attendu a la forme `{:fun, types_des_arguments, inconnue_du_résultat}`. Le type des arguments se calcule dans l'environnement de l'appelant ; il n'est pas nécessaire de connaître les valeurs ni d'exécuter le corps de la fonction. Expliquez l'erreur du dernier test. Est-ce la fonction identité qui est incohérente, ou notre règle de partage du type à travers le `let` qui est trop restrictive ? Ce souci motive le carnet suivant. Si vous avancez vite, inférez `fn(f, x) { f(f(x)) }` à la main, puis construisez son AST. Justifiez pourquoi `f` doit renvoyer un type qu'il accepte aussi en entrée. ## Avant de passer au carnet suivant Conservez votre tentative, un résultat prédit puis observé et une explication avec vos mots. Au carnet suivant, vous copierez votre propre code dans les cellules indiquées ; aucun module n'est importé implicitement d'un autre notebook. Vous pouvez reporter vos règles dans le squelette `mini-typeur` (`lib/`), puis utiliser ses tests de paliers : `mix test`, `mix test --include argent`, `mix test --include argent --include or`. Le squelette et les notebooks ont des noms de modules différents : adaptez les appels plutôt que de copier un fichier sans le relire. Ces carnets préparent le sujet Types du projet noté d’AP9, hors du rendu AP1–AP3. Le projet commence en semi-autonomie et se termine à la maison. Les supports restent des bases à affiner d’ici janvier ; le périmètre, le barème et l’échéance seront précisés avant le lancement. D’ici là, gardez vos essais dans `entrainement/`. Pour toute question : [aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).