URL: https://linuxfr.org/users/linkdd/journaux/letlang-ecrire-un-compilateur-en-rust-partie-3 Title: [Letlang] Écrire un compilateur en Rust (partie 3) Authors: David Delassus Date: 2022年04月25日T00:18:18+02:00 License: CC By-SA Tags: letlang, rust, typechecking et langage_de_programmation Score: 12 Bonjour Nal, Tu seras peut-être content d'apprendre que Letlang avance plutôt bien. Voici donc un nouveau "devlog" qui aujourd'hui parlera de vérification des types, et de comment je compte compiler une définition de type. Voici d'abord une petite table des matières de ma série d'articles sur ce projet : - [Encore un nouveau langage de programmation](https://linuxfr.org/users/linkdd/journaux/letlang-encore-un-nouveau-langage-de-programmation) - [Écrire un compilateur en Rust](https://linuxfr.org/users/linkdd/journaux/letlang-ecrire-un-compilateur-en-rust) - [Écrire un compilateur en Rust (partie 2)](https://linuxfr.org/users/linkdd/journaux/letlang-ecrire-un-compilateur-en-rust-partie-2) - [Faire la différence entre un nombre et une quantité](https://linuxfr.org/users/linkdd/journaux/letlang-faire-la-difference-entre-un-nombre-et-une-quantite) ## Rappel de syntaxe Avant de rentrer dans le vif du sujet, faisons un petit point sur la notion de type en Letlang. **Concept 1 :** Une variable n'a pas de type qui lui est propre. Prenons l'exemple du langage C : ```c int i; char c; struct Foo myvar; ``` Les variables `i`, `c` et `myvar` ont un et un seul type. En Python : ```python def action(duck): duck.quack() ``` `duck` a toujours un unique type, la fonction `action` ne sait pas lequel, mais une erreur sera levée si ce type ne définit pas une méthode `quack`. Le fait est quand même que `duck` a un unique type que l'on peut récupérer avec le code suivant : ```python print(type(duck)) ``` En Letlang, c'est une autre histoire. On n'a pas de fonction `type`, ou `typeof`. Une variable peut appartenir à plusieurs types. Par exemple, `42` est un `int`, un `float`, un nombre pair, un nombre complexe, etc... **Concept 2 :** C'est le type qui définit les propriétés nécessaires pour déterminer si une variable lui appartient. Des exemples de code valent mille mots : ``` class even(n: int) { n % 2 = 0 } ``` On définit un nouveau type `even`. Il est construit à partir d'une valeur qui appartient au type `int`. Et il stipule qu'il contient toutes les valeurs dont le modulo par 2 est égal à 0. C'est comme si l'on définissait la fonction suivante (code Python) : ```python def is_even(n): return isinstance(n, int) and n % 2 == 0 ``` Et cette fonction est ensuite exécutée à chaque fois qu'il y a besoin de vérifier qu'une variable est bien un nombre entier, par exemple : ``` func div_by_2(n: even) -> int { n / 2 } ``` Un appel de cette fonction se traduirait par (code Python) : ```python if not is_even(n): raise TypeError("oops") div_by_2(n) ``` **Concept 3 :** On peut composer les types ensembles. En Letlang, comme en TypeScript, on va avoir les opérateurs `|`, `&` et `!` qui vont permettre de composer plusieurs types pour en créer de nouveaux. Exemple : ``` class even(n: int) { n % 2 = 0 } class odd(n: int & !even) ``` **Concept 4 :** Il existe des types primitifs. Les "valeurs littérales" en Letlang sont typées : - `42` est un `int` et un `float` (et un `number`) - `"hello world"` est une `string` - `true` est un `bool` - `:ok` est un `atom` (cf Erlang/Elixir) - `(:ok, 42)` est un `tuple` J'ai pas encore implémenté les types plus complexes comme les listes, les ensembles, et les dictionnaires (à la TypeScript). Mais ça viendra, chaque chose en son temps :) **Concept 5 :** Les valeurs littérales sont également des types. Cela permet de créer des types du style : ``` class result(v: (:ok, T) | (:error, E)) ``` `:ok` et `:error` sont utilisés en tant que type. Ainsi le tuple `(:un_autre_atom, 42)` n'appartient pas à ce type. ## Un framework pour vérifier les types Que je vérifie les types à la compilation, ou au runtime (les deux seront nécessaires), j'ai besoin d'une manière de représenter en Rust à la fois : - les valeurs - les types - les propriétés à vérifier - les paramètres des types génériques Commençons par se représenter les valeurs primitives : ```rust #[derive(Debug, Clone, PartialEq)] pub enum PrimitiveValue { Boolean(bool), Integer(i64), Float(f64), String(String), Atom(String), } ``` Et de manière plus générale, n'importe quelle valeur : ```rust #[derive(Debug, Clone, PartialEq)] pub enum Value<'a> { Primitive(PrimitiveValue), Tuple(Vec<&'a Value<'a>>), // list, set, dict, ... } ``` Maintenant, le compilateur va pouvoir encapsuler les données avec ce type `Value` lors de la génération du code : ```rust let ok_atom = Value::Primitive(PrimitiveValue::Atom("ok".to_string())); let n_val = Value::Primitive(PrimitiveValue::Integer(42)); let result_tuple = Value::Tuple(vec![&ok_atom, &n_val]); ``` Comme dit précédemment, un type Letlang équivaut à une fonction qui prend en paramètre une valeur et retourne un booléen (vrai si la valeur appartient au type, faux sinon). Cette "fonction" a besoin d'information supplémentaires, comme les paramètres génériques du type par exemple. On va donc plutôt représenter cela avec une structure qui implémente un trait. Notre trait va être tout simple : ```rust pub trait Type { fn has(&self, llval: &Value) -> bool; } ``` Ainsi, chaque "type" Letlang sera traduit par une structure qui implémente ce trait. Bien sûr, le "runtime" Letlang va en fournir quelques uns par défaut : ```rust pub struct BooleanType; impl Type for BooleanType { fn has(&self, llval: &Value) -> bool { match llval { Value::Primitive(PrimitiveValue::Boolean(_)) => true, _ => false, } } } ``` Jusque là, c'est plutôt simple, on va avoir la même chose pour les autres types primitifs. On va ensuite créer un type `ValueType` qui représentera les valeurs primitives en tant que type : ```rust pub struct ValueType<'v> { pub llval: &'v PrimitiveValue, } impl<'v> Type for ValueType<'v> { fn has(&self, llval: &Value) -> bool { match llval { Value::Primitive(pval) => { pval == self.llval }, _ => false, } } } ``` **NB :** Ici, j'utilise bien `PrimitiveValue` et non `Value`. On verra par la suite que les valeurs composites sont typées par des types génériques. En parlant du loup, vient maintenant notre premier type générique. En effet, le type `tuple` n'existe pas, il s'agirat plutôt du type `tuple`. Son implémentation n'est pas très compliquée : ```rust pub struct TupleType<'t> { pub members_types: Vec<&'t dyn Type>, // T... } impl<'t> Type for TupleType<'t> { fn has(&self, llval: &Value) -> bool { match llval { Value::Tuple(members) => { // si pas le même nombre d'éléments, même pas la peine de continuer if members.len() != self.members_types.len() { return false; } // liste de couple (value, type) let pairs = members.iter().zip(self.members_types.iter()); for (member_val, member_type) in pairs { if !member_type.has(member_val) { // si l'un des membres du tuple ne correspond pas au type attendu... return false; } } true }, _ => false, } } } ``` En bref, on s'assure que chaque élément de la valeur correspond au type correspondant du tuple. Pour boucler notre framework, on a besoin d'implémenter le résultat des opérateurs `|`, `&` et `!`. Rien de bien complexe encore une fois : ```rust pub struct OneOfType<'t> { pub lltypes: Vec<&'t dyn Type>, } impl<'t> Type for OneOfType<'t> { fn has(&self, llval: &Value) -> bool { for lltype in self.lltypes.iter() { if lltype.has(llval) { return true; } } false } } ``` On se prépare à une future optimisation qui traduira `a | b | c` en `|(a, b, c)` et non `|(a, |(b, c))`. Même si l'implémentation actuelle de mon AST n'intègre pas cette optimisation, ce n'est pas très grave. ```rust pub struct AllOfType<'t> { pub lltypes: Vec<&'t dyn Type>, } impl<'t> Type for AllOfType<'t> { fn has(&self, llval: &Value) -> bool { for lltype in self.lltypes.iter() { if !lltype.has(llval) { return false; } } true } } ``` Pareil, pas de grande surprise ici. Juste totalement l'opposé du type `OneOfType`. ```rust pub struct NotType<'t> { pub lltype: &'t dyn Type, } impl<'t> Type for NotType<'t> { fn has(&self, llval: &Value) -> bool { !self.lltype.has(llval) } } ``` Voilà. On a maintenant notre framework complet. Mettons le à l'épreuve. ## Une paire d'exemple **Exemple 1 :** Le type `result` Reprenons sa définition : ``` class result(v: (:ok, T) | (:error, E)) ``` Quel code Rust devrait produire le compilateur ? En premier lieu, il y a sa représentation : ```rust pub struct ResultType<'t> { pub ok_val_type: &'t dyn Type, // T pub err_val_type: &'t dyn Type, // E } ``` **NB :** Les noms des structures et des champs ici sont générés par un humain (moi), pas par le futur compilateur qui produira sûrement des choses du style `branch_0` / `branch_1` / etc... Et pour l'implémentation : ```rust impl<'t> Type for ResultType<'t> { fn has(&self, llval: &Value) -> bool { // le but est de créer dans un premier temps le type `(:ok, T) | (:error, E)` // on commence par `(:ok, T)` : // on représente l'atom `:ok` en tant que type let ok_tag = PrimitiveValue::Atom("ok".to_string()); let ok_tag_type = ValueType { llval: &ok_tag }; // et on construit le type `tuple<:ok, T>` let ok_tuple_type = TupleType { members_types: vec![&ok_tag_type, self.ok_val_type], }; // on enchaîne avec `(:error, E)` : // on représente l'atom `:error` en tant que type let err_tag = PrimitiveValue::Atom("error".to_string()); let err_tag_type = ValueType { llval: &err_tag }; // et on construit le type `typle<:error, T>` let err_tuple_type = TupleType { members_types: vec![&err_tag_type, self.err_val_type], }; // enfin, on peut combiner les deux avec l'opérateur | : let lltype = OneOfType { lltypes: vec![ &ok_tuple_type, &err_tuple_type, ], }; // le type `result` n'inclut pas de check supplémentaire : lltype.has(llval) } } ``` Ok, c'est plutôt intéressant. Grâce à ce mécanisme, le système d'inférence de type sera juste une "factory" qui à partir d'un AST retourne une instance de ces structures. **Exemple 2 :** Le type `even` Reprenons sa définition : ``` class even(n: int) { n % 2 = 0 } ``` Cela donnerait : ```rust pub struct EvenType; impl Type for EvenType { fn has(&self, llval: &Value) -> bool { let int_type = IntegerType {}; if !int_type.has(llval) { return false; } let res = call("=", call("%", llval, &Value::Primitive(PrimitiveValue::Integer(2)) ), &Value::Primitive(PrimitiveValue::Integer(0)) ); match res { Value::Primitive(PrimitiveValue::Boolean(true)) => true, _ => false, } } } ``` **NB :** Ici l'usage de `call` représente l'exécution du code présent dans la définition du type. Cela ne sera certainement pas sa forme définitive cela dit. Mais l'idée est bien là. ## Conclusion Ce framework me permettra d'implémenter le type checking lors de la phase de compilation, et le système d'inférence de type sera un ensemble de "factory" générant les types en fonction de l'AST. Ce code généré lors de la compilation sera également inclut au runtime. En effet, les données issues d'effets de bords (comme la lecture depuis un fichier, socket, clavier, ...) devront aussi être vérifiées au runtime. Je suis curieux d'avoir ton avis sur le design et l'implémentation. Penses tu qu'il y a mieux ? Pour ceux qui ont tout lu, voici un carré glacé : ![carré glacé](https://img.cuisineaz.com/660x660/2013/12/20/i52726-millefeuilles.jpeg)

AltStyle によって変換されたページ (->オリジナル) /