Le C++ expressif n° 2 : jouons avec la syntaxe

Bienvenue dans ce deuxième article consacré aux Domain-Specific Embedded Language (DSEL) en C++. Dans l'introduction nous avons vu les avantages des DSEL et évoqué les possibilités offertes par Boost.Proto. J'ai aussi montré des exemples de Boost.Spirit, un DSEL en C++ qui se rapproche de la syntaxe EBNF.

Vous pensez peut-être que tous les DSEL sont compliqués et pas vraiment pratiques. Je vous rassure, ça n'est pas le cas. Dans cet article, je vais passer en revue le design et l'implémentation d'un simple DSEL. À la fin, vous serez capable d'écrire un petit DSEL utile.

Voici un petit problème. Vous avez une API de formatage de chaîne de caractères à la Mad-Libs (1) qui prend une chaîne de caractères comme « There are more things in {place}, Horatio, than are dreamt of in your {thing}.\n » qui contient deux éléments et un std::map contenant les remplacements à faire.

// On déclare et initialise une std::map contenants les remplacements à faire
std::map<std::string, std::string> subst;
subst["place"] = "heaven and earth";
subst["thing"] = "philosophy";
 
// Affiche à l'écran: There are more things in heaven and earth, Horatio,
//         than are dreamt of in your philosophy.
std::cout << format( "There are more things in {place}, Horatio, "
                     "than are dreamt of in your {thing}.\n", subst );

Appeler cette API est ennuyant, car déclarer et remplir un std::map peut prendre plusieurs lignes à coder. Sachant que la paresse est l'une des caractéristiques des développeurs géniaux (2), ils voudront naturellement changer ça pour tout coder sur une ligne. C'est facile et en plus, nous allons le faire !

Nous arrivons à la partie la plus amusante : décider de la syntaxe de notre futur mini langage. La première étape est de comprendre un point important sur l'écriture d'un DSEL : votre langage doit être composé d'expressions valides en C++. Nous ne pouvons utiliser que les identificateurs, les opérateurs et les fonctions que le C++ fournit. Et votre langage doit obéir aux règles de priorités et d'associativités du C++. Par exemple, ce morceau de code est joli, mais il n'est pas valide en C++ :

// ATTENTION : n'est pas valide en C++
format( "There are...", {"place": "heaven and earth",
                         "thing": "philosophy"} );

En revanche, ces expressions-là sont valides :

// OK, valide en C++
format( "There are...", map("place", "heaven and earth")
                           ("thing", "philosophy") );
 
format( "There are...", map["place"]("heaven and earth")
                           ["thing"]("philosophy") );
 
format( "There are...", map["place"] = "heaven and earth" +
                        map["thing"] = "philosophy" );
 
format( "There are...", (map["place"] = "heaven and earth",
                         map["thing"] = "philosophy") );

Attention ! Soyez conscient que dans votre DSEL, vous ne pouvez pas assigner une nouvelle expression à une expression qui signifie déjà quelque chose ! Prenons par exemple :

map("place" == "heaven and earth")
   ("thing" == "philosophy")

En C++, appliquer l'opérateur d'égalité sur deux chaînes de caractères compare les deux pointeurs. Aïe. Quand vous allez construire votre DSEL, faites attention à ne pas vous placer dans ce genre de situation.

Remarquez que dans chaque cas, on a utilisé des expressions qui obéissent aux règles syntaxiques du C++. Prenez un moment pour réfléchir aux surcharges d'opérateurs nécessaires pour que ce code compile. Par exemple, la première expression a besoin d'une surcharge d'opérateur au niveau de l'objet map qui prend deux arguments et retourne lui-même un objet surchargé sur l'opérateur d'appel de fonction, etc.

La dernière surcharge avec l'opérateur virgule , est intéressante. Remarquez que j'entoure l'expression de parenthèses. Notons quand même que la virgule en C++ sert aussi bien d'opérateur que de séparateur d'argument, ce qui la rend difficile à travailler avec les DSEL.

L'une de ces expressions est différente des autres. Pensez à la priorité des opérateurs. Pouvez-vous repérer l'intrus ?

Vous êtes peut-être en train de penser « comment vais-je réussir à compiler ça ? ». En réalité c'est la partie la plus facile et c'est là où Proto est efficace. En ajoutant quelques lignes de code, nous pouvons rendre notre exemple du dessus compilable, même s'il n'affiche rien :

#include <string>
#include <boost/proto/proto.hpp>
 
struct map_ {};
boost::proto::terminal<map_>::type map = {};
 
template< class Expr >
void format( std::string fmt, Expr const & expr )
{}
 
int main()
{
    // OK, C++ valide
    format( "There are...", map("place", "heaven and earth")
                               ("thing", "philosophy") );
 
    format( "There are...", map["place"]("heaven and earth")
                               ["thing"]("philosophy") );
 
    format( "There are...", map["place"] = "heaven and earth" +
                            map["thing"] = "philosophy" );
 
    format( "There are...", (map["place"] = "heaven and earth",
                             map["thing"] = "philosophy") );
}

Nous avons inclus un fichier d'en-tête, défini un symbole et c'est tout. Proto définit déjà des surcharges d'opérateurs qui font que n'importe quelle expression, comme le terminal map de l'exemple ci-dessus, peut être combinée avec des arbres d'expressions plus grands.

Arbres hétérogènes
Les constructions d'arbres d'expressions de Proto ne sont pas des choses communes pour un développeur Java ou un partisan de l'orienté objet. Il n'y a aucune allocation dynamique, pas de classes abstraites et pas de fonctions membres virtuelles. C'est un arbre hétérogène ; chaque nœud possède des informations sur comment il a été créé et quels sont les types de ses enfants. Cet arbre est construit sans aucune copie, ce qui le rend souple à l'exécution (si l'optimisation fait bien son travail évidemment).

Regardons plus attentivement deux des quatre expressions du dessus, ainsi que les structures créées par Proto. Nous avons ici les arbres des deux dernières expressions, celle avec l'opérateur virgule et celle avec l'opérateur plus :

Regardez la différence entre les deux opérateurs ! L'expression avec la virgule donne un arbre très explicite où chaque clé est directement associée à sa valeur. Plus tard, cela rendra l'arbre plus facile à interpréter comme une map. L'expression avec l'opérateur plus a une structure totalement différente, la clé "place" n'est pas du tout à côté de sa valeur "heaven and earth". Le fait qu'il n'y ait pas de relation simple entre chaque nœud, qui associe une clé et une valeur, rend l'interprétation de cet arbre comme une map très difficile.

La raison de la différence est la priorité de l'opérateur plus. Il possède une plus grosse priorité que l'opérateur égal, ainsi (a = b + c = d) se lit aussi (a = (b + c) = d). L'opérateur virgule a une priorité très basse, ainsi (a = b, c = d) se lit ((a = b), (c = d)). Cela ressemble plus à ce qu'on voudrait. En effet, les règles du C++ sont fixées et immuables ; si vous les ignorez, c'est à vos risques et périls.

Boost.Proto fournit un outil pratique pour explorer la structure des expressions. Passez seulement votre expression à display_expr pour obtenir une vue d'ensemble de la structure. Par exemple, ce code :

proto::display_expr( (map["place"]="heaven and earth", map["thing"]="philosophy") );

écrira sur la sortie std::cout (3) :

comma(
    assign(
        subscript(
            terminal(struct map_)
          , terminal(place)
        )
      , terminal(heaven and earth)
    )
  , assign(
        subscript(
            terminal(struct map_)
          , terminal(thing)
        )
      , terminal(philosophy)
    )
)

Boost.Proto rend l'exploration de votre DSEL vraiment très facile. Essayez et amusez-vous sans retenue avec ça.

Maintenant que nous avons exploré les différentes possibilités, il est temps de choisir une syntaxe pour notre petit langage. Puisque le but de notre exercice est d'écrire le moins possible sur notre clavier, nous allons regarder la syntaxe la plus concise :

format( "There are...", map("place", "heaven and earth")
                           ("thing", "philosophy") );

Si nous passons l'expression map à proto::display_expr, nous verrons quelque chose comme cela :

function(
    function(
        terminal(struct map_)
      , terminal(place)
      , terminal(heaven and earth)
    )
  , terminal(thing)
  , terminal(philosophy)
)

C'est vraiment un arbre très simple, il n'y a que deux nœuds non terminaux et ce sont tous les deux des appels de fonction. Ces nœuds ont chacun trois nœuds enfants : la « fonction », la clé et la valeur. Dans ce cas, la « fonction » est soit l'élément terminal « map » ou une autre fonction, rendant cette structure de données récursive.

Un moyen de traiter une structure de données récursive est d'utiliser des fonctions récursives. Nous pouvons facilement parcourir cet arbre et remplir un std::map au fur et à mesure. C'est ce que font les deux fonctions suivantes. Les explications sont dessous :

typedef std::map<std::string, std::string> string_map;
 
// Fonction récursive utilisée pour remplir la map
template< class Expr >
void fill_map( Expr const & expr, string_map & subs )
{
    using boost::proto::value;      // on lit la valeur d'un élément terminal
    using boost::proto::child_c;    // on récupère le énième enfant d'un élément non terminal
    subs[ value(child_c<1>(expr)) ] = value(child_c<2>(expr));
    fill_map( child_c<0>(expr), subs );
}
 
// L'élément terminal map termine la récursion
void fill_map( boost::proto::terminal<map_>::type const &, string_map & )
{}

Parcours d'arbre
Pour des arbres simples, écrire ses propres fonctions récursives pour les traiter n'est pas si difficile. Cependant, pour les arbres avec des structures plus riches, cette approche devient rapidement irréalisable. Pour parler en terme de construction de compilateur, ça serait comme si yacc construisait un l'arbre d'expression (Abstract Syntax Tree, AST), mais ne le parcourait pas, vous laissant effectuer cette tâche et générer le code par vous-même. Rassurez-vous, Proto offre un moyen bien plus puissant pour parcourir et manipuler des arbres, nous en parlerons dans les prochains articles.

Nous allons utiliser fill_map en lui passant l'arbre d'expression et un std::map à remplir. Il fonctionne en épluchant une couche de l'arbre à la fois, utilisant ainsi les deux éléments terminaux de chaque couche pour insérer une nouvelle paire clé/valeur dans la map.

fill_map présente deux accesseurs de Proto : value et child_c. value est utilisé pour accéder à la valeur dans un élément terminal. child_c récupère le N^e enfant d'un élément non terminal.

Maintenant que nous pouvons parcourir un arbre et construire un std::map, le reste c'est de la tarte. Nous offrons simplement une nouvelle API format qui transmet à l'ancienne et voilà ! C'est fini. La solution complète ressemble à ça :

////////////////////////////////////////////////////////////////////////////
//
// Un simple DSEL pour créer des associations comme une map
//
////////////////////////////////////////////////////////////////////////////
 
#include <map>
#include <string>
#include <iostream>
#include <boost/proto/proto.hpp>
#include <boost/xpressive/xpressive.hpp>
#include <boost/xpressive/regex_actions.hpp>
 
struct map_ {};
boost::proto::terminal<map_>::type map = {};
 
typedef std::map<std::string, std::string> string_map;
 
// Fonction récursive utilisée pour remplir la map
template< class Expr >
void fill_map( Expr const & expr, string_map & subs )
{
    using boost::proto::value;      // lit une valeur d'un élément terminal
    using boost::proto::child_c;    // récupère le énième enfant d'un élément non terminal
    subs[ value(child_c<1>( expr )) ] = value(child_c<2>(expr));
    fill_map( child_c<0>(expr), subs );
}
 
// L'élément terminal map termine la récursion
void fill_map( boost::proto::terminal<map_>::type const &, string_map & )
{}
 
// La veille fonction format qui accepte une map d'éléments à remplacer
std::string format( std::string fmt, string_map & subs )
{
    namespace xp = boost::xpressive;
    using namespace xp;
    sregex const rx = '{' >> (s1= +_w) >> '}';        // comme {(\\w+)}
    return regex_replace(fmt, rx, xp::ref(subs)[s1]);
}
 
// La nouvelle fonction format qui redirige vers l'ancienne
template< class Expr >
std::string format( std::string fmt, Expr const & expr )
{
    string_map subs;
    fill_map( expr, subs );
    return format( fmt, subs );
}
 
int main()
{
    std::cout << format("There are more things in {place}, Horatio, "
                        "than are dreamt of in your {thing}.\n"
                      , map("place", "heaven and earth")
                           ("thing", "philosophy") );
}

Comme prévu, ce code affiche :

There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy.

J'ai glissé quelques codes en plus pour voir si vous étiez attentif. C'est Boost.Xpressive, une bibliothèque de manipulation d'expressions régulières et de chaînes de caractères. La première fonction surchargée de format construit une expression régulière :

sregex const rx = '{' >> (s1= +_w) >> '}';  // comme {(\\w+)}

La ligne suivante transmet l'expression régulière à regex_replace pour effectuer la substitution :

return regex_replace(fmt, rx, xp::ref(subs)[s1]);

Le troisième paramètre est une sorte de fonction de substitution anonyme. Il dit : prend la partie de la chaîne de caractères qui correspond à +_w (un mot entier), utilise-le pour l'indexer dans la map subs et utiliser le résultat comme élément de remplacement. xp::ref est nécessaire pour retarder l'évaluation de l'index jusqu'à ce que la correspondance soit trouvée. L'expression régulière et la fonction anonyme viennent de deux DSEL différents, mais vous remarquerez comment ils arrivent à collaborer ensemble à travers l'utilisation partagée de l'élément s1. Ce genre de création de DSEL est l'une des plus puissantes et excitantes caractéristiques des DSEL.

En comptant le DSEL que nous venons de définir, ce code source utilise un total de trois DSEL. Tous ont été construits avec Proto.

Dans cet article, on construit un petit DSEL pour exprimer des relations comme des maps. Avec l'aide de Proto, c'est assez facile. En effet, on pourrait dire que le terme « DSEL » ne s'applique même pas à une interface de bibliothèque aussi simple. C'est vrai : la limite entre les DSEL et les interfaces de bibliothèques bien réfléchies est floue. Mais même pour le cas le plus extrême comme celui-là, Proto possède une collection d'outils pour rendre le travail plus facile.

Dans le prochain article, nous allons renforcer les spécifications de cette interface de bibliothèque, ajouter quelques paramètres pour vérifier et utiliser quelques techniques astucieuses pour améliorer le report d'erreurs des templates.

À la prochaine !

Merci à Eric Niebler de nous avoir autorisés à traduire Expressive C++: Playing with Syntax.

Merci à Flob90 pour sa relecture et à _Max_ pour sa relecture orthographique.