Lambda回归自己:这合法吗?

程序格式不正确(叮当声是对的) [dcl.spec.auto]/9 :

如果表达式中出现具有未缩减占位符类型的实体的名称,则程序的格式不正确。但是,一旦在函数中看到未丢弃的返回语句,从该语句派生的返回类型就可以在函数的其余部分使用,包括在其他返回语句中。

基本上,内部lambda的返回类型的推导取决于它本身(这里命名的实体是call操作符),因此必须显式地提供一个返回类型。在这种特殊情况下,这是不可能的,因为您需要内部lambda的类型,但无法命名它。但是在其他一些情况下,像这样强制递归lambda是可行的。

即使没有这个,你也有一个 dangling reference .

让我再详细说明一下,在与更聪明的人(即T.C.)讨论之后,原始代码(略微缩减)和提议的新版本(同样缩减)之间有一个重要的区别:

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

这就是内心的表达 self(self) f1 ,但是 self(self, p) 依赖于 f2 . 当表达式不相关时,可以使用。。。急切地( [temp.res]/8 static_assert(false) 是一个硬错误,不管它所在的模板是否实例化)。

为了 ,编译器(比如说,clang)可以尝试急切地实例化它。你知道,一旦你到了那一步,外λ的推导类型 ; #2 上面(这是内部lambda的类型),但是我们尝试更早地使用它(把它当作一个点) #1

f2层 ,我们不能急于实例化,因为它是依赖的。我们只能在使用点实例化,到那时我们就知道了一切。

y-combinator . 论文的实施:

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

你想要的是:

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

: 这个构造是否严格按照C++规范似乎有争议。主流观点似乎认为这是无效的。有关更深入的讨论,请参阅其他答案。这个答案的其余部分适用 如果 这个构造是有效的;下面经过调整的代码可以与MSVC++和gcc一起使用,OP发布了进一步修改的代码,也可以与clang一起使用。

这是未定义的行为,因为内部lambda捕获参数 self 通过引用,但是 自己 超出范围 return 在7号线上。因此,当稍后执行返回的lambda时,它正在访问对超出范围的变量的引用。

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

valgrind 说明了这一点:

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

相反,您可以将外部lambda更改为通过引用而不是通过值获取self,从而避免了一堆不必要的副本,同时也解决了问题:

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

这样做有效:

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

叮当声是正确的。

看起来标准中导致这种格式错误的部分是 [dcl.spec.auto]p9 :

如果表达式中出现具有未减少占位符类型的实体的名称,则程序将失败 病态的。 可以在函数的其余部分(包括其他返回语句)中使用从该语句派生的。 [示例:

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
}

[结束示例]

如果我们看看这个提议 A Proposal to Add Y Combinator to the Standard Library 它提供了一个有效的解决方案:

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

C++ 11/14 lambdas不鼓励递归:没有办法从lambda函数的体中引用lambda对象。

它引用了一个 dicussion in which Richard Smith alludes to the error that clang is giving you :

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

Recursive lambdas 这就解释了为什么这是不可能的,并围绕 dcl.spec.auto#9 限制,并展示了在没有限制的情况下实现这一目标的方法:

例子:

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

}

从lambda自身引用lambda的一种自然尝试是将其存储在变量中并通过引用捕获该变量:

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

然而,这是不可能的,因为语义循环

另一种自然的方法是使用std::函数:

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

这种方法可以编译,但通常会引入抽象惩罚:std::函数可能会导致内存分配,而lambda的调用通常需要间接调用。

看来叮当声是对的。考虑一个简化的例子:

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

让我们像一个编译器(一点)一样来研究它:

• 类型 it 是 Lambda1
• it(it); 触发调用运算符的实例化
• 模板调用运算符的返回类型为 auto
• 我们返回一个lambda,它捕获类型的第一个参数 λ1 .
• self(self)
• 注意: 自我(self) 这正是我们的出发点!

嗯,你的代码不起作用。但事实上:

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

测试代码:

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

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

您的代码是UB和格式错误,不需要诊断。这很有趣,但两者都可以独立修复。

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

self 通过值,然后内部捕获 自己 outer 完成跑步。所以断层绝对是可以的。

解决方法:

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

代码格式错误。要了解这一点,我们可以展开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);

这将实例化 __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;
};

__outer_lambda__::operator() .

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

self(self) __outer_lambda__(__outer_lambda__ const&) . 但我们正在努力推断 __outer_lambda__::operator()(__outer_lambda__) .

你不能那样做。

__外部λ::运算符()(\uu外部λ) 实际上并不依赖于 __inner_lambda__::operator()(int) C++在推导返回类型时不关心,它只是逐行检查代码。

自我(self) 在我们推断之前就用过了。格式错误的程序。

自我(self) 直到后来:

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

完成后,很明显主要的问题只是悬而未决的引用,而不接受代码的编译器在lambda部门受到了一些挑战。

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

一个完全模板化的版本,反映了原始代码中的内部lambda捕获模板化类型项的方式:

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

我猜这是内部机制中的模板,正式的规则是被设计来禁止的。如果他们真的禁止原来的建筑。