# Atelier facultatif — Un petit langage à pile ## Prolonger la calculatrice d'AP1 En AP1, le carnet `ap1-05-pile-calculatrice.livemd` construit une calculatrice à pile à partir de morceaux lus dans une chaîne. Ce notebook est un prolongement facultatif de 45 min, pour les élèves qui ont fini en séance ou pour un travail après AP2. Il ne constitue pas un prérequis des cinq carnets de l'interpréteur à arbre. Nous allons interpréter une liste de tokens dans l'ordre où ils apparaissent. Ce notebook est autonome : les tokens sont fournis, et votre lexer n'est pas nécessaire pour commencer. Comptez 10 min pour la trace guidée puis 35 min de travail accompagné sur le code et ses vérifications. Une *pile* garde les valeurs en attente ; sa tête est son sommet. Un entier est empilé. Un opérateur prend les deux valeurs au sommet, calcule un résultat et l'empile à leur place. L'opérateur vient donc après ses arguments : `3 4 + 2 *` signifie « additionner 3 et 4, puis multiplier le résultat par 2 ». C'est la notation *postfixe*. Sauvegardez cet atelier dans `entrainement/`. Le seul fichier collecté pour AP2 est la série des cinq notebooks numérotés dans `AP2/`, consacré à l’interpréteur à arbre. Évaluez les cellules dans l'ordre. Remplacez les `nil` à compléter, puis lancez les vérifications fournies. Si une vérification échoue, reprenez le cas indiqué et réévaluez votre code. Dans les vérifications, `for {tokens, attendu} <- liste do … end` parcourt chaque couple de la liste, et `if … do raise … end` arrête la cellule avec un message si un cas échoue. Ce sont des outils fournis, que vous n'avez pas à réécrire. ## Suivre l'état de la pile (10 min) Regardons le programme `3 4 + 2 *`, dont les tokens sont `[{:int, 3}, {:int, 4}, :plus, {:int, 2}, :multiply]`. | Token consommé | Pile après l'étape, sommet à gauche | |---|---| | aucun | `[]` | | `{:int, 3}` | `[3]` | | `{:int, 4}` | `[4, 3]` | | `:plus` | `[7]` | | `{:int, 2}` | `[2, 7]` | | `:multiply` | `[14]` | À la fin, la pile doit contenir exactement une valeur. Nous renvoyons alors `{:ok, 14}`. Pourquoi serait-il incorrect d'accepter une pile finale vide, ou une pile qui contient encore deux valeurs ? Tracez maintenant `8 3 -` sur papier. Au moment de soustraire, la pile vaut `[3, 8]`. Dans le motif `[b, a | pile]`, nous calculons donc `a - b`. **L'ordre des arguments compte.** Avec l'addition seule, cette erreur pourrait passer inaperçue ! ## Compléter l'interpréteur (35 min) `Pile.eval/1` démarre avec une pile vide, puis appelle `parcourir/2`. Ce deuxième argument est l'accumulateur. Cette fois, c'est une liste qui représente l'état du calcul. Complétez les quatre clauses marquées `nil` : l'entier empile sa valeur, les opérateurs `:plus`, `:minus` et `:multiply` remplacent les deux nombres au sommet par leur résultat. Poursuivez ensuite sur les tokens restants. Les tokens `{:int, nombre}` fournis contiennent des entiers non négatifs ; un calcul peut toutefois produire un résultat négatif. Les clauses d'erreur sont fournies : - `{:error, :operandes_manquants}` si un opérateur n'a pas deux nombres ; - `{:error, :pile_finale_invalide}` si la pile finale n'a pas une valeur ; - `{:error, :symbole_inconnu}` pour un autre token, notamment une parenthèse. Le lexer peut reconnaître davantage de symboles que notre petit langage à pile n'en accepte. Dans cette notation, les parenthèses sont inutiles : l'ordre des opérations est donné par l'ordre des tokens. ```elixir defmodule Pile do def eval(tokens) do parcourir(tokens, []) end def parcourir([], [resultat]) do {:ok, resultat} end def parcourir([], _pile) do {:error, :pile_finale_invalide} end def parcourir([{:int, nombre} | reste], pile) do nil end def parcourir([:plus | reste], [b, a | pile]) do nil end def parcourir([:minus | reste], [b, a | pile]) do nil end def parcourir([:multiply | reste], [b, a | pile]) do nil end def parcourir([:plus | _reste], _pile) do {:error, :operandes_manquants} end def parcourir([:minus | _reste], _pile) do {:error, :operandes_manquants} end def parcourir([:multiply | _reste], _pile) do {:error, :operandes_manquants} end # Les clauses de l'extension division pourront être ajoutées ici. def parcourir([_symbole | _reste], _pile) do {:error, :symbole_inconnu} end end ``` Vérifications fournies : ```elixir for {tokens, attendu} <- [ {[{:int, 3}, {:int, 4}, :plus, {:int, 2}, :multiply], {:ok, 14}}, {[{:int, 8}, {:int, 3}, :minus], {:ok, 5}}, {[{:int, 3}, {:int, 8}, :minus], {:ok, -5}}, {[{:int, 10}, {:int, 3}, :minus, {:int, 2}, :minus], {:ok, 5}}, {[{:int, 10}, {:int, 3}, {:int, 2}, :minus, :minus], {:ok, 9}}, {[{:int, 0}], {:ok, 0}}, {[], {:error, :pile_finale_invalide}}, {[{:int, 1}, {:int, 2}], {:error, :pile_finale_invalide}}, {[:plus], {:error, :operandes_manquants}}, {[{:int, 1}, :minus], {:error, :operandes_manquants}}, {[{:int, 1}, :multiply], {:error, :operandes_manquants}}, {[{:int, 1}, {:int, 2}, :plus, :plus], {:error, :operandes_manquants}}, {[:lparen, {:int, 1}, :rparen], {:error, :symbole_inconnu}}, {[{:int, 1}, :mystere], {:error, :symbole_inconnu}} ] do if Pile.eval(tokens) != attendu do raise "Vérifiez la pile et l'ordre des arguments pour #{inspect(tokens)}." end end IO.puts("Pile : calculs et erreurs vérifiés") ``` Complétez cette cellule de texte : 1. Tracez les appels de `Pile.eval([{:int, 8}, {:int, 3}, :minus])` avec les deux arguments de `parcourir/2` à chaque étape. 2. Pourquoi les clauses qui reconnaissent `[b, a | pile]` doivent-elles précéder les clauses `:operandes_manquants` ? 3. Que reste-t-il dans la pile pour `[{:int, 1}, {:int, 2}]` ? Pourquoi n'est-ce pas simplement le résultat 2 ? 4. Ajoutez un programme valide et un programme invalide de votre choix, avec leurs résultats attendus et leur vérification. ## Raccorder votre lexer, si le socle est terminé Copiez votre module `Lexer` complété depuis le laboratoire facultatif `ap2-transformations.livemd` (sur les entiers) dans une nouvelle cellule de code. Vous pouvez alors essayer le raccord suivant, affiché comme du texte pour que l'atelier reste autonome tant que vous n'avez pas copié votre lexer : ```text {:ok, tokens} = Lexer.lex("3 4 + 2 *") Pile.eval(tokens) ``` Le résultat attendu est `{:ok, 14}`. Pourquoi le texte `"3 + 4"`, que le lexer accepte, provoquerait-il ici `:operandes_manquants` ? La notation infixe habituelle demande un parser : c'est le travail des carnets numérotés d'AP2. ## Extension facultative — Ajouter la division Si vous avez terminé, ajoutez le token `:divide`. Il doit calculer `a / b` en respectant le même ordre des arguments. En Elixir, `/` renvoie un flottant : `8 / 2` donne `4.0`. Pour une division par zéro, renvoyez `{:error, :division_par_zero}` ; si les arguments manquent, conservez `{:error, :operandes_manquants}`. Placez vos clauses avant le dernier cas `:symbole_inconnu`. Vous pouvez utiliser le test `b == 0`, qui reconnaît aussi `0.0`, pour traiter le zéro. Cette extension est facultative et peut être jointe au rendu de cycle pour un bonus. Cas à essayer dans une cellule de code après votre modification : ```text Pile.eval([{:int, 8}, {:int, 2}, :divide]) # {:ok, 4.0} Pile.eval([{:int, 1}, {:int, 0}, :divide]) # {:error, :division_par_zero} Pile.eval([{:int, 1}, :divide]) # {:error, :operandes_manquants} ``` Sauvegardez ce notebook dans `entrainement/`, puis revenez au bilan de votre séance. Il n'y a pas de rendu supplémentaire pour cet atelier. Si un bout de syntaxe Elixir vous manque, les [fiches de référence](https://ap-2026.noce.fr/reference/) se consultent au besoin. Pour toute question, vous pouvez me contacter par email : [aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).