Stork, Partie 3 : Implémentation d'expressions et de variables

Dans la partie 3 de notre série, notre langage de programmation léger fonctionnera enfin. Il ne sera pas Turing-complet, il ne sera pas puissant, mais il pourra évaluer des expressions et même appeler des fonctions externes écrites en C++.

Je vais essayer de décrire le processus avec le plus de détails possible, principalement parce que c'est le but de cette série de blogs, mais aussi pour ma propre documentation car, dans cette partie, les choses se sont un peu compliquées.

J'ai commencé à coder pour cette partie avant la publication du deuxième article, mais il s'est avéré que l'analyseur d'expression devrait être un composant autonome qui mérite son propre article de blog.

Cela, ainsi que certaines techniques de programmation infâmes, ont permis à cette partie de ne pas être monstrueusement grosse, et pourtant, certains lecteurs pointeront très probablement lesdites techniques de programmation et se demanderont pourquoi j'ai dû les utiliser.

Pourquoi utilisons-nous des macros ?

Au fur et à mesure que j'ai acquis de l'expérience en programmation en travaillant sur différents projets et avec différentes personnes, j'ai appris que les développeurs ont tendance à être assez dogmatiques, probablement parce que c'est plus facile de cette façon.

Le premier dogme de la programmation est que l' goto est mauvaise, diabolique et horrible. Je peux comprendre d'où vient ce sentiment, et je suis d'accord avec cette notion dans la grande majorité des cas lorsque quelqu'un utilise l' goto . Cela peut généralement être évité et un code plus lisible pourrait être écrit à la place.

Cependant, on ne peut nier que la rupture de la boucle interne en C++ peut être facilement accomplie avec l' goto . L'alternative - qui nécessite une variable bool ou une fonction dédiée - pourrait être moins lisible que le code qui tombe dogmatiquement dans le seau des techniques de programmation interdites.

Le deuxième dogme, pertinent exclusivement pour les développeurs C et C++, est que les macros sont mauvaises, diaboliques, affreuses et, fondamentalement, un désastre imminent. Ceci est presque toujours accompagné de cet exemple :

 #define max(a, b) ((a) > (b) ? (a) : (b)) ... int x = 3; int z = 2; int y = max(x++, z);

Et puis il y a une question : Quelle est la valeur de x après ce morceau de code, et la réponse est 5 parce que x est incrémenté deux fois, un de chaque côté du ? -opérateur.

Le seul problème est que personne n'utilise de macros dans ce scénario. Les macros sont mauvaises si elles sont utilisées dans un scénario où les fonctions ordinaires fonctionnent bien, surtout si elles prétendent être des fonctions, de sorte que l'utilisateur n'est pas conscient de leurs effets secondaires. Cependant, nous ne les utiliserons pas en tant que fonctions et nous utiliserons des lettres majuscules pour leurs noms afin qu'il soit évident qu'il ne s'agit pas de fonctions. Nous ne pourrons pas les déboguer correctement, et c'est dommage, mais nous allons vivre avec cela, car l'alternative consiste à copier-coller le même code des dizaines de fois, ce qui est beaucoup plus sujet aux erreurs que les macros. Une solution à ce problème est d'écrire le générateur de code, mais pourquoi devrions-nous l'écrire alors que nous en avons déjà un intégré en C++ ?

Les dogmes en programmation sont presque toujours mauvais. J'utilise prudemment "presque" ici juste pour éviter de tomber récursivement dans le piège dogmatique que je viens de mettre en place.

Vous pouvez trouver le code et toutes les macros pour cette partie ici.

variables

Dans la partie précédente, j'ai mentionné que Stork ne sera pas compilé en binaire ou quelque chose de similaire au langage d'assemblage, mais j'ai également dit que ce sera un langage typé statiquement. Il sera donc compilé, mais dans un objet C++ qui pourra s'exécuter. Cela deviendra plus clair plus tard, mais pour l'instant, disons simplement que toutes les variables seront des objets en soi.

Puisque nous voulons les conserver dans le conteneur de variables globales ou sur la pile, une approche pratique consiste à définir la classe de base et à en hériter.

 class variable; using variable_ptr = std::shared_ptr<variable>; class variable: public std::enable_shared_from_this<variable> { private: variable(const variable&) = delete; void operator=(const variable&) = delete; protected: variable() = default; public: virtual ~variable() = default; virtual variable_ptr clone() const = 0; template <typename T> T static_pointer_downcast() { return std::static_pointer_cast< variable_impl<typename T::element_type::value_type> >(shared_from_this()); } };

Comme vous pouvez le voir, c'est assez simple, et la fonction clone , qui fait la copie en profondeur, est sa seule fonction membre virtuelle en dehors du destructeur.

Comme nous utiliserons toujours des objets de cette classe via shared_ptr , il est logique de l'hériter de std::enable_shared_from_this , afin que nous puissions facilement en obtenir le pointeur partagé. La fonction static_pointer_downcast est là pour plus de commodité car nous devrons fréquemment effectuer une conversion descendante de cette classe vers son implémentation.

La véritable implémentation de cette classe est variable_impl , paramétrée avec le type qu'elle contient. Il sera instancié pour les quatre types que nous utiliserons :

 using number = double; using string = std::shared_ptr<std::string>; using array = std::deque<variable_ptr>; using function = std::function<void(runtime_context&)>;

Nous utiliserons double comme type de nombre. Les chaînes sont comptées en référence, car elles seront immuables, pour permettre certaines optimisations lors de leur passage par valeur. Array sera std::deque , car il est stable, et notons simplement que runtime_context est la classe qui contient toutes les informations pertinentes sur la mémoire du programme pendant l'exécution. Nous y reviendrons plus tard.

Les définitions suivantes sont également fréquemment utilisées :

 using lvalue = variable_ptr; using lnumber = std::shared_ptr<variable_impl<number>>; using lstring = std::shared_ptr<variable_impl<string>>; using larray = std::shared_ptr<variable_impl<array>>; using lfunction = std::shared_ptr<variable_impl<function>>;

Le "l" utilisé ici est raccourci pour "lvalue". Chaque fois que nous avons une lvalue pour un type, nous utiliserons le pointeur partagé vers variable_impl .

Contexte d'exécution

Pendant l'exécution, l'état de la mémoire est conservé dans la classe runtime_context .

 class runtime_context{ private: std::vector<variable_ptr> _globals; std::deque<variable_ptr> _stack; std::stack<size_t> _retval_idx; public: runtime_context(size_t globals); variable_ptr& global(int idx); variable_ptr& retval(); variable_ptr& local(int idx); void push(variable_ptr v); void end_scope(size_t scope_vars); void call(); variable_ptr end_function(size_t params); };

Il est initialisé avec le nombre de variables globales.

• _globals conserve toutes les variables globales. Ils sont accessibles avec la fonction membre global avec l'index absolu.
• _stack conserve les variables locales et les arguments de la fonction, et l'entier en haut de _retval_idx conserve l'index absolu dans _stack de la valeur de retour actuelle.
• La valeur de retour est accessible avec la fonction retval , tandis que les variables locales et les arguments de la fonction sont accessibles avec la fonction local en passant l'index relatif à la valeur de retour actuelle. Les arguments de la fonction ont des indices négatifs dans ce cas.
• La fonction push ajoute la variable à la pile, tandis que end_scope supprime le nombre de variables passé de la pile.
• La fonction call redimensionnera la pile de un et poussera l'index du dernier élément de _stack vers _retval_idx .
• end_function supprime la valeur de retour et le nombre d'arguments transmis de la pile et renvoie également la valeur de retour supprimée.

Comme vous pouvez le constater, nous n'implémenterons aucune gestion de la mémoire de bas niveau et nous tirerons parti de la gestion de la mémoire native (C++), que nous pouvons tenir pour acquise. Nous n'implémenterons aucune allocation de tas non plus, du moins pour le moment.

Avec runtime_context , nous avons enfin tous les blocs de construction nécessaires pour le composant central et le plus difficile de cette partie.

Expressions

Pour expliquer pleinement la solution compliquée que je vais présenter ici, je vais brièvement vous présenter quelques tentatives infructueuses que j'ai faites avant de choisir cette approche.

L'approche la plus simple consiste à évaluer chaque expression en tant que variable_ptr et à avoir cette classe de base virtuelle :

 class expression { ... public: variable_ptr evaluate(runtime_context& context) const = 0; lnumber evaluate_lnumber(runtime_context& context) const { return evaluate(context)->static_pointer_downcast<lnumber>(); } lstring evaluate_lstring(runtime_context& context) const { return evaluate(context)->static_pointer_downcast<lstring>(); } number evaluate_number(runtime_context& context) const { return evaluate_lnumber(context)->value; } string evaluate_string(runtime_context& context) const { return evaluate_lstring(context)->value; } ... }; using expression_ptr = std::unique_ptr<expression>;

Nous hériterons alors de cette classe pour chaque opération, telle que l'addition, la concaténation, l'appel de fonction, etc. Par exemple, ce serait l'implémentation de l'expression d'addition :

 class add_expression: public expression { private: expression_ptr _expr1; expression_ptr _expr2; public: ... variable_ptr evaluate(runtime_context& context) const override{ return std::make_shared<variable_impl<number> >( _expr1->evaluate_number(context) + _expr2->evaluate_number(context) ); } ... };

Nous devons donc évaluer les deux côtés ( _expr1 et _expr2 ), les ajouter, puis construire variable_impl<number> .

Nous pouvons downcaster des variables en toute sécurité car nous avons vérifié leur type pendant la compilation, ce n'est donc pas le problème ici. Cependant, le gros problème est la pénalité de performance que nous payons pour l'allocation de tas de l'objet renvoyé, qui, en théorie, n'est pas nécessaire. Nous faisons cela pour satisfaire la déclaration de la fonction virtuelle. Dans la première version de Stork, nous aurons cette pénalité lorsque nous renverrons des nombres à partir de fonctions. Je peux vivre avec cela, mais pas avec la simple expression de pré-incrémentation faisant l'allocation de tas.

Ensuite, j'ai essayé avec des expressions spécifiques au type héritées de la base commune :

 class expression { ... public: virtual void evaluate(runtime_context& context) const = 0; ... }; class lvalue_expression: public virtual expression { ... public: virtual lvalue evaluate_lvalue(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_lvalue(context); } ... }; using lvalue_expression_ptr = std::unique_ptr<lvalue_expression>; class number_expression: public virtual expression { ... public: virtual number evaluate_number(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_number(context); } ... }; using number_expression_ptr = std::unique_ptr<number_expression>; class lnumber_expression: public lvalue_expression, public number_expression { ... public: virtual lnumber evaluate_lnumber(runtime_context& context) const = 0; lvalue evaluate_lvalue(runtime_context& context) const override { return evaluate_lnumber(context); } number evaluate_number(runtime_context& context) const override { return evaluate_lnumber(context)->value; } void evaluate(runtime_context& context) const override { return evaluate_lnumber(context); } ... }; using lnumber_expression_ptr = std::unique_ptr<lnumber_expression>;

Ce n'est qu'une partie de la hiérarchie (uniquement pour les nombres), et nous avons déjà rencontré des problèmes de forme en losange (la classe héritant de deux classes avec la même classe de base).

Heureusement, C++ offre l'héritage virtuel, qui donne la possibilité d'hériter de la classe de base, en gardant le pointeur vers celle-ci, dans la classe héritée. Par conséquent, si les classes B et C héritent virtuellement de A, et que la classe D hérite de B et C, il n'y aurait qu'une seule copie de A dans D.

Il y a cependant un certain nombre de pénalités que nous devons payer dans ce cas - les performances et l'incapacité de descendre de A, pour n'en nommer que quelques-unes - mais cela ressemblait toujours à une opportunité pour moi d'utiliser l'héritage virtuel pour la première fois dans ma vie.

Maintenant, l'implémentation de l'expression d'addition semblera plus naturelle :

 class add_expression: public number_expression { private: number_expression_ptr _expr1; number_expression_ptr _expr2; public: ... number evaluate_number(runtime_context& context) const override{ return _expr1->evaluate_number(context) + _expr2->evaluate_number(context); } ... };

En termes de syntaxe, il n'y a rien de plus à demander, et c'est aussi naturel que possible. Cependant, si l'une des expressions internes est une expression numérique lvalue, elle nécessitera deux appels de fonction virtuelle pour l'évaluer. Pas parfait, mais pas terrible non plus.

Ajoutons des chaînes dans ce mélange et voyons où cela nous mène :

 class string_expression: public virtual expression { ... public: virtual string evaluate_string(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_string(context); } ... }; using string_expression_ptr = std::unique_ptr<string_expression>;

Puisque nous voulons que les nombres soient convertibles en chaînes, nous devons hériter number_expression de string_expression .

 class number_expression: public string_expression { ... public: virtual number evaluate_number(runtime_context& context) const = 0; string evaluate_string(runtime_context& context) const override { return tostring(evaluate_number(context)); } void evaluate(runtime_context& context) const override { evaluate_number(context); } ... }; using number_expression_ptr = std::unique_ptr<number_expression>;

Nous avons survécu à cela, mais nous devons redéfinir la méthode virtuelle d' evaluate , sinon nous serons confrontés à de graves problèmes de performances en raison d'une conversion inutile de nombre en chaîne.

Donc, les choses deviennent évidemment laides, et notre conception leur survit à peine parce que nous n'avons pas deux types d'expressions qui devraient être converties l'une à l'autre (dans les deux sens). Si tel était le cas, ou si nous essayions d'avoir une sorte de conversion circulaire, notre hiérarchie ne pourrait pas le gérer. Après tout, la hiérarchie doit refléter la relation est-une, et non la relation est-convertible-en, qui est plus faible.

Toutes ces tentatives infructueuses m'ont conduit à une conception compliquée mais - à mon avis - correcte. Premièrement, avoir une seule classe de base n'est pas crucial pour nous. Nous avons besoin de la classe d'expression qui serait évaluée à void, mais si nous pouvons faire la distinction entre les expressions void et les expressions d'un autre type au moment de la compilation, il n'est pas nécessaire de les convertir dans un runtime. Par conséquent, nous allons paramétrer la classe de base avec le type de retour de l'expression.

Voici l'implémentation complète de cette classe :

 template <typename R> class expression { expression(const expression&) = delete; void operator=(const expression&) = delete; protected: expression() = default; public: using ptr = std::unique_ptr<const expression>; virtual R evaluate(runtime_context& context) const = 0; virtual ~expression() = default; };

Nous n'aurons qu'un seul appel de fonction virtuelle par évaluation d'expression (bien sûr, nous devrons l'appeler de manière récursive), et puisque nous ne compilons pas en code binaire, c'est un assez bon résultat. Il ne reste plus qu'à faire la conversion entre les types, quand c'est autorisé.

Pour ce faire, nous allons paramétrer chaque expression avec le type de retour et l'hériter de la classe de base correspondante. Ensuite, dans la fonction d' evaluate , nous convertirons le résultat de l'évaluation en la valeur de retour de cette fonction.

Par exemple, voici notre expression d'addition :

 template <typename R> class add_expression: public expression<R> { ... R evaluate(runtime_context& context) const override{ return convert<R>( _expr1->evaluate(context) + _expr2->evaluate(context) ); } ... };

Pour écrire la fonction "convert", nous avons besoin d'une infrastructure :

 template<class V, typename T> struct is_boxed { static const bool value = false; }; template<typename T> struct is_boxed<std::shared_ptr<variable_impl<T> >, T> { static const bool value = true; }; string convert_to_string(number n) { std::string str if (n == int(n)) { str = std::to_string(int(n)); } else { str = std::to_string(n); } return std::make_shared<std::string>(std::move(str)); } string convert_to_string(const lnumber& v) { return convert_to_string(v->value); }

La structure is_boxed est un trait de type qui a une constante interne, value , qui prend la valeur true si (et seulement si) le premier paramètre est un pointeur partagé vers variable_impl paramétré avec le second type.

L'implémentation de la fonction convert serait possible même dans les anciennes versions de C++, mais il existe une instruction très utile en C++17 appelée if constexpr , qui évalue la condition au moment de la compilation. S'il est évalué à false , il supprimera complètement le bloc, même s'il provoque l'erreur de compilation. Sinon, il supprimera le bloc else .

 template<typename To, typename From> auto convert(From&& from) { if constexpr(std::is_convertible<From, To>::value) { return std::forward<From>(from); } else if constexpr(is_boxed<From, To>::value) { return unbox(std::forward<From>(from)); } else if constexpr(std::is_same<To, string>::value) { return convert_to_string(from); } else { static_assert(std::is_void<To>::value); } }

Essayez de lire cette fonction :

• Convertir s'il est convertible en C++ (c'est pour le pointeur variable_impl upcast).
• Déballez s'il est en boîte.
• Convertir en chaîne si le type cible est chaîne.
• Ne rien faire et vérifier si la cible est vide.

À mon avis, c'est beaucoup plus lisible que l'ancienne syntaxe basée sur SFINAE.

Je vais donner un bref aperçu des types d'expression et omettre certains détails techniques afin de rester raisonnablement bref.

Il existe trois types d'expressions feuilles dans une arborescence d'expressions :

• Expression de variable globale
• Expression de variable locale
• Expression constante

 template<typename R, typename T> class global_variable_expression: public expression<R> { private: int _idx; public: global_variable_expression(int idx) : _idx(idx) { } R evaluate(runtime_context& context) const override { return convert<R>( context.global(_idx) ->template static_pointer_downcast<T>() ); } };

Outre le type de retour, il est également paramétré avec le type de variable. Les variables locales sont traitées de la même manière, et c'est la classe des constantes :

 template<typename R, typename T> class constant_expression: public expression<R> { private: T _c; public: constant_expression(T c) : _c(std::move(c)) { } R evaluate(runtime_context& context) const override { return convert<R>(_c); } };

Dans ce cas, nous convertissons la constante immédiatement dans le constructeur.

Ceci est utilisé comme classe de base pour la plupart de nos expressions :

 template<class O, typename R, typename... Ts> class generic_expression: public expression<R> { private: std::tuple<typename expression<Ts>::ptr...> _exprs; template<typename... Exprs> R evaluate_tuple( runtime_context& context, const Exprs&... exprs ) const { return convert<R>(O()( std::move(exprs->evaluate(context))...) ); } public: generic_expression(typename expression<Ts>::ptr... exprs) : _exprs(std::move(exprs)...) { } R evaluate(runtime_context& context) const override { return std::apply( [&](const auto&... exprs){ return this->evaluate_tuple(context, exprs...); }, _exprs ); } };

Le premier argument est le type de foncteur qui sera instancié et appelé pour l'évaluation. Les autres types sont des types de retour d'expressions enfants.

Afin de réduire le code passe-partout, nous définissons trois macros :

 #define UNARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1> \ auto operator()(T1 t1) {\ code;\ }\ };\ template<typename R, typename T1>\ using name##_expression = generic_expression<name##_op, R, T1>; #define BINARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1, typename T2>\ auto operator()(T1 t1, T2 t2) {\ code;\ }\ };\ template<typename R, typename T1, typename T2>\ using name##_expression = generic_expression<name##_op, R, T1, T2>; #define TERNARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1, typename T2, typename T3>\ auto operator()(T1 t1, T2 t2, T3 t3) {\ code;\ }\ };\ template<typename R, typename T1, typename T2, typename T3>\ using name##_expression = generic_expression<name##_op, R, T1, T2, T3>;

Notez que operator() est défini comme un modèle, bien qu'il ne soit généralement pas nécessaire de l'être. Il est plus facile de définir toutes les expressions de la même manière au lieu de fournir des types d'arguments en tant qu'arguments de macro.

Maintenant, nous pouvons définir la majorité des expressions. Par exemple, voici la définition de /= :

 BINARY_EXPRESSION(div_assign, t1->value /= t2; return t1; );

Nous pouvons définir presque toutes les expressions en utilisant ces macros. Les exceptions sont les opérateurs qui ont défini l'ordre d'évaluation des arguments (opérateur logique && et || , ternaire ( ? ) et virgule ( , ) ), index de tableau, appel de fonction et param_expression , qui clone le paramètre pour le transmettre à la fonction par valeur.

Il n'y a rien de compliqué dans la mise en œuvre de ceux-ci. L'implémentation des appels de fonction est la plus complexe, je vais donc l'expliquer ici :

 template<typename R, typename T> class call_expression: public expression<R>{ private: expression<function>::ptr _fexpr; std::vector<expression<lvalue>::ptr> _exprs; public: call_expression( expression<function>::ptr fexpr, std::vector<expression<lvalue>::ptr> exprs ): _fexpr(std::move(fexpr)), _exprs(std::move(exprs)) { } R evaluate(runtime_context& context) const override { std::vector<variable_ptr> params; params.reserve(_exprs.size()); for (size_t i = 0; i < _exprs.size(); ++i) { params.push_back(_exprs[i]->evaluate(context)); } function f = _fexpr->evaluate(context); for (size_t i = params.size(); i > 0; --i) { context.push(std::move(params[i-1])); } context.call(); f(context); if constexpr (std::is_same<R, void>::value) { context.end_function(_exprs.size()); } else { return convert<R>( context.end_function( _exprs.size() )->template static_pointer_downcast<T>() ); } } };

Il prépare le runtime_context en poussant tous les arguments évalués sur sa pile et en appelant la fonction call . Il appelle ensuite le premier argument évalué (qui est la fonction elle-même) et renvoie la valeur de retour de la méthode end_function . Nous pouvons également voir l'utilisation de la syntaxe if constexpr ici. Cela nous évite d'écrire la spécialisation pour toute la classe pour les fonctions qui renvoient void .

Maintenant, nous avons tout ce qui concerne les expressions disponibles pendant l'exécution. La seule chose qui reste est la conversion de l'arborescence d'expressions analysées (décrite dans le billet de blog précédent) en arborescence d'expressions.

Générateur d'expressions

Pour éviter toute confusion, nommons différentes phases de notre cycle de développement du langage :

• Meta-compile-time : la phase d'exécution du compilateur C++
• Compilation : la phase où le compilateur Stork s'exécute
• Runtime : la phase d'exécution du script Stork

Voici le pseudo-code du générateur d'expression :

 function build_expression(nodeptr n, compiler_context context) { if (n is constant) { return constant_expression(n.value); } else if (n is identifier) { id_info info = context.find(n.value); if (context.is_global(info)) { return global_variable_expression(info.index); } else { return local_variable_expression(info.index); } } else { //operation switch (n->value) { case preinc: return preinc_expression( build_expression(n->child[0]) ); ... case add: return add_expression( build_expression(n->child[0]), build_expression(n->child[1]) ); ... case call: return call_expression( n->child[0], //function n->child[1], //arg0 ... n->child[k+1], //argk ); } } }

En plus de devoir gérer toutes les opérations, cela semble être un algorithme simple.

Si cela fonctionnait, ce serait formidable, mais ce n'est pas le cas. Pour commencer, nous devons spécifier le type de retour de la fonction, et ce n'est évidemment pas fixé ici, car le type de retour dépend du type de nœud que nous visitons. Les types de nœuds sont connus au moment de la compilation, mais les types de retour doivent être connus au moment de la méta-compilation.

Dans le post précédent, j'ai mentionné que je ne vois pas l'avantage des langages qui effectuent une vérification de type dynamique. Dans de tels langages, le pseudo-code présenté ci-dessus pourrait être implémenté presque littéralement. Maintenant, je suis tout à fait conscient des avantages des langages de type dynamique. Le karma instantané à son meilleur.

Heureusement, nous connaissons le type de l'expression de niveau supérieur - cela dépend du contexte de la compilation, mais nous connaissons son type sans analyser l'arborescence de l'expression. Par exemple, si nous avons la boucle for :

 for (expression1; expression2; expression3) ...

La première et la troisième expressions ont un type de retour void car nous ne faisons rien avec leur résultat d'évaluation. La deuxième expression, cependant, a un number de type car nous la comparons à zéro, afin de décider d'arrêter ou non la boucle.

Si nous connaissons le type de l'expression liée à l'opération de nœud, il déterminera généralement le type de son expression enfant.

Par exemple, si l'expression (expression1) += (expression2) a le type lnumber , cela signifie que expression1 a également ce type et expression2 a le type number .

Cependant, l'expression (expression1) < (expression2) a toujours le type number , mais leurs expressions enfants peuvent avoir le type number ou le type string . Dans le cas de cette expression, nous vérifierons si les deux nœuds sont des nombres. Si c'est le cas, nous construirons expression1 et expression2 comme expression<number> . Sinon, ils seront du type expression<string> .

Il y a un autre problème que nous devons prendre en compte et traiter.

Imaginez si nous devons construire une expression du type number . Ensuite, nous ne pouvons rien renvoyer de valide si nous rencontrons un opérateur de concaténation. Nous savons que cela ne peut pas arriver, car nous avons déjà vérifié les types lorsque nous avons construit l'arbre d'expression (dans la partie précédente), mais cela signifie que nous ne pouvons pas écrire la fonction modèle, paramétrée avec le type de retour, car elle aura des branches invalides selon sur ce type de retour.

Une approche diviserait la fonction par type de retour, en utilisant if constexpr , mais elle est inefficace car si la même opération existe dans plusieurs branches, nous devrons répéter son code. Nous pourrions écrire des fonctions séparées dans ce cas.

La solution implémentée divise la fonction en fonction du type de nœud. Dans chacune des branches, nous vérifierons si ce type de branche est convertible en type de retour de fonction. Si ce n'est pas le cas, nous lancerons l'erreur du compilateur, car cela ne devrait jamais arriver, mais le code est trop compliqué pour une revendication aussi forte. J'ai peut-être fait une erreur.

Nous utilisons la structure de traits de type explicite suivante pour vérifier la convertibilité :

 template<typename From, typename To> struct is_convertible { static const bool value = std::is_convertible<From, To>::value || is_boxed<From, To>::value || ( std::is_same<To, string>::value && ( std::is_same<From, number>::value || std::is_same<From, lnumber>::value ) ); };

Après cette scission, le code est presque simple. Nous pouvons transtyper sémantiquement du type d'expression d'origine vers celui que nous voulons construire, et il n'y a pas d'erreurs lors de la méta-compilation.

Cependant, il y a beaucoup de code passe-partout, donc je me suis fortement appuyé sur les macros pour le réduire.

 template<typename R> class expression_builder{ private: using expression_ptr = typename expression<R>::ptr; static expression_ptr build_void_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_number_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lnumber_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_string_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lstring_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_array_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_larray_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_function_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lfunction_expression( const node_ptr& np, compiler_context& context ); public: static expression_ptr build_expression( const node_ptr& np, compiler_context& context ) { return std::visit(overloaded{ [&](simple_type st){ switch (st) { case simple_type::number: if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lnumber); } else { RETURN_EXPRESSION_OF_TYPE(number); } case simple_type::string: if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lstring); } else { RETURN_EXPRESSION_OF_TYPE(string); } case simple_type::nothing: RETURN_EXPRESSION_OF_TYPE(void); } }, [&](const function_type& ft) { if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lfunction); } else { RETURN_EXPRESSION_OF_TYPE(function); } }, [&](const array_type& at) { if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(larray); } else { RETURN_EXPRESSION_OF_TYPE(array); } } }, *np->get_type_id()); } };

La fonction build_expression est la seule fonction publique ici. Il invoque la fonction std::visit sur le type de nœud. Cette fonction applique le foncteur passé sur le variant , le découplant dans le processus. Vous pouvez en savoir plus à ce sujet et sur le foncteur overloaded ici.

La macro RETURN_EXPRESSION_OF_TYPE appelle des fonctions privées pour la construction d'expressions et lève une exception si la conversion n'est pas possible :

 #define RETURN_EXPRESSION_OF_TYPE(T)\ if constexpr(is_convertible<T, R>::value) {\ return build_##T##_expression(np, context);\ } else {\ throw expression_builder_error();\ return expression_ptr();\ }

Nous devons retourner le pointeur vide dans la branche else, car le compilateur ne peut pas connaître le type de retour de la fonction en cas de conversion impossible ; sinon, std::visit exige que toutes les fonctions surchargées aient le même type de retour.

Il y a, par exemple, la fonction qui construit des expressions avec string comme type de retour :

 static expression_ptr build_string_expression( const node_ptr& np, compiler_context& context ) { if (std::holds_alternative<std::string>(np->get_value())) { return std::make_unique<constant_expression<R, string>>( std::make_shared<std::string>( std::get<std::string>(np->get_value()) ) ); } CHECK_IDENTIFIER(lstring); switch (std::get<node_operation>(np->get_value())) { CHECK_BINARY_OPERATION(concat, string, string); CHECK_BINARY_OPERATION(comma, void, string); CHECK_TERNARY_OPERATION(ternary, number, string, string); CHECK_INDEX_OPERATION(lstring); CHECK_CALL_OPERATION(lstring); default: throw expression_builder_error(); } }

Il vérifie si le nœud contient une constante de chaîne et construit constant_expression si c'est le cas.

Ensuite, il vérifie si le nœud contient un identifiant et renvoie une expression de variable globale ou locale de type lstring dans ce cas. Il peut contenir un identifiant si nous implémentons des variables constantes. Sinon, il suppose que le nœud détient l'opération de nœud et essaie toutes les opérations qui peuvent renvoyer string .

Voici les implémentations des macros CHECK_IDENTIFIER et CHECK_BINARY_OPERATION :

 #define CHECK_IDENTIFIER(T1)\ if (std::holds_alternative<identifier>(np->get_value())) {\ const identifier& id = std::get<identifier>(np->get_value());\ const identifier_info* info = context.find(id.name);\ if (info->is_global()) {\ return std::make_unique<\ global_variable_expression<R, T1>\ >(info->index());\ } else {\ return std::make_unique<\ local_variable_expression<R, T1>\ >(info->index());\ }\ }

 #define CHECK_BINARY_OPERATION(name, T1, T2)\ case node_operation::name:\ return expression_ptr(\ std::make_unique<name##_expression<R, T1, T2> > (\ expression_builder<T1>::build_expression(\ np->get_children()[0], context\ ),\ expression_builder<T2>::build_expression(\ np->get_children()[1], context\ )\ )\ );

La macro CHECK_IDENTIFIER doit consulter compiler_context pour construire une expression de variable globale ou locale avec l'index approprié. C'est la seule utilisation du compiler_context dans cette structure.

Vous pouvez voir que CHECK_BINARY_OPERATION appelle de manière récursive build_expression pour les nœuds enfants.

Emballer

Sur ma page GitHub, vous pouvez obtenir le code source complet, le compiler, puis saisir des expressions et voir le résultat des variables évaluées.

J'imagine que, dans toutes les branches de la créativité humaine, il y a un moment où l'auteur se rend compte que son produit est vivant, dans un certain sens. Dans la construction d'un langage de programmation, c'est le moment où l'on voit que le langage "respire".

Dans la prochaine et dernière partie de cette série, nous implémenterons le reste de l'ensemble minimal de fonctionnalités de langage pour le voir fonctionner en direct.