# AP3 · 1 — Donner un sens aux octets ## Notre question Le processeur de votre ordinateur ne lit pas un arbre Elixir : il lit des *octets*, c-à-d. des nombres entre 0 et 255, rangés les uns après les autres en mémoire. Nous allons définir une petite architecture dont les programmes sont de vrais binaires, puis, au fil des étapes, une machine qui les exécute. L'architecture est fictive ; son code ne tournerait pas tel quel sur un processeur ARM ou x86, mais les questions qu'elle pose sont les mêmes. Aujourd'hui, nous décidons comment retrouver une instruction dans une suite d'octets qui ne contient aucun séparateur. > **Repères.** [Repères CPU, slides 7 à 11](https://ap-2026.noce.fr/slides/AP3.html#7) : mémoire, registres, PC et cycle d'exécution, cache, pile, programme en mémoire. [Atelier, slides 12 à 19](https://ap-2026.noce.fr/slides/AP3.html#12) : format des instructions, codec, syntaxe binaire. Elixir : motifs binaires `<<…>>`, `byte_size/1`. Poly, chap. 6 « Des octets aux instructions ». 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 ``` ## Un programme sans séparateurs Regardez `<<11, 1, 2>>` : trois octets. Est-ce trois instructions, ou une seule ? Les octets ne portent pas leur signification tout seuls ; il faut une convention commune à celui qui écrit le programme et à celui qui le lit. Cette convention s'appelle le *jeu d'instructions*. Notre jeu d'instructions fixe que le premier octet d'une instruction est son *opcode*, le numéro de l'opération. Selon l'opcode, l'instruction s'arrête là ou se poursuit par un *opérande*, une donnée qui l'accompagne : un numéro de case ou une adresse sur deux octets, ou bien un nombre sur huit octets. Ainsi `<<11, 1, 2>>` est une seule instruction : l'opcode `11` annonce `load`, et les deux octets suivants forment son opérande. Pour écrire un entier sur deux octets, nous adoptons l'ordre *big endian* : l'octet de poids fort vient d'abord. `1, 2` représente donc `1 × 256 + 2 = 258`, et `<<11, 1, 2>>` se lit `load 258`. Un nombre, lui, occupe huit octets au format flottant IEEE 754, la représentation standard des nombres à virgule ; nous n'avons pas besoin d'en connaître le détail, Elixir sait l'écrire et le relire pour nous. Voici le tableau complet, qui est notre contrat : | Instruction | Opcode décimal | Opérande | Taille en octets | | --- | ---: | --- | ---: | | `:halt` | 0 | aucun | 1 | | `{:push, nombre}` | 1 | flottant 64 bits big endian | 9 | | `true`, `false` | 2, 3 | aucun | 1 | | `:plus`, `:minus`, `:multiply`, `:divide` | 4, 5, 6, 7 | aucun | 1 | | `:neg`, `:lt`, `:eq` | 8, 9, 10 | aucun | 1 | | `{:load, case}`, `{:store, case}` | 11, 12 | entier 16 bits big endian | 3 | | `{:jump, adresse}`, `{:jump_false, adresse}` | 13, 14 | entier 16 bits big endian | 3 | Lisons-le ligne par ligne. Les instructions sont écrites telles qu'elles apparaîtront dans nos listes Elixir : un atome quand il n'y a pas d'opérande, un tuple `{:push, 8.0}` ou `{:load, 258}` sinon. Les booléens s'écrivent `True` et `False` dans notre petit langage, mais `true` et `false` dans la liste d'instructions. `==` compare seulement des nombres, comme en AP2. Les deux dernières lignes serviront aux étapes 3 et 4 ; nous fixons leur format dès aujourd'hui, une fois pour toutes. ### Prédire avant de coder Une *adresse* est la position d'un octet dans le programme, comptée depuis `0`. Écrivez les adresses des quatre instructions de `push 8.0 ; push 3.0 ; minus ; halt`. Quel est le nombre d'octets du programme ? Que lirait-on en commençant à l'adresse `3`, au milieu du premier flottant ? Conservez vos réponses avant d'exécuter les cellules suivantes. Le *PC* (*program counter*, ou compteur ordinal) est l'adresse en octets de la prochaine instruction à lire. Ce n'est donc pas son numéro dans la liste : la troisième instruction de notre programme n'est pas à l'adresse `2`. Le décodage doit rendre l'instruction **et l'adresse qui la suit**, car une instruction n'occupe pas toujours un seul octet. ## Concevoir le codec > 💡 Un *binaire* Elixir est une suite d'octets entre doubles chevrons : > `<<11, 1, 2>>`. L'écriture `<>` construit un > octet puis un entier non signé sur deux octets ; par ex. > `<<11, 258::unsigned-big-16>>` vaut `<<11, 1, 2>>`. La même notation, à > gauche d'un `=` ou en tête de clause, *lit* ces valeurs : > `<> = <<11, 1, 2, 0>>` lie > `opcode` à `11`, `value` à `258` et `rest` à `<<0>>`, les octets qui > suivent. `<>` écrit un flottant sur huit octets et le > relit de même. Ce sont des octets, pas forcément du texte ; `byte_size/1` > mesure leur nombre, et `binary_part(binary, position, longueur)` en extrait > un morceau. > > Les tables fournies `@simple` et `@operand` sont des *maps*, des > dictionnaires immuables : `Map.fetch(@simple, :halt)` rend `{:ok, 0}` et > `Map.fetch(@simple, :inconnu)` rend `:error`, alors que `@simple[:inconnu]` > rend `nil`. Pour retrouver l'atome à partir d'un octet, > `Enum.find(@simple, fn {_op, byte} -> byte == 0 end)` rend la paire > `{:halt, 0}`, ou `nil` si aucune paire ne convient. Le préfixe `@` désigne un > attribut du module, une constante fixée à la compilation ; ce n'est pas une > mémoire modifiable. > > Une clause peut poser une condition avec `when` : `def encode({:push, number}) > when is_float(number)` n'est choisie que pour un flottant ; `is_integer/1` et > `value in 0..65_535` s'emploient de même. Enfin, `{:error, :a_concevoir}` > marque les clauses que vous devez remplacer. Écrivez les deux fonctions entières `encode/1` et `decode_at/2`. Le listing est fourni : `disassemble/1` appelle votre décodeur en avançant d'instruction en instruction et rend `{:ok, [{adresse, instruction}, …]}`. Il utilise `with`, qui enchaîne une étape rendant `{:ok, …}` et n'exécute la suite que si le motif correspond ; sinon il rend l'erreur telle quelle. - `encode(instruction)` rend `{:ok, binaire}` ou `{:error, {:invalid_instruction, instruction}}`. - `decode_at(binaire, pc)` rend `{:ok, instruction, pc_suivant}`. Il refuse les adresses hors du binaire, les opcodes inconnus et les opérandes tronqués, avec une erreur de votre choix, par ex. `{:error, {:invalid_pc, pc}}`, `{:error, {:unknown_opcode, pc, octet}}` ou `{:error, {:truncated_operand, pc}}`. - Un opérande de `load`, `store` ou saut appartient à `0..65_535`. `push` accepte un flottant, par ex. `8.0`, et refuse un entier Elixir comme `8`. La clause de `halt` donne un exemple. Commencez par `push` et `minus`, puis étendez votre convention à tout le tableau. Le sommet d'une pile et les effets des instructions ne concernent pas encore le codec : il transforme seulement une représentation en une autre. ```elixir # Une architecture pédagogique : opcodes u8, adresses/slots u16, flottants f64. defmodule MiniBytecode do @simple %{halt: 0, true: 2, false: 3, plus: 4, minus: 5, multiply: 6, divide: 7, neg: 8, lt: 9, eq: 10} @operand %{load: 11, store: 12, jump: 13, jump_false: 14} def encode(:halt), do: {:ok, <<0>>} def encode(_instruction), do: {:error, :a_concevoir} def decode_at(_binary, _pc), do: {:error, :a_concevoir} def disassemble(binary), do: listing(binary, 0, []) defp listing(binary, pc, acc) when pc == byte_size(binary), do: {:ok, Enum.reverse(acc)} defp listing(binary, pc, acc) do with {:ok, instruction, next} <- decode_at(binary, pc), do: listing(binary, next, [{pc, instruction} | acc]) end end ``` ## Faire parler les octets ### Premier passage : nombres, soustraction et arrêt Commencez par vérifier les trois instructions recommandées, et lisez la cellule avant de la lancer. `<<1, 8.0::float-big-64>>` est le binaire attendu pour `push 8.0`, neuf octets. `binary` est le programme entier, vingt octets. `decode_at(binary, 9)` doit retrouver `push 3.0` et annoncer `18` comme adresse suivante ; le listing doit retrouver quatre instructions, même si leur taille n'est pas uniforme. Les quatre derniers essais sont des refus : une adresse négative, l'adresse `20` qui est juste après la fin, un opcode `255` qui n'existe pas et un `push` dont il manque le flottant. ```elixir Check.equal(MiniBytecode.encode({:push, 8.0}), {:ok, <<1, 8.0::float-big-64>>}) Check.equal(MiniBytecode.encode(:minus), {:ok, <<5>>}) Check.error(MiniBytecode.encode({:push, 8})) binary = <<1, 8.0::float-big-64, 1, 3.0::float-big-64, 5, 0>> Check.equal(byte_size(binary), 20) Check.equal(MiniBytecode.decode_at(binary, 9), {:ok, {:push, 3.0}, 18}) Check.equal(MiniBytecode.disassemble(binary), {:ok, [{0, {:push, 8.0}}, {9, {:push, 3.0}}, {18, :minus}, {19, :halt}]}) Check.error(MiniBytecode.decode_at(binary, -1)) Check.error(MiniBytecode.decode_at(binary, 20)) Check.error(MiniBytecode.decode_at(<<255>>, 0)) Check.error(MiniBytecode.decode_at(<<1, 0>>, 0)) ``` ### Étendre aux opérandes entiers Ajoutez ensuite les instructions portant une case ou une adresse. Ces essais vérifient l'ordre des octets, `<<11, 1, 2>>` pour `load 258`, la limite sur seize bits, puisque `65_536` ne tient pas sur deux octets, et le refus d'un opérande incomplet. Les encoder ne demande pas encore de savoir les exécuter. Ajoutez un aller-retour personnel : une instruction de votre choix, encodée puis décodée, doit revenir à l'identique. ```elixir Check.equal(MiniBytecode.encode({:load, 258}), {:ok, <<11, 1, 2>>}) Check.error(MiniBytecode.encode({:load, 65_536})) Check.equal(MiniBytecode.decode_at(<<11, 1, 2>>, 0), {:ok, {:load, 258}, 3}) Check.error(MiniBytecode.decode_at(<<11, 0>>, 0)) ``` ## Indices, si le besoin se présente **Premier indice.** Séparez trois familles : les opcodes sans opérande, ceux suivis d'un entier et le cas du flottant. Les deux maps fournies évitent de répéter le tableau dans vos clauses. **Deuxième indice.** `<<1, number::float-big-64>>` écrit neuf octets ; `<>` en écrit trois. La même syntaxe dans un motif lit ces valeurs, et `rest::binary` capture les octets qui suivent. **Troisième indice.** Vérifiez d'abord `0 <= pc < byte_size(binary)`, extrayez le suffixe avec `binary_part(binary, pc, byte_size(binary) - pc)`, puis reconnaissez ses premiers octets avec un motif par forme. Placez la clause qui reconnaît un opérande tronqué, par ex. `<<1, _::binary>>`, après la clause complète et avant le cas « opcode inconnu ». ### Pour la mise en commun Reprenez votre prédiction sur l'adresse `3` : l'octet y vaut `0`, et votre décodeur, lancé là, répond `halt`, alors qu'aucune instruction ne commence à cette adresse. Expliquez pourquoi le décodeur ne peut pas reconnaître à lui seul qu'une adresse pointe au milieu d'un opérande. Proposez une information supplémentaire permettant de valider les cibles des futurs sauts. Si vous avancez vite, ajoutez un affichage hexadécimal. `Base.encode16/1` est fourni par Elixir : `Base.encode16(<<11, 1, 2>>)` rend `"0B0102"`, deux chiffres par octet. Distinguez cette écriture hexadécimale des adresses décimales du listing. ## 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).