Le C++ expressif n° 5 : une bibliothèque de fonctions lambda en à peine 30 lignes

La semaine dernière nous avons écrit les quelques prémisses de notre bibliothèque de lambda. Comme nous allons y faire référence, je vais recopier ici l'exemple complet :

#include <cassert>
#include <boost/proto/proto.hpp>
using namespace boost;

struct arg1_tag {};
proto::terminal<arg1_tag>::type const arg1 = {};

// Un "algorithme" Proto : une grammaire avec des transformées intégrées
// pour l'évaluation d'expressions lambda (explications dans l'article précédent).
struct Lambda
  : proto::or_<
        // Si on évalue un placeholder terminal, on retourne l'état.
        proto::when< proto::terminal<arg1_tag>, proto::_state >
        // Sinon, on choisit l'action par "défaut".
      , proto::otherwise< proto::_default< Lambda > >
    >
{};

int main()
{
    // Évalue la lambda arg1 + 42, ce qui replace arg1 par 1.
    int i = Lambda()( arg1 + 42, 1 );
    assert( i == 43 );
}

Avec ce simple programme, nous pouvons évaluer des arbres d'expressions de n'importe quelle complexité faisant intervenir le placeholder arg1. Pas si mal pour un programme aussi petit.

Mais en tant que bibliothèque de lambda, cette solution laisse quand même à désirer. Le plus gros problème est que l'expression arg1+42 n'est qu'un arbre tout bête sans signification particulière ; il attend seulement d'être passé à l'algorithme Lambda pour y être évalué. Ce serait bien mieux si l'on pouvait évaluer l'arbre d'expressions en passant des arguments directement à la lambda, tel que (arg1 + 42)(1). De cette manière on pourrait passer (arg1+42) à des algorithmes comme std::transform. Nous verrons comment dans une minute ; avant cela, je dois éclaircir certains points.

J'ai largement usé et abusé de ce mot « expression » qui peut prendre plusieurs significations, et il est important de clarifier les choses, aussi permettez-moi de faire ici une brève digression. La première chose à considérer pour une expression C++ est sa conformité syntaxique. 1 << 8 est une expression C++, au sens où un compilateur C++ peut l'interpréter. Ici, << est juste un opérateur binaire dont l'associativité et la priorité sont connues.

Les choses deviennent plus intéressantes quand on se penche sur la sémantique. Que signifie << ? Il prend l'opérande de gauche, sur lequel il effectue un décalage binaire vers la gauche suivant la quantité exprimée par l'opérande de droite, c'est bien cela ? Curieusement, personne ne pense à s'interroger sur ce que signifie un décalage binaire vers la gauche de std::cout par la quantité "hello world". Dans le contexte d'opérations sur un flux sortant, << change complètement de signification. (À ce jour, certains ont encore du mal à l'admettre. Ceux-ci devraient ignorer ce qui suit.)

Y a-t-il d'autres manières d'envisager les expressions ? Considérons le système de types et le modèle objet du C++. Une expression C++ possède un type et une valeur qui peuvent être complètement indépendants de sa syntaxe et de sa sémantique. std::cout << "hello world" possède un type std::ostream & et une valeur std::cout. Ceci est bien indépendant du fait qu'il écrive « hello world » dans un flux sortant.

Plus ? Qu'en est-il des aspects conceptuels ? Si cont est un conteneur de la STL, alors nous savons (A) que cont.begin() s'interprète comme du C++ valide, (B) que cela signifie « obtenir l'itérateur de début », et (C) qu'il a assurément un type et une valeur ; mais nous savons également que son type répond à des concepts tels que ForwardIterator ou RandomAccessIterator. En résumé, les expressions ne sont pas aussi simples que l'on pourrait le penser !

Quel rapport avec la conception d'un DSEL ? Les auteurs et utilisateurs d'un DSEL en C++ doivent être capables de naviguer entre ces différents aspects lorsqu'ils lisent ou écrivent un code spécifique à un domaine. arg1 + 42 s'interprète comme du C++, possède un type et une valeur (un arbre représentant l'expression), et son type modélise un concept appelé ProtoExpression. Donc en disant que arg1 + 42 est une « expression Proto », je sous-entends tout ce qui précède.

Il n'y a pas grand-chose à dire sur la sémantique des expressions Proto, si ce n'est leur tendance à s'agglutiner pour former des expressions Proto de plus en plus grandes. En particulier, arg1 + 42, seule, ne possède pas encore une sémantique « lambda » ; il faut la passer à l'algorithme Lambda qui l'interprète comme une expression lambda. Il serait souhaitable de définir un concept LambdaExpression qui affine celui de ProtoExpression en ajoutant operator(), et que arg1 + 42 modélise ce nouveau concept. Désormais, quand je dirai « expression lambda », toutes ces informations — syntaxe, sémantique, types, valeurs, concepts — seront aussi du voyage.

Il existe une relation simple entre les expressions que j'ai citées : une expression lambda est une sorte d'expression Proto, qui est une sorte d'expression C++. Ces relations sont illustrées dans la Figure 1. Au niveau le plus basique — la syntaxe —, elles sont toutes semblables. À des niveaux plus évolués, elles divergent, et c'est à l'utilisateur du DSEL qu'il incombe d'y mettre de l'ordre. Pas besoin de compliquer les choses ; après tout, à quand remonte la dernière fois où vous avez regardé std::cout << "hello world" en vous demandant ce que cela signifiait ?

Comme il est précisé ci-dessus, arg1 + 42 est une expression Proto. Mais nous sommes en train de construire une bibliothèque de lambda, bon sang — au diable les expressions Proto, on veut des expressions lambda ! Comment crée-t-on un type qui modélise le concept LambdaExpression ? On peut facilement ajouter un operator() à arg1 de manière à ce que arg1(1) retourne 1. Mais personne n'est au courant pour notre operator(), donc, en ce qui le concerne, Proto considère toujours arg1 comme une simple ProtoExpression. Pire encore, arg1 + 42 est elle aussi une simple ProtoExpression, mais sans notre membre operator() spécial. Proto l'en a tout bonnement amputé !

Il doit exister un moyen de « sous-classer » des expressions Proto pour créer des expressions lambda de manière à ce qu'elles se combinent en lambda de plus grande taille au lieu de dégénérer en expressions Proto trop peu commodes. Dans Proto, le procédé de sous-classement d'expressions Proto est appelé « extension d'expression », et implique de renseigner quelque peu Proto quant à votre domaine.

Dans Proto, vous pouvez étendre des expressions en définissant un domaine et en attribuant des propriétés (comme des fonctions membres supplémentaires) à des expressions au sein de ce domaine. Qu'est-ce qu'un domaine ? Vu depuis un DSL, un domaine est une sorte de portée intellectuelle ; les problèmes au sein d'un domaine ont tendance à partager des caractéristiques, de même pour leurs solutions. L'algèbre linéaire est un domaine ; la manipulation de texte est un domaine ; etc. Un domaine Proto est similaire : les expressions Proto partageant un domaine Proto ont les mêmes propriétés, telles que des fonctions membres supplémentaires.

Un domaine Proto est juste un type C++. À la manière d'une classe de trait, un domaine Proto vous renseigne sur un DSEL. Toutes les expressions Proto ont un domaine Proto associé, qui décrit ce qui rend les expressions spéciales dans ce domaine. Vous pouvez l'obtenir grâce à proto::domain_of, mais vous en aurez rarement besoin. Il serait en effet étrange de dire, « des types d'expressions sont associés à des types de domaine », on se contente de dire « des expressions sont dans des domaines ».

Le rôle le plus important d'un domaine Proto est de faire savoir à Proto comment créer de nouvelles expressions dans ce domaine. Par défaut, les expressions se trouvent dans proto::default_domain, et Proto n'a pas d'action particulière à entreprendre lors de la création de nouvelles expressions. Mais si vous assignez un domaine personnalisé à une expression (nous verrons comment dans une minute), alors vous pouvez dire à Proto de wrapper toutes les nouvelles expressions avec un adaptateur d'expression personnalisé, dans lequel peuvent être ajoutés des comportements supplémentaires - tels que la fonction membre operator(), par exemple.

Les wrappers d'expressions spécifiques à un domaine sont désignés en tant que classes d'extension d'expression. On peut renseigner Proto sur ceux-ci via un domaine muni d'un type que l'on appelle générateur, décrit ci-dessous.

En résumé, nous avons :

Domaine

• Un type associé avec une expression Proto. Un domaine Proto est une classe de trait avec un certain nombre de types associés qui renseignent Proto sur le DSEL. Les plus grandes expressions partagent le domaine des plus petites qui les composent. L'un des types associés à un domaine Proto est un générateur.

Générateur

• Un objet-fonction qui accepte un objet d'expression Proto et retourne un nouvel objet -- une lambda, peut-être -- qui étend l'expression. En général, cela consiste seulement à l'encapsuler dans un wrapper personnalisé.

Extensions d'expression

• Les wrappers personnalisés sont appelés extensions d'expression, et c'est là que se situe tout ce qui a trait à un domaine, tel que les fonctions membres personnalisées.

Il y a une relation circulaire entre ces trois concepts : par exemple, les expressions lambda sont dans un domaine lambda, lequel possède un générateur lambda associé, lequel crée des expressions lambda, fermant ainsi la boucle. Les relations entre expressions, domaines et générateurs sont représentées dans la Figure 2 ci-dessus.

Le code rendra cela un peu plus concret.

Dans le code ci-dessous, vous verrez comment les trois concepts décrits au-dessus — domaines, générateurs et extensions d'expression — interagissent pour créer une expression lambda. D'abord, nous définissons lambda_domain :

// Déclaration anticipée de notre adaptateur d'expression personnalisé.
template<typename ProtoExpression> struct lambda_expr;

// Définition d'un domaine lambda et de son générateur, ce qui encapsule 
// simplement toute nouvelle expression dans notre adaptateur personnalisé.
struct lambda_domain
  : proto::domain< proto::generator<lambda_expr> >
{};

À la ligne 2 nous prédéclarons notre adaptateur d'expression lambda. Cela rend possible son utilisation à la ligne 7 lorsque l'on déclare lambda_domain. La structure lambda_domain est une manière d'expliquer à Proto comment posttraiter chaque nouvelle expression lambda ; en l'occurrence, en les passant par un proto::generator<lambda_expr>. C'est un objet-fonction qui encapsule des expressions dans lambda_expr (qui reste à définir).

Définissons maintenant lambda_expr, notre adaptateur d'expression personnalisé. C'est là que nous mettrons nos suppléments spécifiques au domaine (explications ci-dessous) :

// Une lambda est une expression avec un operator()
// qui évalue cette lambda.
template<typename ProtoExpression>
struct lambda_expr
  : proto::extends<ProtoExpression, lambda_expr<ProtoExpression>, lambda_domain>
{
    lambda_expr(ProtoExpression const &expr = ProtoExpression())
      : lambda_expr::proto_extends(expr)
    {}

    // De sorte que boost::result_of puisse être utilisé pour calculer
    // le type de retour de cette expression lambda.
    template<typename Sig> struct result;

    template<typename This, typename Arg>
    struct result<This(Arg)>
      : boost::result_of<Lambda(This const &, Arg const &)>
    {};

    // Évaluation des expressions lambda.
    template<typename Arg1>
    typename result<lambda_expr(Arg1)>::type
    operator()(Arg1 const & arg1) const
    {
        return Lambda()(*this, arg1);
    }
};

C'est à la ligne 5 — héritage depuis proto::extends — que les associations entre la classe du domaine lambda, du générateur et de l'extension sont établies. Les trois paramètres template sont : l'expression Proto que nous étendons, l'expression lambda que nous définissons, et le domaine avec lequel toutes les expressions lambda sont associées. Le constructeur à la ligne 7 correspond à un squelette minimal, le reste dépend de vous.

C'est à la ligne 23 que nous donnons (enfin !) aux expressions lambda leur operator(). À la ligne 25, nous utilisons l'algorithme Lambda que nous avons défini précédemment. Notez que nous passons *this comme premier paramètre. L'algorithme Lambda s'attend à recevoir un modèle du concept ProtoExpression. Puisque *this fait référence à une instance de lambda_expr qui modélise LambdaExpression, et que LambdaExpression dérive de ProtoExpression, cela fonctionne.

Le seul autre détail intéressant est la classe template interne result et l'utilisation de boost::result_of pour calculer le type de retour de l'algorithme Lambda. Lambda est un objet-fonction de style TR1 valide (grâce à l'héritage de proto::or_). Et avec l'ajout de la classe template interne result, tous les objets lambda_expr ont également un style TR1 valide(1).

Nous y sommes presque. Tout ce qu'il reste à faire, c'est faire de arg1 une expression lambda pour que les expressions dans lesquelles elle apparaît soient également des expressions lambda. Pour ce faire, nous l'encapsulons juste dans lambda_expr :

// Définition de arg1 comme précédemment, mais encapsulé dans lambda_expr.
typedef lambda_expr<proto::terminal<arg1_tag>::type> arg1_type;
arg1_type const arg1 = arg1_type();

Avec ce dernier changement, chaque expression impliquant arg1 devient à son tour une lambda par contamination, et possède un operator() qui évalue l'expression lambda. Maintenant nous y sommes. (Pour l'instant.)

Quand tout est mis bout à bout, notre petite bibliothèque de lambda ressemble à ceci :

#include <boost/proto/proto.hpp>
using namespace boost;

struct arg1_tag {};

// Déclaration anticipée de notre adaptateur d'expression personnalisé.
template<typename ProtoExpression> struct lambda_expr;

// Définition d'un domaine lambda et de son générateur, ce qui encapsule 
// simplement toute nouvelle expression dans notre adaptateur personnalisé.
struct lambda_domain
  : proto::domain< proto::generator<lambda_expr> >
{};

// Un "algorithme" Proto : une grammaire avec transformées intégrées pour
// l'évaluation d'expressions lambda (expliqué dans l'article précédent).
struct Lambda
  : proto::or_<
        // À l'évaluation d'un placeholder terminal, retourner l'état.
        proto::when< proto::terminal<arg1_tag>, proto::_state >
        // Sinon, adopter le comportement par défaut.
      , proto::otherwise< proto::_default< Lambda > >
   >
{};

// Une lambda est une expression avec un operator() qui évalue la lambda.
template<typename ProtoExpression>
struct lambda_expr
  : proto::extends<ProtoExpression, lambda_expr<ProtoExpression>, lambda_domain>
{
    lambda_expr(ProtoExpression const &expr = ProtoExpression())
      : lambda_expr::proto_extends(expr)
    {}

    // Pour que boost::result_of puisse servir à calculer
    // le type de retour de cette expression lambda.
    template<typename Sig> struct result;

    template<typename This, typename Arg>
    struct result<This(Arg)>
      : boost::result_of<Lambda(This const &, Arg const &)>
    {};

    // Évalue les expressions lambda.
    template<typename Arg1>
    typename result<lambda_expr(Arg1)>::type
    operator()(Arg1 const & arg1) const
    {
        return Lambda()(*this, arg1);
    }
};

// Définition de arg1 comme précédemment, mais encapsulé dans lambda_expr.
typedef lambda_expr<proto::terminal<arg1_tag>::type> arg1_type;
arg1_type const arg1 = arg1_type();

// Fin de la bibliothèque lambda ici. Début du code de test.
#include <cassert>

int main()
{
    int i = (arg1 + 42)(1);
    assert( i == 43 );
}

Sans compter les commentaires, les lignes vides et le code de test (qui ne fait pas partie de la bibliothèque), on arrive à 34 lignes selon mes calculs. Maintenant que tout fonctionne, faisons quelques essais :

Le code ci-dessus utilise notre bibliothèque de 34 lignes pour remplir un tableau avec les 10 premiers nombres de Fibonacci. Pas si mal. Si vous êtes perplexe quant au fonctionnement de cette lambda, vous êtes peut-être dérouté par l'expression &arg1. Proto a surchargé l'opérateur unaire operator& pour que &arg1 construise une arborescence d'expression Proto. L'arborescence pour (&arg1)[-2] + (&arg1)[-1] est présentée en figure 4.

// Implémentation standard de l'algo std::transform.
for(; begin != end; ++begin, ++out )
    *out = fun(*begin);

int *begin = data+2, *out = data+2;
for(; begin != data+10; ++begin, ++out )
    *out = ((&arg1)[-2] + (&arg1)[-1])(*begin);

int *begin = data+2, *out = data+2;
for(; begin != data+10; ++begin, ++out )
    *out = (&*begin)[-2] + (&*begin)[-1];

Il y a un léger problème avec notre solution, mais à moins que vous ne soyez un spécialiste du langage, je ne m'attends pas à ce que vous le repériez : le placeholder arg1 requiert une initialisation dynamique. Cela signifie qu'il doit être construit à l'exécution. Le problème est que l'ordre d'initialisation des dépendances pourrait causer l'utilisation de arg1 avant que son constructeur ne soit appelé. C'est mauvais pour nous.

Nous pouvons éviter le problème d'ordre d'initialisation en faisant de arg1 un PODQu'est-ce qu'un type POD ? et en utilisant une initialisation statique. En C++03, ça signifie que lambda_expr ne peut pas avoir de constructeur ni utiliser l'héritage.(3) Pas de problème ; Proto fournit un autre mécanisme pour étendre les expressions : BOOST_PROTO_EXTENDS et consors. Nous pouvons redéfinir lambda_expr comme suit :

// Une lambda est une expression avec un operator() qui
// évalue la lambda.
template<typename ProtoExpression>
struct lambda_expr
{
    BOOST_PROTO_BASIC_EXTENDS(ProtoExpression, lambda_expr, lambda_domain)
    BOOST_PROTO_EXTENDS_ASSIGN()
    BOOST_PROTO_EXTENDS_SUBSCRIPT()

    // Pour que boost::result_of puisse servir à calculer
    // le type de retour de cette expression lambda.
    template<typename Sig> struct result;

    template<typename This, typename Arg>
    struct result<This(Arg)>
      : boost::result_of<Lambda(This const &, Arg const &)>
    {};

    // Évalue les expressions lambda.
    template<typename Arg1>
    typename result<lambda_expr(Arg1)>::type
    operator()(Arg1 const & arg1) const
    {
        return Lambda()(*this, arg1);
    }
};

Nous avons dû remplacer l'héritage depuis proto::extends et le constructeur de lambda_expr par trois macros. La première en ligne 6 établit les relations entre le domaine, le générateur et la classe d'extension lambda. La seconde et la troisième macro définissent respectivement des fonctions membres operator= et operator[] arborescentes. (Certes, les macros sont déplaisantes, mais nécessaires avec C++03. Les règles assouplies quant aux types POD et les constructeurs constexpr de C++0x rendront inutiles ce genre de pirouettes.)

Maintenant que nous avons changé lambda_expr pour permettre une initialisation statique, nous pouvons l'utiliser lors de l'initialisation du placeholder arg1 comme suit :

lambda_expr<proto::terminal<arg1_tag>::type> const arg1 = {};

L'initialisation par accolades (appelée initialisation par agrégat) découle de ce que lambda_expr n'a plus de constructeur. Et puisque l'initialisation d'objets lambda_expr nécessite maintenant une syntaxe différente, nous devons changer le générateur de lambda lors de la définition de lambda_domain de la façon suivante :

// Définition d'un domaine lambda et de son générateur, ce qui encapsule 
// simplement toute nouvelle expression dans notre adaptateur personnalisé.
struct lambda_domain
  : proto::domain< proto::pod_generator<lambda_expr> >
{};

Notez bien que nous avons remplacé proto::generator par proto::pod_generator. Le seul objectif de ce changement était d'obtenir que Proto utilise les accolades à l'initialisation de nouveaux objets lambda_expr au lieu de la syntaxe ordinaire d'appel de constructeur.

#include <boost/proto/proto/hpp>
using namespace boost;

struct arg1_tag {};

// Forward-declare our custom expression wrapper
template<typename ProtoExpression> struct lambda_expr;

// Define a lambda domain and its generator, which
// simply wraps all new expressions our custom wrapper
struct lambda_domain
  : proto::domain< proto::pod_generator<lambda_expr> >
{};

// A grammar with embedded transforms for evaluating lambda expressions
struct Lambda
  : proto::or_<
        // When evaluating a placeholder terminal, return the state.
        proto::when< proto::terminal<arg1_tag>, proto::_state >
        // Otherwise, do the "default" thing.
      , proto::otherwise< proto::_default< Lambda > >
    >
{};

// A lambda is an expression with an operator() that
// evaluates the lambda.
template<typename ProtoExpression>
struct lambda_expr
{
    BOOST_PROTO_BASIC_EXTENDS(ProtoExpression, lambda_expr, lambda_domain)
    BOOST_PROTO_EXTENDS_ASSIGN()
    BOOST_PROTO_EXTENDS_SUBSCRIPT()

    // So that boost::result_of can be used to calculate
    // the return type of this lambda expression.
    template<typename Sig> struct result;

    template<typename This, typename Arg>
    struct result<This(Arg)>
      : boost::result_of<Lambda(This const &, Arg const &)>
    {};

    // Evaluate the lambda expressions
    template<typename Arg1>
    typename result<lambda_expr(Arg1)>::type
    operator()(Arg1 const & arg1) const
    {
        return Lambda()(*this, arg1);
    }
};

lambda_expr<proto::terminal<arg1_tag>::type> const arg1 = {};

// End lambda library. Begin test code:
#include <algorithm>

int main()
{
    int data[10] = {0,1};
    // Fibonacci sequence
    std::transform(data+2, data+10, data+2, (&arg1)[-2] + (&arg1)[-1]);
}

Avec les changements ci-dessus pour pallier le problème d'ordre d'initialisation (et aux conditions sus-citées), notre minibibliothèque de lambda compte maintenant 32 lignes de code. OK, ça ne fait pas tout à fait 30 comme promis. Vous me pardonnez ? J'espère que vous avez apprécié cette introduction aux classes de grammaires, de transformées et d'extensions Proto. Nous en verrons bien davantage dans de futurs articles, mais pour l'instant, vous avez déjà plus qu'il n'en faut pour commencer à construire vos propres langages intégrés avec Proto.

Dans le prochain article, nous allons remédier à l'insuffisance majeure de ce DSEL de lambda : le fait qu'il n'accepte qu'un seul argument. Accepter des arguments supplémentaires est une chose aisée, et nous verrons en cours de route comment rédiger des transformées Proto, pour les rendre bien plus flexibles et puissantes.

À bientôt !

Merci à Bartosz Milewski et David Abrahams pour leurs précieux commentaires sur ce billet.