Interpréteur µRust 1 : expressions, instructions, variables

Vous allez dans ce TP et le prochain écrire un interpréteur pour µRust en suivant les étapes vues en cours.

Découverte du squelette de code

Récupérez le squelette de code et exécutez le programme.

Note: sur les machines du département, il faudra peut-être changer votre CARGO_HOME pour pouvoir installer les dépendences.

Exemple

shell$ cargo run µRust # 1+1*1 1+1*1 shell$

Examinez l'arborescence du projet (par exemple tree .). Le répertoire parsing contient tous les sous-modules du module parsing. Vous n'avez pas à aller lire les fichiers qui sont dans ce répertoire.

Sinon vous avez 5 autre modules (inutile de lire tous les fichiers en détail pour le moment):

  • binop.rs: le type des opérateurs binaires (+, -, *, /, etc). Pour le moment il n'y a que des opérations sur les entiers, vous aurez une version plus compliquée plus tard
  • error.rs: le type des erreurs, que ce soit d'analyse syntaxique (parsing) ou d'évaluation. Pas besoin de modifier ce fichier.
  • expression.rs: le type des expressions arithmétiques, avec les implémentations des traits Display et Parse. Comme pour binop.rs, ce fichier sera amené à s'enrichir.
  • identifier.rs: le type des identifiants (les variables), grosso modo des chaînes de caractères non mutables et partageables en clonant "sans coût" (cf pointeur intelligent Rc vu dans le cours précédent)
  • parser.rs: la définition du trait Parse et des erreurs d'analyse syntaxique

Mise en place de la boucle read-eval-print

  1. Lancez le programme avec cargo run. Lisez main.rs et vérifiez que vous comprenez bien ce qu'il fait.

  2. Modifiez main.rs de sorte à construire l'arbre syntaxique de l'expression saisie par l'utilisateur; pour utiliser Expression::parse(&str), il vous faudra importer le module expression (use expression::Expression) et le trait Parse (use parser::Parse). Affichez l'expression avec les chaines de format {} (Display) et {:?} (Debug). Vous devriez avoir quelque chose comme ceci.

shell$ cargo run µRust # 1+1*1 (1 + (1 * 1)) BinOp(Const(1), Add, BinOp(Const(1), Mul, Const(1))) shell$ cargo run µRust # 1+1* Cannot parse shell$
  1. Créez un fichier src/eval.rs et définissez-y une méthode eval pour les expressions, en supposant qu'elles sont sans variables, et sans vous préoccuper des erreurs de division par 0.
// eval.rs
//...

impl Expression {
    pub fn eval(&self) -> isize { 
        match self {
            /* ... */
            Identifier(_) => todo!("plus tard"), 
        }
    }
}
  1. Appelez la méthode eval dans la fonction main de main.rs pour afficher la valeur de l'expression.
shell$ cargo run µRust # 1+1*1 - : isize = 2 shell$
  1. Modifiez la signature de la méthode eval, comme vu en cours, pour gérer les erreurs d'évaluation (notamment une division par zéro). Faites afficher les erreurs dans le main(profitez de l'implémentation de Display pour les erreurs).
shell$ cargo run µRust # 1/0 Evaluation Error: Division by zero shell$
  1. Ajoutez une boucle dans la fonction main pour avoir une vrai boucle REPL (voir cours).
shell$ cargo run µRust # 1+1*1 - : isize = 2 µRust # 1-1*1 - : isize = 0 ^D shell$

Espaces de noms et instructions let

  1. Ajoutez un fichier src/namespace.rs qui déclare un struct NameSpace contenant une HashMap associant des identifiants à des isize (voir cours). Implémentez les constructeurs et méthodes new, find et declare.
  2. Ecrivez un module de test dans src/namespace.rs pour tester vos méthodes (ou utilisez celui-ci)
  3. Dans eval.rs, modifiez la méthode eval de Expression pour prendre en compte l'espace de noms, et enlevez le todo!() du cas Identifier. À la suite, écrivez un module de test de votre méthode eval qui vérifie que 1+x s'évalue à 2 dans un espace de nom où x vaut 1, et lève l'erreur Undefined dans un espace de nom vide.
  4. Lisez la définition du type Instruction dans le fichier src/instruction.rs et ajoutez ce fichier à votre projet.
  5. Dans eval.rs, définissez une méthode exec(&self, ns: &mut NameSpace) qui exécute une instruction.
  6. Reprennez la boucle REPL de la fonction main de sorte à non plus évaluer des expressions mais exécuter des instructions
shell$ cargo run µRust # let x = 0 x : isize = 0 µRust # let y = x + 1 y : isize = 1 µRust # x + y - : isize = 1 ^D shell$

Piles d'espaces de noms et blocs

  1. On veut ajouter comme suit une ligne au fichier instruction.rs:
pub enum Instruction {
    Expr(Expression),
    Let{id:Identifier, expr:Expression},
    Block(Vec<Instruction>), // <- NOUVEAU!
}

Récupérez le fichier instruction.rs (v2) qui fait essentiellement ce changement (mais aussi met à jour le parser et l'affichage d'instructions).

  1. Insérez un todo!() dans le match de la méthode exec (fichier eval.rs) pour gérer ce nouveau constructeur Block. Vérifiez que votre projet compile à nouveau.

  2. Ajoutez un fichier namespacestack.rs à votre projet qui implémente une pile d'espaces de noms, comme vu en cours. Implémentez les méthodes new, push, pop, declare, et find vues en cours.

  3. Écrivez un test qui crée une pile avec un espace de noms vide, déclare x valant 0, puis déclare y valant 0, puis empile un nouvel espace de noms vide, et déclare x valant 1. Vérifiez que find renvoie bien 1 pour x, 0 pour y, et une erreur pour z.

  4. Dans le fichier eval.rs, modifiez l'argument de la méthode exec (ce n'est plus un NameSpace, mais un NameSpaceStack) puis supprimez le todo!() de la méthode exec et ajoutez du code pour exécuter un bloc d'instructions. En attendant mieux, renvoyez 0 pour un bloc d'instruction vide. Modifiez aussi l'argument de la méthode eval (idem, ce n'est plus un NameSpace mais un NameSpaceStack).

  5. Modifiez la fonction main de sorte à passer les exemples vus en cours avec des blocs imbriqués.

Sprint final

Récupérez les fichiers src/binop.rs (version 2), src/expression.rs (version 2) et src/instruction.rs (version 3) et étendez votre interpréteur de façon à

  • gérer des valeurs de types entiers, booléens, et unit
  • gérer des expressions conditionnelles et des instructions conditionnelles
  • gérer des variables mutables
  • gérer des boucles while

Il vous faudra créer un enum Type pour représenter le type d'une valeur, un enum Value pour représenter une valeur, décommenter le constructeur TypeMismatch dans error.rs, et remplacer la plupart des isize de votre code par des Value. Les variables mutables auront un type non mutable: les valeurs qu'elles peuvent prendre doivent rester du même type que leur valeur initiale. Attention à bien évaluer de façon paresseuse les opérateurs booléens comme vu en cours.

Tests: exemples de saisies et sorties attendues

Dépannage

Pour changer le CARGO_HOME sur les machines du département

  • éditez la ligne export CARGO_HOME= de votre fichier ~/.zshrc (ou ~/.profile, ou ~/.zprofile, ...) comme suit
export CARGO_HOME=~/.cargo_home
  • créez le répertoire s'il n'existe pas déjà (mkdir -p ~/.cargo_home)
  • lancez cargo run depuis un nouveau terminal