Lambda 返回自身：这合法吗？

编辑：关于这种结构是否严格符合 C++ 规范，似乎存在一些争议。普遍的看法似乎是它无效。请参阅其他答案以获取更深入的讨论。如果结构有效，则此答案的其余部分适用;下面调整后的代码适用于 MSVC++ 和 gcc，并且 OP 发布了进一步修改的代码，这些代码也适用于 clang。

这是未定义的行为，因为内部 lambda 通过引用捕获参数，但在第 7 行之后超出范围。因此，当稍后执行返回的 lambda 时，它正在访问对超出范围的变量的引用。selfselfreturn

#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

看来咔嚓声是对的。考虑一个简化的例子：

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

让我们像编译器一样浏览它（一点点）：

• 的类型是带有模板调用运算符的。itLambda1
• it(it);触发调用操作员的实例化
• 模板调用算子的返回类型是 ，所以我们必须推导它。auto
• 我们返回一个 lambda 捕获 type 的第一个参数。Lambda1
• 该 lambda 也有一个调用运算符，它返回调用的类型self(self)
• 注意：这正是我们开始的！self(self)

因此，无法推断出类型。

根据 [dcl.spec.auto]/9，程序格式不正确（clang 是正确的）：

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

基本上，内部 lambda 的返回类型的推导取决于自身（此处命名的实体是调用运算符）——因此您必须显式提供返回类型。在这种特殊情况下，这是不可能的，因为您需要内部 lambda 的类型，但无法命名它。但是在其他情况下，尝试像这样强制递归 lambda 是可行的。

即使没有它，你也有一个悬而未决的参考。

---

在与更聪明的人（即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);

也就是说，内部表达式不依赖于 ，而是依赖于 。当表达式是非依赖的时，可以使用它们...急切地（[temp.res]/8，例如，无论它所在的模板是否被实例化，硬错误如何）。self(self)f1self(self, p)f2static_assert(false)

对于 ，编译器（比如 clang）可以尝试热切地实例化它。一旦你在上面的点上得到它，你就知道了外部 lambda 的推导类型（它是内部 lambda 的类型），但我们试图更早地使用它（把它想象成点）——我们试图在我们还在解析内部 lambda 时使用它，然后我们知道它的类型到底是什么。这与 dcl.spec.auto/9 相冲突。f1;#2#1

但是，对于 ，我们不能尝试急切地实例化，因为它是依赖的。我们只能在使用点进行实例化，到那时我们就知道了一切。f2

---

为了真正做这样的事情，你需要一个 y 组合器。从论文中可以看出：

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

TL;博士;

clang是正确的。

看起来使这种格式不正确的标准部分是 [dcl.spec.auto]p9：

如果表达式中出现具有未推导占位符类型的实体的名称，则程序为 格式错误。但是，一旦在函数中看到未丢弃的 return 语句，返回类型 从该语句推导出的可以在函数的其余部分使用，包括在其他 return 语句中。 [ 示例：

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 lambda 不鼓励递归：无法从 lambda 函数的主体中引用 lambda 对象。

它引用了理查德·史密斯（Richard Smith）的论证，其中暗示了clang给你的错误：

我认为这作为一流的语言功能会更好。我没有时间参加 Kona 之前的会议，但我打算写一篇论文，允许给 lambda 起一个名字（范围限定在它自己的身体）：

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

在这里，“fib”等价于 lambda 的 *this（尽管 lambda 的闭包类型不完整，但有一些令人讨厌的特殊规则允许它工作）。

Barry 向我指出了后续提案 Recursive lambdas，它解释了为什么这是不可能的，并绕过了限制，还展示了今天在没有它的情况下实现这一目标的方法：dcl.spec.auto#9

Lambda 是用于本地代码重构的有用工具。但是，我们有时希望从内部使用 lambda，以允许直接递归或允许将闭包注册为延续。这在当前的 C++ 中很难很好地完成。

例：

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

}

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

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

但是，由于语义循环，这是不可能的：直到处理 lambda 表达式之后才会推断出 auto 变量的类型，这意味着 lambda 表达式无法引用该变量。

另一种自然的方法是使用 std：：function：

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

这种方法可以编译，但通常会引入抽象惩罚：std：：function 可能会产生内存分配，并且 lambda 的调用通常需要间接调用。

对于零开销解决方案，通常没有比显式定义本地类类型更好的方法了。

根据编译器将为 lambda 表达式生成的类（或者更确切地说应该）重写代码很容易。

完成此操作后，很明显，主要问题只是悬空的引用，并且不接受代码的编译器在 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);
}

我猜想，正是这种内部机制中的模板，正式规则旨在禁止。如果他们确实禁止原始结构。

好吧，你的代码不起作用。但这确实：

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 又格式错误，无需诊断。这很有趣;但两者都可以独立修复。

首先，UB：

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

这是 UB，因为 Outer 按值获取，然后 Inside 通过引用捕获，然后在完成运行后继续返回它。所以段错误是绝对可以的。selfselfouter

修复：

[&](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__)

你不被允许这样做。

虽然实际上 的返回类型实际上并不依赖于 的返回类型，但 C++ 在推断返回类型时并不关心;它只是逐行检查代码。__outer_lambda__::operator()(__outer_lambda__)__inner_lambda__::operator()(int)

并在我们推论之前使用。格式不正确的程序。self(self)

我们可以通过隐藏到以后来修补它：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);
}

现在代码是正确的并编译了。但我认为这有点黑客;只需使用 YCOMBINATOR。