# AP3 · 2 — Exécuter sans regarder l’arbre ## Notre question Nous savons retrouver des instructions dans des octets. Il reste à choisir leur ordre et à leur donner un effet. Nous allons compiler un arbre arithmétique d'AP2 en une liste d'instructions, l'assembler en octets, puis exécuter ces seuls octets : la machine n'aura plus jamais l'arbre sous les yeux. > **Repères.** [Slides 20 à 29](https://ap-2026.noce.fr/slides/AP3.html#20) : parcours postordre, machines à pile, état et cycle de la machine, invariant de pile. Elixir : la pile est une liste, `with` enchaîne les étapes. Poly, chap. 3, 4 et 6. Vous partez d'arbres d'AP2 écrits à la main : aucun téléchargement, aucun parser terminé à importer. À partir de l'étape 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. > 💡 Les étapes suivent une progression ; je préciserai en cours les notebooks à travailler et ceux à rendre. La cellule suivante définit `Check`, notre petit outil de vérification : `Check.equal(obtenu, attendu)` lève une erreur, avec les deux valeurs, si elles diffèrent ; `Check.error(valeur)` exige un tuple `{:error, raison}`. Évaluez-la une fois, puis lancez les cellules de vérification après chaque modification. ```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 ``` ## Quelle mémoire a notre machine ? Une machine classique expose des *registres* de calcul nommés, de petites cases dans le processeur, par ex. `r0` et `r1`, et chaque instruction dit dans lesquels prendre ses opérandes. Notre machine est une *machine à pile* : les opérandes d'un calcul sont implicitement les valeurs au sommet d'une pile, et le résultat y retourne. Nous ne simulons donc pas de banc de registres généralistes. Voici les données qui décrivent notre machine : | Élément | Représentation dans la VM | Rôle | | --- | --- | --- | | Code | binaire immuable | instructions et opérandes encodés | | PC | entier, adresse en octets | indique quoi décoder ensuite | | Pile de valeurs | liste, sommet à gauche | résultats intermédiaires du calcul | | Cases locales | map `case => valeur` | mémoire des variables, à l'étape 3 | | Budget et trace | entier et liste | outils de l'émulateur pour observer et arrêter | Lisons ce tableau. Le code est le binaire de l'étape 1 ; il ne change jamais pendant l'exécution. Le PC est un registre de contrôle au sens conceptuel : un entier qui dit quelle adresse décoder ensuite. La pile de valeurs est une liste Elixir dont le sommet est la tête, à gauche : empiler `3.0` sur `[8.0]` donne `[3.0, 8.0]`, et dépiler retire cette tête. Les cases locales attendront l'étape 3 ; nous transportons dès maintenant une map vide `%{}` pour ne pas changer la forme de la boucle plus tard. Le budget de pas et la trace sont des outils de l'émulateur, pas des données du programme cible. Dans une vraie machine à pile, un registre SP (*stack pointer*) repère l'adresse du sommet ; notre liste suffit et nous n'entretenons pas de SP. La pile de valeurs du langage ne doit pas être confondue avec la pile d'appels d'Elixir, celle qui exécute cet émulateur. ### Prédire une trace Une *trace* est la liste des états de la machine, relevés avant chaque instruction. Sans exécuter, complétez les états du programme `push 8.0 ; push 3.0 ; minus ; halt` : PC, instruction, pile. Quelle valeur faut-il soustraire à quelle autre lorsque la pile vaut `[3.0, 8.0]` ? Pour compiler un nœud `left - right`, nous devons produire ses deux valeurs avant la soustraction. Le parcours *postordre* visite le fils gauche, le fils droit, puis émet l'opération du parent ; l'opération vient donc après ses enfants, exactement comme dans la notation polonaise inverse de la calculatrice à pile d'AP1. Choisissez un arbre où inverser les fils change le résultat ; une addition seule serait un mauvais témoin. ## Reprise — codec et concaténation > 💡 `Enum.reduce_while(list, initial, fn item, acc -> ... end)` parcourt > une liste en passant chaque élément et un accumulateur à une fonction > anonyme. Celle-ci rend `{:cont, nouvel_acc}` pour continuer ou > `{:halt, résultat}` pour s'arrêter aussitôt. Par ex. > `Enum.reduce_while([1, 2, 3], 0, fn n, total -> {:cont, total + n} end)` > rend `6`. Cette fonction permet d'arrêter l'assemblage à la première > erreur. Une récursion explicite avec les mêmes états convient tout aussi > bien : c'est l'accumulateur d'AP1. > > `with {:ok, value} <- operation(), do: next(value)` n'exécute `next` que si > le résultat d'`operation()` correspond au motif `{:ok, value}` ; sinon la > valeur qui n'a pas correspondu, typiquement `{:error, raison}`, est rendue > directement. Plusieurs lignes `<-` propagent ainsi la première erreur > rencontrée. Enfin, `<>` concatène deux binaires : `<<1>> <> <<2, 3>>` vaut > `<<1, 2, 3>>`, et `<<>>` est le binaire vide. Copiez **votre module `MiniBytecode` de l'étape 1** dans cette cellule, à la place des commentaires. Ajoutez `assemble(instructions)` : encodez chaque instruction, concaténez les binaires et rendez `{:ok, binaire}`, ou propagez la première erreur d'encodage. `Enum.reduce_while/3` ou une récursion avec accumulateur conviennent. Cet assembleur provisoire ne connaît pas encore les étiquettes ; l'étape 4 le remplacera. ```elixir # Copiez ici votre MiniBytecode de l'étape 1. # Ajoutez assemble/1 dans ce module, avec les fonctions auxiliaires utiles. ``` ### Vérifier la continuité Ce premier essai ne dépend ni du compilateur ni de la VM à écrire ensuite : il relit `push 8.0` à l'adresse `0`, puis assemble deux instructions en dix octets. ```elixir Check.equal(MiniBytecode.decode_at(<<1, 8.0::float-big-64, 0>>, 0), {:ok, {:push, 8.0}, 9}) Check.equal(MiniBytecode.assemble([{:push, 8.0}, :halt]), {:ok, <<1, 8.0::float-big-64, 0>>}) ``` ## Concevoir le parcours de compilation Le compilateur reçoit les arbres d'AP2 : `{:number, 8.0}` et `{:bool, true}` pour les feuilles, `{:neg, arbre}` pour le moins unaire et `{:binary, op, gauche, droite}` pour une opération, où `op` est l'un des atomes `:plus`, `:minus`, `:multiply`, `:divide`, `:lt`, `:eq`. Ainsi `8.0 - 3.0` est `{:binary, :minus, {:number, 8.0}, {:number, 3.0}}`. La clause du nombre donne un exemple : une feuille produit une liste d'une seule instruction. Ajoutez les autres clauses de `emit/1`. Pour `{:bool, true}`, produisez une instruction ; pour `{:neg, arbre}` et `{:binary, op, gauche, droite}`, combinez avec `++` les listes obtenues récursivement, dans l'ordre du postordre. Rendez `{:ok, instructions}` ou une erreur explicite pour un arbre hors de ce sous-langage, par ex. une fonction ; la garde `when op in [...]` peut vous servir à n'accepter que les opérateurs connus. `compile/1`, fournie, assemble votre résultat et ajoute `halt`. La compilation n'évalue jamais le calcul : aucune addition Elixir des valeurs de l'arbre n'est nécessaire, ni souhaitable. ```elixir defmodule MiniCompiler do def compile(tree) do with {:ok, code} <- emit(tree), do: MiniBytecode.assemble(code ++ [:halt]) end def emit({:number, value}), do: {:ok, [{:push, value}]} def emit(_tree), do: {:error, :a_concevoir} end ``` ## Concevoir la boucle lire / décoder / exécuter Le squelette fournit les contrats. `run(binary, limit \\ 10_000)` déclare un second argument facultatif : `MiniVM.run(binary)` accorde dix mille pas, `MiniVM.run(binary, 2)` en accorde deux. `trace/2` lance `loop/6` avec le PC `0`, une pile vide, des cases vides, le budget et une trace vide. Les noms commençant par `_` sont des arguments encore inutilisés : donnez-leur de vrais noms quand vous écrivez la clause. La transition de `push`, `step/4`, donne un exemple : elle reçoit l'instruction, l'adresse suivante `next`, la pile et les cases, et rend le nouvel état `{:ok, next, [value | stack], locals}`. Écrivez les transitions des autres instructions, puis la boucle `loop/6` en entier. Commencez par `push`, `minus` et `halt` pour retrouver la trace précédente, puis l'addition. Nous pouvons construire la boucle ensemble ; les autres opérations se généralisent selon le point d'arrêt annoncé. Les vérifications sont séparées en un premier passage sur la soustraction, puis des extensions. Voici le contrat des transitions. `halt` exige une pile avec exactement une valeur et rend `{:halt, valeur}`. Un booléen s'empile comme un nombre. `neg` remplace le nombre au sommet par son opposé. Un opérateur binaire dépile droite puis gauche, c-à-d. que le motif `[right, left | stack]` nomme les deux premières valeurs, et empile son résultat. Rendez `{:error, raison}` si la pile manque d'opérandes, si les types ne conviennent pas, par ex. un booléen dans une addition, ou si une division a un diviseur nul. Toutes les autres transitions rendent `{:ok, nouveau_pc, nouvelle_pile, cases}`. Les gardes `is_float/1` et `is_boolean/1` distinguent les types. La boucle enchaîne cinq gestes à chaque tour : 1. Avec un budget nul, rendre `{:error, :step_limit}`. 2. Lire l'instruction au PC avec le codec : c'est le *fetch* et le *decode*. 3. Enregistrer l'état avant son exécution dans la trace. 4. Appliquer `step(instruction, pc_suivant, pile, cases)` : c'est l'*execute*. 5. S'arrêter sur `{:halt, valeur}` ; sinon recommencer sur le nouvel état avec un budget diminué de un. Une erreur de transition est rendue sous la forme `{:error, {pc, raison}}`, avec l'adresse de l'instruction fautive, ce qui permet de la retrouver dans le listing. Le résultat de `trace/2` est `{:ok, valeur, états}`, les états dans l'ordre chronologique. Chaque état est une map à clés atomes, `%{pc: pc, instruction: instruction, stack: pile, locals: cases}`, que l'on lit ensuite avec un point : `etat.pc`. Cette boucle récursive transmet son état dans les arguments : on retrouve l'accumulateur et la récursion terminale d'AP1, le `halt` jouant le rôle du cas de base. ```elixir defmodule MiniVM do def run(binary, limit \\ 10_000) do with {:ok, value, _trace} <- trace(binary, limit), do: {:ok, value} end def trace(binary, limit \\ 10_000), do: loop(binary, 0, [], %{}, limit, []) defp loop(_binary, _pc, _stack, _locals, _fuel, _trace), do: {:error, :a_concevoir} defp step({:push, value}, next, stack, locals), do: {:ok, next, [value | stack], locals} defp step(_instruction, _next, _stack, _locals), do: {:error, :a_concevoir} end ``` ## Vérifier des choix qui pourraient sembler équivalents > 💡 `{:ok, binary} = MiniCompiler.compile(tree)` lie `binary` si la > compilation réussit, et lève une `MatchError` sinon : c'est voulu, le > message montre alors l'erreur rendue. `Enum.map(states, & &1.pc)` construit > la liste des PC ; la capture `& &1.pc` abrège `fn state -> state.pc end` et > lit la clé `:pc` d'une map. `Enum.at(states, 2)` lit le troisième état, car > les indices commencent à zéro, et `List.last/1` le dernier. Ces fonctions > servent ici à lire vos traces. ### Premier passage : une soustraction complète Prédisez la liste des instructions avant de lancer la cellule. Ce premier passage ne demande que `push`, `minus`, `halt` et la boucle : il valide une chaîne complète, de l'arbre à la valeur. Les adresses visitées doivent être `0`, `9`, `18`, `19` ; la pile avant `minus` doit valoir `[3.0, 8.0]` et la pile finale `[5.0]`. Avec un budget de deux pas, la machine s'arrête sur `{:error, :step_limit}` avant `minus`. Les deux derniers essais sont des binaires écrits à la main : `<<5, 0>>` lance `minus` sur une pile vide, et `<<0>>` demande un résultat à une pile qui n'en a pas. ```elixir tree = {:binary, :minus, {:number, 8.0}, {:number, 3.0}} Check.equal(MiniCompiler.emit(tree), {:ok, [{:push, 8.0}, {:push, 3.0}, :minus]}) {:ok, binary} = MiniCompiler.compile(tree) {:ok, value, states} = MiniVM.trace(binary) Check.equal(value, 5.0) Check.equal(Enum.map(states, & &1.pc), [0, 9, 18, 19]) Check.equal(Enum.at(states, 2).stack, [3.0, 8.0]) Check.equal(List.last(states).stack, [5.0]) Check.equal(MiniVM.run(binary, 2), {:error, :step_limit}) Check.error(MiniVM.run(<<5, 0>>)) Check.error(MiniVM.run(<<0>>)) ``` ### Étendre les opérations et vérifier leurs limites Cette cellule attend la division, la comparaison et le refus des fonctions. Gardez le premier passage réussi pendant que vous ajoutez ces cas. La division `1.0 / 0.0` doit échouer à l'adresse `18`, celle de `divide`, avec `{:error, {18, :division_by_zero}}` ; la comparaison `1.0 < 2.0` rend `{:ok, true}` ; l'arbre d'une fonction est refusé dès la compilation. Ajoutez aussi une division dont le résultat change si l'on inverse les opérandes. ```elixir {:ok, bad} = MiniCompiler.compile({:binary, :divide, {:number, 1.0}, {:number, 0.0}}) Check.equal(MiniVM.run(bad), {:error, {18, :division_by_zero}}) {:ok, comparison} = MiniCompiler.compile({:binary, :lt, {:number, 1.0}, {:number, 2.0}}) Check.equal(MiniVM.run(comparison), {:ok, true}) Check.error(MiniCompiler.compile({:fn, ["x"], {:name, "x"}})) ``` ## Indices et mise en commun **Premier indice.** Pour `emit/1`, distinguez feuilles et nœuds ; le parent sait composer les réponses de ses enfants. Pour `loop/6`, distinguez arrêt, poursuite et erreur, comme pour le petit interpréteur d'AP2 ; un `case` sur le résultat de `step` fait ce tri. **Deuxième indice.** Le décodeur vous donne déjà le PC qui suit. Ajoutez l'état courant en tête de la trace, `[etat | trace]`, et inversez une seule fois à l'arrêt avec `Enum.reverse/1`. **Troisième indice.** Sur une opération binaire, la première valeur dépilée est l'opérande droit. Expliquez cette convention à votre voisin avec `8.0 / 2.0`, qui doit rendre `4.0` et non `0.25`. Pourquoi la VM n'a-t-elle plus besoin de connaître les parenthèses, les noms des nœuds de l'AST ou les priorités d'opérateurs ? Si vous avancez vite, calculez la hauteur maximale de pile nécessaire à un arbre et comparez à la trace de la VM. ## Avant de reprendre les slides Conservez votre tentative, un résultat prédit puis observé et une explication avec vos mots. Une fonction inachevée accompagnée d'une trace juste permet déjà de discuter de l'idée ; la mise en commun sert à comparer vos choix et à débloquer le point nécessaire pour poursuivre. À l'étape suivante, vous copierez votre propre code dans les cellules indiquées ; aucun module n'est importé implicitement d'un autre notebook. Sauvegardez ce fichier dans `AP3/`. Je préciserai en cours les notebooks à terminer et le minimum attendu, en fonction de notre avancement. Les étapes suivantes restent disponibles pour approfondir ; les prolongements non demandés sont facultatifs et peuvent apporter un bonus. Ce travail rejoint le rendu unique du cycle AP1–AP3 le 6 décembre 2026 à 23 h 59 (Paris), sans devoir intermédiaire. AP4 s'ouvrira par un quiz de dix minutes sur cette séance : relisez le chapitre 6 du poly, « Des octets aux instructions ». Nous discuterons aussi de vos choix à l'oral. Quand un bout de syntaxe vous manque, le [poly](https://ap-2026.noce.fr/poly/poly-elixir.pdf) en donne la forme avec un exemple : le langage aux chapitres 1 à 4, les octets et les binaires au chapitre 6. Pour toute question : [aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).