Les expressions lambda (λ)

Les expressions λ font partie des nouveaux outils proposés par C++ 11, et allègent en grande partie la rédaction de foncteurs pour utilisation locale. Nous présentons donc tout d'abord ces outils, que vous apprécierez sans doute beaucoup.

Par la suite, nous montrons comment même avec C++ 03, il était possible de créer des entités ayant un comportement analogue à celui d'une lambda-expression; il s'agit d'un exercice amusant, mais il est clair que les facilités du langage sont nettement préférables.

Enfin, quelques lectures complémentaires vous seront proposées.

Le lambda-calcul, souvent écrit λ-calcul, fut développé par Alonzo Church , un pionnier de l'informatique théorique avec Alan Turing, John von Neumann et une poignée d'autres qui mériteraient aussi d'être nommés ici. Il s'agit d'une idée à la fois d'une grande simplicité et d'une grande puissance. Avec ce calcul, on peut définir les concepts de calculabilité et de récursivité.

Certains langages, en particulier des langages fonctionnels comme Lisp et ses dialectes, peuvent être considérés comme étant des applications concrètes de l'idée de λ-calcul. La généricité du λ-calcul repose en partie sur des règles de substitution qui permettent d'exprimer une application de fonction comme étant équivalente à une autre expression.

La spécification de la version 3.0 du langage C# implémente les λ-expressions pour introduire une notation compacte de substitutions susceptible de remplacer des méthodes anonymes. Quelques exemples en sont visibles ci-dessous (l'opérateur de substitution y est noté =>). Vous trouverez plus de détails à ce sujet ici

(int x) => x + 1
(x, y) => x * y
Func <int,double>  f2 => x => x * 3.14159;

Dans le langage C#, l'avènement des λ-expressions semble fortement lié à l'insertion de la technologie LINQ.

En effet, les λ-expressions permettent de simplifier certaines opérations de sélection d'éléments dans des clauses SQL générant des collections, comme dans l'exemple à droite.

L'expression C# 3.0 suivante:
from c in clients
   where c.Ville == "Montréal"
   select c.Nom

...sera transformée en une autre expression, plus familière aux habitués de l'approche OO et exploitant le caractère synthétique des λ-expressions :

clients.
   Where(c => c.Ville == "Montréal").
   Select(c => c.Nom)

Avec l'avènement d'abstractions aussi fortes que la programmation générique et le polymorphisme, toutefois, il devient possible d'exprimer des λ-expressions à même les outils du langage.

Imaginons par exemple qu'on veuille écrire un programme C++ s'appuyant sur les algorithmes standards et cherchant, par exemple, à trouver le premier élément d'une séquence d'entiers (un tableau, disons).

La solution classique avec une fonction prédicat serait :

bool plus_petit_que_4(int val) {
   return val < 4;
}
#include <iostream>
#include <iterator>
#include <algorithm>
#include <random>
int main() {
   using namespace std;
   // initialiser le générateur de nombres pseudo aléatoires
   random_device rd;
   mt19937 prng { rd() };
   int tab[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   // mélanger les éléments du tableau
   shuffle(begin(tab), end(tab), prng);
   // afficher le tableau mélangé
   copy(begin(tab), end(tab), ostream_iterator<int>{ cout, " " });
   // trouver et afficher le premier élément respectant la contrainte du prédicat
   cout << '\n' << *find_if(begin(tab), end(tab), plus_petit_que_4) << endl;
}

Cette solution n'est pas très flexible, on le remarquera; une version avec foncteurs serait un sérieux pas en avant :

class PlusPetitQue {
   int seuil;
public:
   PlusPetitQue(int seuil) : seuil{ seuil } {
   }
   bool operator()(int n) const {
      return n < seuil;
   }
};
// ... inclusions et using ...
int main() {
   int tab[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   random_device rd;
   mt19937 prng { rd() };
   shuffle(begin(tab), end(tab), prng);
   copy(begin(tab), end(tab), ostream_iterator<int>{ cout, " " });
   // trouver et afficher le premier élément respectant la contrainte du prédicat
   cout << endl << *find_if(begin(tab), end(tab), PlusPetitQue{ 4 }) << endl;
}

En effet, cette version a la qualité de permettre de comparer les éléments d'une séquence avec une valeur arbitraire plutôt qu'avec une valeur connue à la compilation. On profite de la capacité qu'a le foncteur (un objet) de conserver un état pour la durée de son existence en lui confiant la borne avec laquelle comparer chaque élément de la séquence. Un gain net de généricité.

Cela dit, cette version peut encore gagner en généricité au prix d'un petit effort supplémentaire, d'un peu d'imagination et en combinant programmation générique et polymorphisme.

Les λ de C++

Avec C++ 11, les λ font leur entrée dans le langage en tant qu'outil à part entière. Une λ est une expression compacte à partir de laquelle le compilateur générera un foncteur.

Par exemple, supposons que nous réduisions le problème de compter les éléments d'une séquence dont la valeur se situe sous un certain seuil à la fonction suivante :

template <class T, class It>
   int compter_sous_seuil(It debut, It fin, const T &seuil) {
      int n = 0;
      for (; debut != fin; ++debut)
         if (*debut < seuil)
            ++n;
      return n;
   }

Pour un vecteur d'entiers v, afficher à la sortie standard les éléments de valeur inférieure à 4 s'exprimerait alors :

cout << compter_sous_seuil(begin(v), end(v), 4);

Une amélioration possible de l'implémentation de la fonction serait de remplacer la répétitive par un appel à std::count_if(). Cela serait possible en passant par un foncteur intermédiaire. Supposons que ce foncteur soit local à la fonction; nous aurions alors :

template <class T, class It>
   int compter_sous_seuil(It debut, It fin, const T &seuil) {
      using std::count_if;
      class PlusPetitQue {
         T seuil;
      public:
         PlusPetitQue(const T &seuil) : seuil{ seuil } {
         }
         bool operator()(const T &val) const {
            return val < seuil;
         }
      };
      return count_if(debut, fin, PlusPetitQue{ seuil });
   }

Cela fonctionnerait, et serait sans doute un peu plus rapide que la version originale de la fonction, mais la quantité de code à rédiger s'est accrue de manière significative. Ceci peut décourager les gens d'utiliser les algorithme standards et les foncteurs, malgré leurs nombreux avantages.

C'est ici que les λ entrent en scène. Examinez le code suivant :

template <class T, class It>
   int compter_sous_seuil(It debut, It fin, const T &seuil) {
      return count_if(debut, fin, [&](const T &val) {
         return val < seuil;
      });
   }

Plus concis, vous en conviendrez. Le code qu'on retrouve va à l'essentiel, et omet presque tous les détails auxquels une implémentation manuelle d'une foncteur aurait dû porter attention. Pourtant, il s'agit de code précisément équivalent en termes de performance à la version reposant sur un foncteur.

Anatomie d'une λ

Comme le fait remarquer Kevlin Henney en 2015, la λ minimale en C++ est [](){}(), soit une λ vide, sans paramètre, ne retournant rien et que l'on exécute. Techniquement, dans ce cas, les parenthèses pour les paramètres sont optionnelles, et on pourrait écrire []{}().

Une λ a la structure suivante :

Examinons chacun de ces éléments constitutifs, en utilisant à titre d'exemple le λ nommé f. Remarquez le recours au type auto de C++ 11, qui déduit le type d'une variable du type de l'expression servant à l'initialiser. Les λ sont des types presque anonymes : nous ne voulons pas connaître le nom que le compilateur aura utilisé pour chacune d'elles.

La liste de captures est ce qui apparaît entre crochets au début de la λ. Cette section permet de spécifier les éléments locaux à la fonction qui seront capturés par le foncteur une fois celui-ci généré par le compilateur. Les éléments globaux qui étaient accessibles là où la λ a été générée sont implicitement accessibles dans le corps de la λ (merci à Frédérick Martel-Lupien pour m'avoir fait remarquer ceci).

Lorsque [] est spécifié (paire de crochets vide), cela signifie qu'aucune variable de l'environnement ne sera capturée. Cela correspond à un foncteur sans attributs et muni strictement d'un constructeur par défaut banal. La mention [&] signifie capturer par référence tous les éléments pertinents de l'environnement, alors que la mention [=] signifie capturer par copie tous les éléments pertinents de l'environnement.

Dans notre exemple, la variable seuil est capturée par référence lors de la construction de la λ et peut donc être utilisée dans la définition de son opérateur (). Une capture par copie aurait aussi été correcte mais aurait pu être coûteuse si T::T(const T&) s'était avéré coûteux.

Il est aussi possible d'y aller à la pièce (par exemple [&x,=y] pour capturer x par référence et y par copie).

auto f = [&](const T &val) {
   //    ^^^
   return val < seuil;
};

 

La liste de paramètres correspond aux paramètres passés à l'opérateur () du foncteur une fois celui-ci généré. Il peut évidemment y en avoir autant que pour n'importe quelle fonction, dans la mesure où cela correspond à l'usage qui serait fait de la λ par la suite. On peut l'omettre si la λ n'admet par de paramètres (si elle est d'arité nulle).

Ainsi, [](){ return 3; } pourrait s'écrire []{ return 3; } tout simplement.

auto f = [&](const T &val) {
   //       ^^^^^^^^^^^^^^
   return val < seuil;
};

Il est possible de spécifier un type de retour à l'opérateur () qui sera généré, par exemple pour répondre à des besoins particuliers. Dans ce cas-ci, le type sera sans doute bool mais nous pourrions souhaiter retourner une valeur de type int.

auto f = [&](const T &val) -> bool {
   //                      ^^^^^^^
   return val < seuil;
};

Enfin, l'implémentation de la λ suit, et est typiquement l'essence du code que nous aurions voulu générer de prime abord.

auto f = [&](const T &val) {                        // <--
   return val < seuil;   // <--
};                       // <--

Remarquez la syntaxe reposant sur ->, nouvelle avec C++ 11, pour spécifier le type de retour d'une fonction. Cette syntaxe sert surtout aux λ mais peut aussi être utilisée pour d'autres fonctions. Par exemple :

auto carre(int n) -> long { return n*n; }

est une écriture équivalente à

long carre(int n) { return n*n; }

et peut servir dans certains cas pointus de programmation générique. Pour en savoir plus, voir ../TrucsScouts/Syntaxe-unifiee-fonctions.html.

Le schéma ci-dessous montre la relation entre les divers éléments d'une λ et du foncteur correspondant. La correspondance, comme vous pouvez le constater, est directe, et le code généré dans chaque cas offre exactement les mêmes performances.

Maiontenant que les λ sont répandues dans la plupart des compilateurs, ce mécanisme est parmi les plus populaires de C++ 11.

Enrichissement avec C++ 14 – λ génériques

L'un des principaux atouts de C++ 14 sur le très innovateur C++ 11 est l'avènement de λ génériques. En effet, s'il est possible depuis C++ 11 d'exprimer par des λ des foncteurs de manière concise, comme :

Expressions λ Foncteurs équivalents
auto addint = [](int a, int b) {
   return a + b;
};
auto addX = [](X a, X b) {
   return a + b;
};
struct addint {
   auto operator()(int a, int b) const -> decltype(a+b) {
      return a + b;
   }
};	
struct addX {
   auto operator()(X a, X b) const -> decltype(a+b) {
      return a + b;
   }
};

...il devient possible avec C++ 14 d'exprimer une λ générique comme suit :

Expression λ Foncteur équivalent
auto add = [](auto a, auto b) {
   return a + b;
};
struct add {
   template <class T>
      auto operator()(T a, T b) const -> decltype(a+b) {
         return a + b;
      }
};

Ce faisant, la généricité s'adjoint à la simplicité d'écriture. Cette nouvelle façon de programmer change vraiment la pratique de la programmation de manière considérable.

Enrichissement avec C++ 14 – captures plus complètes

Avec C++ 11, les λ pouvaient capturer par valeur (par copie) ou par référence. Depuis C++ 14, il est possible de capturer par mouvement, et il est possible de renommer des variables lors d'une copie. Ce qui suit donne un exemple (académique et d'utilité limitée) ce que qu'il est possible d'exprimer dans un bloc de capture avec les λ maintenant :

#include <memory>
#include <iostream>
using namespace std;
struct X {
   int valeur = 3;
};
int main() {
   int n = 10;
   auto p = make_unique<X>();
   auto f = [p = std::move(p), niter = n, inc = -1]() mutable -> int {
      cout << p->valeur << ' ';
      return niter += inc;
   }();
}

J'ai délibérément limité les actions dans le bloc de capture à une utilisation de nouveaux mécanismes, les autres ayant déjà été expliqués précédemment. Ainsi :

Cet élargissement des capacités des expressions λ les rend encore plus polyvalentes.

Retourner une λ d'une fonction

Pour retourner une λ d'une fonction, il est d'usage en C++ 11 d'avoir recours à une std::function de signature appropriée, du fait que le type exact d'une λ est inconnu du programme; même si nous savions le type généré par un compilateur donné, ce type ne serait pas garanti pour les autres compilateurs, ou même pour les compilations ultérieures avec un même compilateur. Depuis C++ 14, les fonctions pouvant être de type auto, il est possible de retourner directement une lambda d'une fonction, dans la mesure où certaines règles d'hygiène sont respectées.

Exemples – λ immuables

Notre premier exemple sera celui d'une λ sans paramètres et retournant toujours true, un exemple banal :

Avec C++ 11 Avec C++ 14
std::function<bool()> tautologie() {
   return []{ return true; };
}
auto tautologie() {
   return []{ return true; };
}

Autre exemple simple, basé sur une fermeture : celui d'une λ capable d'ajouter une même quantité à plusieurs valeurs, une à la fois, telle qu'elle pourrait être utilisée dans un std::transform().

Avec C++ 11 Avec C++ 14
std::function<float(float)> ajouter(float montant) {
   return [montant](float x) { return x + montant; };
}
auto ajouter(float montant) {
   return [montant](float x) { return x + montant; };
}

Le recours à une copie dans la capture de la λ est normal ici, du fait que la λ sera retournée par la fonction; si une capture est faite par référence, il faut avoir la certitude que le référé existera encore après la fin de la fonction, ce qui exclut les variables locales. Ainsi, ce qui suit est dangereux et mène à un comportement indéfini :

// ... inclusions et using ...
std::function<int()> vilain(int n) { // un paramètre est une variable locale, à plus forte partie un paramètre passé par valeur
   return [&]() { return n; }; // oups! n a été capturé par référence
} // n décède ici... mais la λ retournée a une référence dessus!
int main() {
  auto f = danger(3);
  cout << f() << endl; // indefini : l'appel utilise une référence au paramètre n, qui est local à vilain
}

On pourrait se demander pourquoi du code aussi dangereux compilerait, mais il se trouve qu'il est parfois tout à fait raisonnable pour une λ de capturer une variable par référence. Par exemple :

// ... inclusions et using ...
template <class It, class T>
   T somme(It debut, It fin) {
      using value_type = typename iterator_traits<It>::value_type;
      T resultat = {};
      auto cumul = [&](const value_type &val) {
         resultat += val;
      };
      for_each(debut, fin, cumul);
      return resultat;
}

Évidemment, dans cet exemple, utiliser std::accumulate() aurait été préférable, mais il demeure clair que la capture de resultat par référence est une opération tout à fait légale.

Exemple – λ mutable

Il arrive que retourner une λ mutable soit l'action souhaitée. Par défaut, les variables capturées par valeur dans une λ sont considérées const lors de l'action de l'opérateur (). Par exemple, ceci est illégal :

int i = 3;
auto f = [=]() {
   return i++; // illégal, i est considéré const ici
};

Dans un tel cas, il faut qualifier la λ de mutable. Par exemple :

int i = 3;
auto f = [=]() mutable {
   return i++; // légal
};

Ceci peut par exemple servir à la mise en place d'un générateur de nombres séquentiels :

// ... includes et using ...
template <class T>
   function<T()> generer_sequence(T cur = {}) {
      return [=]() mutable { return cur++; }; }
   }
int main() {
   auto gen = generer_sequence(1.5); // gen générera 1.5, 2.5, 3.5, ...
   cout << gen() << endl;
   cout << gen() << endl;
   cout << gen() << endl;
}

Exemple – λ récursive d'une fonction

Cette section est fortement inspirée d'un texte de Sumant Tambe que vous trouverez sur http://cpptruths.blogspot.ca/2013/10/creating-recursive-lambdas-and.html, et qui explore d'autres techniques pour en arriver à résoudre le même problème. Je lui suis reconnaissant car j'ai vécu le même problème que lui quelques jours plus tard dans un tronçon subtil de mes travaux de doctorat, alors il m'a sûrement épargné quelques jours de recherche!

Pour qu'une λ soit récursive, il faut qu'elle soit nommée et placée dans une std::function ou dans une entité de fonctionnalité équivalente. Par exemple, ceci ne compilera pas :

// ... inclusions et using ...
int main() {
   auto fac = [](int n) {
      return n == 0 || n == 1? 1.0 : n * fac(n-1); // illégal: il faudrait connaître le type de fac ici, et on ne le connaît pas encore (auto ne suffit pas)
   };
   cout << fac(5) << endl;
}

Avec une std::function, tout fonctionne normalement...

// ... inclusions et using ...
int main() {
   function<double(int)> fac = [&](int n) {
      return n == 0 || n == 1? 1.0 : n * fac(n-1); // Ok
   };
   cout << fac(5) << endl;
}

Notez la capture par référence de fac elle-même, qui est nécessaire pour y faire référence, justement, à l'intérieur. Pour ce qui est de retourner une telle λ d'une fonction, par contre, c'est une autre histoire.

// ... inclusions et using ...
function<double(int)> generer_factorielle() {
   function<double(int)> fac = [&](int n) {
      return n == 0 || n == 1 ? 1.0 : n * fac(n-1);
   };
   return fac;
}
int main() {
   auto fac = generer_factorielle();
   cout << fac(5) << endl; // boum! Mais pourquoi?
}

Quel est le problème ici? Simplement, la variable fac dans generer_factorielle() capture une référence sur fac... qui est en fait une variable locale à la fonction generer_factorielle(), donc qui est détruite à la fin de cette fonction. Conséquemment, la variable fac de main() est une copie de la variable fac de generer_factorielle(), et cette copie utilise une référence à une variable qui n'existe plus.

Une solution est d'utiliser une écriture comprenant une λ dans une λ le code suit, après quoi vous trouverez des explications.

// ... inclusions et using ...
function<double(int)> generer_factorielle() {
   function<double(int)> fac = [](int n) {
      function<double(int)> impl = [&](int n) {
         return n == 0 || n == 1 ? 1.0 : n * impl(n-1);
      };
      return impl(n);
   };
   return fac;
}
int main() {
   auto fac = generer_factorielle();
   cout << fac(5) << endl; // et voilà!
}

Ici, la λ externe est placée dans fac, et cette dernière encapsule une λ interne nommée impl. Puisque la λ interne vit dans la λ externe, la référence sur impl dans impl demeure valide pendant une exécution de fac.

Si des états doivent persister pour la λ interne, il est d'usage de les capturer par copie dans la λ externe, quitte à qualifier le λ externe de mutable pour permettre à la λ interne de les manipuler sans problème. Notez que cela inclut tout particulièrement des références sur this dans une méthode d'instance.

Les IIFE Immediately-Invoked Function Expressions

Supposons qu'un objet doive être initialisé à l'aide de plusieurs opérations, et que cette initialisation soit locale, pas du type que l'on retrouve disséminées un peu partout dans le programme.

Il est possible de réaliser cette initialisation dans une fonction; cette approche fonctionne bien, mais demander d'introduire une nouvelle entité nommée (la fonction en question) dans le programme, ce qui est irritant quand il est clair que cette fonction n'existe que pour un seul cas d'utilisation, très local.

class X {
   // ... bla bla ...
};
X fonction_jetable_et_complexe() {
   // ... bla bla ...
}
int main() {
   const X obj = fonction_jetable_et_complexe();
   // ...
}

Utiliser une IIFE règle ce problème. L'idée est simple :

  • Plutôt que d'écrire et de nommer une fonction, écrivez une expression λ
  • Ne nommez pas la λ. Plutôt, appelez-la immédiatement
  • Laissez le compilater s'amuser à optimiser le tout. Il adorera
class X {
   // ... bla bla ...
};
int main() {
   const X obj = []() -> X {
      // ... code jetable et complexe
      // retournant un X correctement
      // initialisé
   }(); // on l'appelle immédiatement!
   // ...
}

La particularité d'une IIFE est d'être anonyme et appelée sur-le-champ. Utiliser cette technique pour initialiser un objet n'est que l'une de ses principales applications.

Surcharge de λ

Il est a priori impossible de surcharger une λ en C++. En effet, une seule version de l'opérateur () est générée pour chaque expression telle que celle proposée à droite, au sens où dans un cas comme celui-ci, le foncteur associé à la λ f n'expose qu'un seul opérateur (), soit int f::operator(int). Cependant, il est possible de contourner cette contrainte avec un peu d'ingéniosité, comme le montre cette technique attribuée (à ma connaissance, du moins) à Mathias Gaunard, et avec laquelle je suis tombé en contact à la lecture de l'article http://cpp-next.com/archive/2012/09/unifying-generic-functions-and-function-objects/ de Dave Abrahams.

auto f = [](int i) {
   return i + 1;
};

La technique en question va comme suit :

À titre d'exemple :

template <class F0, class F1>
   struct overload_set : F0, F1 {
      overload_set(F0 x0, F1 x1)
         : F0(x0), F1(x1)
      {
      }
      using F0::operator();
      using F1::operator();
   };
template <class F0, class F1>
   overload_set<F0,F1> overload(F1 f0, F2 f1) {
      return { f0,f1 };
   }
auto f = overload(
   [](){
      return 1;
   },
   [](int x){
      return x+1;
   }
);
int main() {
   int x = f();
   int y = f(2);
}

Ce faisant, il devient possible de combiner (par composition d'appels à overload()) autant de foncteurs et de λ que souhaité.

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !