Lambda kembali sendiri: apakah ini legal?

Pertimbangkan program yang cukup tidak berguna ini:

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

Pada dasarnya kami mencoba membuat lambda yang kembali dengan sendirinya.

• MSVC mengkompilasi program, dan menjalankannya
• gcc mengkompilasi program, dan itu segfault
• clang menolak program dengan pesan:

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

Kompiler mana yang benar? Apakah ada pelanggaran kendala statis, UB, atau tidak keduanya?

Perbarui sedikit modifikasi ini diterima oleh dentang:

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

Pembaruan 2 : Saya mengerti bagaimana menulis sebuah functor yang mengembalikan dirinya sendiri, atau bagaimana menggunakan kombinator Y, untuk mencapai ini. Ini lebih merupakan pertanyaan pengacara bahasa.

Pembaruan 3 : pertanyaannya bukanlah apakah legal bagi lambda untuk mengembalikan dirinya sendiri secara umum, tetapi tentang legalitas cara khusus untuk melakukan ini.

Pertanyaan terkait: C ++ lambda kembali sendiri .

Program tidak berbentuk (clang is right) menurut [dcl.spec.auto] / 9 :

Jika nama entitas dengan jenis tempat penampung yang tidak dikurangi muncul dalam ekspresi, programnya salah bentuk. Namun, setelah pernyataan pengembalian yang tidak dibuang telah terlihat dalam suatu fungsi, jenis pengembalian yang disimpulkan dari pernyataan itu dapat digunakan di seluruh fungsi, termasuk dalam pernyataan pengembalian lainnya.

Pada dasarnya, pengurangan tipe kembalian lambda dalam bergantung pada dirinya sendiri (entitas yang dinamai di sini adalah operator panggilan) - jadi Anda harus secara eksplisit menyediakan tipe kembalian. Dalam kasus khusus ini, itu tidak mungkin, karena Anda memerlukan jenis lambda bagian dalam tetapi tidak dapat memberi nama. Tetapi ada kasus lain di mana mencoba memaksa lambda rekursif seperti ini, yang bisa berhasil.

Bahkan tanpa itu, Anda memiliki referensi yang menggantung .

Izinkan saya menjelaskan lebih lanjut, setelah berdiskusi dengan seseorang yang jauh lebih pintar (yaitu TC) Ada perbedaan penting antara kode asli (sedikit dikurangi) dan versi baru yang diusulkan (juga dikurangi):

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

Dan itu adalah ekspresi batin self(self)tidak bergantung f1, tetapi self(self, p)bergantung pada f2. Ketika ekspresi non-dependen, ekspresi tersebut dapat digunakan ... dengan penuh semangat ( [temp.res] / 8 , misalnya bagaimana static_assert(false)hard error terlepas dari apakah template yang ditemukannya itu dibuat instance-nya atau tidak).

Sebab f1, kompiler (seperti, katakanlah, clang) dapat mencoba membuat instance ini dengan bersemangat. Anda tahu jenis deduksi lambda luar setelah Anda mencapai itu ;pada poin di #2atas (ini adalah tipe lambda bagian dalam), tetapi kami mencoba menggunakannya lebih awal dari itu (anggap saja pada titik #1) - kami sedang mencoba untuk menggunakannya saat kita masih mengurai lambda bagian dalam, sebelum kita mengetahui jenis sebenarnya. Itu bertentangan dengan dcl.spec.auto/9.

Namun, karena f2, kita tidak bisa mencoba membuat instantiate dengan bersemangat, karena itu tergantung. Kita hanya dapat memberi contoh pada titik penggunaan, yang pada saat itu kita mengetahui segalanya.

Untuk benar-benar melakukan sesuatu seperti ini, Anda memerlukan kombinator-y . Implementasi dari makalah:

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

Dan yang Anda inginkan adalah:

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

Sunting : Tampaknya ada beberapa kontroversi mengenai apakah konstruksi ini benar-benar valid sesuai spesifikasi C ++. Pendapat yang berlaku sepertinya tidak valid. Lihat jawaban lainnya untuk pembahasan yang lebih menyeluruh. Sisa dari jawaban ini berlaku jika konstruksinya valid; kode tweak di bawah ini bekerja dengan MSVC ++ dan gcc, dan OP telah memposting kode yang dimodifikasi lebih lanjut yang bekerja dengan clang juga.

Ini adalah perilaku tidak terdefinisi, karena lambda bagian dalam menangkap parameter selfdengan referensi, tetapi selfkeluar dari cakupan setelah returndi baris 7. Jadi, ketika lambda yang dikembalikan dijalankan nanti, itu mengakses referensi ke variabel yang telah keluar dari ruang lingkup.

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

Menjalankan program dengan valgrindmenggambarkan ini:

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

Alih-alih, Anda dapat mengubah lambda luar untuk mengambil sendiri dengan referensi alih-alih berdasarkan nilai, sehingga menghindari banyak salinan yang tidak perlu dan juga menyelesaikan masalah:

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

Ini bekerja:

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

dentang benar.

Sepertinya bagian dari standar yang membuat bentuk buruk ini adalah [dcl.spec.auto] p9 :

Jika nama entitas dengan jenis tempat penampung yang tidak dikurangi muncul dalam ekspresi, programnya salah bentuk. Namun, setelah pernyataan pengembalian yang tidak dibuang telah terlihat dalam suatu fungsi, jenis pengembalian yang disimpulkan dari pernyataan itu dapat digunakan di seluruh fungsi, termasuk dalam pernyataan pengembalian lainnya. [Contoh:

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
}

—Dan contoh]

Pekerjaan asli melalui

Jika kita melihat proposal A Proposal untuk Menambahkan Y Combinator ke Perpustakaan Standar, ini memberikan solusi yang berfungsi:

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

dan secara eksplisit mengatakan contoh Anda tidak mungkin:

C ++ 11/14 lambda tidak mendorong rekursi: tidak ada cara untuk mereferensikan objek lambda dari badan fungsi lambda.

dan merujuk pada diskusi di mana Richard Smith menyinggung kesalahan yang diberikan oleh clang kepada Anda :

Saya pikir ini akan lebih baik sebagai fitur bahasa kelas satu. Saya kehabisan waktu untuk pertemuan pra-Kona, tetapi saya bermaksud menulis makalah untuk memungkinkan pemberian nama pada lambda (tercakup dalam tubuhnya sendiri):

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

Di sini, 'fib' setara dengan lambda * this (dengan beberapa aturan khusus yang mengganggu untuk memungkinkan ini bekerja meskipun jenis penutupan lambda tidak lengkap).

Barry mengarahkan saya ke proposal tindak lanjut Lambda rekursif yang menjelaskan mengapa hal ini tidak mungkin dan bekerja di sekitar dcl.spec.auto#9batasan dan juga menunjukkan metode untuk mencapai ini hari ini tanpanya:

Lambdas adalah alat yang berguna untuk pemfaktoran ulang kode lokal. Namun, terkadang kami ingin menggunakan lambda dari dalam dirinya sendiri, baik untuk mengizinkan rekursi langsung atau untuk mengizinkan penutupan didaftarkan sebagai kelanjutan. Ini sangat sulit dilakukan dengan baik dalam C ++ saat ini.

Contoh:

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

}

Salah satu upaya alami untuk mereferensikan lambda dari dirinya sendiri adalah menyimpannya dalam variabel dan menangkap variabel itu dengan referensi:

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

Namun, ini tidak mungkin karena sirkularitas semantik : jenis variabel otomatis tidak disimpulkan sampai setelah ekspresi lambda diproses, yang berarti ekspresi lambda tidak dapat mereferensikan variabel.

Pendekatan alami lainnya adalah dengan menggunakan std :: function:

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

Pendekatan ini mengkompilasi, tetapi biasanya memperkenalkan penalti abstraksi: std :: function mungkin menimbulkan alokasi memori dan pemanggilan lambda biasanya akan memerlukan panggilan tidak langsung.

Untuk solusi overhead-nol, seringkali tidak ada pendekatan yang lebih baik daripada mendefinisikan tipe kelas lokal secara eksplisit.

Sepertinya dentang itu benar. Pertimbangkan contoh yang disederhanakan:

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

Mari kita bahas seperti kompiler (sedikit):

• Jenisnya itadalah Lambda1dengan operator panggilan template.
• it(it); memicu instansiasi operator panggilan
• Jenis kembalian dari operator panggilan template adalah auto, jadi kita harus menyimpulkannya.
• Kami mengembalikan lambda yang menangkap parameter tipe pertama Lambda1.
• Lambda itu juga memiliki operator panggilan yang mengembalikan tipe pemanggilan self(self)
• Perhatikan: self(self)persis seperti yang kita mulai!

Dengan demikian, jenisnya tidak dapat disimpulkan.

Nah, kode Anda tidak berfungsi. Tapi ini memang:

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

Kode tes:

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

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

Kode Anda adalah UB dan berformat buruk, tidak diperlukan diagnostik. Yang lucu; tetapi keduanya bisa diperbaiki secara independen.

Pertama, UB:

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

ini adalah UB karena bagian luar diambil selfoleh nilai, kemudian bagian dalam ditangkap selfdengan referensi, kemudian dilanjutkan untuk mengembalikannya setelah outerselesai dijalankan. Jadi segfaulting sudah pasti ok.

Cara mengatasinya:

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

Kode tetap berbentuk buruk. Untuk melihat ini, kami dapat memperluas lambda:

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

ini contoh __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;
};

Jadi selanjutnya kita harus menentukan jenis kembalian __outer_lambda__::operator().

Kami melewatinya baris demi baris. Pertama kita buat __inner_lambda__tipe:

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

Sekarang, lihat di sana - jenis kembaliannya adalah self(self), atau __outer_lambda__(__outer_lambda__ const&). Tapi kami sedang mencoba menyimpulkan jenis pengembalian __outer_lambda__::operator()(__outer_lambda__).

Anda tidak diizinkan melakukan itu.

Meskipun pada kenyataannya tipe kembalian __outer_lambda__::operator()(__outer_lambda__)sebenarnya tidak bergantung pada tipe kembalian __inner_lambda__::operator()(int), C ++ tidak peduli saat mengurangi tipe kembalian; itu hanya memeriksa kode baris demi baris.

Dan self(self)digunakan sebelum kami menyimpulkannya. Program yang buruk.

Kita bisa menambalnya dengan bersembunyi self(self)sampai nanti:

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

dan sekarang kodenya benar dan terkompilasi. Tapi saya pikir ini sedikit hack; cukup gunakan ycombinator.

Cukup mudah untuk menulis ulang kode dalam istilah kelas yang kompilator akan, atau lebih tepatnya, menghasilkan untuk ekspresi lambda.

Setelah selesai, jelas bahwa masalah utamanya hanyalah referensi yang menggantung, dan kompiler yang tidak menerima kode tersebut agak tertantang di departemen lambda.

Penulisan ulang menunjukkan bahwa tidak ada dependensi melingkar.

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

Versi template penuh untuk mencerminkan cara lambda bagian dalam dalam kode asli, menangkap item yang berjenis template:

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

Saya rasa template dalam mesin internal inilah, yang dirancang untuk dilarang oleh aturan formal. Jika mereka melarang konstruksi aslinya.