Lambda se retourne: est-ce légal?

Considérez ce programme assez inutile:

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self);
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

Fondamentalement, nous essayons de faire un lambda qui se retourne.

• MSVC compile le programme et il s'exécute
• gcc compile le programme, et il segmente les défauts
• clang rejette le programme avec un message:

  error: function 'operator()<(lambda at lam.cpp:6:13)>' with deduced return type cannot be used before it is defined

Quel compilateur a raison? Y a-t-il une violation de contrainte statique, UB ou aucun des deux?

Mettre à jour cette légère modification est acceptée par clang:

  auto it = [&](auto& self, auto b) {
          std::cout << (a + b) << std::endl;
          return [&](auto p) { return self(self,p); };
  };
  it(it,4)(6)(42)(77)(999);

Mise à jour 2 : Je comprends comment écrire un foncteur qui se renvoie lui-même, ou comment utiliser le combinateur Y, pour y parvenir. C'est plus une question de langue-avocat.

Mise à jour 3 : la question n'est pas de savoir s'il est légal pour un lambda de se retourner en général, mais de la légalité de cette manière spécifique de le faire.

Question connexe: C ++ lambda se renvoyant .

Le programme est mal formé (clang a raison) par [dcl.spec.auto] / 9 :

Si le nom d'une entité avec un type d'espace réservé non déduit apparaît dans une expression, le programme est mal formé. Une fois qu'une instruction de retour non supprimée a été vue dans une fonction, cependant, le type de retour déduit de cette instruction peut être utilisé dans le reste de la fonction, y compris dans d'autres instructions de retour.

Fondamentalement, la déduction du type de retour du lambda interne dépend de lui-même (l'entité nommée ici est l'opérateur d'appel) - vous devez donc fournir explicitement un type de retour. Dans ce cas particulier, c'est impossible, car vous avez besoin du type du lambda interne mais vous ne pouvez pas le nommer. Mais il y a d'autres cas où essayer de forcer des lambdas récursifs comme celui-ci peut fonctionner.

Même sans cela, vous avez une référence pendante .

Permettez-moi d'élaborer un peu plus, après avoir discuté avec quelqu'un de beaucoup plus intelligent (c.-à-d. TC) Il y a une différence importante entre le code original (légèrement réduit) et la nouvelle version proposée (également réduite):

auto f1 = [&](auto& self) {
  return [&](auto) { return self(self); } /* #1 */ ; /* #2 */
};
f1(f1)(0);

auto f2 = [&](auto& self, auto) {
  return [&](auto p) { return self(self,p); };
};
f2(f2, 0);

Et c'est que l'expression intérieure self(self)n'est pas dépendante pour f1, mais self(self, p)dépendante pour f2. Lorsque les expressions ne sont pas dépendantes, elles peuvent être utilisées ... avec empressement ( [temp.res] / 8 , par exemple comment static_assert(false)est une erreur matérielle, que le modèle dans lequel il se trouve soit instancié ou non).

Car f1, un compilateur (comme, disons, clang) peut essayer d'instancier cela avec empressement. Vous connaissez le type déduit du lambda externe une fois que vous y arrivez ;au point #2ci-dessus (c'est le type du lambda interne), mais nous essayons de l'utiliser plus tôt que cela (pensez-y comme au point #1) - nous essayons pour l'utiliser pendant que nous analysons encore le lambda interne, avant de savoir quel est son type. Cela va à l'encontre de dcl.spec.auto/9.

Cependant, pour f2, nous ne pouvons pas essayer d'instancier avec empressement, car c'est dépendant. Nous ne pouvons instancier qu'au point d'utilisation, à partir duquel nous savons tout.

Pour vraiment faire quelque chose comme ça, vous avez besoin d'un combinateur y . La mise en œuvre du papier:

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

Et ce que vous voulez, c'est:

auto it = y_combinator([&](auto self, auto b){
    std::cout << (a + b) << std::endl;
    return self;
});

Edit : Il semble y avoir une controverse quant à savoir si cette construction est strictement valide selon la spécification C ++. L'opinion dominante semble être qu'elle n'est pas valable. Voir les autres réponses pour une discussion plus approfondie. Le reste de cette réponse s'applique si la construction est valide; le code modifié ci-dessous fonctionne avec MSVC ++ et gcc, et l'OP a publié un code modifié qui fonctionne également avec clang.

C'est un comportement indéfini, car le lambda interne capture le paramètre selfpar référence, mais selfsort de la portée après la returnligne 7. Ainsi, lorsque le lambda retourné est exécuté plus tard, il accède à une référence à une variable qui est hors de portée.

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self); // <-- using reference to 'self'
      };
  };
  it(it)(4)(6)(42)(77)(999); // <-- 'self' is now out of scope
}

L'exécution du programme avec valgrindillustre ceci:

==5485== Memcheck, a memory error detector
==5485== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5485== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5485== Command: ./test
==5485== 
9
==5485== Use of uninitialised value of size 8
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485== 
==5485== Invalid read of size 4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  Address 0x4fefffdc4 is not stack'd, malloc'd or (recently) free'd
==5485== 
==5485== 
==5485== Process terminating with default action of signal 11 (SIGSEGV)
==5485==  Access not within mapped region at address 0x4FEFFFDC4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  If you believe this happened as a result of a stack
==5485==  overflow in your program's main thread (unlikely but
==5485==  possible), you can try to increase the size of the
==5485==  main thread stack using the --main-stacksize= flag.
==5485==  The main thread stack size used in this run was 8388608.

Au lieu de cela, vous pouvez changer le lambda externe pour prendre self par référence au lieu de par valeur, évitant ainsi un tas de copies inutiles et résolvant également le problème:

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto& self) { // <-- self is now a reference
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self);
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

Cela marche:

==5492== Memcheck, a memory error detector
==5492== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5492== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5492== Command: ./test
==5492== 
9
11
47
82
1004

TL, DR;

clang est correct.

Il semble que la section de la norme qui rend cette mauvaise forme est [dcl.spec.auto] p9 :

Si le nom d'une entité avec un type d'espace réservé non déduit apparaît dans une expression, le programme est mal formé. Une fois qu'une instruction de retour non ignorée a été vue dans une fonction, cependant, le type de retour déduit de cette instruction peut être utilisé dans le reste de la fonction, y compris dans d'autres instructions de retour. [ Exemple:

auto n = n; // error, n’s initializer refers to n
auto f();
void g() { &f; } // error, f’s return type is unknown

auto sum(int i) {
  if (i == 1)
    return i; // sum’s return type is int
  else
    return sum(i-1)+i; // OK, sum’s return type has been deduced
}

—End exemple]

Travail original à travers

Si nous examinons la proposition A Proposal to Add Y Combinator to the Standard Library, elle fournit une solution de travail:

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

et il dit explicitement que votre exemple n'est pas possible:

Les lambdas C ++ 11/14 n'encouragent pas la récursivité: il n'y a aucun moyen de référencer l'objet lambda à partir du corps de la fonction lambda.

et il fait référence à une discussion dans laquelle Richard Smith fait allusion à l'erreur que le bruit vous donne :

Je pense que ce serait mieux en tant que fonctionnalité de langage de première classe. J'ai manqué de temps pour la réunion pré-Kona, mais j'avais l'intention d'écrire un papier pour permettre de donner un nom à un lambda (adapté à son propre corps):

auto x = []fib(int a) { return a > 1 ? fib(a - 1) + fib(a - 2) : a; };

Ici, «fib» est l'équivalent du lambda * this (avec quelques règles spéciales ennuyeuses pour permettre à cela de fonctionner bien que le type de fermeture du lambda soit incomplet).

Barry m'a indiqué la proposition de suivi Lambdas récursives qui explique pourquoi cela n'est pas possible et qui contourne la dcl.spec.auto#9restriction et montre également des méthodes pour y parvenir aujourd'hui sans elle:

Les lambdas sont un outil utile pour la refactorisation du code local. Cependant, nous voulons parfois utiliser le lambda de l'intérieur de lui-même, soit pour permettre la récursivité directe, soit pour permettre à la fermeture d'être enregistrée comme une continuation. Ceci est étonnamment difficile à bien accomplir dans le C ++ actuel.

Exemple:

  void read(Socket sock, OutputBuffer buff) {
  sock.readsome([&] (Data data) {
  buff.append(data);
  sock.readsome(/*current lambda*/);
}).get();

}

Une tentative naturelle de référencer un lambda à partir de lui-même consiste à le stocker dans une variable et à capturer cette variable par référence:

 auto on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

Cependant, cela n'est pas possible en raison d'une circularité sémantique : le type de la variable auto n'est déduit qu'après le traitement de l'expression lambda, ce qui signifie que l'expression lambda ne peut pas référencer la variable.

Une autre approche naturelle consiste à utiliser une fonction std :::

 std::function on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

Cette approche compile, mais introduit généralement une pénalité d'abstraction: la fonction std :: peut entraîner une allocation de mémoire et l'invocation du lambda nécessitera généralement un appel indirect.

Pour une solution sans surcoût, il n'y a souvent pas de meilleure approche que de définir explicitement un type de classe locale.

Il semble que clang a raison. Prenons un exemple simplifié:

auto it = [](auto& self) {
    return [&self]() {
      return self(self);
    };
};
it(it);

Passons en revue comme un compilateur (un peu):

• Le type de itest Lambda1avec un opérateur d'appel de modèle.
• it(it); déclenche l'instanciation de l'opérateur d'appel
• Le type de retour de l'opérateur d'appel de modèle est auto, nous devons donc le déduire.
• Nous retournons un lambda capturant le premier paramètre de type Lambda1.
• Ce lambda a également un opérateur d'appel qui retourne le type de l'appel self(self)
• Remarque: self(self)c'est exactement ce avec quoi nous avons commencé!

En tant que tel, le type ne peut pas être déduit.

Eh bien, votre code ne fonctionne pas. Mais cela fait:

template<class F>
struct ycombinator {
  F f;
  template<class...Args>
  auto operator()(Args&&...args){
    return f(f, std::forward<Args>(args)...);
  }
};
template<class F>
ycombinator(F) -> ycombinator<F>;

Code de test:

ycombinator bob = {[x=0](auto&& self)mutable{
  std::cout << ++x << "\n";
  ycombinator ret = {self};
  return ret;
}};

bob()()(); // prints 1 2 3

Votre code est à la fois UB et mal formé, aucun diagnostic n'est requis. Ce qui est drôle; mais les deux peuvent être fixés indépendamment.

Tout d'abord, l'UB:

auto it = [&](auto self) { // outer
  return [&](auto b) { // inner
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};
it(it)(4)(5)(6);

c'est UB parce que externe prend selfpar valeur, puis interne capture selfpar référence, puis continue à le renvoyer une fois l' outerexécution terminée. Donc, le segfaulting est définitivement ok.

Le correctif:

[&](auto self) {
  return [self,&a](auto b) {
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};

Le code reste mal formé. Pour voir cela, nous pouvons développer les lambdas:

struct __outer_lambda__ {
  template<class T>
  auto operator()(T self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      T self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};
__outer_lambda__ it{a};
it(it);

cela instancie __outer_lambda__::operator()<__outer_lambda__>:

  template<>
  auto __outer_lambda__::operator()(__outer_lambda__ self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};

Nous devons donc ensuite déterminer le type de retour de __outer_lambda__::operator().

Nous le parcourons ligne par ligne. Nous créons d'abord le __inner_lambda__type:

    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };

Maintenant, regardez là - son type de retour est self(self), ou __outer_lambda__(__outer_lambda__ const&). Mais nous sommes en train d'essayer de déduire le type de retour de __outer_lambda__::operator()(__outer_lambda__).

Vous n'êtes pas autorisé à faire ça.

Alors qu'en fait le type de retour de __outer_lambda__::operator()(__outer_lambda__)ne dépend pas réellement du type de retour de __inner_lambda__::operator()(int), C ++ ne se soucie pas de la déduction des types de retour; il vérifie simplement le code ligne par ligne.

Et self(self)est utilisé avant de le déduire. Programme mal formé.

Nous pouvons corriger cela en cachant self(self)à plus tard:

template<class A, class B>
struct second_type_helper { using result=B; };

template<class A, class B>
using second_type = typename second_type_helper<A,B>::result;

int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [self,&a](auto b) {
        std::cout << (a + b) << std::endl;
        return self(second_type<decltype(b), decltype(self)&>(self) );
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

et maintenant le code est correct et compile. Mais je pense que c'est un peu de hack; utilisez simplement le ycombinator.

Il est assez facile de réécrire le code en termes de classes qu'un compilateur générerait, ou plutôt devrait, générer pour les expressions lambda.

Lorsque cela est fait, il est clair que le problème principal est juste la référence pendante, et qu'un compilateur qui n'accepte pas le code est quelque peu contesté dans le département lambda.

La réécriture montre qu'il n'y a pas de dépendances circulaires.

#include <iostream>

struct Outer
{
    int& a;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner( a, self );    //! Original code has dangling ref here.
    }

    struct Inner
    {
        int& a;
        Outer& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Outer& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

Une version entièrement basée sur un modèle pour refléter la façon dont le lambda interne dans le code d'origine capture un élément qui est d'un type basé sur un modèle:

#include <iostream>

struct Outer
{
    int& a;

    template< class > class Inner;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner<Arg>( a, self );    //! Original code has dangling ref here.
    }

    template< class Self >
    struct Inner
    {
        int& a;
        Self& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Self& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

Je suppose que c'est ce modèle dans le mécanisme interne, que les règles formelles sont destinées à interdire. S'ils interdisent la construction d'origine.