wake-up-neo.com

Lambda kehrt zurück: Ist das legal?

Betrachten Sie dieses ziemlich nutzlose Programm:

#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);
}

Grundsätzlich versuchen wir, ein Lambda zu erzeugen, das sich selbst zurückgibt.

  • MSVC kompiliert das Programm und es wird ausgeführt
  • gcc kompiliert das Programm und es schlägt fehl
  • clang weist das Programm mit einer Meldung zurück:

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

Welcher Compiler ist richtig? Liegt eine statische Einschränkungsverletzung vor, UB, oder keine?

Update Diese geringfügige Änderung wird von clang akzeptiert:

  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);

Update 2 : Ich verstehe, wie man einen Funktor schreibt, der sich selbst zurückgibt, oder wie man den Y-Kombinator verwendet, um dies zu erreichen. Dies ist eher eine Frage des Sprachjuristen.

Update 3 : die Frage ist nicht ob es legal ist, dass ein Lambda sich im Allgemeinen selbst zurückgibt, aber über das Legalität dieser spezifischen Art, dies zu tun.

Verwandte Frage: C++ - Lambda, das sich selbst zurückgibt .

121
n.m.

Das Programm ist schlecht (klingelt ist richtig) per [dcl.spec.auto]/9 :

Wenn der Name einer Entität mit einem nicht reduzierten Platzhaltertyp in einem Ausdruck angezeigt wird, ist das Programm falsch aufgebaut. Sobald eine nicht verworfene return-Anweisung in einer Funktion gefunden wurde, kann der aus dieser Anweisung abgeleitete return-Typ im Rest der Funktion verwendet werden, auch in anderen return-Anweisungen.

Grundsätzlich hängt der Abzug des Rückgabetyps des inneren Lambda von sich selbst ab (die hier genannte Entität ist der Aufrufoperator) - Sie müssen also explizit einen Rückgabetyp angeben. In diesem speziellen Fall ist das unmöglich, da Sie den Typ des inneren Lambdas benötigen, ihn aber nicht benennen können. Aber es gibt auch andere Fälle, in denen versucht wird, rekursive Lambdas wie diese zu erzwingen, die funktionieren können.

Auch ohne das haben Sie eine baumelnde Referenz .


Lassen Sie mich noch etwas näher darauf eingehen, nachdem ich mit jemandem gesprochen habe, der viel schlauer ist (d. H. T.C.). Es gibt einen wichtigen Unterschied zwischen dem ursprünglichen Code (leicht reduziert) und der vorgeschlagenen neuen Version (ebenfalls reduziert):

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);

Und das heißt, der innere Ausdruck self(self) ist nicht abhängig von f1, Sondern self(self, p) ist abhängig von f2. Wenn Ausdrücke nicht abhängig sind, können sie ... eifrig ( [temp.res]/8 verwendet werden, z. B. wie static_assert(false) ein schwerer Fehler ist, unabhängig davon, ob die Vorlage es ist findet sich in instanziiert oder nicht).

Für f1 Kann ein Compiler (wie z. B. Clang) versuchen, dies eifrig zu instanziieren. Sie kennen den abgeleiteten Typ des äußeren Lambda, sobald Sie diesen ; Bei Punkt #2 Oben erreicht haben (es ist der Typ des inneren Lambda), aber wir versuchen, ihn früher zu verwenden ( Betrachten Sie es als Punkt #1) - wir versuchen es zu verwenden, während wir noch das innere Lambda analysieren, bevor wir wissen, was es eigentlich ist. Das verstößt gegen dcl.spec.auto/9.

Für f2 Können wir jedoch nicht versuchen, eifrig zu instanziieren, da dies abhängig ist. Wir können nur an der Verwendungsstelle instanziieren, an welcher Stelle wir alles wissen.


Um so etwas wirklich zu tun, benötigen Sie einen y-Kombinator . Die Umsetzung aus dem 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));
}

Und was Sie wollen, ist:

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

Edit : Es scheint einige Kontroversen darüber zu geben, ob diese Konstruktion streng gültig ist pro die C++ Spezifikation. Die vorherrschende Meinung scheint zu sein, dass es nicht gültig ist. In den anderen Antworten finden Sie eine ausführlichere Diskussion. Der Rest dieser Antwort gilt wenn die Konstruktion ist gültig; Der nachstehende optimierte Code funktioniert mit MSVC++ und gcc, und das OP hat weiteren modifizierten Code veröffentlicht, der auch mit clang funktioniert.

Dies ist undefiniertes Verhalten, da das innere Lambda den Parameter self als Referenz erfasst, aber self nach return in Zeile 7 den Gültigkeitsbereich verlässt. Wenn also das Lambda zurückgegeben wird Wird es später ausgeführt, greift es auf einen Verweis auf eine Variable zu, die außerhalb des Gültigkeitsbereichs liegt.

#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
}

Das Ausführen des Programms mit valgrind veranschaulicht dies:

==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.

Stattdessen können Sie das äußere Lambda so ändern, dass es sich nach Referenz und nicht nach Wert richtet. Auf diese Weise vermeiden Sie unnötige Kopien und lösen das Problem:

#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);
}

Das funktioniert:

==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
35
TypeIA

TL; DR;

klirren ist richtig.

Es sieht so aus, als wäre der Abschnitt des Standards, der diese Fehlform macht, [dcl.spec.auto] p9 :

Wenn der Name einer Entität mit einem nicht reduzierten Platzhaltertyp in einem Ausdruck vorkommt, ist das Programm fehlerhaft. Sobald eine nicht verworfene return-Anweisung vorliegt In einer Funktion kann der aus dieser Anweisung abgeleitete Rückgabetyp jedoch im Rest der Funktion verwendet werden, auch in anderen return-Anweisungen. [Beispiel:

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 Beispiel]

Originelle Arbeit durch

Wenn wir uns den Vorschlag ansehen Ein Vorschlag zum Hinzufügen von Y Combinator zur Standardbibliothek er bietet eine funktionierende Lösung:

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));
}

und es heißt ausdrücklich, dass Ihr Beispiel nicht möglich ist:

C++ 11/14-Lambda fördern keine Rekursion: Es gibt keine Möglichkeit, das Lambda-Objekt aus dem Körper der Lambda-Funktion zu referenzieren.

und es verweist auf ein eine Diskussion, in der Richard Smith auf den Irrtum anspielt, den das Klingen Ihnen macht :

Ich denke, das wäre besser als erstklassiges Sprachfeature. Ich hatte keine Zeit mehr für das Pre-Kona-Meeting, aber ich wollte ein Papier schreiben, um einem Lambda einen Namen zu geben (der sich auf seinen eigenen Körper bezieht):

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

Hier ist 'fib' das Äquivalent des Lambdas * this (mit einigen ärgerlichen Sonderregeln, damit dies funktioniert, obwohl der Verschlusstyp des Lambdas unvollständig ist).

Barry verwies mich auf den Folgeantrag Recursive Lambdas , der erklärt, warum dies nicht möglich ist und um das dcl.spec.auto#9 Einschränkung und zeigt auch Methoden, um dies heute ohne es zu erreichen:

Lambdas sind ein nützliches Werkzeug für das Refactoring von lokalem Code. Manchmal möchten wir jedoch das Lambda aus sich selbst heraus verwenden, um entweder eine direkte Rekursion zu ermöglichen oder um zu ermöglichen, dass der Abschluss als Fortsetzung registriert wird. Dies ist in aktuellem C++ überraschend schwer zu bewerkstelligen.

Beispiel:

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

}

Ein natürlicher Versuch, ein Lambda von sich aus zu referenzieren, besteht darin, es in einer Variablen zu speichern und diese Variable durch Referenz zu erfassen:

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

Dies ist jedoch aufgrund einer semantischen Zirkularität nicht möglich : Der Typ der Auto-Variablen wird erst nach der Verarbeitung des Lambda-Ausdrucks abgeleitet, das heißt Der Lambda-Ausdruck kann nicht auf die Variable verweisen.

Ein anderer natürlicher Ansatz ist die Verwendung einer std :: -Funktion:

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

Dieser Ansatz kompiliert, führt jedoch in der Regel eine Abstraktionsstrafe ein: Für die Funktion std :: ist möglicherweise eine Speicherzuweisung erforderlich, und für den Aufruf des Lambda ist in der Regel ein indirekter Aufruf erforderlich.

Für eine Zero-Overhead-Lösung gibt es oft keinen besseren Ansatz als die explizite Definition eines lokalen Klassentyps.

21
Shafik Yaghmour

Es scheint, als ob Klirren richtig ist. Betrachten Sie ein vereinfachtes Beispiel:

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

Lass es uns wie einen Compiler durchgehen (ein bisschen):

  • Der Typ von it ist Lambda1 Mit einem Vorlagenaufrufoperator.
  • it(it); löst die Instanziierung des Anrufbetreibers aus
  • Der Rückgabetyp des Operator für Vorlagenaufrufe ist auto, daher müssen wir ihn herleiten.
  • Wir geben ein Lambda zurück, das den ersten Parameter vom Typ Lambda1 Erfasst.
  • Dieses Lambda hat auch einen Aufrufoperator, der den Typ des Aufrufs self(self) zurückgibt.
  • Hinweis: self(self) ist genau das, womit wir begonnen haben!

Daher kann der Typ nicht abgeleitet werden.

13
Rakete1111

Ihr Code funktioniert nicht. Aber das macht:

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>;

Testcode:

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

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

Ihr Code ist sowohl UB als auch schlecht geformt, keine Diagnose erforderlich. Welches ist lustig; beides kann aber unabhängig voneinander behoben werden.

Erstens, die UB:

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

dies ist UB, da der äußere Wert self nach Wert nimmt und der innere Wert self nach Verweis aufnimmt und ihn dann zurückgibt, nachdem outer die Ausführung beendet hat. Segfaulting ist also auf jeden Fall in Ordnung.

Die Reparatur:

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

Der Code bleibt ist schlecht geformt. Um dies zu sehen, können wir die Lambdas erweitern:

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);

dies instanziiert __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;
};

Als nächstes müssen wir den Rückgabetyp von __outer_lambda__::operator() bestimmen.

Wir gehen es Zeile für Zeile durch. Zuerst erstellen wir den Typ __inner_lambda__:

    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;
    };

Schauen Sie sich das an - der Rückgabetyp ist self(self) oder __outer_lambda__(__outer_lambda__ const&). Aber wir sind gerade dabei, den Rückgabetyp von __outer_lambda__::operator()(__outer_lambda__) abzuleiten.

Das darfst du nicht.

Während der Rückgabetyp von __outer_lambda__::operator()(__outer_lambda__) tatsächlich nicht vom Rückgabetyp von __inner_lambda__::operator()(int) abhängt, ist es C++ egal, wann Rückgabetypen abgeleitet werden. es überprüft einfach den Code Zeile für Zeile.

Und self(self) wird verwendet, bevor wir daraus geschlossen haben. Schlecht geformtes Programm.

Wir können dies korrigieren, indem wir self(self) bis später verstecken:

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);
}

und jetzt ist der Code korrekt und kompiliert. Aber ich denke, das ist ein bisschen Hack; benutze einfach den ycombinator.

Es ist einfach genug, den Code in Bezug auf die Klassen umzuschreiben, die ein Compiler für die Lambda-Ausdrücke generieren würde oder sollte.

Wenn das erledigt ist, ist es klar, dass das Hauptproblem nur die baumelnde Referenz ist und dass ein Compiler, der den Code nicht akzeptiert, in der Lambda-Abteilung etwas in Frage gestellt wird.

Das Umschreiben zeigt, dass es keine zirkulären Abhängigkeiten gibt.

#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);
}

Eine vollständig mit Vorlagen versehene Version, die die Art und Weise widerspiegelt, in der das innere Lambda im Originalcode ein Element erfasst, das mit Vorlagen versehen ist:

#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);
}

Ich vermute, dass es diese Vorlage in der internen Maschinerie ist, die die formalen Regeln verbieten sollen. Wenn sie das ursprüngliche Konstrukt verbieten.