Rustre

Rustre est un compilateur Lustre écrit en Rust. Le but de ce projet est de fournir un compilateur plus agréable à utiliser que le compilateur officiel (meilleurs messages d'erreur, meilleure documentation, interface en ligne de commande plus intuitive), mais aussi d'explorer de nouvelles idées pour le design de compilateurs, s'inspirant notamment des travaux de Rust Analyzer et de rustc.

Éventuellement, nous aimerions aussi fournir un framework pour manipuler du code source Lustre, permettant de développer des outils en plus du compilateur (formattage de code par exemple).

Enfin, nous pensons que Lustre a du potentiel en tant que langage embarqué, c'est à dire qu'un interpréteur pourrait être intégré à un logiciel pour pouvoir lui développer des plugins en Lustre. Or, l'interpréteur officiel étant developpé en OCaml, il est beaucoup plus compliqué à intégrer à un programme que le serait une bibliothèque Rust ou C compilée en langage machine.

Architecture des modules

Diagramme des modules prévisionnel

Ce diagramme n'inclut que les principaux modules.

Légende:

⬭ Modules internes (développés par nous)
□ Modules externes (dépendances sur des bibliothèques développées à part)

Responsabilité des modules

rustre-parser-tests-codegen: Génère des tests unitaires pour rustre-parser à partir des fichiers de tests du dépôt Lustre officiel
rustre-parser: Parseur et lexeur Lustre, production d'AST rowan
rustre-core: Salsa, type-checking, ...
rustre-cli: Point d'entrée de l'interface en ligne de commande

Dépendances externes (bibliothèques)

Les dépendances externes sont distribuées grâce au gestionnaire de paquets officiel du langage Rust, cargo, et hébergées sur https://crates.io. Nous conseillons le site non-officiel https://lib.rs comme front-end plus joli à crates.io. Les dépendances listées ci-dessus sont non-exhaustives; certaines n'ont pas d'intérêt à être détaillées et des dizaines/centaines d'autres sont transitives.

L'intérêt des principales bibliothèques est rapidement passé en revue dans le glossaire.

Architecture classique d'un compilateur

Avant de présenter l'architecture du compilateur Rustre, nous allons présenter l'architecture classique d'un compilateur, afin d'en exposer les limites et expliquer pourquoi nous avons décidé de ne pas adopter cette approche.

Un compilateur est un programme qui prend du code source (lisible et rédigé par des humains) en entrée, et qui génère un fichier binaire (généralement exécutable). Dans le cas de Lustre, avec les outils officiels, on peut :

générer l'extended code d'un programme (inlining de tous les nœuds pour n'en avoir plus qu'un seul)
générer du code C équivalent à un programme
générer un binaire équivalent à un programme
générer un automate équivalent à un programme
simuler un programme (sans compiler son code source)
faire du model-checking sur un programme

Ici, on va se concentrer sur le cas où on veut générer un binaire.

Passes et représentations intermédiaires

Un compilateur se divise en plusieurs « passes » (comprendre « étapes ») successives, ayant chacune un rôle précis dans la manipulation du code source. Chaque passe utilise ses propres structures de données pour se représenter le code source, appelées « représentations intermédiaires » (en réalité, plusieurs passes consécutives peuvent utiliser la même représentation intermédiaire).

Généralement, on distingue ces passes :

le lexeur, prend le code source sous forme de texte et produit une liste de tokens (~ mots) distints
le parseur, utilise la liste des tokens pour construire un arbre représentant de manière abstraite le programme
différentes passes de vérification (qui dépendent du langage et de ses règles), par exemple vérifier que les types sont cohérents
différentes passes d'optimisation
une passe finale qui génère du binaire

Lexeur

Le lexeur prend en entrée du code source et génère une liste de tokens, pré-découpant le code source pour faciliter son analyse. Cette étape élimine (généralement) des informations inutiles comme les espaces ou les commentaires.

On peut imaginer un lexeur Lustre qui prendrait ce code source :

const n = 4;

-- Multiplexeur à deux entrées
function multiplex (a, b, s : bool) returns (f : bool)
let
    f = (a and s) or (b and not s);
tel;

Et qui renvoie cette liste de tokens :

#![allow(unused)]
fn main() {
Const, Ident("n"), Egal, Int(4), PointVirgule,
Function, Ident("multiplex"), ParenGauche,
Ident("a"), Virgule, …
}

Parseur

Le parseur construit une représentation intermédiaire qu'on appelle AST (Abstract Syntax Tree). C'est une représentation du code source sous forme d'arbre.

Un parseur Lustre pourrait produire l'arbre suivant pour le code source précédent.

#![allow(unused)]
fn main() {
FichierLustre {
    declarations: [
        Constante { nom: "n", valeur: Entier(4) },
        Fonction {
            nom: "multiplex",
            entrees: [
                ("a", Bool),
                ("b", Bool),
                ("c", Bool),
            ],
            sorties: [
                ("f", Bool),
            ],
            equations: [
                "f", Or(
                    And(Var("a"), Var("s")),
                    And(Var("b"), Not(Var("s"))),
                ),
            ],
        },
    ],
}
}

Passes suivantes

Les passes suivantes vont vérifier certaines propriétés sur l'AST, le transformer et l'enrichir de nouvelles informations (ce qui demandera d'autres représentations intermédiaires, mais qui resteront généralement sous forme d'arbres).

Ces passes sont dans un ordre bien défini, et vont « en avant » (on exécute la première passe, puis on passe son résultat à la seconde, et ainsi de suite).

Inconvénients de cette approche

On a peu de résilience face aux erreurs : concevoir un AST qui peut être partiellement valide n'est pas possible (ou du moins, demande un travail spécial). Une erreur dans une passe fait s'arrêter la compilation entièrement, même si une partie du programme est valide et aurait pu être analysée d'avantage.

On doit également multiplier les représentations intermédiaires. Par exemple si on veut ajouter le type de chaque variable et de chaque expression, on doit redéfinir entièrement chaque type de l'AST. Puis, si dans une passe suivante on veut ajouter un compteur du nombre d'utilisation de chaque variable/fonction/nœud (pour émettre un avertissement si certains sont définis sans jamais être utilisés), on doit à nouveau redéfinir l'AST avec ce nouveau champ dans chaque type.

Rajouter une passe peut être compliqué, surtout dans le cas où on développe des outils parallèles au compilateur (plugin d'IDE, linter).

Pour palier aux inconvénients de l'architecture traditionnelle des compilateurs, on propose une nouvelle architecture basée sur :

un lexeur assez classique
un arbre de syntaxe qui hiérarchise les tokens dans un arbre, mais sans construire un AST dans lequel les informations sont synthétisées
un AST fonctionnel qui exploite les tokens dans l'arbre de syntaxe pour mettre en évidence la structure de l'arbre et les propriétés de chaque nœud
un système de queries (« demandes » / « requêtes ») inter-dépendantes

Pour celà, on s'appuie sur des crates déjà existantes, qui sont respectivement :

S'appuyer sur ces bibliothèques nous permet de gagner du temps, et de profiter d'implémentations performantes et bien testées des algorithmes dont nous avons besoin.

Arbre de syntaxe

Les arbres de syntaxe que l'on construit sont des arbres d'arité arbitraire, où chaque nœud est étiqueté par un token.

Les tokens sont représentés par un type énuméré, sans données associée aux constructeurs. Mais en plus des tokens produits par le lexeur (identifiant, mot-clé, constante, etc.), cette énumération contient des variantes qui permettent de donner une sémantique à l'arbre (« déclaration de fonction » par exemple).

Prenons le code suivant :

function id (x : bool) returns (f : bool)
let
    f = x;
tel;

Le lexeur produit une liste de token qui ressemble à :

#![allow(unused)]
fn main() {
Function
Ident // « id »
LeftParen
Ident // « x »
Colon
Bool
RightParen
Returns
LeftParen
Ident // « f »
Colon
Bool
RightParen
Let
Ident // « f »
Equal
Ident // « x »
Semicolon
Tel
Semicolon
}

Le « parseur » (étape 2 dans la liste donnée plus haut), va alors hiérarchiser les tokens de cette manière :

#![allow(unused)]
fn main() {
FunctionDeclaration
  Function
  Ident // « id »
  Parameters
    LeftParen
    VariableDeclaration
      Ident // « x »
      Colon
      Bool
    RightParen
  Return
  Outputs
    LeftParen
    VariableDeclaration
      Ident // « f »
      Colon
      Bool
    RightParen
  Let
  FunctionBody
    Equation
      EquationLHS
        Ident // « f »
      Equal
      EquationRHS
        Ident // « x »
    Semicolon
  Tel
  Semicolon
}

Naviguer dans l'arbre de syntaxe

Pour parcourir cette arbre de syntaxe facilement, on met en place une API fonctionnelle.

Les différentes fonctions de parcours de l'arbre étant très répétitives, on génère ce code à l'aide d'ungrammar. Cette crate permet à partir d'un fichier décrivant une grammaire, de générer du code source Rust arbitraire au moment de la compilation.

Par exemple, cette règle ungrammar :

Root = IncludeStatement* PackageBody? PackageList?

Genère ce code (pas besoin de le lire en détail, faut juste voir qu'avec une petite ligne on peut générer beaucoup de code répétitif) :

#![allow(unused)]
fn main() {
// Root

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Root {
    pub(crate) syntax: SyntaxNode,
}

impl AstNode for Root {
    fn can_cast(kind: Token) -> bool {
        kind == Token::Root
    }

    fn cast(syntax: SyntaxNode) -> Option<Self> {
        if Self::can_cast(syntax.kind()) {
            Some(Self { syntax })
        } else {
            None
        }
    }

    fn syntax(&self) -> &SyntaxNode {
        &self.syntax
    }
    fn expect(syntax: SyntaxNode) -> Self {
        Self::cast(syntax).expect("Failed to cast to Root")
    }
}

impl Root {
    pub fn all_include_statement(&self) -> impl Iterator<Item = IncludeStatement> {
        self.syntax().children().filter_map(IncludeStatement::cast)
    }
    pub fn package_body(&self) -> Option<PackageBody> {
        self.syntax().children().find_map(PackageBody::cast)
    }
    pub fn package_list(&self) -> Option<PackageList> {
        self.syntax().children().find_map(PackageList::cast)
    }
}
}

Manipuler l'arbre : le système de queries

Le système de queries est ce qui va permettre d'implémenter les différentes passes du compilateur.

Une query peut être vue comme une fonction : elle prend des paramètres en entrée, et calcule un résultat de sortie. Cependant cette fonction doit être pure : si les entrées sont les mêmes, alors les sorties seront les mêmes. De cette manière, on peut mettre en cache le résultat des queries et éviter de refaire plusieurs fois le même calcul.

Une query va généralement dépendre du résultat d'autres queries, qu'elle peut demander à exécuter. Mais contrairement à un système de passes classique, c'est la query qui indique de quoi elle dépend, et pas le système qui lui passe le résultat des passes précédentes en entrée.

Le système fonctionne donc « à l'envers » : on lance la query « génère du binaire », qui va demander à exécuter les passes précendentes, en remontant jusqu'aux premières passes (« construit un arbre de syntaxe pour tel fichier »).

Pour certaines queries, il est intéressant d'écrire leur cache sur le disque en plus de la mémoire, pour pouvoir les réutiliser la prochaine fois que le compilateur est lancé.

Avantages de cette architecture

On peut reconstruire facilement une petite partie de l'arbre de syntaxe (utile si on veut développer un « language server » ou un plugin d'IDE qui réagit dès que le code est modifié dans l'éditeur).

On ne perd aucune information : tous les tokens sont préservés, les commentaires et les espaces peuvent rester dans l'AST, sans pour autant nous gêner la plupart du temps (utile si on veut développer un formatteur automatique ou un générateur de documentation, mais aussi pour afficher des erreurs pertinentes).

C'est possible de créer un arbre de syntaxe partiellement valide. Si on arrive pas à parser quelques tokens, on peut les englober dans un nœud « Error » et passer à la suite.

On peut enrichir l'AST facilement en ajoutant des queries, sans avoir à redéfinir des représentations intermédiaires.

Lustre ayant des sorties variées (extended code, binaire, C, etc.), le système de queries est particulièrement adapté. On définit une query par type de sortie, et on les laisse définir leur dépendances, sans avoir à redéfinir toute la suite de passes à chaque fois.

Lustre étant un langage pur, on peut définir une query d'interprétation d'un nœud/fonction et mettre ses résultats en cache, pour créer un interpréteur intégré au compilateur qui soit efficace.

Lexeur (logos)

Code source

Pour écrire un lexeur facilement, on utilise la crate logos.

Cette crate fournit une macro procédurale qu'on peut appliquer à un enumération. Chaque variante de l'énumération est un token possible, et on les annote avec un attribut indiquant comment reconnaître ce token.

use logos::Logos; // on importe la macro

#[derive(Logos)] // on l'utilise pour générer le code du lexeur
enum Token {
    #[token("let")]
    Let,

    #[token("function")]
    Function,

    #[regex(r"[ \t\n\f]+", logos::skip)]
    Space,

    // etc.
}

fn main() {
    // la fonction Token::lexer est générée par logos
    let mut lexer = Token::lexer("let let function let");
    // lexer est un itérateur, donc on peut récupérer la liste de tous les
    // tokens avec un collect
    let tokens: Vec<_> = lexer.collect();
    assert_eq!(
        tokens,
        vec![ Token::Let, Token::Let, Token::Function, Token::Let ],
    );
}

Pour les différents attributs disponibles, voir la documentation de logos.

Normalement le lexeur est complet, mais si besoin d'autres tokens pourront être ajoutés.

Attention, beaucoup de variantes de l'énumaration Token ne sont en fait pas des tokens qu'on peut retrouver dans le code source, mais des étiquettes pour l'arbre de syntaxe (cf. le chapitre suivant). Seuls ceux avec un attribut de logos sont de vrais tokens.

Limitations

TODO

Parsing résilient

Problématique

Le parsing correspond à la traduction d'une séquence ordonnée de lexèmes en un arbre syntaxique plus structuré. L'approche traditionelle consiste à définir l'arbre de syntaxe en dur, grâce à des structures. Par exemple:

// ...

enum Statement {
    VoidExpression(Expression), // expression au résultat non utilisé, appel de fonction
    VariableDeclaration {
        name: String,
        explicit_type: Option<Type>,
        initializer: Option<Expression>,
    },
    If {
        condition: Expression,
        then: Block,
        r#else: Block,
    },
    Return(Expression),
    // ...
}

// ...

Pour construire une telle structure, de nombreuses approches existent déjà (LL, LR, LALR) et peuvent être implémentées de différentes manières (combinateurs, générateurs Yacc/Bison/JavaCC/etc.). Un inconvénient majeur réside dans la structure de données elle même, qui n'est pas capable de représenter d'éventuelles erreurs. Concrètement, si un lexème non attendu est lu à un moment donné, le parseur s'arrête, renvoie une erreur, et ne pourra pas "retomber sur ses pieds". On se retrouve alors avec un message du style:

Error: in file "~/fichier_avec_erreur.lus", line 11, col 12 to 12, token ';':
Error: Syntax error


bye

Sympa non? Cet exemple est produit par lv6, le compilateur Lustre officiel.

Ces échecs ne sont pas pratiques pour de nombreuses raisons:

Si un fichier est plein d'erreurs, on ne pourra résoudre les erreurs qu'une par une, du début à la fin, en relançant la compilation à chaque fois qu'on pense en avoir réglée une. Il nous sera impossible d'avoir un message d'erreur sur une erreur à la fin du fichier tant que tout le début du fichier n'est pas correctement parsé.
Il est impossible de faire un language server utilisable, pour intégrer le langage dans un IDE. Au cours de l'écriture d'un code, il y a probablement plus d'instants où le code n'est pas gramaticalement correct que l'inverse. Si notre analyse syntaxique échoue systématiquement tant que le code n'est pas parfait, notre serveur de langage a un intérêt très limité, et certaines fonctionnalités comme l'autocomplétion n'ont aucun sens à être implémentées.

Rendre l'arbre de syntaxe moins rigide

Intrinsèquement, notre problème ne vient pas du type de parseur utilisé, mais bien de la représentation de l'AST sous la forme d'une structure avec des champs biens définis, qui se doivent d'être présents. On souhaiterait au contraire permettre à des éléments d'un noeud syntaxique de ne pas être présents ou d'être au mauvais endroit, tout en structurant quand même la suite de lexèmes sous la forme d'un arbre.

Plutôt que de réinventer la roue, nous utiliseront les structures de données fournies par la bibliothèque Rust rowan, qui est inspiré par la libsyntax de Swift et est développée par l'équipe derrière le language server officiel Rust, rust-analyzer.

Il y a plusieurs concepts intéressants qu'impose/incite l'usage de cette bibliothèque:

Les arbres de syntaxe traditionnels sont constitués d'une multitude de structures précises, bien typées, qui s'emboîtent de façon prévisible. Les arbres de syntaxe rowan sont uniquement constitués de "noeuds" et de "feuilles" génériques. Les feuilles sont les léxèmes fourni au parseur, et les noeuds sont des jetons additionnels permettant de classifier le groupe de noeuds/feuilles que forment les enfants d'un noeud.
Les arbres de syntaxe ne doivent perdre aucune information. Les arbres de syntaxe traditionnels ommettent souvent les espaces, les sauts de ligne et les commentaires, et il est même courant de les ignorer dès l'analyse lexicale. Ici, ces caractères "inutiles" sont gardés. Cela permet de restituer parfaitement le code source à partir d'un arbre de syntaxe, ce qui peut être utile lors de la création d'outils de formattage automatique.
- On notera d'ailleurs que pour obtenir le code source, il suffit de parcourir l'arbre de syntaxe en profondeur et concaténer les représentations textuelles de chaque feuille. La séquence de lexèmes reste strictement dans le même ordre, on ne fait que grouper des éléments de l'arbre à différents niveaux de profondeur.
Les erreurs sont tolérées. Si le parseur lit un léxème innatendu dans un contexte donné (ou n'en lit pas), il peut émettre un noeud Error et placer le léxème dedans, signalant aux étapes suivantes que le léxème doit être ignoré.
- Il est très important de ne pas "jeter" le léxème innatendu mais de bien le placer quelque part dans l'arbre, afin de toujours pouvoir restituer le code source malgré l'erreur.
- Il est possible de créer plusieurs tags Error différents pour typer/classifier les types d'erreurs. Dans notre cas, nous ne typons pas nos erreurs car les descriptions des erreurs sont émises directement au moment du parsing dans une liste à part. Le seul but du noeud Error est de mettre un token à part pour ne pas qu'il soit malencontreusement interprété par les étapes suivantes.

Construire l'arbre

Maintenant que nous avons la structure de données, il reste à traduire une séquence de lexèmes en un arbre rowan. Nous n'avons aucune restriction particulière quant au type de parseur à utiliser. Par simple préférence, nous utilisons la bibliothèque nom, qui suggère une architecture de parseurs basés sur des combinateurs et fournit beaucoup de combinateurs utiles.

L'architecture de nom n'est pas nativement conçue pour parser des arbres rowan. Les combinateurs nom renvoient beaucoup de types Rust très divers alors qu'un arbre rowan n'est constitué que de léxèmes et de noeuds nommés. Il faut donc re-créer quelques parseurs nom usuels adaptés. Voici des parseurs tels que nom les fournit:

Combinateur	Description	Signature `nom`
`opt(P)`	Exécute le parseur P [0; 1] fois	`fn(Parser<T>) -> Parser<Option<T>>`
`many0(P)`	Exécute le parseur P [0; ∞] fois	`fn(Parser<T>) -> Parser<Vec<T>>`
`tuple((P, Q, ...))`	Exécute les parseurs en chaîne	`fn(Parser<T>, Parser<U>, ...) -> Parser<(T, U, ...)>`

Une liste non exhaustive mais plus longue de combinateur nom est (mieux) documentée ici

Afin que tous ces parseurs renvoient le même type de valeur, on introduit un type Children qui représente une liste de noeuds/léxèmes rowan. Ce type sera renvoyé par tous les parseurs.

opt essaye d'exécuter le parseur passé en paramètre. En cas de succès, il renvoie directement la valeur de retour de son parseur. En cas d'échec, il renvoie un Children vide.
many0 exécute plusieurs fois le parseur qu'on lui donne et fusionne par accumulation chaque Children produit à chaque exécution, en un seul Children qui sera retourné.
tuple fusionne également les Children renvoyés par ses parseurs, la différence étant qu'il prend une "liste" finie et non homogène de parseurs. Nous le renommerons join pour ne pas que le type de retour soit incohérent.

On définit également un combinateur node(tag: Token, parser: P) qui exécute le parseur une seule fois et englobe ses Children dans un noeud rowan de "tag" spécifié. Il renvoie un Children qui contient comme élément unique ce nouveau noeud.

Tous ces nouveux parseurs de compatibilité rowan/nom sont définis dans un module sobrement appelé rowan-nom, qui est suffisamment découplé du reste du code pour pouvoir être facilement -- ulterieurement -- extrait vers une autre crate Rust indépendante de rustre, pour pouvoir servir dans d'autres projets.

Simplification des requêtes vers l'arbre de syntaxe

Type-checking

Lustre est un langage statiquement et strictement typé. Chaque terme d'une équation et chaque expression a un type fixé, qui peut être déterminer avant l'exécution. Le typage statique a pour avantage majeur par rapport au typage dynamique de réduire considérablement les risques d'erreurs lors de l'exécution, et permet usuellement d'exécuter les programmes plus rapidement en évitant de devoir vérifier le type des valeurs pendant l'exécution.

Il existe beaucoup de mises en œuvre de type-checkers d'un langage à l'autre. Certains, comme celui d'OCaml, ont des capacités très puissantes d'inférence de type, c'est-à-dire que le type d'une valeur (un paramètre de fonction, par exemple) peut être déterminé en fonction de son usage.

let add a b = a + b;

OCaml devine que la fonction add prend deux int en paramètre, car c'est ce que l'opérateur + requiert.

Heureusement pour nous, Lustre est un langage beaucoup plus simple. Les types des arguments des fonctions sont déclarés explicitement, et les types des expressions sont déterminés par leur parcours en profondeur uniquement — pas dans l'autre sens.

Résilience

Le but de Rustre étant d'être le plus résilient possible, nous utilisons une approche au type-checking qui convient à cette exigence. Voici la représentation actuelle d'un type :

#![allow(unused)]
fn main() {
#[derive(Clone, Debug, Default, Eq, Hash, PartialEq)]
pub enum Type {
    /// Returned when an identifier cannot be resolved, or from an operator when it cannot resolve
    /// its type due to an operand being unknown to.
    #[default]
    Unknown,

    Boolean,
    Integer,
    Real,
    Function {
        args: Vec<Type>,
        ret: Vec<Type>,
    },
    Array {
        elem: Box<Type>,
        size: usize,
    },

    /// Tuple value or return type of a function with multiple (or 0) values
    ///
    /// A tuple **cannot** contain only one element, but **may** be empty. More specifically, if a
    /// function returns exactly one value, it **mustn't** be typed as a `ReturnTuple` as this would
    /// prevent it from being used as an operand to pretty much all operators.
    Tuple(Vec<Type>),
}
}

La partie intéressante est la variante Type::Unknown. Essentiellement, l'idée est que lorsqu'un type ne peut pas être déterminé à cause d'une erreur de l'utilisateur·ice (variable inexistante, fonction inexistante, opérateur appliqué à des opérandes illégaux...), on émet un diagnostic approprié et on renvoie ce type Unknown. Ensuite, celui-ci se comportera comme un joker, évitant qu'une erreur dans une expression cause une cascade d'erreurs dans toutes les expressions qui en dépendent.

Indices de types

Très souvent, il est possible d'avoir une idée plus ou moins précise du type que doit avoir une expression depuis l'extérieur (i.e. depuis un nœud parent dans l'AST). Par exemple, ici, on pourrait déterminer le type de a + b sans connaître le type des deux opérandes.

[...]
var sum : real;
let
  sum = a + b;
tel;

Cette information peut s'avérer utile pour produire des messages d'erreur toujours plus personnalisés et précis. Nous mettons ça en œuvre en passant en paramètre de notre query de résolution de type un éventuel type "attendu". Celui-ci n'est jamais utilisé pour résoudre le type de l'expression passée en paramètre, mais uniquement à des fins d'amélioration des diagnostics.

Voici un exemple de ce que permet ce changement :

function squared (n : int) returns (r : int);
let
  r = n^2; -- confusion d'opérateur : n^2 créé un tableau de 2 éléments qui valent n
tel;

Comme le résolveur de type — et en particulier la branche qui gère l'opérateur ^ — sait que le type attendu pour r est un int, on peut gérer cette confusion possible avec un message sur-mesure, plutôt qu'un bête type mismatch: expected int, found int^2 :

Warning: possible confusion
   ╭─[tests/adder.lus:4:10]
   │
 4 │     r = n^2;
   │         ─┬─
   │          ╰─── the `^` operator creates an array by repeting an element a given number of times, it is not a power operator (hint: use ** instead)
───╯

Initialisation des variables et des paramètres

En Lustre, toutes les valeurs de retour et les variables intermédiaires doivent être initialisées.

function double (x : real) returns (y : real);
let
  y = 2. * x;
tel;

Si on omettait l'équation y = 2. * x;, lv6 nous renverrait cette erreur:

Error: in file "double.lus", line 1, col 5 to 10, token 'double':
Error: 
*** "y" (output y:real on base(y,0)) is not defined. 
*** Defined variables are: 
  -

A première vue, vérifier quelle valeur est assignée et quelle valeur ne l'est pas peut paraître simple. Mais Lustre permet des cas de figure beaucoup plus complexes. Prenons par exemple une modélisation d'un registre à décalage, un composant eléctronique courant qui peut s'apparenter à une file de valeurs booléennes de taille constante.

node shift_register (input : bool) returns (queue : bool^8 ; carry_out : bool);
let
  queue[0] = input;
  queue[1..8] = false^7 -> pre queue[0..7];
  carry_out = pre queue[8];
tel;

Pour expliquer rapidement, ligne par ligne:

On insère l'input en tête de queue

On definit les 7 valeurs restantes comme étant

que des false au cycle 0

puis les 7 premières valeurs de la file au cycle précédent respectif, pour tous les cycles suivants

On définit la retenue sortante comme étant la dernière valeur de la file au cycle précédent

On remarque plusieurs choses dans ce code quant à l'initialisation des variables :

D'une part, nous avons plusieurs variables à initialiser. Cela reste un cas relativement simple à gérer.
D'autre part, la variable queue est composite (ou plutôt son type). Il s'agit d'un tableau de taille constante dont chaque élément doit être initialisé individuellement et il faut donc pouvoir gérer l'initialisation partielle d'une valeur. En particulier, ce qui est intéressant est de savoir si une variable est parfaitement initialisée, et sinon quels "morceaux" de la variable ne le sont pas (afin d'emmettre des messages d'erreur précis).

Afin de respecter la spécification, il est important que rustre vérifie que les variables sont intégralement initialisées. En plus du respect de la spécification, cela fournit également des garanties sur lesquelles des étapes sous-jacentes pourront reposer. Par exemple, si on veut compiler un programme Lustre en langage machine (e.g. pour de la compilation JIT), il est probable que nous passions par le back-end LLVM, qui considère les accès à de la mémoire non initialisé comme un comportement indéfini (UB). En vérifiant préalablement que toutes les variables sont bien affectées, on s'épargne la nécéssité de les initialiser avec une valeur quelconque (par exemple 0).

Approche par développement des variables composites

La première approche qui a été considérée est de simplement développer les variables dites "composites" (structures et tableaux). Par exemple, une variable color : int^3 pourrait être développée en color_0 : int, color_1 : int et color_2 : int. Il est alors très simple de vérifier que les variables originales ont été intégralement initialisées en vérifiant que les variables développées les sont toutes individuellement.

Il est probable que le compilateur officiel fonctionne comme ça, car cette expansion des valeurs composites est notamment effectuée lors de l'expansion du code .lus en .ec (extended code).

Cette approche a deux inconvénients:

Il est plus compliqué de reporter des messages d'erreur clairs lorsqu'une variable n'est pas bien initialisée, et on se retrouve presque à réimplémenter (à l'envers) l'algorithme de la deuxième approche (ci-dessous)
L'empreinte mémoire et processeur peut être inutilement élevée pour des programmes utilisant des grosses structures de données. Par exemple, une simple fonction identité qui prend une structure développable en 10000 champs demanderait un travail énorme à être vérifiée alors qu'il s'agit d'une tâche triviale.

Approche par arbre de partition

Notre approche n'est pas très différente de la précédente, sauf que le développement des variables en éléments composites fait de manière paresseuse (à la manière d'un quadtree par exemple). L'idée est la suivante:

Partons d'une variable de retour pixels : rgb^5^3 avec type rgb = { r, g, b: int }, que nous souhaitons initialiser. On s'apprête à itérer sur toutes les équations d'un noeud Lustre. On commence par créer un ensemble de variables à initialiser (il s'agit en pratique des variables de retour ainsi que des var déclarées dans le noeud). Ici il n'y a qu'une valeur de retour.
pixels
Maintenant, nous itérons sur les équations. Admettons que la première d'entre elle définisse à 0 le canal vert du pixel haut-gauche de l'écran: pixels[0][0].g = 10. L'ensemble de variable à initialiser ressemble donc maintentant à ça:
pixels[0][0].r
pixels[0][0].b
pixels[1]
pixels[2]
pixels[3]
pixels[4]
Et ainsi de suite, on ne garde dans cet ensemble que les "morceaux" de variables pas encore initialisés. Lorsque toutes les équations ont été parcourues, il est alors très simple de voir si toutes les variables sont effectivement initialisées (ensemble vide) et sinon, lesquelles restent à affecter.

Cette vérification nécéssite d'avoir accès au type des variables, et ne peut donc être effectuée qu'après une phase de type-checking. Notons également que l'ensemble de variables à initialiser peut également être représenté sous forme d'arbre, plutôt qu'un ensemble.

Génération

La génération d'extended code (abrégé EC dans la suite) n'est pas documenté par l'implémentation officielle. Cette page cherche donc à fournir une documentation expliquant comment générer un tel code à partir d'un fichier Lustre écrit par un⋅e utilisateurice. Elle se base sur le code de l'implémentation officielle et l'observation de ses sorties.

Types

Seuls les types de base (int/bool/real) sont conservés. Les types « anonymes » sont également conservés.

Pour les variables de type tableau, on remplace chaque élément du tableau par une variable unique.

const x : int^3 = [1, 2, 3];

-- devient

const x_0 : int = 1;
const x_1 : int = 2;
const x_2 : int = 3;

Les énumérations sont remplacées par un type anonyme et un ensemble de constante externes.

type e = enum { A, B };

const e_value : e = A;

-- devient

type e;
const A : e;
const B : e;

const e_value : e = A;

Les structures sont remplacées par des variables individuelles pour chacun de leur champs.

type s = { x : int; y : real };
const s_value : s = s { x = 42; y = 3.1415 };

-- devient

const s_value_x = 42;
const s_value_y = 3.1415;

Nœuds

Les expressions sont séparées pour obtenir un seul opérateur par équation/assertion.

assert x and y and z;
z = x or y and (a < 12);

-- devient

assert_1 = x and y;
assert_2 = assert_1 and z;
assert assert_2;

a_lt_12 = a < 12;
x_or_y = x or y;
z = x_or_y and a_lt_12;

Les opérateurs suivants sont étendus : map, fill, red, fillred, boolred, condact, diese, merge, nor.

Packages

À faire plus tard…

Prise de note

Quand on compile un programme Lustre avec lv6 -ec, plusieurs options sont en réalité activées¹ :

les options pour générer du code LV4 sont activées
- les itérateurs sont inlinés (???) (global_opt.inline_iterator <- true;)
- when_on_ident <- true
- les arrays sont étendues (opt.expand_arrays <- true)
les énumérations sont transformées en constantes
on élimine les when not (no_when_not)
on supprime les préfixes (no_prefix)
on étend les nœuds (opt.expand_nodes <- true)

Une fois que ces options ont été activées, un fichier .ec contenant l'EC est écrit², puis la compilation termine.

La déclaration du nœud en elle-même ne change pas, mais son corps (si il existe) est transformé.³

Les assertions ne sont pas changées.

https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/synchrone/lustre-v6/-/blob/ad176d2a7891cc6b12b98c107f210e03b86d5d24/lib/lv6MainArgs.ml#L259

https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/synchrone/lustre-v6/-/blob/ad176d2a7891cc6b12b98c107f210e03b86d5d24/bin/lv6/main.ml#L309-L311

https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/synchrone/lustre-v6/-/blob/ad176d2a7891cc6b12b98c107f210e03b86d5d24/lib/licDump.ml#L788

Glossaire

Ce lexique définit des termes spécifiques à notre projet. Les définitions ne sont pas objectives et peuvent légèrement varier des définitions communément admises.

Analyseur lexical: Algorithme qui scinde un texte en lexèmes localisés. Situé dans rustre-parser.
Arbre de syntaxe sans perte: Arbre de syntaxe qui inclut tous les lexèmes passés en entrée, y compris les espaces, saut de lignes, commentaires et lexèmes non-reconnus (sous un lexème Error spécial). On peut en restituer le fichier d'entrée sans aucune perte d'informations.
Arbre de syntaxe typé: Arbre de syntaxe abstraite qui représente la structure du programme sans informations superflues (espaces blancs, commentaires) et où les valeurs sont typées. On se laisse la possibilité de conserver les commentaires "de documentation" dans l'AST dans l'éventualité de construire un générateur de documentation similaire à rustdoc, javadoc ou doxygen.
clap (command-line argument parser): Bibliothèque permettant de parser les arguments de ligne de commande
Equation: (d'après la spec) Une affectation dans un noeud lustre (e.g. a = b + 2;) ou une assertion.
Lexème: Elément atomique produit par un analyseur lexical. Une différence par rapport à beaucoup d'implémentations est qu'il existe dans notre cas des lexèmes spéciaux pour représenter les espaces blancs, les commentaires, les sauts de ligne et même les lexèmes non reconnus (Error).
Lexème localisé: Lexème accompagné d'un intervalle d'entiers correspondant à sa position dans le texte. Contrairement à d'autres représentations possibles de lexèmes, les nôtres ne contiennent pas leur valeur lorsqu'ils sont paramétriques. Par exemple, un lexème correspondant à un nombre entier litéral s'appelle juste IConst et ne stocke pas la valeur de l'entier. Si on veut la récupérer, il faut utiliser la localisation du lexème et parser ce nombre dans le code source a posteriori.
logos: Bibliothèque pour générer un analyseur lexical à partir d'un enum Rust dont chaque variante est annotée. Par exemple, pour lexer des expressions mathématiques simples, on pourrait définir:
```
#[derive(Logos)]
enum Token {
  #[token("+")]
  Plus,

  #[token("-")]
  Minus,

  #[regex(r"\d+")]
  Literal,

  #[regex(r"\s+")]
  Whitespace,

  #[error]
  Error,
}
```
...et logos s'occupe de nous générer la fonction d'analyse lexicale.
nom: Bibliothèque pour construire des parseurs basés sur des combinateurs
rowan: Bibliothèque pour représenter et construire des arbres de syntaxe génériques sans perte
yeter: Bibliothèque pour concevoir un système de compilation incrémentale basée sur des "queries". Cette bibliothèque est développée par nous spécfiquement pour les besoins de rustre, et s'inspire d'architectures existantes.

Sources

https://github.com/rust-lang/rust-analyzer/blob/master/docs/dev/syntax.md https://rustc-dev-guide.rust-lang.org/query.html

Rustre

Rustre

Architecture des modules

Diagramme des modules prévisionnel

Responsabilité des modules

Dépendances externes (bibliothèques)

Architecture classique d'un compilateur

Passes et représentations intermédiaires

Lexeur

Parseur

Passes suivantes

Inconvénients de cette approche

Arbre de syntaxe

Naviguer dans l'arbre de syntaxe

Manipuler l'arbre : le système de queries

Avantages de cette architecture

Lexeur (logos)

Limitations

Parsing résilient

Problématique

Rendre l'arbre de syntaxe moins rigide

Construire l'arbre

Simplification des requêtes vers l'arbre de syntaxe

Type-checking

Résilience

Indices de types

Initialisation des variables et des paramètres

Approche par développement des variables composites

Approche par arbre de partition

Génération

Types

Nœuds

Packages

Prise de note

Expansion des énumérations

Types

Constantes

Nœuds

Glossaire

Sources