Suport technique et veille technologique

LinuxFr.org : les journaux  -  [Letlang] Écrire un compilateur en Rust (partie 3)

 -  Avril 2022 - 

Sommaire

• • Rappel de syntaxe
  • Un framework pour vérifier les types
  • Une paire d'exemple
  • Conclusion

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
• Écrire un compilateur en Rust
• Écrire un compilateur en Rust (partie 2)
• Faire la différence entre un nombre et une quantité

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 :

int i;
char c;
struct Foo myvar;

Les variables i, c et myvar ont un et un seul type.

En 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 :

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) :

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) :

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 :

#[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 :

#[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 :

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 :

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 :

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 :

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 :

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 :

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.

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.

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 :

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 :

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 :

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é :

Commentaires : voir le flux Atom ouvrir dans le navigateur

par David Delassus