# AP3 · 4 — Choisir la prochaine instruction

## Notre question

Jusqu'ici, le PC avançait toujours dans l'ordre du programme. Avec `case`, une
branche doit rester inexécutée. Nous allons produire des sauts et résoudre
leurs adresses avec un assembleur à deux passes. Ensuite, nous comparerons la
machine à l'interpréteur sur un même programme.

> **Repères.** [Slides 39 à 48](https://ap-2026.noce.fr/slides/AP3.html#39) : sauts, étiquettes, premier assembleur, deux passes. Elixir : `Enum.reduce/3` avec un accumulateur, tuples comme étiquettes. Poly, chap. 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
```

## Le contrôle est un choix de chemin

Deux instructions de l'étape 1 n'ont pas encore d'effet. `jump adresse`
remplace le PC par une adresse absolue, comptée depuis le début du binaire.
`jump_false adresse` dépile un booléen : si celui-ci est faux, la VM saute à
l'adresse ; sinon, elle continue à l'adresse qui suit l'instruction. Dans les
deux cas, la condition a été consommée. Les deux branches n'ont pas besoin de
produire le même type à l'exécution ; chacune doit laisser exactement une
valeur sur la pile, pour respecter l'invariant de l'étape 2. Le mini-projet
typeur d'AP9 étudie une restriction statique supplémentaire.

Comment exécuter `case True { True -> 8.0 False -> 3.0 }` sans passer par la
branche fausse après avoir calculé `8.0` ? Dessinez les deux chemins avant de
coder. Puis remplacez `3.0` par `1.0 / 0.0` : ce calcul ne doit jamais
s'exécuter, alors qu'il est bien présent dans le binaire.

## Pourquoi un assembleur en deux passes ?

Le compilateur sait qu'il faut « sauter à la branche fausse » avant de savoir
combien d'octets occupent tous les calculs précédents. Il émet donc une
*étiquette*, un nom qui tient la place d'une adresse : `{:label, :otherwise}`
marque une position et `{:jump_false, :otherwise}` y renvoie. Notre codec
refuse un tel opérande, puisqu'il attend un entier ; c'est l'*assembleur* qui
remplacera le nom par l'adresse. Voici la liste symbolique du `case`
précédent, avec l'adresse courante avant chaque élément :

| Instruction symbolique | Adresse avant instruction | Taille |
| --- | ---: | ---: |
| `true` | 0 | 1 |
| `{:jump_false, :otherwise}` | 1 | 3 |
| `{:push, 8.0}` | 4 | 9 |
| `{:jump, :done}` | 13 | 3 |
| `{:label, :otherwise}` | 16 | **0** |
| `{:push, 3.0}` | 16 | 9 |
| `{:label, :done}` | 25 | **0** |
| `:halt` | 25 | 1 |

Lisons ce tableau. La première passe additionne les tailles et note l'adresse
atteinte à chaque étiquette : elle construit `%{otherwise: 16, done: 25}`. Une
étiquette ne produit aucun octet, d'où sa taille nulle et deux lignes
successives à la même adresse. La deuxième passe remplace les références par
des adresses, retire les étiquettes et encode les instructions.
`jump_false :otherwise` devient `<<14, 0, 16>>`, soit les trois octets
hexadécimaux `0E 00 10`, et le programme mesure 26 octets.

Prédisez les nouvelles adresses si l'on remplace `push 8.0` par trois
instructions `push 8.0 ; push 2.0 ; divide`. Pourquoi compter les
instructions, plutôt que leurs octets, donnerait-il une adresse erronée ?

## Concevoir les deux passes

> 💡 `Enum.reduce(list, initial, fn item, acc -> ... end)` parcourt une liste
> avec un accumulateur et rend sa dernière valeur ; c'est la version `Enum` de
> l'accumulateur d'AP1. L'accumulateur peut être un couple : avec `{0, %{}}`
> au départ, la fonction s'écrit `fn instruction, {pc, labels} -> … end` et
> rend le couple mis à jour. `Map.has_key?(labels, name)` teste une clé ;
> `Map.put/3` l'ajoute. `IO.iodata_to_binary([<<1>>, <<2, 3>>])` concatène
> une liste de morceaux binaires en `<<1, 2, 3>>` ; elle ne résout aucune
> adresse à votre place.

Copiez **votre module `MiniBytecode` de l'étape 3**, puis remplacez son
assembleur par `assemble/1` et ses auxiliaires. Ajoutez `size/1` d'après le
tableau : `0` pour une étiquette, `9` pour un `push`, `3` pour une instruction
à opérande entier, `1` sinon. Gardez votre codec. Rendez `{:ok, binaire}` ;
refusez les étiquettes dupliquées avec `{:error, {:duplicate_label, nom}}`,
les références absentes avec `{:error, {:unknown_label, nom}}`, les
instructions invalides, et un programme de plus de 65 535 octets avec
`{:error, :program_too_large}`. Les cas de vérification fixent ces erreurs
observables.

Séparez une passe qui localise les étiquettes d'une passe qui encode : la
première transporte l'adresse courante et la table ; la seconde transporte
la table sans la modifier et accumule les morceaux encodés, par ex. dans une
liste à concaténer à la fin.

```elixir
# Copiez ici votre MiniBytecode de l'étape 3.
# Remplacez assemble/1 par votre assembleur à deux passes.
# Ajoutez size/1 et vos fonctions auxiliaires dans ce même module.
```

## Concevoir l'émission d'un case

Copiez **votre module `MiniCompiler` de l'étape 3**. Ajoutez `label: 0` à l'état
initial, puis écrivez toute la clause `emit/3` du nœud
`{:case, condition, oui, non}`. `state.label` permet de réserver un identifiant
neuf, que vous incrémentez comme le compteur de cases ; vous pouvez en dériver
deux étiquettes, par ex. `{:else, id}` et `{:done, id}`, des tuples qui restent
distincts d'un `case` à l'autre. Réservez cet identifiant **avant** de compiler
les sous-arbres : un `case` imbriqué peut lui aussi avoir besoin d'étiquettes.

Le code émis suit le tableau précédent : la condition, un `jump_false` vers
l'étiquette « sinon », la branche vraie, un `jump` vers l'étiquette « fin »,
l'étiquette « sinon », la branche fausse, puis l'étiquette « fin ». Le
compteur de cases locales continue d'augmenter à travers les deux branches.
Leur environnement lexical reste celui du `case`. Les noms sont donc vérifiés
à la compilation dans les deux branches, même si une seule sera exécutée.
Gardez enfin les fonctions et les appels explicitement hors cible :
`{:fn, _, _}` rend `{:error, {:unsupported, :function}}` et `{:call, _, _}`
rend `{:error, {:unsupported, :call}}`.

```elixir
# Copiez ici votre MiniCompiler de l'étape 3.
# Ajoutez label: 0 à l'état initial, puis la clause emit/3 de case.
# Gardez les fonctions et les appels explicitement hors cible.
```

## Reprise — VM et validation des sauts

> 💡 `MapSet.new([0, 9, 18])` construit un ensemble sans doublon, et
> `MapSet.member?(ensemble, 9)` teste l'appartenance ; une liste et
> `adresse in liste` conviennent aussi. `elem({0, :halt}, 0)` lit la première
> case d'un tuple, de sorte que `Enum.map(listing, &elem(&1, 0))` rend les
> adresses du listing.

Copiez **votre module `MiniVM` de l'étape 3**, puis ajoutez les deux
transitions de saut à `step/4`. Pour `jump`, l'adresse suivante `next` est
ignorée au profit de l'opérande ; pour `jump_false`, refusez une condition qui
n'est pas un booléen, puis choisissez `next` ou l'opérande selon sa valeur.

Avant de démarrer la boucle, dans `trace/2`, désassemblez le programme et
vérifiez que chaque cible de saut appartient à l'ensemble des adresses du
listing ; sinon, rendez `{:error, {:invalid_jump, adresse}}`. Le codec seul ne
pouvait pas le savoir : un entier sur seize bits est toujours décodable, même
s'il tombe au milieu d'un flottant. Le budget arrête une boucle mal
construite ; il ne prouve pas sa terminaison.

```elixir
# Copiez ici votre MiniVM de l'étape 3.
# Ajoutez les transitions jump et jump_false.
# Validez les cibles avant de démarrer loop/6.
```

## Vérifier les chemins et les limites

> 💡 `for {condition, yes, no, result} <- liste do ... end` parcourt une liste
> de tuples en nommant leurs cases et exécute le bloc pour chacun.
> `binary_part(binary, 1, 3)` extrait les trois octets à partir de l'adresse
> `1`, ici ceux du `jump_false`.

Lisez les cas avant de les exécuter. La liste symbolique est celle du
tableau : 26 octets, `<<14, 0, 16>>` à l'adresse `1`, un listing de six
instructions. La trace attendue, `0, 1, 4, 13, 25`, porte sur les instructions
visitées, donc elle diffère du listing qui contient les deux branches.
Viennent ensuite les refus de l'assembleur, une étiquette inconnue, une
étiquette dupliquée, un programme de 65 536 octets, puis ceux de la VM : un
saut vers l'adresse `1`, au milieu d'un opérande, et un `jump 0` qui boucle
jusqu'à épuiser un budget de cinq pas. Les cas compilés cachent une division
par zéro dans la branche inactive, imbriquent deux `case`, et vérifient qu'une
condition qui n'est pas un booléen est refusée à l'exécution.

```elixir
symbolic = [true, {:jump_false, :otherwise}, {:push, 8.0}, {:jump, :done},
  {:label, :otherwise}, {:push, 3.0}, {:label, :done}, :halt]
{:ok, binary} = MiniBytecode.assemble(symbolic)
Check.equal(byte_size(binary), 26)
Check.equal(binary_part(binary, 1, 3), <<14, 0, 16>>)
Check.equal(MiniBytecode.disassemble(binary), {:ok,
  [{0, true}, {1, {:jump_false, 16}}, {4, {:push, 8.0}},
   {13, {:jump, 25}}, {16, {:push, 3.0}}, {25, :halt}]})
{:ok, 8.0, states} = MiniVM.trace(binary)
Check.equal(Enum.map(states, & &1.pc), [0, 1, 4, 13, 25])
Check.equal(MiniBytecode.assemble([{:jump, :missing}]), {:error, {:unknown_label, :missing}})
Check.equal(MiniBytecode.assemble([{:label, :x}, {:label, :x}]), {:error, {:duplicate_label, :x}})
Check.equal(MiniBytecode.assemble(List.duplicate(:halt, 65_536)), {:error, :program_too_large})
Check.equal(MiniVM.run(<<13, 0, 1, 0>>), {:error, {:invalid_jump, 1}})
Check.equal(MiniVM.run(<<13, 0, 0>>, 5), {:error, :step_limit})

bad = {:binary, :divide, {:number, 1.0}, {:number, 0.0}}
for {condition, yes, no, result} <- [
  {true, {:number, 8.0}, bad, 8.0}, {false, bad, {:number, 3.0}, 3.0}] do
  {:ok, program} = MiniCompiler.compile({:case, {:bool, condition}, yes, no})
  Check.equal(MiniVM.run(program), {:ok, result})
end
nested = {:case, {:bool, true},
  {:case, {:bool, false}, {:number, 0.0}, {:number, 5.0}}, {:number, 9.0}}
{:ok, program} = MiniCompiler.compile(nested)
Check.equal(MiniVM.run(program), {:ok, 5.0})
Check.error(MiniCompiler.compile({:case, {:bool, true}, {:number, 1.0}, {:name, "missing"}}))
{:ok, invalid_condition} = MiniCompiler.compile({:case, {:number, 1.0}, {:number, 2.0}, {:number, 3.0}})
Check.error(MiniVM.run(invalid_condition))
Check.error(MiniBytecode.assemble([:unknown]))
Check.equal(MiniCompiler.compile({:fn, ["x"], {:name, "x"}}), {:error, {:unsupported, :function}})
```

## Une règle que notre machine ne vérifie pas

Prédisez `case True { True -> 1.0 False -> False }`. Notre compilateur résout
les noms dans les deux branches, mais il n'exige pas qu'elles produisent le
même type. Quelle branche la VM visitera-t-elle ? Le typeur proposé en AP9
ajoutera cette règle sur les types, même pour une branche qui ne s'exécute pas.

```elixir
mixed = {:case, {:bool, true}, {:number, 1.0}, {:bool, false}}
{:ok, program} = MiniCompiler.compile(mixed)
Check.equal(MiniVM.run(program), {:ok, 1.0})
```

## Indices et mise en commun

**Premier indice.** Pour la passe 1, transportez un PC et une map des étiquettes.
Pour la passe 2, transportez cette map sans la modifier.

**Deuxième indice.** La branche vraie doit sauter par-dessus la branche fausse.
La condition du `case`, elle, est toujours évaluée. Le saut conditionnel consomme
son résultat et laisse la pile prête pour la branche choisie.

**Troisième indice.** Les étiquettes du `case` extérieur et celles d'un `case`
intérieur doivent être distinctes, même si leurs noms décrivent le même rôle.
L'état rendu par chaque sous-arbre contient les identifiants déjà consommés.

Préparez une démonstration courte pour la mise en commun : montrez le même
calcul comme AST, instructions symboliques, octets et trace. Expliquez le rôle
de l'assembleur et pourquoi la VM n'évalue qu'une branche du `case`.

### Pour aller plus loin

Les fonctions restent hors cible. Concevez sur papier un *cadre d'appel* : où
conserver l'adresse de retour, les paramètres et les variables locales ? Une
fermeture d'AP2 demanderait en plus de conserver l'environnement de définition.
Autre piste : ajoutez un désassembleur lisible, ou un calcul de hauteur de pile
vérifiant que les deux branches rejoignent le même état de pile.

## 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. Comparez maintenant votre machine à l'interpréteur sur un même programme,
avec une trace et un contre-exemple.

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).