L'arbre syntaxique abstrait : la représentation interne de FLIN

Entre votre code source et le programme en cours d'exécution vit un arbre. Chaque noeud est une décision. Chaque branche est une relation entre des parties de votre programme. L'arbre syntaxique abstrait -- AST -- est la représentation interne du compilateur de ce que vous avez écrit, dépouillé de tout le bruit syntaxique dont les humains ont besoin pour lire le code mais pas les machines.

Les parenthèses ont disparu. Les points-virgules ont disparu. Les espaces blancs ont disparu. Ce qui reste est de la structure pure : cette expression est une addition binaire de ces deux sous-expressions. Cette instruction déclare une variable avec ce nom et cette valeur initiale. Cet élément de vue a ces attributs et ces enfants. L'AST capture le sens du programme, pas sa mise en forme.

L'AST de FLIN a un défi inhabituel. La plupart des langages de programmation n'ont qu'un type de chose : du code. FLIN en a trois : du code impératif (variables, flux de contrôle, opérations), des données déclaratives (définitions d'entités avec des champs typés) et des vues réactives (templates de type HTML avec des expressions embarquées). L'AST doit représenter les trois de manière assez uniforme pour que le vérificateur de types et le générateur de code les traitent, tout en préservant assez de structure spécifique au domaine pour que chacun conserve sa sémantique.

Cet article examine comment nous avons conçu l'AST de FLIN, quels noeuds il contient et les compromis que nous avons faits en chemin.

Le niveau supérieur : programmes et instructions

Un programme FLIN est une séquence d'instructions. Il n'y a pas de fonction main, pas d'en-tête de module, pas de boilerplate. Vous ouvrez un fichier .flin, écrivez des instructions, et le compilateur les traite de haut en bas.

L'AST représente cela avec deux types :

rustpub struct Program {
    pub statements: Vec<Stmt>,
}

pub enum Stmt {
    VarDecl {
        name: String,
        type_annotation: Option<FlinType>,
        initializer: Expr,
        span: Span,
    },
    EntityDecl {
        name: String,
        fields: Vec<FieldDecl>,
        span: Span,
    },
    Save {
        expr: Expr,
        span: Span,
    },
    Delete {
        expr: Expr,
        where_clause: Option<Expr>,
        span: Span,
    },
    If {
        condition: Expr,
        then_body: Vec<Stmt>,
        else_body: Option<Vec<Stmt>>,
        span: Span,
    },
    For {
        variable: String,
        index: Option<String>,
        iterable: Expr,
        body: Vec<Stmt>,
        span: Span,
    },
    Route {
        method: HttpMethod,
        path: String,
        body: Vec<Stmt>,
        span: Span,
    },
    ExprStmt {
        expr: Expr,
        span: Span,
    },
    ViewElement(ViewNode),
}

Chaque variante d'instruction transporte un span -- l'emplacement source où elle a été parsée. Ce span se propage à travers tout le pipeline de compilation : si le vérificateur de types trouve une erreur dans une déclaration de variable, il rapporte le span de cette déclaration, pas un générique "quelque part dans le fichier". Si le générateur de code émet du bytecode pour une instruction save, il enregistre le span dans la table de numéros de ligne pour que les erreurs à l'exécution puissent pointer vers la source.

Déclarations de variables

L'instruction la plus simple est aussi la plus courante :

flincount = 0
name: text = "Juste"

Les deux produisent des noeuds Stmt::VarDecl. La première a type_annotation: None -- le type sera inféré par le vérificateur de types. La seconde a type_annotation: Some(FlinType::Text) -- le développeur a explicitement déclaré le type.

Cette annotation optionnelle est une décision de conception clé. La philosophie de FLIN est "des types que vous écrivez rarement, une sûreté que vous obtenez toujours". Le vérificateur de types inférera count comme int à partir du littéral 0. Mais quand l'inférence serait ambiguë (une liste vide, un nombre qui pourrait être int ou float), le développeur peut ajouter une annotation explicite. L'AST préserve les deux formes sans préférence, laissant le vérificateur de types décider comment gérer chaque cas.

Déclarations d'entités

Les entités sont le modèle de données de FLIN. Ce ne sont pas des classes, pas des structs, pas des tables -- ce sont les trois à la fois. Une déclaration d'entité définit un type de données persistant avec des champs typés, des valeurs par défaut optionnelles et un versionnage automatique.

flinentity Todo {
    title: text
    done: bool = false
    created: time = now
}

L'AST représente cela comme :

rustpub struct FieldDecl {
    pub name: String,
    pub field_type: FlinType,
    pub default: Option<Expr>,
    pub span: Span,
}

Chaque champ a une annotation de type obligatoire (contrairement aux variables, où l'annotation est optionnelle). Le default est une expression, pas une valeur -- now est un mot-clé qui s'évalue à l'horodatage courant au moment où l'entité est créée. L'AST le préserve comme un noeud Expr::Keyword(Keyword::Now), que le générateur de code émettra comme une instruction bytecode LoadNow.

Les déclarations d'entités sont de la pure donnée au niveau de l'AST. Elles ne génèrent ni flux de contrôle ni expressions. Le générateur de code les gère en enregistrant le schéma de l'entité dans une table de recherche, pour que les opérations save, delete et find suivantes connaissent la structure de l'entité.

Noeuds d'expression

Les expressions sont le coeur de tout langage de programmation, et l'enum d'expression de FLIN est le plus grand type de l'AST :

rustpub enum Expr {
    // Littéraux
    Literal(LiteralValue),
    Identifier(String),
    List(Vec<Expr>),
    Map(Vec<(Expr, Expr)>),

    // Opérations
    Binary { left: Box<Expr>, op: BinOp, right: Box<Expr> },
    Unary { op: UnaryOp, operand: Box<Expr> },
    Assign { target: Box<Expr>, value: Box<Expr> },

    // Accès
    Member { object: Box<Expr>, field: String },
    Index { object: Box<Expr>, index: Box<Expr> },
    Call { callee: Box<Expr>, args: Vec<Expr> },
    MethodCall { object: Box<Expr>, method: String, args: Vec<Expr> },

    // Spécifique à FLIN
    EntityConstruct { name: String, fields: Vec<(String, Expr)> },
    Ask { query: Box<Expr> },
    Search { query: Box<Expr>, entity: String, field: String, limit: Option<Box<Expr>> },
    Temporal { expr: Box<Expr>, time: Box<Expr> },
    Match { subject: Box<Expr>, arms: Vec<MatchArm> },

    // Vue (embarqué dans les expressions quand utilisé à l'intérieur des vues)
    ViewInterpolation(Box<Expr>),
}

Plusieurs aspects de cette conception méritent un examen.

Box partout. Les types récursifs en Rust nécessitent une allocation sur le tas via Box, parce que le compilateur a besoin de connaître la taille de chaque type au moment de la compilation. Une expression Binary contient deux sous-expressions, dont chacune pourrait elle-même être Binary. Sans Box, le type aurait une taille infinie. Ce n'est pas une préoccupation de performance -- le coût d'allocation de boxer quelques centaines de noeuds d'expression est négligeable comparé au travail que le vérificateur de types et le générateur de code feront avec eux.

Variantes spécifiques à FLIN. EntityConstruct, Ask, Search et Temporal ne se trouvent pas dans les AST de langages généralistes. Ils encodent la sémantique spécifique au domaine de FLIN directement dans la structure de l'arbre. Un noeud Ask ne se désucre pas en un appel de fonction -- c'est un concept de première classe que le vérificateur de types valide (la requête doit être une expression texte) et que le générateur de code émet comme une instruction bytecode Ask dédiée.

Pas de parenthèses, pas de précédence. La structure de l'arbre encode la précédence implicitement. L'expression 2 + 3 * 4 est représentée comme Binary(Literal(2), Add, Binary(Literal(3), Mul, Literal(4))) -- la multiplication est un enfant de l'addition, donc elle s'évalue en premier. Le parser a fait le travail d'encoder la précédence dans la structure de l'arbre ; l'AST n'a pas besoin de l'enregistrer séparément.

Noeuds de vue

La couche de vue de FLIN est là où l'AST s'écarte le plus dramatiquement des AST de langages traditionnels. Un noeud de vue représente un élément de type HTML avec des attributs, des gestionnaires d'événements et des enfants :

rustpub struct ViewNode {
    pub tag: String,
    pub attributes: Vec<ViewAttribute>,
    pub children: Vec<ViewChild>,
    pub span: Span,
}

pub enum ViewAttribute {
    Static { name: String, value: String },
    Dynamic { name: String, expr: Expr },
    EventHandler { event: String, handler: Expr },
}

pub enum ViewChild {
    Element(ViewNode),
    Text(String),
    Expression(Expr),
    If { condition: Expr, then_children: Vec<ViewChild>, else_children: Option<Vec<ViewChild>> },
    For { variable: String, index: Option<String>, iterable: Expr, children: Vec<ViewChild> },
}

Considérez ce code FLIN :

flin<button class="primary" click={count++}>
    {count}
</button>

La représentation AST :

• ViewNode avec tag "button"
• - ViewAttribute::Static { name: "class", value: "primary" }
• - ViewAttribute::EventHandler { event: "click", handler: Expr::Unary(PostIncrement, Identifier("count")) }
• - ViewChild::Expression(Expr::Identifier("count"))

La structure du noeud de vue reflète la structure HTML, mais avec des expressions FLIN embarquées à chaque point où un comportement dynamique se produit. Les attributs statiques sont des chaînes. Les attributs dynamiques contiennent des expressions. Les gestionnaires d'événements contiennent des expressions. Le contenu enfant peut être du texte statique, des éléments imbriqués, des expressions interpolées ou des constructions conditionnelles/de boucle.

Cette conception signifie que le vérificateur de types peut valider les expressions de vue de la même façon qu'il valide les expressions de code : count++ dans un gestionnaire d'événement est vérifié exactement comme count++ dans un bloc de code. Le générateur de code gère les aspects spécifiques à la vue (création d'éléments DOM, liaison de gestionnaires, mise en place de la réactivité) tout en déléguant l'émission d'expression aux mêmes méthodes qu'il utilise pour le code.

La représentation des types

Chaque expression dans l'AST aura éventuellement un type, déterminé par le vérificateur de types. Mais l'AST lui-même ne transporte pas d'information de type -- il représente le programme tel que le développeur l'a écrit, avant toute analyse. Les types apparaissent dans l'AST uniquement quand le développeur les a explicitement écrits :

rustpub enum FlinType {
    Text,
    Int,
    Float,
    Bool,
    Time,
    File,
    Money,
    Semantic(Box<FlinType>),  // semantic text
    List(Box<FlinType>),       // [text]
    Optional(Box<FlinType>),   // text?
    Entity(String),            // User, Todo
    Any,                       // Utilisé en interne
    TypeVar(u32),              // Utilisé par l'inférence de types
}

Les variantes Semantic, List et Optional sont des constructeurs de types -- ils prennent un type interne et produisent un nouveau type. semantic text est un Semantic(Box(Text)). [int] est un List(Box(Int)). text? est un Optional(Box(Text)).

La variante TypeVar(u32) n'apparaît pas dans l'AST parsé. Elle est créée par l'algorithme d'inférence de types (Hindley-Milner, couvert dans le prochain article) pour représenter des types inconnus qui seront résolus par unification. Le fait qu'elle vive dans le même enum que les types concrets signifie que le vérificateur de types peut mélanger librement types connus et inconnus, sans types enveloppants ni cas spéciaux.

Décisions de conception et compromis

AST non typé vs AST typé. Certains compilateurs utilisent un seul type d'AST qui accumule l'information de type au fur et à mesure de l'analyse. D'autres utilisent deux types séparés : un AST non typé produit par le parser et un AST typé produit par le vérificateur de types. Nous avons choisi l'approche de l'AST unique, où le vérificateur de types annote l'AST existant plutôt que d'en produire un nouveau. Cela réduit la duplication de code (pas de hiérarchies de types parallèles) au coût de la sûreté de types (le vérificateur de types doit faire confiance au fait que les types sont peuplés avant que le générateur de code ne les lise). Pour une équipe de deux personnes, moins de code gagne.

Des spans sur chaque noeud. Transporter un Span sur chaque noeud d'instruction et d'expression coûte 16 octets par noeud (deux valeurs Position de 12 octets chacune, moins le padding). Pour un programme FLIN typique avec quelques centaines de noeuds AST, c'est quelques kilo-octets -- complètement négligeable. Le bénéfice est que chaque erreur de compilateur, chaque erreur de type, chaque avertissement de génération de code peut pointer vers l'emplacement source exact. Nous n'avons jamais eu à déboguer un problème "d'où vient cette erreur ?".

Enfants plats vs imbrication récursive. Les enfants de vue sont stockés comme Vec<ViewChild> plutôt que comme un arbre récursif. Cela signifie qu'un <div> avec trois enfants est une liste plate, pas un arbre binaire imbriqué. La représentation plate est plus facile à itérer dans le générateur de code et produit un bytecode plus propre. Elle correspond aussi à la façon dont les développeurs HTML pensent à leur balisage : un parent avec une liste d'enfants, pas une liste chaînée.

Pas de désucrage. Certains compilateurs désucrent la syntaxe complexe en formes plus simples au niveau de l'AST -- par exemple, transformer une boucle for en une boucle while avec un itérateur. FLIN ne désucre pas. Chaque forme syntaxique a sa propre variante AST et son propre chemin de génération de code. Cela rend le compilateur plus verbeux mais aussi plus prévisible : le bytecode généré pour une boucle for ressemble à une boucle for, pas à une boucle while qui itère par hasard.

Parcourir l'arbre

Le vérificateur de types et le générateur de code ont tous deux besoin de parcourir l'AST. Plutôt que d'implémenter le pattern visiteur (qui est idiomatique en Java mais maladroit en Rust), nous utilisons de simples expressions match :

rustfn emit_stmt(&mut self, stmt: &Stmt) -> Result<(), CodeGenError> {
    match stmt {
        Stmt::VarDecl { name, initializer, .. } => {
            self.emit_expr(initializer)?;
            self.define_variable(name);
            Ok(())
        }
        Stmt::EntityDecl { name, fields, .. } => {
            self.register_entity(name, fields);
            Ok(())
        }
        Stmt::If { condition, then_body, else_body, .. } => {
            self.emit_if(condition, then_body, else_body.as_deref())
        }
        Stmt::For { variable, index, iterable, body, .. } => {
            self.emit_for(variable, index.as_deref(), iterable, body)
        }
        Stmt::Save { expr, .. } => {
            self.emit_expr(expr)?;
            self.emit_opcode(OpCode::Save);
            Ok(())
        }
        // ... autres variantes
    }
}

Le match exhaustif de Rust est l'avantage clé ici. Si nous ajoutons une nouvelle variante d'instruction à l'enum Stmt, le compilateur nous force à la gérer dans chaque expression match qui opère sur les instructions. Nous ne pouvons pas oublier de gérer un nouveau type de noeud -- le code ne compilera pas tant que nous ne le faisons pas. C'est le même principe qui rend le type Result de Rust plus sûr que les exceptions : le compilateur suit ce que vous avez géré et ce que vous n'avez pas géré.

De l'AST au bytecode : un exemple complet

Pour rendre l'AST concret, traçons l'exemple du compteur à travers l'arbre :

flincount = 0
<button click={count++}>{count}</button>

Le parser produit cet AST :

Program
  Stmt::VarDecl
    name: "count"
    type_annotation: None
    initializer: Expr::Literal(Integer(0))
  Stmt::ViewElement
    ViewNode
      tag: "button"
      attributes:
        EventHandler
          event: "click"
          handler: Expr::Unary(PostIncrement, Identifier("count"))
      children:
        ViewChild::Expression(Expr::Identifier("count"))

Le vérificateur de types parcourt cet arbre et détermine : - count a le type Int (inféré du littéral 0) - L'expression du gestionnaire d'événement count++ opère sur un Int, produisant un Int -- valide - L'interpolation de vue {count} référence un Int, qui sera converti en Text pour l'affichage -- valide

Le générateur de code parcourt l'arbre typé et émet du bytecode : - LoadInt0 + StoreGlobal "count" pour la déclaration de variable - CreateElement "button" pour l'élément de vue - CreateHandler "click" + LoadGlobal "count" + Dup + Incr + StoreGlobal "count" + TriggerUpdate + EndHandler + BindHandler pour le gestionnaire d'événement - LoadGlobal "count" + BindText pour l'interpolation de texte - CloseElement pour finir le bouton - Halt pour terminer le programme

Chaque phase lit l'AST, fait son travail et passe le résultat à la phase suivante. L'AST est la lingua franca du compilateur -- le langage commun que toutes les phases comprennent.

L'AST en chiffres

250 lignes de définitions de types. C'est toute la représentation interne d'un langage de programmation avec du code impératif, des données déclaratives, des vues réactives, des requêtes temporelles et des expressions d'intention IA. Les types enum de Rust font le gros du travail : chaque variante est sa propre "classe" en termes orientés objet, mais avec du matching exhaustif et zéro surcharge à l'exécution.

Ce qui a suivi

L'AST est un arbre de noeuds non typés. Il connaît la structure du programme mais pas si cette structure a du sens. Peut-on additionner un entier et une chaîne ? Peut-on appeler une méthode sur un booléen ? Peut-on sauvegarder une entité qui n'a pas été définie ? L'AST ne le sait pas. Le vérificateur de types, si.

Le prochain article couvre le système d'inférence de types de FLIN, construit sur l'algorithme Hindley-Milner -- le même algorithme utilisé par Haskell et ML. Il détermine le type de chaque expression dans l'AST sans nécessiter que le développeur écrive des annotations de type, détecte les erreurs au moment de la compilation plutôt qu'à l'exécution, et supporte le polymorphisme let pour que les structures de données génériques fonctionnent correctement.

Ceci est la partie 14 de la série "Comment nous avons construit FLIN", qui documente comment un CEO à Abidjan et une IA CTO ont construit un langage de programmation en partant de zéro.

Navigation de la série : - [11] Session 1 : mise en place du projet et 42 mots-clés - [12] Construire un lexer en partant de zéro en Rust - [13] Pratt Parsing : comment FLIN lit votre code - [14] L'arbre syntaxique abstrait : la représentation interne de FLIN (vous êtes ici) - [15] L'inférence de types Hindley-Milner dans un langage personnalisé