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 herzustellen, das sich selbst zurückgibt.

• MSVC kompiliert das Programm und es wird ausgeführt
• gcc kompiliert das Programm und es gibt Fehler
• clang lehnt das Programm mit einer Meldung ab:

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

Welcher Compiler ist richtig? Gibt es eine statische Einschränkungsverletzung, 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 Sprachrechtsanwalts.

Update 3 : Die Frage ist nicht, ob es für ein Lambda legal ist, sich generell zurückzugeben, sondern ob es legal ist, diese spezielle Methode zu verwenden.

Verwandte Frage: C ++ Lambda gibt sich zurück .

Das Programm ist schlecht geformt (Klirren ist richtig) gemäß [dcl.spec.auto] / 9 :

Wenn der Name einer Entität mit einem nicht abgeleiteten Platzhaltertyp in einem Ausdruck angezeigt wird, ist das Programm fehlerhaft. Sobald eine nicht verworfene return-Anweisung in einer Funktion angezeigt 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 Lambda benötigen, ihn aber nicht benennen können. Es gibt aber auch andere Fälle, in denen der Versuch, solche rekursiven Lambdas zu erzwingen, funktionieren kann.

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 (z. B. TC). 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 ist, dass der innere Ausdruck self(self)nicht abhängig ist f1, sondern self(self, p)abhängig ist für f2. Wenn Ausdrücke nicht abhängig sind, können sie ... eifrig verwendet werden ( [temp.res] / 8 , z. B. wie static_assert(false)ist ein schwerer Fehler, unabhängig davon, ob die Vorlage, in der sie sich befindet, instanziiert ist oder nicht).

Denn f1ein Compiler (wie zum Beispiel Clang) kann versuchen, dies eifrig zu instanziieren. Sie kennen den abgeleiteten Typ des äußeren Lambdas, sobald Sie diesen ;Punkt #2oben erreicht haben (es ist der Typ des inneren Lambdas), aber wir versuchen, ihn früher zu verwenden (denken Sie an den Punkt #1) - wir versuchen es um es zu verwenden, während wir noch das innere Lambda analysieren, bevor wir wissen, um welchen Typ es sich tatsächlich handelt. Das läuft dcl.spec.auto/9 zuwider.

Doch für die f2, können wir nicht eifrig zu instanziiert versuchen, weil es abhängig ist. Wir können nur am Verwendungsort instanziieren, bis zu welchem ​​Punkt wir alles wissen.

Um so etwas wirklich zu machen, braucht man 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;
});

Bearbeiten : Es scheint einige Kontroversen darüber zu geben, ob diese Konstruktion gemäß der C ++ - Spezifikation streng gültig ist. Die vorherrschende Meinung scheint zu sein, dass es nicht gültig ist. Weitere Informationen finden Sie in den anderen Antworten. Der Rest dieser Antwort gilt, wenn die Konstruktion gültig ist; Der unten optimierte Code funktioniert mit MSVC ++ und gcc, und das OP hat weiteren modifizierten Code veröffentlicht, der auch mit clang funktioniert.

Dies ist ein undefiniertes Verhalten, da das innere Lambda den Parameter als selfReferenz erfasst , aber selfnach returnZeile 7 den Gültigkeitsbereich verlässt. Wenn das zurückgegebene Lambda später ausgeführt wird, greift es auf eine Referenz auf eine Variable zu, die den Gültigkeitsbereich verlassen hat.

#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 valgrindveranschaulicht 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 selbst als Referenz statt als Wert nimmt, wodurch unnötige Kopien vermieden und das Problem gelöst werden:

#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

TL; DR;

Klirren ist richtig.

Es sieht so aus, als ob der Abschnitt des Standards, der diese schlecht geformt macht, [dcl.spec.auto] p9 ist :

Wenn der Name einer Entität mit einem nicht abgeleiteten Platzhaltertyp in einem Ausdruck angezeigt wird, ist das Programm fehlerhaft. Sobald eine nicht verworfene return-Anweisung in einer Funktion angezeigt wurde, kann der aus dieser Anweisung abgeleitete return-Typ 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
}

- Beispiel beenden]

Originalarbeit durch

Wenn wir uns den Vorschlag A Vorschlag zum Hinzufügen eines Y-Kombinators zur Standardbibliothek ansehen , bietet er 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 Lambdas fördern keine Rekursion: Es gibt keine Möglichkeit, das Lambda-Objekt aus dem Hauptteil der Lambda-Funktion heraus zu referenzieren.

und es bezieht sich auf eine Diskussion, in der Richard Smith auf den Fehler anspielt, den Clang Ihnen gibt :

Ich denke, dies wäre besser als erstklassiges Sprachfeature. Ich hatte keine Zeit mehr für das Treffen vor Kona, aber ich wollte ein Papier schreiben, um einem Lambda einen Namen zu geben (der auf seinen eigenen Körper beschränkt ist):

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

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

Barry wies mich auf den Folgeantrag Rekursive Lambdas hin, der erklärt, warum dies nicht möglich ist, die dcl.spec.auto#9Einschränkung umgeht und auch Methoden zeigt, um dies heute ohne sie zu erreichen:

Lambdas sind ein nützliches Tool für das Refactoring von lokalem Code. Manchmal möchten wir das Lambda jedoch aus sich heraus verwenden, um entweder eine direkte Rekursion zu ermöglichen oder um die Schließung als Fortsetzung zu registrieren. Dies ist in aktuellem C ++ überraschend schwer zu erreichen.

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 automatischen Variablen wird erst abgeleitet, nachdem der Lambda-Ausdruck verarbeitet wurde, was bedeutet, dass der Lambda-Ausdruck nicht auf die Variable verweisen kann.

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 wird kompiliert, führt jedoch normalerweise zu einer Abstraktionsstrafe: Die Funktion std :: kann eine Speicherzuweisung verursachen, und der Aufruf des Lambda erfordert normalerweise einen indirekten Aufruf.

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

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

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

Gehen wir es wie ein Compiler durch (ein bisschen):

• Der Typ itist Lambda1mit einem Vorlagenaufrufoperator.
• it(it); löst die Instanziierung des Anrufbetreibers aus
• Der Rückgabetyp des Vorlagenaufrufoperators ist auto, daher müssen wir ihn ableiten.
• Wir geben ein Lambda zurück, das den ersten Parameter des Typs erfasst Lambda1.
• Dieses Lambda hat auch einen Anrufoperator, der den Typ des Aufrufs zurückgibt self(self)
• Hinweis: self(self)Genau damit haben wir begonnen!

Daher kann der Typ nicht abgeleitet werden.

Nun, Ihr Code funktioniert nicht. Aber das tut:

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; aber beide können 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 selfWert nach Wert nimmt, der innere Wert selfnach Referenz erfasst und nach outerAbschluss des Laufvorgangs zurückgegeben wird. Segfaulting ist also definitiv in Ordnung.

Die Reparatur:

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

Der Code bleibt 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;
};

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

Wir gehen es Zeile für Zeile durch. Zuerst erstellen wir __inner_lambda__Typ:

    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 dort nach - der Rückgabetyp ist self(self)oder __outer_lambda__(__outer_lambda__ const&). Aber wir sind gerade dabei, den Rückgabetyp von abzuleiten __outer_lambda__::operator()(__outer_lambda__).

Das darfst du nicht.

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

Und self(self)wird verwendet, bevor wir es abgeleitet haben. Schlecht geformtes Programm.

Wir können dies korrigieren, indem wir uns 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 ykombinator.

Es ist einfach genug, den Code in Bezug auf die Klassen neu zu schreiben, 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 herausgefordert ist.

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 Version mit vollständigen Vorlagen, die die Art und Weise widerspiegelt, in der das innere Lambda im Originalcode ein Element mit Vorlagen erfasst:

#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 denke, es ist diese Vorlage in der internen Maschinerie, die die formalen Regeln verbieten sollen. Wenn sie das ursprüngliche Konstrukt verbieten.