Nouvel arc. Après la cryptographie, on s’attaque à quelque chose de plus vertigineux : un compilateur verbose, écrit en verbose. Le langage qui commence à se décrire lui-même.

Soyons honnêtes d’entrée — et c’est important. Il ne s’agit pas (pas encore) de verbosec compilant la totalité de son propre code. Ce qui existe aujourd’hui, c’est un front end complet — tokenizer, parser, analyses, interpréteur, vérificateur de types — écrit en verbose, pour un sous-ensemble jouet du langage. Le tout compilé par verbosec en code machine natif. Pas une démo interprétée : un binaire ELF de ~60 Ko qui lit votre programme et vous dit ce qui ne va pas. C’est examples/vexprparse.verbose : 102 concepts, 219 règles.

On va le parcourir brique par brique. Ce chapitre pose la fondation sans laquelle rien d’autre n’existe : comment représenter un programme.

Pourquoi écrire le compilateur en verbose ?

La question mérite une réponse, parce qu’elle n’est pas qu’un exercice — elle touche à la thèse même de verbose.

Aujourd’hui, le compilateur (verbosec) est écrit en Rust. Et une partie de la logique — certaines primitives — est du Rust qui émet directement du x86-64, sans source verbose. Conséquence concrète : pour auditer un binaire verbose, pour comprendre vraiment ce qu’il fait, il faut à un moment lire du Rust. Et faire confiance à ce Rust — et à celui, ou ce qui, l’a écrit.

Or c’est précisément ce que verbose refuse. Toute la série tient sur quatre mots : on ne fait pas confiance, on vérifie. On lit la source, déclarée et prouvée. Si le chemin de la source au binaire passe par du Rust non vérifiable, la confiance fuit par là.

Écrire le front end en verbose déplace cette logique dans le langage lui-même : le tokenizer, le parser, les analyses deviennent un fichier .verbose, vérifié sous le régime de preuves de verbose, puis compilé en natif. L’auditeur lit du verbose, pas du Rust. Le Rust restant se réduit à une base petite, stable, vérifiée une fois (le vérificateur). La confiance, binaire par binaire, se déplace du Rust vers la source prouvée.

Et c’est le dogfooding ultime : un compilateur est la chose la plus difficile à exprimer. Si verbose peut décrire son propre front end, sous son propre régime de preuves, alors le langage n’est pas un jouet — il tient sur la tâche la plus exigeante qui soit.

Du texte vers un arbre

Un compilateur ne peut rien faire avec du texte plat. x + y * 2, pour un humain, est une suite de caractères ; pour un compilateur, c’est une structure — un arbre, où la multiplication se niche sous l’addition (priorité des opérateurs) :

  Le texte  "x + y * 2"  est en réalité un arbre :

            ( + )
           /     \
         x      ( * )
               /     \
             y         2

Tout commence là. Avant d’évaluer, de vérifier les types, de détecter une variable inconnue — il faut d’abord transformer le texte en cet arbre. C’est l’AST (Abstract Syntax Tree). Et pour le construire, il faut un moyen de représenter un arbre en tant que donnée.

Un arbre, c’est un type somme récursif

C’est ici que le travail des chapitres précédents paie. Un arbre se déclare en verbose comme un type somme — un type qui peut prendre plusieurs formes — dont certaines formes se référencent elles-mêmes :

concept Ast
  variants:
    AstNum  of (value : number)
    AstVar  of (start : number, len : number)
    AstBin  of (op : number, lhs : Ast, rhs : Ast)
    AstNeg  of (inner : Ast)
    AstIf   of (cond : Ast, thn : Ast, els : Ast)
    AstCall of (callee_start : number, callee_len : number, args : ArgList)
    ...

Lisez AstBin : une opération binaire contient un opérateur, un sous-arbre gauche Ast, et un sous-arbre droit Ast. Le type se contient lui-même. C’est ça, la récursivité d’un arbre : une addition dont les deux côtés sont, eux aussi, des expressions. AstIf en contient trois (condition, branche then, branche else). AstNum et AstVar, eux, sont des feuilles — ils ne contiennent pas d’autre Ast.

Notre exemple devient alors, exactement :

  AstBin( + ,
          AstVar(x),
          AstBin( * , AstVar(y), AstNum(2)) )

L’arbre dessiné plus haut, écrit comme une valeur. Et a.b.c ? AstField(AstField(AstVar(a), b), c) — l’imbrication suit la structure.

Pas de pointeurs : une arène d’index

Reste un problème. Verbose n’a ni tas (heap) ni pointeurs — c’est une des raisons pour lesquelles ses binaires sont si petits et si vérifiables. Comment, alors, construire un arbre de taille arbitraire ?

La réponse : une arène. Tous les nœuds vivent dans un seul espace borné, et un nœud désigne ses enfants par leur index, pas par un pointeur.

  concept_group VExpr [max_depth: 4096, max_nodes: 65535]

  arène :  [0]  AstVar(x)
           [1]  AstVar(y)
           [2]  AstNum(2)
           [3]  AstBin( * , lhs=1, rhs=2)    ← référence les index 1 et 2
           [4]  AstBin( + , lhs=0, rhs=3)    ← la racine

L’arbre se construit de bas en haut : d’abord les feuilles, puis les nœuds qui les relient. max_depth: 4096, max_nodes: 65535 ne sont pas décoratifs — ce sont les bornes statiques dont le vérificateur a besoin pour prouver que tout reste fini. Pas d’allocation dynamique, pas de débordement possible, et pourtant un arbre de structure quelconque.

Dans le même groupe vivent les tokens, les environnements et les diagnostics — tous variants de VExpr, tous reliés par index. Une seule arène pour tout le front end.

Pourquoi cette brique d’abord

Parce que tout le reste s’y branche. Le tokenizer produira des Token dans cette arène. Le parser les consommera pour bâtir des Ast. Les analyses parcourront l’arbre pour trouver vos erreurs. L’interpréteur le descendra pour calculer un résultat. Sans une façon de représenter l’arbre — récursive, bornée, vérifiable — il n’y a pas de compilateur du tout.

Et c’est l’aboutissement direct de ce qu’on a construit avant : la récursion de l’article #1, les preuves de terminaison de l’article #3. Un AST, c’est la structure récursive par excellence — et verbose la représente sous les mêmes garanties que tout le reste : bornée, sans pointeur, prouvée finie.

Le programme est devenu une donnée. Le prochain chapitre le fabriquera à partir du texte brut : le tokenizer.