Calculatrice Rust OCaml

Dans cette note de blog, je vais présenter un projet sur lequel je travaille. Il est très librement inspiré d’une UE que j’ai suivie en L1 en 2024-2025 sur l’analyse syntaxique fonctionnelle, ainsi que de l’article qui a servi de base à ce cours, Monadic Parser Combinators de Graham Hutton et Erik Meijer. Dans cette note, je vais dans un premier temps présenter le projet et son architecture. Ensuite, on décrira la manière dont les parseurs sont construits, pour finir sur la façon dont ces parseurs sont intriqués avec du code Rust pour leur utilisation finale.

Projet et architecture

Je me suis lancé dans ce projet pour développer des compétences :

• la programmation en OCaml (le cours de L1 était en Idris2)
• la programmation système en Rust (fork de processus)
• revoir le parsing fonctionnel et le pousser plus loin

Dans cette optique, je me suis imposé comme objectif de développer un shell rudimentaire. Cependant, comme ce projet est très important et afin de ne pas me lancer dans quelque chose de trop ambitieux que je risquerais d’abandonner, j’ai planifié un objectif intermédiaire : la programmation d’une calculatrice.

Pour mener à bien ce projet, j’ai appliqué la structure suivante :

Grammaire et représentation intermédiaire

j’ai commencé par définir la représentation interne en Rust et OCaml :

enum Expr {
    Number(i64),
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Null,
}

type expression = 
  | Val of int
  | Add of expression * expression
  | Sub of expression * expression
  | Mul of expression * expression
  | Div of expression * expression

ces deux représentations sont équivalentes et permettent de définir en compréhension des expressions arithmétiques simples.

pour ce qui est de la version .json, j’ai simplement utilisé des objets définis comme suit :

{"op" : "add", "arg" : [<obj>, <obj>]}

où op définit l’opérateur et arg la liste des arguments qui peuvent être des int ou des expressions.

Moteur de parsing

pour les parseurs, je me suis basé, comme indiqué dans l’introduction, sur l’article Monadic Parser Combinators de Graham Hutton et Erik Meijer pour développer mon moteur de parsing. ce modèle est basé sur le type suivant :

type 'a parser = string -> ('a * string) list

Ce type représente une fonction qui prend en entrée une chaîne de caractères et retourne une liste de tuples, avec le premier élément du type du parseur et le deuxième la chaîne restante sous forme de string. Ce choix a été fait pour s’en servir comme une option, avec la possibilité d’avoir plusieurs résultats possibles, mais dans ce projet je ne l’ai pas utilisé : soit le parseur réussit et retourne une liste contenant un unique tuple, soit il échoue et retourne une liste vide.

On peut donc définir deux parseurs extrêmement basiques :

(* ce parseur reussi tout le temps retourant sont argument sans rien consommer
nom dans l'article : result *)
let pure a =
  fun inp -> [ (a, inp) ]
  
(* ce parseur echoue tout le temps
nom dans l'article : zero *)
let empty =
  fun _inp -> []

bon, si on ne peut pas consommer de caractère, la puissance de ce modèle de parsing est assez faible. on définit donc un parseur qui consomme un caractère :

(* ce parseur consome un caracter et le retourn
nom dans l'article : item *)
let item : char parser = function
  | "" -> []
  | s -> [(s.[0], String.sub s 1 (String.length s - 1))]

On a une bonne base, mais il serait intéressant de pouvoir combiner ces parseurs. On va donc commencer par définir le parseur d’enchaînement :

(* ce parsuer permet d'enchainer deux parsuer le resultat du premeir est passer en argument au deuxiemme
nom dans l'article : bind *)
let ( >>= ) p1 pp2 = 
  fun inp -> match p1 inp with
    | [] -> []
    | l ->  List.concat (List.map (uncurry pp2) l)

on prend soin d’appliquer le second parseur à tous les résultats potentiels du premier parseur.

afin de simplifier le développement, on utilise la fonction de binding d’OCaml https://ocaml.org/manual/5.2/bindingops.html:

(* alias pour utiliser la syntaxe let>>= *)
let (let>>=) p1 p2 = p1 >>= p2

on définit aussi un alias pour enchaîner des parseurs sans en propager le résultat :

(* ce parseur est un equivalent de f >>= k.g ou k est la fonction constent *)
let ( >> ) p1 p2 = p1 >>= Fun.const p2
(* alias pour utiliser la syntaxe let>>= *)
let (let>>) p1 p2 = p1 >> p2

ces parseurs nous permettent de commencer à définir des parseurs intéressants :

(* ce parseur consome un caracter et reussis s'il verifie bien une assertion
nom dans l'article : sat *)
let sat p : char parser = 
  let>>= c = item in 
  
  match p c with 
  | true  -> pure c
  | false -> empty

Ce code donne un exemple de l’utilisation du binding OCaml et constitue un premier parseur vraiment intéressant. Il permet de vérifier qu’un caractère remplit un prédicat.

On peut dériver de ce parseur le parseur qui reconnaît un caractère particulier :

(* ce parseur consome un caracter et reussis s'il est egal a sont argument
nom dans l'article : char *)
let char c : char parser = sat (fun x -> c == x)

Afin d’augmenter encore la puissance du schéma, on va définir un opérateur d’alternative. Il permet de tester un parseur et, en cas d’échec, d’appliquer le deuxième (dans le cas où l’on veut faire diverger les résultats, on a la méthode plus, mais dans la mesure où je ne l’utilise pas dans ce projet je ne développerai pas dessus) :

(* parsuer concatenation de chois avec prioriter sur le premier *)
let ( <|> ) p1 p2 = 
  fun inp -> match p1 inp with
    | [] -> p2 inp
    | result -> result

on va définir deux opérations : many, qui permet d’utiliser un parseur autant de fois qu’il réussit et retourne une liste de résultats, et some, qui a le même effet que many mais échoue si le parseur ne peut pas être appliqué au moins une fois (donc many peut réussir en retournant une liste de résultats vide) :

(* ces deux parseur repete restpctiment 0 ou n fois et 1 ou n fois le parseur passer en argument
nom dans l'article : many et many1 *)
let rec many p =
  some p <|> pure []
and some p =
  let>>= x = p in
  let>>= xs = many p in
  pure (x :: xs)

pour définir ces parseurs, on a utilisé une définition mutuellement récursive.

(* Parse une expression de la forme : p (op p)*
en appliquant les opérateurs de manière associative à gauche.
nom dans l'article : chainl1 *)
let chainl1 p pop =
  let>>= x = p in
  let>>= fys = many (
        let>>= f = pop in
        let>>= y = p   in
        pure (f,y)
      ) in
  pure (List.fold_left (fun a (fu, b) -> fu a b) x fys)

ce dernier parseur présenté permet de parser de manière plus simple les clauses d’un opérateur particulier.

Parseur arithmétique

bon, la dernière section était assez abstraite, on va passer à des choses un peu plus pratiques. l’objectif de cette section est d’expliquer comment est construit le parseur d’expressions arithmétiques de ce projet.

dans un premier temps, on va définir un parseur pour parser les nombres entiers :

let digit = sat (fun c -> List.mem c ['0'; '1'; '2'; '3'; '4'; '5'; '6'; '7'; '8'; '9'])

Ce parseur reconnaît un chiffre.

let digits = some digit

Celui-ci reconnaît une série non nulle de chiffres.

let int = 
  let>>= dig = digits in
  let toInt = fun x -> int_of_string (String.of_seq (List.to_seq x)) in
  pure (toInt dig)

On définit pour finir ce parseur qui permet de reconnaître une chaîne de chiffres et de la convertir en int OCaml.

On va aussi définir un parseur qui reconnaît un parseur p mis entre parenthèses :

let parentised p =
  char '(' >>
  let>>= v = p in
  char ')' >>
  pure v

Pour approcher le parsing d’une expression arithmétique simple, on va commencer par exposer de manière non formelle l’idée derrière le parsing :

une expression arithmétique est un enchaînement de nombres et d’expressions arithmétiques parenthésées séparées par des opérateurs.

cette définition est un bon début, mais lorsqu’on l’implémente de manière naïve elle ne fonctionne pas comme escompté. En effet, elle ne prend pas en compte les priorités opératoires.

la solution que j’ai choisie pour régler cette subtilité est de reformuler ce qu’est une expression arithmétique :

une expression est un ensemble de clauses f séparées par des opérations + et -. une clause f est définie comme un ensemble de nombres ou d’expressions arithmétiques parenthésées séparées par des opérations * et /.

avec cette définition on peut constater que cette fois-ci les priorités sont correctement définies.

on essaie de définir cette définition de manière un peu plus formelle :

expression = f ((+ | -) f)*
f          = b ((* | /) b)*
b          = nobre | expression prenthese

On va maintenant définir ce parseur en OCaml. Il est intéressant de noter que si la définition formelle est bien faite, cette définition peut être extrêmement aisée :

let opSomme = (char '+' >> pure (fun a b -> Add (a, b))) <|>
              (char '-' >> pure (fun a b -> Sub (a, b)))

let opFacteur = (char '*' >> pure (fun a b -> Mul (a, b))) <|>
                (char '/' >> pure (fun a b -> Div (a, b)))

ces deux parseurs définissent des parseurs qui associent un opérateur à une fonction prenant deux arguments et retournant l’objet correspondant à l’application de ces deux objets, l’opération dans le contexte de la représentation OCaml.

let expr_val = let>>= v = int in (pure (Val v))

on définit aussi ce parseur simple pour reconnaître les nombres entiers et les convertir dans le contexte de la représentation interne OCaml.

on peut enfin définir le parseur arithmétique en représentant notre définition formelle.

let rec somme   input = (chainl1 facteur opSomme       ) input
    and facteur input = (chainl1 expr    opFacteur     ) input
    and expr    input = (parentised somme <|> expr_val ) input

let parseur = somme

On peut ensuite écrire des fonctions basiques pour convertir la représentation interne OCaml en JSON. On fait ensuite en sorte que le programme prenne une string sur son entrée standard et retourne le résultat en JSON sur sa sortie standard.

let input = read_line ()

let () = match AnalyseurArithmetique.parseur input with
  | (c, "") :: _ -> Printf.printf "%s\n" (AnalyseurArithmetique.jsonify c)
  | _ -> print_endline "{\"err\" : \"error not implement\" }"

Intrication avec le Rust

dans cette dernière partie on va détailler comment ce code OCaml a été intriqué avec le Rust.

pour la communication entre les deux programmes on utilise les I/O standard d’un processus lancé comme enfant :

fn parse_input(input: &String) -> String {
    static PARSER: &str = "analyser_syntax_ocamel/analyser/_build/install/default/bin/analyser";

    let mut parser_proces = Command::new(PARSER)
        .stdin(Stdio::piped())
        .stdout(Stdio::piped())
        .spawn()
        .expect("parser problemme");

    let pin = parser_proces.stdin.as_mut().unwrap();
    pin.write_all(input.as_bytes()).unwrap();

    let pout = parser_proces.wait_with_output().unwrap();
    let binding = String::from_utf8_lossy(&pout.stdout);
    let output = binding.as_ref();

    println!("Output: {}", output);
    return output.to_string();
}

on a aussi codé cet évaluateur très basique de la représentation interne Rust qui correspond au json parser issu du parseur OCaml :

fn eval(expr: &Expr) -> i64 {
    match expr {
        Expr::Number(n) => *n,
        Expr::Add(a, b) => eval(a) + eval(b),
        Expr::Sub(a, b) => eval(a) - eval(b),
        Expr::Mul(a, b) => eval(a) * eval(b),
        Expr::Div(a, b) => eval(a) / eval(b),
        Expr::Null => 0,
    }
}

Conclusion

Ce projet m’a permis de jeter les bases d’une architecture simple pour une application combinant OCaml et Rust afin de réaliser de l’analyse syntaxique. Cette architecture est volontairement minimaliste, car elle a pour objectif principal de préparer le terrain pour un projet plus avancé à venir dans le futur. Il m’a également permis de mieux comprendre la conception de parseurs fonctionnels et l’intérêt de séparer l’analyse syntaxique (OCaml) de l’exécution (Rust), ce qui ouvre la voie à des applications plus complexes comme un shell complet ou un interpréteur.