Le C++ expressif n° 1 : introduction

Dissimulé dans C++ se cache un autre langage - d'innombrables autres langages, en fait - tous sont meilleurs que le C++ pour résoudre certains types de problèmes. Ces domain-specific languages (abrégé DSL) sont par exemple des langages pour l'algèbre linéaire ou des langages de requêtes, ils ne peuvent faire qu'une seule chose, mais ils le font bien. On peut créer et utiliser ces langages directement dans le C++, en utilisant la puissance et la flexibilité du C++ pour remplacer les parties communes du langage par les parties spécifiques au domaine que nous utilisons. Dans cette série d'articles, nous allons regarder de près les domain-specific languages, dans quels domaines sont-ils utiles et comment peut-on facilement les implémenter en C++ avec l'aide de Boost.Proto.

Retour en 1958, John Backus travaillait sur un problème fastidieux, comment précisément établir la syntaxe du langage ALGOL. Il en est arrivé à un système qui décrit la syntaxe de n'importe quel langage informatique. Ce système, qui a beaucoup évolué au fil des années, est connu sous le nom d'EBNF et il se présente sous diverses formes partout où un langage informatique a besoin d'être défini : spécifications officielles, outils à la construction d'un compilateur, etc.

L'omniprésence d'EBNF est une preuve de sa puissance simple et élégante. Avec juste quelques lignes, on peut, par exemple, décrire la syntaxe, les priorités et l'associativité entre les opérateurs arithmétiques infixes :

expression = terme ( ( ?+' terme ) | ( ?-' terme ) )* ;
 
terme = facteur ( ( ?*' facteur ) | ( ?/' facteur ) )* ;
 
facteur = UINT | ?(? expression ?)' | ?-' facteur ;

L'EBNF est un excellent exemple de domain-specific language ; c'est exactement l'outil qu'il faut pour ceux qui s'occupent de l'analyse grammaticale et l'analyse syntaxique, mais c'est aussi très utile pour tous les autres. Le fait que ça soit hautement spécialisé fait partie son charme. Il vous permet de vous consacrer pleinement à ce que vous voulez mettre en place, sans être distrait par des choses sans importance. Mais il y a un inconvénient, si vous avez besoin de faire quelque chose qui ne relève pas du domaine de compétence d'EBNF, alors EBNF est inutile. C'est la bête noire de tous les DSL, vous avez souvent besoin d'une petite porte pour vous échapper des limites de votre domaine.

En revanche, le C++ est un langage de programmation polyvalent. Tout ce qui peut être fait, peut être fait avec le C++. Mais la puissance et la flexibilité ont un coût : il y a beaucoup de choses pour lesquelles le C++ n'est pas particulièrement à l'aise. La construction des compilateurs me vient à l'esprit, le C++ ne supporte pas directement des choses comme EBNF. Néanmoins, le C++ est très bon pour concevoir des bibliothèques. La responsabilité appartient aux développeurs de bibliothèques pour fournir les meilleures utilisations possible du C++. Et en plaçant les connaissances spécifiques à un domaine dans une bibliothèque C++, les utilisateurs ne tombent pas des nues quand ils ont besoin de faire quelque chose en dehors des compétences de la bibliothèque, ils peuvent toujours retourner au bon vieux C++ !

Mais quel est le meilleur moyen pour fournir une bibliothèque C++ avec une notation appropriée et des concepts avec lesquelles les utilisateurs sont familiers ? Les développeurs de bibliothèques C++ « moderne » sont arrivés avec une solution originale : utiliser les opérateurs fournis par le C++ pour se rapprocher des notations spécifiques à un domaine. Puisqu'ils ressemblent à des petits langages construits de parties d'un plus gros langage, ces bibliothèques sont appelées domain-specific embedded languages que nous abrégerons par DSEL. Si c'est bien fait, les résultats peuvent être impressionnants.

Prenons, par exemple, la bibliothèque Boost.Spirit, une bibliothèque de décomposition analytique(1) qui donne à l'utilisateur un langage semblable à EBNF pour définir la grammaire. Voici l'équivalent avec Spirit de la grammaire EBNF vu plus haut :

/////////////////////////////////////////////////////////////////////
//  Une grammaire Spirit qui reconnait les expressions de calcul infixes
/////////////////////////////////////////////////////////////////////
 
// boost::spirit::qi fournit le générateur d'analyse
boost::spirit::qi::rule<Iterator> expression, term, factor;
 
// Une expression est un terme suivi d'un ou plusieurs zéros
// les autres termes sont séparés par des ?+' ou ?-'
/* L'équivalent EBNF est :
expression = terme     ( ( '+'    terme ) | ( '-'    terme ) )* ; */
expression = term >> *( ( '+' >> term ) | ( '-' >> term ) )  ;
 
// Un terme est un facteur suivi d'un ou plusieurs zéros.
// Les autres facteurs sont séparés par ?*' ou ?/'
/* L'équivalent EBNF est :
terme = facteur     ( ( '*'    facteur) | ( '/'    facteur ) )* ; */
term = factor >> *( ( '*' >> factor ) | ( '/' >> factor ) )  ;
 
// Un facteur est un entier non signé ou
// une expression entre parenthèses ou
// un facteur négatif
using boost::spirit::qi::uint_;
/* L'équivalent EBNF est
facteur = UINT  | '('    expression    ')' | '-'    facteur ; */
factor = uint_ | '(' >> expression >> ')' | '-' >> factor ;

Si vous louchez un peu des yeux, vous pourrez voir à quel point la grammaire Spirit correspond à la grammaire EBNF même si cela n'est pas parfait.

Une « règle » (rule) dans Spirit est l'équivalent C++ d'une règle de grammaire en EBNF ; les opérateurs >> et | et * ont tous été surchargés et sont utilisés par Spirit pour respectivement définir les séquences de grammaire, l'alternance et la répétition. Comment ça fonctionne ? Un moyen clair pour Spirit pourrait être d'utiliser l'opérateur de décalage de bits à droite >> pour « décaler à droite » et retourner un objet « règle ». À la place Spirit utilise l'opérateur de décalage de bits à droite pour retourner quelques objets temporaires qui tiennent simplement sur les opérandes gauches et droites. Il en est de même pour tous les autres opérateurs. Le résultat est une expression comme :

factor >> *( ( '*' >> factor ) | ( '/' >> factor ) )

Ce code « capture » l'expression entière - types, structures, valeurs, etc. - dans un arbre d'expression. Quand cet arbre est assigné à un objet « règle », Spirit parcourt l'arbre et l'interprète comme une règle de grammaire. Quand tout est parcouru, on peut utiliser la variable expression ci-dessus comme un analyseur afin de valider des expressions arithmétiques infixes. Pas mal !

C'est l'approche générale par les DSEL : utiliser la surcharge d'opérateur pour construire des arbres qui capturent l'expression. Après avoir capturé une expression, on peut maintenant la travailler plus en profondeur. À ce moment, un arbre peut être analysé, optimisé, transformé et évalué de manières spécifiques au domaine utilisé.

Spirit est un ensemble d'outils de construction de compilateur comme yacc . En plus de la grammaire EBNF, il fournit d'autres abstractions comme :

• un arbre syntaxique abstrait (2)  : un arbre de représentation standard d'un programme analysé ;
• les actions sémantiques (3)  : des morceaux de code exécutable que vous pouvez attacher aux règles de grammaire qui font faire des choses à votre analyseur ;
• et une multitude d'algorithmes de compilation qui opèrent sur les AST.

… tous peuvent être exprimés directement dans votre programme C++ comme des expressions. Ces abstractions basiques - grammaires, AST, actions sémantiques et algorithmes de compilation - deviendront importantes plus tard dans un contexte différent que nous verrons.

C'est l'essence même de celui-ci : en installant des choses qui permettent aux concepts du domaine d'être exprimés directement et brièvement avec des expressions C++ (cf. Spirit et EBNF plus haut), on peut rendre les utilisateurs de notre bibliothèque plus à l'aise et donc plus productifs.

Qui plus est, on peut souvent le faire tout en réalisant de grands gains de performances. Avec un accès complet à l'arbre d'expression, une bibliothèque dédiée peut analyser l'arbre et déterminer des stratégies optimales d'évaluation. Un bon exemple est Blitz++, une bibliothèque de calculs matriciels qui a battu les performances du langage FORTRAN, quelque chose qu'on ne pensait pas possible à l'époque. Il réalise ses performances remarquables en analysant un arbre d'expression complet et en appliquant des transformations complexes et spécifiques comme la fusion de boucles(4). C'est uniquement possible, car Blitz++ a accès à l'arbre expression complet pour effectuer ses optimisations.

Le terme est « domain-specific embedded language », mais vous êtes pardonnés si vous pensez que Spirit est une simple « bibliothèque ». Imaginez ce qui pourrait changer si nous avions tous cru de tout notre cœur que les DSEL étaient réellement des langages. Suivons cette logique : les bibliothèques qui implémentent les DSEL seraient des compilateurs et écrire une telle bibliothèque serait comme écrire un compilateur. Et comme nous avons vu, écrire des compilateurs est une tâche assez commune avec des outils comme yacc ou Spirit pour rendre le travail plus facile. Il s'ensuit qu'il devrait y avoir un outil pour les développeurs de DSEL, qui fournit des abstractions pour les codeurs : grammaires, AST, actions sémantiques et des algorithmes de compilation. Ce dont nous avons besoin est un ensemble d'outils de construction de compilateurs pour les DSEL. Boost.Proto est cet ensemble d'outils.

Une analogie avec Spirit est pertinente puisque Spirit et Proto font à peu près la même chose, mais à des moments différents. Spirit génère des programmes qui décomposent du texte à l'exécution. Proto génère des programmes qui analysent des arbres d'expression C++ à la compilation(5). Pour résumer, un banal compilateur devrait être implémenté avec Spirit. Et Spirit devrait être implémenté avec un outil comme Proto.

Je n'ai pas parlé de la façon dont les bibliothèques sont typiquement implémentées aujourd'hui. Ça implique un bon morceau de métaprogrammation par template qui est une tâche assez difficile. Proto nous laisse écrire la bibliothèque Spirit en fonction de grammaire semblable à EBNF et d'actions sémantiques, ça ne ressemble plus à l'impénétrable et fragile code spaghetti qui est souvent associé à la métaprogrammation avec des patrons. Ce serait un grand pas en avant :

• les DSEL seraient plus faciles à développer et maintenir ;
• les DSEL seraient définis plus rigoureusement et robustement, amenant des interfaces plus conviviales et des meilleurs messages d'erreurs ;
• et le plus important, les transformations de code qui étaient excessivement complexes avant seraient maintenant réalisables.

Le potentiel pour les transformations de codes complexes ouvre des possibilités infinies. Arrivez-vous à voir les possibilités ? Avec de tels outils, on peut extraire des expressions, analyser des parties et tout réassembler pour faire des fusions des boucles pour le calcul matriciel à la manière de Blitz++, ou définir notre propre syntaxe pour des transactions, ou interpréter une expression comme un langage de requête, etc.

Boost.Proto est présent dans Boost depuis la version 1.37. Puisque c'est un outil de construction de compilateurs dans la tradition de yacc et Spirit, Proto peut construire un AST pour vous. Avec Proto, c'est aussi simple que ça :

#include <iostream>
#include <boost/proto/proto.hpp>
namespace proto = boost::proto;
 
int main()
{
   // Créons un terminal Proto qui entoure une chaine de caractère
   // Soyons culotté et appelons le « cout »
   proto::terminal< char const * >::type cout = { "cout" };
 
   // Créons un arbre d'expression et passons-le à display_expr
   // pour l'afficher joliment.
   proto::display_expr(
       cout << "hello" << ' ' << "proto!"
   );
}

L'argument de proto::display_expr n'est pas une expression de sortie, bien que nous n'ayons pas fait exprès d'y ressembler ; à la place, l'expression construit un arbre qui représente l'expression. Qu'est-ce que ça signifie pour les chaînes de caractères et les caractères ? Cela n'a pas d'importance. C'est juste un arbre qui sera évalué plus tard, peu importe la manière ou la quantité. L'opérateur ‹‹ dans l'expression est fourni par Proto, ainsi que tous les autres opérateurs. Construire un AST avec Proto est simple. Vous n'avez pas à définir un patron ou implémenter une surcharge d'opérateur.

Le résultat du programme ci-dessus est :

shift_left(
   shift_left(
       shift_left(
           terminal(cout)
         , terminal(hello)
       )
     , terminal( )
   )
 , terminal(proto!)
)

Vous pouvez clairement voir que Proto construit un arbre pour nous dont la structure correspond aux priorités et à l'associativité des opérateurs C++.

Comme vous pouvez le supposer, Proto arrive avec des outils pour définir des grammaires qui correspondent aux expressions et des actions sémantiques que vous pouvez associer aux règles de grammaire qui insuffleront la vie à vos DSEL. J'ai tellement de choses à dire, mais je vais garder le reste pour plus tard. Dans les futurs articles, je vais décrire Proto plus en détail, construire de simples, mais utiles DSEL tout en travaillant lentement vers un objectif : le design d'un autre DSEL - qui sortira bientôt - appelé Boost.Phoenix, une bibliothèque qui brouille la ligne entre le code C++ et les données, promettant d'apporter la puissance des macros de Lisp aux programmeurs C++. Quand cette série sera terminée, vous serez comme Néo dans la Matrice, voyant votre propre code comme des données que vous pourrez plier à votre volonté.

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

Merci à JolyLoic, à 3DArchi, à Joel F, à Jean-Marc.Bourguet, à gl, à Alp et à Aleph69 pour leur relecture, à Mahefasoa pour sa relecture orthographique.