Quelque chose comme Linq

Le langage C# a quelques caractéristiques plutôt chouettes. En particulier, on y offre ce qu'on y appelle Linq, pour Language Integrated Query, un mécanisme permettant, à  l'aide d'expressions λ, d'exprimer des opérations sur une source de données (une base de données, un conteneur, un énumérable au sens large, etc.) dans le langage plutôt qu'à  travers des chaînes de caractères.

En lisant http://www.drdobbs.com/cpp/linq-like-list-manipulation-in-c/240166882 j'ai eu l'idée d'implémenter moi aussi une sorte de Linq pour C++, en utilisant une syntaxe connexe à  celle proposée dans l'article, mais avec une autre approche pour ce qui est de l'implémentation sous-jacente. Ce qui suit n'est que le fruit de ce divertissement, pas une implémentation commerciale; cela dit, si ça peut vous inspirer...

Une tentative syntaxiquement imparfaite

Le premier jet que je vous propose fonctionne, et fonctionne bien d'ailleurs, mais a un petit irritant sur le plan syntaxique qui fait qu'on ne voudra pas s'y arrêter.

Idée générale

L'idée générale va comme suit :

Programmes de test

Quelques programmes de test suivent. Le premier, à  partir d'un conteneur d'entiers, crée un conteneur de ceux qui sont de valeur 5 ou 7 et passe ce nouveau conteneur en paramètre à  une fonction qui en affichera les éléments.

#include "linqlike.h"
#include <iostream>
#include <vector>
using namespace std;
template <class C>
   void print_elems(C && conteneur) {
      for (const auto &e : conteneur)
         cout << e << ' ';
      cout << '\n';
   }
int main() {
   using namespace linq_like;
   vector<int> v{ 2, 3, 5, 7, 11 };
   print_elems(
      from(v) >>
         where<int>([](int n) { return n == 5 || n == 7; }) >>
         sink<int>()
   );
}

L'expression from(v) crée une source de données sur la base du contenu de v. Sur le plan technique, pour enchaîner les opérations avec un seul et même opérateur >>, il nous faut un format commun entre les opérations. Dans notre implémentation, ce format sera fonctionnel (voir plus bas). Nous acceptons n'importe quel prédicat applicable à  un élément de la source pour discriminer dans la clause where, mais il est clair que les expressions λ sont l'outil privilégié ici. L'opération sink retourne un conteneur primitif (j'utilise un vector à  l'interne, par souci d'efficacité).

Le deuxième, à  partir d'un conteneur de string, crée un conteneur d'entiers contenant leurs tailles, puis crée un conteneur de ceux qui sont de valeur 5 ou 7 et compte le nombre d'éléments de ce conteneur.

#include "linqlike.h"
#include <iostream>
#include <vector>
#include <string>
#include <string_view>
using namespace std;
int main() {
   using namespace linq_like;
   vector<string> v{ "yo","man","genre","mettons","tigidou man" };
   auto n = from(v) >>
         select<string>([](const string &s) -> int { return static_cast<int>(s.size()); }) >>
         where<int>([](int n) { return n == 5 || n == 7; }) >>
         count<int>();
   cout << n << endl;
}

La clause select est différente du where, en ce sens que where prend une source de données d'un certain type et retourne une autre source de données (potentiellement plus petite, dû à  l'action du prédicat) du même type, alors que select applique une transformation aux éléments de la source et laisse par conséquent sortir une séquence d'un autre type.

Le troisième, à  partir d'un conteneur de string, crée un conteneur d'entiers contenant leurs tailles, puis crée un conteneur de ceux qui sont de valeur 5 ou 7, puis crée un conteneur de float dont les éléments ont une valeur de 0.5 plus élevée que celles du conteneur dont ils sont inspirés, puis crée une list<float> à  partir de ces valeurs et en affiche les éléments.

#include "linqlike.h"
#include <iostream>
#include <vector>
#include <string>
#include <list>
using namespace std;
template <class C>
   void print_elems(C && conteneur) {
      for (const auto &e : conteneur)
         cout << e << ' ';
      cout << '\n';
   }
int main() {
   using namespace linq_like;
   vector<string> v{ "yo","man","genre","mettons","tigidou man" };
   print_elems(
      from(v) >>
         select<string>([](const string &s) -> int { return static_cast<int>(s.size()); }) >>
         where<int>([](int n) { return n == 5 || n == 7; }) >>
         select<int>([](int n) { return n + 0.5f; }) >>
         to_<list<float>, float>()
   );
}

Après ces quelques exemples, il est probablement clair pour vous que la capacité d'exprimer à  même le code source des combinaisons d'opérations rappelant celles que l'on retrouve dans une requête SQL est un avantage intéressant. Je présume que le besoin d'indiquer à  chaque fois (where<int>, select<string>, to_<list<float>,float>, ...) le type source est un irritant pour vous comme pour moi.

Implémentation

L'implémentation de cette version va comme suit.

Pour les besoins de la cause, j'ai placé les outils qui suivent dans l'espace nommé linq_like, dans le but d'éviter des conflits. Pensons par exemple à  count(), qui pourrait causer problème avec std::count() pour qui a inclus <algorithm> puis fait un using namespace std; même s'il s'agit d'une bien mauvaise habitude. 

#ifndef LINQ_LIKE_H
#define LINQ_LIKE_H
#include <functional>
#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>
namespace linq_like {

Ce que nous nommerons une source<T> est une source de données de type T, destinée à  n'importe laquelle des opérations qui suivent. Pour fins de rapidité, nous utilisons un vector<T> à  l'interne pour entreposer les données.

Nous avons implémenté le constructeur de mouvement parce que nous souhaitons maximiser le recours à  cette sémantique dans la mécanique que nous mettons en place. En effet, la plupart des opérations enchaînées dans notre mécanique retournent des temporaires jetables, ce qui laisse entendre que le recours au mouvement peut réduire de manière importante la quantité de copies dans le code généré.

 
   template <class T>
      struct source {
         using content_type = std::vector<T>;
         using value_type = T;
         content_type data;
         source() = default;
         source(const content_type &data) : data{ data } {
         }
         source(source &&src) : data{ std::move(src.data) } {
         }
         template <class It>
            source(It debut, It fin) : data { debut, fin } {
            }
         content_type value() const {
            return data;
         }
         using iterator = typename content_type::iterator;
         using const_iterator = typename content_type::const_iterator;
         using size_type = typename content_type::size_type;
         iterator begin() {
            return data.begin();
         }
         const_iterator begin() const {
            return data.begin();
         }
         const_iterator cbegin() const {
            return data.cbegin();
         }
         iterator end() {
            return data.end();
         }
         const_iterator end() const {
            return data.end();
         }
         const_iterator cend() const {
            return data.cend();
         }
         size_type size() const {
            return data.size();
         }
         bool empty () const {
            return data.empty();
         }
         template <class U>
            void push_back(U &&elem) {
               data.push_back(std::forward<U>(elem));
            }
         template <class ... Args>
            void emplace_back(Args && ... args) {
               data.emplace_back(std::forward<Args>(args)...);
            }
      };

Nous mettons de l'avant cette préférence pour le mouvement dans l'opérateur >> sur une source<T> nommée src et une fonction fct de type F, en passant src par mouvement à  fct. Notez que l'opérateur >> n'est en fait qu'un relais dans une séquence de combinaisons de fonctions ici. Notez aussi que, pour que le code client ci-dessus fonctionne, il faut que les clauses comme select ou where retournent... des fonctions!

 
   template <class T, class F>
      auto operator>>(source<T> && src, F fct) {
         return fct(std::move(src));
      }

Du lot, la fonction from() est sans doute la plus simple : il s'agit d'une simple fonction de fabrication d'un source<T> à  partir d'un conteneur de T. Les versions pour couvrir le cas des tableaux bruts est laissé en exercice.

 
   template <class C>
      source<typename C::value_type> from(const C &data) {
         return source<typename C::value_type> { std::begin(data), std::end(data) };
      }

Un select accepte une fonction fct de type F et retourne une fonction qui appliquera fct sur chaque élément d'une éventuelle source<T> nommée src.

Le code montre de manière évidente que select dissimule un std::transform(), mais il adviendra souvent en pratique que le select permette principalement de choisir un ou plusieurs états d'un objet en fonction des besoins du code client.

La partie la plus subtile du code ici est le type de retour : une fonction (std::function) prenant en paramètre une source<T> et retournant une source<U>... le problème étant bien sûr de déterminer U, car il s'agit en fait du type de l'application de fct sur un T.

Ceci explique le recours à  declval<T>(). En effet :

  • La « fonction » declval<T>() retournerait, si elle était appelée, une hypothétique instance de T, « créée » sans qu'on ne sache comment
  • Évidemment, declval est déclarée sans être définie, donc il serait erronné de vraiment appeler cette fonction... Sa raison d'être est de permettre certaines manoeuvres de métaprogrammation
  • Ce qui nous intéresse vraiment est le type de l'application de fct sur un T. C'est ce qui explique l'écriture (laborieuse) decltype(fct(declval<T>())) qui exprime précisément cette réalité. Dans la fonction select, nous nommons dest_type ce type
  • Conséquemment, le function retourné par select a pour signature source<dest_type>(source<T>)
 
   template <class T, class F>
      auto select(F fct) {
         using namespace std;
         using dest_type = decltype(fct(declval<T>()));
         return [fct](source<T> src) {
            source<dest_type> dest;
            transform(begin(src), end(src), back_inserter(dest), fct);
            return dest;
         };
      }

La clause where est plus simple, au sens où elle retourne un function acceptant un source<T> et retournant un autre source<T>.

Dans ce cas, l'algorithme s'exprime bien sous la forme d'un copy_if() tenant compte du prédicat suppléé par le code client.

 
   template <class T, class Pred>
      auto where(Pred pred) {
         using namespace std;
         return [pred](source<T> src) {
            source<T> dest;
            copy_if(begin(src), end(src), back_inserter(dest), pred);
            return dest;
         };
      }

La clause sink retourne une fonction retournant un vecteur des valeurs résultant des transformations réalisées en cours de route.

 
   template <class T>
      auto sink() {
         return [](source<T> src) {
            return src.value();
         };
      }

La clause to_ retourne une fonction retournant un conteneur choisi par le code client et contenant les valeurs (converties dans le type indiqué à  l'appel) résultant des transformations réalisées en cours de route.

Techniquement, sink<T> équivaut à  to_<vector<T>,T>.

 
   template <class D, class T>
      auto to_() {
         return [](source<T> src) {
            return D{ src.begin(), src.end() };
         };
      }

La clause count retourne une fonction retournant la cardinalité d'un source<T>. Elle est simple et se veut un exemple de ce qui pourrait être fait (d'autres calculs, comme average par exemple, pourraient être envisagés).

 
   template <class T>
      auto count() {
         return[](source<T> src) {
            return src.size();
         };
      }
}
#endif

Bien que tout ceci fonctionne et soit extensible, l'obligation d'indiquer manuellement le type de données source à  chaque étape est fastidieuse.

Pour voir le code entier de cette version : https://wandbox.org/permlink/OyvZWWWpz9KEfmey

Si vous préférez voir le code entier en version C++ 11, plus verbeux avec types de retour explicites : https://wandbox.org/permlink/f59JwK9OaQltf6CN

Un peu mieux

L'approche présentée ci-dessus fonctionne mais est syntaxiquement lourde, du fait que le compilateur ne connaît pas le type source au point de génération des clauses, ce qui nous force chaque fois à  expliciter ce type qui, bien entendu, devrait être évident.

Idée générale

Ce qui suit est un allègement syntaxique significatif pour le code client. Évidemment, l'effort doit se déplacer vers le code serveur... donc vers nous.

Programme de test

Je présenterai le code que nous écrirons à  titre de programmes de test sous une forme comparative, dans le but de mettre en valeur les avantages à  l'utilisation de cette nouvelle approche.

« Avant » « Maintenant » 
#include "linqlike.h"
#include <iostream>
#include <vector>
using namespace std;
template <class C>
   void print_elems(C && conteneur) {
      for (const auto & e : conteneur)
         cout << e << ' ';
      cout << '\n';
   }
int main() {
   using namespace linq_like;
   vector<int> v{ 2, 3, 5, 7, 11 };
   print_elems(
      from(v) >>
         where<int>([](int n) { return n == 5 || n == 7; }) >>
         sink<int>()
   );
}
 
#include "linqlike.h"
#include <iostream>
#include <vector>
using namespace std;
template <class C>
   void print_elems(C && conteneur) {
      for (const auto & e : conteneur)
         cout << e << ' ';
      cout << '\n';
   }
int main() {
   using namespace linq_like;
   vector<int> v{ 2, 3, 5, 7, 11 };
   print_elems(
      from(v) >>
         where([](int n) { return n == 5 || n == 7; }) >>
         sink()
   );
}

Les différences sont subtiles mais visibles : le code client n'a plus à  expliciter le type des données sources à  chaque étape. La clause where<int> à  gauche devient simplement where à  droite, et sink<int> devient tout simplement sink. Il y a un clair gain d'utilisabilité ici.

« Avant » « Maintenant » 
#include "linqlike.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
   using namespace linq_like;
   vector<string> v{ "yo","man","genre","mettons","tigidou man" };
   auto n = from(v) >>
         select<string>([](const string &s) { return static_cast<int>(s.size()); }) >>
         where<int>([](int n) { return n == 5 || n == 7; }) >>
         count<int>();
   cout << n << endl;
}
 
#include "linqlike.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
   using namespace linq_like;
   vector<string> v{ "yo","man","genre","mettons","tigidou man" };
   auto n = from(v) >>
         select([](const string &s) { return static_cast<int>(s.size()); }) >>
         where([](int n) { return n == 5 || n == 7; }) >>
         count();
   cout << n << endl;
}

Le même gain d'écriture apparaît ici. Chaque fois que l'on arrive au même résultat avec une écriture plus minimaliste, plus près de l'essentiel, nous faisons des gains sur le plan de l'utilisabilité.

Enfin, pour un troisième exemple, nous avons ceci.

« Avant » « Maintenant » 
#include "linqlike.h"
#include <iostream>
#include <vector>
#include <string>
#include <list>
using namespace std;
template <class C>
   void print_elems(C && conteneur) {
      for (const auto & e : conteneur)
         cout << e << ' ';
      cout << endl;
   }
int main() {
   using namespace linq_like;
   vector<string> v{ "yo","man","genre","mettons","tigidou man" };
   print_elems(
      from(v) >>
         select<string>([](const string &s) { return static_cast<int>(s.size()); }) >>
         where<int>([](int n) { return n == 5 || n == 7; }) >>
         select<int>([](int n) { return n + 0.5f; }) >>
         to_<list<float>, float>()
   );
}
 
#include "linqlike.h"
#include <iostream>
#include <vector>
#include <string>
#include <list>
using namespace std;
template <class C>
   void print_elems(C && conteneur) {
      for (const auto & e : conteneur)
         cout << e << ' ';
      cout << endl;
   }
int main() {
   using namespace linq_like;
   vector<string> v{ "yo","man","genre","mettons","tigidou man" };
   print_elems(
      from(v) >>
         select([](const string &s) { return static_cast<int>(s.size()); }) >>
         where([](int n) { return n == 5 || n == 7; }) >>
         select([](int n) { return n + 0.5f; }) >>
         to_<list<float>>()
   );
}

Encore une fois, l'écriture a été épurée de détails techniques qui ne devraient pas être du ressort du code client. Remarquez la clause to_ en fin d'expression, qui demande encore à  droite que le type de destination soit explicité; cette exigence est légitime, à  mon avis, mais le fait que le type des données sources ne doive plus être explicité rend le tout beaucoup plus digeste – je suis plus à  l'aise d'écrire to_<list<float>>() que d'écrire to_<list<float>,float>(), personnellement.

Implémentation

Le glissement qui permet cet allègement syntaxique est le passage de fonctions retournant des expressions lambda; à  une combinaison de fonction génératrices et de foncteurs génériques. L'idée est simple; prenant pour exemple la clause where :

Le code détaillé suit.

La beauté des changements que nous apportons avec cette version est qu'outre l'allègement syntaxique qu'ils permetent, leur impact sur le code en tant que tel est très localisé. Même les inclusions de bibliothèques restent telles quelles.

 
#ifndef LINQ_LIKE_H
#define LINQ_LIKE_H
#include <functional>
#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>
namespace linq_like {

Le type source<T> est aussi exactement tel qu'il était auparavant. Les ajustements que nous apportons avec cette version sont strictement opératoires.

 
   template <class T>
      struct source {
         using content_type = std::vector<T>;
         using value_type = T;
         content_type data;
         source() = default;
         source(const content_type &data) : data{ data } {
         }
         source(source &&src) : data{ std::move(src.data) } {
         }
         template <class It>
            source(It debut, It fin) : data{ debut, fin } {
            }
         content_type value() const {
            return data;
         }
         using iterator = typename content_type::iterator;
         using const_iterator = typename content_type::const_iterator;
         using size_type = typename content_type::size_type;
         iterator begin() {
            return data.begin();
         }
         const_iterator begin() const {
            return data.begin();
         }
         const_iterator cbegin() const {
            return data.cbegin();
         }
         iterator end() {
            return data.end();
         }
         const_iterator end() const {
            return data.end();
         }
         const_iterator cend() const {
            return data.cend();
         }
         size_type size() const {
            return data.size();
         }
         bool empty () const {
            return data.empty();
         }
         template <class U>
            void push_back(U &&elem) {
               data.push_back(std::forward<U>(elem));
            }
         template <class ... Args>
            void emplace_back(Args && ... args) {
               data.emplace_back(std::forward<Args>(args)...);
            }
      };

L'opérateur >> n'a pas changé lui non-plus, sa vocation étant précisément la même, soit déplacer une source vers une fonction et retourner le résultat pour poursuivre un enchaînement d'expressions. La nuance entre « cette » version et la précédente est dans la sémantique : ici, nous appelons un opérateur () générique d'un objet, lui fournissant par le fait même le type de son paramètre au point d'appel, sans que cela ne transparaisse dans le code source.

 
   template <class T, class F>
      auto operator>>(source<T> && src, F fct) {
         return fct(std::move(src));
      }

La fonction génératrice from demeure telle quelle, n'ayant pour rôle que de saisir une copie d'une source de données et la transposer dans une format sous notre contrôle.

 
   template <class C>
      auto from(const C &data) {
         return source<typename C::value_type> { std::begin(data), std::end(data) };
      }

La clause select est notre premier exemple de ce glissement sémantique menant à  un allègement syntaxique :

  • la fonction select sert à  apprendre le type F de la fonction à  appliquer, ce qui doit être fait au moment où le code client la sollicite
  • cette fonction retourne un select_impl<F> connaissant la fonction, mais qui peut être utilisé (operator()(S)) avec un certain type source S... qui sera, en pratique, un source<T> pour un certain type T)
  • puisque la fonction operator() « apprend » en quelque sorte le type auquel il s'applique et ce, au moment où il est appliqué, plus besoin d'indiquer ce type au moment de l'appel à  select... Voilà !
 
   template <class F>
      class select_impl {
         F fct;
      public:
         select_impl(F fct) : fct{ fct } {
         }
         template <class S>
            auto operator()(S src) const {
               using value_type = typename S::value_type;
               using namespace std;
               using dest_type = decltype(fct(declval<value_type>()));
               source<dest_type> dest;
               transform(begin(src), end(src), back_inserter(dest), fct);
               return dest;
            }
      };
   template <class F>
      select_impl<F> select(F fct) {
         return {fct};
      }

La technique est la même, en plus simple (car le type en entrée de l'opérateur () est le même que le type en sortie), pour la clause where.

 
   template <class Pred>
      class where_impl {
         Pred pred;
      public:
         where_impl(Pred pred) : pred{ pred } {
         }
         template <class T>
            auto operator()(source<T> src) {
               using namespace std;
               source<T> dest;
               copy_if(begin(src), end(src), back_inserter(dest), pred);
               return dest;
            }
      };
   template <class Pred>
      where_impl<Pred> where(Pred pred) {
         return { pred };
      }

La clause sink est très simple, mais requiert tout de même la dichotomie entre fonction génératrice et foncteur générique pour reporter au point d'utilisation la découverte du type du paramètre.

 
   struct sink_impl {
      template <class T>
         auto operator()(source<T> src) const {
            return src.value();
         }
   };
   sink_impl sink() {
      return {};
   }

La clause to_<D> doit apprendre le type D de destination dès l'appel de la fonction génératrice, et encoder ce type dans celui du foncteur to_impl<D>. Ce dernier sera toutefois responsable d'apprendre le type de la source à  partir de laquelle la conversion devra être réalisée.

 
   template <class D>
      struct to_impl {
         template <class T>
            D operator()(source<T> src) {
               return { src.begin(), src.end() };
            }
      };
   template <class D>
      to_impl<D> to_() {
         return {};
      }

Enfin, la clause count est de complexité analogue à  celle de la clause sink.

 
   struct count_impl {
      template <class T>
         auto operator()(source<T> src) const {
            return src.size();
         }
   };
   count_impl count() {
      return {};
   }
}
#endif

Il y a beaucoup d'ajouts à  faire, et d'expérimentation à  réaliser. Par exemple, il est relativement simple d'exprimer un order_by_ascending acceptant une fonction permettant d'aiguiller le critère de tri, par exemple

order_by_ascending([](const string &s) {
   return s->size();
}

... et qui effectuerait un tri de diverses string en ordre croissant de longueur, mais quelle serait la meilleure écriture pour exprimer des tris d'abord par longueur, puis par nombre de voyelles? Un enchainement de critères de tris devrait-il s'écrire comme ceci...

vector<string> v = ...
auto loc = locale{""};
auto est_voyelle = [&loc](char c) -> bool {
   const auto ch = toupper(c, loc);
   return ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U' || ch == 'Y';
};
auto res = from(v) >> order_by_ascending([](const string &s) { return s->size(); })
                   >> then_by_ascending([est_voyelle](const string &s) { return count_if(begin(s), end(s), est_voyelle); })
                   >> sink();

ou comme cela?

vector<string> v = ...
auto loc = locale{""};
auto est_voyelle = [&loc](char c) -> bool {
   const auto ch = toupper(c, loc);
   return ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U' || ch == 'Y';
};
auto res = from(v) >> order_by_ascending([](const string &s) {
                         return s->size();
                      }).then_by_ascending([est_voyelle](const string &s) {
                         return count_if(begin(s), end(s), est_voyelle);
                      })
                   >> sink();

Ce n'est qu'un exemple parmi plusieurs... Amusez-vous!

Pour voir le code entier de cet exemple : https://wandbox.org/permlink/aebdjXQ3jz7urGDZ

Lectures complémentaires

Valid XHTML 1.0 Transitional

CSS Valide !