01 sept. 2010

Le futur standard C++ : les fonctions lambda

Je me souviens de ces vertes années où, élève ingénieur, j'ai appris ce qu'étaient les fonctions lambda. La beauté de la chose m'avait alors complètement échappé, d'autant plus que programmant principalement en C et en C++, je n'en avais strictement aucun besoin. A noter que le caractère qui m'apparaissait particulièrement abscons de ces constructions était principalement du au fait qu'on étudiait alors le meilleur langage du monde, que des spécialistes énamourés ont surnommé "plein de parenthèses insipides".

10 ans après, la nouvelle tombe : mes langages de prédilection (à l'heure actuelle, C# et C++[1]) intègrent les fonctions lambda. Bon. OK. Il est temps d'y réfléchir sérieusement.

Notes

[1] Le draft le plus récent du language C++ est disponible en ligne ici N3126:

L'existant

Le standard C++ actuel ne supporte bien évidemment pas les fonctions lambda, mais il est toutefois possible de les émuler grâce aux possibilités du langage. Deux choses nous sont nécessaires :

  1. un système pour exécuter une fonction dans un contexte donné
  2. un système qui autorise l'exécution de n'importe quelle fonction

Le premier point est traité grâce à la surcharge des opérateurs, qui nous permet de surcharger l'opérateur () d'une classe. La classe sert alors de capture du contexte - les propriétés peuvent nous servir pour stocker ou référencer n'importe quelle donnée. Ce qu'on obtient est un foncteur, un objet qui se comporte comme une fonction mais auquel on peut associer des informations supplémentaires :

struct multiplie_et_accumule
{
  // capture par référence
  int& a;
  // capture par copie
  int b;
  // constructeur nécessaire à cause de la capture par référence
  multiplie_et_accumule(int& _a, int _b) : a(_a), b(_b) { }
  // opération 
  void operator()(int param)
  {
    a += b * param;
  }
};

Le second point est traité grâce aux templates du C++. Ils me permettent de définir un utilisateur de foncteur générique :

template <class _InIter, class _Function>
void operate(_InIter first, _InInter last, _Function function)
{
  while (first !=last)
  {
    function(*first);
    ++first;
  }
}

Bien évidemment, cette solution pratique est loin d'être idéale. Premièrement, le code du foncteur est particulièrement verbeux : en éliminant les commentaires, j'ai quand même 10 lignes de code alors que la seul qui m'intéresse vraiment est l'opération en elle même. Deuxièmement, le standard C++ interdit l'utilisation de types définis localement avec des templates. Le foncteur doit être défini à l'extérieur de la fonction qui va in fine l'utiliser, et ce même si cette fonction est la seule à utiliser ce foncteur.

Dans l'esprit, on a quelque chose qui n'est pas trop mal. Dans la pratique, on devrait pouvoir faire mieux.

Les fonction lambda - les propositions N1958 et 1968 (pdf)

En 2006, Valentin Samko propose d'intégrer les expression lambda au langage C++. Indépendamment de cette proposition, Jeremiah Willcock, Jaakko Jarvi, Doug Gregor, Bjarne Stroustrup et Andrew Lumsdaine rédigent conjointement une seconde proposition. De ces deux propositions différentes, c'est clairement la seconde qui va émerger et rassembler - bien que le concept de capture du contexte soit issu de la première de ces deux propositions.

Comment définit-on une expression lambda en C++11 ? La syntaxe utilisée est celle-ci :

[ lambda-capture ] ( parameter-list ) -> return-type { statement-list }

Il y a peu de chance que parameter-list, return-type et statement-list vous pose problème. La partie -> return-type est d'ailleurs optionnelle si la fonction lambda n'est composé que d'une instruction return (voir quelques exemples ci-dessous).

Ce qui est nouveau (outre la forme), c'est cette lambda-capture en début d'expression. Comme vous pouvez vous en douter, cette liste de capture va nous servir à capturer le contexte d'exécution de l'expression lambda. Mais d'abord, c'est quoi un contexte d'exécution ? Si on veut faire grossier, on dira qu'il s'agit de la pile locale d'exécution de la fonction. Lorsqu'une fonction s'exécute, elle réserve sur la pile du programme l'espace mémoire nécessaire au stockage de toutes les variables utilisées en local. Lorsque la fonction termine, cet espace mémoire est libéré automatiquement.

Une fonction lambda a ceci de particulier qu'elle peut s'exécuter à n'importe quel instant une fois qu'elle a été défini. Son contexte d'exécution est bien évidemment celui de la fonction appelante, mais ce n'est pas réellement ce qu'on veut : l'intérêt est en fait de l'exécuter dans le contexte de la fonction dans laquelle elle est définie (ci-après la fonction parent), ce qui permet de faire référence à ses données locale. Pour ce faire, on capture le contexte d'exécution au moment de la définition de la fonction lambda. C'est ce contexte qui sera plus tard utilisé lorsque la fonction lambda sera exécutée.

Comment capture-t-on ce contexte ?

Premièrement, il y a plusieurs méthodes de capture :

  • la capture par copie : la variable à laquelle la fonction lambda accède est en fait une copie de la variable définie dans le fonction parent. Une modification sur cette variable n'a pas d'incidence sur la variable de la fonction parent.
  • la capture par référence : la variable à laquelle on accède est une référence sur la variable définie dans la fonction parent. La variable peut donc être modifiée par la fonction lambda.

Il faut ensuite choisir qu'est ce qui va être capturé. On peut souhaiter capturer l'intégralité du contexte d'exécution de la fonction parent. C'est bien sûr une possibilité, mais est-ce vraiment utile ? Généralement, on souhaitera se limiter aux seules variables qui ont un intérêt pour la fonction lambda.

Une fois ces choix effectuer, on peut commencer à regarder à quoi cette lambda-capture ressemble :

lambda-capture :
vide |
capture-default |
capture-default, capture-list |
capture-list
capture-list :
capture |
capture ... |
capture, capture-list

Déjà, si lambda-capture est vide, alors aucune partie du contexte ne sera capturé. Ensuite, capture-default est = ou &. = indique que, par défaut, le contexte est capturé par copie - tandis que & indique que par défaut, le contexte est capturé par référence. Si on n'indique que capture-default, alors tout le contexte est capturé. Voilà pour les cas simples.

int multiplier = 10;
int divisor = 5;
// on ne capture aucun contexte. Ni multiplier ni divisor ne sont accessible. auto lambda1 = [](int a) -> int { return a*a; };
// le contexte complet est capturé par référence // multiplier et divisor sont accessible, et les modifications // se répercutent auto lambda2 = [&](int a) -> int { ++multiplier; return a*multiplier; };
// le contexte complet est capturé par copie // multiplier et divisor sont accessible, mais les modifications ne // se répercutent pas auto lambda3 = [=](int a) -> int { return a*multiplier; }

Au delà de ces cas très simples - et pas forcément très intelligent : l'exemple montre ainsi que divisor est accessible à des lambdas qui ne l'utilisent pas - on peut spécifier quelles variable fait partie de la capture du contexte de manière individuelle.

// multiplier est capturée par référence
auto lambda4 = [&multiplier] -> int { /* code */ };
// multiplier et divisor sont capturées par copie
auto lambda5 = [multiplier, divisor] -> int { /* code */ };
// multiplier est capturé par référence, divisor l'est par copie
auto lambda6 = [&multiplier, divisor] -> int { /* code */ };

Si on veut spécifier que le contexte complet est capturé par copie (ou par référence) sauf certaines variables, on peut aussi le faire en spécifiant d'abord le capture-default

// le contexte complet est capturé par référence, sauf divisor qui l'est pas copie.
auto lambda7 = [&,divisor] -> int { :* code */ };

En fait, il n'y a guère qu'une seule règle à suivre : une variable ne peut être capturé qu'une fois.

Utiliser les fonctions lambda

Parce que c'est bien beau de définir des choses, encore faut-il les utiliser. Et là, on a de la chance : car les fonction lambda s'utilisent comme des fonctions tout ce qu'il y a de plus normal. Bien évidemment, dans la plupart des cas, on souhaite pouvoir passer une lambda en paramètre d'une autre fonction : il faut donc en connaître le type. C'est là que le bas blesse, parce que le type sous-jacent d'une lambda est un détails d'implémentation. En gros, les compilateurs font ce qu'ils veulent.

Est-on bloqué pour autant ? Bien sûr que non !

Premièrement, affecter une lambda à une variable est facile grâce au mot-clef auto (je donne plusieurs exemples ci-dessus). Ensuite, puisqu'une lambda se comporte comme une fonction, on peut utiliser le même truc que celui utilisé pour exécuter n'importe quel type de foncteur : en passant par des templates, on laisse le compilateur gérer la déduction du type réel pour n'utiliser que le mécanisme d'appel de la fonction lambda - avec un bonus : la fonction template ne prends pas nécessairement une lambda, mais peut continuer à prendre un foncteur ou même un pointeur sur fonction en argument.

Un exemple d'utilisation

Fort heureusement pour les amoureux des lambdas (et je vous prédis qu'ils vont rapidement se compter par centaines), certains compilateurs du marché les ont déjà intégré - et notamment les versions récentes de g++ ainsi que Visual C++ .Net 2010 (la version Express est, comme d'habitude, gratuite sur le site de Microsoft).

J'ai peu ainsi apprécier la puissance de cette fonctionnalité nouvelle en implémentant une petite classe, très inspirée par l'extension Linq du C#. Laissez moi donc vous présenter la classe query[1]

#ifndef query_h 
#define query_h
#include <vector> #include <algorithm>
template <class _Type> class query { public: typedef std::vector<_Type> container_type; typedef typename container_type::iterator iterator; typedef typename container_type::const_iterator const_iterator; typedef typename container_type::value_type value_type;
private: container_type m_content;
private: void push_back(value_type value) { m_content.push_back(value); }
public: query() { }
template <class _InIter> query(_InIter first, _InIter last) : m_content(first, last) { }
template <class _OtherType> query(const std::vector<_OtherType>& content) : m_content(content.begin(), content.end()) { }
query(const query& other) : m_content(other.begin(), other.end()) { }
~query() { }
query& operator=(const query& other) { return *this; }
template <class _Callable> query& with(_Callable callable) { auto predicate = [&](const value_type& value) { return !callable(value); }; m_content.erase(std::remove_if(m_content.begin(), m_content.end(), predicate), m_content.end()); return *this; }
template <class _Callable> query& order_by(_Callable callable) { auto predicate = [&](const _Type& first, const _Type& other) { return callable(first) < callable(other); }; std::sort(m_content.begin(), m_content.end(), predicate); return *this; }
const_iterator begin() const { return m_content.begin(); } const_iterator end() const {return m_content.end(); } iterator begin() { return m_content.begin(); } iterator end() { return m_content.end(); } };
template <class _Type> query<_Type> from(const std::vector<_Type>& in) { return query<_Type>(in); }
template <class _Type, class _InIter> query<_Type> from(_InIter first, _InIter last) { return query<_Type>(first, last); }
#endif // query_h

Comment utiliser cette classe ? Le code suivant va vous éclairer :

#include <iostream>
#include <vector>
#include "query.h"
struct test { test() : a(false), b(0) { } test(bool _a, int _b) : a(_a), b(_b) { } bool a; int b; };
int main(int argc, char* argv[]) { std::vector<test> c;
c.push_back(test(false, 2)); c.push_back(test(false, 5)); c.push_back(test(true, 4)); c.push_back(test(true, 1)); c.push_back(test(true, 0)); c.push_back(test(false, 6)); c.push_back(test(true, 3));
auto result = from<test>(c.begin(), c.end()) .with( [](const test& t) { return t.a; } // 1 ) .order_by( [](const test& t) { return t.b; } // 2 );
std::for_each(result.begin(), result.end(), [](const test& t) { std::cout << "A=" << t.a << "; B=" << t.b << std::endl; });
return 0; }

Le code extrait une partie de la collection c (la condition d'extraction est spécifiée par la lambda 1) et trie cet extrait selon l'ordre spécifié par la lambda 2.Le programme écrit ceci sur la sortie standard :

A=1; B=0
A=1; B=1
A=1; B=3
A=1; B=4

On voit que les données sont triées selon la valeur de test::b (tel que spécifié dans la lambda 2), et que seules les instances dont test::a est vrai sont là.

Si j'avais du écrire les foncteur équivalents, chacun d'eux aurait nécessite plusieurs lignes de code situé autre part. Avec des fonctions lambda, mon code est entièrement écrit là où j'en ai besoin - en termes de maintenance, les conséquences ne sont pas les même si je dois effectuer une modification dans les fonctions lambda ou dans les foncteurs.

On notera que les méthode query<>::with() et query<>::order_by() utilisent leurs propres fonctions lambda internes pour effectuer une opération complexe à partir de l'opération spécifiée par l'utilisateur. Ainsi, les comparaisons nécessaire pour trier la liste des valeurs est faite dans une lambda qui capture la lambda utilisateur par référence.

Conclusion

Maintenant que vous avez lu cet article, vous avez le devoir d'étudier de manière plus sérieuse ce nouvel outil mis à notre disposition par le comité de normalisation du C++. les expression lambda autorisent mille et un raccourcis qui rendront votre code plus court, plus lisible - et donc plus facile à maintenir. La portée du changement fait que c'est une des évolution majeure du futur standard, une avec laquelle il faudra compter !

Notes

[1] Notez bien que cette classe n'est qu'un test. Elle est relativement peu intelligente,puisqu'elle commence par copier les données qu'on lui donne. On devrait pouvoir mieux faire...

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet