Lambda powraca: czy to legalne?

Rozważ ten dość bezużyteczny program:

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

Zasadniczo próbujemy utworzyć lambdę, która sama się zwraca.

• MSVC kompiluje program i działa
• gcc kompiluje program i powoduje jego segfaults
• clang odrzuca program z komunikatem:

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

Który kompilator ma rację? Czy istnieje naruszenie statycznego ograniczenia, UB, czy żadne z nich?

Zaktualizuj tę niewielką modyfikację zaakceptowaną przez 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);

Aktualizacja 2 : Rozumiem, jak napisać funktor, który sam się zwraca, lub jak użyć kombinatora Y, aby to osiągnąć. To jest bardziej kwestia językowo-prawnicza.

Aktualizacja 3 : nie chodzi o to, czy lambda powraca w ogóle, ale o legalność tego konkretnego sposobu robienia tego.

Powiązane pytanie: lambda w C ++ zwraca samą siebie .

Program jest źle sformułowany (clang is right) per [dcl.spec.auto] / 9 :

Jeśli w wyrażeniu pojawia się nazwa encji z nieredukowanym typem symbolu zastępczego, program jest źle sformułowany. Jednak po zauważeniu w funkcji niezrzuconej instrukcji return, typ zwracany wyprowadzony z tej instrukcji może być użyty w pozostałej części funkcji, w tym w innych instrukcjach return.

Zasadniczo, odliczenie typu zwracanego wewnętrznej lambdy zależy od siebie (jednostka, o której tu mowa, jest operatorem wywołania) - musisz więc jawnie podać typ zwracany. W tym konkretnym przypadku jest to niemożliwe, ponieważ potrzebujesz typu wewnętrznej lambdy, ale nie możesz jej nazwać. Ale są inne przypadki, w których próba wymuszenia rekurencyjnych lambd, takich jak ta, może zadziałać.

Nawet bez tego masz zwisające odniesienie .

Pozwólcie, że rozwinę trochę więcej, po omówieniu z kimś znacznie mądrzejszym (tj. TC). Istnieje ważna różnica między oryginalnym kodem (nieco zmniejszona) a proponowaną nową wersją (również zmniejszoną):

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

I to jest to, że wewnętrzna ekspresja self(self)nie jest zależna od f1, ale self(self, p)jest zależna od f2. Gdy wyrażenia są niezależne, można ich używać ... ochoczo ( [temp.res] / 8 , np. Jakistatic_assert(false) jest twardy błąd niezależnie od tego, czy szablon, w którym się znajduje, jest instancji, czy nie).

Dla f1, kompilatora (jak, powiedzmy, dzyń) może próbować wystąpienia tego chętnie. Znasz wydedukowany typ zewnętrznej lambdy, gdy dojdziesz do tego ;w punkcie #2powyżej (jest to typ wewnętrznej lambdy), ale próbujemy użyć go wcześniej (pomyśl o tym jak w punkcie #1) - próbujemy używać go, gdy nadal analizujemy wewnętrzną lambdę, zanim dowiemy się, jaki jest jej typ. To jest sprzeczne z dcl.spec.auto/9.

Jednak f2nie możemy próbować gorliwie tworzyć instancji, ponieważ jest to zależne. Instancję możemy utworzyć tylko w momencie użycia, kiedy to wiemy już wszystko.

Aby naprawdę zrobić coś takiego, potrzebujesz kombinatora y . Realizacja z artykułu:

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

A czego chcesz to:

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

Edycja : Wydaje się, że istnieją pewne kontrowersje dotyczące tego, czy ta konstrukcja jest ściśle poprawna zgodnie ze specyfikacją C ++. Przeważająca opinia wydaje się być nieprawidłowa. Zobacz inne odpowiedzi, aby uzyskać dokładniejszą dyskusję. Pozostała część odpowiedzi ma zastosowanie, jeśli konstrukcja jest prawidłowa; ulepszony kod poniżej działa z MSVC ++ i gcc, a OP opublikował dodatkowo zmodyfikowany kod, który działa również z clang.

Jest to niezdefiniowane zachowanie, ponieważ wewnętrzna lambda przechwytuje parametr selfprzez odniesienie, ale selfwychodzi poza zakres po returnlinii 7. Zatem, gdy zwrócona lambda jest wykonywana później, uzyskuje dostęp do odniesienia do zmiennej, która wyszła poza zakres.

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

Uruchomienie programu z valgrindilustruje to:

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

Zamiast tego możesz zmienić zewnętrzną lambdę, aby przyjmowała siebie przez odniesienie zamiast według wartości, unikając w ten sposób zbędnych kopii, a także rozwiązując 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);
}

To działa:

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

brzęk jest poprawny.

Wygląda na to, że sekcja standardu, która sprawia, że ​​ten źle sformułowany jest to [dcl.spec.auto] p9 :

Jeśli w wyrażeniu pojawia się nazwa encji z nieredukowanym typem symbolu zastępczego, program jest źle sformułowany. Jednak po zauważeniu w funkcji niezrzuconej instrukcji return, typ zwracany wyprowadzony z tej instrukcji może być użyty w pozostałej części funkcji, w tym w innych instrukcjach return. [Przykład:

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
}

- koniec przykładu]

Oryginalna praca

Jeśli spojrzymy na propozycję, aby dodać Y Combinator do biblioteki standardowej , zapewni ona działające rozwiązanie:

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

i wyraźnie mówi, że twój przykład nie jest możliwy:

Lambdy w języku C ++ 11/14 nie zachęcają do rekurencji: nie ma możliwości odniesienia się do obiektu lambda z treści funkcji lambda.

i odwołuje się do dyskusji, w której Richard Smith nawiązuje do błędu, który daje ci dzwonek :

Myślę, że byłoby to lepsze jako funkcja języka pierwszej klasy. Zabrakło mi czasu na spotkanie przed Kona, ale zamierzałem napisać artykuł, który pozwoli nadać lambdzie nazwę (w zakresie jej własnego ciała):

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

W tym przypadku „fib” jest odpowiednikiem lambda * this (z pewnymi irytującymi specjalnymi regułami, które pozwalają na to, mimo że typ zamknięcia lambda jest niepełny).

Barry wskazał mi kolejną propozycję Lambdy rekurencyjne, która wyjaśnia, dlaczego nie jest to możliwe i działa wokół dcl.spec.auto#9ograniczenia, a także pokazuje metody osiągnięcia tego celu dzisiaj bez niego:

Lambdy są użytecznym narzędziem do lokalnego refaktoryzacji kodu. Czasami jednak chcemy użyć lambda z samego siebie, aby umożliwić bezpośrednią rekursję lub zezwolić na zarejestrowanie zamknięcia jako kontynuacji. Jest to zaskakująco trudne do osiągnięcia w obecnym C ++.

Przykład:

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

}

Naturalną próbą odniesienia do lambdy z samej siebie jest zapisanie jej w zmiennej i przechwycenie tej zmiennej przez odniesienie:

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

Nie jest to jednak możliwe ze względu na semantyczną cykliczność : typ zmiennej auto nie jest wydedukowany, dopóki nie zostanie przetworzone wyrażenie lambda, co oznacza, że ​​wyrażenie lambda nie może odwoływać się do zmiennej.

Innym naturalnym podejściem jest użycie funkcji std :::

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

Takie podejście jest kompilowane, ale zazwyczaj wprowadza karę za abstrakcję: funkcja std :: może spowodować alokację pamięci, a wywołanie lambda będzie zazwyczaj wymagało wywołania pośredniego.

W przypadku rozwiązania z zerowym narzutem często nie ma lepszego podejścia niż jawne zdefiniowanie typu klasy lokalnej.

Wygląda na to, że brzęk ma rację. Rozważmy uproszczony przykład:

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

Przejdźmy przez to jak kompilator (trochę):

• Typ itjest Lambda1z operatorem wywołania szablonu.
• it(it); wyzwala wystąpienie operatora połączenia
• Typ zwracany przez operatora wywołania szablonu to auto, więc musimy to wydedukować.
• Zwracamy lambdę przechwytującą pierwszy parametr typu Lambda1.
• Ta lambda również ma operator wywołania, który zwraca typ wywołania self(self)
• Uwaga: self(self)to jest dokładnie to, od czego zaczęliśmy!

W związku z tym nie można wywnioskować typu.

Twój kod nie działa. Ale to robi:

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

Kod testowy:

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

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

Twój kod jest zarówno UB, jak i źle sformułowany, nie jest wymagana diagnostyka. Co jest zabawne; ale oba można naprawić niezależnie.

Po pierwsze, UB:

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

to jest UB, ponieważ zewnętrzny przyjmuje selfwartość, a następnie wewnętrzny przechwytuje selfprzez odniesienie, a następnie zwraca go po outerzakończeniu działania. Więc segfaulting jest zdecydowanie w porządku.

Poprawka:

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

Kod pozostaje źle sformułowany. Aby to zobaczyć, możemy rozszerzyć lambdy:

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

to tworzy wystąpienie __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;
};

Następnie musimy określić typ zwracania __outer_lambda__::operator().

Przechodzimy przez to linijka po linijce. Najpierw tworzymy __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;
    };

A teraz spójrz tam - jego typ zwracany to self(self)lub __outer_lambda__(__outer_lambda__ const&). Ale jesteśmy w trakcie próby ustalenia zwracanego typu __outer_lambda__::operator()(__outer_lambda__).

Nie możesz tego zrobić.

Chociaż w rzeczywistości zwracany typ __outer_lambda__::operator()(__outer_lambda__)nie jest w rzeczywistości zależny od zwracanego typu __inner_lambda__::operator()(int), C ++ nie przejmuje się dedukowaniem zwracanych typów; po prostu sprawdza kod linia po linii.

I self(self)jest używany, zanim go wydedukowaliśmy. Źle ukształtowany program.

Możemy to załatać, ukrywając na self(self)później:

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

a teraz kod jest poprawny i kompiluje się. Ale myślę, że to trochę hack; po prostu użyj ycombinator.

Dość łatwo jest przepisać kod pod kątem klas, które kompilator wygenerowałby lub raczej powinien wygenerować dla wyrażeń lambda.

Kiedy to się skończy, staje się jasne, że głównym problemem jest tylko wiszące odniesienie, a kompilator, który nie akceptuje kodu, jest nieco trudniejszy w dziale lambda.

Przepisanie pokazuje, że nie ma zależności cyklicznych.

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

Wersja w pełni oparta na szablonie, odzwierciedlająca sposób, w jaki wewnętrzna lambda w oryginalnym kodzie przechwytuje element typu szablonowego:

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

Wydaje mi się, że jest to szablonowanie w wewnętrznej maszynerii, którego formalne reguły mają zabraniać. Jeśli zabraniają oryginalnej konstrukcji.