URL: https://linuxfr.org/users/linkdd/journaux/letlang-ecrire-un-compilateur-en-rust
Title: [Letlang] Écrire un compilateur en Rust
Authors: David Delassus
Date: 2022年03月07日T22:42:53+01:00
License: CC By-SA
Tags: letlang, rust, codegen, compilateur et langage_de_programmation
Score: 15
Bonjour Nal,
Il y a quelques temps, je t'ai présenté [Letlang](https://linuxfr.org/users/linkdd/journaux/letlang-encore-un-nouveau-langage-de-programmation), un projet de langage de programmation fonctionnelle.
Il a pour but d'être compilé vers du code natif, avec un système de type strict et expressif basé sur une logique d'ordre supérieur.
Malheureusement, avec le boulot (mission freelance + [Kubirds](https://kubirds.com)), j'ai pas beaucoup de temps à y consacrer, à part quelques heures par-ci par-là.
L'un des objectifs initiaux de ce langage était d'en faire un langage compilé. Comment ? En produisant du [LLVM IR](https://llvm.org/docs/LangRef.html). Je me suis gratté la tête pas mal de temps sur comment représenter les structures de haut niveau que je veux introduit dans un langage bas niveau comme LLVM IR.
Et puis... un déclic. Vous connaissez un langage un peu plus haut niveau qui compile via LLVM ? Oui, c'est ça, le **Rust**.
Le compilateur Letlang est écrit en Rust, alors pourquoi pas simplement produire du code Rust et ensuite appeler `rustc` ?
Voici un exemple :
```rust
use std::{
 process::{Command, Stdio},
 io::Writer,
 error::Error,
};
fn main() -> Result<(), Box<dyn Error>> {
 let source_code = b"fn main() { println!(\"hello world\"); }";
 let cmd = Commamd::new("rustc").args(["-o", "test", "-"]);
 let mut proc = cmd.stdin(Stdio::piped()).spawn()?;
 if let Some(mut stream) = proc.stdin.as_mut() {
 if let Ok(_size) = stream.write(source_code) {
 proc.wait()?;
 }
 else {
 proc.kill()?;
 return Err(/* some error */);
 }
 }
 else {
 proc.kill()?;
 return Err(/* some error */)
 }
 Ok(())
}
```
Un petit `cargo run` et hop, on a un binaire `test` qui affiche `hello world`.
À partir de là, le compilateur devient assez simple :
 - on a l'AST décrit avec le système de type de Rust (sous forme d'enum et de struct)
 - on utilise le design pattern *visitor* pour parcourir cet AST et produire le code source Rust
 - enfin, on envoi le code source produit à `rustc`
**DISCLAIMER:** Je fais du Rust seulement depuis quelques mois. Je ne prétend pas être un expert dans le langage, et il est tout à fait possible que le code que je produis ne soit pas le plus efficace / optimisé en terme d'usage de la mémoire / ... Je suis bien sûr ouvert à vos critiques les plus viscérales pour me permettre de progresser :)
## Créer l'AST (Abstract Syntax Tree)
C'est la partie la plus simple, on définit grâce au système de type Rust la structure du langage. Lorsque l'on implémentera le parseur, on va extraire les informations dans cet arbre, que l'on passera tel quel au compilateur.
On peut donc déjà commencer à travailler sur le compilateur avant même d'avoir le parseur.
Petit exemple :
```rust
#[derive(Clone, Debug, PartialEq)]
enum Expression {
 Number(f64),
 BinaryOperation { lhs: Box<expression>, op: String, rhs: Box<expression> },
 UnaryOperation { op: String, expr: Box<expression> },
}
impl Enumeration {
 pub fn number(val: 64) -> Box<self> {
 Box::new(Self::Number(val))
 }
 pub fn add(a: Box<expression>, b: Box<expression>) -> Box<self> {
 Box::new(Self::BinaryOperation {
 lhs: a,
 op: "+".to_string(),
 rhs: b,
 })
 }
 pub fn factorial(n: Box<expression>) -> Box<self> {
 Box::new(Self::UnaryOperation {
 op: "!".to_string(),
 expr: n,
 })
 }
}
```
L'usage de `Box<t>` est requis car il s'agit d'un type récursif. L'implémentation qui suit fournit juste quelques helpers pour créer l'AST :
```rust
let ast = Expression::factorial(
 Expression::add(
 Expression::number(2),
 Expression::number(3),
 )
);
```
## Produire le code Rust
Afin de me simplifier la vie lors de la production du code Rust, j'ai décidé d'utiliser la biliothèque [tinytemplate](https://crates.io/crates/tinytemplate).
### Le context de compilation
La première étape est de créer une structure `Context` que l'on va utiliser lors du parcours de l'AST :
```rust
use tinytemplate::TinyTemplate;
struct Context<'a> {
 pub tt: TinyTemplate<'a>,
 // other contextual data, like symbol lookup tables etc...
}
```
Et l'implémentation qui va bien :
```rust
use tinytemplate::format_unescaped;
static SOME_NODE_CODE: &'static str = include_str!("some_node_code.rs.tt");
impl Context<'_> {
 pub fn new() -> Self {
 let mut tt = TinyTemplate::new();
 tt.set_default_formatter(&format_unescaped); // on veut pas de &quot; etc...
 tt.add_template("some_node", SOME_NODE_CODE).expect("should be a valid template");
 Self { tt, /* ... */ }
 }
}
```
### Préparer la gestion d'erreur
Lors du parcours de l'AST, il est possible de rencontrer des erreurs. On va se créer un type spécial pour pouvoir les retourner :
```rust
use std::fmt;
type Result<t> = std::result::Result<t, CompilationError>;
#[derive(Debug)]
struct CompilationError {
 message: String,
}
impl CompilationError {
 pub fn new(message: String) -> Self {
 Self { message }
 }
}
impl fmt::Display for CompilationError {
 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 write!(f, "CompilationError: {}", self.message)
 }
}
impl std::error::Error for CompilationError {
 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
 None
 }
}
```
### Le design pattern Visitor
Un dernier prérequis est le trait qu'il va falloir implémenter pour chaque partie de l'AST :
trait Visitor {
 type Node;
 fn visit(node: Box<node>, context: &mut context) -> Result<string>;
}
```
### Prendre des p'tits bouts d'trucs, et les assembler ensemble
Enfin! On peut commencer à travailler :
```rust
use serde_json::json;
impl Visitor for Expression {
 type Node = Expression;
 fn visit(node: Box<expression>, context: &mut context) -> Result<string> {
 match *node {
 Expression::Number(val) => Ok(format!("{}", val),
 Expression::UnaryOperation { op, expr } => {
 let inner_code = Expression::visit(expr, context)?;
 let data = json!({
 "operator": op,
 "inner_code": inner_code,
 })
 let res = context.tt.render("some_node", &data);
 if let Ok(code) = res {
 Ok(code)
 }
 else {
 Err(CompilationError::new("oops".to_string()))
 }
 },
 Expression::BinaryOperation { lhs, op, rhs } => {
 let lhs_code = Expression::visit(lhs, context)?;
 let rhs_code = Expression::visit(rhs, context)?;
 // [...] similaire a UnaryOperation
 }
 }
 }
}
```
Si je reprend mon AST initial, je peux maintenant le traduire en Rust :
```rust
let ast = Expression::factorial(
 Expression::add(
 Expression::number(2),
 Expression::number(3),
 )
);
let mut context = Context::new();
let source_code = Expression::visit(ast, &context)?;
// call rustc with `source_code.as_bytes()`
```
## Conclusion
Cette solution facilite grandement l'implémentation du compilateur. En effet, l'implémentation du runtime sera faite dans un langage qui me donne certaine garantie concernant la sécurité de la mémoire. Chose que je n'aurais certainement pas pu fournir avec LLVM IR directement.
De même, si je veux ajouter des dépendances au runtime (comme par exemple GMP pour les nombres à précision arbitraire), ou permettre d'inline du Rust en Letlang, ou d'utiliser l'ecosystème Rust en Letlang, tout de suite, cela rend le langage un peu plus utile :)
Cela veut également dire que pour compiler du code Letlang, on aura besoin de la toolchain Rust. C'est parfaitement acceptable je trouve.
Et toi Nal, qu'en penses tu ?
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="httpS://linuxfr.org/users/linkdd/journaux/letlang-ecrire-un-compilateur-en-rust.md">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="httpS://linuxfr.org/users/linkdd/journaux/letlang-ecrire-un-compilateur-en-rust.md" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>