# AP2 · 2 — Garder le calcul dans un arbre

## Notre question

Avec la règle de l'étape 1, `1.0 + 2.0 * 3.0` donne `9.0`. Nous voulons
maintenant qu'il donne `7.0`, tandis que `(1.0 + 2.0) * 3.0` donne `9.0` : la
multiplication est prioritaire, et les parenthèses imposent un groupement.
Nous voulons aussi garder le programme sous une forme que plusieurs outils
pourront parcourir : l'évaluer aujourd'hui, le compiler en AP3, le typer en
projet.

```text
1.0 + 2.0 * 3.0
(1.0 + 2.0) * 3.0
8.0 - 3.0 - 2.0
```

Cette forme est un *arbre de syntaxe abstraite*, ou AST : chaque opération
est un *nœud* dont les deux enfants sont ses opérandes, et chaque nombre est
une *feuille*. Dessinez les trois arbres avant de commencer. Où se trouve
l'opération exécutée en dernier ? C'est la *racine* de l'arbre. En Elixir,
un nombre devient `{:number, valeur}` et une opération devient
`{:binary, opérateur, gauche, droite}` : un tuple dont le premier élément dit
la catégorie du nœud, et dont les enfants sont eux-mêmes des tuples. Les
parenthèses orientent la construction, mais n'ont pas besoin de devenir un
nœud dans l'AST.

> **Repères.** [Slides 14 à 26](https://ap-2026.noce.fr/slides/AP2.html#14) : arbre, parcours postordre, grammaire, descente récursive, priorités choisies par chaque langage, le programme comme donnée. Elixir : tuples imbriqués, `case`, une clause par nœud, valeur par défaut `\\`, expliqués au point d'emploi. Poly, chap. 2 « Le pattern matching », chap. 4 « Fonctions, clauses, récursion » et chap. 5, § 5.2 à 5.5, de « Un arbre pour garder le calcul » à « De la grammaire à l'arbre ».

> 💡 Point de départ conseillé : écrivez et testez cette étape en séance.
> Je préciserai en cours les notebooks à travailler et ceux à rendre.
> **Sauvegardez-le dès maintenant sous `AP2/ap2-02-arbres.livemd`.**

## Reprendre vos briques

Depuis `ap2-01-calcul-direct.livemd`, copiez vos modules `DecimalLiteral`,
`ArithmeticInput` et `ArithmeticOps` dans les deux cellules indiquées. Ne copiez
pas `DirectCalculator` : nous allons changer de représentation. Chaque notebook
a sa propre session ; il faut réévaluer ces copies ici.

```elixir
# Copiez ici vos modules DecimalLiteral et ArithmeticInput.
```

```elixir
# Copiez ici votre module ArithmeticOps.
```

Les vérifications de ce notebook utilisent `assert`, fourni par Elixir via
ExUnit : une condition fausse arrête la cellule et affiche la valeur obtenue
à côté de celle attendue. Évaluez la cellule d'import une fois, puis
réévaluez votre code avant ses tests après chaque modification.

```elixir
import ExUnit.Assertions
```

Cette vérification confirme que votre lexer recopié reconnaît bien les parenthèses :

```elixir
assert ArithmeticInput.lex("(2.0 + 3.0)") ==
  {:ok, [:lparen, {:number, 2.0}, :plus, {:number, 3.0}, :rparen]}
```

## Parcourir l'arbre pour calculer

Pour obtenir la valeur d'une addition, il faut d'abord celles de ses deux
enfants : les valeurs remontent des feuilles vers la racine. Ce parcours, où
chaque nœud est traité après ses enfants, s'appelle le *postordre*. Pour
`1.0 + 2.0 * 3.0`, la feuille gauche donne `1.0`, le sous-arbre droit donne
`6.0`, puis la racine donne `7.0`.

Écrivez `Interpreter.eval/2`. Son second argument sera notre environnement à
l'étape suivante ; pour l'instant, passez-le simplement aux appels récursifs
sans le lire. Le cas du nombre est fourni. Pour une opération, calculez les
deux sous-arbres, puis appelez `ArithmeticOps.apply/3` ; propagez les erreurs
sans les transformer en valeurs. Le nœud de négation est `{:neg, arbre}` ;
`ArithmeticOps.negate/1` traite sa valeur.

> 💡 La ligne `def eval(tree, env \\ [])`, sans corps, déclare une valeur par
> défaut : `eval(arbre)` équivaut à `eval(arbre, [])`. Elixir exige cette
> en-tête à part dès qu'une fonction à plusieurs clauses possède un défaut. Le
> `_env` des clauses suivantes nomme un argument que l'on ne lit pas encore.
>
> `with` accepte plusieurs étapes, séparées par des virgules ; la suite n'est
> exécutée que si chacune correspond à son motif. Par ex.,
> `with {:ok, tokens} <- lex(source), {:ok, value} <- calculate(tokens) do …`
> s'arrête à la première erreur et la rend telle quelle.

Commencez par les arbres dessinés ci-dessus, écrits à la main : vous pouvez
donc vérifier l'évaluation avant de construire le parser. Gardez un arbre de
soustraction parmi vos tests. Pourquoi `8.0 + 3.0` ne révélerait-il pas une
inversion des deux enfants, alors que `8.0 - 3.0` la montre immédiatement ?

```elixir
defmodule Interpreter do
  def eval(tree, env \\ [])
  def eval({:number, value}, _env), do: {:ok, value}
  def eval(_tree, _env), do: {:error, :not_implemented}
  # Ajoutez les cas des opérations et de la négation avant la dernière clause.
end
```

Prédisez la valeur de cet arbre, puis ajoutez un `assert` pour votre arbre de soustraction :

```elixir
assert Interpreter.eval({:binary, :multiply,
  {:binary, :plus, {:number, 1.0}, {:number, 2.0}}, {:number, 3.0}}) == {:ok, 9.0}
```

## Lire un morceau et rendre le reste

Le *parser* est la brique qui construit l'arbre à partir des tokens. Nous
écrivons une *descente récursive* : une fonction de lecture par règle de la
*grammaire*, chacune appelant les lecteurs des règles qu'elle contient. Voici
la grammaire de cette étape, dans la notation du poly : `:=` se lit « est
formé de », `|` sépare des alternatives, et `( … )*` signifie « répété zéro
fois ou davantage ». Cette étoile n'est pas la multiplication de notre langage.

```text
expression := sum
sum        := product (("+" | "-") product)*
product    := unary (("*" | "/") unary)*
unary      := "-" unary | primary
primary    := number | "(" expression ")"
```

La priorité est inscrite dans la profondeur : une somme est faite de
produits, et non l'inverse, donc `2.0 * 3.0` est lu en entier par le lecteur
des produits avant que la somme ne reprenne la main. C'est ainsi que la
multiplication finit sous l'addition dans l'arbre.

Le contrat d'un lecteur est `{:ok, arbre, reste}` ou `{:error, raison}` : la
lecture s'arrête au premier token qui n'en fait plus partie, par ex. `:rparen`,
et rend ce reste à son appelant, qui sait quoi en faire. C'est exactement ce
que faisait `Integer.parse/1` avec le reste d'une chaîne en AP1.
`ArithmeticParser.read/1` est le lecteur d'une expression complète ;
`parse/1`, fourni ci-dessous, exige au contraire une entrée entièrement
consommée. Voici le contrat de `read/1` sur un exemple, au format `iex>` ; la
parenthèse reste à traiter :

```text
iex> ArithmeticParser.read([{:number, 4.0}, :rparen])
{:ok, {:number, 4.0}, [:rparen]}
```

Concevez les fonctions de lecture, une par règle. Commencez par les nombres
et `+`, ajoutez `*` avec sa priorité, puis les parenthèses. Le moins unaire
vient en dernier si vous manquez de temps. La lecture des nombres fournit un
exemple de la forme : `primary([{:number, n} | rest])` doit rendre
`{:ok, {:number, n}, rest}`. C'est à vous d'écrire les autres fonctions et
leurs cas d'arrêt. Le point d'arrêt sera précisé en cours : un lecteur de
nombres et d'une opération suffit pour expliquer le reste transmis ; les
priorités et les parenthèses peuvent se poursuivre ensuite. Les tests
ci-dessous décrivent la version complète.

> 💡 `case résultat do … end` choisit la première branche dont le motif
> correspond, comme les clauses d'une fonction d'AP1 ; la branche
> `error -> error` attrape tout le reste. Dans `parse/1`, les trois branches
> distinguent une lecture complète, des tokens en trop et une erreur.
>
> Si vous factorisez vos lecteurs (somme et produit ont la même forme),
> `&product/1` désigne la fonction `product` à un argument sans l'appeler, et
> une fonction reçue dans un paramètre `reader` s'appelle `reader.(tokens)`,
> avec un point. Vous pouvez aussi garder des fonctions séparées, plus
> longues mais tout aussi correctes.

```elixir
defmodule ArithmeticParser do
  def parse(tokens) do
    case read(tokens) do
      {:ok, tree, []} -> {:ok, tree}
      {:ok, _tree, rest} -> {:error, {:unexpected_tokens, rest}}
      error -> error
    end
  end
  def read(_tokens), do: {:error, :not_implemented}
  # Écrivez vos lecteurs et leurs fonctions auxiliaires ici.
end
```

Avant d'évaluer, dites quel lecteur s'arrête devant le `:rparen` du deuxième
test, et pourquoi les cinq entrées du `for` doivent échouer dans `parse/1`
alors que certaines ont un début lisible.

```elixir
{:ok, tokens} = ArithmeticInput.lex("1.0 + 2.0 * 3.0")
assert ArithmeticParser.parse(tokens) == {:ok,
  {:binary, :plus, {:number, 1.0},
    {:binary, :multiply, {:number, 2.0}, {:number, 3.0}}}}
assert ArithmeticParser.read([{:number, 4.0}, :rparen, :plus, {:number, 2.0}]) ==
  {:ok, {:number, 4.0}, [:rparen, :plus, {:number, 2.0}]}
for source <- ["", "(1.0", "1.0)", "1.0 2.0", "1.0 +"] do
  {:ok, tokens} = ArithmeticInput.lex(source)
  assert {:error, _} = ArithmeticParser.parse(tokens)
end
```

## Relier le texte au calcul

Cette vérification utilise les deux briques : lancez-la lorsque votre parser
traite les opérations demandées. Si celui-ci est encore partiel, continuez à
tester l'évaluateur avec vos arbres manuels ; il servira directement à l'étape 3.

> 💡 Dans `for {source, expected} <- liste do … end`, le motif `{source, expected}`
> défait chaque couple de la liste, exactement comme un `=` le ferait : le
> texte et sa valeur attendue reçoivent chacun un nom.

```elixir
for {source, expected} <- [
  {"1.0 + 2.0 * 3.0", 7.0}, {"(1.0 + 2.0) * 3.0", 9.0},
  {"8.0 - 3.0 - 2.0", 3.0}, {"8.0 / 2.0 / 2.0", 2.0}
] do
  {:ok, tokens} = ArithmeticInput.lex(source)
  {:ok, tree} = ArithmeticParser.parse(tokens)
  assert Interpreter.eval(tree) == {:ok, expected}
end
```

### Si vous bloquez

Premier indice : `expression` demande d'abord un `product`. Deuxième indice :
quand `+` suit, l'arbre déjà lu devient le fils gauche du nouvel arbre. Continuez
avec ce nouvel arbre ; cette accumulation explique l'association à gauche de `-`.
Troisième indice : après `(`, réutilisez `read/1`, puis exigez et consommez `)` ;
s'il manque, c'est une erreur à nommer.

### Pour aller plus loin

Ajoutez le moins unaire et testez `-2.0 * --3.0`. Écrivez un autre parcours de
l'arbre, par ex. compter les opérations ou réafficher l'expression complètement
parenthésée. Vous n'avez pas à modifier le parser pour ajouter ce parcours :
c'est tout l'intérêt d'avoir gardé le calcul comme une donnée.

## Avant de reprendre les slides

Montrez le sous-arbre qui impose la priorité de `*`, puis celui qui impose
l'association à gauche de `8.0 - 3.0 - 2.0`. Expliquez pourquoi `read/1` doit rendre
un reste alors que `parse/1` le refuse. Ajoutez un cas qui aurait piégé votre
première version et décrivez la correction. Retenez enfin que nous avons
séparé trois briques, lexer, parser et évaluateur, et que l'arbre est la
donnée qu'elles se passent : le compilateur d'AP3 le lira tel quel.

Écrivez vos réponses dans une cellule Markdown de ce notebook, avec votre
contre-exemple et ce qu'il vous a appris. Sauvegardez ce notebook dans `AP2/`.
Pour le rendu unique du cycle AP1–AP3, je préciserai en cours les étapes
à terminer et le résultat minimum attendu. Les numéros indiquent l'ordre
de progression, pas une liste de devoirs. Les prolongements non demandés
restent facultatifs et peuvent apporter un bonus.
L'échéance commune est le 6 décembre 2026 à 23 h 59 (Paris) ; il n'y a pas
de devoir intermédiaire. AP3 s'ouvrira par un quiz de dix minutes sur
cette séance : relisez le chapitre 5 du poly, « Construire un langage ».

Si un bout de syntaxe Elixir vous manque en route, les chapitres 1 à 4 du
[poly](https://ap-2026.noce.fr/poly/poly-elixir.pdf) se consultent au besoin ; ils ne sont pas un prérequis de cette
étape.

Pour toute question, vous pouvez me contacter par email :
[aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).