C++ Expressif - Amusons-nous avec la composition de fonctions

L'idée derrière la composition de fonctions est vraiment très simple : étant donné deux fonctions, créons une autre fonction qui a pour effet d'en appliquer une sur le résultat de l'application de l'autre. Ce genre d'opérations sur les fonctions est bien plus simple avec un langage fonctionnel. Par exemple, définissons deux fonctions triviales, inc et square et composons-les pour faire square_and_add_one. Ici, j'utilise le langage Haskell. Si vous ne le connaissez pas, ce n'est pas grave. Une explication suit le code.

-- Définit une fonction « inc » qui incrémente son argument de 1
inc x = x + 1
 
-- Définit une fonction « square » qui met son argument au carré
square x = x * x
 
-- Définit une fonction « square_and_add_one » qui met son argument
-- au carré puis l'incrémente de 1
square_and_add_one = (inc . square)
 
-- Affiche « 10 »
main = do print (square_and_add_one 3)

Pourquoi la composition de fonctions est- elle intéressante  ?

La composition de fonctions encourage la réutilisation du code. Une bibliothèque générique de fonctions ne devrait en aucun cas offrir une fonction square_and_add_one, mais elle pourrait proposer et , c'est tout ce dont vous avez besoin si vous pouvez facilement les composer.

Pour les développeurs C++, il est probablement plus simple de comprendre ce code Haskell en regardant l'équivalent C++ :

#include <iostream>

template<typename T>
T inc(T x) { return x + 1; }
template<typename T>
T square(T x) { return x * x; }
 
template<typename T>
T square_and_add_one(T x) { return inc(square(x)); }
 
int main()
{
    std::cout << square_and_add_one(3) << std::endl;
}

Ces deux programmes sont très similaires. Un point particulièrement intéressant est le fait qu'en C++, nous devons sortir de notre façon de dire que ces fonctions étaient des templates. Avec Haskell, nous le faisons directement. Ce dernier a un typage fort comme le C++, mais il a un typage plus puissant qui laisse son compilateur déterminer les types. Donc, par exemple, à la ligne 2, le compilateur Haskell sait que inc est une fonction qui prend et retourne un T sans que personne ne le lui dise.

Les définitions de square_and_add_one montrent la divergence entre les solutions. Vous êtes probablement familier avec le fonctionnement de la déduction des types pour les fonctions templates en C++ (par exemple la manière dont la ligne 26 permet de déduire que le type T à la ligne 16 est int). Et si le compilateur C++ peut faire cela, alors celui d'Haskell peut aussi le faire. Mais en Haskell, la définition de est d'un tout autre genre. Nous n'avons même pas à dire combien d'arguments elle prend ! Pourquoi ?

Nous avons la réponse en regardant la définition de à la ligne 9. Notons l'utilisation de l'opérateur infixe .. Il s'agit de l'opérateur de composition des fonctions en Haskell. À partir de l'expression (inc . square), Haskell sait construire une nouvelle fonction qui est équivalente à Inc (square x). Les parenthèses autour de square x sont nécessaires, car sans elles, Haskell essayerait de passer à la fois square et xà inc comme étant des arguments, ce qui donnerait une erreur. Haskell peut analyser inc (square x) et déterminer son type en se basant sur les types de inc et square : c'est aussi une fonction qui prend et retourne un T. Puisque le compilateur peut le déterminer, nous n'avons pas besoin de le lui préciser.

En revanche, regardez la définition en C++ de square_and_add_one : vous avez à préciser devant la signature de la fonction que c'est aussi une fonction qui prend et retourne un T, bien que le compilateur puisse techniquement les déterminer en se basant sur le corps de la fonction. Dommage.

L'opérateur de composition de fonctions en Haskell ne fait en effet pas partie du noyau du langage. Il est une pure extension de bibliothèque. Sans se surpasser, nous, programmeurs C++, devons aussi pouvoir définir la composition de fonctions dans une bibliothèque, n'est-ce pas ? C'est-à-dire, nous voulons définir un composant réutilisable qui, compte tenu des deux fonctions unaires (fonctions avec un seul argument) F1 et F2, définit une troisième fonction C qui se comporte comme F1(F2(x)). De manière générale, F1 et F2 ont la possibilité d'être polymorphiques (elles peuvent opérer sur n'importe quel type de données), tout comme les exemples Haskell et C++ ci-dessus.

À quoi donc ressemble une telle solution logicielle ? Essayons de généraliser la composition de fonctions faite avec square_and_add_one ci-dessus. Au lieu de coder en dur square et inc, passons-les comme arguments. Bonne idée, mais on tombe sur un os. Comment passer une fonction template comme square à une autre fonction ? On ne peut pas, parce qu'une fonction template n'est pas une entité : elle n'a pas d'adresse et n'occupe pas d'espace. On ne peut même pas l'utiliser comme paramètre template ! La seule chose que l'on peut faire avec une fonction template c'est de l'utiliser pour instancier une fonction. C'est-à-dire, &square ne compile pas, mais &square<int> qui instancie square avec int et prend l'adresse de la fonction résultante fonctionne. Les fonctions templates ne sont pas des objets de première classe. Pour en rajouter une couche, square<int> n'est pas non plus polymorphique : il travaille uniquement sur les entiers. En revanche, les fonctions d'Haskell sont à la fois des objets de première classe et polymorphiques, ce qui rend la composition de fonctions plus facile à réaliser dans ce langage.

Assez rapidement, on se retrouve face à une grosse limitation en C++ : pour composer des fonctions polymorphiques, nous ne pouvons pas utiliser de fonctions !

Nous ne sommes pas encore morts. Les fonctions d'ordre supérieur de la STL comme std ::accumulate nous montrent la voie à suivre : encapsuler la fonction dans un objet. En définissant une classe avec une fonction membre operator(), on obtient des objets de première classe qui se comportent comme des fonctions. Ces objets ont toutes les qualités que l'on peut attendre des objets de première classe : on peut les passer, les retourner, les stocker et les copier à volonté.

Je tiens à souligner le fait que les foncteurs de la STL tels que std::plus ne sont pas polymorphiques. C'est-à-dire, vous pouvez créer un objet de type std::plus<int>, mais son operator() prend et retourne seulement des entiers. On peut le rendre plus polymorphique en déplaçant la paramétrisation de la classe vers la fonction membre. C'est-à-dire, qu'au lieu de transformer la classe en un template, on transforme plutôt son operator() en template. Un objet de ce type plus se comportera simplement comme une fonction polymorphique.

Réécrivons inc et square comme étant des foncteurs polymorphiques et définissons un template composed_fn que nous pouvons utiliser pour composer les deux et créer square_and_add_one. Le code est expliqué ci-dessous :

#include <iostream>
 
// Un type pour réaliser un foncteur polymorphique
struct inc_t
{
    template<typename T>
    T operator()(T x) const { return x + 1; }
};
 
// Foncteur agissant comme une fonction polymorphique
inc_t const inc = inc_t();
 
struct square_t
{
    template<typename T>
    T operator()(T x) const { return x * x; }
};
 
square_t const square = square_t();
 
// Ici, c'est un foncteur qui compose deux autres
// foncteurs. Il se comporte comme l'opérateur infixe . d'Haskell
template<typename Fn1, typename Fn2>
struct composed_fn
{
    explicit composed_fn(Fn1 f1 = Fn1(), Fn2 f2 = Fn2())
      : fn1(f1), fn2(f2)
    {}
 
    template<typename T>
    T operator()(T x) const // PROBLÈME ICI
    {
        return fn1(fn2(x));
    }
 
    Fn1 fn1;
    Fn2 fn2;
};
 
// Compose deux fonctions
typedef composed_fn<inc_t, square_t> square_and_add_one_t;
square_and_add_one_t const square_and_add_one = square_and_add_one_t();
 
int main()
{
    // Affiche « 10 »
    std::cout << square_and_add_one(3) << std::endl;
}

Cette solution a un gros défaut, mais au moins elle marche. On peut utiliser le template composed_fn pour composer deux « fonctions ». La ligne inc_t const inc = inc_t() déclare un objet global appelé inc et l'initialise avec inc_t() qui est une instance construite par défaut de type inc_t.

Le problème avec cette solution apparaît à la ligne 31. Le template composed_fn est supposé être générique : prendre deux foncteurs et les composer. Cependant, c'est faire une grosse hypothèse qui réduit grandement sa généricité : quand on passe un objet de type T, fn1(fn2(x)) retourne aussi un objet de type T. Bien que ce soit effectivement le cas dans notre exemple d'étude, ce n'est pas garanti. Si vous utilisez un compilateur C++0x, le problème se résout avec decltype et la nouvelle syntaxe de déclaration des fonctions (voir encadré), mais pour ceux d'entre nous qui vivent dans le présent, quelques pirouettes sont nécessaires. Le template composed_fn a besoin d'un moyen de récupérer les types Fn1 et Fn2, « Quand je te passe un objet de type T, quel est le type de l'objet que tu retournes ? » Bienvenue au protocole TR1 result_of.

Pour résoudre le problème de la déduction du type de retour, utilisons decltype et la nouvelle syntaxe de déclaration des fonctions du C++0x comme suit :

template<typename Fn1, typename Fn2>
struct composed_fn
{
    Fn1 fn1;
    Fn2 fn2;
 
    explicit composed_fn(Fn1 f1 = Fn1(),
                         Fn2 f2 = Fn2())
      : fn1(f1), fn2(f2)
    {}
 
    template<typename T>
    auto operator()(T x) const
        -> decltype(fn1(fn2(x)))
    {
        return fn1(fn2(x));
    }
};

Avec Haskell, le compilateur reconnaît juste les types des fonctions et peut propager automatiquement les types lorsque les fonctions sont composées. Nous ne sommes pas aussi chanceux en C++, c'est pourquoi le TR1 offre un utilitaire appelé result_of et un protocole associé pour déclarer et calculer les types de retours des foncteurs. On peut résoudre notre problème de composition des fonctions si l'on modifie nos foncteurs pour suivre le protocole comme suit :

// Redéfinit inc pour être un foncteur
// qui suit le protocole TR1 result_of
struct inc_t
{
    // Les templates imbriqués result servent à calculer
    // le type de retour
    template<typename Signature>
    struct result;
 
    template<typename This, typename T>
    struct result<This(T)> { typedef T type; };
 
    template<typename T>
    T operator()(T x) const { return x + 1; }
};
 
inc_t const inc = inc_t();

Maintenant, même sans decltype, il y a un moyen de demander à inc_t quel genre d'objet il retournera lorsqu'on lui passera un int. La réponse est : inc_t ::result<inc_t(int)> ::type, qui, dans notre cas, est un alias pour int. (J'en dirai plus sur l'étrange type inc_t(int) ci-dessous.) En général, vous ne devez pas accéder directement au template imbriqué result comme ceci (voir encadré). Il vaut mieux utiliser l'utilitaire result_of dans le namespace std, std ::tr1, ou boost selon l'avancement de votre implémentation du C + +. Depuis que l'implémentation de Boost fonctionne, je m'en tiens à ceci : boost::result_of<inc_t(int)>::type.

IV-A. Pourquoi result_of est si compliqué ▲

struct simple_fn
{
    // Ce n'est PAS le protocole TR1 result_of. Ne
    // faites pas ça de cette façon
    template<typename T>
    struct result { typedef T type; };
 
    template<typename T>
    T operator()(T x) const;
};

struct weird_fn
{
    template<typename T>
    struct result { /* Que diable mettre ici ??? */ };
 
    int & operator()(int);
    int const & operator()(int) const; // surcharge sur la constance de *this
    float operator()(float, float);    // accepte un nombre différent d'arguments
};

boost::result_of< weird_fn(int) >::type            // int &
boost::result_of< weird_fn const(int) >::type      // int const &
boost::result_of< weird_fn(float, float) >::type   // float

On peut en déduire que boost::result_of<inc_t(int)>::type est un alias pour int. Mais réfléchissons-y un moment. Qu'est-ce que inc_t(int) ? C'est un type de fonction. Si vous êtes un développeur C de la vieille école, vous êtes probablement plus familier avec les pointeurs de fonctions comme int(*)(int) qui est un pointeur sur une fonction qui prend et retourne un int. Si vous enlevez le pointeur, vous obtenez un type de fonction. C'est comme une signature de fonction, mais sans le nom de la fonction. Vous ne pouvez créer qu'une variable d'un type de fonction, mais cela ne vous empêche pas d'utiliser ce type dans le code.

Si on lit littéralement le type inc_t(int), c'est le type d'une fonction qui prend un entier et retourne un objet de type inc_t. Mais nulle part, nous n'avons défini de fonction qui retourne inc_t. Il est clair que quelque chose d'amusant se produit. Comment donnons-nous du sens au type inc_t(int) ? La réponse est que result_of interprète ce type d'une manière particulière ; il le lit comme une demande : (approximativement) quel est le type de l'expression inc_t()(int()) ? (Ici, inc_t() et int() sont des objets temporaires construits sur place via les constructeurs par défaut.) En fait, result_of n'a pas besoin d'évaluer l'expression pour trouver son type ; à la place, il sait regarder à l'intérieur deinc_t pour le template result, parce qu'il respecte le protocole.

En d'autres termes, result_of utilise les types de fonctions comme un langage spécifique au domaine de l'embarqué pour préciser les appels de fonctions. Hors de result_of, le type inc_t(int) a une signification ; à l'intérieur de celui-ci, il en a une autre. Ce DSL est si efficace que le subterfuge a pu vous échapper. C'est un point très important et nous y reviendrons.

Maintenant que nous avons un moyen de déclarer et calculer les types de retours des foncteurs, nous pouvons finalement écrire une implémentation correcte de composed_fn. En suivant les enseignements de result_of, on peut même rendre cette interface un peu plus intuitive : en utilisant les types de fonctions comme un DSL pour décrire les appels de fonctions.

// Un type non défini, utilisé comme paramètre factice dans notre DSL
struct _;
 
template<typename Signature>
struct composed_fn;
 
// Un template composed_fn amélioré qui utilise le protocole TR1
// result_of pour déclarer et calculer les types de retour des fonctions
template<typename Fn1, typename Fn2>
struct composed_fn<Fn1(Fn2(_))>
{
    explicit composed_fn(Fn1 f1 = Fn1(), Fn2 f2 = Fn2())
      : fn1(f1), fn2(f2)
    {}
 
    template<typename Signature>
    struct result;
 
    template<typename This, typename T>
    struct result<This(T)>
    {
        typedef typename boost::result_of<Fn2(T)>::type U;
        typedef typename boost::result_of<Fn1(U)>::type type;
    };
 
    template<typename T>
    typename result<composed_fn(T)>::type operator()(T x) const
    {
        return fn1(fn2(x));
    }
 
    Fn1 fn1;
    Fn2 fn2;
};
 
// Compose deux fonctions. Utilise un type de fonction pour spécifier comment
// les fonctions doivent être composées
typedef composed_fn< inc_t(square_t(_)) > square_and_add_one_t;
square_and_add_one_t const square_and_add_one = square_and_add_one_t();

Ce template composed_fn est capable de composer n'importe quel couple de foncteurs polymorphiques unaires implémentant le protocol result_of. Notons l'utilisation du type de fonction inc_t(square_t(_)) dans la définition de square_and_add_one. On déclare un type factice nommé _ servant de paramètre factice et utilisé dans une pseudo-expression d'appel de fonctions fait de types de fonctions imbriquées. En plus d'une esthétique simple, cette interface a l'avantage de rendre virtuellement impossible la confusion sur la fonction appelée en premier.

Finalement, après des douzaines de lignes de codes (et bien plus cachées au sein de boost::result_of), nous avons obtenu ce qu'Haskell fait en cinq lignes.

Utiliser les types de fonctions pour représenter des appels de fonctions est une astuce pratique. Maintenant que nous savons cela, nous pouvons, au prix d'un petit effort supplémentaire, l'étendre pour rendre notre template composed_fn plus puissant. En utilisant les types de fonctions, composed_fn peut réunir autant de fonctions qu'on veut avec une interface simple et intuitive. Par exemple, qu'attendez-vous du code suivant ?

composed_fn< inc_t(square_t(inc_t(square_t(_)))) > fun;
int i = fun(3);

Si vous êtes comme moi, vous vous attendez à ce qu'il soit équivalent à :

int i = inc(square(inc(square(3))));
assert( i == 101 );

Cela semble assez naturel. Notre template composed_fn ne le permet pas encore, mais ce n'est pas difficile à ajouter en utilisant la composition récursive de fonctions et une ou deux astuces. Continuez la lecture pour les explications.

// Un type non défini, utilisé comme paramètre factice dans notre DSL
struct _;
 
template<typename Signature>
struct composed_fn;
 
// Un template composed_fn amélioré qui utilise le protocole TR1
// result_of pour déclarer et calculer les types de retour des fonctions
template<typename Fn1, typename F>

struct composed_fn<Fn1(F)>
{
    // Compose récursivement tous les types de fonctions imbriqués pour construire
    // un foncteur composé à partir d'eux
    typedef composed_fn<F> Fn2;
 
    explicit composed_fn(Fn1 f1 = Fn1(), Fn2 f2 = Fn2())
      : fn1(f1), fn2(f2)
    {}
 
    template<typename Signature>
    struct result;
 
    template<typename This, typename T>
    struct result<This(T)>
    {
        typedef typename boost::result_of<Fn2(T)>::type U;
        typedef typename boost::result_of<Fn1(U)>::type type;
    };
 
    template<typename T>
    typename result<composed_fn(T)>::type
    operator()(T x) const
    {
        return fn1(fn2(x));
    }
 
    Fn1 fn1;
    Fn2 fn2;
};
 
// Cette spécialisation terminée, la récursion commence à la ligne 14
// « composed_fn<Fn(_)> fn; fn(3); » est équivalent à « Fn fn; fn(3); »
template<typename Fn>
struct composed_fn<Fn(_)> : Fn {};
 
// ASTUCE ! Lisez ce qui suit pour savoir pourquoi cette spécialisation est nécessaire
template<typename Fn>
struct composed_fn<Fn *> : composed_fn<Fn> {};

Avec cette définition de composed_fn, vous pouvez composer à volonté des foncteurs selon vos désirs. Comme promis ci-dessus, vous pouvez faire ce genre de tambouille :

// La composition de plusieurs fonctions fonctionne
composed_fn< inc_t(square_t(inc_t(square_t(_)))) > fn;
 
// Affiche 101 comme attendu
std::cout << fn(3) << std::endl;

La seule partie technique est que les types de fonctions « se dégradent » vers des types pointeurs de fonctions dans certains cas. Comme vous ne pouvez pas passer d'une fonction à une autre, quand le compilateur voit un de ces types sans aucun sens comme Fn1(Fn2(_)), il se dit, « Ah, cette personne veut probablement dire Fn1(Fn2(*)(_)) » et compile en fait de cette façon. Cela s'appelle la dégradation de type et se produit aussi avec les types de tableaux (ils se décomposent aussi en pointeurs). Nous avons besoin de nous adapter à cette étrangeté en ajoutant une spécialisation pour les pointeurs à la ligne 48. Elle enlève seulement le pointeur pour utiliser ensuite la bonne implémentation.

Bon, nous pouvons donc créer de risibles types comme « composed_fn< inc_t(square_t(inc_t(square_t(_)))) > ». Quelle utilité à tout ça ? Certes, avec inc et square, ce n'est pas très passionnant. Mais considérons à la place des foncteurs polymorphiques nommés first et second qui retournent le premier et le second membre d'une std ::pair, par exemple :

// Étant donné une std::pair p, first(p) retourne p.first (implémentation non détaillée)
first_t const first = first_t();
 
// … et second(p) retourne p.second
second_t const second = second_t();

Imaginons maintenant une grosse structure de données en arbre entièrement composé de paires de paires, etc. Que pensez-vous d'un type comme celui-ci :

// Que signifie ce type ?
composed_fn< first_t(second_t(second_t(_))) >

Il décrit un foncteur qui se déplace dans l'arbre et retourne un élément particulier, n'est-ce pas ?

Ce type a quelques propriétés intéressantes. Nous pouvons non seulement utiliser ce type pour faire des calculs à la compilation (quel est le type de cet élément imbriqué), mais on peut aussi l'utiliser pour réaliser des calculs similaires à l'exécution (cherche-moi cet élément). On a des calculs à la compilation et à l'exécution, réunis dans un petit outil soigné. C'est concis, et (comme tout bon petit DSL) ça fait ce que ça dit.

De plus, les fonctions composées de cette façon sont très efficaces. Rien n'est caché à l'optimisateur. Ce qui semble être un nombre extraordinaire d'appels de fonctions peut être entièrement inliné. Appliquer composed_fn< first_t(second_t(second_t(_))) > à une paire p est exactement équivalent à écrire p.second.second.first. L'avantage de la fonction composée est qu'elle est à la fois utile à la compilation et à l'exécution ; l'expression est seulement utile à l'exécution.

Pourquoi suis-je en train d'insister sur la composition de fonctions ? Quel est le lien avec les langages orientés domaine et Boost.Proto ? Si vous avez suivi cette série d'articles, vous savez que Proto transforme les expressions C++ en arbres qui sont proches de paires de paires. On peut utiliser les types de fonctions comme une façon très concise de décrire les calculs sur les arbres d'expressions : on peut se déplacer dans ceux-ci, sortir des éléments, appliquer des transformations, calculer des résultats, construire de nouveaux arbres, faire ce que l'on veut. Pour atteindre ce mécanisme, tout ce qu'on a besoin de savoir est comment écrire un foncteur avec le TR1 et comment composer des foncteurs en utilisant les types de fonctions. Et maintenant on le sait.

Les développeurs Haskell qui font ça depuis longtemps doivent sûrement lever les yeux au ciel, comme possédés. Nous n'avons rien fait qu'ils ne peuvent faire en quelques lignes. Mais haut les cœurs, développeurs C++. Contrairement à Haskell, C++ est un langage de développement multiparadigme nous donnant plusieurs façons de définir une solution. Et le fait de pouvoir ajouter des constructions fonctionnelles au C++ avec une bibliothèque témoigne de sa force. (Le fait que l'on doit le faire est, hélas, un témoignage d'un autre genre.)

À l'exécution, le développement C++ peut être orienté objet fonctionnel, générique, ce que l'on veut. Utilisez le paradigme qui correspond à votre problème et vos envies. Mais, à la compilation (en utilisant les templates), le développement C++ est fonctionnel pur - pas d'état mutable, s'il vous plaît ! Et si vous voulez faire les deux en un - comme avec notre template composed_fn - vous devez vous positionner à l'intersection des paradigmes utilisés à la compilation et à l'exécution : programmation fonctionnelle. C'est pour cela que garder un œil sur un langage comme Haskell qui gère bien la FP vaut le coup.

Dans le prochain article de la série, nous verrons comment utiliser le DSL des types de fonctions que nous avons développés dans cet article pour étendre l'algorithme Lambda Proto des deux derniers articles. Quand nous aurons fini, la petite bibliothèque lambda que nous aurons développée sera de loin plus utile.

En attendant…

Merci à Bartosz Milewski et David Abrahams pour leurs précieux commentaires sur cet article.

Nous remercions sincèrement Eric Niebler qui nous a autorisés à traduire son article intitulé Expressive C++: Fun With Function Composition et à le publier sur Developpez.com. Nous remercions également Florian Blanchet pour sa traduction, Francis Walter pour la mise au gabarit et sa relecture technique, Malick Seck et Claude Leloup pour leur relecture orthographique.