execution de mon petit langage

a marqué ce sujet comme résolu.

@adri1 en fait je me suis un peu mélangé les pinceaux entre ma question et mon exemple, il y a des cas où on voit le problème aussi sans avoir de fonctions locales, mais juste des blocs imbriqués.

let x = 1
{
  let x = 2
}
assert (x == 2)

Ici on a un problème si let x = 2 écrase le binding pour x dans l’environnment, au lieu de juste le "shadower".

gasche

On est d’accord que le cas raisonnable est plutôt d’avoir assert x == 1 qui passe ? Autrement dit, x=2 shadow le x du scope parent dans le bloc, mais ne change pas ce que le scope global voit. J’ai l’impression que le cas du shadowing est couvert proprement en ne faisant jamais remonter le HashMap<Ident, Value> (et en faisant descendre les variables capturées). Autrement dit, le code suivant doit passer :

let x = 1
let y = 42
{
    let x = y + 1
    assert x == 43
}
assert x == 1

hs: pourquoi plusieurs personne utilise ocaml pour créer un mini langage parce qu’a part d’être fonctionnelle(même si c’est déjà un grand avantage) il a pas de tres grand avantage (sans vouloir blesser les fan d’OCaml)

C’est sûrement un mélange de plusieurs choses :

  • écrire un lexer, un parser, et un interpréteur marche plutôt bien en paradigme fonctionnel ;
  • il n’y a pas besoin d’un écosystème très riche pour écrire un compilateur ou un interpréteur, donc le fait que OCaml soit relativement "niche" n’est pas un problème ;
  • les gens qui écrivent des petits langages pour étudier des aspects précis du design d’un langage ont souvent une culture informatique relativement large, et tendent à graviter autour de langages qui sont eux-même plutôt bien conçus d’un point de vue académique (certains de ces projets qui démarrent comme une expérience donnent naissance à des langages industriels puisque les premiers compilateurs Rust étaient en OCaml, jusqu’à ce que Rust en tant que langage ait été suffisamment mûr pour écrire le compilo en Rust) ;
  • le phénomène s’auto-entretient probablement puisqu’il y a beaucoup de ressources sur le sujet qui utilisent des exemples en OCaml.
+0 -0

Je pense qu’on peut gérer les blocs imbriqués en ayant une liste de tables, une par bloc, en remontant dans la liste pour trouver la table qui a défini un certain identifier (et en ajoutant les nouvelles déclarations dans la table la plus récente). Ça me semble quand même nettement plus compliqué qu’utiliser une structure de table associative persistente (on a un environnement qu’on étend, et quand on sort d’un bloc on retourne à la valeur précédente de l’environnment). C’est sans doute un peu plus efficace dans le cas courant (mais pas forcément si on a plein de fonctions locales et qu’on paie une copie de la table pour calculer une fermeture).

Au sujet du choix du langage: on pourrait demander, à l’inverse, pourquoi s’embêter à écrire un évaluateur en Rust, ce qui ajoute pas mal de complexité en plus par rapport à une version OCaml. Comparer:

| While {cond; body} ->
  while eval env cond |> get_bool do
    ignore (eval env body)
  done;
  Unit
            Expr::While { ref cond, ref body } => {
                while self.eval_expr(*cond.clone())? == Value::Bool(true) {
                    self.eval_expr(*body.clone())?;
                }
                return Ok(Value::None);
            },

Les deux codes font clairement la même chose (j’ai un peu changé le code OCaml pour suivre le même protocole que la version Rust, où on mute l’environnement en place plutôt que le renvoyr), et ont la même structure, et c’est lisible des deux côtés. Mais les nouveautés de Rust, le fait d’avoir à écrire ref cond dans le pattern et *cond dans le corps et en fait *cond.clone() car on évalue l’expression plusieurs fois, ne sont pas spécialement utiles dans ce domaine et rajoutent du bruit en plus. Rien de choquant — c’est clairement plus sympa à écrire en Rust qu’en C — mais pas non plus d’avantage clair et des petits inconvénients qui s’enchaînent.

Peut-être que l’OP a prévu d’investir des efforts dans l’efficacité de l’interpréteur, et que c’est la raison du choix du Rust. Je pense qu’avec ce style d’interprète ("tree-walking") on n’aura jamais un truc particulièrement efficace de toute façon, quel que soit le langage. Il vaut mieux compiler vers un bytecode simple et interpréter ça. Pour l’interpréteur de bytecode, Rust (ou C++) apporte sans doute un avantage de performances par rapport à OCaml. Pour le compilateur, il n’y a sans doute pas de différence. On pourrait comprendre l’intérêt, dans ce cadre, d’écrire tout en Rust pour la simplicité d’un outillage unifié (Rust est mieux pour la partie bas-niveau, et un peu plus lourd mais pas honteux non plus sur la partie haut-niveau). Mais ce n’est pas ce dont il est question ici.

pourquoi ai je fait en rust mon interpreteur ?

déjà je ne le ferai pas en ocaml parce que je viens de débuter j’ai juste écris ceci pour m’exercer :


type keyword = If | Else | For | While | Let | In ;; 
type bool = True | False ;;
type op = Add | Sub | Mul | Div ;;
type str = {value: string} ;; 
type number = {value: float};;

type literal = 
  | Bool of bool
  | String of str
  | Number of number
;;

type token =
  | Keyword of keyword
  | Literal of literal
  | Operator of op 
;;

j’ai commencé à faire un interpréteur en python mais je me suis dis (hmmm pourquoi crée un interpréteur dans un interpréteur qui déjà lent ). pas en C ou en C++ à. cause des pointeurs fou , pas en java parce que je n’aime pas ce langage , pas en js pace que je trouve que c’est pas fait comme ça , donc j’ai choisi rust

voilà comment je gére les variables globales et locales (attention c’est peut êtes compliqué )

let x = 5
if x = 2 { // creation d'une nouvelle vm qui sera supprimer à la fin du block
           // la variable x n'existe pas sur la nouvelle vm 
  let x = 3 // je crée la nouvelle variable dans la nouvelle vm  
  let z = global x // je cherche dans l'ancienne vm la variable x 
  global x = 9 // je modifie dans l'ancienne vm , la variable x
  let y = 5 // creation de la variable y dans la nouvelle vm
  let s = x // attention sans le mot clé global , mon langage va chercher dans l'actuelle vm c'est à dire que x vaut 3 et pas 9 
} // je détruit la nouvelle et je passe sur l'ancienne vm 
print x // x vaut 9 (ligne 5)

Mais global n’a pas de sens quand tu peux avoir plusieurs scopes imbriquées, pas juste deux. (Si tu as trois blocs imbriqués, global ça parle de quoi ? Ou alors on dit global global pour remonter de deux blocs ?) C’est le genre de trucs moches qu’on trouve en Python, mais qu’on n’a pas envie de reproduire dans un nouveau langage.

Salut,

Au cas où tu repasses par là, une façon classique est d’avoir ton lexer qui trie les accolades comme délimiteur, il voit l’accolade ouvrante et fermante comme deux symboles différents. Lorsque ton parser rencontre une accolade ouvrante, tu l’appelles récursivement sur le reste des tokens et tu assignes la sortie de cet appel à un bloc. Lorsque tu rencontres une accolade fermante, tu sors de l’appel courant. Évidemment, il faut une erreur si tu rencontres une accolade fermante alors que tu es dans le premier niveau d’appel, et une erreur si tu rencontres la fin de l’entrée alors que tu es dans un niveau différent du premier niveau d’appel.

j’ai essaye de creer les block dans la generation de mon arbre syntaxique

C’est bien le bon endroit, c’est au moment de passer de Vec<Token> à une Expr que tu as besoin de ça (tu peux voir ton programme entier comme un bloc d’ailleurs).

mais ?

une façon classique est d’avoir ton lexer qui trie les accolades comme délimiteur,

le lexer c’est avant la generation d’arbre ? non o_O

sinon, on ne peut pas modifier une variable (c’est plus simple) :P

+0 -0

Le lexer ne s’occupe que de produire le token Token::Delimiter(Delimiter::LeftCurlyBracket) pour { et Token::Delimiter(Delimiter::RightCurlyBracket) pour }. C’est ensuite le parser qui s’occupe de l’aspect récursif de la chose lorsqu’il tombe sur ces tokens.

+0 -0

haa , mais c’est ce que j’ai fait :D

par contre vue que je suis nul en anglais je l’ai appele LeftBrace et RightBrace

mais peux tu m’aider j’ai essaye de le faire je n’arrive pas :

parser.rs

use crate::lexer::Token;
use crate::lexer::Keyword;
use crate::lexer::Seperator;
use crate::lexer::Operator;
use crate::lexer::Identifier;

use crate::tree::Expr;
use crate::tree::Op;

pub struct Parser {
    pub block : Vec<Expr>,
    is_block : bool
}

impl Parser {
    pub fn new() -> Parser {
        Parser {
            block : Vec::new(),
            is_block : false
        }
    }

    pub fn parse_token(&mut self, tokens: &mut Vec<Token>) -> Result<Expr, String> {
        if tokens.len() == 0 {
            return Err("Unexpected end of file".to_string());
        }
        let token = tokens[0].clone();
        let mut else_ = Expr::Empty;
        let mut if_ = Expr::Empty;
        match token {
            Token::NewLine => {
                tokens.remove(0);
                if tokens.iter().any(|t| t == &Token::NewLine) {
                    return Ok(Expr::Empty);
                } else {
                    return self.parse_token(tokens);
                }
            }
            Token::Seperator(Seperator::LeftBrace) => {
                tokens.remove(0);
                let mut body = Vec::new();
                while tokens[1] != Token::Seperator(Seperator::RightBrace) {
                    body.push(self.parse_token(tokens)?);
                }
                tokens.remove(0);
                return Ok(Expr::Block { body: body.clone() });

            },
            Token::Literal(n) => {
                tokens.remove(0);
                if ! self.is_block {  
                    self.block.push(Expr::Literal { value: n.clone() });
                }
                return Ok(Expr::Literal { value: n.clone() });
                
                
            },
            Token::Identifier(i) => {
                tokens.remove(0);
                if ! self.is_block {  
                    self.block.push(Expr::Identifier { name: i.0.clone() });
                }
                return Ok(Expr::Identifier { name: i.0.clone() });
            },
            Token::Keyword(k) => {
                match k {
                    Keyword::If => {
                        let copy_of_is_block = self.is_block.clone();
                        tokens.remove(0); // remove if
                        self.is_block = true;
                        let cond = self.parse_token(tokens)?;
                        let then = self.parse_token(tokens)?;
                        self.is_block = false;
                        if tokens[0] != Token::Seperator(Seperator::RightBrace) {
                            return Err("Expected '}'".to_string());
                        }
                        tokens.remove(0); // remove }
                        if ! copy_of_is_block {
                            self.block.push(Expr::IfThen { cond: Box::new(cond.clone()), then: Box::new(then.clone()) });
                        }
                        return Ok(Expr::IfThen { cond: Box::new(cond.clone()), then: Box::new(then.clone()) });
                    },
                    Keyword::While => {
                        let copy_of_is_block = self.is_block;
                        tokens.remove(0); // remove "while" of while block
                        let cond = self.parse_token(tokens)?;
                        self.is_block = true;
                        let body = self.parse_token(tokens)?;
                        self.is_block = false;
                        if tokens[0] != Token::Seperator(Seperator::RightBrace) {
                            return Err("Expected '}'".to_string());
                        }
                        tokens.remove(0); // remove }
                        if ! copy_of_is_block {
                            self.block.push(Expr::While { cond: Box::new(cond.clone()), body: Box::new(body.clone()) });
                        }
                        return Ok(Expr::While { cond: Box::new(cond.clone()), body: Box::new(body.clone()) });

                    },
                    Keyword::Let => {
                        let copy_of_is_block = self.is_block;
                        tokens.remove(0);
                        if let Token::Identifier(Identifier(name)) = tokens[0].clone() {
                            tokens.remove(0);
                            if tokens[0] != Token::Operator(Operator::Assign) {
                                return Err("Expected operator '='".to_string());
                            } else {
                                tokens.remove(0);
                            }
                            let mut value;
                            if self.is_block {
                                value = self.parse_token(tokens)?;
                            } else {
                                self.is_block = true;
                                value = self.parse_token(tokens)?;
                                self.is_block = false;
                            }
                            if ! copy_of_is_block {
                                self.block.push(Expr::Assign { name: name.clone(), value: Box::new(value.clone()) });
                            }
                            return Ok(Expr::Assign {
                                name: name.clone(),
                                value: Box::new(value.clone())
                            });
                        } else {
                            return Err("Expected identifier".to_string());
                        }
                    },
                    Keyword::For => {
                        let copy_of_is_block = self.is_block;
                        tokens.remove(0);
                        if let Token::Identifier(Identifier(name)) = tokens[0].clone() {
                            tokens.remove(0);
                            if tokens[0] != Token::Keyword(Keyword::In) {
                                return Err("Expected keyword 'in'".to_string());
                            } else {
                                tokens.remove(0);
                            }
                            self.is_block = true;
                            let range = self.parse_token(tokens)?;
                            self.is_block = false;
                            let body = self.parse_token(tokens)?;
                            if tokens[0] != Token::Seperator(Seperator::RightBrace) {
                                return Err("Expected '}'".to_string());
                            }
                            tokens.remove(0);
                            if ! copy_of_is_block {
                                self.block.push(Expr::For {
                                    name: name.clone(),
                                    iter: Box::new(range.clone()),
                                    body: Box::new(body.clone())
                                });
                            }
                            return Ok(Expr::For {
                                name: name.clone(),
                                iter: Box::new(range.clone()),
                                body: Box::new(body.clone())
                            });


                        } else {
                            return Err("Expected identifier: no var".to_string());
                        }
                    },
                    
                    _ => { return Err("Unexpected keyword: ".to_string()); }
                }
            },
            Token::Operator(op) => {
                tokens.remove(0); // remove operator of binary expression
                let left = self.parse_token(tokens)?;
                let right = self.parse_token(tokens)?;
                let op_enum = match op {
                    Operator::Add => Op::Add,
                    Operator::Sub => Op::Sub,
                    Operator::Mul => Op::Mul,
                    Operator::Div => Op::Div,
                    Operator::Mod => Op::Mod,
                    Operator::Eq => Op::Eq,
                    Operator::Lt => Op::Lt,
                    Operator::Gt => Op::Gt,
                    Operator::Le => Op::Le,
                    Operator::Ge => Op::Ge,
                    Operator::Neq => Op::Neq,
                    Operator::And => Op::And,
                    Operator::Or => Op::Or,
                    Operator::Assign => Op::Assign,

                    
                };
                if ! self.is_block {  
                    self.block.push(Expr::BinOp {
                        op: op_enum.clone(),
                        left: Box::new(left.clone()),
                        right: Box::new(right.clone())
                    });
                }
                
                return Ok(Expr::BinOp {
                    op: op_enum.clone(),
                    left: Box::new(left.clone()),
                    right: Box::new(right.clone())
                });
            }
            _ => Err(format!("Unexpected token: {:?}", tokens[0]))
        }

    }

    
}

je sais , mon code est horrible , pour l’instant j’ai supprimer le else

mon code ne marche pas

PS: block en faite c’est le body du file

+0 -0

par contre vue que je suis nul en anglais je l’ai appele LeftBrace et RightBrace

Brace est probablement moins courant que curly bracket, mais c’est correct. Par contre, Separator au lieu de Delimiter est un beau gallicisme (et Seperator au lieu de Separator est une faute d’orthographe :p ).

            Token::Seperator(Seperator::LeftBrace) => {
                tokens.remove(0);
                let mut body = Vec::new();
                while tokens[1] != Token::Seperator(Seperator::RightBrace) {
                    body.push(self.parse_token(tokens)?);
                }
                tokens.remove(0);
                return Ok(Expr::Block { body: body.clone() });

            },

NightProg

Mmm ça me parait bizarre ton affaire. Déjà, tu parses les tokens du bloc un par un : ça ne peut pas marcher parce qu’un token isolé sera rarement une Expr valide ! J’écrirais quelque chose qui ressemblerait à ça (c’est vu de loin sans réfléchir aux cas particuliers) :

match token {
    Token::Delimiter(Delimiter::LeftBrace) => {
        tokens.remove(0);
        self.parse_token(tokens)
    }
    Token::Delimiter(Delimiter::RightBrace) => {
        current_expression.try_into()
    }
}

current_expression est une expression en cours de formation par ton parser. En l’état, tu parses tes tokens de façon assez pédestre en absorbant des tokens de façon un peu erratique pour former des expressions complètes ce qui complexifie pas mal toutes tes branches. Tu aurais intérêt à pouvoir représenter une expression qui n’est pas finie PartialExpr (peut être que ça serait plus flexible en en faisant un trait object, à voir) que tu nourris à ton parser. Ce PartialExpr doit être capable de dire quels sont les tokens suivant valides et implémenter TryInto<Expr> qui ne réussit que lorsque l’expression est effectivement finie. Au début du parsing, on pourrait imaginer que tu démarres avec une PartialExpr qui représente un bloc qu’on vient d’ouvrir (le scope global de ton programme).

Autres remarques liées à Rust :

  • tu fais beaucoup de tokens.remove(0), ce qui est très inefficace. Tu as deux stratégies pour y remédier: soit tu ne fais pas du tout de remove et tu gardes une position en mémoire (ça me parait plus sage, il me parait un peu étrange qu’un parser ait besoin de muter le vecteur de Token à parser), soit tu utilises un structure de données qui est plus efficace pour virer le premier élément tel que VecDeque.
  • tu devrais tirer parti du fait que ton match est une expression et donc que les branches sont évaluées directement comme une expression. Tu as beaucoup de return inutiles, je pense que clippy le ferait remarquer.
  • dans la branche que j’ai citée précédemment, tu fabriques un body, tu le remplies, puis… tu le clone avant de sortir du scope où il existe. Le clone est donc parfaitement inutile.
+0 -0

Separator au lieu de Delimiter est un beau gallicisme (et Seperator au lieu de Separator est une faute d’orthographe :p ).

zut alors , moi qui croisai les doigts pour que ca soit un mot anglais :P

Ce PartialExpr doit être capable de dire quels sont les tokens suivant valides et implémenter

PartialExpr est une struct ? une enum ? un trait ? (mon instinct me dis que c’est une struct)

je n’ai pas trop compris pour l’implementation, dis moi si c’est bon:

struct PartialExpr {
  obj_already_read: Vec<Token>,
  obj_at_read: Vec<Token>,
  expr: Expr
}


impl TryInto<Expr> for PartialExpr {
    type Error = String;
    fn try_into(self) -> Result<Expr, Self::Error> {
      // ... 
    }
}

tu devrais tirer parti du fait que ton match est une expression et donc que les branches sont évaluées directement comme une expression. Tu as beaucoup de return inutiles, je pense que clippy le ferait remarquer.

oui , je vais regarder

merci pour ton temps

+0 -0

Separator au lieu de Delimiter est un beau gallicisme (et Seperator au lieu de Separator est une faute d’orthographe :p ).

zut alors , moi qui croisai les doigts pour que ca soit un mot anglais :P

C’est un mot anglais, c’est juste qu’il n’est pas utilisé dans ce contexte.

Je reprends mon explication sur PartialExpr (en faire un trait est probablement le plus simple) parce que j’ai pas été clair. Dans l’état des choses, lorsque tu rencontres par exemple un Token::Keyword(Keyword::Let), tu t’empresses d’aller lire les tokens suivants pour vérifier que tu as un identificateur, puis un signe égal, puis un truc qui te donne une valeur pour enfin former une Expr::Assign. Ça te donne un code compliqué et pas très réutilisable si par exemple tu changes ce que tu autorises après let (ou les contextes dans lesquels let peut être utilisé). Ton principal problème est que tu essaies impérativement de fournir un expression constante, et ça t’oblige à gérer tous les cas possibles dans chaque branche de ton match token (par exemple ton code qui gère les blocs est explosé de partout parce que tu veux autoriser les blocs dans beaucoup de contexte). Une façon de contourner ce problème est que ta fonction parse_token ne chercher pas à faire des expressions complètes tout le temps et délègue la responsabilité de savoir ce qui est autorisé dans des bouts d’expressions. Par exemple, quand tu rencontres un let, tu pourrais former une expression partielle LetPartialExpr qui n’acceptera qu’un identificateur ou produira une erreur. Si tu rencontres un identificateur, tu obtiens un LetIdPartialExpr qui n’acceptera qu’un signe = ou produira une erreur. Tu obtiens alors un LetIdEqPartialExpr qui acceptera tout ce qui peut conduire à une Expr (beaucoup de choses!) (note que t’es pas obligé d’avoir autant de types intermédiaires, c’est à toi de voir ce qui est comfortable). Ton parser va se fier à la PartialExpr en cours pour accepter ou refuser les tokens suivants jusqu’à obtenir une Expr complète.

Tout ce mécanisme revient essentiellement à écrire une grammaire pour ton langage sous forme objet.

+1 -0

donc si j’ai compris, il faut creer un trait PartialExpr, puis implementer par example à LetExpr etc

et moment de la generation d’arbre syntatic:

Keyword::Let => {
    index -= 1;
    current = LetExpr::new();
},
Token::Literal(i) => {
   match i {
      Literal::String(n) => {
          current = current.push(n);
      }
   }
}

j’ai bon? :P

+0 -0

Mes deux cents (je ne connais pas Rust): pour moi, il est probablement nécessaire de passer par une phase de parsing (que tu es en train d’implémenter) qui vérifier que ton code est syntaxiquement correct et te générant un abstract syntax tree (qu’il me semble que tu es en train de construire), suivi seulement de l’exécution, ou tu peux vérifier la sémantique (de types, entre autre, pour éviter des 1 + 'abc').

et moment de la generation d’arbre syntatic:

Keyword::Let => {
    index -= 1;
    current = LetExpr::new();
},
Token::Literal(i) => {
   match i {
      Literal::String(n) => {
          current = current.push(n);
      }
   }
}

C’est pas très clair, je ne peux pas deviner où sont ces branches, ce qu’est index, le scope de current (qui se retrouve dans deux branches qui se suivent mais n’ont à priori rien à voir puisque le match n’est pas fait sur le même type) et ce que fait current.push sans un squelette de code.

désolé mais je ne code pas sans ta réponse(je ne veux pas écrire du code faux) un oui ou un non suffirait

Je pense que c’est une mauvaise idée, comprendre pourquoi un design donné fonctionne passe aussi par comprendre pourquoi d’autres designs ne fonctionnent pas aussi bien. Il ne faut pas hésiter à se planter et tenter ensuite de corriger le tir lorsque tu te rends compte que le code part en vrille parce que tu as mal abstrait quelque chose, c’est plus formateur que d’attendre la solution sans rien essayer. C’est aussi plus proche de ce qui se passe quand tu développes une solution à un problème pas forcément très bien connu, modifier les abstractions manipulées dans le code pour le rendre plus souple/lisible/performant/correct est une compétence qui se développe beaucoup en pratiquant.

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte